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

ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

eprint.iacr.org

Post reply on HN
Print view View original

31–40 of 56 posts

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#31

Post by dr_zoidberg »

mikeash wrote: post #19
13of40 wrote: post #14

Earlier quoted context omitted.

Do you have a good citation for that or is it just a personal theory?

Apple used to have a bug where they'd report PIN failure before writing that failure to nonvolatile storage. Somebody took advantage of this by building a box that cut power before the write could be performed, allowing a brute force attack: https://www.intego.com/mac-security-blog/iphone-pin-pass-cod... The proposal here is similar, just using a different technique to prevent the write. There isn't any nonvolatile s…

Thanks for the link, it looks interesting.

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#32

Post by nullc »

cjbprime wrote: post #12
ge0rg wrote: post #11

Earlier quoted context omitted.

Please elaborate the downvotes. While not actually testing Curve25519 is perfectly valid for the authors, comepletly ignoring its existence is a bit far-fetched, as it is clearly in scope. To quote the first sentence of the paper: "We show that elliptic-curve cryptography implementations on mobile devices are vulnerable to electromagnetic and power side-channel attacks." At least they should have said "some implement…

Upvoted, you're totally correct. Each of these attacks is providing support to DJB's focus on constant time implementations of everything.

Your comment is demonstrating the material misunderstandings created by the overused of marketing for subtle technical matters.

The implementations of ed25519 that you can find, including the ones worked on by DJB, are not "constant time everything"-- they're constant time for secret key operations. Other operations, like signature verification, are variable time... because that is usually fine and important for performance. It isn't always fine, however, -- you don't want an voting system anonymizer leaking information about which order it is validating which ballots, for example.

Of course, 25519 implementations are by far not the only cryptographic code which achieves basic side-channel resistance-- and there are other things which go further and try to achieve stronger resistance to other kinds of sidechannels by also implementing blinding...

If people go around incorrectly thinking these implementations are "constant time everything", eventually someone will get burned -- because the real culprit isn't constant time or not, it's the mismatch between requirements and provided properties. Since speed is also a frequently required (security!) property there is no such thing as a strictly more conservative choice, and no replacement for understanding and imagination.

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#33

Post by tptacek »

nullc wrote: post #30
ge0rg wrote: post #8

This is a really impressive piece of work. Unfortunately, the authors completely ignore Curve25519[0], which was designed by DJB (and implemented as NaCl[1]), with the goal to reduce side-channel vulnerabilities. From a random Curve25519 presentation [2]: - No data-dependent branches. - No data-dependent indexing. I really wonder how much can be extracted from a NaCl implementation under the same conditions. [0] http…

> - No data-dependent branches. > - No data-dependent indexing. These are implementation properties not properties of the curve. 25519 is a fine set of parameters but it always disappoints me to see this conflation. The implementations being attacked here were grotesquely sidechannel vulnerable. There are grotesquely sidechannel vulnerable ed25519 implementations (esp. parties that have been bitten by the 'tutorial t…

Really? Do you have links to vulnerable Ed25519 implementations? I absolutely believe you; I'm just interested in them for exercises.

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#34

Post by nullc »

tptacek wrote: post #33
nullc wrote: post #30

Earlier quoted context omitted.

> - No data-dependent branches. > - No data-dependent indexing. These are implementation properties not properties of the curve. 25519 is a fine set of parameters but it always disappoints me to see this conflation. The implementations being attacked here were grotesquely sidechannel vulnerable. There are grotesquely sidechannel vulnerable ed25519 implementations (esp. parties that have been bitten by the 'tutorial t…

Really? Do you have links to vulnerable Ed25519 implementations? I absolutely believe you; I'm just interested in them for exercises.

For example: https://github.com/vbuterin/ed25519/blob/master/ed25519.py#L...

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#35

Post by powerbutton65 »

Confiks wrote: post #25

I always see these non-intrusive side channels being applied to asymmetric cryptography. From using a microphone to listen in on GPG RSA private keys, to now the difference between point adding and point doubling in ECDSA. But I wonder if there are feasible, modern attacks against software using symmetric encryption. For example products offering full disk encryption, or encrypted volumes. Or are the operations in sy…

The authors cite some EM side-channel attacks in the paper (eg [0,1])

[0]: https://eprint.iacr.org/2015/561.pdf [1]: https://eprint.iacr.org/2015/727.pdf

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#36

Post by nullc »

CiPHPerCoder wrote: post #10

Oh if only there were a elliptic curve digital signature algorithm that was side-channel resistant and well studied by cryptography experts. https://en.wikipedia.org/wiki/EdDSA (Fortunately, we should see its adoption when TLS 1.3 is standardized.)

EdDSA is not fundamentally more sidechannel resistant; sidechannel resistance is a function of the implementation.

EdDSA's authors make a reasonable argument that it takes less work with their parameters to make a timing sidechannel free implementation which is also fast (at least for secret key operations); but "less work" isn't really the problem when comparing to a grotesquely vulnerable implementation, especially where it would be perfectly acceptable to take a slowdown implied by an especially simple way of making the operation constant time.

It would be more accurate to say that so far EdDSA has had a more conscientious implementation culture around it. But I think that won't last if too many people misunderstand sidechannel resistance as automatic there (even now one can go to lists of ed25519 implementations and get linked, without warning, to implementations which are not sidechannel resistant at all).

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#37

Post by tptacek »

nullc wrote: post #34
tptacek wrote: post #33

Earlier quoted context omitted.

Really? Do you have links to vulnerable Ed25519 implementations? I absolutely believe you; I'm just interested in them for exercises.

For example: https://github.com/vbuterin/ed25519/blob/master/ed25519.py#L...

Thanks!

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#38

Post by ge0rg »

tptacek wrote: post #26
ge0rg wrote: post #11

Earlier quoted context omitted.

Please elaborate the downvotes. While not actually testing Curve25519 is perfectly valid for the authors, comepletly ignoring its existence is a bit far-fetched, as it is clearly in scope. To quote the first sentence of the paper: "We show that elliptic-curve cryptography implementations on mobile devices are vulnerable to electromagnetic and power side-channel attacks." At least they should have said "some implement…

This is academic crypto research involving one of the most important names in this part of the field (Eran Tromer is one of the people who invented microarchitectural side channel attacks). I don't know that it's typical for research like this to comprehensively evaluate targets that aren't relevant to the research. Regardless, here we have an attack on the ECDSA k-nonce. People who use Curve25519 don't even use ECDS…

I'm only a crypto hobbyist, so I haven't followed the field (side-channel attacks on ECC) too closely. Still, the authors themselves address ECC and not jus ECDSA in the related work section, and I considered Curve/Ed-25519 to be a sufficiently important contribution to the field to at least mention it.

One way or the other, this is really impressive work and it shows yet another reason to avoid ECDSA, unless you are a crypto rocket surgeon.

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#39

Post by powerbutton65 »

mikeash wrote: post #23
marcosdumay wrote: post #20

Earlier quoted context omitted.

They are highly correlated. The best way to achieve constant time is making your code paths data independent, that is, it always execute the same instructions, whatever the data. This code will also use constant power and have constant EM emission. (Except for low level optimizations in hardware, that may break any of those characteristics.)

That parenthetical sounds extremely important! Won't executing the same instructions on different data use different amounts of power and emit different amounts of EM? For example, I would think (naively, I'm only familiar with the most basic of hardware whatnot) that multiplying 0 and 0 would not use the same amount of power and emit the same EM as multiplying 0xffffffff by 0xffffffff.

Yes, this exactly the basis of differential power analysis. This was first demonstrated back in 1999 by Kocher et al [0]

[0]: https://www.cis.upenn.edu/~nadiah/courses/cis800-02-f13/read...

Re: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

#40

Post by software_radio »

ge0rg wrote: post #11
ge0rg wrote: post #8

This is a really impressive piece of work. Unfortunately, the authors completely ignore Curve25519[0], which was designed by DJB (and implemented as NaCl[1]), with the goal to reduce side-channel vulnerabilities. From a random Curve25519 presentation [2]: - No data-dependent branches. - No data-dependent indexing. I really wonder how much can be extracted from a NaCl implementation under the same conditions. [0] http…

Please elaborate the downvotes. While not actually testing Curve25519 is perfectly valid for the authors, comepletly ignoring its existence is a bit far-fetched, as it is clearly in scope. To quote the first sentence of the paper: "We show that elliptic-curve cryptography implementations on mobile devices are vulnerable to electromagnetic and power side-channel attacks." At least they should have said "some implement…

The paper clearly says what was vulnerable. Don't extrapolate from the summary, that most likely wasn't even written by "them."
Post reply on HN