BIP324 ciphersuite

sipa commented at 10:00 pm on June 29, 2023: member

Depends on #27985 and #27993, based on and partially replaces #25361, part of #27634. Draft while dependencies are not merged.

This adds implementations of:

The ChaCha20Poly1305 AEAD from RFC8439 section 2.8, including test vectors.
The FSChaCha20 stream cipher as specified in BIP324, a rekeying wrapper around ChaCha20.
The FSChaCha20Poly1305 AEAD as specified in BIP324, a rekeying wrapper around ChaCha20Poly1305.
A BIP324Cipher class that encapsulates key agreement, key derivation, and stream ciphers and AEADs for BIP324 packet encoding.

The ChaCha20Poly1305 and FSChaCha20Poly1305 implementations are new, taking advance of the improvements in #27993.

DrahtBot commented at 10:00 pm on June 29, 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	jamesob, theStack, stratospher

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:

#28100 (crypto: more Span<std::byte> modernization & follow-ups 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.

DrahtBot added the label CI failed on Jun 30, 2023

sipa force-pushed on Jun 30, 2023

DrahtBot removed the label CI failed on Jun 30, 2023

sipa force-pushed on Jul 7, 2023

DrahtBot added the label CI failed on Jul 7, 2023

sipa force-pushed on Jul 7, 2023

sipa renamed this:
~~BIP324 ciphers: FSChaCha20 and FSChaCha20Poly1305~~
BIP324 ciphersuite
on Jul 7, 2023

sipa force-pushed on Jul 8, 2023

DrahtBot removed the label CI failed on Jul 8, 2023

sipa force-pushed on Jul 10, 2023

sipa force-pushed on Jul 11, 2023

DrahtBot added the label Needs rebase on Jul 12, 2023

sipa force-pushed on Jul 12, 2023

DrahtBot removed the label Needs rebase on Jul 12, 2023

DrahtBot added the label CI failed on Jul 12, 2023

sipa force-pushed on Jul 13, 2023

DrahtBot removed the label CI failed on Jul 13, 2023

sipa marked this as ready for review on Jul 17, 2023

sipa force-pushed on Jul 17, 2023

sipa commented at 10:54 pm on July 17, 2023: member

Rebased after merge of #28065, and marked ready for review as dependencies #27993 and #27985 are in.

in src/crypto/chacha20poly1305.cpp:86 in 26a7c254dc outdated

68+    m_chacha20.Seek64(nonce, 1);
69+    m_chacha20.Crypt(UCharCast(plain.data()), UCharCast(cipher.data()), plain.size());
70+
71+    // Get first block of keystream.
72+    std::byte first_block[64];
73+    m_chacha20.Seek64(nonce, 0);

jamesob commented at 2:29 pm on July 19, 2023:

26a7c254dcb49a92070c88cc7963e4996cd9e7c7

(Non-blocking note:) a little unexpected that this is written out of sequence with how it’s described in RFC 8439;

First, a Poly1305 one-time key is generated from the 256-bit key and nonce using the procedure described in Section 2.6.

Next, the ChaCha20 encryption function is called to encrypt the plaintext, using the same key and nonce, and with the initial counter set to 1.

No harm in writing it this way, since a Seek64() resets any determinant state for Keystream64()/Crypt64(), but just had to squint for a few seconds to make sure it was okay.

sipa commented at 2:00 pm on July 21, 2023:

I believe this may be clearer now that it’s been rewritten. Also see #28008 (review) for a rationale, if you’re curious.

in src/test/crypto_tests.cpp:976 in 26a7c254dc outdated

844+                         "73206f66202739393a204966204920636f756c64206f6666657220796f75206f"
845+                         "6e6c79206f6e652074697020666f7220746865206675747572652c2073756e73"
846+                         "637265656e20776f756c642062652069742e",
847+                         "50515253c0c1c2c3c4c5c6c7",
848+                         "808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9f",
849+                         {7, 0x4746454443424140},

jamesob commented at 3:53 pm on July 19, 2023:

Note for reviewers that RFC test vectors use network byte order (big-endian); the Nonce96 constructor here expects little-endian representation. Hence the reversal relative to RFC vectors.

sipa commented at 1:59 pm on July 21, 2023:

Note for reviewers that RFC test vectors use network byte order (big-endian);

That’s not really accurate. The RFC (and its test vectors) see the nonce as a 12-byte array, not as a number that needs encoding. If anything, it assumes little-endian encoding (see https://datatracker.ietf.org/doc/html/rfc8439#section-2.3, “A 96-bit nonce, treated as a concatenation of three 32-bit little-endian integers.”).

the Nonce96 constructor here expects little-endian representation.

The Nonce96 type here is indeed a pair of 32-bit and 64-bit integers which are serialized in little-endian notation to obtain the 12-byte array nonce in the RFC8439 sense.

Hence the reversal relative to RFC vectors.

The reversal is actually due to the fact that integer constants in C++ (and in English…) are written in big-endian. After that point, everything in the code and the spec are little-endian.

in src/test/crypto_tests.cpp:981 in 26a7c254dc outdated

849+                         {7, 0x4746454443424140},
850+                         "d31a8d34648e60db7b86afbc53ef7ec2a4aded51296e08fea9e2b5a736ee62d6"
851+                         "3dbea45e8ca9671282fafb69da92728b1a71de0a9e060b2905d6a5b67ecd3b36"
852+                         "92ddbd7f2d778b8c9803aee328091b58fab324e4fad675945585808b4831d7bc"
853+                         "3ff4def08e4b7a9de576d26586cec64b61161ae10b594f09e26a7e902ecbd060"
854+                         "0691");

jamesob commented at 4:00 pm on July 19, 2023:

Note for reviewers that this ciphertext includes the Poly1305 tag; in the RFC, ciphertext vector omits the tag.

sipa commented at 5:32 pm on July 21, 2023:

Yeah, it gives the tag separately; the RFC doesn’t actually require the tag to be sent at the end.

sipa commented at 9:12 pm on July 26, 2023:

Added a comment to explain.

in src/crypto/chacha20poly1305.cpp:54 in c61fa6ab59 outdated

53+    poly1305.Update(aad).Update(Span{PADDING}.first(aad_padding));
54     // Process the padded ciphertext with Poly1305.
55-    poly1305.Update(cipher);
56-    poly1305.Update(Span{PADDING}.first((16 - (cipher.size() % 16)) % 16));
57+    unsigned cipher_padding = (16 - (cipher.size() % 16)) % 16;
58+    poly1305.Update(cipher).Update(Span{PADDING}.first(cipher_padding));

theStack commented at 8:03 pm on July 20, 2023:

(in commit c61fa6ab5917f3745a917f4fc2f3a9e96629d5d9) nit: these refactoring changes in UpdateTag seem to be unrelated to FSChaCha20Poly1305, I think they can be already included the commit that introduces the ChaCha20Poly1305 AEAD (to avoid touching it again later and keep the diff small)? Also, aad_padding and cipher_padding could be const.

sipa commented at 0:32 am on July 21, 2023:

Fixed.

in src/crypto/chacha20poly1305.cpp:69 in 26a7c254dc outdated

64+{
65+    assert(cipher.size() == plain.size() + EXPANSION);
66+
67+    // Encrypt using ChaCha20 (starting at index 1).
68+    m_chacha20.Seek64(nonce, 1);
69+    m_chacha20.Crypt(UCharCast(plain.data()), UCharCast(cipher.data()), plain.size());

theStack commented at 9:03 pm on July 20, 2023:

nit: could encrypt after generating the poly1305 key to avoid having to Seek64 twice, as the chacha20 object is already at the desired block count 1 after the Keystream call below (I think generate-poly1305-key -> encrypt -> compute tag is also the order as described in RFC8439). On the other hand, performance-wise it shouldn’t make a difference as Seek64 is quite cheap, and maybe it’s even preferred to be explicit about the block counter instead. I haven’t looked at any other ChaCha20Poly1305 AEAD implementation yet, so no idea what is common practice here. Just an idea.

sipa commented at 0:32 am on July 21, 2023:

I believe it’s better not to do that, though it really doesn’t matter much.

The reason is that if we’d start by generating the key, we’d have to store that key in memory somewhere, leave it there for the whole encryption, then fetch it again (at which point it’s quite possibly gone from CPU caches) to compute the tag. By seeking and deriving at the end, we only need the chacha20 key/state, which is likely still hot at that point (as it’s needed every 64 bytes of encryption). And the seeking itself is trivial.

in src/crypto/chacha20poly1305.cpp:76 in 26a7c254dc outdated

71+    // Get first block of keystream.
72+    std::byte first_block[64];
73+    m_chacha20.Seek64(nonce, 0);
74+    m_chacha20.Keystream(UCharCast(first_block), sizeof(first_block));
75+    // Use the first 32 bytes of the first keystream block as poly1305 key.
76+    Poly1305 poly1305{Span{first_block}.first(Poly1305::KEYLEN)};

theStack commented at 9:14 pm on July 20, 2023:

nit: it might be worth introducing a generate-poly1305-key helper (or even one that also does the tag computation already, given also aad and ciphertext) that can be called in Encrypt and Decrypt, to deduplicate code?

sipa commented at 0:30 am on July 21, 2023:

Done, I’ve replaced UpdateTag with ComputeTag, which does the whole tag calculation, including poly1305 key generation.

theStack commented at 9:32 pm on July 20, 2023: contributor

Reviewed the first four commits so far (up to c61fa6ab5917f3745a917f4fc2f3a9e96629d5d9), verified that the implementations of AEADChaCha20Poly1305, FSChaCha20 and FSChaCha20Poly1305 match the corresponding RFC8439 / BIP324 specifications. As with previous PRs, verified the test vectors (this time using PyCryptodome again) which was a bit more effort this time, as the rekeying wrappers FSChaCha20{Poly1305} also had to be implemented first: https://gist.github.com/theStack/e910505e39204c695a073ccc6d63719a

Left a few nits below.

sipa force-pushed on Jul 21, 2023

jamesob commented at 1:30 pm on July 21, 2023: contributor

Submitting partial review (now to some degree obviated) up to the FSChaCha20 implementation.

Looking good so far. I also did cross-validation of the test vectors with a Python library (happily a different implementation than The Stack Man) - the script for that can be found here, where I’ve manually copied test data from @sipa’s cpp and verified with the unrelated Python implementation.

in src/crypto/chacha20poly1305.cpp:45 in d377aa6086 outdated

40+    return (ret != 0);
41+}
42+
43+#endif
44+
45+/** Compute poly1305 thag. chacha20 must be set to the right nonce, block 0. Will be at block 1 after. */

jamesob commented at 6:04 pm on July 21, 2023:

cacc8fe2b59e45cde248a031c5ebbf9ec39c5b8f

“thag.” Sounds Nordic.

sipa commented at 9:12 pm on July 26, 2023:

Fixed.

in src/crypto/chacha20.h:135 in 5e0ca4ba37 outdated

130+    /** The number of rekey operations that have happened. */
131+    uint64_t m_rekey_counter{0};
132+
133+public:
134+    /** Length of keys expected by the constructor. */
135+    static constexpr unsigned KEYLEN = 32;

jamesob commented at 6:52 pm on July 21, 2023:

5e0ca4ba371570d1a5275c5a79bc0c1253d97ead

Odd to me that KEYLEN doesn’t live higher up in the class hierarchy, since the other ChaCha20* only deal in 32-byte keys, but definitely not a big deal.

sipa commented at 5:13 pm on July 25, 2023:

See #28100, which modernizes class ChaCha20 too.

in src/test/crypto_tests.cpp:288 in df4303b996 outdated

292     std::vector<std::byte> keystream(plain.size());
293+    AEADChaCha20Poly1305 aead{key};
294     aead.Keystream(nonce, keystream);
295     for (size_t i = 0; i < plain.size(); ++i) {
296-        BOOST_CHECK_EQUAL(plain[i] ^ keystream[i], cipher[i]);
297+        BOOST_CHECK((plain[i] ^ keystream[i]) == expected_cipher[i]);

jamesob commented at 8:19 pm on July 21, 2023:

df4303b996f8b4f095de18edd7d3dbe281b5f124

If you have to retouch, maybe worth keeping the BOOST_CHECK_EQUAL (which compiles for me okay) since it’ll give a printout of the mismatch.

sipa commented at 9:12 pm on July 26, 2023:

Fixed.

in src/test/bip324_tests.cpp:95 in d377aa6086 outdated

91@@ -89,9 +92,67 @@ void TestBIP324PacketVector(
92     BOOST_CHECK(ciphertext.size() >= out_ciphertext_endswith.size());
93     BOOST_CHECK(Span{out_ciphertext_endswith} == Span{ciphertext}.last(out_ciphertext_endswith.size()));
94 
95-    // Note that we don't test decryption here, as the test vectors don't provide the other party's
96-    // private key, so we cannot act like them. See the bip324_cipher_roundtrip fuzz test for a test
97-    // that does cover decryption.
98+    for (unsigned error = 0; error <= 11; ++error) {

theStack commented at 1:15 am on July 22, 2023:

off-by-one, the “message index wrong” kind of error type (error=12) is currently not tested:

0    for (unsigned error = 0; error <= 12; ++error) {

(to avoid issues like this, could add an enum with error types and give the highest error sth like ERROR_HIGHEST, to be used in the loop counter, but that’s probably overkill)

sipa commented at 2:59 pm on July 24, 2023:

Fixed.

I’ve chosen not to introduce an enum, because it’s not a very good with with the multiple bit error cases.

in src/test/fuzz/crypto_chacha20.cpp:164 in 5e0ca4ba37 outdated

159+    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
160+
161+    auto key = fuzzed_data_provider.ConsumeBytes<std::byte>(FSChaCha20::KEYLEN);
162+    key.resize(FSChaCha20::KEYLEN);
163+    auto salt = fuzzed_data_provider.ConsumeBytes<std::byte>(FSChaCha20::KEYLEN);
164+    salt.resize(FSChaCha20::KEYLEN);

theStack commented at 10:22 pm on July 23, 2023:

salt is currently not used anywhere.

sipa commented at 2:59 pm on July 24, 2023:

No idea where this came from. Fixed.

sipa force-pushed on Jul 24, 2023

jamesob commented at 4:20 pm on July 25, 2023: contributor

Review check-in; up to (but not including) 9e65744c4f44ce89f3176870d3cc25ac2b6bdc08

sipa commented at 3:27 am on July 26, 2023: member

After thinking/working through further PRs, I’m beginning to wonder if it isn’t better if these classes support incremental computation (i.e., the entire message/packet to be encrypted/decrypted isn’t required to be presented in a one (or two) contiguous block(s) of memory, at a single point in time).

The advantage would primarily be a slightly lower latency when receiving a large P2P message. As is, the entire message needs to be received before any decryption can take place. With an incremental API, it could be decrypted on-the-fly as bytes are received over the wire, allowing a possibly shorter delay after the last byte is received. To get an idea about numbers: FSChaCha20Poly1305 on my Ryzen 5950X takes ~1.6 ns/byte, which would be 3.2 ms for a 2 MB block.

So advantages:

Lower latency when decrypting large messages.
More natural ability for split processing, possibly allowing fewer intermediary buffers to assemble plaintexts.

Disadvantages:

More complex code, needing more complex tests to cover all possible scenarios.
Harder to make a safe-to-use API. The current approach has the advantage that it’s impossible to get a decrypted message back if it fails the authenticity check. This is virtually impossible to prevent with an incremental API.

WDYT?

carnhofdaki commented at 8:50 am on July 26, 2023: contributor

@sipa I think that the disadvantages you mention are much worse than the advantages it would bring. I think that keeping it simple is (at least in this implementation intended for first appearance in the master branch) an important feature of BIP-324.

As for me and my poor old Bitcoin node, please do not add complexity to the code.

jamesob commented at 1:41 pm on July 26, 2023: contributor

To get an idea about numbers: FSChaCha20Poly1305 on my Ryzen 5950X takes ~1.6 ns/byte, which would be 3.2 ms for a 2 MB block.

I was curious how this (additive?) 3.2ms delay compares to existing block connection latency, so I sampled some logs from some of the okayish-CPU-but-well-networked machines I run. The Connect block: XXms logs average to 67.8ms from that sample (after stripping out the long startup outliers). So from my perspective, this additional latency, while not negligible, wouldn’t dissuade me personally from running with v2 P2P links.

But that said, assuming those numbers (68ms average connect time, +3.2ms V2 slowdown), we are talking about a theoretical 4.7% hit to global block propagation speed. For me this is right on the cusp of risking higher stale block rates, but that’s not based on anything aside from gut feeling. Maybe we need to go back and review @cdecker’s work on block propagation sensitivity…

Of course, assuming that a 2MB transmission is necessary to connect blocks is a pessimistic assumption - compact blocks probably makes for a much lighter message most of the time. So I should walk back that “5% global propagation slowdown” concern as a little bombastic.

Pulling average cmpctblock message sizes from the same node(s), we find that the average is ~21807 bytes, or 0.022MB. In that case, we’re talking about a marginal V2 slowdown of 0.035ms, or 0.05% - which is much more palatable.

WDYT?

For me, V2 is a very important feature to get deployed. I would be hesitant to block the path to its deployment with items that are not themselves critical. So my assessment would be based on the particulars:

How much more complicated do you think a “streaming” API would be?
- What’s the rough size of the diff from this change?
If a streaming API necessarily delays the authentication of messages, what does this mean for new DoS conditions?

But I guess after realizing that the marginal delays we’re talking about will be pretty much negligible for high-bandwidth compactblock receiving nodes, my vote is that we continue with this simple and more obviously correct/safe approach, and leave a streaming reimplementation for a later day - which presumably can be done without any protocol changes.

sipa commented at 2:47 pm on July 26, 2023: member

@jamesob Thanks for your comments, I think I largely agree.

It’s a good observation that the case where a large non-compact block message is necessary for block connectivity is already fairly pessimal. Some more points to put this overhead in perspective:

If you assume - say - a 1 Gbit/s connection, then receiving a byte takes 8 ns already, so adding 1.6 ns at most adds ~20% (regardless of whether the received data is short or big), and this ignores any other processing on top for the new block.
This overhead inherently exists on the sender side in a way that cannot be avoided (as the block or whatever message is not constructed incrementally). So arguably, for the overall node-to-node latency, it’s at worst a 10% overhead at 1 Gbit/s. EDIT: Actually, no, streaming encryption is also possible, and possibly helpful.
We can probably bring that 1.6 ns number down by a factor 2x or 4x using machine-specific optimizations if need be (which will improve both sender and receiver).

How much more complicated do you think a “streaming” API would be?

It’d consist of more functions, e.g. StartEncrypt / StartDecrypt, EncryptData / DecryptData, FinishEncrypt / FinishDecrypt, instead of functions that deal with the message in one go. On the other hand, it would allow dropping the functions that currently exist which accept a split buffer plaintext.

I think most of the complexity would really be in designing them in a way that doesn’t break abstractions too much. E.g. can you make it so that a caller does not need to know that the precisely first byte and last 16 bytes do not need a corresponding decryption buffer, for a BIP324 packet?

What’s the rough size of the diff from this change?

Almost entirely in tests I think (and harder to understand API). The actual non-test code changes would be minimal, I expect.

If a streaming API necessarily delays the authentication of messages,

Quite the opposite. A streaming API means that encryption/decryption (and authentication) state can be updated any time part of a message is processed/received. When the last bytes arrive, there would just be a finalization step, rather than needing to still perform the entire computation.

what does this mean for new DoS conditions?

Nothing, because semantically nothing changes. The conceptual behavior must be:

Message is received (in full).
Message is authenticated. If this fails, disconnect.
Message is decrypted, and released to the caller.

In a streaming setting, some of that decryption and authentication computation is done during the receiving, rather than sequentially. However, the overall behavior must still be indistinguishable from the receive/authenticate/decrypt sequence. In particular, the caller cannot take any action that depends on the decrypted message content before the entire message has been authenticated (otherwise you introduce a decryption oracle). This is I think the biggest concern with a streaming API: the caller immediately gets (parts of) the decrypted message back, but is not allowed to use/inspect them in any way before the full message has been processed.

jamesob commented at 3:10 pm on July 26, 2023: contributor

This is I think the biggest concern with a streaming API: the caller immediately gets (parts of) the decrypted message back, but is not allowed to use/inspect them in any way before the full message has been processed.

So just to be sure I understand, the risk is not any additional space requirement (since we need to buffer the full decrypted message anyway as things stand right now), but rather the risk of streaming is that the caller of this API will make some unwise use of a partially processed message before it has been proven to be authentic.

If correct, this strikes me as a pretty remote risk given that the consumption of this API is limited to our codebase and so it should be easy to make users aware of this caveat.

All that said, I still think we should proceed as-is, and I will continue review on this changeset.

sipa commented at 3:15 pm on July 26, 2023: member

So just to be sure I understand, the risk is not any additional space requirement (since we need to buffer the full decrypted message anyway as things stand right now), but rather the risk of streaming is that the caller of this API will make some unwise use of a partially processed message before it has been proven to be authentic.

Yes.

If correct, this strikes me as a pretty remote risk given that the consumption of this API is limited to our codebase and so it should be easy to make users aware of this caveat.

I have no doubt that we’re able to write correct code that doesn’t do anything wrong here. Still, it will make the code harder to understand for future contributors.

All that said, I still think we should proceed as-is, and I will continue review on this changeset.

Makes sense.

in src/test/bip324_tests.cpp:53 in 9e65744c4f outdated

48+    auto in_aad = ParseHex<std::byte>(in_aad_hex);
49+    auto mid_send_garbage = ParseHex<std::byte>(mid_send_garbage_hex);
50+    auto mid_recv_garbage = ParseHex<std::byte>(mid_recv_garbage_hex);
51+    auto out_session_id = ParseHex<std::byte>(out_session_id_hex);
52+    auto out_ciphertext = ParseHex<std::byte>(out_ciphertext_hex);
53+    auto out_ciphertext_endswith = ParseHex<std::byte>(out_ciphertext_endswith_hex);

jamesob commented at 3:48 pm on July 26, 2023:

9e65744c4f44ce89f3176870d3cc25ac2b6bdc08

Only if you retouch, might be nice to declare the values that don’t change here as const auto.

sipa commented at 9:12 pm on July 26, 2023:

Done.

in src/test/bip324_tests.cpp:88 in 9e65744c4f outdated

83+    }
84+    std::vector<std::byte> ciphertext(contents.size() + cipher.EXPANSION);
85+    cipher.Encrypt(contents, in_aad, in_ignore, ciphertext);
86+
87+    // Verify ciphertext.
88+    if (!out_ciphertext.empty()) BOOST_CHECK(out_ciphertext == ciphertext);

jamesob commented at 4:46 pm on July 26, 2023:

9e65744c4f44ce89f3176870d3cc25ac2b6bdc08

Slightly confused by why this conditional is necessary - can you explain in what case our expected ciphertext would be empty, but the actually generated ciphertext wouldn’t be? I’ve tried removing this conditional but I get test failures.

sipa commented at 9:14 pm on July 26, 2023:

Added a comment to explain, and restructured a bit.

The BIP’s test vectors specify either out_ciphertext (for short messages) or out_ciphertext_endswith (for long messages), the other one is empty. We should only compare the one that was provided.

in src/test/fuzz/bip324.cpp:122 in 9e65744c4f outdated

113+        uint32_t dec_length = (from_init ? responder : initiator).DecryptLength(Span{ciphertext}.first(initiator.LENGTH_LEN));
114+        if (!damage) {
115+            assert(dec_length == length);
116+        } else {
117+            // For performance reasons, don't try to decode if length got increased too much.
118+            if (dec_length > 16384 + length) break;

jamesob commented at 5:38 pm on July 26, 2023:

9e65744c4f44ce89f3176870d3cc25ac2b6bdc08

Choice of 2**14 arbitrary?

sipa commented at 9:15 pm on July 26, 2023:

Kind of. Permitting this to grow too large makes the test slower. The plaintext also has this restriction.

in src/test/fuzz/bip324.cpp:126 in 9e65744c4f outdated

121+        }
122+
123+        // Decrypt
124+        std::vector<std::byte> decrypt(dec_length);
125+        bool dec_ignore{false};
126+        bool ok = (from_init ? responder : initiator).Decrypt(Span{ciphertext}.subspan(initiator.LENGTH_LEN), aad, dec_ignore, decrypt);

jamesob commented at 5:41 pm on July 26, 2023:

9e65744c4f44ce89f3176870d3cc25ac2b6bdc08

Small thing, but if you retouch maybe:

 0diff --git a/src/test/fuzz/bip324.cpp b/src/test/fuzz/bip324.cpp
 1index 5df279b7df..376728d61d 100644
 2--- a/src/test/fuzz/bip324.cpp
 3+++ b/src/test/fuzz/bip324.cpp
 4@@ -109,8 +109,10 @@ FUZZ_TARGET(bip324_cipher_roundtrip, .init=Initialize)
 5             }
 6         }
 7
 8+        auto& receiver{from_init ? responder : initiator};
 9+
10         // Decrypt length
11-        uint32_t dec_length = (from_init ? responder : initiator).DecryptLength(Span{ciphertext}.first(initiator.LENGTH_LEN));
12+        uint32_t dec_length = receiver.DecryptLength(Span{ciphertext}.first(initiator.LENGTH_LEN));
13         if (!damage) {
14             assert(dec_length == length);
15         } else {
16@@ -123,7 +125,7 @@ FUZZ_TARGET(bip324_cipher_roundtrip, .init=Initialize)
17         // Decrypt
18         std::vector<std::byte> decrypt(dec_length);
19         bool dec_ignore{false};
20-        bool ok = (from_init ? responder : initiator).Decrypt(Span{ciphertext}.subspan(initiator.LENGTH_LEN), aad, dec_ignore, decrypt);
21+        bool ok = receiver.Decrypt(Span{ciphertext}.subspan(initiator.LENGTH_LEN), aad, dec_ignore, decrypt);
22         // Decryption *must* fail if the packet was damaged, and succeed if it wasn't.
23         assert(!ok == damage);
24         if (!ok) break;

sipa commented at 9:15 pm on July 26, 2023:

Done.

jamesob approved

jamesob commented at 8:19 pm on July 26, 2023: contributor

ACK 180909f2c859be3c79630d9705c26a457715b9ed (jamesob/ackr/28008.3.sipa.bip324_ciphersuite)

Looks great. I’ve spent about a week ramping up on BIP-324, reading the BIPs and underlying RFC 8439, asking @sipa stupid questions about the garbage terminator, and carefully reviewing the code in this pull request. I’ve verified the ChaCha20-Poly1305 test vectors against an unrelated implementation (Python’s chacha20poly1305, in this script).

I haven’t hand-verified the BIP-325 test vectors, but I have at least verified that they are a faithful reproduction of the same vectors used to validate the example BIP-0325 Python implementation, included in the BIPs repo. So at the very least, I have verified that this implementation is a faithful reproduction of the one sketched by the BIP.

The code looks very good, and is pretty easy to follow with minor cosmetic phrasing differences from the protocol flow described in the BIP. Outside of running tests, I haven’t run this branch on mainnet simply because none of the changes really interface with live codepaths; this code will certainly be used in future BIP-325 related patches, which will merit live testing. I think it is sufficient to lean on the introduced test coverage to attest to the safety of this change.

 0-----BEGIN PGP SIGNED MESSAGE-----
 1Hash: SHA512
 2
 3ACK 180909f2c859be3c79630d9705c26a457715b9ed ([`jamesob/ackr/28008.3.sipa.bip324_ciphersuite`](https://github.com/jamesob/bitcoin/tree/ackr/28008.3.sipa.bip324_ciphersuite))
 4
 5Looks great. I've spent about a week ramping up on BIP-324, reading the BIPs and underlying RFC 8439, asking [@sipa](/bitcoin-bitcoin/contributor/sipa/) stupid questions about the garbage terminator, and carefully reviewing the code in this pull request. I've verified the ChaCha20-Poly1305 test vectors against an unrelated implementation (Python's chacha20poly1305, in [this script](https://github.com/jamesob/bitcoin-review-data/blob/master/28008.sipa.bip324_ciphersuite/verifycrypto.py).
 6
 7I haven't hand-verified the BIP-325 test vectors, but I have at least verified that they are a faithful reproduction of the same vectors used to validate the example BIP-0325 Python implementation, included in the BIPs repo. So at the very least, I have verified that this implementation is a faithful reproduction of the one sketched by the BIP.
 8
 9The code looks very good, and is pretty easy to follow with minor cosmetic phrasing differences from the protocol flow described in the BIP. Outside of running tests, I haven't run this branch on mainnet simply because none of the changes really interface with live codepaths; this code will certainly be used in future BIP-325 related patches, which will merit live testing. I think it is sufficient to lean on the introduced test coverage to attest to the safety of this change.
10-----BEGIN PGP SIGNATURE-----
11
12iQIzBAEBCgAdFiEEGNRVI1NPYuZCSIrGepNdrbLETwUFAmTBf74ACgkQepNdrbLE
13TwVTEA/+OTunSNd8cy1tB+STraanydPQT1rrA4veCl+/h9ibFHn6c9Pn4HG1rp9k
14cVWzTlPyOfcMDk/iuRokKFVlr+Wa6dcZnPzVdBDM+2qzf89zgyYj9yWgIuPMEOYd
15Gas3TC1msNAkDJmXH95UzwB4BGlemZPzMu6t1ybcYM3uEaPQWeG6xU36Izr+UdHm
16poPOOhPJcvSqLnvk1x0UfuYUPWSBog8XWiz2MLcH2e8AG+55JcAEUXCAZBVuaL52
17dPUW4WbYphjlBGyEW0JFTq/Euy2tCw14KFHCZ/T0Mhriz5OsXLWj4C+9MfOFRnce
18f85wGR62bpLICOmnWYfpKpbHPWzlmRTZ4r134R1dKjqwhUk8WKdm+HxWZLB0MVQS
19T7n8U3HIyzXF7cBNmi0V+t6ZT1ZXEMxG0dQhTe+3FEbq10wZt26nuTIeWETnFtZ6
20/2dm+3Z7xdCULkrH6IANt9dnpsqRD3IvQRmJuLlBSMNsbulIzLiWiaeLHWgxHcis
21ZGN9Ki+KulvwR4JCwtKTluFWrLQZUSRhqK0I5LgUlJT4R53d/0E48LSqvO0r4QUq
22we7dlJG+LaoS1brms80GlguqSrQ7ngWBNHi6k1V6yCJZfKV5ppGrdV8fRpz8fBE2
23esgxrh2yp1RA8SMGFh+k7yZ5RgoV36uZkERwfLMHdpkm/ZwHQH4=
24=H+8R
25-----END PGP SIGNATURE-----

0Tested on Linux-6.4.3-arch1-1-x86_64-with-glibc2.37
1
2Configured with ./configure 'BDB_LIBS=-L/home/james/src/bitcoin/db4/lib -ldb_cxx-4.8' BDB_CFLAGS=-I/home/james/src/bitcoin/db4/include 'CXXFLAGS=-fPIE -pipe -O2 -g -Wthread-safety-analysis -Wall -Werror=sign-compare ' --disable-gui-tests --disable-fuzz-binary --enable-wallet --enable-debug --with-daemon --enable-natpmp-default
3
4Compiled with /usr/bin/ccache /usr/bin/clang++ -std=c++17 -mavx -mavx2 -mpclmul -fPIE -pipe -O2 -g -Wthread-safety-analysis -Wall -Werror=sign-compare  -O0 -g3 -ftrapv -fdebug-prefix-map=$(abs_top_srcdir)=.  -Wstack-protector -fstack-protector-all -fcf-protection=full -fstack-clash-protection -msse4.1 -msse4.2 -msse4 -msha  i
5
6Compiler version: clang version 15.0.7

crypto: remove outdated variant of ChaCha20Poly1305 AEAD

Remove the variant of ChaCha20Poly1305 AEAD that was previously added in
anticipation of BIP324 using it. BIP324 was updated to instead use rekeying
wrappers around otherwise unmodified versions of the ChaCha20 stream cipher
and the ChaCha20Poly1305 AEAD as specified in RFC8439.

9fd085a1a4

crypto: add the ChaCha20Poly1305 AEAD as specified in RFC8439

This adds an implementation of the ChaCha20Poly1305 AEAD exactly matching
the version specified in RFC8439 section 2.8, including tests and official
test vectors.

9ff0768bdc

crypto: add FSChaCha20, a rekeying wrapper around ChaCha20

This adds the FSChaCha20 stream cipher as specified in BIP324, a
wrapper around the ChaCha20 stream cipher (specified in RFC8439
section 2.4) which automatically rekeys every N messages, and
manages the nonces used for encryption.

Co-authored-by: dhruv <856960+dhruv@users.noreply.github.com>

0fee267792

crypto: add FSChaCha20Poly1305, rekeying wrapper around ChaCha20Poly1305

This adds the FSChaCha20Poly1305 AEAD as specified in BIP324, a wrapper
around the ChaCha20Poly1305 AEAD (as specified in RFC8439 section 2.8) which
automatically rekeys every N messages, and automatically increments the nonce
every message.

aa8cee9334

bench: add benchmark for FSChaCha20Poly1305

Add a benchmark for FSChaCha20Poly1305 encryption, so the overhead of key
generation and authentication can be observed for various message sizes.

af2b44c76e

crypto: support split plaintext in ChaCha20Poly1305 Encrypt/Decrypt c91cedf281

Add BIP324Cipher, encapsulating key agreement, derivation, and stream/AEAD ciphers

Co-authored-by: dhruv <856960+dhruv@users.noreply.github.com>

990f0f8da9

tests: add decryption test to bip324_tests 1c7582ead6

sipa force-pushed on Jul 26, 2023

theStack commented at 2:15 am on July 27, 2023: contributor

Regarding the stream API discussion, I’d also prefer simplicity over efficiency for now and hence vote for keeping the implementation as-is; the potential advantage of “slightly lower latency when receiving a large P2P message” doesn’t seem to outweigh the increased complexity / review power needed, even if it would mostly affect test code. @jamesob made some convincing points for that and I’m also sharing the following sentiment:

For me, V2 is a very important feature to get deployed. I would be hesitant to block the path to its deployment with items that are not themselves critical.

Back to the actual code. Continued review from commit 5/8 (af2b44c76e5de8ce880381e5535ead37ab0b3ba9) onwards. Verified that the BIP324Cipher class implementation matches the BIP and also checked the corresponding test vectors by extending my own hacky Python implementation using PyCryptodome (for ChaCha20, ChaCha20Poly1305, SHA256 and HKDF with HMAC_SHA256) + ellswift from our test framework for (see updated gist https://gist.github.com/theStack/e910505e39204c695a073ccc6d63719a).

Planning another full review round over the next days, still have to look at the fuzz tests and the decryption error test cases.

jamesob approved

jamesob commented at 4:34 pm on July 27, 2023: contributor

reACK 1c7582e

Based on the interdiff (https://github.com/jamesob/bitcoin-review-data/blob/master/28008.sipa.bip324_ciphersuite/4.1c7582e/interdiff.3.180909f.diff), which contains the few minor changes @sipa has mentioned above (const declarations, doc adds, small refactors).

by extending my own hacky Python implementation using PyCryptodome (for ChaCha20, ChaCha20Poly1305, SHA256 and HKDF with HMAC_SHA256) + ellswift from our test framework for (see updated gist https://gist.github.com/theStack/e910505e39204c695a073ccc6d63719a).

Nice job @theStack! Less code necessary than I would’ve thought.

in src/test/bip324_tests.cpp:134 in 1c7582ead6

132+
133+        // Construct copied (and possibly damaged) copy of ciphertext.
134+        // Decrypt length
135+        auto to_decrypt = ciphertext;
136+        if (error >= 2 && error <= 9) {
137+            to_decrypt[InsecureRandRange(to_decrypt.size())] ^= std::byte(1U << InsecureRandRange(8));

theStack commented at 12:00 pm on July 28, 2023:

tiny-nit (or more, a curiosity question): Was it intended to derive the bit position within the byte randomly? Due to the choice of having 8 error values for this case, I was assuming that the idea was to systematically damage with all bit positions 0..7.

0            to_decrypt[InsecureRandRange(to_decrypt.size())] ^= std::byte(1U << (error - 2));

But in practice it shouldn’t really matter and I guess both are fine.

sipa commented at 12:44 pm on July 30, 2023:

That very much sounds like it could have been my intent, but I honestly can’t remember. I’ll make this change if I retouch.

stratospher commented at 3:58 am on August 14, 2023:

done in #28267.

theStack approved

theStack commented at 12:11 pm on July 28, 2023: contributor

ACK 1c7582ead6e1119899922041c1af2b4169b0bc74

Finished reviewing. Code looks good to me, checked carefully that the implementation matches BIP324 and verified the test vectors (see above). :heavy_check_mark:

in src/test/fuzz/bip324.cpp:78 in 990f0f8da9 outdated

73+    LIMITED_WHILE(provider.remaining_bytes(), 1000) {
74+        // Mode:
75+        // - Bit 0: whether the ignore bit is set in message
76+        // - Bit 1: whether the responder (0) or initiator (1) sends
77+        // - Bit 2: whether this ciphertext will be corrupted (making it the last sent one)
78+        // - Bit 3-4: controls the maximum aad length (max 511 bytes)

stratospher commented at 2:54 pm on August 3, 2023:

990f0f8: aad in the BIP allows upto 4095 max bytes (max garbage length). is this a performance saver too?

sipa commented at 10:15 pm on August 13, 2023:

The (FS)ChaCha20Poly1305 cipher really supports up to $2^{64}-1$ bytes of AAD. It just so happens that we only use it for garbage, and the garbage is limited to 4095 bytes. We need some kind of limit anyway, but it’s a fair point that for our purposes, 4095 would be a more natural limit.

stratospher commented at 3:58 am on August 14, 2023:

done in #28267.

in src/crypto/chacha20.cpp:355 in 0fee267792 outdated

350+        m_chacha20.Keystream(UCharCast(new_key), sizeof(new_key));
351+        // Update its key.
352+        m_chacha20.SetKey32(UCharCast(new_key));
353+        // Wipe the key (a copy remains inside m_chacha20, where it'll be wiped on the next rekey
354+        // or on destruction).
355+        memory_cleanse(new_key, sizeof(new_key));

achow101 commented at 6:25 pm on August 4, 2023:

In 0fee267792eb8cbdd48ad78f1712420b5d8d905b “crypto: add FSChaCha20, a rekeying wrapper around ChaCha20”

We have secure_allocator which handles this cleaning when the object is destroyed, could we use that instead of having to remember to explicitly memory_cleanse secret data?

sipa commented at 10:27 pm on August 13, 2023:

@achow101 We have a zero_after_free_allocator, which sounds like what you’re describing. The secure_allocator goes a step further an allocates from a pool of non-swappable memory pages on supporting systems.

The secure_allocator’s behavior does sound overkill for the BIP324 purpose, I feel, and it may be counterproductive even because non-swappable memory is limited, and we really want it for our high-quality RNG and wallet keys.
The zero_after_free_allocator’s behavior is what we want, but actually using an allocator still comes with the additional cost that it would mean FSChaCha20 objects would require an additional heap allocation every time the keys are cycled. I feel that doesn’t weigh up against the added ease of understanding that approach brings.

in src/test/crypto_tests.cpp:285 in aa8cee9334 outdated

280+    auto expected_cipher = ParseHex<std::byte>(cipher_hex);
281+    std::vector<std::byte> cipher(plain.size() + FSChaCha20Poly1305::EXPANSION);
282+
283+    FSChaCha20Poly1305 enc_aead{key, 224};
284+    for (uint64_t i = 0; i < msg_idx; ++i) {
285+        std::byte dummy_tag[FSChaCha20Poly1305::EXPANSION] = {{}};

achow101 commented at 6:38 pm on August 4, 2023:

In aa8cee93342ee857931afec9af3ff5dbd8ce7749 “crypto: add FSChaCha20Poly1305, rekeying wrapper around ChaCha20Poly1305”

This variable could live outside of the loop and just be reused every time.

stratospher commented at 7:02 am on August 13, 2023:

done in #28267.

in src/crypto/chacha20poly1305.cpp:96 in 9ff0768bdc outdated

91+
92+    // Verify tag (using key drawn from block 0).
93+    m_chacha20.Seek64(nonce, 0);
94+    std::byte expected_tag[EXPANSION];
95+    ComputeTag(m_chacha20, aad, cipher.first(plain.size()), expected_tag);
96+    if (timingsafe_bcmp(UCharCast(expected_tag), UCharCast(cipher.data() + plain.size()), EXPANSION)) return false;

achow101 commented at 7:05 pm on August 4, 2023:

In 9ff0768bdcca06836ccc673eacfa648e801930cb “crypto: add the ChaCha20Poly1305 AEAD as specified in RFC8439”

This could be made easier to read using cipher.last().

0    if (timingsafe_bcmp(UCharCast(expected_tag), UCharCast(cipher.last(EXPANSION).data()), EXPANSION)) return false;

stratospher commented at 7:02 am on August 13, 2023:

done in #28267.

in src/bip324.h:56 in 990f0f8da9 outdated

51+
52+    /** Retrieve our public key. */
53+    const EllSwiftPubKey& GetOurPubKey() const noexcept { return m_our_pubkey; }
54+
55+    /** Initialize when the other side's public key is received. Can only be called once. */
56+    void Initialize(const EllSwiftPubKey& their_pubkey, bool initiator) noexcept;

achow101 commented at 7:16 pm on August 4, 2023:

In 990f0f8da92a2d11828a7c05ca93bf0520b2a95e “Add BIP324Cipher, encapsulating key agreement, derivation, and stream/AEAD ciphers”

Could you add a comment explaining what the values for initiator mean?

stratospher commented at 7:03 am on August 13, 2023:

done in #28267.

in src/test/bip324_tests.cpp:137 in 1c7582ead6

135+        auto to_decrypt = ciphertext;
136+        if (error >= 2 && error <= 9) {
137+            to_decrypt[InsecureRandRange(to_decrypt.size())] ^= std::byte(1U << InsecureRandRange(8));
138+        }
139+
140+        // Decrypt length and resize ciphertext to accomodate.

stratospher commented at 9:04 am on August 5, 2023:

(micro nit) 1c7582e: s/accomodate/accommodate

stratospher commented at 7:03 am on August 13, 2023:

done in #28267.

stratospher commented at 9:29 am on August 10, 2023: contributor

tested ACK 1c7582e.

tested it using this branch which uses random inputs from FuzzedDataProvider to check whether the ciphertext produced by this PR and the python BIP code produce the same output.

I also liked the simpler current approach for streaming API changes. the interfaces of the cipher look more efficient and cleaner compared to the previous implementations!

fanquake commented at 9:58 am on August 10, 2023: member

We can track and deal with all remaining comments in one of the followup PRs.

fanquake merged this on Aug 10, 2023

fanquake closed this on Aug 10, 2023

sidhujag referenced this in commit 53844e6b59 on Aug 10, 2023

stratospher referenced this in commit d2ee2f39fe on Aug 13, 2023

stratospher commented at 7:00 am on August 13, 2023: contributor

we’d want fuzz tests for AEADChaCha20Poly1305 and FSChaCha20Poly1305 right? wrote one in #28263 and picked up some review suggestions from here in #28267 in case it helps.

stratospher referenced this in commit d22d5d925c on Aug 14, 2023

fanquake referenced this in commit 5606d7f5a8 on Aug 15, 2023

sidhujag referenced this in commit 012d3e68f1 on Aug 17, 2023

Retropex referenced this in commit 0e99d4e370 on Oct 4, 2023

Retropex referenced this in commit 5f62ed90f6 on Oct 4, 2023

kwvg referenced this in commit 60f86301ee on Feb 19, 2024

kwvg referenced this in commit e1acc63929 on Feb 20, 2024

kwvg referenced this in commit b74c6ffba8 on Feb 23, 2024

kwvg referenced this in commit c211b6f0a9 on Feb 24, 2024

kwvg referenced this in commit 6f752b9f34 on Feb 27, 2024

kwvg referenced this in commit f7e09b9417 on Feb 27, 2024

kwvg referenced this in commit d4233256f6 on Feb 29, 2024

kwvg referenced this in commit 5feb595d01 on Mar 5, 2024

kwvg referenced this in commit 1b1924e3d5 on Mar 5, 2024

PastaPastaPasta referenced this in commit e84e3d9c85 on Mar 6, 2024

fanquake referenced this in commit 1db0be8353 on Jul 16, 2024

bitcoin locked this on Dec 5, 2024

BIP324 ciphersuite #28008

Reviews

Conflicts