Catch up on stories from the past week (and beyond) at the Slashdot story archive


Forgot your password?
Encryption Security PlayStation (Games) News

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

New Elliptic Curve Cryptography Record

Comments Filter:
  • See, they were right when they said video games were bad !
  • While you only have 199 PS3's.
  • On the PS3, the effort is equivalent to about 14 full 56-bit DES key searches!

    Isn't DES still used by the financial industry, most often for wire fund transfers and ATMs? 3DES, specifically. *shakes head* They're doomed.

    • Re: (Score:2, Informative)

      I don't know what keying option [] 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/

  • by JoshuaZ ( 1134087 ) on Sunday July 12, 2009 @01:28PM (#28668291) Homepage

    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.

  • And in English, this means what exactly?

    • From TFA (Score:3, Informative)

      by CarpetShark ( 865376 )

      Why this is relevant

      Calculations of this sort may serve to boost our confidence in the strength of elliptic curve cryptography (ECC). To better understand how hard it would be to solve the supposedly hard mathematical problems underlying ECC, we try to solve ECDLP for parameters that are relatively small compared to those that would be used in ECC. The resulting runtimes combined with common extrapolation methods then yield hardness estimates based on which "secure" parameters can be selected or the securi

    • Basically (if I understood correctly), an ellipse is a structure that is very easy to invert to form some random structure, but it's very difficult to take that random structure and re-constitute the ellipse from it given no other information.
  • by MosesJones ( 55544 ) on Sunday July 12, 2009 @02:07PM (#28668529) Homepage

    Okay so they've done some cool stuff with their 200 PS3s.... but does anyone else get the feeling that they are mainly just having massive LAN parties and they just doing some research whenever the Dean asks where the money has gone.

    Oh hang on, they are pure mathematicians... this sort of stuff is their equivalent of a LAN party.

    • by ceoyoyo ( 59147 ) on Sunday July 12, 2009 @05:07PM (#28669799)

      Nope, these guys are a bunch of applied crypto geeks / coders. A pure mathematician isn't the least bit interested in how fast you can get your brute force crypto code to run on a PS3.

      And pure mathematician LAN parties use blackboards.

      • by linzeal ( 197905 )
        Marker Boards you mean, markers last a lot longer than chalk and the average applied mathematician can survive on marker board fumes, coffee/amphetamines and uncooked pop tarts or ramen longer than any freshman/grad student.
  • The runtime that we observed for the 112-bit case implies that, even though the 160-bit ECC standard is supposed to be phased out by the end of the year 2010, for the next decade no regular user needs to be overly concerned about the security of 160-bit ECC.

    While in general this is an impressive result and an interesting use of the PS3 computing architecture, the above conclusion is flawed. Just because their approach did not yield a result in a computationally reasonable length of time in no way implies

    • While the ECC problem is more and more analyzed, which means it is starting to be *more* reliable. Chances of a solution "falling out of the sky" are pretty low. Also, it is not said that if something like a solution is found it does not mean that key size is the important factor. It might well be that it doesn't matter or even that the problem only is specific to certain domain parameters.

      Also notice that the difference between 112 bit ECC and 163 bit ECC (the NIST standard curves are 163 bit) is much l

Karl's version of Parkinson's Law: Work expands to exceed the time alloted it.