# ChaCha cipher + Poly1305

The Poly1305-AES paper summarizes the MAC as

$$\mathrm{Poly1305}(m, \mathrm{AES}_k(n)) = {H_r(m) + \mathrm{AES}_k(n)} \mod 2^{128}$$

Can I presume that $+$ here is just meant as a form of 16-byte mixing $H_r(m)$ and $\mathrm{AES}_k(n)$, and that XOR would be equally effective (since both already are 16 bytes)?

Now following from that, if I were to use Poly1305-ChaCha, could I simply append $H_r(m)$ to the plaintext and XOR it with the cipherstream just like regular plaintext? Because the cipherstream is already a function of the key and the nonce this seems safe.

-
Just look at salsa20-poly1305 in nacl and do the same thing with chacha. Or just use nacl. The advantage of chacha over salsa is minor. – CodesInChaos Mar 7 '13 at 21:00

To answer your original question: no, you can't presume that you can replace the addition mod $2^{128}$ within $Poly1305$ with XOR, and not change the security properties (at least, not without some serious analysis).

The security of the MAC depends on the fact that, given any two distinct messages $M_1$ and $M_2$, and any integer $\Delta$, then the following is true only for a limited number of values of $r$:

$H_r(M_1) - H_r(M_2) \equiv \Delta\bmod 2^{128}$

In other words, if you treat this as an equation in one unknown $r$, then there is only a small set of solutions, no matter that $M_1$, $M_2$ and $\Delta$ are (assuming $M_1 \neq M_2$)

If you replace the addition in $Poly1305$ with exclusive or, then the corresponding relationship would be:

$H_r(M_1) \oplus H_r(M_2) = \Delta$

It may be the case that one might be able to find clever values of $M_1$, $M_2$ and $\Delta$ where this holds for a number of values of $r$; if this is possible, then this would cut severely into the security properties.

Now, it is possible that this altered equation also has a bounded number of solutions in $r$; unless someone does some analysis and shows that, it seems unwise to trust it.

-
I don't think this is correct (I might be wrong though). The security proof works by proving that $H_r(m) = H_r(m') + g$ is rare, by finding an upper limit. Using the $H_r(m)$ building block the $Poly1305$ function is defined, but changes to $Poly1305$ do not affect the security proof of $H_r$. The idea that using XOR in the Poly1305 function would suddenly mean that the underlying $H_r$ proof also must use XOR eludes my understanding. – orlp Mar 8 '13 at 4:26
@nightcracker: well, if you change $Poly1305$ to be $Poly1305'(m, AES_k(n)) = H_r(m) \oplus AES_k(n)$, that means that the original security proof on $H_r(m)$ is irrelevant. Look at it this was; suppose we did know values $m$, $m'$ and $\Delta$ so that $H_r(M_1) \oplus H_r(M_2) = \Delta$ for half the possible $r$ values. What that means is that if you learn the value $Poly1305'(M_1, n)$, you have a good guess for $Poly1305'(M_2, n)$, namely, $Poly1305'(M_1, n) \oplus \Delta$. Hence, you need to prove that relation holds with small probability. – poncho Mar 8 '13 at 5:17
Thank you for your explanation. – orlp Mar 8 '13 at 14:06

I'll follow CodesInChaos's advice. Just for reference, this is what NaCl does (the paper is rather confusing on this):

1. Expand the key with the 24 byte nonce into the regular XSalsa20 cipherstream (though it does seem to use some strange key expansion using HSalsa with a 0 nonce as a first step, I have no idea why).
2. Take the first 16 bytes of the cipherstream as $r$, the next 16 bytes as $c$.
3. The authenticator of the message is $H_r(m) + c \mod 2 ^ {128}$, the encrypted message is $m$ XOR'ed with the rest of the cipherstream.
-
HSalsa is used to turn Salsa20 (8-byte nonce) into XSalsa20 (24-byte nonce) as per "Extending the Salsa20 nonce" paper: cr.yp.to/snuffle/xsalsa-20081128.pdf – dchest Mar 8 '13 at 9:29
@dchest: yes, but what I'm referring to in my answer as "strange key expansion" is the difference between NaCl and XSalsa20 in the paper. XSalsa20 is defined as $Salsa(HSalsa(key, n1), n2)$ if you split up the 24-byte nonce into 16 bytes (n1) and 8 bytes (n2). However, NaCl does something else: $Salsa(HSalsa(HSalsa(key, 0), n1), n2)$. There's no explanation for this in the paper, hence I referred to it as "some strange key expansion". – orlp Mar 8 '13 at 13:58
I think you're referring to hashing the result of DH. djb says you should hash the result of curve25519 scalar multiplication before using it ("Both of you can then hash this shared secret and use the result as a key for, e.g., Poly1305-AES." cr.yp.to/ecdh.html), so crypto_box uses HSalsa as a hash function for shared key. Crypto_secretbox doesn't have this step. – dchest Mar 9 '13 at 9:28
@nightcracker I recommend splitting your implementation into two parts. 1) KeyExchange aka. crypto_box_beforenm which is Hash(scalarMult(b,A)) with HSalsa as the default hash 2) AuthenticatedEncryption aka. crypto_secret_box or crypto_box_afternm which is Salsa20(HSalsa20(key, n1), n2) – CodesInChaos Mar 9 '13 at 10:08
@dchest: ah I see, that explains it - thanks. – orlp Mar 9 '13 at 11:15