Slashdot Mirror

← Back to Stories (view on slashdot.org)

New Attack Against Multiple Encryption Functions

Posted by kdawson on from the think-harder dept.

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."

10 of 130 comments (clear)

  1. Re:ehm by moderatorrater · · Score: 5, Informative

    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.

  2. DES, AES, Blowshifh, twofish likely immune by Hoplite3 · · Score: 3, Informative

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

    --
    Use the Firehose to mod down Second Life stories!
    1. Re:DES, AES, Blowshifh, twofish likely immune by Cyberax · · Score: 3, Informative

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

    2. Re:DES, AES, Blowshifh, twofish likely immune by Anonymous Coward · · Score: 5, Informative

      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.

  3. Nice use of language by gazbo · · Score: 3, Informative
    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?

  4. Correct the summary/FUD by trifish · · Score: 5, Informative

    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).

    1. Re:Correct the summary/FUD by secPM_MS · · Score: 5, Informative
      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.

    2. Re:Correct the summary/FUD by swillden · · Score: 3, Informative

      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.

      --
      Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
  5. Re:ehm by beckerist · · Score: 2, Informative

    So long as there are ways to decrypt, there will always be a way to "attack." It isn't necessarily the fault of the algorithm either. Prime example: social engineering.

  6. Re:Use two different encryption methods. by Zironic · · Score: 3, Informative

    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.