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
  aes_armv8  the same driver again, on AArch64, against the instructions

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.

On AArch64 the same driver is then built a second time, as aes_armv8, against
cbits/aes/armv8.c with the crypto extension turned on.  AESE, AESMC and PMULL
look nothing up and branch on nothing, so that run must report nothing at all
-- not "nothing outside known.txt", nothing; a table site appearing there
would mean the dispatch had not picked the instructions.  The two runs keep
each other honest: the table-driven one has to report and the instruction one
has to be silent, and either going the wrong way says the run is not
measuring what it claims to.

Until that was added the harness ran only on x86-64, so crypton's AArch64 AES
and GHASH had never been put to it -- which was noticed when the GHASH was
rewritten.

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.