# Constant time implementations of crypto algorithms

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?

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.

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

2. 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.

• Can you elaborate a bit on how every function can be made side channel resistant? – stflow Mar 12 '18 at 4:22
• In the worst case you have to compute all branches and arithmetically mask out the results you're not interested in. This increases computation cost by computing all variants instead of revealing branches based on secrets I.e. indexing lookups over an array or branching if some number is negative. Bit slicing is what we use to make constant time AES. Bit slicing may sometimes even be faster – cypherfox Mar 12 '18 at 4:38
• Regarding hardware acceleration of arbitrary functions. If you accelerate chacha20, you'll be disappointed with the ratio compared to soft vs hard AES. – cypherfox Mar 12 '18 at 4:40
• Thanks! So the EC * functions (or at least parts of it) are not typically implemented in hardware is it? – stflow Mar 12 '18 at 4:52
• Side-channel is much more than timing. We know of no way to protect implementations up to an infinite order power attack, therefore I would rather say that no function can be made side channel resistent. – Ruggero Mar 13 '18 at 11:47

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.

• Thanks for that information on AES. Will look up bitslicing. Is it implemented in openssl or any of the popular libraries? – stflow Mar 13 '18 at 3:14
• @stflow It looks like OpenSSL's bitslicing implementation for x86 requires SSSE3, so it has the same requirements as the single-block one. I imagine that the bitsliced SSSE3 version is faster than the single-block SSSE3, though. – Myria Mar 13 '18 at 5:37
• What are the sources of non-constant time for AES? I mean there's no exponentiation or something similar which is highly dependent on time. – hola Sep 23 '20 at 6:44