New Attack Against Multiple Encryption Functions

An anonymous reader sends word of a paper presented a few days back by Adi Shamir, the S in RSA, that promises a new form of mathematical attack against a broad range of cryptographic ciphers. The computerworld.com.au report leans heavily on Schneier's blog entry from the Crypto 2008 conference and the attached comments. Shamir's paper has not been published yet. "[The new attack could affect] hash functions (such as MD5, SHA-256), stream ciphers (such as RC4), and block ciphers (such as DES, Triple-DES, AES) at the Crypto 2008 conference. The new method of cryptanalysis has been called a 'cube attack' and formed part of Shamir's invited presentation at Crypto 2008 — 'How to solve it: New Techniques in Algebraic Cryptanalysis.' The new attack method isn't necessarily going to work against the exact ciphers listed above, but it offers a new generic attack method that can target basically formed ciphers irrespective of the basic cipher method in use, provided that it can be described in a 'low-degree polynomial equation'... What may be the biggest outcome from this research is the range of devices in widespread use that use weaker cryptographic protection, due to power or size limitations, that are now vulnerable to a straightforward mathematical attack."

Re:ehm

[moderatorrater]

The summary is blatantly wrong. Take a look at the schneier blog post (from 3 days ago) and the second update: this attack only works against LSFR encryption of a low order, which means that none of the schemes mentioned in the summary are actually affected.

Now, if I were to actually RTFA, I would know whether the article was slow on the uptake or slashdot, and whether or not they should have known that the attack wouldn't affect the major algorithms, just smaller ones. Either Slashdot's dead wrong on this or computerworld is, and I'm not sure which one's more likely.

DES, AES, Blowshifh, twofish likely immune

[Hoplite3]

See Schneier's blog. No word on MD5, which is extremely common.

Nice use of language

[gazbo]

Contrast:

[The new attack could affect] hash functions (such as MD5, SHA-256), stream ciphers (such as RC4), and block ciphers (such as DES, Triple-DES, AES)...The new attack method isn't necessarily going to work against the exact ciphers listed above

With:

Okay, he thinks that AES is immune to this attack...And this attack doesn't apply to any block cipher -- DES, AES, Blowfish, Twofish, anything else -- in common use

Slight shift in implications, dontchathink?

Re:DES, AES, Blowshifh, twofish likely immune

[Cyberax]

MD5 is already completely broken: http://en.wikipedia.org/wiki/MD5#History_and_cryptanalysis [wikipedia.org]

Correct the summary/FUD

[trifish]

As Schneier wrote (emphasis mine): "this attack doesn't apply to any block cipher -- DES, AES, Blowfish, Twofish, anything else -- in common use; their degree is much too high." Now, correct the misleading summary (or be uninformed FUD spreader like Computerworld).

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Use two different encryption methods.

[Zironic]

Well, they rely on knowing what method you used but so does any cryptography attack, it's impossible to create an attack that can target any encryption since it's impossible to tell the difference between something encrypted and random noise.

So if the attacker knows you're using two different methods he just has to crack them both one at a time. It's not terribly different from knowing you use one method.

What you're doing is just attempting to practise security through obscurity when you layer encryption on encryption.

Re:Correct the summary/FUD

[secPM_MS]

The "low degree" here may be a bit higher than most readers suspect. The abstract I have for the talk is:

ABSTRACT: In this talk I will describe a new algebraic attack which is very powerful and very general. It can solve large systems of low degree polynomial equations with surprisingly low complexity. For example, solving dense random-looking equations of degree 16 in several thousand variables over GF(2) (which correspond to many types of LFSR-based stream ciphers) can now be practically done in less than 2^{32} complexity by the new technique.

That said, the algebraic degree associated with modern block codes is far beyond this. The possible uility of such approaches in reducing the complexity of collision generation in hashes is yet undetermined.

Re:Correct the summary/FUD

[swillden]

Would not a modern block cipher, AES for example, be of at least order 128 or possibly higher with at least as many variables?

No. When you convert a cipher into a set of polynomial equations, the degree is dependent upon internal details of the cipher. It has nothing to do with the number of bits in the key. For example, I can make a cipher with a 1000-bit key, but a structure that is so simple that it can be represented with a linear function -- degree 1.

Re:DES, AES, Blowshifh, twofish likely immune

[Anonymous Coward]

While finding collisions quickly does indeed show MD5 has weaknesses, no one has found a efficient way to match an existing checksum. For most that's the definition of completely broken.