Slashdot Mirror
Weak Elliptic Curve Cryptography Brute-Forced
thegrommit writes "It seems one implementation of elliptic curve cryptography has been broken. It took four years to break a 109 bit key, but the contest sponsors (who provide encryption products for Cisco, Nortel and Palm among others) believe it's still impossible to break their 163 bit keys. The real question is, for how long?" Update: 11/07 01:59 GMT by T : Dan Kaminsky wrote to point out that the key here was really brute forced, and not broken -- that is, no fundamental flaw was discovered in the algorithm.
It wasn't broken, it was brute-forced.
--
Oh yea! (insert Slashdot grumblings here)
http://mathworld.wolfram.com/EllipticCurve.html
It was also use by Anrew Wiles in 1993 to prove Fermat's famous last thereom.
http://mathworld.wolfram.com/FermatsLastTheorem.ht ml
Enjoy!
It is nice to see that Monico is donating the majority of the prize money to the FSF.
/<en
The winner is giving 8 grand to the FSF. Monico, who took up the challenge to "raise awareness of cryptography", will donate the bulk of his prize money to the Free Software Foundation and the remaining $2,000 to two men whose computers helped solve the problem.
Since a 163-bit key is 2^54 times more complex than a 109-bit key, and it took 4 years for the 109-bit key, aren't we looking at at least 4 * 2^53 years, not even figuring in the elliptical complexity (which I admit I would need to read up on)?
According to calc.exe, 4 * 2^53 years is 36,028,797,018,963,968 years. Anybody want to start working on that one?
We already covered this on slashdot. This is just Yahoo picking up on it now.
The truth about Scientology, Xenu, and you: Operation Clambake
Impossible seems like a pretty weird word to ever use in this sort of situation.
Except that they didn't use the word 'impossible'... you can thank the slashdot editor for that bit of nonsense. The article actually claims it is "computationally infeasible" to break the larger keys.
Just because brute-force is an inelegant method of breaking encryption doesn't mean it isn't valid.
Brute force just gives a baseline against which other attacks can be measured. With a brute-force break, it takes the same amount of time to break one key that it takes to break any other. With a cryptanalytic attack, on the other hand, you only need to successfully attack one key as a proof of concept; once you've expended the effort to break one key cryptanalytically, you've broken the system and probably reduced the effort to break a key by a couple dozen orders of magnitude relative to the baseline.
Will I retire or break 10K?
Why? What good does that do? But since you care, it's in Luo, and is just copied from jaluo.com. Not that that helps you understand what it says...
It's only the 109-bit keys that's been brute forced. Quoting the article, it would take 100 million times more computing power to take the 163-bit challenge:
"It would be about 100 million times harder (to break) than what was just done," Vanstone said. "If you could get every machine on the planet working on the problem...you're still not going to be able to touch the 163 problem."
I don't think Apple has any troubles using this key as of yet. And it's certainly not an insecure approach to OS security. The encoding of these algorithms is quite fast. This would be a good performance thing for the OS.
Not true. A proper one time pad, used appropriately
(e.g. only one time!) is mathematically provable to be absolutly secure, not just "practically secure".
The problem with one time pads is the key distribution problem - how do all sides agree and share a key without exposing that key to the bad guy? Especially since with a OTP, the key is as long as the original plaintext in which you want to encrypt.
Quantum Key Distribution algorithms such as BB84 (which is what people are actually refering to when they talk about "Quantum Cryptography") allows two parties to exchange absolutly secure OTP keys over an insecure medium, while the properties of quantum mechanics ensure that an adversary couldn't evesdrop or modify the traffic in transit.
Actually, you're almost right. But so very wrong. There is one cryptosystem that is IMPOSSIBLE(!!) to break: the One Time Pad. With that exception, it just becomes very hard. Another thing to realize about these codes is that *none* of them are provably hard. They are thought to be hard, but some mathematical genius might come out tomorrow with a fast method of computing discrete logs, or factoring primes, or figuring out elliptic curves. For now, it is practically impossible, but it might very well be trivial should such a breakthrough occur.
There is no such thing as a crypto key that is impossibile to crack. What it comes down to is how improbably it is to crack it. In this example, it took 10,000 computers 549 days to crack it and it's only 109 bits. At 163 bits, that's a doubling in difficulty for ever (sic) additional bit.
Just add a bit, and suddenly you've pushed off the efficiencies gained by moore's law for another 18 months. By going to 163 bits, you've got a good 80 years before the that key can be broken in the same time as this 109 bit key. Frankly I wouldn't be too worried about that problem.
As long as your crypto is good enough to make it too expensive to crack for those who might want to crack it, you've got no worries. And I don't see a lot of people out there able to throw together the 10K computers to crack a key who also don't mind wasting almost two years on the effort.
There are lots of organizations with 10,000 computers, or more. There are distributed systems like SETI which could put a million computers on this problem. People can improve the algorithms used to attack the problem.
I doubt it'll be 80 years before 163 bit is brute forced.
No electrons were harmed creating this post, though some may have been subjected to electrical and/or magnetic fields.
IANAC (I am not a Cryptographer)
every time you increase the bit length by 1, it doubles the brute processing time it takes to crack it. A 219 bit key is 109 bits longer then a 109 bit key, therefore it would take 2^109 = 6.4903710731685345356631204115251e+32 times as long to crack it. If I recall correctly, the reason why you sometimes see huge keys that are 1024 or 2048 bits long is the possibility that a weakness is found in the encryption technique that makes it a lot faster to brute force the key.
Lawyers, MBA's, RIAA? A jedi fears not these things!
261 days to double is below Moore's Law? I'm sure Gordon Moore would like to hear this. The usual expression is that semiconductor (whatever) doubles every 18 months. If you say speed doubles every 18 months, that's about 540 days -- comfortably LONGER than 261 days.
1000+ bit keys (or larger) are mandatory for secure large-prime public key systems now, but they are overkill for elliptic curves. Adding one bit to an ECC key gives relatively more strength than adding one bit to an RSA key does; that 109 bit ECC problem is already roughly comparable to factoring a 512 to 640 bit product of large primes.
But thanks for playing anyway.
One-time pads are uncrackable- mathematical proof exists. That assumes (and it's a rather large assumption) that the rules of using a one time pad are followed.
Messages encrypted with a OTP have been deciphered in the past, but not from any mathematical failing- people simply failed to correctly follow the rules.
1. You need a random process to generate the pad. This means random, not pseudorandom. Admittedly, modern pseudorandom number generator algorithms are very complex, and trying to reverse engineer (hey!) a PRNG from just a stream of outputs would be a mammoth task. Rules are rules, however complex- if your pad is pseudorandom, your cipher will only be pseudo-uncrackable. The Enigma produced vey complex keys with a convoluted series of rules, but if you know how an Enigma works, as the Brits did, you can use the ciphertext to help find the key, and then dechiper the entire message. This is one area where quantum mechanics fits in- lots of nice random phenomena arise naturally from quantization- I'll get back to that. Also, the key on the pad must be as long as the message you wish to encode- if you try to encode a 2000-character message by using a 1000-character key two times, your security is no longer guaranteed.
2. Only use each key on the pad once. That's why it's a one-time pad. If you use the same key more than once, you remove the randomness, and create a pattern that can help the cryptanalyst. Deciphering will still be difficult- but if you wanted difficult, you could have just used triple-DES or RSA or elliptic curve crypto- those are all varying degrees of difficult. You want impossible.
OTP is unbreakable, if you follow the rules- but the rules are really hard follow. You need random processes, and once you have these neat pads, you face the Key Exchange Problem- if you have an agent out in the field that you'd like to communicate with, and you must communicate in an absolutely secure fashion, you must get a copy of the one-time pad to the agent- it's the only thing that will decipher your messages. However, you can't just pick up the phone and relay the contents of the pad to your agent- the enemy might be bugging your phones- and hilarious hijinks will no doubt ensue when the enemy uses their new your insecurely transmitted pad to read your secure encrypted messages. Encrypting transmission is a good idea, but you can't use OTP to send the first OTP to the agent- how will the agent decrypt his encrypted pad? The classic analogy is that you're trying to send a key (think physical, lock-opening key) in a locked box that only the key inside the box can open. You could encrypt the key with hardass public key crypto, say 1024-bit RSA, but that isn't unbreakable in the same now-and-forever sense as OTP. It would be vulnerable to quantum computers, and vulnerable to any computer if someone discovered a polynomial time algorithm for prime factorization of really gigantic numbers, or if I win a Clay Mathemtics Prize for proving P=NP. You could of course do what the government does for secure key distribution- send couriers carrying OTPs directly to the agent in the field. This is an expensive, difficult, dangerous method, so better ways were searched for.
This is of course where Quantum Cryptography comes in. Photons all have specific polarizations. You can send a stream of randomly polarized photons through a polarizing filter, and photons with the same polarization angle as the filter will pass, while those with a polarization rotated 90 degrees with respect to the filter are blocked. What then happens to photons that have some intermediate angle? On the macroscale, we can say that the intensity of the light is a function of the angle, and infer that at a 45 degree tilt, 1/2 of the light is blocked, and 1/2 passes through. Enter Quantum Mechanics. It is fairly obvious to see the effect that polarizing filters have on a large scale quantity of light, but what about individual photons? Since the intensity of light at a 45 degree angle is 1/2 its normal value, one can infer that one half of the photons with a 45 degree polarization pass through, while one half are blocked. Simple enough. But if you send just one photon through with a 45 degree polarization, can you determine whether it will pass through? The answer, surprisingly enough, is no. You cannot determine whether a photon will pass through, and you will not know whether it passed through until it hits (or fails to hit) a detector on the other side. Can't determine? That makes it a random process, perfect to set up a OTP. It happens to have some interesting side benefits as well. Since the possibilities are pass and blocked, two possibilities- a string of photons sent at the filter produces a random binary sting of 1's (passed) and 0's (blocked). There is another fascinating benefit- if someone tries to sit in the middle of the photon stream and determine photon polarization, their eavesdropping will be evident- by checking the polarization of a photon in transit, they change the value of the polarization. All two people using quantum crypto need to do is confirm a few values that were sent (this can be done insecurely, since these values will not actually be used in the cipher pad)- if they match up, then send the message, encoded with the OTP, if not, someone is eavesdropping, and so discard the pad. It's a lot more complex than that, of course, but that's the general idea- you can use QC to generate a one-time pad, and then send it in such a way that you know whether or not you're being spied on.
"FDA staff reviewers expressed concern about the number of patients who were left out of the study because they died."
A common mistake I've seen is people assuming that key size == keyspace size. For nearly all cyphers this isn't true. Suppose, for example, that your key requires a large prime number. The Prime Number Theorem says that the fraction of numbers up to N that are prime is approximately 1/lg(N) (that's base e, not base 2). So if we are using a k-bit prime number as the key, the keyspace size would be 2^k/(k*lg(2)), not 2^k. This isn't a huge reduction in keyspace size, but then again most codes have much stronger restrictions on valid keys.
The point is, a code with, say, 1024-bit keys may only give you, say, a 700-bit keyspace.
For everyone interested in cryptographic stuff, I always suggest to read the publications of Bruce Schneier (http://www.counterpane.com). His monthly newsletter "crypto-gram" is very interesting and really fun to read (at least most times) and he produced several books I like very much (especially "secrets and lies", or "Applied Cryptography", if you are interested in mathematics of cryptography)