Slashdot Mirror
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."
I store all of my passwords in plain text!
I talk about stuff.
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.
See Schneier's blog. No word on MD5, which is extremely common.
Use the Firehose to mod down Second Life stories!
With:
Slight shift in implications, dontchathink?
FOR GREAT JUSTICE!
I am not your blowing wind, I am the lightning.
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).
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.
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.
Ban the Math, it's a circumvention tool.
Everything uses polynomial equations, what matters is the degree. Elliptic curve crypyography uses really high degree polynomials so you don't have to worry.
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 a hash or stream cipher, taking a key of any length. Radio Gatun is nice because its core can fit in under 2k of memory and it's an elegant, extensible construction.
However, scanning the paper describing the function, I note the quote "It has algebraic degree 2" on page 10. So it looks like a nice, small elegant cryptographic primitive has fallen.
FUD!
Does this mean, can I finally recover the data encrypted by the Gpcode virus?
One of our competitors trademarked the term "hypothesis". From now on, we will call them "boneheaded ideas".
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'.
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.
Really Simple Acronyms.
Was that so hard?
There are two types of people in the world: Those who crave closure
I do one better. I use inkblot tests. I can leave them in plain sight and their totally secure.
Co-worker: Your password is "flower"?
Me: What? No. It's "zombie clown hitting fish with hammer". What's wrong with you?
Those who believe the Internet is private,
find their privates are on the Internet.
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.)
The living have better things to do than to continue hating the dead.
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:
Help fight poverty: Punch a poor person.
Me too. It's ******
What?
Your password is hunter2?
The obvious solution to this problem is to develop an un-decryptable cypher.
Behold:
AME33u899##d8909iksalel!
Slashdot: news for Apple. Stuff that Apple.
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 the decrypted data, figure out the method used and then decrypt all the data?
I'd love to stick it to the application vendor. What a dick move.
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.
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.
The world's burning. Moped Jesus spotted on I50. Details at 11.
No you moron, that's my password!
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.
Solution 1: x = 1
Solution 2: x = -1
Solution 3: x = BUFFER OVERFLOW
%#$%#%#%#%##%%$$
I hate printers.
Was that NP hard?
Was that so hard?
I hate printers.
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 to require a specific technology like "encryption" for data security. --Ben Wright http://hack-igations.blogspot.com/2008/02/encryption-legislation-goes-overboard.html
Benjamin Wright, Dallas, Texas, benjaminwright.us
Imagine a beowoulf cluster of quantum computers!
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.
I hereby place the above post in the public domain.
AND MASSIVE DAMAGE!
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?
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 hereby place the above post in the public domain.
What an amateur.
I use ROT14. That really screws 'em up.
You never really know how close to the edge you can go until you fall off.
Some security... you have just become a victim of social engineering. If you have to correct people who misinterpret your inkblots, your security is even weaker than with a simple 4 letter all lower case numeric-only password... like 1-2-3-4.
/. account with "zombie clown hitting fish with hammer" as the password...
And now to log into your
Because there are many solutions to m mod n? Example X^2 = 1 mod 8 One solution: X^2 = 1, X = +/- 1 Another solution X^2 = 9 = 1 mod 8 X = +/-3 Etc ...
WTF? He said he likes to mop, not mopeds, get your decryption right.
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.
http://frontalot.com/index.php/?page=lyrics&lyricid=41
...*whoosh!*
A fool and his lamb are worth two in the bush.
...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.
That said, what's the difference between lower case numbers and upper case numbers?
--sabre86
"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...
Don't tell me to get a life. I'm a gamer; I have LOTS of lives!
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.
aq4jhfg80q34tru92q34wv354rgq3giehjgbpoe
=Then what's the point? (Couldn't decipher it could you?!)
Wow! Cool! Me too! I have 5 different inkblots for logging into five different systems.
All five passwords are "Boobies".
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
"An elephant wearing a hat."
Editor, A1-AAA AmeriCaptions
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.
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?
Wolde you bothe eate your cake, and have your cake?
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, then the space of possible plaintexts for the public-key cipher is at least as large as the keyspace for the secret-key cipher, and then the chosen-plaintext attack is no longer the weakest point.
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
The next thing to remember is to put next things next.
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 encrypting every possible plaintext with the known public key until one matches the known ciphertext. This is really well-known stuff.
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.
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.
The next thing to remember is to put next things next.
MOD PARENT UP.
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.
"We have to move past Furher Yay Transfers!"
Get your dogma outta my yard!
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?