Timing Attacks on ECDSA, ECDHE, AES and SHA2 Are there any known timing attacks (both practical and theoretical) on any implementations of  the following?


ECDSA (I'm aware of this one - are there any applicable to prime fields?),
ECDHE (again, over a prime field),
AES,
SHA2
The attack which you link to, on ECDSA, is related to the following: the signer computes several values $kG$, for random $k$ values chosen uniformly modulo $n$ ($n$ is the size of the subgroup generated by $G$). One such value is generated for each signature. It is important that the selection is uniform: even small biases can be exploited in order to make a key recovery attack. The crucial point is that each ECDSA signature consists in a pair $(r,s)$ where $s = (m+xr)/k \pmod n$ where $m$ is known (it is the hash of the signed message). Each signature involves a new $k$, thus a new $r$ (because $r$ is obtained from $kG$); the $r$ value follow a definite distribution modulo $n$. So if $k$ are biased, then the bias easily turns into an information leak on $x$ (the private key). As an extreme case, if a $k$ value is reused, then the two corresponding signatures suffice to recompute $x$ directly (this is what happened to Sony with their PS3 firmware signature system).

In the OpenSSL implementation of $kG$ on binary curves (using a variant of Montgomery's ladder), it so happens that the code was "optimizing" things by making $\lceil\log k\rceil$ iterations only; so that if $k$ was shorter than $n$ by, say, 3 bits (happens once every eight signatures or so) then the loop was slightly faster (3 less iterations). The attacker can detect that. If the attacker can make the target generate signatures on messages that the attacker knows (that's easy when the target is a SSL server; the attacker just has to connect), then the attacker can keep a subset of the signatures, precisely those where $k$ was "short". This becomes equivalent to a biased $k$ generation, and leads to private key reconstruction.

I describe this to show the important point: it is not specific to elliptic curves over binary fields. In fact, it is not specific to elliptic curves. A classic square-and-multiply implementation of a modular exponentiation for plain DSA could be equally vulnerable. Elliptic curves (in prime fields or binary fields) are not especially weak or strong in that matter. It is best described as a weakness of DSA (and variants, including ElGamal signatures and Schnorr signatures). To protect against it, the implementation must take care to take a constant time in all cases, so as not to leak information on $k$.



It seems unlikely that ECDH would suffer from a similar issue. With ECDH, leaking information about the private key length seems benign enough. The problem with DSA arises from leaking bias information on a value $k$ which is used along with the private key $x$ in "simple" operations (multiplication and division modulo a prime). Diffie-Hellman, be it modulo a prime or on an elliptic curve, does not feature such "simple operations" involving a randomly selected value and a permanent private key.

Moreover, in the case of ECDHE, the final "E" means ephemeral, which more or less implies that the DH private key will not live long. SSL/TLS server may reuse the same DH private key for a few connections (as long as the private key is kept in RAM only, it fulfills the "ephemeral" contract), but normal SSL/TLS servers tend not to do that much. Generating a new DH private key is efficient. This correspondingly severely limits the power of the attacker: timing attacks are statistical in nature, which means that they need to work over several measures which involve the same secret value. With ephemeral DH keys, the private keys can be regenerated often enough to defeat timing attacks in a quite generic way.



For AES, timing attacks are again based on implementation characteristics. Specifically, "normal" AES implementations use lookup tables, and thus exercise caches. The attack will work either on evicting parts of these tables from cache and then measuring the algorithm execution time (thus counting the number of cache misses involved during the execution), or on having the attacker's data evicted from cache when the AES block cipher runs, and then working out (again with timings) which parts of the data were impacted. In both cases, this allows the attacker to gain some information on the intermediate values used in the algorithm, leaking information on the key.

The attack is quite feasible when the attacker can run his own code on the same machine, so as to use the same caches (this is a setup which applies to traditional multi-user mainframes, but also to virtual machines, where one VM may spy on another). For a remote attacker, this has also been demonstrated in lab conditions, but then it depends on a lot of parameters, and the remoteness makes execution time harder to measure with high precision; applicability to any specific real-life situation is hard to assess.

There are table-free AES implementations (see this question) but they use specific CPU features, or are quite slower, or both. Recent x86 CPU have an hardware AES which is very fast, and immune to such timing attacks.



SHA-2 is a family of hash functions. As such, they don't have keys. If they contain no secret, then there is nothing to obtain through timing attacks...

A hash function may be used on secret data, though, in particular in HMAC. SHA-2 is all arithmetic operations, no tables, no data-dependent branches. It seems hard to make a SHA-2 implementation which would be susceptible to timing attacks.