(before using it for anything besides feeding the PRNG)

Part of #17694

This removes a comment presumably introduced for debugging that was left
in accidentally. Bug not in any released version of Tor. Fixes bug
17092.

Apparently this only happens with clang (or with some particular
clang versions), and only on i386.

Fixes 16970; bug not in any released Tor.

Found by Teor; fix from Yawning.

This should fix the x86 build, since variables that require 16 byte
alignment will now actually be 16 byte aligned.

This probably requires the user to manually set CFLAGS, but should
result in a net gain on 32 bit x86. Enabling SSE2 support would be
possible on x86_64, but will result in slower performance.

Implements feature #16535.

The code was always in our Ed25519 wrappers, so enable it when using
the ed25519-donna backend, and deal with the mocking related
crypto_rand silliness.

Implements feature 16533.

The only reason 16 byte alignment is required is for SSE2 load and
store operations, so only align datastructures to 16 byte boundaries
when building with SSE2 support.

This fixes builds with GCC SSP on platforms that don't have special
case code to do dynamic stack re-alignment (everything not x86/x86_64).

Fixes bug #16666.

This was causing a false positive on our arm builders.

This needs to be done to allow for the possibility of removing the
ref10 code at a later date, though it is not performance critical.
When integrated by kludging it into tor, it passes unit tests, and is
twice as fast.

Integrating it the "wrong" way into common/crypto_ed25519.c passes
`make check`, and there appear to be some known answer tests for this,
so I assume I got it right.

Blinding a public key goes from 139.10 usec to 70.78 usec using
ed25519-donna (NB: Turboboost/phase of moon), though the code isn't
critical path, so supporting it is mostly done for completeness.

Integrate ed25519-donna into the build process, and provide an
interface that matches the `ref10` code.  Apart from the blinding and
Curve25519 key conversion, this functions as a drop-in replacement for
ref10 (verified by modifying crypto_ed25519.c).

Tests pass, and the benchmarks claim it is quite a bit faster, however
actually using the code requires additional integration work.

This is a clean copy of ed25519-donna as of commit:

  8757bd4cd209cb032853ece0ce413f122eef212c

https://github.com/floodyberry/ed25519-donna

teor authored Sep 28, 2014 and Nick Mathewson committed Sep 28, 2014

Standardise usage in ge_scalarmult_base.c for 1 new fix.

This helps us avoid undefined behavior. It's based on a patch from teor,
except that I wrote a perl script to regenerate the patch:

  #!/usr/bin/perl -p -w -i

  BEGIN { %vartypes = (); }

  if (/^[{}]/) {
      %vartypes = ();
  }

  if (/^ *crypto_int(\d+) +([a-zA-Z_][_a-zA-Z0-9]*)/) {
      $vartypes{$2} = $1;
  } elsif (/^ *(?:signed +)char +([a-zA-Z_][_a-zA-Z0-9]*)/) {
      $vartypes{$1} = '8';
  }

  # This fixes at most one shift per line. But that's all the code does.
  if (/([a-zA-Z_][a-zA-Z_0-9]*) *<< *(\d+)/) {
      $v = $1;
      if (exists $vartypes{$v}) {
  	s/$v *<< *(\d+)/SHL$vartypes{$v}($v,$1)/;
      }
  }

  # remove extra parenthesis
  s/\(SHL64\((.*)\)\)/SHL64\($1\)/;
  s/\(SHL32\((.*)\)\)/SHL32\($1\)/;
  s/\(SHL8\((.*)\)\)/SHL8\($1\)/;

teor authored Sep 28, 2014 and Nick Mathewson committed Sep 28, 2014

The macros let us use unsigned types for potentially overflowing left
shifts. Create SHL32() and SHL64() and SHL8() macros for convenience.

There are some loops of the form

       for (i=1;i<1;++i) ...

And of course, if the loop index is initialized to 1, it will never
be less than 1, and the loop body will never be executed.  This
upsets coverity.

Patch fixes CID 1221543 and 1221542

When size_t is the most memory you can have, make sure that things
referring to real parts of memory are size_t, not uint64_t or off_t.

But not on any released Tor.

Add some documentation

Rename "derive" -> "blind"

Check for failure on randombytes().

Our integer-definition headers apparently suck in a definition for
select(2), which interferes with the select() in ge_scalarmult_base.c

This implementation allows somebody to add a blinding factor to a
secret key, and a corresponding blinding factor to the public key.

Robert Ransom came up with this idea, I believe.  Nick Hopper proved a
scheme like this secure.  The bugs are my own.

For proposal 228, we need to cross-certify our identity with our
curve25519 key, so that we can prove at descriptor-generation time
that we own that key.  But how can we sign something with a key that
is only for doing Diffie-Hellman?  By converting it to the
corresponding ed25519 point.

See the ALL-CAPS warning in the documentation.  According to djb
(IIUC), it is safe to use these keys in the ways that ntor and prop228
are using them, but it might not be safe if we start providing crazy
oracle access.

(Unit tests included.  What kind of a monster do you take me for?)

This will be needed/helpful for the key blinding of prop224, I
believe.

This is another case where DJB likes sticking the whole signature
prepended to the message, and I don't think that's the hottest idea.

The unit tests still pass.

Unit tests still pass.

Apparently, ref10 likes implicit conversions from int64 to int32 more
than our warnings do.

We might use libsodium or ed25519-donna later on, but for now, let's
see whether this is fast enough.  We should use it in all cases when
performance doesn't matter.