Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

New Elliptic Curve Cryptography Record

Soulskill posted more than 5 years ago | from the feistel-would-be-impressed dept.

Encryption 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!"

cancel ×

43 comments

Sorry! There are no comments related to the filter you selected.

Video Games (0)

danknight (570145) | more than 5 years ago | (#28668217)

See, they were right when they said video games were bad !

I have 200 PS3's (1)

Thantik (1207112) | more than 5 years ago | (#28668235)

While you only have 199 PS3's.

Re:I have 200 PS3's (0)

Anonymous Coward | more than 5 years ago | (#28668427)

Yeah seriously. All they're saying is that they have more than 200 PS3. So for all we know they used a million of them. How about an upper bound next time? Or ::shudders:: the actual number?

Re:I have 200 PS3's (1)

weirdcrashingnoises (1151951) | more than 5 years ago | (#28668807)

Ok ok, we give in.

We have 200.5

Re:I have 200 PS3's (1)

pushing-robot (1037830) | more than 5 years ago | (#28670877)

They're just playing it safe. No matter how many PS3s you own, [youtube.com] somebody always has one more. [youtube.com]

And then it simply becomes an arms race. [youtube.com]

56 bit DES? (1)

girlintraining (1395911) | more than 5 years ago | (#28668259)

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:56 bit DES? (0)

Anonymous Coward | more than 5 years ago | (#28668279)

3DES uses DES 3 times, with 3 different keys. (3 X 56 bit)
but due to "meet in the middle" search methods, the complexity of a brute force attack is "only" 2^112, which is more than enough to make it impossible.

Re:56 bit DES? (4, Informative)

The Snowman (116231) | more than 5 years ago | (#28668409)

3DES uses DES 3 times, with 3 different keys. (3 X 56 bit)
but due to "meet in the middle" search methods, the complexity of a brute force attack is "only" 2^112, which is more than enough to make it impossible.

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:56 bit DES? (1)

moskau (965206) | more than 5 years ago | (#28668897)

3DES runs the second round backwards, which enables the "meet in the middle" attacks.

You mean because the second key is used with the decryption operation? Why would a meet in the middle attack not be possible if three encryption operations were used?

Re:56 bit DES? (1)

sfarmstrong (1106577) | more than 5 years ago | (#28675293)

A meet-in-the-middle attack still works on 3DES, but it can only strip off one layer of DES. Thus, 3DES has 112 bits of security (56*2).

Quoting from the grandparent:

3DES runs the second round backwards, which enables the "meet in the middle" attacks.

I have no idea whether that "second round backwards" thing is true, but this has nothing to do with why 3DES is vulnerable to meet-in-the-middle attacks. Meet-in-the-middle attacks [wikipedia.org] work on any plaintext that's encrypted multiple times with the same cipher but different keys. If you encrypted with AES-128 twice, that ciphertext would also be vulnerable to a meet-in-the-middle attack. (Though the space cost would be see high that such an attack would be even more impossible than an AES-128 bruteforce already is.)

Re:56 bit DES? (3, Informative)

Neredera (1170095) | more than 5 years ago | (#28669205)

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? (1, Informative)

Anonymous Coward | more than 5 years ago | (#28669661)

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.

Re:56 bit DES? (2, Informative)

FearForWings (1189605) | more than 5 years ago | (#28668721)

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.

Cuda? (0)

Anonymous Coward | more than 5 years ago | (#28668271)

I'd love to see this done on some GPUs in the vein of folding@home.

Re:Cuda? (4, Informative)

volsung (378) | more than 5 years ago | (#28668593)

From the page: "Sloppy reduction allowed us to make our code branch-free and thereby very efficient on the PS3's 4-way SIMD Synergistic Processing Units (SPUs)." This sounds promising for CUDA. If this code is really branch-free, it should fly on a GTX 285. NVIDIA's GT200 chips have a lot more raw compute power, but less flexibility, than the Cell processor on the PS3. The usual CUDA performance killer is irregular memory read patterns and highly divergent branching.

Re:Cuda? (3, Funny)

CarpetShark (865376) | more than 5 years ago | (#28669193)

NVIDIA's GT200 chips have a lot more raw compute power, but less flexibility, than the Cell processor on the PS3

That's nothing. The Wii version will crunch those numbers as fast as you can wave your arms.

Re:Cuda? (2, Funny)

mathx314 (1365325) | more than 5 years ago | (#28671787)

...assuming you have no arms.

For those who aren't number theorists... (5, Informative)

JoshuaZ (1134087) | more than 5 years ago | (#28668291)

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... (4, Funny)

azav (469988) | more than 5 years ago | (#28668361)

And this means what?

Re:For those who aren't number theorists... (4, Informative)

JoshuaZ (1134087) | more than 5 years ago | (#28668369)

It means that we've pushed up how large p needs to be for this sort of cryptography to be considered secure.

Re:For those who aren't number theorists... (1)

azav (469988) | more than 5 years ago | (#28668397)

That's the executive summary I was looking for. Thanks much.

Re:For those who aren't number theorists... (1)

mustafap (452510) | more than 5 years ago | (#28668407)

>That's the executive summary I was looking for

executive? did you stumble here by accident?

Re:For those who aren't number theorists... (1)

fractoid (1076465) | more than 5 years ago | (#28673633)

So in the pissing contest of cryptography... the guys in TFA can 'p higher'?

Re:For those who aren't number theorists... (0)

Cyberax (705495) | more than 5 years ago | (#28668507)

Small correction: arithmetic modulo prime does not form a field.

It forms a ring - a slightly less strict structure, without requirements for multiplicative identity (and existence of multiplicative inverse) and commutativity for multiplication.

ECC does not require fields as well, it works fine with rings.

Links: http://en.wikipedia.org/wiki/Ring_(mathematics) [wikipedia.org]
http://en.wikipedia.org/wiki/Field_(mathematics) [wikipedia.org]

Re:For those who aren't number theorists... (4, Informative)

JoshuaZ (1134087) | more than 5 years ago | (#28668533)

Er, not exactly. You can do ECC in a general ring but there are reasons one would rather not generally. Also, arithmetic modulo a prime always forms a field. Arithmetic modulo n for composite n only has a ring structure. But if n is prime then everybody gets inverses.

Re:For those who aren't number theorists... (1)

Cyberax (705495) | more than 5 years ago | (#28668571)

Sorry, for noise. My abstract algebra is a bit rusty, modulo n arithmetic indeed forms a finite field if n is prime.

Re:For those who aren't number theorists... (1)

maxume (22995) | more than 5 years ago | (#28669113)

Off-topic, potentially obnoxious question: Are the wes ones and yous in there habit, or are they preference?

I guess it isn't really that obnoxious, unless you choose to take it very personally; mostly, if it is a preference, I'm curious as to why.

Re:For those who aren't number theorists... (1)

JoshuaZ (1134087) | more than 5 years ago | (#28669503)

More habit than anything else. Mathematicians are fond of the first person plural when discussing proofs. I myself have a habit of using second person. The two combine in a way that isn't I suppose the easiest writing style.

Re:For those who aren't number theorists... (0)

Anonymous Coward | more than 5 years ago | (#28669225)

You've been reading Wikipedia again, haven't you? Stop it or you will go blind.

Re:For those who aren't number theorists... (1)

MrCrassic (994046) | more than 5 years ago | (#28670663)

Thanks for the really good explanation, Josh.

Translation please (1)

azav (469988) | more than 5 years ago | (#28668339)

And in English, this means what exactly?

Re:Translation please (-1, Troll)

Anonymous Coward | more than 5 years ago | (#28668535)

Funny. I graduated high school in the United States. The farthest I got in math was Calculus I.

That was ten years ago, and I still understood that well enough.

Either your school really sucked, or you're an idiot.

Yet your logical skills are lacking (0)

Anonymous Coward | more than 5 years ago | (#28669251)

Either your school really sucked, or you're an idiot.

Those two are never mutually exclusive.

From TFA (2, Informative)

CarpetShark (865376) | more than 5 years ago | (#28670237)

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 security of employed ECC systems can be assessed.

A soon to be abolished ECC standard uses 160-bit prime fields. Solving ECDLP over such fields is generally believed to require an effort that is at least 16 million times as large as for 112-bit prime fields. 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.

In other words, they're overconfident for now, but someone will crack it next year and prove 'em all wrong.

Re:Translation please (1)

Durandal64 (658649) | more than 5 years ago | (#28673385)

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.

Anyone else suspicious (4, Funny)

MosesJones (55544) | more than 5 years ago | (#28668529)

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.

Re:Anyone else suspicious (0)

Anonymous Coward | more than 5 years ago | (#28668741)

If you had ever met any of these researchers you would realize how silly it is to suggest they have LAN parties. Peter Montgomery or Arjen Lenstra at a LAN party is a ridiculous notion!

Re:Anyone else suspicious (0)

Anonymous Coward | more than 5 years ago | (#28668833)

Sounds about right. Two hundred socially inadequate virgins masturbating over consumer electronics. Hmmm, sounds more like like an Apple convention - so that would be gay virgins.

Re:Anyone else suspicious (3, Funny)

ceoyoyo (59147) | more than 5 years ago | (#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.

Re:Anyone else suspicious (1)

linzeal (197905) | more than 5 years ago | (#28673081)

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.

Re:Anyone else suspicious (0)

Anonymous Coward | more than 5 years ago | (#28670851)

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.

But does it run on windows?

160 bit key is safe? (1)

Fnord666 (889225) | more than 5 years ago | (#28671417)

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 that one does not exist. It just means that this isn't it.

Re:160 bit key is safe? (1)

owlstead (636356) | more than 5 years ago | (#28674523)

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 larger than say a 1024 bit RSA key and a 1792 bit one as the security of the keys scales linearly instead of in a curve as with RSA.

As you rightly notice, it does not protect against any other attacks than the standard mechanism. I do think you need to read the conclusion only as relevant with their method of analysis.

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?