ChaCha matrix - tests for original implementation not passing due to bad counter encoding?

Question

Hello everyone and already thanks for taking your time to read this!

I am currently implementing ChaCha20 (256-bit key) for my bachelor thesis. I know that there are two version of ChaCha out there; the version used in IETF protocols and the one with the original design by DJB.

As far as I understood, the only difference should be that the original has a 64-bit nonce and a 64-bit counter while the other has a 96-bit nonce and a 32-bit counter.

I have taken this information from section 2.3 of RFC7539:

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.

Further down the section, the following ChaCha state matrix is shown which clarifies the usage of a 32-bit counter and a 96-bit nonce:

cccccccc  cccccccc  cccccccc  cccccccc
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
bbbbbbbb  nnnnnnnn  nnnnnnnn  nnnnnnnn

c=constant k=key b=blockcount n=nonce

I have used the test vectors in section 2.3.2 of the same paper to successfully verify my implementation of the block function:

Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13:14:15:16:17:18:19:1a:1b:1c:1d:1e:1f
Nonce = (00:00:00:09:00:00:00:4a:00:00:00:00)
Block Count = 1

Since the key, the counter and the nonce are unequal 0 and the tests passed, I can say that my encoding of the numbers is very likely to be correct. I have encoded all of them (including the constants) as little-endian except the counter since this is how the state before the block function should look like as described in the same section:

After setting up the ChaCha state, it looks like this:

ChaCha state with the key setup.

   61707865  3320646e  79622d32  6b206574
   03020100  07060504  0b0a0908  0f0e0d0c
   13121110  17161514  1b1a1918  1f1e1d1c
   00000001  09000000  4a000000  00000000

I have then went on and also used the test vectors for the encryption of a message in section 2.4.2 with which I could also successfully verify my implementation thus I am pretty sure that my implementation is correct according to the IETF version.

Now I also wanted to implement the original version by DJB. Since I assumed that only the counter and nonce size changed, I thought this would be pretty straightforward. I have used this test vectors taken from here:

Key:    0xc4 0x6e 0xc1 0xb1 0x8c 0xe8 0xa8 0x78
        0x72 0x5a 0x37 0xe7 0x80 0xdf 0xb7 0x35
        0x1f 0x68 0xed 0x2e 0x19 0x4c 0x79 0xfb
        0xc6 0xae 0xbe 0xe1 0xa6 0x67 0x97 0x5d
IV:     0x1a 0xda 0x31 0xd5 0xcf 0x68 0x82 0x21
Rounds: 20

Keystream block 1:
0xf6 0x3a 0x89 0xb7 0x5c 0x22 0x71 0xf9
0x36 0x88 0x16 0x54 0x2b 0xa5 0x2f 0x06
0xed 0x49 0x24 0x17 0x92 0x30 0x2b 0x00
0xb5 0xe8 0xf8 0x0a 0xe9 0xa4 0x73 0xaf
0xc2 0x5b 0x21 0x8f 0x51 0x9a 0xf0 0xfd
0xd4 0x06 0x36 0x2e 0x8d 0x69 0xde 0x7f
0x54 0xc6 0x04 0xa6 0xe0 0x0f 0x35 0x3f
0x11 0x0f 0x77 0x1b 0xdc 0xa8 0xab 0x92

Keystream block 2:
0xe5 0xfb 0xc3 0x4e 0x60 0xa1 0xd9 0xa9
0xdb 0x17 0x34 0x5b 0x0a 0x40 0x27 0x36
0x85 0x3b 0xf9 0x10 0xb0 0x60 0xbd 0xf1
0xf8 0x97 0xb6 0x29 0x0f 0x01 0xd1 0x38
0xae 0x2c 0x4c 0x90 0x22 0x5b 0xa9 0xea
0x14 0xd5 0x18 0xf5 0x59 0x29 0xde 0xa0
0x98 0xca 0x7a 0x6c 0xcf 0xe6 0x12 0x27
0x05 0x3c 0x84 0xe4 0x9a 0x4a 0x33 0x32

Since the IV is 64-bit, I am assuming that this are indeed test vectors for the original ChaCha implementation.

Now my problem is (almost exactly as with my other question 2 weeks ago) that I can reproduce the first key block with counter set to 0 but not the second one (counter set to 1). Since I could pass the test for the first key block (and all other tests where the counter is set to 0), I am assuming that my encoding for everything except for the counter is correct.

Thus my question is: What is the correct encoding of the counter in the original implementation of ChaCha?

I have tried writing it in little-endian with no success.

Something other confusing to me is - which I mention here because it may have something to do with my counter problem - that in the ChaCha specification of DJB, following is said:

There are three differences in the details [in contrast to Salsa20]. First, ChaCha permutes the order of words in the output block to match the permutation described above. [...] Second, ChaCha builds the initial matrix with all attacker-controlled input words at the bottom:

constant constant constant constant
key      key      key      key
key      key      key      key
input    input    input    input

The key words are simply copied in order; the input words are the block counter followed by the nonce; the constants are the same as in Salsa20.

Since it is said that the "key words are simply copied in order", I would have assumed that it must be in big-endian since that is the order one would read the key; but my tests are passing for the counter set to 0 with key != 0 in little-endian (same for the nonce) so I assume that I am just misunderstanding this and he actually means that everything is written in little-endian? (Which didn't work for me with counter != 0 as mentioned above.)

Answer 1

I have finally solved my problem:

I needed to transform the counter into little-endian, then split it it into 4 byte chunks, formatting each chunk again as little-endian:

1. 00:00:00:00:00:00:00:01 ("raw" counter value)
2. 01:00:00:00:00:00:00:00 (as little-endian)
3. 01:00:00:00 00:00:00:00 (split into 4 byte chunks)
4. 00:00:00:01 00:00:00:00 (each chunk as little-endian)

Maybe this will help somebody in the future.