New attack against multiple encryption functions

Computerworld ^ | 8/22/08 | Carl Jongsma

[LibWhacker]

New mathematical attack works against a broad range cryptographic functions.

Unless you're a dyed in the wool cryptographic geek you probably didn't know that there was a Crypto conference, or even a chain of worldwide crypto conferences that take place each year. Fortunately, for the most of us that aren't crypto geeks there are a handful of very highly skilled people who are; they can take the highly theoretical and complex mathematical proofs and arguments that make up most of modern cryptographic and cryptanalytic research and put it into plain language.

Probably the best known is Bruce Schneier, who is a dedicated crypto geek famous for his general Information Security and cryptographic work; including being responsible (or partly responsible) for ciphers such as Blowfish and Twofish. From his blog he has provided a tantalising suggestion that one of the most famous names in cryptography is introducing a new form of cryptanalysis.

Adi Shamir, who is the S in RSA, has presented material at the Crypto 2008 conference that has promised a new form of mathematical attack against a broad range of cryptographic ciphers, including hash functions (such as MD5, SHA-256), stream ciphers (such as RC4), and block ciphers (such as DES, Triple-DES, AES). 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".

Comments from people who saw the presentation and had a chance to speak with Shamir (drawn from the comments in Schneier's blog) indicate that the new attack method isn't necessarily going to work against the exact ciphers listed above, but it presents 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".

Without access to the paper (expected to be published later this year), the full scope of the discovery can't be easily determined. It may be that it delivers an order of magnitude improvement over existing methods, but implementation will still take such a long period of time that it is effectively impractical for attack against time sensitive content. Then again, it may be that it has brought it into a viable timeframe, something that can be achieved with a handful of modern machines - nothing that is too far out of reach of the motivated and resourced attacker.

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 straight forward mathematical attack. This might mean that some content delivery systems or simple communications channels are now vulnerable to a viable attack, or it could just form the basis of interesting class work for budding cryptographers and cryptanalysts.

Either way, it is something that will be worth watching over the next 12-18 months to see how it evolves.

[CedarDave]

Tech list PING!

[AprilfromTexas]

thanks, keep us posted

[KarlInOhio]

Unless you're a dyed in the wool cryptographic geek you probably didn't know that there was a Crypto conference, or even a chain of worldwide crypto conferences that take place each year.

I've got my invitation right here.

SDASKDIEKDKVSJKDIESLDLKDMVEOOWOOSLLSWNMBVNMZ
AEOIJFKLVIIEIDKBLLPPWJBIWMQMQMNNXNXNXXN
EIIOOFFKMADMBOAPWKMGNWEKBNAEKAMBZXLXKZOPW

If you can't decrypt it, you don't belong at the conference. :-)

[proxy_user]

They don’t mention whether it would work against 256-bit 16-round Blowfish or Twofish.

[willgolfforfood]

"They don’t mention whether it would work against 256-bit 16-round Blowfish or Twofish."

I'm guessing it does NOT.

Really, and I mean REALLY guessing, that's what I'm doing.

[ShadowAce]

[zeugma]

while these attacks may not be practical today, the thing to remember is that they only get better with age.