4
$\begingroup$

I need to encrypt some packets on a constrained hardware.

I was enthusiast about the NaCl suit, since Chacha/Salsa20 is a nice and fast symmetric cipher algorithm when no AES-NI instructions is available. But I discovered that poly1305 (the authentication layer) is based on AES!

Why? If I plan to use cryptobox it's because there is no AES; but if AES is available in hardware, may I prefer AES-GCM?

What is the logic behind this? Why poly1305-AES and not poly1305-Salsa20?

$\endgroup$
3
  • 1
    $\begingroup$ Are you sure that NaCl uses poly-1305 with AES and not with Salsa20? $\endgroup$
    – SEJPM
    Commented Sep 13, 2016 at 14:24
  • $\begingroup$ indeed i can't prove it, since the initial paper was about poly1305-AES, I guessed NaCl did use it... I may be wrong... (it may use xsalsa20 according to this : cr.yp.to/highspeed/naclcrypto-20090310.pdf) $\endgroup$
    – yota
    Commented Sep 13, 2016 at 14:56
  • $\begingroup$ From the website: crypto_box is curve25519xsalsa20poly1305, a particular combination of Curve25519, Salsa20, and Poly1305 specified in Cryptography in NaCl. crypto_secretbox is crypto_secretbox_xsalsa20poly1305, a particular combination of Salsa20 and Poly1305. $\endgroup$ Commented Aug 1, 2022 at 18:00

1 Answer 1

4
$\begingroup$

Why poly1305-AES and not poly1305-Salsa20?

You misunderstand. Poly1305-AES has always been defined in terms of an underlying Poly1305 function combined with AES:

$\text{Poly1305}_r(m, \text{AES}_k(n))$, the Poly1305-AES authenticator of a message $m$ with nonce $n$ under secret key $(k, r)$, is defined as the 16-byte unsigned little-endian representation of $$\left(\left(\left(c_{1}r^q + c_{2}r^{q−1} + \cdots + c_{q}r^1\right) \text{mod } 2^{130} − 5\right) + \text{AES}_k(n)\right) \text{mod } 2^{128}$$ [definition of $c = f(m)$ omitted for brevity]

As you can see, under this definition, AES is:

  • Not being computed inside of the function; rather, its output is being fed into $\text{Poly1305}_r$ as an argument

  • Trivially replaceable by any other cipher

  • Only being run on a single nonce, not the whole message

  • Clearly doing nothing but whitening this single per-message nonce anyway

So performance shouldn't be an issue. If you are on an embedded system with no dedicated cryptography instructions and need to do AEAD on a 10-gigabyte $m$, even a reference implementation of Poly1305-AES would only have to "inefficiently" crunch $n$ once. (This would become a problem when processing many individual messages; see below for why this isn't an issue in practice.)


The IETF definition of the underlying Poly1305 function doesn't even bother expressing whitening preferences against the nonce, instead just demanding a "one-time key" per se, and leaving it up to the caller to ensure uniqueness:

Poly1305 takes a 32-byte, one-time key and a message and produces a 16-byte tag that authenticates the message such that an attacker has a negligible chance of producing a valid tag for a inauthentic message.

The first 16 bytes of the one-time key form an integer, $r$, as follows: the top four bits of the bytes at indexes 3, 7, 11 and 15 are cleared, the bottom 2 bits of the bytes at indexes 4, 8 and 12 are cleared and the 16 bytes are taken as a little-endian value.

An accumulator is set to zero and, for each chunk of 16 bytes from the input message, a byte with value $1$ is appended and the 17 bytes are treated as a little-endian number. If the last chunk has less than 16 bytes then zero bytes are appended after the $1$ until there are 17 bytes. The value is added to the accumulator and then the accumulator is multiplied by $r$, all $\text{mod } 2^{130} - 5$.

Finally the last 16 bytes of the one-time key are treated as a little-endian number and added to the accumulator, $\text{mod } 2^{128}$. The result is serialised as a little-endian number, producing the 16 byte tag.


In fact, "in the real world", AES is generally replaced with the in-use stream cipher in non-AES AE(AD) constructions. Both TLS’ AEAD_CHACHA20_POLY1305, and (relevantly to your question as-stated) crypto_box’s default mode of x25519+ChaCha20-Poly1305 (Libsodium’s documentation) internally use the message cipher’s hash function for preprocessing the nonce into the key for Poly1305.

So you aren't actually using AES for Poly1305 key preprocessing in this case (though, even if you were, it wouldn't actually be a performance issue; the only real threat would be its making your cryptosystem vulnerable to two different ciphers’ future breakages vs. just one).

$\endgroup$
0

Your Answer

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

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