Add Poly1305 implementation

jonasschnelli commented at 8:56 pm on March 3, 2019: contributor

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

Required for BIP151 (and related to #15512).

jonasschnelli added the label Utils/log/libs on Mar 3, 2019

jonasschnelli force-pushed on Mar 3, 2019

DrahtBot commented at 10:44 pm on March 3, 2019: member

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

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.

jonasschnelli force-pushed on Mar 4, 2019

practicalswift commented at 9:20 pm on March 4, 2019: contributor

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 :-)

jonasschnelli commented at 2:43 pm on March 5, 2019: contributor

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

0CHACHA20_1MB, 5, 340, 13.3704, 0.00772624, 0.00806671, 0.00775259
1CHACHA20_256BYTES, 5, 250000, 2.41802, 1.92206e-06, 1.95887e-06, 1.92964e-06
2CHACHA20_64BYTES, 5, 500000, 1.28993, 5.07247e-07, 5.26875e-07, 5.14802e-07
3HASH_1MB, 5, 340, 22.5945, 0.0128931, 0.0135617, 0.0132931
4HASH_256BYTES, 5, 250000, 6.84513, 5.43544e-06, 5.54961e-06, 5.45136e-06
5HASH_64BYTES, 5, 500000, 7.47419, 2.94502e-06, 3.04259e-06, 2.99531e-06
6POLY1305_1MB, 5, 340, 10.2145, 0.00591661, 0.00609435, 0.00601109
7POLY1305_256BYTES, 5, 250000, 1.88446, 1.48188e-06, 1.52889e-06, 1.52119e-06
8POLY1305_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).

jonasschnelli commented at 2:44 pm on March 5, 2019: contributor

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

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

laanwj commented at 6:15 pm on March 7, 2019: member

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.

sipa commented at 6:31 pm on March 7, 2019: member

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.

jonasschnelli force-pushed on Mar 7, 2019

practicalswift commented at 8:10 pm on March 7, 2019: contributor

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

sipa commented at 8:12 pm on March 7, 2019: member

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

practicalswift commented at 8:22 pm on March 7, 2019: contributor

@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.

in src/crypto/poly1305.cpp:6 in e3d8d0f7b3 outdated

0@@ -0,0 +1,141 @@
1+// Copyright (c) 2019 The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+// Based on the public domain implementation by Andrew Moon
6+// poly1305-donna-unrolled.c from https://github.com/floodyberry/poly1305-donna

sipa commented at 5:29 pm on March 25, 2019:

I can’t really find the code this is based on anymore (perhaps it was moved?). It seems identical to code here though: https://github.com/jhcloos/openssh-chacha-poly1305/blob/master/poly1305-donna-unrolled.c ?

jonasschnelli commented at 5:32 pm on March 25, 2019:

The code is taken from the OpenSSH project (correct link is https://github.com/openssh/openssh-portable/blob/90e51d672711c19a36573be1785caf35019ae7a8/poly1305.c). I kept the reference (see https://github.com/openssh/openssh-portable/blob/90e51d672711c19a36573be1785caf35019ae7a8/poly1305.c#L3).

sipa commented at 11:11 pm on March 25, 2019: member

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

laanwj commented at 10:11 am on March 26, 2019: member

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

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

Add Poly1305 implementation 03be7f48fa

Add Poly1305 bench b34bf302f2

Poly1305: tolerate the intentional unsigned wraparound in poly1305.cpp e9d5e97561

jonasschnelli commented at 5:14 pm on March 26, 2019: contributor

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

jonasschnelli force-pushed on Mar 26, 2019

laanwj commented at 10:53 am on March 27, 2019: member

thanks, utACK e9d5e975612e828ec44f9247b4c5c08f0268d360

laanwj merged this on Mar 27, 2019

laanwj closed this on Mar 27, 2019

laanwj referenced this in commit 208406038c on Mar 27, 2019

PastaPastaPasta referenced this in commit 0766c55cb7 on Jun 19, 2019

laanwj referenced this in commit 28d1353f48 on Jul 11, 2019

sidhujag referenced this in commit aae6de0fc9 on Jul 11, 2019

PastaPastaPasta referenced this in commit bf737f4b91 on Jul 18, 2019

PastaPastaPasta referenced this in commit 1bf6613178 on Jul 18, 2019

PastaPastaPasta referenced this in commit 4493671b87 on Jul 23, 2019

PastaPastaPasta referenced this in commit 0840ce3a92 on Jul 23, 2019

PastaPastaPasta referenced this in commit e5f34cab48 on Aug 6, 2019

PastaPastaPasta referenced this in commit 8214c765d4 on Aug 6, 2019

barrystyle referenced this in commit 1ffc186995 on Jan 22, 2020

barrystyle referenced this in commit 7ebc414298 on Jan 22, 2020

jasonbcox referenced this in commit 4bd1daa5b6 on Sep 21, 2020

dhruv added this to the "Done" column in a project

DrahtBot locked this on Dec 16, 2021

Add Poly1305 implementation #15519

Conflicts