From the abstract "We show that elliptic-curve cryptography implementations on mobile devices are vulnerable to electromagnetic and power side-channel attacks. We demonstrate full extraction of ECDSA secret signing keys from OpenSSL and CoreBitcoin running on iOS devices, and partial key leakage from OpenSSL running on Android and from iOS's CommonCrypto. These non-intrusive attacks use a simple magnetic probe placed in proximity to the device, or a power probe on the phone's USB cable. They use a bandwidth of merely a few hundred kHz, and can be performed cheaply using an audio card and an improvised magnetic probe".
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.
> - 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 to ecc' bug and implemented it themselves; or are otherwise reusing the verification multi-exp for signing)... and there are implementation of other things which are not vulnerable.
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 implementations" or "widely-used implementations".
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 ECDSA; they use Ed25519's deterministic Schnorr-style signatures. It's not even the same signature construction.
So what you're asking of the authors seems a bit like the authors of the DROWN paper explaining that their RSA padding oracle attack doesn't work if you instead use DH key agreement.
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.
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.
The paper serves to demonstrate that electromagnetic side-channel attacks on mobile devices (even almighty Apple stuff) are feasible. ECDSA is just an example they chose. Also, Curve25519 is only side-channel resistant to timing side-channels, this does NOT protect it in any way against the EM side-channels exploited in this paper. You can't expect the authors to go over every possible curve out there.
I was not questioning the impact of their demonstration, which is really impressive.
However, being responsible academics, they should have done their related work research. And when doing related work research on side-channel attacks against elliptic curves, it is hardly possible to miss Curve25519 and the fact that it was designed with side-channel attacks in mind. The authors at least reference earlier work by DJB on attacking AES.
Also, Curve25519 is only side-channel resistant to timing side-channels, this does NOT protect it in any way against the EM side-channels exploited in this paper.
This only reinforces the point that performing an EM side-channel attack on Curve25519/NaCl/Sodium would have been a good contribution to the state of the art, with mentioning Curve25519 in the "Future work" section a viable second.
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.
Constant time only reduces the chance of 'simple power analysis' (SPA) which is predominantly what the authors perform ('simple' is misleading but it's just the name for it).
There are a number of works that perform 'differential power analysis' (DPA) attacks on mobile devices that target symmetric crypto. These are generally both constant time and constant execution path. In this instance, attackers can attack the data dependancy in the EM emanations.
Simple example! a program that XORs two registers:
r1 = r1 XOR r2
If r2 has all the bits set to 1, then this will completely invert the contents of r1. This in turn consumes more energy (and hence emit more EM) in comparison to if r2 was all 0's. Hope that clarifies.
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.
That depends on the specifics. The fastest implementation of most integer instructions use constant time.
Constant power and EM depend on some extra factors, but when there is variance, it is normally very small (a transistor or two not switching for each bit of difference).
It's great to see this kind of work published. It is worth noting however that the US government is well aware of these kind of attacks. The Snowdon docs show that the CIA have been performing side-channel analysis since 2012 on the Iphone 4s and Ipad 2: https://theintercept.com/2015/03/10/ispy-cia-campaign-steal-...
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.
For us it was an iterative process that started with making a commitment to
do our best to do the right thing-- accepting that we don't control how the
users us the software and that to do a good job we must defend against a
very broad class of attacks... and that it's a good investment of time to
really refine the tools here so that the users have the least time lost
to worrying about the details of the underlying behavior. The earlier work on cache sidechannel attacks against OpenSSL also helped convince other people that this was important.
Pieter did a cache timing attack project against DES at his university in
2004. I had experience with modeling fine scale algorithm delays as part of
ultra-low latency audio codec work. So we had a little bit of additional background
beyond regular systems programming and mathematical experience.
We spent time studying other implementations and academic papers on the
subject-- just a product of searching and following citations-- and we implemented and measured (both in timing form and 'read
the assembly' form). Pieter had to do some algebraic work to adapt
a 'unified' group law approach to our curve and coordinate system.
[Then all of this also presented additional verification work to
validate that the new group law was algebraically correct.]
Because we accepted that this was going to be a considerable amount
of work, we didn't refrain from trying multiple ideas and throwing
things away. The libsecp256k1 codebase is written in a clean (IMO),
typesafe, heavily tested way that makes iteration easier.
We initially implemented a bit-slicing approach to achieve memory
access uniformity. After we thought we were at least a strict
improvement over OpenSSL, we contacted an outside expert (Yuval
Yarom, one of the authors of this paper, in fact) and they were
kind enough to give our implementation a look-- and pointed
out some additional research that showed our particular bit
slicing approach was not quite constant time on common hardware.
So we fixed that too.
I don't consider our work done on this-- we are likely vulnerable
to differential power analysis on at least some hardware. We've
implemented a basic level of blinding to harden against that-- but
without a good measurement setup it's hard to tell if our efforts are
helping (or maybe hurting, though that's unlikely). I loaned Thomas
Daede a USRP, and he's been attempting to set up a DPA continuous
integration rig for us (https://bitcointalk.org/index.php?topic=1319848.0);
but it's effort that is competing with a lot of other projects for
attention for all of us. Similarly some (now uncommon) hardware has things like data-variable time multipliers, and on that hardware little can be done beyond blinding; but again, without more analysis it's hard to know exactly where that stands.
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?
You can add noise, which means they will have to collect more data and filter it in order to perform the attack. That cans make the attack harder, but not impossible.
To me this sounds similar to the problem of how to execute a timing-based attack over a network with variable latency. The key is to make lots of requests very quickly. You can then statistically narrow down very small variations even though they're built on top of a larger trend signal like the network latency or a piece of music.
As another commenter suggested, there may also be signal processing techniques to "mod out" the interference from the music (perhaps measured with a probe on the audio output?) and measure only what's left.
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.
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 symmetric ciphers so 'constant' as not to reveal anything about the master key?
Side-Channel attacks are nasty. Wonder why the FBI wasn't able to use this to hack the San Bernardino iPhone 5C, the NSA must be aware of this? From the article
In the sequel, unless stated otherwise, the experiments were performed on Apple iPhone 3GS which exhibited a particularly clear signal.
Hope Apple fixes this in future models, even when opened.
San Bernardino 5C could be cracked in two days using a NAND flash write blocker. You only need to program an FPGA to buffer writes to NAND chips in RAM instead of passing them through and to allow the reads, then you just try N PIN codes and reboot while resetting the blocker state cache. N is 4 if they haven't tried any PINs and 1 if there are delays after each because they've tried a couple PINs already. Phone boot time is ~1 minute, T(10000) = 10000 minutes / N (= a week if N==1)
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:
A personal theory. The iPhone Wiki has a description of iPhone storage structure - it seems newer phones (pre Secure Enclave) don't have separate NOR, NVRAM and NAND - they just use NAND for everything.
[1] https://www.theiphonewiki.com/wiki/NOR
How would that attack work? The key isn't resident; it's derived in part from the passcode. The target can't do any useful work with the key that could leak through side channels, because it doesn't have the key.
iOS 9, which apparently isn't vulnerable to this, was released 3 months prior to the San Bernardino attack. Furthermore, is a locked phone just sitting there performing time-dependent ECDSA signing operations all day long?
This paper seems to focus on old Apple hardware (the newest I can find is the iPhone 5s). I wonder what the results would be on Apple's newest hardware (6 and above).
The Apple hardware perspective is mostly just a gimmick. The side-channel leaks are a direct result of the ARM IP core (also not Apple proprietary). This is arguably old news, people have been attacking ARM based mobile devices for years now.
It would be far more interesting to see if they could attack the Apple crypto hardware accelerators which AFAIK are hardened against these types of attack (as is the Apple CommonCrypto framework as of IOS 9). Apple seems to have ramped up their side-channel game in recent years.
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).
> 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.
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).
