Documented 2^255-19 carry propagation

Fixes #185

Carry propagation is now justified, in a way that I can personally vouch
for (I used to rely on SUPERCOP's ref10 code and proofs).

The use of arithmetic right shifts is also documented, and a workaround
has been devised in case someone somewhere uses a platforms that does
not perform sign extension. (That will never happen.)

Fixed assumption in 2^255-19 carry propagation

Careful re-examination of the carry propagation code revealed that
SUPERCOP's invariants for fe_tobytes() were not respected: there is a
possibility that the inputs slightly outrange the set of input for which
SUPERCOP's original proof was intended.

This happens in invsqrt(), used for EdDSA verification And Elligator,
and the reverse map of Elligator.  X25519 is unaffected.

Note that we were unable to produce a set of input that actually
triggers this range overflow.  Moreover, careful mathematical analysis
(and tests with SAGE) showed that fe_tobytes() is actually much more
tolerant than SUPERCOP's proof let on.  As far as I can tell, this
slight overflow cannot trigger any observable bug.

Still, I figured it would be a good idea to abide those invariants
anyway, if only to facilitate future audits.  To this end, I made sure
the inputs of fe_tobytes() came directly from either multiplications
(which perform a carry propagation), or constants (where carry
propagation has been pre-computed).

TIS-CI: ensure results are correct

Lighter TIS-CI tests

Overhauled TIS-CI test suite

Tests: fixed tweak coverage for Elligator.

Shifting the index by 6 caused a reuse of one bit, leading to 4
different configurations instead of 8.
Shifting by 5 means we are using the 3 least significant bits of the
index, as was always intended.

Fixed tis-ci.c declarations

Removed non-standard empty array

Manual: fixed old HChacha20 function name

Manual: function prototype typo

Tests: all messages to standard ouput

Never ignore test failures

Added vector based Chacha20 tests

Re-ignore tests/vectors.h

simplified TEST macro

We'll no longer need the entry points, TIS-CI will have dedicated tests

Reworked test vectors header format

- Removed the header from git (we will no longer need it)
- Replaced the direct arrays by character strings in hexadecimal format.

That last one is an attempt to make those vectors more readable and
smaller (vectors.h is the biggest source of bloat in the tarballs).

Merge pull request #195 from fscoto/master+doc-malleability

doc: clarify signature malleability in crypto_sign

doc: clarify signature malleability in crypto_sign

Fixes #189; see the discussion there for details.

Dedicated test suite for TIS-CI

TIS-CI needs a dedicated test suite, different from the regular one.  So
I'm following my Chief Testing Officer's advice, and stole his work like
I should have from the very beginning.

We'll need to refine this, but this should be a good first step.

Merge pull request #191 from fscoto/master+doc-malleability

HISTORY: note 2.0.5 rejecting modified signatures

Merge pull request #192 from fscoto/master+argon2i-oops-the-params-also-matter

argon2i: Note that all parameters influence output

argon2i: Note that all parameters influence output

Sparked by #190.

HISTORY: note 2.0.5 rejecting modified signatures

Change introduced in 974e55d21c1fac7a2e21f91cb7174601b653180a and
24f4be7acc3ec7ff613715a7a97597e587f6d6d8.

The actual reasons to introduce this were actually performance-related.

Sparked by #189.

documented make install USE_ED25519=true

Fixed copy in man2html.sh

Poly1305 carry propagation now uses loops

Mostly for consistency with 25519 arithmetic.
Also slightly reduces binary size in some cases, most notably -Os.

Small carry simplification

More readable Blake2b unrolled loop

Fixed compiler warning

Fixes #187

Note: w should remain a signed integer, so w-1 is correctly compared in
the FOR_T loop.

No longer ignore tests/vectors.h (for TIS-CI)

Fixed tis.config (3)

Fixed tis.config (2)

Fixed tis.config

Added TIS-CI support

Prepared entry points for TIS-CI

Separated basic/advanced functions in different folders

Addresses MON-01-005
Fixes #182

Better low/high level separation in the header.

Partially addreses MON-01-005.  #182

Also added various warnings in comments.

Also pretend the min number of Argon2i iterations passes is 3.
It's not true, but any less would not be secure.

Argon2i hash is now allowed to overlap with the work area

Fixes #183

Almost all of Monocypher allows arguments to overlap. Users may come to
expect it, and misuse those who don't allow such an overlap. (Chacha20
and AEAD are an exception, but (i) portability concerns prevents us to
allow it properly, and (ii) disallowed overlaps tend to trigger visible
corruptions immediately.)

Before, having the hash coincide with the working area meant the output
was always zero.  All passwords have the same hash.  Therefore all
passwords are correct.  Oops.  For the record, I made the mistake, and
caught the bug only days later, by pure luck.

Now overlap is allowed, and gives the right result. Note that the work
area is still wiped.  The wipe just happens *before* the final hash is
computed.

Merge pull request #184 from fscoto/master+mon-01-001

intro: macOS, illumos and Solaris have arc4random_buf(3)

Fix #180

intro: macOS, illumos and Solaris have arc4random_buf(3)

Better test for crypto_x25519_inverse()

Removed redundant all zero test vector

Added Kleshni/Elligator-2 test vectors

An auditor recently told me about the following repository on GitHub:

  https://github.com/Kleshni/Elligator-2/

I was able to steal a couple test vectors from them.  Not all of them
unfortunately:

- Some representative exceed 2^254, and Monocypher do not decode
  negative representatives.  Instead, it assumes it has a positive
  representative, and clears the two most significant bits before
  decoding.

- It is not clear yet what encoding does, and some points in the (few)
  test vectors have their most significant bit set. Monocypher ignores
  the most significant bit of curve point, basically assumes they are
  all below 2^255 - 19.  Adding those points will require tweaking
  similar to the tweaking applied to the Hash to Curve RFC draft test
  vectors.

Added extern "C" to optional & deprecated files

Adjusted changelog date

Updated changelog

Optimised key loading in Blake2b

The idea is to avoid the slow loading code in the internal
blake2b_update() function, and avoid the overhead of calling
crypto_blake2b_update().

It's a micro-optimisation that in principle shouldn't matter that much,
but it might help a bit if we repeatedly hash small messages with a key,
as can happen in authenticated key exchanges like Monokex.

Removed #define from vectors.h

Also reduced the size of vectors.h by removing indirections and printing
numbers in decimal form. Hopefully this will make the tarball a little
smaller.

Fixed various compiler warnings

Fixes #179

Merge pull request #178 from fscoto/master+fix-includes

doc: Fix .In for optional code

doc: Fix crypto_ed25519_public_key function name

doc: Fix .In for optional code

README: Monocypher is not compatible with NaCl

Fixes #177

This removes the suggestion that we can replace Monocypher with NaCl.
We cannot, only Libsodium is compatible.

Cosmetic. compact grouping of vtables

Turned ALIGN into a function

Merge pull request #173 from fscoto/master+reproball

Make tarball generation reproducible

dist.sh: Make tarball reproducible

Make Elligator test vector gen deterministic

This paves the way for reproducible tarballs.
Since the test vectors must be generated for a complete tarball,
these must agree everywhere.

The lack of actual randomness is harmless because these are test
vectors, not actual usages of Elligator.

More readable Blake2 round function

Fixed (NULL + 0) undefined behaviour

It appears that arithmetic on NULL pointers is undefined, even when we
just add zero.

Monocypher generally allows input buffers to be NULL pointers if their
length is zero.  This is because we never dereference those pointers in
this case.  Likewise, we should not perform any arithmetic on them.

The fix is to return immediately when the input buffer length is zero.

Merge pull request #171 from stevefan1999-personal/patch-1

Add extern C if C++ presents

Update monocypher.h

Trim scalar in place

Fixes #170

Reverts 6411aa419f113a283feac0240b736a1f7e1e8ed1

Turns out MSVC didn't like the aliasing in trim_scalar(), and managed to
break the code.

And this wasn't very elegant in hindsight anyway.

Worked around Microsoft compiler warning

Fixes #169

MSVC issues a warning when we try to negate an unsigned number.  The goal
however was to perform bit twiddling, so I used bitwise negation.
Hopefully the compiler will not complain about overflow, which is
perfectly well defined on unsigned numbers.

Reordered functions and constants

Inlined fe_mul121666)

Simplified GF(2^255-19) carry propagation

There used to be two ways to perform carry propagation: a "fast" one,
used after decoding and multiplication by small numbers, and a "safe"
one, more conservative, used after full multiplications or squarings.

Using the safe carry propagation simplifies the source code and
facilitates audits.  The cost is a 1% performance hit for X25519.

Fixed shift of integers on 16 bit machines

Indentation fix

comment nitpick

Merge pull request #168 from fscoto/master+argon2-doc-iter

argon2i: Warn about conequences of nb_iterations < 3

argon2i: Warn about conequences of nb_iterations<3

Update CHANGELOG date

Fixed CHANGELOG version number

Various makefile cleanups

Moved the pkg-config files elsewhere, to simplify the makefile. A simple
variable substitution takes care of $(PREFIX).

Fixed missing "/" in libdir path (which somehow didn't seem to confuse
pkg-config).

Path variable no longer include $(DESTDIR). Instead, we prefix it
explicitly every time we use a path.

More thorough testing

Nitpicks

Some more tests

Merge pull request #165 from fscoto/master+license-bump

LICENCE.md: Bump everyone's year

Merge pull request #164 from fscoto/master+misc-doc

Sweeping manual review nitpick fixes

LICENCE.md: Bump everyone's year

Non-trivial contributions by everyone.

Address review concerns from #164.

1. Remove recommendation for 512-bit BLAKE2b.
   32 bytes is enough, and it's not like we offer EC functions of a
   higher security level either.
   The text added in 628f027 already does enough to recommend proper
   hash output lengths.
2. Bump .Dd date in crypto_poly1305.3monocypher.
3. crypto_verify16 add "byte by byte" for both accuracy of how a MAC
   with a variable-time comparison function will be found and
   for dramatic reasons because it sounds like doom is slowly
   approaching, byte by byte.

crypto_ietf_chacha20: Add missing section to .Xr

While there and bumping dates, fix authorship years for the CC0 part.

crypto_sign_init_first_pass: Swap emphasis

The original emphasis, when skimmed, made the message read that the
first pass *causes* loss of all security, which is the opposite of what
we want to emphasize.

Also bump authorship notice years while there and mdoc date that we
forgot to bump when we introduced the power-analysis and glitching
example.

crypto_sign: s/document/message/

We don't need to introduce new, confusing terminology right at the end
of the page.

crypto_curve_to_hidden: Add missing word

crypto_argon2i: The given usages are just examples; clarify as much

crypto_blake2b: Harmonize description with MAC example

crypto_verify: wording nitpicks

1. s/guessed a few bytes/guessed a byte/
   Nobody guesses multiple bytes per attempt except by sheer dumb luck.
2. Add missing "functions" to make one sentence not seem incomplete.

intro, crypto_poly1305: standardize "one-time"

doc: crypto_xchacha20 does XChaCha20, not Chacha20

crypto_x25519: Note that _from_eddsa exists

crypto_key_exchange: Note that _from_eddsa exists

Manual: nits & typos

Update changelog

Fixed copyright year

Added constant time tests with Valgrind

The trick is to call Monocypher API with uninitialised buffers.

If Valgrind complains about uninitialised something, that means an array
index or a conditional jump depends on secret data.

Note that crypto_check() is not tested: that's because it doesn't even
try to be constant time.

Note that a couple tested functions do have secret dependent conditional
jumps.  Those jumps however are just final checks, that just reveal
success or failure (and those are revealed anyway, as part as the
semantics of the function being tested).

Note that optimisations are disabled for the compilation of `ctgrind.c`
and the linking of `ctgrind.out`. This is an attempt to maximise
Valgrind's findings.

Also note that Valgrind seems to miss a secret dependent conditional
jump (it finds only one where we should have 2). But that may just be
Valgrind squashing the error report, instead of an actual miss.

Manual: fixed function name

Squeeze some more lines of code

And we are back below 2000

Optimised scalar inversion with Montgomery multiplication

This causes us to overshoot the 2000 lines mark by 35 lines or so.  But
this is much faster than using the much slower mul_add() routine.