Timing Attacks on ECDSA, ECDHE, AES and SHA2

Question

Are there any known timing attacks (both practical and theoretical) on any implementations of the following?

1. ECDSA (I'm aware of this one - are there any applicable to prime fields?),
2. ECDHE (again, over a prime field),
3. AES,
4. SHA2

Answer 1

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.

Answer 2

Elliptic Curves over binary fields

In naive implementation of Elliptic Curves, either $GF(p)$ or $GF(2^{n})$ will be vulnerable to some timing attacks. The paper you provided is on OpenSSL's implementation of EC with $GF(2^{n})$. This implementation uses Montgomery's ladder scalar multiplication, which is in fact very good for making sure that most of the multiplication runs in constant amount of time per round. The issue is that the algorithm does not always run constant number of rounds.

Elliptic Curves over Prime Fields

The Attack presented against binary fields above could work against some implementations of some Elliptic Curves. However, many of NIST prime fields are just little bit less than $2^{log2(p)}$. Therefore, the bits of $k$ can have only very small bias. In ECDHE, if the peer is the attacker, a lot more inputs are controlled by the peer, but keys have short life time.

This paper is about attacking OpenSSL's RSA by measuring time used by a specific reduction at the end of Montgomery reduction. Although this is for RSA, similar reduction can be used if using Montgomery to calculate ECP (and thus it can be expected that some ECP implementations are likely vulnerable).

AES

Most AES implementations use table lookup, which means they usually are vulnerable to at least cache timing attacks. Paper describing timing attack against table lookup-based AES implementation on OpenSSL.

There are ways to avoid using table lookups, but they have cost:

• Either use new processor with AES instructions or
• Use only constant time instructions to replace the table lookup (likely causes significant performance penalty)

SHA-256 and SHA-512

SHA-256 and SHA-512 implementation only uses addition, rotation, and bitwise operations, all of which execute in constant time on most processors. The algorithms contain no input or state dependent table lookups. Thus, most likely implementations of these algorithms are timing attack free.

Summary

For most of the algorithms, i.e. ECDSA, ECDHE, AES the timing attack free implementation can be very hard to implement, and it may be also significantly slower. For these reasons, it is often not practical to make timing attack free implementation. In case you care about timing attacks, you need to ensure you use implementation expected to be timing attack resistant.

For AES, it is common for hardware-based implementations to be timing attack resistant (but not all).

For SHA-2, the most implementations appear to be likely side channel free.

In ECDHE, the keys used are ephemeral. For this reason, although in theory it could be possible to make timing attack, it is harder to make practical timing attacks than against ECDSA or AES.

Answer 3

There is vast literature on timing attacks on AES, but to the best of my knowledge no such attack on SHA-2 or any construction that uses SHA-2 (e.g., HMAC-SHA256).