Update ChaCha20 to RFC 8439?

Sjors commented at 2:39 pm on June 9, 2020: member

Our implementation of ChaCha20 is based on RFC 7539 which has been declared obsolete by RFC 8439.

For example the nonce changed from 64-bit to 96-bit:

Note also that the original ChaCha had a 64-bit nonce and 64-bit block count. We have modified this here to be more consistent with recommendations in Section 3.2 of [RFC5116]. This limits the use of a single (key,nonce) combination to 2^32 blocks, or 256 GB, but that is enough for most uses. In cases where a single key is used by multiple senders, it is important to make sure that they don’t use the same nonces. This can be assured by partitioning the nonce space so that the first 32 bits are unique per sender, while the other 64 bits come from a counter.

I have no idea if any of the changes are really material.

Given that we plan to use ChaCha20 in MuHash3072 (#19055), if we ever want to write an RFC for that, we should probably use the new version of ChaCha20.

This is also relevant for the BIP-151 followup, which appears also to based on RFC 7539. Since the original BIP151 is withdrawn and its replacement hasn’t been proposed, it’s not too late to change that. RFC 8439 also defines ChaCha20-Poly1305, at minimum the test vectors seem different.

RFC 8439 has some errata:

bug in Poly1305 pseudo code (2.5.1)
bug in ChaCha20 pseudo code (2.4.1)
remarks about constant-timeness for Poly1305

Sjors commented at 2:39 pm on June 9, 2020: member

cc @sipa, @fjahr, @jonasschnelli

jonasschnelli commented at 8:00 pm on June 9, 2020: contributor

For example the nonce changed from 64-bit to 96-bit: I have no idea if any of the changes are really material.

AFAIK not for our use case. We can fairly control the sequence numbers and can make sure that nonce-reuses under the same key will not happen.

Reading RFC 8439, it looks like they have reduced the block counter from 64 to 32 bits and use now word 13 (which before was the upper 32bit of the 64bit counter) to extend the nonce from 64 to 96 bits.

Given that we plan to use ChaCha20 in MuHash3072 (#19055), if we ever want to write an RFC for that, we should probably use the new version of ChaCha20.

AFAIK, #19055 uses only the keystream part (CPRNG) of ChaCha20 (similar to our FastRandomContext). Shouldn’t be a problem at all (it keeps the counter/nonce always 0).

This is also relevant for the BIP-151 followup, which appears also to based on RFC 7539. Since the original BIP151 is withdrawn and its replacement hasn’t been proposed, it’s not too late to change that. RFC 8439 also defines ChaCha20-Poly1305, at minimum the test vectors seem different.

For BIP324, I don’t think RFC 8439 matters. In BIP324, it’s mandatory to not crypt more than 1GB of data under the same key which should be far enough to never hit a nonce reuse (with 64bit nonces).

As for the AEAD construction (ChaCha20-Poly1305), BIP324 uses a slightly modified and for our use-case optimised AEAD (ChaCha20-Poly1305@Bitcoin) which is almost identical to the openSSH version ChaCha20-Poly1305@OpenSSH (which is widely used since a while). The test vectors of RFC8439 won’t match therefore.

However, the code implementation should be very carefully reviewed so that nonce/key reuse is not possible (regardless of its 64 or 96bit).

Maybe ideally @sipa or @real-or-random could drop a comment here.

real-or-random commented at 9:00 am on June 10, 2020: contributor

Our implementation of ChaCha20 is based on RFC 7539 which has been declared obsolete by RFC 8439.

For example the nonce changed from 64-bit to 96-bit:

This is not true, ChaCha20 as specified in RFC 7539 already had a 96-bit nonce and a 32-bit counter. It’s however true that ChaCha20-IETF (as in the RFCs) differs from the ChaCha20 proposal by Bernstein. All of this has already created confusion in the past, see https://en.wikipedia.org/wiki/Salsa20#ChaCha20_adoption .

In the end, all of this does not really matter as long as the counter does not overflow. It matters mostly for interoperability. But I think the reasoning given in the RFCs in not very relevant for us. They want 96-bit nonces for compabitility: RFC5116, which defines a generic AEAD API, recommends 96-bit nonces.

AFAIK, #19055 uses only the keystream part (CPRNG) of ChaCha20 (similar to our FastRandomContext). Shouldn’t be a problem at all (it keeps the counter/nonce always 0).

Maybe there’s a misconception here. ChaCha20 is basically just a CPRNG, there are no parts other than the keystream part (=stream of pseudorandom bytes, internally created in blocks of 64 bytes). You can use ChaCha20 as a stream cipher then, to encrypt and decrypt but this operation is then simply XORing the stream of pseudorandom bytes to the message. I have no idea about MuHash, but one of (counter, nonce) those should change if you derive more than 64 pseudorandom bytes (= more than one block but as I said, this is internally handled by ChaCha20).

dhruv commented at 8:30 pm on August 5, 2022: contributor

The new BIP324 working draft (pending release) uses RFC8439 and #25361 adds that support into our implementation. #25354 also fixes a bug (inefficiency, not correctness) in our ChaCha20 implementation. I think we can close this issue?

real-or-random commented at 9:54 pm on August 5, 2022: contributor

I think we can close this issue?

Yes, it can be closed, independently of the two mentioned PRs. There are no algorithmic changes between RFC 7540 and RFC 8439. Quoting the latter:

RFC 7539, the predecessor of this document, was meant to serve as a stable reference and an implementation guide. It was a product of the Crypto Forum Research Group (CFRG). This document merges the errata filed against RFC 7539 and adds a little text to the Security Considerations section.

fanquake closed this on Aug 5, 2022

achow101 referenced this in commit b4794740f8 on Jul 12, 2023

sipa commented at 7:19 pm on July 12, 2023: member

For posterity, this has been fully addressed by #27985.

sidhujag referenced this in commit 4adf185bcf on Jul 12, 2023

bitcoin locked this on Jul 11, 2024

Update ChaCha20 to RFC 8439? #19225