Merge pull request #125 from fscoto/master

Document BLAKE2 RFC

Document BLAKE2 RFC

Merge pull request #124 from fscoto/master

README: nitpicks

README: nitpick: make links HTTPS where possible

README: nitpick: missing colon

Options 1 and 2 had colons after them, but option 3 didn't.

Merge pull request #123 from fscoto/master

manual: roff formatting fixes

manual: roff formatting fixes

Merge pull request #122 from fscoto/master

Add HISTORY sections

manual: Address HISTORY review concerns

Add HISTORY sections

Clarified installation instructions

Related to #120

Made the 3 options (from source, from lib, system wide installation)
clearer, and stated the ability to change compilation flags explicitly.
(Those flags are all standards, but not everyone may know them).

Merge pull request #121 from fscoto/master

makefile: switch from $() to backticks

makefile: switch from $() to backticks

This fixes building with gmake on Solaris 10,
and likely some other platforms with /bin/sh before POSIX standardized
$() for command substitution.

Addresses issue #120.

Edit nipick

Merge pull request #119 from fscoto/master

Update manual with variable changes

crypto_kex_{x,xk1} man pages: address review

Better represent Fabio Scotoni's involvment

Update manual with variable changes

Also pulls the descriptions of the arguments to the front,
which makes them easier to discern.

Fixed variable shadowing

Optimised Poly1305 loading code

By actually *rolling* the loading code.  I haven't looked at the
assembly, but I suspect the loop is easier for the compiler to
vectorise.

This results in a 5% speed increase on my machine (Intel i5 Skylake
laptop, gcc 7.3.0).

This fix was made possible by @Sadoon-AlBader on GitHub, who submitted
pull request #118

Clarified why some buffers are not wiped

ge_msub() and ge_double_scalarmult_vartime() aren't clear why they don't
wipe their buffers.  I have added warnings that they indeed don't do so,
and thus should not be used to process secrets.

This also makes clear to auditors that failing to wipe the buffers was
intentional.

Argon2 salts are at least 8 bytes

Improved the key exchange API

crypto_kex_ctx is now differentiated into a client specific context, and
a server specific context.  The distinction is entirely artificial (it's
the same thing under the hood), but it prevents some misuses at compile
time, making the API easier to use.

The name of the arguments have also been changed: "local" and "remote"
have been replaced by "client" and "server" whenever appropriate.  The
previous names made implementation easier, but their meaning was context
dependent, and thus confusing. The new names have stable meanings, and
thus easier to document and use.

TODO: update the manual to reflect those changes.

Merge pull request #117 from fscoto/master

man: fix whitespace and macro invocation issues

man: fix whitespace and macro invocation issues

- There was some trailing whitespace on some of the lines of the new
  pages that I hadn't noticed.
- There was a .PP instead of .Pp.
- There was a .Fa with no space after it.

Merge pull request #116 from fscoto/master

LICENCE: update copyright year

LICENCE: update copyright year

Changes have been made since 2017.

Merge pull request #115 from fscoto/master

Add kex man pages

American -> British

Address points brought up by @LoupVaillant in review

Add kex man pages

Corrected undefined behaviour in kex tests

Calling those functions again on the same status not only does not make
any sense, it can grow the transcript beyond its maximum size of 128
bytes, which triggers a buffer overflow.  We needed to save the context
so we could re-run the relevant function where we left of.

It's the second time the TIS interpreter finds a bug that the other
sanitisers didn't.

Added secure channel protocols (experimental)

At long last, the NaCl family of crypto libraries is gaining direct
support for secure channels.

Up until now, the choices were basically invent our own protocol, or
give up and use a TLS library, thus voiding the usability improvements
of NaCl libraries.

Now we have a solution.  It's still a bit experimental, it's not yet
documented, but it's there.  And soon, we will finally be able to shift
the cryptographic right answer for secure channels away from TLS, and
towards the NaCl family.  Or perhaps just Monocypher, if for some reason
Libsodium doesn't follow suit. :-)

Build: allow overwriting of symbolic link

More RFC number corrections

RFC 7539 has been obsoleted by RFC 8439.
Incremental EdDSA didn't change to RFC 8032.

Corrected RFC number in EdDSA manual

Clarified Argon2 allocation in the manual

Added comment on speed tests

The way I measure timings is not perfectly portable. Users who
get weird results are encouraged to modify this bit of code to
have proper measurements.

Fixed speed-sodium build

Removed division by zero in speed benchmarks

If some library is so fast that it goes below the resolution of the
timer we're using to measure it, the measured duration may be zero, and
then trigger a division by zero when we convert it to a speed in Hz.

This could possibly happen with a very fast library (Libsodium), on a
very fast machine, with a sufficiently low resolution timer.

This patch reworks and simplifies things a bit, and adds an explicit
check. We now print "too fast to be measured" instead of dividing by
zero.

Documentation typo

Wrong array size in function argument

Fixes #114

Most proably harmless, but nevertheless ugly.

Forgot Libsodium include dependency

Allow the test suite to customise its random seed

This will only affect the property based tests, not the test vectors
themselves.  The idea is to let paranoid users run the test suite with
lots and lots of different streams of random numbers, just to be safe.

Test vector generation could undergo a similar transformation, though it
is less likely to be worth the trouble (we'd have to generate the test
vectors, compile the test suite all over again).

Link SHA-512 code when using -DED25519_SHA512

When the $CFLAGS variable contains the -DED25519_SHA512 option (by
default it doesn't), the code from src/optional/sha512.c is
automatically linked to the final libraries (libmonocypher.a and
libmonocypher.so).

That way, users who need to install a ED25519 compliant version of
Monocypher can do so simply by altering the compilation options with the
$CFLAGS variable.

Made L an array of *signed* integers

Was unsigned previously, causing a bunch of implementation defined
conversions.  No machine nowadays are no 2's complement, but it's still
cleaner that way.

Try not to waste the stack

Fixed MSVC W4 warnings

Fixes #112

Decoupled window widths, minimised stack usage

The width of the pre-computed window affects the program size. It has
been set to 5 (8 elements) so we can approach maximum performance
without bloating the program too much.

The width of the cached window affects the *stack* size. It has been set
to 3 (2 elements) to avoid blowing up the stack (this matters most on
embedded environments). The performance hit is measurable, yet very
reasonable.

Footgun wielders can adjust those widths as they see fit.

Inlined window caching

Optimised addition of base point window

Fully pre-compute the base point window

Parameterise sliding window width with a macro

This is more general, perhaps even more readable this way. This also
lays the groundwork for using different window widths for the
pre-computed window and the cached one. (The cached window has to be
smaller to save stack space, while the pre-computed constant is allowed
to be bigger).

Test -DBLAKE2_NO_UNROLLING flag

Convert int indices to size_t

Fixes #111 (MSVC warnings)

All indices in Monocypher are size_t.  We might as well be consistent.

Added -DBLAKE2_NO_UNROLLING preprocessor option

Less bloat, faster on some embedded platforms.

Const correctness

No intermediate buffer for HChacha20

That buffer wasn't really needed, so I optimised it away

Overlap test for HChacha20

Manual: wrong nonce size in examples

Removed version numbers from coverage script

Merge pull request #108 from fscoto/master+doc/windows-random

Recommend BCryptGenRandom on Windows

Recommend BCryptGenRandom on Windows

CryptGenRandom is deprecated.

Better code coverage for EdDSA

C++ compatibility

2.0.5 changelog

fe_ccopy() now works the same as fe_cswap()

cosmetic

Added tests for HChacha20

Not that it needed any (XChacha20 were enough), but it's easier to
communicate to outsiders that HChacha20 is correct when we have explicit
test vectors.

Properly prevent S malleability

S malleability was mostly prevented in a previous commit, for reasons
that had nothing to do with S malleability.  This mislead users into
thinking Monocypher was not S malleable.

To avoid confusion, I properly verify that S is strictly lower than L
(the order of the curve).  S malleability is no longer a thing.

We still have nonce malleability, but that one can't be helped.

Also added Wycheproof test vectors about malleability.

Simplified sliding windows a bit

Removed sliding windows edge cases

By making sure the scalar's most significant bits are 0, we remove an
edge case, and can skip the epilogue of the sliding windows.

This adds 2 bytes to the sliding windows representation of the scalars,
but also makes the code smaller and simpler.

Corrected wrong comment

Signed sliding windows for EdDSA

Signed sliding windows are effectively one bit wider than their unsigned
counterparts, without doubling the size of the corresponding look up
table.  Going from 4-bit unsigned to 5-bit signed allowed us to gain
almost 17 additions on average.

This gain is less impressive than it sounds: the whole operation still
costs 254 doublings and 56 additions, and going signed made window
construction and look up a bit slower.  Overall, we barely gained 2.5%.

We could gain a bit more speed still by precomputing the look up table
for the base point, but the gains would be similar, and the costs in
code size and complexity would be even bigger.

Reduced EdDSA malleability for sliding windows

Signed sliding windows can overflow the initial scalar by one bit.  This
is not a problem when the scalar is reduced modulo L, which is smaller
than 2^253.  The second half of the signature however is controlled by
the attacker, and can be any value.

Legitimate signatures however always reduce modulo L.  They don't really
have to, but this helps with determinism, and enables test vectors.  So
we can safely reject any signature whose second half exceeds L.

This patch rejects anything above 2^253-1, thus guaranteeing that the
three most significant bits are cleared.  This eliminate s-malleability
in most cases, but not all.  Besides, there is still nonce malleability.

Users should still assume signatures are malleable.

EdDSA double scalarmult can now subtract

This allows it to handle signed sliding windows (not yet implemented).

EdDSA sliding windows now indicate the number

This is in preparation for signed sliding windows.  Instead of choosing
-1 for doing nothing, and an index to point to the table, we write how
much we add directly (that means 0 for nothing).  We divide the number
by 2 to get the index.

The double scalarmult routine doesn't handle negative values yet.

Thank Mike Hamburg for his advice on comb algorithms

Referenced the signed comb for EdDSA

Factored out mul_add() algorithm

It is was originally only used in signature verification, but the
transformation to all bits sets for the signed comb algorithm now also
uses it.

It also makes the high level algorithms a bit more readable.

EdDSA is back to constant time

Proper Signed comb for EdDSA (not constant time yet)

Signed comb with unsigned table

Or, bitwiseshiftleft saves the day.  The current code is hacky as hell,
but it works, and it cleared up my confusion.  Turns out a suitable
signed comb is quite different from an unsigned one: the table itself
should represent -1 and 1 bits, instead of 0 and 1 bits.

Right now the same effect is achieved with 2 additions (more precisely,
an addition and a subtraction).  With the proper table, it can be one
operation.

Desperate attempt to sort the signed comb mess

Separated odd/even tables

5-bit table for EdDSA

Just to make sure the table generation process is correct.

Moved EdDSA scalar operations

Just ground work for signed combs.

Inlined ge_from_xy() (called only once)

Avoid macros where we can

Turns out a simple test (which doesn't depend on a secret) was enough to
not need the macro at all.  And we still save that multiplication.

Avoids the first doubling for EdDSA signatures

The overhead of this first multiplication is not much, but it's
measurable.

Note the use of a macro for the constant time lookup and addition. It
could have been a function, but the function call overhead eats up all
the gains (I guess there are too many arguments to push to and pop from
the stack).

Avoids the first few doublings in EdDSA verification

Legitimate scalars with EdDSA verification are at most 253-bit long.
That's 3 bits less than the full 256 bits.  By starting the loop at the
highest bit set, we can save a couple doublings.  It's not much, but
it's measurable.

Comb for EdDSA signatures in Niels coordinates

While it takes a bit more space to encode, this also avoids some initial
overhead, and significantly reduces stack size.

Note: we could do away with the T2 coordinate to reduce the overhead of
constant time lookup, but this would also require more work per point
addition.  Experiments suggest the bigger table is a little faster.

All field element constants have the proper invariants

A number of pre-computed constant didn't follow the ideal invariants set
forth by the carry propagation logic.  This increased the risk of limb
overflow.

Now all such constants are generated with fe_frombytes(), which
guarantees they can withstand the same number of additions and
subtraction before needing carry propagation. This reduces the risks,
and simplifies the analysis of code using field arithmetic.

Revert "Cleaner fe_frombytes() (loading field elements)"

This reverts commit 6ee8787e61b3918789eab0ab38ce176abc767abb.

Turns out this commit was a huge blunder.  Carry propagation works by
minimising the absolute value of each limb.  The reverted patch did not
do that, resulting in limbs that were basically twice as big as they
should be.

While it could still work, this would at least reduce the margin for
error.  Better safe than sorry, and keep the more versatile loading
routine we had before.

Likewise, constants should minimise the absolute value of their limbs.
Failing to do so caused what was described in issue #107.

Cleaner fe_frombytes() (loading field elements)

The old version of fe_frombytes() from the ref10 implementation was not
as clean as I wanted it to be: instead of loading exactly the right
bytes, it played fast and loose, then used a carry operation to
compensate.

It works, but there's a more direct, simpler, and I suspect faster
approach: put the right bits in the right place to begin with.

Merged the Montgomery ladder back  to crypto_x25519()

EdDSA stopped using the ladder, making it a separate function no longer
makes sense.

Specialised adding code for EdDSA signatures

- Saved one multiplication by assuming Z=1
- Hoisted wipes out of loops
- Removed wipes for variable time additions

This made both signatures and verification a bit faster.  (Note: current
signature verification speed is only 23% slower than key exchange.  I
didn't think it could be that fast.)

Full pre-computed table for EdDSA signatures

The main gain for now comes from reducing the amount of constant time
lookup.  We could reduce the table's size even further, *or* save a few
multiplications.

I'm currently a little suspicious of the way I generated the table. If
it passes the tests, it shouldn't have any error, but it still requires
some checking.

ge_double() is now more readable

It's also become easier to hoist buffers out of loops

Cleaner point addition for EdDSA

Point addition used to use 8 intermediate variables.  That's 6 more than
what was needed.  Removing them made wiping faster, and shrank the stack
by 240 bytes. (Stack size may matter in embedded systems.)