



Stream Ciphers Cower Before Adi Shamir's CUBE ATTACK 




Swee Won Lo

Date : 20081009 AM 09:54, Hit : 4110 



Adi Shamir brought a big new wrecking ball to bear on stream ciphers at Crypto 2008, the 28th International Cryptology Conference, one that will send architects of the algorithms back to their keyboards.
Cryptographers view stream ciphers as the vanguard of encryption for embedded systems, so Shamir's new class of attack was a "wake up call" for the field, said David Wagner, the conference's program chair and associate professor of computer science at the University of California, Berkeley.
Stream ciphers are applied in devices like cell phones, radio frequency identification (RFID) chips, car key fobs, and other lowend appliances that are not computers per se, but incorporate software.
Shamir and coauthor Itai Dinur presented their "cube attack" in a talk at the conference. While a moredetailed paper is still forthcoming, Shamir and Dinur's work was the talk of the conference. And with good reason: Shamir is cryptographic royalty, having invented the RSA algorithm with Ron Rivest and Leonard Aldeman almost 30 years ago.
Researchers at the conference were stunned with the cube attack's simplicity and efficacy.
Wagner:
"There were lots of people like me who slapped their foreheads and said, 'Why didn't I think of that!'"
Stream ciphers employ symmetric key cryptography, an approach that uses one key for encryption and another closelyrelated key for decryption. The keys are usually so closely related that they are identical, meaning a compromised key can decrypt encrypted information.
"People knew that for some of these stream ciphers, they could express the output as a formula of the key," Wagner said. A given key's formula, though, is complex. As long as the formula was too long to write down  which many are  experts felt the algorithms were secure.
"What Adi discovered is, well, that isn't necessarily so," he said.
Shamir and Dinur noticed patterns in the output of certain keys if the output could be expressed as a polynomial. In its original form, the polynomial is unmanageably long. But their attack helps boil the string of variables down to a smaller, more comprehensible size. The shorter formula then leaks bits of the cryptographic key, Wagner said, enabling an attacker to break the encryption and access the data.
The above excerpt is taken from arstechnica.com and is modified to suit the context in this webpage. For the complete article, please head to arstechnica.com. 








