Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Security Encryption

New Attack Against Multiple Encryption Functions 130

Posted by kdawson 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."
This discussion has been archived. No new comments can be posted.

New Attack Against Multiple Encryption Functions More

New Attack Against Multiple Encryption Functions

Comments Filter:

  • Ha! I'm immune! (Score:5, Funny)

    by DikSeaCup ( 767041 ) on Friday August 22, 2008 @10:59AM (#24705853) Homepage
    I store all of my passwords in plain text!

  • news at 11? (Score:1, Redundant)

    by Zironic ( 1112127 )

    Low degree polynomals are relatively easy to crack, news at 11?

    I thought most people used RSA nowadays because of it's mathematical ubreakability. (Huge polynomal):

    Breaking of the stream ciphers can be a problem though.

    • RSA is a public-key cipher. They usually don't get used directly because they're much more expensive computationally than AES and the like, and potentially vulnerable to chosen-plaintext attacks. Real protocols like SSL typically use a public-key cipher like RSA or DSA to negotiate a shared secret key and perform authentication, and then switch to a symmetric cipher like AES or IDEA.
      • They usually don't get used directly because they're much more expensive computationally than AES and the like, and potentially vulnerable to chosen-plaintext attacks.

        I was with you up until the last bit. Do you have any information regarding public-key ciphers being vulnerable to chosen plaintext attacks? And which of the various public-key encryption algorithms are vulnerable?

        • All of them are vulnerable. If you have a ciphertext, and you know the public key, you can just try brute-forcing the space of plaintexts rather than the space of keys, which may be much smaller, especially if the plaintexts all have a known form. Effectively, the fact that the public key must be public gives an attacker the ability to encrypt an unlimited number of chosen plaintexts.

          If you use the public-key algorithm to encrypt a randomly generated secret key, and then switch to a secret-key cipher, the

          • Re: (Score:1)

            by bbhack ( 98541 )

            Effectively, the fact that the public key must be public gives an attacker the ability to encrypt an unlimited number of chosen plaintexts.

            Uhm, no, I don't think so. There is not symmetry between the encryption by private key and by public key. You cannot search for a ciphertext match by bruteforce plaintext + pubkey.

            You may be on to something, but please explain more.

            IANAC

            • Suppose Alice sends a message to Bob and encrypts it with Bob's public key. You're trying to intercept that message, and get to see the ciphertext, and you also get to see Bob's public key. If you knew Bob's private key you could decrypt the message and get the plaintext just like he does, but it'd take an unreasonably large amount of processor time to compute his private key from his public key, so you can't do that. If you know the space of possible plaintexts is relatively small, though, you can try e

              • With that aproach you still never get the secret key, you only become able to read small messages since the space of plaintexts is actually gargantuan.

                The users of a public key algorithm can also protect themselves by just adding random noise to their messages.

                • Re: (Score:1)

                  by bbhack ( 98541 )

                  The users of a public key algorithm can also protect themselves by just adding random noise to their messages.

                  Correct. I was thinking of signing, and I had things backwards, but by injecting entropy into the encryption by public key, chosen plaintext attack becomes "hard". In fact, this is not optional.

  • DES, AES, Blowshifh, twofish likely immune (Score:4, Informative)

    by Hoplite3 ( 671379 ) on Friday August 22, 2008 @11:05AM (#24705939)

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

  • Nice use of language (Score:3, Informative)

    by gazbo ( 517111 ) on Friday August 22, 2008 @11:06AM (#24705965)
    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?

  • Correct the summary/FUD (Score:5, Informative)

    by trifish ( 826353 ) on Friday August 22, 2008 @11:09AM (#24706011)

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

    • Re: (Score:3, Interesting)

      by Kjella ( 173770 )

      Here's the bane of reliable internet news. I now predict have a kazillion stories like "OMG the sky is falling" on the news sites I visit because they produce way more hits than "completely irrelevant theoretical crypto-attack found". It's really that simple, I think even if they KNOW the story is bogus it's better to get the headliner and then make a "correction" later.

      • Re: (Score:2)

        by trifish ( 826353 )

        Yes. The sad truth is that even the researchers themselves engage in FUD spreading. It is much easier to get publicity if you claim "I can break anything (but wait 2 weeks for the full details)." When those full details are revealed (i.e. the fact that there is no real attack is implicitly contained in the paper) it is already too late to undo the FUD. Nobody really cares.

      • Re: (Score:2)

        by lgw ( 121541 )

        What part of this is specifi to internet news. This isn't news, this is CNN!

    • Re:Correct the summary/FUD (Score:5, Informative)

      by secPM_MS ( 1081961 ) on Friday August 22, 2008 @11:44AM (#24706609)
      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 (Score:4, Interesting)

        by CodeBuster ( 516420 ) on Friday August 22, 2008 @12:23PM (#24707259)

        That said, the algebraic degree associated with modern block codes is far beyond this.

        Would not a modern block cipher, AES for example, be of at least order 128 or possibly higher with at least as many variables? It was also mentioned in the summary of TFA that older or lower power devices might be vulnerable, but really where are these devices being used right now? It has been my experience that if something is encrypted at all (i.e. someone actually bothered to think about security) then a stronger algorithm is generally selected (AES, 3-DES, Twofish, etc...); otherwise, and this happens all too often, encryption is simply not employed even though it easily could have been and probably should have been.

        • Re:Correct the summary/FUD (Score:4, Informative)

          by swillden ( 191260 ) <shawn-ds@willden.org> on Friday August 22, 2008 @01:33PM (#24708465) Journal

          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: (Score:2)

        by trifish ( 826353 )

        Your post, sir, is as misleading as the Computerworld article. Was the ambiguity in it deliberate or unintentional? I hope the latter.

    • .. (or be a uninformed FUD spreader like Computerworld)

      That was completely uncalled for. What has Computerworld done to deserve being compared to kdawson?

    • Re: (Score:2)

      by fermion ( 181285 )
      further comments suggest that it might be used against systems with weaker protection, such as HDTV, bluetooth, mobile telephone networks. So no, the secure stuff is still secure. In any case, the secure stuff is seldom broken by breaking the encryption. The secure stuff is broken by social and other backdoor attacks.
    • Well, seeing as kdawson is the editor, I'm not surprised at the summary's inaccuracy.
  • My understanding is that this is the big issue about mathematical attacks: They depend on the encryption method. If you merely encrypt things more than once, using two or more different encryption methods, the chances there will ever be a successful mathematical attack are very, very small.

    I have an enormous amount of respect for Bruce Schneier, but his writing is designed to get him business, not to give easy answers to big problems.

    I recommend GNU Privacy Guard [gnupg.org].

    • Re:Use two different encryption methods. (Score:4, Informative)

      by Zironic ( 1112127 ) on Friday August 22, 2008 @11:18AM (#24706185)

      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.

      • I think my point is correct: It is very unlikely that two different very strong encryption methods will be cracked at the same time. So using two or more, even if the methods and their order are known by an attacker, provides protection against attack.

        You said, "... it's impossible to create an attack that can target any encryption..." That's part of what I was saying.

        And my comment should not have been moderated Redundant, since all the comments posted before it were just junk when it was posted.

        • Re: (Score:2)

          by flonker ( 526111 )

          Actually, the security of using two encryption methods is not fully additive as you would assume. (Security refers to the amount of time required to crack the message.)

          If you use the same key for both encryption methods, it may actually be less secure. (ie. The old ROT13 twice joke.)

          If you use two different keys, the security of the resultant encryption has a minimum security of the stronger of the two algorithm/keys, and in a perfect case, the maximum security is simply the security of the first protocol

    • Re: (Score:3, Funny)

      by TMB ( 70166 )

      That's why I use rot13 not once, but twice!

      • Re: (Score:2)

        by pjt33 ( 739471 )
        I use it three times, in encrypt-decrypt-encrypt mode. It works for DES, so it must be good!

    • Re:Use two different encryption methods. (Score:4, Insightful)

      by moderatorrater ( 1095745 ) on Friday August 22, 2008 @11:52AM (#24706731)

      I have an enormous amount of respect for Bruce Schneier, but his writing is designed to get him business, not to give easy answers to big problems.

      umm, easy answers to big problems? There are none, sir, and while bruce does occasionally plug his own products, I've never thought that he was just into it to make money. Reading his blog is the most informative part of my day.

      Besides, we all know that his real reason for blogging is to help squid become the dominant species on the planet like they were intended to be.

    • Re: (Score:2)

      by Detritus ( 11846 )
      Bad assumption. The composition of two ciphers can be treated as a third cipher, which may not be any stronger than its parents, and can even be weaker. The attacker is not obligated to solve the system in the same sequence that was used to encrypt the plaintext.

      • Re: (Score:2)

        by marxmarv ( 30295 )

        Bad assumption. The composition of two ciphers can be treated as a third cipher, which may not be any stronger than its parents, and can even be weaker.

        Other than the frankly incompetent cases of using two ciphers composed with the same key, or including known plaintext in the inner ciphertext, when has such a weakness been observed?

        The attacker is not obligated to solve the system in the same sequence that was used to encrypt the plaintext.

        I agree that the composite cipher may well be weaker than the sum of its parents. As the composite cipher may contain redundancies that can be optimized away, so too would the attack. However, I don't see why a composed cipher, with each component keyed separately, would not be much stronger than the strongest of its parents.


    • If you merely encrypt things more than once, using two or more different encryption methods, the chances there will ever be a successful mathematical attack are very, very small.
      Maybe. The fact that nobody really does this is a strong indication that this isn't as good a solution as you might think it is though.

      The encryption algorithm itself is likely the strongest part of your whole system anyway. Most of the time the attacks on the system don't completely break it open and make it useless. The weak pa

  • Quick, apply DMCA! (Score:2, Insightful)

    by Anonymous Coward

    Ban the Math, it's a circumvention tool.

  • I'm no crypto guru, but I have read Schneier's Applied Cryptography and have read various papers describing cryptographic primitives. Looking at the blog entry (yes, I do read Slashdot for its articles), the paper hasn't been published yet. We don't know, at this point, whether this is a theoretical attack or a practical attack.

    It doesn't affect AES; it may or may not affect RC4, which is pretty widely used. What it appears to affect is Radio Gatun, a nice, fairly new construction that can either be

  • An order of magnitude improvement in cracking a 56bit key would be significant. However, most of us use far greater key-spaces and only flaws in the crypto itself or the container is the real threat. It is however interesting when anybody can make a massive improvement in cryptoanalysis. A 10x improvement would make cracking 40bit 'consumer-grade' (such as GSM and DECT) crypto trivial on the latest processors. The most likely application is to give governments easy access to snoop 'private' phone and data conversations.

    This is not threatening to me at all. I don't really see the need to encrypt phone calls in the first place. It is absolutely essential to encrypt other data. This seems to be because there is a social taboo about tapping phones, but not so much so with data. Therefore all system admins must use SSH and others should consider it too.

    The real threat is the quantum computer, if it exists in a practical form. If that is the case, there is one complete solution -- The awkward 'one-time pad'.

    • Re:The synopsis stated "low grade" crypto (Score:5, Insightful)

      by eudaemon ( 320983 ) on Friday August 22, 2008 @11:36AM (#24706469)

      The reason to casually encrypt phone calls or any other data is to prevent the casual snooping of same.

      Look at this way -- the barrier to entry for snooping your data is very low, and getting lower with each
      new executive order. On the other hand the barrier to entry on snooping your data can be set arbitrarily high;
      you can choose anything from 56 bit single-DES to 2048 bit RC4. The effort required to casually snoop you for
      no other reason has now exploded. It was fear of people adopting this strategy and blocking the casual snooping
      that inspired the clipper chip. It was the people's laziness, ignorance or both towards protecting their privacy
      and their fear of terror that has eroded any expectation of privacy now, which is truly unfortunate.

      If we had an expectation of privacy in this country, I think things would be very different now with regards to
      all the second order effects such as identity theft.

      • The barrier to entry for snooping your data is very low, and getting lower with each
        new executive order. On the other hand the barrier to entry on snooping your data can be set arbitrarily high;
        you can choose anything from 56 bit single-DES to 2048 bit RC4.

        I find this point fascinating, actually. It has never been easier to provably hide information, even as the social safeguards protecting privacy are being systematically dismantled.

        In some ways, each of those Executive Orders is doing us a favor, by telling us again and again, "Encrypt your communications, or keep your trap shut."

    • A 10x improvement would make cracking 40bit 'consumer-grade' (such as GSM and DECT) crypto trivial on the latest processors. The most likely application is to give governments easy access to snoop 'private' phone and data conversations.

      Governments either tap unencrypted GSM conversations at the basestation or have custom hardware to break 40 bit encryption. Or both probably.

    • Re: (Score:2)

      by thogard ( 43403 )

      40 bit DES is already in the realm of home machines. The problem isn't trying all the 2^40 key combinations but detecting when one of them gives you the right key. If you know the plain text is most likly ASCII, then you can check that the top bits of a block are all zeros but then you still have to have another way to process the 2^32 results that pass the 1st test. The more you know about the plain text the more false results you can discard but there still may be loads of other keys that might look ri

    • Imagine a beowoulf cluster of quantum computers!

    • The real threat is the quantum computer, if it exists in a practical form. If that is the case, there is one complete solution -- The awkward 'one-time pad'.

      I use a "one-time pad" for all my account logins.

      A Post-it note counts as a one-time pad, right?

    • The real threat is the quantum computer, if it exists in a practical form.

      Incorrect. No one has demonstrated any way to use a quantum computer (even if one existed) to break a symmetric block cipher like AES or DES. Shor's algorithm allows a quantum computer to factor large numbers quickly, which would destroy RSA, and it seems likely that similar approaches might be used to attack other public-key algorithms.

      Public key cryptography is useful for easing the key distribution problem, but it's not essential to most uses of cryptography.

    • Re: (Score:1)

      by rjhubs ( 929158 )

      As others have mentioned, this is not an attack on the key space, so the size of your key won't matter. Rather it is an attack on the algorithm itself, which is more like saying, this analysis will make the algorithm not so 'random'.

      From my small understanding of cryptography and the vague article is that some ciphers can be represented in a polynomial form. I remember in my crypto class we were shown how to figure out the polynomial of one of the algorithms but i've long forgotten it. But anyways, cryp

    • Re: (Score:2)

      by Prune ( 557140 )

      The real threat is the quantum computer, if it exists in a practical form. If that is the case, there is one complete solution -- The awkward 'one-time pad'.

      Nonsense. There are many quantum-resistant encryption algorithms (such as most of the symmetric encryption ones).

  • Why is 'low-degree polynomial equation' in quotes? These are the things every high school and middle school student studies; it's not some exotic term.

    • Re: (Score:2)

      by u38cg ( 607297 )
      Well, given that Taco & co can't manage to add up the number of people who wish idle./. would go the f*** away, I think it's safe to assume that 'low-degree polynomial equation' is pretty scary biscuits from their point of view.

  • "Cube" attack (Score:2, Redundant)

    by dpilot ( 134227 )

    TFA (I read it a day or two ago, before it was posted to Slashdot.) mentions this as a "cube" attack, along with the low-order polynomial stuff, etc.

    Does this also mean that TIMECUBE is busted?
    I know it's been a while since TIMECUBE reared its ugly head here, but it would be good to hear that it's fully busted, not just sleeping.

    (For the humor impaired, I know the cube attack has nothing to do with TIMECUBE other than sharing 4 letters, but it seemed like a neat idea.)

  • I've recently come across a situation where my client's data is being held hostage by their application vendor. The vendor decided to encrypt the data during one of their 'upgrades' and now that the client wants to move to another application, the vendor won't decrypt the data without being paid a huge fee. They probably used something easy like an XOR cipher but I don't have the time to research how to figure this out. Are there any tools out there that I can use to give a sample of the encrypted data and
    • Such a situation would be illegal in most countries, time for court. BTW, next time use ant-virus as I am aware that you have been infected by an encrypting virus and the writers want money to decrypt your data, you were just too embarrassed to tell the truth.

  • Cube attack in detail... (Score:4, Funny)

    by Anonymous Coward on Friday August 22, 2008 @12:03PM (#24706923)

    ENCRYPTION IS CUBE
    cube have 4 sides
    1 side = 1 encryption stage
    ENCRYPTION STAGE IS TIME
    TIME IS CUBE
    THEREFORE ENCRYPTION = TIME
    time slowed by day/night on planet corners
    move algorythm to cube corners to solve in limited time
    move algorithm to cube centers to unsolve in unlimited time.

  • From a public policy perspective: This post reminds us that cryptography is a dynamic and sometimes surprising science. The implication is that to achieve data security with cryptography is not just a simple task. But politicians have recently been writing laws and regulations with the assumption that to "encrypt" data is the end-all be-all of data security. It is not. Lawmakers are unwise [blogspot.com] to require a specific technology like "encryption" for data security. --Ben Wright http://hack-igations.blogspot [blogspot.com]

  • It will be interesting to see the full paper (Score:5, Insightful)

    by wirelessbuzzers ( 552513 ) on Friday August 22, 2008 @12:51PM (#24707691)

    I saw the talk. The cube attack was very impressive: it allowed Shamir to break a fairly difficult-looking toy cipher (constructed, of course, to have an Achilles heel, but still probably impossible to break with other known techniques). He used only one bit per packet (with a million packets) and didn't use any particular knowledge of the cipher's internals.

    However, as presented the attack probably only breaks toy examples. Its real-world applicability will depend on how well Shamir and Dinur manage to adapt it to ciphers which don't have this simple structure. For example, it will be difficult to apply the attack to either hash functions or block ciphers, because their iterated design tends to give them high degree. The attack will also be difficult to adapt because of its low tolerance for noise and its applicability to a narrow range of scenarios. Still, Shamir believes that it will be applicable at least to some modern stream ciphers, so I'll be keeping an eye out for the full version.

    • I was at the talk as well. It look like the technique will be applicable to a number of LFSRs, but the most interesting thing I saw was that the preprocessing stage lets you figure out whether a cipher is susceptible to the attack without knowing anything about the cipher. The preprocessing stage starts with a guess at the degree of an unknown cipher, and adjusts the guess based on the results of the preprocessing tests.

      Current block ciphers have degrees that are (probably) in the thousands, but hey, if

  • This is just more snake oil bunk that really shows no weakness in modern hash functions or algorithms either one.
  • How many orders of magnitude would one have to increase breaking 256bit Serpent to make it relative to one life time?... :P
  • "And give him head whenever he wants." - Sidney Poitier.

Slashdot Top Deals

One man's constant is another man's variable. -- A.J. Perlis

Close