Tracking constant-time claims

[D. J. Bernstein]

SUPERCOP now includes

(1) a simple mechanism for implementations to declare that they're
constant-time, and

(2) a modified version of Moritz Neikes's TIMECOP to make it easier
for implementors to search for variable-time compiled code (and
some other types of bugs) via valgrind.

This will provide a basis for collecting and checking data regarding the
NIST IR 8309 statement that "Faster, constant-time implementations on
Intel x64 processors were provided for many of the algorithms", and
regarding similar claims in round 3. It's important to track what's
actually claimed and known about this topic: consider, e.g.,

https://perso.telecom-paristech.fr/aschaub/publis/2018ivsw.pdf
https://frodokem.org/files/FrodoKEM-specification-20200325.pdf

suggesting that the Frodo code was constant-time even though it was in
fact exploitably variable-time (https://eprint.iacr.org/2020/743.pdf).

Mechanisms #1 and #2 are separate because the declaration is making a
security guarantee while TIMECOP isn't. Variable-time code can slip past
TIMECOP in various ways; constant-time code is the responsibility of the
implementor, not of TIMECOP. But TIMECOP did locate, e.g., the
variable-time Frodo code:

https://post-apocalyptic-crypto.org/timecop/crypto_kem/frodokem640/reference/index.html

I've checked 598 implementations of various primitives in SUPERCOP and
marked them as constant-time. I focused on subroutines marked "used",
but I also added constant-time declarations for ThreeBears (slightly
patched) and Ed25519 as crypto_kem and crypto_sign examples. The latest
benchmarks shown in

https://bench.cr.yp.to/results-kem.html#amd64-hiphop
https://bench.cr.yp.to/results-sign.html#amd64-hiphop

include red "T:" warnings for implementations that haven't been declared
to be constant-time---which is pretty much all kem+sign primitives for
the moment, but this can be expected to change rapidly.

Implementors should consult

https://bench.cr.yp.to/tips.html#constant-time
https://bench.cr.yp.to/tips.html#timecop

for more information. Feel free to ask questions on the eBATS mailing
list. Implementors who have already been careful to write constant-time
code should still run TIMECOP as a double-check and then send a message
to the eBATS mailing list along the following lines:

The following implementations are constant-time, and have been
checked by TIMECOP:

20200809 titan0 amd64 20200809 crypto_sign ed25519/constbranchindex timecop_pass crypto_sign/ed25519/ref gcc_-march=native_-mtune=native_-O3_-g_-fwrapv_-fPIC_-fPIE 1 0

Implementations that use rejection sampling will first need to add some
crypto_declassify() calls for the rejection conditions. TIMECOP will
then treat the rejection conditions as public. It's the implementor's
fault (or, more likely, the designer's fault!) if these rejection
conditions aren't actually independent of secrets.

Please _don't_ do automated TIMECOP runs through other people's code as
a basis for declaring that the code is constant-time. Again, TIMECOP
isn't making guarantees; there has to be a human in the loop taking
responsibility. Also, please don't do automated TIMECOP runs as a basis
for claiming that code _isn't_ constant-time; such claims are often
correct (as in the Frodo example) but often wrong (as in typical
rejection-sampling loops).

---Dan

[daniel.apon]

" SUPERCOP now includes ..."

 Awesome!

" I've checked 598 implementations of various primitives in SUPERCOP and
marked them as constant-time. "

Thank you Dan!!