So xChaCha20 has a nonce size large enough to safely use a random nonce with the same key. Poly1305 generally uses the first block of the cipher's output to generate its nonce. For xChaCha20 it would be the block zero for poly1305 key/nonce and the rest of the data would be encrypted with block 1 and up. So if one were to send a message you would get something along these lines (order may be different depending on the protocol):

$$\text{Msg} = \{ \text{Poly1305 Tag}\} \mathbin\| \{\text{24 Bytes Nonce} \} \mathbin\| \{ \text{Associated Data} \}\mathbin\| \{\text{Cipher Text} \}$$

Now with this layout, it seems a bit wasteful sending and generating new nonce with every message i.g. 24 bytes packet/message overhead, and CPU time generating random nonces. Especially since xChaCha20 can send $2^{64}$ blocks with one key and nonce pair. One could just send the nonce once and then start sending their stream of data and on the last message send the poly1305 tag. However, if it was a lot of data having to wait for all of it to be sent before verifying the poly1305 tag has its own host of problems. It seems more practical to generate Poly1305 tags as you go.

However, pretty much all constructions I see only use block 0 for the Poly1305 key/nonce it seems perfectly reasonable to me to use other block counters for the Poly1305 key. For instance, let's say someone wants to send a long stream of data. For illustrative purposes lets consider some rough construction that sends 7 xChaCha20 blocks at a time:

Example construction

Now, my question is why have I not seen a construction along these lines? Is there something I am overlooking, or is xChaCha20 just too new or this is a rather niche concern, or was I not looking hard enough? Since some construction along these lines allows one to verify data as they receive it and also avoids generating many new nonces and having to repeatedly send them adding message overhead.

Edit: Probably should have been more clear here poly1305_tag(block_x) is supposed to include both ciphertext and associated data. The image above was kinda already getting kinda wide for something like

$$poly1305_{tag}(block_x, \text{associated data} \mathbin\| ciphertext).$$

Similar as mentioned in the note below that xChaCha20_x() includes the key and nonce. Mainly this is question is about using other block counters other than zero to be a key for poly1305 to generate multiple tags for a longer data stream.

  • $\begingroup$ The Associated Data must be authenticated. Do you have a problem similar to this. $\endgroup$
    – kelalaka
    Commented Dec 25, 2021 at 12:43
  • $\begingroup$ Maybe I was not being clear enough the associated data is being ran through poly1305 at least that was my intention when describing this. Otherwise of course it could be manipulated. What I was saying above is that is running poly1305 with block number x as the poly1305 key. $\endgroup$
    – Keith
    Commented Dec 25, 2021 at 12:49
  • $\begingroup$ Also no it's more about using the different blocks to key the poly1305 authentication tag along the way. When I look at implementations they pretty just use block 0 of chacha20. I don't see reason why using other blocks output from chacha20/xchacha20 would cause a problem since poly1305 will keep getting unique inputs. That then you can use to generate a tag to authenticate the cipher text and any associated data. Basically same construction as what you normally do for block_0 and then encrypt block_1 to block_n, but instead your using multiple blocks from xchacha20 for multiple poly1305 tags $\endgroup$
    – Keith
    Commented Dec 25, 2021 at 13:07
  • $\begingroup$ You can edit your question clarify especially about your aim. The devil is in the details. $\endgroup$
    – kelalaka
    Commented Dec 25, 2021 at 14:32
  • $\begingroup$ Added an edit kinda summarizing what I said here. $\endgroup$
    – Keith
    Commented Dec 25, 2021 at 16:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.