Constant time arithmetics

Context

Recent high-profile vulnerabilities in RSA (Cache-bleed), AES, ECDSA involved side-channel attacks. Most often those attacks were carried by timing the difference of execution time depending on user supplied input to restrict private keys to a subset of a large theoretical range.

Attacks can also allow decoding of a private encrypted message.

Other examples

• The Trusted Platform Module in all laptop is vulnerable to timing attacks: http://tpm.fail/
• TLS 1.2 and 1.3: https://www.cryptologie.net/article/461/the-9-lives-of-bleichenbachers-cat-new-cache-attacks-on-tls-implementations/

Concrete non-crypto example

You can read Twitter blogpost of Silhouette, an innovative side-channel attack that uses timing differences between private and public profile on Twitter to determine your Twitter identity bypassing all Twitter and browsers cookies and cross-site mitigations.

And another one exploiting the hardware Spectre vulnerability to read each bit at an arbitrary memory location in 5 lines of C.

Prevention

It is key that execution time does not depend at all on user supplied input. As cryptography rely in big integers computation, a constant time big int implementation is needed.

Challenges

Implementation

Even Openssl does not have full constant time implementation..

Fighting the compiler

We need boolean to implement logic, unfortunately there is no way to prevent compilers to use branches as soon as boolean are involved. So the library cannot use booleans at all and an alternative boolean type must be created.

Hardware

On some hardware, some primitive operations like multiplication are not constant-time. Given the resources we have, we should do constant-time as a best effort.

Guidelines

The following resources gives much more information on challenges, guidelines and implementations of constant time arithmetics:

• Constant-time crypto best practice
• https://bearssl.org/constanttime.html
• https://bearssl.org/ctmul.html
• https://bearssl.org/bigint.html
• Milagro Crypto White paper: http://docs.milagro.io/en/amcl/milagro-crypto-library-white-paper.html
• CryptoJedi on avoiding Carries: https://cryptojedi.org/peter/data/pairing-20131122.pdf
• Apache Milagro-Crypto paper: https://eprint.iacr.org/2017/437.pdf

Testing/implementing constant-time

• Dudect - Dude is my code constant-time
• Frama-C
• Usenix paper - Verifying constant-time implementation
• McBits: fast constant time crypto (Bernstein)