New Attack Against Multiple Encryption Functions 130
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."
Ha! I'm immune! (Score:5, Funny)
Re:Ha! I'm immune! (Score:5, Funny)
Co-worker: Your password is "flower"?
Me: What? No. It's "zombie clown hitting fish with hammer". What's wrong with you?
Re: (Score:2)
And now to log into your
Hold on, I've got to get this out of my system (Score:5, Funny)
...password ... like 1-2-3-4.
So the combination is one, two, three, four, five? That's the stupidest combination I've ever heard in my life! The kind of thing an idiot would have on his luggage!
Apologies to Rick Moranis and Mel Brooks. [imdb.com]
That said, what's the difference between lower case numbers and upper case numbers?
--sabre86
Re: (Score:1)
That said, what's the difference between lower case numbers and upper case numbers?
Upper case numbers aren't alphanumeric. ;)
Re: (Score:3, Funny)
Wow! Cool! Me too! I have 5 different inkblots for logging into five different systems.
All five passwords are "Boobies".
-
Re: (Score:1)
Re:Ha! I'm immune! (Score:5, Funny)
Me too. It's ******
Re:Ha! I'm immune! (Score:5, Funny)
Re:Ha! I'm immune! (Score:4, Funny)
No you moron, that's my password!
Re: (Score:2)
The new slashcode will replace your password with asterisks if you type it out in a comment.
Here's mine: **********
See?
Give it a try.
Re: (Score:1)
news at 11? (Score:1, Redundant)
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.
Re: (Score:2)
Re: (Score:2)
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?
Re: (Score:2)
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)
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
Re: (Score:2)
Re: (Score:2)
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)
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.
Re: (Score:3, Insightful)
Solution 1: x = 1
Solution 2: x = -1
Solution 3: x = BUFFER OVERFLOW
%#$%#%#%#%##%%$$
Re: (Score:1)
uh...
X^2 = 1 % big number.
big number > 1; 1 % big number = 1.
X^2 = 1 % big number == X^2 = 1
X^2 = 1
X = +/- 1 ?
What?
What voodoo are you assuming that gets 4 solutions?
Re: (Score:1)
Re: (Score:1)
There is 1 solution to m mod n.
8 mod 2 = 0.
13 mod 4 = 1.
27 mod 5 = 2.
"X^2 = 9 = 1 mod 8"
9 != 1 mod 8
1 mod 8 = 1
Modulooooooooooooo?
DES, AES, Blowshifh, twofish likely immune (Score:4, Informative)
See Schneier's blog. No word on MD5, which is extremely common.
Re: (Score:3, Informative)
MD5 is already completely broken: http://en.wikipedia.org/wiki/MD5#History_and_cryptanalysis [wikipedia.org]
Re: (Score:2)
Re:DES, AES, Blowshifh, twofish likely immune (Score:5, Informative)
Nice use of language (Score:3, Informative)
With:
Slight shift in implications, dontchathink?
Correct the summary/FUD (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).
Re: (Score:3, Interesting)
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)
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)
What part of this is specifi to internet news. This isn't news, this is CNN!
Re:Correct the summary/FUD (Score:5, Informative)
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)
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)
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)
Your post, sir, is as misleading as the Computerworld article. Was the ambiguity in it deliberate or unintentional? I hope the latter.
Re: (Score:1)
That was completely uncalled for. What has Computerworld done to deserve being compared to kdawson?
Re: (Score:2)
Re: (Score:1)
Use two different encryption methods. (Score:2, Redundant)
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)
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 we agree. (Score:2)
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)
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
Two reasons why. MOD PARENT UP. (Score:2)
Using 2 encryption methods and two keys prevents a vulnerability in one from being a method of attack.
Using 2 encryption methods and two keys prevents a brute-force attack, since brute-force attacks require some way to recognize the success of an attack, such as a series of words as a result. With 2 encryption methods a successful brute-force attack will only present almost perfectly random data to the attacker.
Re: (Score:3, Funny)
That's why I use rot13 not once, but twice!
Re: (Score:2)
Re:Use two different encryption methods. (Score:4, Insightful)
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)
Re: (Score:2)
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.
Re: (Score:2)
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)
Ban the Math, it's a circumvention tool.
Re: (Score:2)
Yeah, thats funny. :)
It's like saying "Quick we need a law against this math, that will get rid of it!"
Re: (Score:2)
Some quick thoughts (Score:1)
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
The synopsis stated "low grade" crypto (Score:5, Interesting)
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)
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.
Re: (Score:2)
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."
Re: (Score:1)
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)
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 (Score:2)
Imagine a beowoulf cluster of quantum computers!
Re: (Score:2)
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?
Re: (Score:2)
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)
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)
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).
'low-degree polynomial equation' (Score:1)
Re: (Score:2)
"Cube" attack (Score:2, Redundant)
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.)
Re:"Cube" attack (Score:4, Funny)
TIMECUBE theory can never be broken because Shamir's math is educated stupid.
Good cracking utility? (Score:2, Offtopic)
Re: (Score:1)
Re: (Score:2)
I have already told them they should notify the State AG. But these people are technologically challenged and don't want to advertise their ignorance. It's all about maintaining appearances.
It takes a lot of balls to do something like this to the government, especially to the police.
The name of the s
Cube attack in detail... (Score:4, Funny)
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.
A CRITICAL FLAW!x7q (Score:1)
...*whoosh!*
Re: (Score:2)
I've always had a problem with my unsolved Rubix-Cube puzzle. I think once I actually understand what you wrote, I might be able to solve the puzzle. Then again, peeling off the stickers and placing them in the correct location is a much more efficient way.
crypto law and public policy (Score:1)
It will be interesting to see the full paper (Score:5, Insightful)
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.
Re: (Score:1)
Current block ciphers have degrees that are (probably) in the thousands, but hey, if
BS (Score:1)
Break my Serpent 256bit! (Score:1)
Setec Astronomy (Score:2)
Frontalot was right (Score:2)
http://frontalot.com/index.php/?page=lyrics&lyricid=41 [frontalot.com]
Re:ehm (Score:5, Informative)
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.
Re: (Score:3, Informative)
Re: (Score:1)
The obvious solution to this problem is to develop an un-decryptable cypher.
Behold:
AME33u899##d8909iksalel!
Re:ehm (Score:5, Funny)
Nonsense. The real solution is to get a court order banning the guy from giving his presentation. After all, as has been demonstrated just recently, court orders are the preferred means of securing anything.
Re: (Score:2)
Re: (Score:1)
FUD!
Re:ehm (Score:5, Funny)
Re: (Score:3, Interesting)
There was a rump session talk on Gpcode, actually. It was suggested that if you had enough porn and/or music on your computer (tens of thousands of files with known headers, I believe), an attack on RC4 would recover your disk. It's related to the attack that breaks WEP. I don't know if it's been implemented.
Re:ehm (Score:5, Funny)
"Honey, we've simply GOT to have all this porn.... to recover our hard drive!"
Kudos to the individual that can pull THAT line off...
Re:disgusting fatbodies (Score:5, Funny)
I'm sure this post is encrypted...If only there were a way to use Schneier's algorithm...Wait...Got it! Here is the decrypted text:
Re: (Score:1)
I'm sure this post is encrypted...If only there were a way to use Schneier's algorithm...Wait...Got it! Here is the decrypted text:
Yes, I agree with moderatorrater. It appears Slashdot was jumping the gun. I like to ride mopeds.
It is, but unfortunately he is using ROT26.
Re: (Score:1)
Re: (Score:3, Funny)
FOR GREAT JUSTICE!
Re: (Score:1)
AND MASSIVE DAMAGE!
Re: (Score:2)
Everything uses polynomial equations, what matters is the degree. Elliptic curve crypyography uses really high degree polynomials so you don't have to worry.
Re: (Score:2)
Really Simple Acronyms.
Was that so hard?
Re: (Score:2)
Was that NP hard?
Was that so hard?
Re: (Score:2)
What an amateur.
I use ROT14. That really screws 'em up.