Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Minerva: Practically exploitable side-channel leakage in ECDSA implementations

minerva.crocs.fi.muni.cz

Post reply on HN
Print view View original

11–20 of 55 posts

Re: Minerva: Practically exploitable side-channel leakage in ECDSA implementations

#11

Post by 1000units »

wolf550e wrote: post #10
svnpenn wrote: post #9

> the trustworthiness of NIST-produced curves being questioned after revelations that the NSA willingly inserts backdoors into software, hardware components and published standards were made; well-known cryptographers have expressed doubts about how the NIST curves were designed, and voluntary tainting has already been proved in the past. https://wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_...

'tptacek would write that no reputable cryptographer believes the NIST curves themselves are backdoored.

Is this a joke? Doesn't everybody believe they're backdoored?

Re: Minerva: Practically exploitable side-channel leakage in ECDSA implementations

#12

Post by wolf550e »

tptacek wrote: post #7

This looks like a really phenomenal writeup, with worked examples. The underlying math and algorithm stuff here is applicable to other attacks; it looks like this is worth a close read.

Can you say whether libgcrypt did something especially stupid? [1]

I understand that most people just take the ref10 code from supercop, but if I were to try to implement ed25519 from the paper (https://ed25519.cr.yp.to/papers.html), what is the chance I would do something like what libgcrypt did, or equally bad?

Basically, is ed25519 secure because everyone uses a known secure implementation or because it is engineered to be genuinely hard to implement incorrectly from the paper? (I know it's both, but is it mostly one or the other?)

1 - They special cased the point at infinity and this short-circuit allowed to count leading zeros.

Re: Minerva: Practically exploitable side-channel leakage in ECDSA implementations

#13

Post by hannob »

1000units wrote: post #11
wolf550e wrote: post #10

Earlier quoted context omitted.

'tptacek would write that no reputable cryptographer believes the NIST curves themselves are backdoored.

Is this a joke? Doesn't everybody believe they're backdoored?

There's two stories that often get mixed together. One is an elliptic curve based random number generator (Dual EC DRBG), and yes, everyone who knows the facts believes it's backdoored.

Then there's some much more general concerns about the NIST curves themselve. These concerns come down to that a) we don't really know how they were generated (there are some numbers in the paper that just "appear out of nowhere") and b) that they've been created by the NSA. But there's no concrete proof of any backdooring and it seems relatively implausible, as no method is known that would explain how that backdooring would work. I guess most people familiar with the facts don't believe they are backdoored.

Re: Minerva: Practically exploitable side-channel leakage in ECDSA implementations

#14

Post by exabrial »

Great writeup. Once again, physical access owns. This line stuck out:

> The attack required 11000 signatures

For a smartcard, this seems rather impractical in the real world. My Nitrokey has 1938 total signs after a month of usage, signing every git commit to our company repository and using it to authenticate over ssh (gpg-agent)

Re: Minerva: Practically exploitable side-channel leakage in ECDSA implementations

#15

Post by j08ny »

tptacek wrote: post #7

This looks like a really phenomenal writeup, with worked examples. The underlying math and algorithm stuff here is applicable to other attacks; it looks like this is worth a close read.

Thanks, a paper is being prepared with the full details and an improved method. The sensitivity of the method to noise (one bad inequality in the lattice can make it not find the key) is really worth looking at, as that would improve the number of signatures necessary for the attack severely.

Re: Minerva: Practically exploitable side-channel leakage in ECDSA implementations

#18

Post by 1000units »

hannob wrote: post #13
1000units wrote: post #11

Earlier quoted context omitted.

Is this a joke? Doesn't everybody believe they're backdoored?

There's two stories that often get mixed together. One is an elliptic curve based random number generator (Dual EC DRBG), and yes, everyone who knows the facts believes it's backdoored. Then there's some much more general concerns about the NIST curves themselve. These concerns come down to that a) we don't really know how they were generated (there are some numbers in the paper that just "appear out of nowhere") and…

Oh, just that once.

Re: Minerva: Practically exploitable side-channel leakage in ECDSA implementations

#19

Post by j08ny »

wolf550e wrote: post #12
tptacek wrote: post #7

This looks like a really phenomenal writeup, with worked examples. The underlying math and algorithm stuff here is applicable to other attacks; it looks like this is worth a close read.

Can you say whether libgcrypt did something especially stupid? [1] I understand that most people just take the ref10 code from supercop, but if I were to try to implement ed25519 from the paper ( https://ed25519.cr.yp.to/papers.html ), what is the chance I would do something like what libgcrypt did, or equally bad? Basically, is ed25519 secure because everyone uses a known secure implementation or because it is engin…

If my two cents count, I would say that if you were to implement EdDSA from the paper, you would have a good chance of creating a secure implementation w.r.t. to this kind of leakage.

However, if you were starting with some Short-Weierstrass EC code in your library, then you might be inclined to skip all the scalar multiplication specific stuff in the Ed25519 paper, just take some (incomplete) Edwards formulas, take some general scalar multiplication algo (or even reuse the one you have for Short-Weierstrass, like libgcrypt) and end up with a vulnerable EdDSA (if your ECDSA was).

The short-circuiting in the addition formulas is necessary if incomplete formulas are used. Either that is done, or the scalar multiplication algorithm has to explicitly find out the bit-length and start so that the point at infinity is not input into them ever.

Re: Minerva: Practically exploitable side-channel leakage in ECDSA implementations

#20

Post by j08ny »

exabrial wrote: post #14

Great writeup. Once again, physical access owns. This line stuck out: > The attack required 11000 signatures For a smartcard, this seems rather impractical in the real world. My Nitrokey has 1938 total signs after a month of usage, signing every git commit to our company repository and using it to authenticate over ssh (gpg-agent)

We are working on lowering that number :)

It is quite a conservative estimate, we didn't want to claim something our PoC couldn't deliver. Also, it is with minimal attack runtime, as in, after you have those signatures and timings it takes a few minutes to get the private key. There is a trade-off where you can get around some of the noise and thus need less signatures if you just throw more computation resources at it.

Post reply on HN