researchers break openssl implementation in bitcoin with only 200 timing attacks
"Earlier this month a new paper by Naomi Benger, Joop van de Pol, Nigel Smart, and Yuval Yarom hit the news. The paper explains how to recover secret keys from OpenSSL's implementation of ECDSA-secp256k1 using timing information from "as little as 200 signatures"; ECDSA-secp256k1 is the signature system used by Bitcoin. The timing information is collected by an attack process running on the same machine, but the process doesn't need any privileges; I don't see any obstacle to running the attack process in a separate virtual machine. Earlier papers by Yarom and Katrina Falkner and Yarom and Benger had explained how to carry out similarly efficient attacks against various implementations of RSA and binary-field ECDSA.
These attacks are what I call "cache-timing attacks": they exploit data flow
- from secrets to load/store addresses and
- from load/store addresses to attacker-visible differences in timing between different addresses.
For comparison, conventional timing attacks exploit data flow
- from secrets to the program counter (i.e., the instruction address as a function of time) and
- from the program counter to attacker-visible differences in timing between different instruction addresses.
In both cases the second part of the data flow is built into chips, but the first part is built into the software.
Did the software designers have to allow data flow from secrets to addresses? "Obviously not!" say the theoreticians. "Everybody knows that any computation using branches and random access to data can be efficiently simulated by a computation that accesses only a predefined public sequence of instructions and a predefined public sequence of memory locations. Didn't you take a course in computational complexity theory? If the software designers had done a better job then this attack would never have worked."
I have a different view. I blame this attack on the ECDSA designers. Every natural implementation of ECDSA makes heavy use of secret branches and secret array indices. Eliminating these secrets makes the code much more complicated and much slower. (The theoreticians are blind to these problems: their notion of "efficient" uses an oversimplified cost metric.) The ECDSA designers are practically begging the implementors to create variable-time software, so it's not a surprise that the implementors oblige
if the design is insecure everything that follows and uses it will be insecure and you only have to wait untill it is discovered, manipulated and made so easy that it can be automatized