Make poly1305 support incremental computation + modernize #27993

pull sipa wants to merge 4 commits into bitcoin:master from sipa:202306_poly1305 changing 8 files +392 −154
  1. sipa commented at 4:01 pm on June 28, 2023: member

    Our current Poly1305 code (src/crypto/poly1305.*) only supports computing the entire tag in one go (the poly1305_auth function takes a key and message, and outputs the tag). However, the RFC8439 authenticated encryption (as used in BIP324, see #27634) scheme makes use of Poly1305 in a way where the message consists of 3 different pieces:

    • The additionally authenticated data (AAD), padded to 16 bytes.
    • The ciphertext, padded to 16 bytes.
    • The length of the AAD and the length of the ciphertext, together another 16 bytes.

    Implementing RFC8439 using the existing poly1305_auth function requires creating a temporary copy with all these pieces of data concatenated just for the purpose of computing the tag (the approach used in #25361).

    This PR replaces the poly1305 code with new code from https://github.com/floodyberry/poly1305-donna (with minor adjustments to make it match our coding style and use our utility functions, documented in the commit) which supports incremental operation, and then adds a C++ wrapper interface using std::byte Spans around it, and adds tests that incremental and all-at-once computation match.

  2. DrahtBot commented at 4:01 pm on June 28, 2023: contributor

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

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    ACK theStack, stratospher, achow101

    If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

    Conflicts

    No conflicts as of last run.

  3. sipa force-pushed on Jun 29, 2023
  4. sipa force-pushed on Jun 30, 2023
  5. sipa force-pushed on Jul 10, 2023
  6. sipa force-pushed on Jul 10, 2023
  7. sipa force-pushed on Jul 10, 2023
  8. sipa force-pushed on Jul 11, 2023
  9. in src/crypto/poly1305.cpp:65 in 4abc8465f7 outdated 
    182+    h1 = st->h[1];
183+    h2 = st->h[2];
184+    h3 = st->h[3];
185+    h4 = st->h[4];
186+
187+    while (bytes >= 16) {
    theStack commented at 1:43 pm on July 11, 2023:

    magic number elimination nit:

    0    while (bytes >= POLY1305_BLOCK_SIZE) {
    sipa commented at 2:42 pm on July 11, 2023:
    Fixed. At some point I decided to eliminate the constant entirely, but then went back to trying to match the original implementation as much as possible.
  10. theStack commented at 2:02 pm on July 11, 2023: contributor

    Concept ACK

    Verified that the poly1305 implementation introduced in 4abc8465f74e390e0f887a5a0be9550d3d179791 matches poly1305-donna (used https://github.com/openbsd/src/blob/master/sys/crypto/poly1305.c as a reference, which is again based on Andrew Moon’s implementation with minor adaptions). Still planning to verify the test vectors with another implementation, likely PyCryptodome.

  11. sipa force-pushed on Jul 11, 2023
  12. crypto: switch poly1305 to incremental implementation 
    This code is taken from poly1305-donna-32.h, poly1305-donna.h, poly1305-donna.c
from https://github.com/floodyberry/poly1305-donna, commit
e6ad6e091d30d7f4ec2d4f978be1fcfcbce72781, with the following modifications:

* Coding style (braces around one-line indented if/for loops).
* Rename unsigned long (long) to uint32_t and uint64_t.
* Rename poly1305_block_size to POLY1305_BLOCK_SIZE.
* Adding noexcept to functions.
* Merging poly1305_state_internal_t and poly1305_context types.
* Merging code from multiple files.
* Place all imported code in the poly1305_donna namespace.
    50269b391f
  13. sipa force-pushed on Jul 12, 2023
  14. in src/crypto/poly1305.h:54 in 7601a60cdd outdated 
    49+
50+    /** Construct a Poly1305 object with a given 32-byte key. */
51+    Poly1305(Span<const std::byte> key) noexcept
52+    {
53+        assert(key.size() == KEYLEN);
54+        poly1305_donna::poly1305_init(&m_ctx, reinterpret_cast<const unsigned char*>(key.data()));
    achow101 commented at 10:32 pm on July 12, 2023:

    In 7601a60cddc4405f58f71879f996322329509dfe “crypto: add Poly1305 class with std::byte Span interface”

    Use UCharCast cast here (and below)?

    sipa commented at 2:44 am on July 13, 2023:
    Done.
  15. in src/test/crypto_tests.cpp:781 in 40de8ce39a outdated 
    777+                 "eea6a7251c1e72916d11c2cb214d3c252539121d8e234e652d651fa4c8cff880",
778+                 "f3ffc7703f9400e52a7dfb4b3d3305d9");
779+    {
780+        // mac of the macs of messages of length 0 to 256, where the key and messages have all
781+        // their values set to the length.
782+        auto total_key = ParseHex("01020304050607fffefdfcfbfaf9ffffffffffffffffffffffffffff00000000");
    theStack commented at 11:14 pm on July 12, 2023:

    could let ParseHex return a std::vector<std::byte> here and below (for the final_tag comparison) to avoid MakeByteSpan calls later

    0        auto total_key = ParseHex<std::byte>("01020304050607fffefdfcfbfaf9ffffffffffffffffffffffffffff00000000");

    (maybe at some point in the future we can change ParseHex to return a vector of std::byte rather than unsigned char by default)

    sipa commented at 2:44 am on July 13, 2023:
    Oh nice, I wasn’t aware of ParseHex<std::byte>. Done.
  16. in src/test/crypto_tests.cpp:785 in 40de8ce39a outdated 
    781+        // their values set to the length.
782+        auto total_key = ParseHex("01020304050607fffefdfcfbfaf9ffffffffffffffffffffffffffff00000000");
783+        Poly1305 total_ctx(MakeByteSpan(total_key));
784+        for (unsigned i = 0; i < 256; ++i) {
785+            std::vector<unsigned char> key(32, (unsigned char)i);
786+            std::vector<unsigned char> msg(i, (unsigned char)i);
    theStack commented at 11:21 pm on July 12, 2023: 
    0            std::vector<std::byte> key(32, std::byte{(unsigned char)i});
1            std::vector<std::byte> msg(i, std::byte{(unsigned char)i});

    With the same idea as above. I think all Make{Writable}ByteSpan calls can be avoided in this commit, which improves readability IMHO quite a bit.

    sipa commented at 2:44 am on July 13, 2023:
    Done.
  17. theStack commented at 11:29 pm on July 12, 2023: contributor

    LGTM overall. Verified the introduced test vectors (40de8ce39a65cb37a74bebcbf7b34ed8e70b7096) with the pyca/cryptography library, which uses OpenSSL in the background (tried with PyCryptodome first, but that didn’t allow use of raw Poly1305 without a cipher algorithm). As expected, everything passes with this alternative implementation as well.

     0#!/usr/bin/env python3
 1from cryptography.hazmat.primitives.poly1305 import Poly1305
 2
 3def test_poly1305(msg, key, tag):
 4    p = Poly1305(bytes.fromhex(key))
 5    p.update(bytes.fromhex(msg))
 6    assert p.finalize() == bytes.fromhex(tag)
 7
 8test_poly1305("8e993b9f48681273c29650ba32fc76ce48332ea7164d96a4476fb8c531a1186a" +
 9              "c0dfc17c98dce87b4da7f011ec48c97271d2c20f9b928fe2270d6fb863d51738" +
10              "b48eeee314a7cc8ab932164548e526ae90224368517acfeabd6bb3732bc0e9da" +
11              "99832b61ca01b6de56244a9e88d5f9b37973f622a43d14a6599b1f654cb45a74" +
12              "e355a5",
13              "eea6a7251c1e72916d11c2cb214d3c252539121d8e234e652d651fa4c8cff880",
14              "f3ffc7703f9400e52a7dfb4b3d3305d9")
15
16total_ctx = Poly1305(bytes.fromhex("01020304050607fffefdfcfbfaf9ffffffffffffffffffffffffffff00000000"))
17for i in range(256):
18    key = bytes([i]*32)
19    msg = bytes([i]*i)
20    p = Poly1305(key)
21    p.update(msg)
22    tag = p.finalize()
23    total_ctx.update(tag)
24assert total_ctx.finalize() == bytes.fromhex("64afe2e8d6ad7bbdd287f97c44623d39")
25
26test_poly1305("000000000000000000000094000000000000b07c4300000000002c002600d500" +
27              "00000000000000000000000000bc58000000000000000000c9000000dd000000" +
28              "00000000000000d34c000000000000000000000000f9009100000000000000c2" +
29              "4b0000e900000000000000000000000000000000000e00000027000074000000" +
30              "0000000003000000000000f1000000000000dce2000000000000003900000000" +
31              "0000000000000000000000000000000000000000000000520000000000000000" +
32              "000000000000000000000000009500000000000000000000000000cf00826700" +
33              "000000a900000000000000000000000000000000000000000079000000000000" +
34              "0000de0000004c000000000033000000000000000000000000002800aa000000" +
35              "00003300860000e000000000",
36              "6e543496db3cf677592989891ab021f58390feb84fb419fbc7bb516a60bfa302",
37              "7ea80968354d40d9d790b45310caf7f3")
38test_poly1305("0000005900000000c40000002f00000000000000000000000000000029690000" +
39              "0000e8000037000000000000000000000000000b000000000000000000000000" +
40              "000000000000000000000000001800006e0000000000a4000000000000000000" +
41              "00000000000000004d00000000000000b0000000000000000000005a00000000" +
42              "0000000000b7c300000000000000540000000000000000000000000a00000000" +
43              "00005b0000000000000000000000000000000000002d00e70000000000000000" +
44              "000000000000003400006800d700000000000000000000360000000000000000" +
45              "00eb000000000000000000000000000000000000000000000000000028000000" +
46              "37000000000000000000000000000000000000000000000000000000008f0000" +
47              "000000000000000000000000",
48              "f0b659a4f3143d8a1e1dacb9a409fe7e7cd501dfb58b16a2623046c5d337922a",
49              "0e410fa9d7a40ac582e77546be9a72bb")

    Left some nits for removing the need for Make{Writable}ByteSpan calls. I think they can also be applied to the TestPoly1305 function.

  18. crypto: add Poly1305 class with std::byte Span interface 40e6c5b9fc
  19. sipa force-pushed on Jul 13, 2023
  20. tests: add more Poly1305 test vectors 8871f7d1ae
  21. Switch all callers from poly1305_auth to Poly1305 class 
    This also removes the old poly1305_auth interface, as it no longer serves any
function. The new Poly1305 class based interface is more modern and safe.
    4e5c933f6a
  22. sipa force-pushed on Jul 13, 2023
  23. in src/test/crypto_tests.cpp:792 in 4e5c933f6a 
    787+            Poly1305{key}.Update(msg).Finalize(tag);
788+            total_ctx.Update(tag);
789+        }
790+        std::vector<std::byte> total_tag(Poly1305::TAGLEN);
791+        total_ctx.Finalize(total_tag);
792+        BOOST_CHECK(total_tag == ParseHex<std::byte>("64afe2e8d6ad7bbdd287f97c44623d39"));
    maflcko commented at 5:57 am on July 13, 2023: 
    0        BOOST_CHECK_EQUAL(HexStr(total_tag), "64afe2e8d6ad7bbdd287f97c44623d39");

    style nit, if you retouch.

    sipa commented at 8:56 pm on July 18, 2023:
    Done in #28100.
  24. theStack approved
  25. theStack commented at 1:20 pm on July 13, 2023: contributor
    ACK 4e5c933f6a40c07d1c68115f7979b89a5b2ba580
  26. sipa commented at 1:22 pm on July 13, 2023: member
    @MarcoFalke You may be interested in the Span<std::byte> usage here.
  27. in src/test/fuzz/crypto_poly1305.cpp:40 in 4e5c933f6a 
    38+    std::vector<std::byte> total_input;
39+
40+    // Process input in pieces.
41+    LIMITED_WHILE(provider.remaining_bytes(), 100) {
42+        auto in = provider.ConsumeRandomLengthString();
43+        poly_split.Update(MakeByteSpan(in));
    maflcko commented at 1:13 pm on July 17, 2023:
    nit: If you want to avoid the cast here, you could make ConsumeRandomLengthByteVector a template on B and then directly consume into a std::vector<std::byte> and use that.
    sipa commented at 8:56 pm on July 18, 2023:
    Done in #28100.
  28. in src/test/crypto_tests.cpp:785 in 4e5c933f6a 
    780+        // their values set to the length.
781+        auto total_key = ParseHex<std::byte>("01020304050607fffefdfcfbfaf9ffffffffffffffffffffffffffff00000000");
782+        Poly1305 total_ctx(total_key);
783+        for (unsigned i = 0; i < 256; ++i) {
784+            std::vector<std::byte> key(32, std::byte{(uint8_t)i});
785+            std::vector<std::byte> msg(i, std::byte{(uint8_t)i});
    maflcko commented at 1:14 pm on July 17, 2023: 
    0            std::vector<std::byte> msg(i, std::byte{uint8_t(i)});

    (nit, just personal preference)

    sipa commented at 8:56 pm on July 18, 2023:
    Done in #28100.
  29. maflcko commented at 1:16 pm on July 17, 2023: member
    Sure, happy to leave comments, but I think it may be better to fix them in a follow-up, unless you really want to here.
  30. stratospher commented at 5:18 pm on July 17, 2023: contributor

    tested ACK 4e5c933.

    cross checked that this is consistent with poly1305-donna implementation. benchmarks look better compared to previous poly1305_auth code too. (also found this blogpost which explains poly1305’s design interesting!)

    noticed this tiny difference in poly1305-donna’s vs RFC 8439 r - though it might also be some trick for later computation i guess.

    • r before clamping: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8
    • Clamped r as a number: 806d5400e52447c036d555408bed685
    • chopping r into 5 pieces for r[0], r[1], r[2], r[3], r[4]
    • can be written as: 806d5, 400e524, 47c036, d555408, bed685
    • r in floodyberry’s : 806d5, 1003949, 47c036, 3555502, bed685
    • where 400e524 = 1003949 + “two zero bits” and d555408 = 3555502 + “two zero bits”
  31. sipa commented at 5:31 pm on July 17, 2023: member
    @stratospher There are two approaches for poly1305 implementations out there; one where the key (and the accumulated hash value) are represented using 32-bit limbs, and one where it’s represented using 26-bit limbs (so in one r = sum(r[i] * 2^(32*i)) while in the other r = sum(r[i] * 2^(26*i))). Poly1305 is designed to make 32-bit limb designs efficient (the masking out of the bits guarantee some overflows are avoided, as explained in the blogpost you link). However, in all my benchmarks the 26-bit limb design (as is used in the poly1305-donna code) is faster. That’s kind of a pity, because it means the masking is pointless (and actually reduces the security of the scheme by a few bits), yet necessary to remain compatible with the poly1305 spec.
  32. sipa commented at 7:57 pm on July 17, 2023: member
    @MarcoFalke Thanks for the comments; I think I’m going to create a separate PR with some further code refactoring related to this as well, outside of the critical path of #25361.
  33. achow101 commented at 10:20 pm on July 17, 2023: member

    ACK 4e5c933f6a40c07d1c68115f7979b89a5b2ba580

    Verified that this was consistent with poly1305-donna.

  34. achow101 merged this on Jul 17, 2023
  35. achow101 closed this on Jul 17, 2023
  36. in src/test/crypto_tests.cpp:206 in 4e5c933f6a 
    207+                poly1305.Update(data.first(now));
208+                data = data.subspan(now);
209+            }
210+            tagres.assign(Poly1305::TAGLEN, std::byte{});
211+            poly1305.Update(data).Finalize(tagres);
212+            BOOST_CHECK(tag == tagres);
    maflcko commented at 9:12 am on July 18, 2023:
    Same nit here: BOOST_CHECK_EQUAL(hextag, HexStr(tagres))
    sipa commented at 8:56 pm on July 18, 2023:
    Done in #28100.
  37. sidhujag referenced this in commit 177a9921d0 on Jul 19, 2023
  38. fanquake referenced this in commit b2ec0326fd on Aug 10, 2023
  39. fanquake referenced this in commit 5eb669024f on Aug 18, 2023
  40. Frank-GER referenced this in commit e6242939ee on Sep 8, 2023
  41. kwvg referenced this in commit 536390d488 on Feb 19, 2024
  42. kwvg referenced this in commit a147f2dac3 on Feb 20, 2024
  43. kwvg referenced this in commit 5085b535e7 on Feb 23, 2024
  44. kwvg referenced this in commit 98ecb56aaf on Feb 24, 2024
  45. kwvg referenced this in commit b8bdd301b4 on Feb 27, 2024
  46. kwvg referenced this in commit 74d8bd6c6c on Feb 29, 2024
  47. kwvg referenced this in commit ff542199bc on Mar 5, 2024
  48. PastaPastaPasta referenced this in commit e84e3d9c85 on Mar 6, 2024
  49. bitcoin locked this on Jul 17, 2024


sipa DrahtBot theStack achow101 maflcko stratospher

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-21 12:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me