Constant-time operations / side-channel attack resistance

[mratsim]

Context

AMCL v3.1. claims that critical calculations are performed in constant-time:

Version 3.1 is a major "under the hood" upgrade. Field arithmetic is
performed using ideas from http://eprint.iacr.org/2017/437 to ensure
that critical calculations are performed in constant time. This strongly
mitigates against side-channel attacks. Exception-free formulae are
now used for Weierstrass elliptic curves. A new standardised script
builds for the same set of curves across all languages.

Obviously the calculation involving private keys must be constant-time, but not having everything constant-time might leave users open to other clever exploits.

Current implementation

For example comparison to zero or one is not constant time and key length can be deduced from it:

https://github.com/status-im/nim-milagro-crypto/blob/4add8c3441802b9962c966d023b629dcfb207640/src/generated/big_384_29.c#L34-L51

Modular inversion uses a lot of if statement, which cannot be constant time as due to cache/prediction misses we can deduce which branches were taken:

https://github.com/status-im/nim-milagro-crypto/blob/4add8c3441802b9962c966d023b629dcfb207640/src/generated/big_384_29.c#L1398-L1459

There is also no tests to count clock cycles for the AMCL library.

Others

This is not an isolated issue, even OpenSSL does not have complete constant-time arithmetics see openssl/openssl#6078, and had successful side-channel attacks against it for RSA (CacheBleed), AES, ECDSA

Testing/implementing constant-time

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

Wishlist

• Having a Nim macro that throws a compiler error if something is not implemented in a constant-time manner or at least, use a secret variable as a conditional.

Updated overview

https://github.com/status-im/nim-constantine/wiki/Constant-time-arithmetics

[cheatfate]

Some more links about constant-time:
https://bearssl.org/constanttime.html
https://bearssl.org/ctmul.html

[mratsim]

Solved by #66 and #68 and detailed investigative work in https://notes.status.im/nim-bls-curve-backends