Constant-time operations / side-channel attack resistance
mratsim opened this issue · 2 comments
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:
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:
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
Some more links about constant-time:
https://bearssl.org/constanttime.html
https://bearssl.org/ctmul.html
Solved by #66 and #68 and detailed investigative work in https://notes.status.im/nim-bls-curve-backends