mratsim commented 6 years ago

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 https://github.com/openssl/openssl/issues/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 commented 6 years ago

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

mratsim commented 4 years ago

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

status-im / nim-blscurve

Constant-time operations / side-channel attack resistance #2