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

41–50 of 56 posts

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

#41

Post by tptacek »

ge0rg wrote: post #38
tptacek wrote: post #26

Earlier quoted context omitted.

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…

Again: Ed25519 isn't ECDSA. Not just different curves, but different signature constructions. Curve25519 and ECDSA are orthogonal. I'd have disagreed with your comment even if you had said "Ed25519" instead of "Curve25519", but I especially disagree with the comment you actually wrote.

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

#42

Post by nullc »

This work is very important.

Some might dismiss it because it is no surprise that these implementations would have serious sidechannel vulnerabilities, and --indeed-- in Bitcoin Core we stopped using OpenSSL for signing two years ago for this reason. But, as cryptographers ourselves, our choices aren't all that representative of application authors in general.

I've found it to be difficult to get parties to stop using obviously vulnerable crypto code-- even businesses making "high security" hardware wallets. Everyone has many other priorities, and without a demonstration the attacks are "too theoretical" to spend time on, or to justify a software slowdown, for many people.

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

#43

Post by superuser2 »

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…

Note that this was patched and is no longer feasible.

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

#44

Post by [deleted] »

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.

[deleted]

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

#45

Post by ge0rg »

tptacek wrote: post #41
ge0rg wrote: post #38

Earlier quoted context omitted.

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…

Again: Ed25519 isn't ECDSA. Not just different curves, but different signature constructions. Curve25519 and ECDSA are orthogonal. I'd have disagreed with your comment even if you had said "Ed25519" instead of "Curve25519", but I especially disagree with the comment you actually wrote.

Thanks for the clarification. While I am aware that Curve25519 is not Ed25519 is not ECDSA, they all at least belong into the field of Elliptic Curve Cryptography. It is hard for an outsider to tell how wide a certain sub-field is, and how far the related work research should go. I merely took the hints from the paper, which addressed ECC in some places, and wrongfully concluded that DJB's research would be still on topic.

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

#46

Post by CiPHPerCoder »

nullc wrote: post #36
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…

> EdDSA is not fundamentally more sidechannel resistant; sidechannel resistance is a function of the implementation. > ... > It would be more accurate to say that so far EdDSA has had a more conscientious implementation culture around it.

Your assessment is correct. EdDSA is deterministic which eliminates the nonce-reuse concerns, but deterministic EdDSA/ECDSA requires side-channel resistance. I erred in my previous comment.

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

#47

Post by tptacek »

ge0rg wrote: post #45
tptacek wrote: post #41

Earlier quoted context omitted.

Again: Ed25519 isn't ECDSA. Not just different curves, but different signature constructions. Curve25519 and ECDSA are orthogonal. I'd have disagreed with your comment even if you had said "Ed25519" instead of "Curve25519", but I especially disagree with the comment you actually wrote.

Thanks for the clarification. While I am aware that Curve25519 is not Ed25519 is not ECDSA, they all at least belong into the field of Elliptic Curve Cryptography. It is hard for an outsider to tell how wide a certain sub-field is, and how far the related work research should go. I merely took the hints from the paper, which addressed ECC in some places, and wrongfully concluded that DJB's research would be still on…

No problem! You just asked why you'd've been downvoted. :)

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

#48

Post by dogma1138 »

powerbutton65 wrote: post #21
AdmiralAsshat wrote: post #17

Silly question based on my layman's understanding of the attack: Can you impede the extraction process simply by having your phone/tablet/laptop generate interference while the decryption process is happening? For instance, if your laptop is simultaneously playing music through its speakers, would the analysis still let them definitively pick out the signing key?

Valid question. You shift the burden from being a cryptography related problem to signal processing related problem.

This isn't exactly a cryptography related problem to begin with, it's an implementation issue which inherently all side channels attacks are. This doesn't mean that you can't add some resistance against side channel attacks to your cryptographic algorithm but it will cost you quite a bit in terms of performance, and for the most part it's not where it should be.

Better silicon should solve some of these issues, for example adding some additional isolation between the power section and the logic a small super-cap with decent in-band filtering might do the trick.

As far as radiating EM goes I'm not sure what can be done but some more additional shielding and EM noise reduction should add some degree of protection.

Most implementations will eventually be vulnerable to some type of side channel attacks, the complexity and cost-vs-benefit is important here.

Launching an evil USB attack on the off chance of getting a key is most likely not very scalable, but considering that NFC/wireless payments for phones will become more and more common, and that crypto-currencies might actually end up being in common day use being able to extract keys during signing from EM leakage might just be the natural evolution of ATM/Payment Cards skimmer attacks.

In the past 2-3 years we had various key extraction attacks using "strange" vectors like EM/audio extraction, temperature, cpu usage, cross platform cache attacks, these attacks can threaten cloud computing and mobile computing quite severely unless we can root them out and being to modify the devices and platforms to be much more resistant to them.

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

#49

Post by ecesena »

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…

On a related note, it'd be interesting to see how these attacks work on curves over binary fields, e.g. ecb233.

These are available in OpenSSL, and the operations of addition and doubling have the same computational cost [1], so these attacks should be harder.

[1] when using affine coordinates, but that's the only thing implemented in openssl for curves over binary fields to the best of my knowledge

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

#50

Post by nullc »

CiPHPerCoder wrote: post #46
nullc wrote: post #36

Earlier quoted context omitted.

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…

> EdDSA is not fundamentally more sidechannel resistant; sidechannel resistance is a function of the implementation. > ... > It would be more accurate to say that so far EdDSA has had a more conscientious implementation culture around it. Your assessment is correct. EdDSA is deterministic which eliminates the nonce-reuse concerns, but deterministic EdDSA/ECDSA requires side-channel resistance. I erred in my previous…

Right.

One can easily implement EdDSA without deterministic nonce generation or with insecure nonce generation (it would be an error to call it EdDSA: but no verifier could tell; and if the signature is accepted that is EdDSA-enough for people to call it that in practice); likewise one could implement ECDSA with deterministic nonce generation (e.g. as specified in RFC6979).

It's not hard to find examples of both.

Post reply on HN