The 2008 provided a lot to talk about this year. If you didn’t know a Crypto Conference existed, you aren’t alone, but it is where the best and brightest mathematicians gather to discuss cryptographic and cryptoanalytic research. However at this conference Adi Shamir (the “S” in RSA Security that stands for Rivest, Shamir and Adleman and that is now owned by EMC) gave a presentation for a new attack on encryption systems called the “cube attack”. The ramifications of this attack sent a collective shockwave across the data security sector. Since encryption is revered as our best alternative and last safe harbor from data exposure, any weakness shown by encryption algorithms can have a dramatic ripple effect in data security.
The presentation was general as to the details it revealed but the recently published white paper called “Cube Attacks on Tweakable Black Box Polynomials” by Itai Dinur and Adi Shamir provides an in depth look at how this attack is carried out. While I would not assume to describe this type of attack better than the white paper itself, this attack provides an order of magnitude improvement for capturing the encryption key through solving such tweakable polynomials. Tweakable polynomials contain both secret variables, or key bits, and public variables, or plaintext bits.
The two most common types of encryption algorithms are block ciphers, such as AES, and stream ciphers such as Trivium. Block ciphers encrypt data in predefined blocks while stream ciphers encrypt data one bit at a time. Although more susceptible to attack, stream ciphers are widely used due to the dramatic performance gains that they deliver over block ciphers in the encryption and decryption processes.
The cube attack shows a dramatic improvement in attacking low polynomial algorithms of which stream ciphers are comprised. Conversely block ciphers polynomials grow exponentially with the number of rounds. A round is considered the specific sequence transformation process plaintext data goes through to perform encryption. The number of rounds in an algorithm is dependent upon the key size. For example AES with a 256 bit key has 14 rounds. So, the cube attack would theoretically lack the ability to successfully attack block ciphers. But with that being said there still could be reason to worry for the following reasons:
- Possible order of magnitude improvement over exhaustive and current attack techniques. Shamir theorizes in the paper that the cube attack could be coupled with other attacks such as side-channel, or meet-in-the-middle attacks, to reduce the order of magnitude of cracking block ciphers. This is particularly worrisome due to the wide distribution of AES in both private industry and government. If it is possible to lower the order of magnitude by coupling this attack with a separate attack, then we would have a real reason to worry if the attack were perfected and performed timely. Although Shamir will bring forth more information in a future publication on the meet-in-the-middle coupling within the cube attack, it would seem reasonable that if a reduction in the order of magnitude of attack is accomplished this could be very worrisome to the future security of widely deployed block ciphers.
- Stream Ciphers are all susceptible. Stream ciphers are low polynomial algorithms and are particularly susceptible to the cube attack. Trivium was used as an example since no previous attacks against it had been better than an exhaustive attack. The cube attack showed a dramatic order of magnitude improvement over an exhaustive attack. Shamir’s conclusion is that Trivium is easily breakable. Bottom line there are now serious security concerns regarding the use of stream cipher algorithms.
- LSFR (Linear Shift Feedback Registers) are likely susceptible. LSFR’s are widely used as random bit/number generators in stream ciphers. Everything digital that uses LSFR random generators is therefore susceptible which could affect any of a number of current applications that employ LSFR, such as Bluetooth, GSM and RFID.
The effects of the cube attack are still being worked through and its true effects on the industry are still mostly unknown. But if Shamir’s new attack method plays out (and I have no reason to believe it will not), the viability of stream ciphers are already seriously weakened just by the potential of such a cube attack. Furthermore if in the future it can be shown that mixing the cube attack with other attacks dramatically lowers the order of magnitude in capturing the block cipher encryption key, industry’s last safe harbor might just be a data security bomb shelter.