Successful timing attacks on elliptic curve cryptography (The H)

[Posted May 25, 2011 by jake]

The H reports on a successful timing attack against the Elliptic Curve digital signature algorithm in OpenSSL:

For their tests, the researchers set up an SSL server with OpenSSL and measured the time it took to create a digital signature using Elliptic Curve DSA (ECDSA). This allowed them to calculate the server's secret key. When establishing an SSL connection via the local loopback interface, they managed to do this almost instantaneously. While packet transfer times on a local network caused measurement uncertainties, these uncertainties could be compensated for with some further calculations. Overall, the attack described in Remote Timing Attacks are Still Practical [PDF] also proved feasible over a network.

No working countermeasures have so far been found; the US-CERT advises that ECDSA should no longer be used for digital signatures. To prevent this type of attack, the researchers recommend implementing time-independent functions for operations on elliptic curves.

Successful timing attacks on elliptic curve cryptography (The H)

Posted May 26, 2011 2:48 UTC (Thu) by Comet (subscriber, #11646) [Link] (2 responses)

The OpenSSH developers have been discussing this and the impact upon their ECDSA support. These: MARC or Google Groups point to the thread.

Damien Miller wrote:

This result concerns binary/GF(2m) fields only and not the prime fields that OpenSSH uses in recent versions. Unless a similar timing oracle is found for GF(p) fields then no OpenSSH-side workaround is required.

I'll note that The H's summarisation is false. US-CERT does not say to not use ECDSA for digital signatures; it says to not use digital signature and binary curves for authentication. There's a world of difference between an interactive protocol where timing can be observed and an offline signing in, eg, PGP.

Successful timing attacks on elliptic curve cryptography (The H)

Posted May 27, 2011 10:47 UTC (Fri) by ballombe (subscriber, #9523) [Link] (1 responses)

In any case cryptographers advise against binary curves in general. They are considered less secure than prime one.

Successful timing attacks on elliptic curve cryptography (The H)

Posted May 31, 2011 6:56 UTC (Tue) by Comet (subscriber, #11646) [Link]

That's a rather sweeping assertion, with no data to back it up. All cryptographers, or some cryptographers, and if some, which?

There almost certainly exist cryptographers who will express doubts about elliptic curves; there also exist cryptographers who express doubt about prime factorisation. Some of these can back their assertions up with some data, many can't. There are plenty of kooks in cryptography, perhaps more than in some other fields simply because this is, broadly speaking, about hiding data from those who would pry, so attracts those who are paranoid but where the opponent really is out to get you. :)

Since all asymmetric cryptography is based upon "what we don't yet know how to do efficiently", any approach will have its naysayers, but until breaks are demonstrated in the public literature, those of us who rely upon publicly available cryptography have limited options open to us.

One issue is that if you only use one form of crypto and have no plans to be able to switch (preferably in-protocol, as part of algorithmic agility, rather than updating clients and servers in lockstep) then you're in deep trouble when a break for that form eventually surfaces. I went into this in more detail at: http://bridge.grumpy-troll.org/2011/02/why-deploy-ecc-in-ssh.html

Calculating a result without revealing timings

Posted May 26, 2011 7:53 UTC (Thu) by epa (subscriber, #39769) [Link]

Surely it is not necessary to use a different algorithm; just add some delay to the one you use. For example, allocate a fixed amount of time (say one millisecond) to calculate the result - a time period that should be ample. If it's ready sooner, wait until the full time has elapsed before replying. If it's not ready in time, fail the operation, or perhaps wait another fixed interval.

Successful timing attacks on elliptic curve cryptography (The H)

Posted May 27, 2011 7:11 UTC (Fri) by alonz (subscriber, #815) [Link] (1 responses)

Won't it be enough to limit the allowable values of k in the signature generation algorithm? Just force the highest bit to be set—and the vulnerability disappears, no?

Successful timing attacks on elliptic curve cryptography (The H)

Posted May 29, 2011 22:27 UTC (Sun) by djm (subscriber, #11651) [Link]

No, then you have fixed a bit of the nonce and can conduct the matrix attack even more easily. (EC)DSA is horrendously sensitive to the privacy of its nonce (just ask Sony).