Add support for RFC8439 variant of ChaCha20 #27985

pull sipa wants to merge 3 commits into bitcoin:master from sipa:202306_chacha20_rfc8439 changing 7 files +174 −71
  1. sipa commented at 9:18 pm on June 27, 2023: member

    Based on and replaces part of #25361, part of the BIP324 project (#27634). See also #19225 for background.

    There are two variants of ChaCha20 in use. The currently implemented one uses a 64-bit nonce and a 64-bit block counter, while the one used in RFC8439 (and thus BIP324) uses a 96-bit nonce and 32-bit block counter. This PR changes the logic to use the 96-bit nonce variant, though in a way that’s compatible with >256 GiB output (by automatically incrementing the first 32-bit part of the nonce when the block counter overflows).

    For those who reviewed the original PR, the biggest change is here that the 96-bit nonce is passed as a Nonce96 type (pair of 32-bit + 64-bit integer) rather than a 12-byte array.

  2. DrahtBot commented at 9:18 pm on June 27, 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, achow101

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

    Conflicts

    Reviewers, this pull request conflicts with the following ones:

    • #28008 (BIP324 ciphersuite by sipa)

    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.

  3. in src/crypto/chacha20.h:34 in 53c1b7adfb outdated 
    28@@ -29,6 +29,15 @@ class ChaCha20Aligned
29     /** set the 64-bit nonce. */
30     void SetIV(uint64_t iv);
31 
32+    /** Set the 96-bit nonce and 32-bit block counter as described by RFC8439.
33+     *
34+     * In this mode, only 2^38 - 64 bytes can be encrypted (minus 64*block_counter).
    stratospher commented at 5:27 am on June 28, 2023:

    53c1b7a: nit: since starting with block_counter = 1 is a detail of RFC8439’s AEAD and not RFC8439’s ChaCha20, would it be better to just mention the general form?

    0     * In this mode, only 2^38 - 64*block_counter bytes can be encrypted.
    sipa commented at 2:26 pm on June 29, 2023:
    Rephrased; indeed, the 2^38 - 64 number only applies to the AEAD and not to ChaCha20 (which supports 2^38).
  4. Sjors commented at 12:17 pm on June 28, 2023: member
    #19225 :-)
  5. sipa commented at 12:44 pm on June 28, 2023: member
    @Sjors Thanks, I had forgotten about that. Added a reference.
  6. in src/test/crypto_tests.cpp:612 in dcaf03969a outdated 
    606@@ -580,6 +607,140 @@ BOOST_AUTO_TEST_CASE(chacha20_testvector)
607                  "224f51f3401bd9e12fde276fb8631ded8c131f823d2c06e27e4fcaec9ef3cf788a3b0aa372600a92b57974cded2b9334794cb"
608                  "a40c63e34cdea212c4cf07d41b769a6749f3f630f4122cafe28ec4dc47e26d4346d70b98c73f3e9c53ac40c5945398b6eda1a"
609                  "832c89c167eacd901d7e2bf363");
610+
611+    // Test vectors from https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#section-7
612+    TestChaCha20("", "0000000000000000000000000000000000000000000000000000000000000000", 0, 0,
    stratospher commented at 7:49 am on June 29, 2023:
    2c0c749: this test vector is repeated in this line.
    sipa commented at 2:26 pm on June 29, 2023:
    I’ve added a comment about it being repeated.
  7. sipa force-pushed on Jun 29, 2023
  8. sipa force-pushed on Jun 29, 2023
  9. sipa commented at 2:30 pm on June 29, 2023: member

    Made some changes:

    • Addressed the comments above.
    • Renamed nonce_low and nonce_high to nonce_prefix and nonce respectively; there isn’t any inherent ordering of low/high between them, but RFC8439 refers to the first one as “32-bit fixed-common part” in one place.
    • Removed the old RFC8439 test vectors (as they were essentially created by translating test vectors for 96/32 nonces to the equivalent 64/64 one). The new RFC8439 test vectors actually match the document.
  10. sipa force-pushed on Jun 30, 2023
  11. sipa commented at 6:08 pm on June 30, 2023: member
    I’ve encapsulated the 96-bit nonce into a using Nonce96 = std::pair<uint32_t, uint64_t>, which makes the interfaces a bit cleaner.
  12. in src/test/crypto_tests.cpp:202 in dd77a27426 outdated 
    197+        c20.Keystream(keystream.data(), expected_keystream.size());
198+        BOOST_CHECK_EQUAL(HexStr(keystream), hex_expected_keystream);
199+    }
200+
201+    if (!hex_input.empty()) {
202+        assert(hex_input.size() == hex_expected_output.size());
    theStack commented at 11:43 pm on July 5, 2023:
    tiny nit (probably only worth changing if you have to retouch): could check this assert unconditionally, to not allow test cases where hex_input is empty but hex_expected_output is not
  13. theStack commented at 11:49 pm on July 5, 2023: contributor
    Concept ACK
  14. theStack approved
  15. theStack commented at 11:22 pm on July 6, 2023: contributor

    Code-review ACK 200e1a292b277d6c32dbd6081d38b715cbc079cb

    Verified that the implementation matches the RFC8439 specification (https://datatracker.ietf.org/doc/html/rfc8439#section-2.3) and checked that the test vectors match the ones from the linked sources (https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#section-7 and https://datatracker.ietf.org/doc/html/rfc8439#page-30).

    Note for other reviewers (that get as easily confused as me): we don’t store the constants in the input array, so our indices are 4 less, e.g. input[8] in our code corresponds to Word 12 in the RFC.

  16. achow101 commented at 11:35 pm on July 6, 2023: member
    Is the current ChaCha20 implementation used for anything that needs backwards compatibility?
  17. sipa commented at 0:26 am on July 7, 2023: member

    @achow101 Good question!

    It’s used by FastRandomContext and MuHash. I haven’t investigated whether there are any uses of FastRandomContext that could generate more than 256 GiB of data, but even if there are there it’s possible to at least use the new seeking style (the current implementation, when using the 96/32 split, when the block counter overflows, just increments the nonce, which is exactly what we’d want for an RNG anyway).

    So no - I think all existing uses could be converted to use the 96/32 split, if the overflow behavior is kept. I’m happy to include that in this PR if reviewers prefer that, or I could leave it for a follow-up.

  18. achow101 commented at 7:05 pm on July 7, 2023: member
    Assuming it doesn’t break a whole lot of tests, I would prefer to change it always use the new version as it removes the need to check that everything is using the right variant.
  19. crypto: Implement RFC8439-compatible variant of ChaCha20 
    There are two variants of ChaCha20 in use. The original one uses a 64-bit
nonce and a 64-bit block counter, while the one used in RFC8439 uses a
96-bit nonce and 32-bit block counter. This commit changes the interface
to use the 96/32 split (but automatically incrementing the first 32-bit
part of the nonce when the 32-bit block counter overflows, so to retain
compatibility with >256 GiB output).

Simultaneously, also merge the SetIV and Seek64 functions, as we almost
always call both anyway.

Co-authored-by: dhruv <856960+dhruv@users.noreply.github.com>
    511a8d406e
  20. tests: improve ChaCha20 unit tests 7f2a985147
  21. sipa force-pushed on Jul 7, 2023
  22. sipa commented at 9:52 pm on July 7, 2023: member
    @achow101 Done. I think this is quite a bit simpler too, thanks. @theStack This was a pretty big change so it invalidates your review (but as an upside also removed the code that you commented about).
  23. achow101 commented at 0:03 am on July 8, 2023: member

    ACK 7f2a985147ef541123c65d5db1c3fc3e533fd4ce

    This PR fundamentally doesn’t change our implementation of ChaCha20, just its interface so that it matches RFC8439. It otherwise behaves in the same way as previously. The new test vectors match those of the RFC.

  24. DrahtBot requested review from theStack on Jul 8, 2023
  25. theStack commented at 10:38 am on July 9, 2023: contributor

    Nice and indeed much simpler now, the actual diff is smaller than I expected. Will re-review tomorrow.

    Meanwhile, I thought it would be nice to have a test case triggering the 32-bit block counter overflow to check for >256 GiB output compatibility and wrote one (test data is created with PyCryptodome, see commit message), maybe it’s worthwhile to include it here: https://github.com/theStack/bitcoin/commit/61b41ad16e35306485a1db508d624d3ddab0ca0a (the next commit https://github.com/theStack/bitcoin/commit/ff289308bf7af8184cc0ecaafe6f5e1842b8f17b goes one step further and checks if the overflow really happened by inspecting the input state before/after test case execution, but not sure if it’s worth it to pollute the ChaCha20 class with test-only methods).

  26. DrahtBot requested review from theStack on Jul 9, 2023
  27. test: add ChaCha20 test triggering 32-bit block counter overflow 
    Verify that our ChaCha20 implementation using the 96/32 split interface
is compatible with >256 GiB outputs by triggering a 32-bit block counter
overflow and checking that the keystream matches one created with an
alternative implementation using a 64/64 split interface with the
corresponding input data. The test case data was generated with the
following Python script using the PyCryptodome library (version 3.15.0):

----------------------------------------------------------------------------------------------
from Crypto.Cipher import ChaCha20
key = bytes(list(range(32))); nonce = 0xdeadbeef12345678; pos = 2**32 - 1
c = ChaCha20.new(key=key, nonce=nonce.to_bytes(8, 'little'))
c.seek(pos * 64); stream = c.encrypt(bytes([0])*128)
print(f"Key: {key.hex()}\nNonce: {hex(nonce)}\nPos: {hex(pos)}\nStream: {stream.hex()}")
----------------------------------------------------------------------------------------------
    0bf87476f5
  28. sipa commented at 2:10 pm on July 9, 2023: member

    @theStack Cherrypicked the first commit. I don’t think the second one adds that much, as presumably there is no way the output can be correct if the internal state is wrong.

    FWIW, the crypto_diff_fuzz_chacha20 fuzz test also tests the overflowing behavior (but still good to have a unit test for it too).

  29. theStack approved
  30. theStack commented at 4:10 pm on July 10, 2023: contributor
    Code-review ACK 0bf87476f55dceb106563156c7c8d6bfb8162e29
  31. DrahtBot requested review from achow101 on Jul 10, 2023
  32. achow101 commented at 7:02 pm on July 11, 2023: member
    ACK 0bf87476f55dceb106563156c7c8d6bfb8162e29
  33. DrahtBot removed review request from achow101 on Jul 11, 2023
  34. achow101 merged this on Jul 12, 2023
  35. achow101 closed this on Jul 12, 2023
  36. sidhujag referenced this in commit 4adf185bcf on Jul 12, 2023
  37. fanquake referenced this in commit b2ec0326fd on Aug 10, 2023
  38. kwvg referenced this in commit 3b124e79a0 on Feb 19, 2024
  39. kwvg referenced this in commit 63a430ecce on Feb 20, 2024
  40. kwvg referenced this in commit 3510f95395 on Feb 23, 2024
  41. kwvg referenced this in commit ce37d4ad09 on Feb 24, 2024
  42. kwvg referenced this in commit 6100bcdac8 on Feb 27, 2024
  43. kwvg referenced this in commit a3e7ceb5bf on Feb 29, 2024
  44. kwvg referenced this in commit d7482eb8a6 on Mar 5, 2024
  45. PastaPastaPasta referenced this in commit e84e3d9c85 on Mar 6, 2024
  46. bitcoin locked this on Jul 11, 2024


sipa DrahtBot stratospher Sjors theStack achow101

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-12-19 00:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me