README

Does the code that handles a secret run in time independent of it?

memcheck already follows undefined bytes through arithmetic and reports the
moment one of them decides a branch or an address.  That is the same question,
so each driver here declares its secret undefined and runs under valgrind:
every report names a place where a secret reached a branch or an index.  The
technique is Adam Langley's ctgrind.

ct_canary.c is the calibration.  It branches on a secret and indexes a table
with one, so it must report; if it does not, the marking is not reaching the
code and the silence of every other driver in that run means nothing.  Round
five learned this the hard way with ThreadSanitizer, which saw nothing through
GHC's runtime including a deliberate race.

What is marked secret in each driver is the thing the caller would call a
private key, and nothing else.  A modulus, a peer's public key, a nonce and a
message are public and stay defined; so does each answer, which is declared
public again before anything looks at it.

  canary   a branch and a table index on a secret -- must report
  powm     crypton_powm_sec, the exponent being an RSA private key
  p256     both scalar multiplications and the scalar inversion
  x25519   the scalar
  ed25519  the private key, through signing
  decaf    Ed448 signing and X448, both private scalars
  chapoly  the ChaCha20 key, the plaintext, and the Poly1305 key
  aes      the AES key and the plaintext, through ECB and GCM

The aes driver is built against cbits/aes/generic.c and cbits/aes/gf.c on
purpose, rather than whatever the machine offers.  AES-NI and the ARMv8
instructions do not look anything up and would report nothing, which would say
nothing about the table-driven code every other machine runs.  That code is
variable-time by construction -- a table index is a byte of the state -- and
so is the table-driven GHASH beside it.  A report from the aes driver is
therefore expected and is a property of those implementations, not a defect
found in them; it is here so that the size of it is written down rather than
assumed.  Everything else is expected to be silent.

What round eight found
----------------------

Of the eight drivers, five were silent: the RSA exponentiation, X25519,
Ed25519, ChaCha20 and Poly1305 never let a private key decide a branch or an
address.  The AES driver reported from the tables, as it was built to.

The other two reported, five places between them, and every one of them an
assert():

  crypton_p256_modmul          assert(top <= 1), assert(top == 0)
  crypton_gf_448_strong_reduce two asserts on a carry and a borrow
  crypton_gf_invert            assert(ret), that what was inverted had an
                               inverse

The first four check an invariant of a reduction rather than anything about
the data, so they hold whatever the input is.  The fifth holds because the two
callers that ask for it are inverting a projective z, which is never zero for
a point on the curve.  Either way the branch goes the same way every time and
no timing follows from it.  They are reported at all because
crypton's C is compiled without NDEBUG, so assert() is live in a released
library.  Twenty-eight assertions ship that way, none of them with a side
effect, and defining NDEBUG measured no faster on P-256, so whether to keep
them is a question about what a library should do when an internal invariant
fails -- abort the process, or carry on -- rather than one about speed.  They
are listed in known.txt and the job passes with them.

The decision was to keep them: an internal invariant that fails in a
cryptographic library is better met with an abort than with a wrong answer
carried onwards.  So this is settled rather than open, and the five entries in
known.txt are permanent.  What is not permanent is anything else appearing
beside them.