New Elliptic Curve Cryptography Record 43
deian writes "Cryptography researchers Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra and Peter L. Montgomery have just announced that they have set a new record for the elliptic curve discrete logarithm problem (ECDLP) by solving it over a 112-bit finite field. The previous record was for a 109-bit prime field and dates back from October 2002. Their calculation was done on the EPFL cluster of more than 200 PS3s (same one used to create the Rogue CA certificates and demonstrate a reproducible attack on MD5 algorithms). On the PS3, the effort is equivalent to about 14 full 56-bit DES key searches!"
For those who aren't number theorists... (Score:5, Informative)
Elliptic curve crypto uses the structure of certain well-behaved elliptic curves over finite fields. An elliptic curve is an equation of the form y^2=x^3 + ax + b (sort of, technically the full form is slightly more general but they can more or less all be reduced to this case). One is generally interested in what the solutions look like for fixed a and b over some well behaved set. For example, one is frequently interested in what the integer and rational solutions in x and y look like when a and b are fixed rational numbers. It turns out that one nice area to look at are elliptic curves over finite fields. By a "field" we mean a set with multiplication and addition reasonably well behaved (both are associative and commutative, multiplication distributes over addition, we have additive and multiplicative identities (i.e. 1 and 0), every element has an additive inverse, and every non-zero element has a multiplicative inverse). Classic examples of fields are the reals and the rationals. The simplest finite fields are formed by looking at arithmetic modulo a prime. It turns out in fact, that this accounts for almost all finite fields. All finite fields have either a prime number of elements (and are formed by the construction just mentioned) or have a prime power number of elements and are formed using a slightly modified construction.
Now, it turns out that if you have a given elliptic curve you can define a reasonably well behaved group on it. Moreover, inverting this operation is not at all easy when operating over a finite field. Essentially, one has an analog to the classic discrete log problem in a general finite field where calculating a^n for fixed a is easy, but given the equation a^n=x for fixed a and x, calculating n is really difficult. Many different crypto systems are based along this idea, the simplest example being Diffie-Hellman. RSA is based off of a very similar related idea. What they did is solve this problem for a really big prime p.
Re:For those who aren't number theorists... (Score:5, Informative)
Re:56 bit DES? (Score:5, Informative)
3DES runs the second round backwards, which enables the "meet in the middle" attacks. While security in general relies on good keys, especially for symmetric ciphers, 3DES in particular is sensitive to poor key choice. There are many keys which may be good for other algorithms that weaken this one significantly. Thankfully we know most of the traits of bad keys, but probably not all. That means that while theoretically the security is high, there are attacks against it which may simplify it further depending on the keys used.
Re:For those who aren't number theorists... (Score:5, Informative)
Re:Cuda? (Score:5, Informative)
Re:56 bit DES? (Score:2, Informative)
I don't know what keying option [wikipedia.org] ATMs generally use with 3DES, but assuming they aren't using the weakest (only equivalent to DES), then "14 full 56-bit' searches in 26 days (13 June - 8 Jul) doesn't pose a significant threat. Being generous, their search is about equivalent to a single complete 60-bit (log(14*2^56)/log(2)=59.8) search over the same time, and according to the Wiki article keying option 2 of 3DES provides "80 bits of security". So their setup would take about 27 million days (26 days * 2^80/2^60) to do a single complete 80-bit search.
Re:56 bit DES? (Score:3, Informative)
That's not quite right. 3DES is not weaker than it has to be. Meet in the middle attacks are possible for all triple encryption constructs.
The second operation is an decryption so that if both triple des keys are the same it is compatible with single des. It does in no way weaken the algorithm.
For any triple encryption the complexity of attacks is only squared the base complexity not cubed as you would expect because of meet in the middle attacks. That's also why normally only 2 independent keys are used and not three. You do not want to suggest a higher complexity than you actually have.
http://en.wikipedia.org/wiki/Triple_DES [wikipedia.org]
http://en.wikipedia.org/wiki/Meet-in-the-middle_attack [wikipedia.org]
Re:56 bit DES? (Score:1, Informative)
Actually, 3DES is usually implemented as DES-EDE-- Encrypt-Decrypt-Encrypt, and the keys aren't necessarily different or independent. The basic idea was to allow backward compatibility with single-DES systems by setting the first and second keys to the same value (typically equal to the final key). Then the first encrypt and decrypt operations would cancel each other out, leaving plaintext to be fed into the final encryption operation. In a case like that, the security is exactly equal to that of DES-- which is to say, 2^56.
You're right about meet-in-the-middle attacks reducing the effective key length to 2^112 when three different keys are used, though.
From TFA (Score:3, Informative)
In other words, they're overconfident for now, but someone will crack it next year and prove 'em all wrong.