Add Poly1305 implementation #15519

This adds a currently unused Poly1305 implementation including test vectors from RFC7539.

Required for BIP151 (and related to #15512).

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #15649 (Add ChaCha20Poly1305@Bitcoin AEAD by jonasschnelli)
• #14047 (Add HKDF_HMAC256_L32 and method to negate a private key by jonasschnelli)
• #14032 (Add p2p layer encryption with ECDH/ChaCha20Poly1305 by jonasschnelli)
• #10102 ([experimental] Multiprocess bitcoin by ryanofsky)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

Intentional unsigned wraparound is triggered in crypto/poly1305.cpp (on at least L122 and L124). That is fine but should be documented in test/sanitizer_suppressions/ubsan to make the -fsanitize=integer Travis job happy :-)

Benchmark done on a aarch64 (RK3328 Quad-Core ARM Cortex A53 64-Bit)

CHACHA20_1MB, 5, 340, 13.3704, 0.00772624, 0.00806671, 0.00775259
CHACHA20_256BYTES, 5, 250000, 2.41802, 1.92206e-06, 1.95887e-06, 1.92964e-06
CHACHA20_64BYTES, 5, 500000, 1.28993, 5.07247e-07, 5.26875e-07, 5.14802e-07
HASH_1MB, 5, 340, 22.5945, 0.0128931, 0.0135617, 0.0132931
HASH_256BYTES, 5, 250000, 6.84513, 5.43544e-06, 5.54961e-06, 5.45136e-06
HASH_64BYTES, 5, 500000, 7.47419, 2.94502e-06, 3.04259e-06, 2.99531e-06
POLY1305_1MB, 5, 340, 10.2145, 0.00591661, 0.00609435, 0.00601109
POLY1305_256BYTES, 5, 250000, 1.88446, 1.48188e-06, 1.52889e-06, 1.52119e-06
POLY1305_64BYTES, 5, 500000, 1.08101, 4.25452e-07, 4.43012e-07, 4.29685e-07

This may be interpreted as a possible performance increase in processing packets with ChaCha2Poly1305 versus Hash256 as checksum (especially small messages).

Benchmark on a Intel i7 with SSE4 i7-8700 CPU @ 3.20GHz)

CHACHA20_1MB, 5, 340, 2.42871, 0.00142497, 0.0014349, 0.00142748
CHACHA20_256BYTES, 5, 250000, 0.443971, 3.53501e-07, 3.56836e-07, 3.54826e-07
CHACHA20_64BYTES, 5, 500000, 0.235031, 9.37462e-08, 9.42958e-08, 9.39654e-08
HASH_1MB, 5, 340, 3.98642, 0.00233798, 0.00234913, 0.00234636
HASH_256BYTES, 5, 250000, 1.12901, 8.97008e-07, 9.10387e-07, 9.03194e-07
HASH_64BYTES, 5, 500000, 1.18437, 4.70553e-07, 4.77644e-07, 4.72031e-07
POLY1305_1MB, 5, 340, 0.974462, 0.000562465, 0.000591879, 0.000565398
POLY1305_256BYTES, 5, 250000, 0.187587, 1.48138e-07, 1.51869e-07, 1.49319e-07
POLY1305_64BYTES, 5, 500000, 0.117305, 4.6148e-08, 4.74575e-08, 4.69618e-08

Intentional unsigned wraparound is triggered in crypto/poly1305.cpp

Right—since when is unsigned integer wraparound a problem? I thought there was only undefined behavior in signed wraparound.

Yes, unsigned overflow is well-defined. Is -fsanitize=undefined enabling that by default? I don't see anything in our configuration turning it on specifically.

@laanwj Unsigned integer wraparound is perfectly well-defined. Intentional unsigned integer wraparound is not problematic at all. Is anyone claiming otherwise? :-)

@practicalswift Do you have any idea why the sanitizer catches it in that case?

@sipa Yes, it is -fsanitize=integer catching it (or more specifically -fsanitize=unsigned-integer-overflow which is enabled as part of -fsanitize=integer):

-fsanitize=unsigned-integer-overflow: Unsigned integer overflow, where the result of an unsigned integer computation cannot be represented in its type. Unlike signed integer overflow, this is not undefined behavior, but it is often unintentional.

An argument to keep it enabled in Travis it that it makes people aware of unintentional unsigned integer wraparound (a common source of bugs, but obviously not UB).

Intentional unsigned integer wraparounds (such as in hashing code) can simply be documented as such by adding a line to test/sanitizer_suppressions/ubsan.

utACK e3d8d0f7b3102ec1e6b787feaac7fe98dd5a7d7a, compared with the original implementation and compared the test vectors with the RFC.

This is giving me new compile warnings (clang 8):

In file included from /.../bitcoin/src/test/crypto_tests.cpp:7:0:
/.../bitcoin/src/crypto/poly1305.h:19:66: warning: ‘__bounded__’ attribute directive ignored [-Wattributes]
     __attribute__((__bounded__(__minbytes__, 4, POLY1305_KEYLEN)));
                                                                  ^
/.../bitcoin/src/crypto/poly1305.h:19:66: warning: ‘__bounded__’ attribute directive ignored [-Wattributes]
/.../bitcoin/src/crypto/poly1305.h:19:66: warning: ‘__bounded__’ attribute directive ignored [-Wattributes]

Removed the bounded attribute (lets don't bother with activate them).

thanks, utACK e9d5e975612e828ec44f9247b4c5c08f0268d360