1
$\begingroup$

The xChaCha cipher detailed here extends the nonce 192bits and works as follows (from the link):

  1. Pass the key and the first 16 bytes of the 24-byte nonce to HChaCha20 to obtain the subkey.
  2. Use the subkey and remaining 8 byte nonce with ChaCha20 as normal (prefixed by 4 NUL bytes, since [RFC8439] specifies a 12-byte nonce).

My question is could we encrypt the 2nd part of the nonce by running an additional initial round (HChaCha20) with the 16 bytes of the nonce and the key?

We could use one of the two parts of the nonce as a counter by incrementing them, given they occupy the usual counter slots. I suppose the same question applies to XSalsa20.

I presume this would compromise something somewhere. It seems like a very simple and cheap way to make a brute force more difficult. The additional round(s) would take about 10ms.

EDIT - hopefully the below makes the idea (somewhat) clearer. My impoverished code is in javascript.

Note: HChaCha20 is initialized the same way as the ChaCha cipher, except that HChaCha20 uses a 128-bit nonce and has no counter. Instead, the block counter is replaced by the first 32 bits of the nonce.

//Encrypt
 subkey = hchacha20(key, nonce[0:15]);
 nonce[0]+=1; //or any part which occupies the usual counter block, nonce[0-4]?
 subkey2 = hchacha20(key, nonce[0:15]);
 nonce[0]-=1; //or..etc  
 subnonce = subkey2 ^ nonce[16:23]; 
 chacha20_nonce = "\x00\x00\x00\x00" + nonce[16:23];
 //Run ChaCha20 
 output = ciphertext + nonce[0:15] + subnonce);
 


//Decrypt    
 subkey = hchacha20(key, nonce[0:15]);
  nonce[0]+=1; //or any part which occupies the usual counter block, nonce[0-4]?
 subkey2 = hchacha20(key, nonce[0:15]); 
 subnonce = subkey2 ^ nonce[16:23]; 
 chacha20_nonce = "\x00\x00\x00\x00" + subnonce;
 //Run ChaCha20 
 output = plaintext;
$\endgroup$
2
  • 1
    $\begingroup$ This still doesn't differ, you still need to transform all of the nonces to the other side. This is still not an improvement over the brute-force. $\endgroup$
    – kelalaka
    Nov 7 '20 at 8:23
  • 1
    $\begingroup$ @kelalaka Yes I see now. The attacker still just needs to brute force 128 bits of key!! I can see now why you thought I was trying to randomise the nonce because encrypting part of it essentially does nothing. Thank you again for putting up with my dense question. $\endgroup$
    – Modal Nest
    Nov 7 '20 at 9:40
1
$\begingroup$

First the XChaCha20-Poly1305 basics

  • Why one may need XChaCha20

    ChaCha20 is 20 round from the ChaCha family. The Bernstein version of ChaChax has a 64-bit nonce and 64 bit counter. Bernstein argued that this should be enough in the XSalsa paper

    There is a standard argument that a 64-bit nonce is long enough. Nonce security does not mean unpredictability; it means uniqueness. Applications can generate a nonce as a monotonic timestamp or simply a counter 1,2,3,...

    For long-lived keys, the 64-bit nonce of ChaCa20 is too short to use securely since with the birthday attack around the 2^32 messages one will have 50% of hitting the same random nonce that will at least result in the loss of the confidentiality.

    XChaCha20 is based on the IETF version that uses 96-bit nonces.

  • The security of ChaCha20-Poly1305 with random nonces

    The ietf' docs say that after around $2^{96}$ messages one should expect a collision with the birthday attack. 50% is very advantageous for the attacker and a more conservative one is generating at most $2^{80}$ nonce so that the collision probability is $\frac{1}{2^{32}}$. And, still, this $2^{80}$ message under one key should be enough for all. Therefore, the XChaCha20 is safe to use with random nonces. The security reduced to the security of the ChaCha20-Poly1305

  • How the ChaCha20-Poly1305 works

    • The 128-bit key and the first 128-bit (16-byte) of the uniform random nonce is processed with the HChaCha20
    • The HChaCha20 returns two 128 bits.
    • The remaining 64-bit ( 8-byte) of the nonce is appended with 4 null bytes.
      xchacha20_encrypt(key, nonce, plaintext, blk_ctr = 0):
           subkey = hchacha20(key, nonce[0:15])
           chacha20_nonce = "\x00\x00\x00\x00" + nonce[16:23]
      
           return chacha20_encrypt(subkey, chacha20_nonce, plaintext, blk_ctr)
      

Back to Questions

My question is could we encrypt the 2nd part of the nonce by running an additional initial round (HChaCha20) with the 16 bytes of the nonce and the key?

I'm reading this like this

```
xchacha20_encrypt(key, nonce, plaintext, blk_ctr = 0):
     subkey = hchacha20(key, nonce[0:15])
     subNonce = hchacha20(key + nonce[0:15], nonce[16:23])
     chacha20_nonce = "\x00\x00\x00\x00" + subNonce
     return chacha20_encrypt(subkey, chacha20_nonce, plaintext, blk_ctr)
```

To decrypt the other side must follow the same steps since they are not reversible! Therefore you need to send the nonce[16:23] as it is.

Therefore is no need for this since we expect that the nonce is generated uniform randomly. If you want to really do it, you can, you will get no advantage on the brute-force side. The attacker will still need to search over 128-bit. As a result, this adds nothing at all to the security.

I presume this would compromise something somewhere. It seems like a very simple and cheap way to make a brute force more difficult. The additional round(s) would take about 10ms.

It doesn't compromise anything at all but also doesn't provide any at all in the security of the XChaCha20-Poly1305. The brute-force attack, as mentioned above, will still need for a 128-bit key search.

$\endgroup$
7
  • $\begingroup$ I know the nonce is random. To be clear, I'm suggesting to encrypt the final 8 bytes of the nonce but use the original (unencrypted 8 bytes) to run the cipher. On the other side decryption would only require the 16bits of the nonce (and key) to decrypt the other 8 bits of the nonce. $\endgroup$
    – Modal Nest
    Nov 5 '20 at 18:01
  • $\begingroup$ There is a good reason to separate them, the first part is used to randomize the key. $\endgroup$
    – kelalaka
    Nov 5 '20 at 18:04
  • $\begingroup$ @kelalka Separate what? I am suggesting to encrypt the part of the nonce that isn't used to randomise the key, with the part that is used to randomise the key. I have said nothing about combining any separate processes into one. I am not suggesting to combine the nonce. In fact, I am suggesting running an extra hChaCha round which would further separate the two parts of the nonce. $\endgroup$
    – Modal Nest
    Nov 5 '20 at 22:14
  • $\begingroup$ nonce[0:15] is used to randomize the key, nonce[16:23] is used as nonce. The nonce should be already generated uniform randomly, so each bit of the nonce is already expected to be parted... $\endgroup$
    – kelalaka
    Nov 5 '20 at 22:24
  • $\begingroup$ I know, and I know the nonce is random. I've not suggested anything to do with randomness of the nonce. I am suggesting to use nonce [0,15] to randomize the key as normal, then run a 2nd round with the nonce [0,15] to encrypt the actual nonce [16,23]. Then run through the encryption with the actual nonce as normal. Apologies if I am not being clear, but I am simply suggesting to encrypt the nonce [16,23] with an additional 'key randomization' round using the nonce [0,15] again but with one of the nonce bytes incremented by '1', as they occupy the 'counter' blocks. $\endgroup$
    – Modal Nest
    Nov 5 '20 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.