Constant time implementations of crypto algorithms

Question

To protect against cache attacks (side channel attacks) generally constant time crypto implementations are advised. In some cases DJB released new algorithms (chacha) that are designed with this in mind (as one of objectives). If so --

1. Are constant time implementations feasible for all popular algorithms? I ask because AES, RSA, SHA*, EC* and DSA algorithms (at least some of them) are not designed with side channel attacks in mind. Given that, are these secure to use in software? ( I know secure is a loaded term here but I am speaking strictly from a side channel perspective).

2. Do all the standard libraries support this constant time implementations? I would like to see an implementation that does this compare against something that does not.

3. I know using an algorithm in hardware is the way to go. When a crypto algorithm is "implemented in hardware", does it usually mean its implemented completely in hardware or are parts of it implenented in microcode? I know AES is probably completely implemented in hardware, what about ECDSA or something thats a bit more complicated?

Answer 1

1. Any function can be made timing attack resistant, and may be more expensive. I.e. AES can be made safe by using a hardware-simulated constant time circuit for lookups (and maybe more magic).

If you need AES: use hardware with a constant time fallback in software. If you don't need AES then prefer it by hardware, then negotiate to a fast software cipher such as chacha20.

2. I'm yet to investigate (as I don't use these "standard libraries"). Which libraries are we including in standard? OpenSSL? LibreSSL? BoringSSL? Libsodium?

3. The AES round function is implemented in hardware. This enables the caller to decide the mode I.e. CTR vs CBC vs GCM etc. Last I checked AESNI included sha1 and sha2, but not any ECDSA nor ECDH nor EdDSA nor RSA. Hardware can implement any of these, however, not all functions have a significant speedup in hardware such that using hardware is preferred.

Answer 2

Regarding AES:

AES in a straightforward, single-block mode is generally written in a way that can be vulnerable to cache timing attacks, and potentially related attacks like Spectre. This is because the only way to get reasonable speed at AES single-block with normal code is to use lookup tables.

x86 CPUs from the last five years or so have AES-NI, and most 64-bit ARM CPUs have the ARMv8 crypto extensions. These are direct implementations of the AES round function in hardware, and are immune to timing attacks.

For CPUs a bit older than these, x86 CPUs with SSSE3 and ARMv7 CPUs with NEON (or ARMv8 CPUs without the crypto extensions, such as the Raspberry Pi 3) can use a vector permutation-based algorithm to do single-block AES in a constant time. The SSSE3 variant is implemented in OpenSSL; I don't know about ARMv7, but I know that it is possible.

On all machines, though, an efficient constant-time implementation is possible if you encrypt 8 blocks at a time. This is the "bitslicing" implementation: you simulate the individual bit operations that a hardware implementation would use. The 8 blocks at a time is for efficiency: bitslicing is considerably slower than a table-based implementation for single blocks, but you can use the width of the CPU's registers to parallelize it.

The biggest downside to bitsliced implementations comes to how you need to provide 8 blocks at a time. Certain block cipher modes cannot be parallelized for a single data stream. For example, the CBC cipher mode cannot be parallelized for encryption, because the input to the current block's cipher depends on the output of the previous block's cipher. (It can be parallelized for decryption.)

If you go the route of using a bitsliced implementation, use a cipher mode that can be parallelized. The common such modes are CTR (counter) and GCM (Galois counter mode). Galois counter mode is expensive on CPUs without hardware AES acceleration, though, due to the need to do carry-less (polynomial mod $2$) multiplication. CTR mode, in contrast, provides no integrity protection on its own, so must be accompanied by something else (such as HMAC). These are tradeoffs to consider.