Is Salsa20+Poly1305 an AEAD?

Question

I see Chacha20Poly1305, XsalsaPoly1305 and AES GCM usually used and mentioned in literature and implementations as AEAD cyphers. My question is that Poly1305 provides authentication and Salsa20 provides encryption, a combination of both can be considered AEAD or not? Even though it is not a standard, does it technically fit the definition of an AEAD?

Answer 1

Yes, it can be implemented as an AEAD cipher, although the common definition uses ChaCha20 instead. ChaCha is a cipher with slightly better diffusion and better performance characteristics; both ciphers are by Daniel Bernstein. If you want to use Salsa instead, then just replace ChaCha20 with Salsa20 - but I would rather not do that.

ChaCha20 / Poly1305 is for instance implemented in a TLS 1.3 cipher suite, which references RFC 8439: ChaCha20 and Poly1305 for IETF Protocols, section 2.8, which defines AEAD_CHACHA20_POLY1305. A well used RFC is a clear indication of standardization.

Answer 2

Of course, it's used as an AEAD !

AEAD stands for Authenticated Encryption with Associated Data

It gives confidentiality as well as authenticity to your encryption, which simply means that the data is encrypted and that no one can alter any bit of your data. The alteration if done will be detected during verification.

ChaCha, Salsa, including their eXtended nonce versions are all stream ciphers and Poly1305 is the authentication mechanism that provides integrity to the data encrypted along with the unencrypted associated data.

ChaCha/Salsa are based on Add Rotate Xor permutation which are CPU friendly, and much like hash functions after the 20 recommended rounds of mixing, the mixed state is added ( $mod \ 2^{32}$ )with the initial state to get the output state. This construction makes it irreversible and there are no known attacks as of now.

They both along with Poly1305 message authentication code were invented by the famous cryptographer Daniel J Bernstein (also known as DJB) , who also invented the famous X25519 crypto system using Curve25519 for ECDH. The two stream ciphers were submitted to the eSTREAM competition, and they have stood the test of time as of now. Even companies like Google have incorporated Chacha20-Poly1305 for their implementation of TLS. They are even using it in their disk encryption project Adiantum Now, why ? It's because both Salsa and ChaCha are resistant to side channel attacks and very easy to implement in software. Further with a 64 bit counter you can encrypt 1 Zettabyte of data securely . But if you use Poly1305 along with it you can only authenticate upto $2^{64}$ bytes ~ 16000 Peta Bytes. But if you use AES GCM you are only limited up to approximately 64 GB of encryption with authentication with the same key and the standard only provides a 96 bit nonce! Further, AES is very slow, if implemented purely in software without hardware acceleration and also prone to cache timing attacks if implemented with lookup tables.

• It's always recommended to use 20 rounds XChaCha/XSalsa with Poly1305. Using the eXtended nonce version is much better because you can use random nonce from a high entropy source.

• With ChaCha/Salsa encryption is parallelisable, same case with Poly1305, authentication is also parallelisable.

• Poly1305 calculates a 16 byte authentication tag for your message based on your secret key . This tag is recalculated by the recepient of the message who knows the secret key and verifies the received data before decryption. It's highly recommended to use a MAC like Poly1305 with ChaCha/Salsa because data encrypted with stream ciphers are subject to malicious bit flip attacks.

• ChaCha20 provides more diffusion than Salsa20.

• Bernstein himself authored Xsalsa20, and based on XSalsa20 's design S. Arciszewski made XChaCha20

• The security of Poly1305 depends on the underlying cipher. Initially Bernstein proposed AES - Poly1305 because AES was popular at that time,

if AES is secure AES -Poly1305 is also secure and from that it follows that if Chacha20/ Salsa20 is secure then Chacha20/Salsa20 Poly1305 is also secure ! Therefore you can use any secure underlying cipher with Poly1305 ! How awesome is that !? See : https://www.google.com/url?sa=t&source=web&rct=j&url=https://cr.yp.to/mac/poly1305-20050329.pdf&ved=2ahUKEwj0ye6uqsfoAhUZxTgGHYz0C3MQFjABegQIBBAC&usg=AOvVaw0k5Ix8nCShQGuBM6QbEAoD

See more info for XChaCha20 poly1305 IETF (32 bit counter): https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-xchacha-03

See Google's blog post on using Chacha20 Poly1305: https://security.googleblog.com/2014/04/speeding-up-and-strengthening-https.html?m=1

Google's Adiantum (for disk encryption uses XChaCha20 poly1305): https://security.googleblog.com/2019/02/introducing-adiantum-encryption-for.html?m=1

Daniel J Bernstein's original paper on XSalsa20 : https://www.google.com/url?sa=t&source=web&rct=j&url=https://cr.yp.to/snuffle/xsalsa-20081128.pdf&ved=2ahUKEwiB2ff7o8foAhVRzDgGHW9BCG0QFjADegQIAxAB&usg=AOvVaw3pfOfep6cl9gtvXr-xP9I4

Wikipedia page for more information about the original Chacha20 and Salsa20 : https://en.m.wikipedia.org/wiki/Salsa20

Answer 3

My question is that Poly1305 provide authentication and Salsa20 provides encryption, a combination of both can be considered AEAD or not?

There are many ways you could combine both, some are AEADs and some are not. For example:

• RFC 8439 ("ChaCha20 and Poly1305 for IETF Protocols") specifies a combination of ChaCha20 and Poly1305 that is an AEAD. You could combine Salsa20 with Poly1305 in an exactly analogous way and you'd get an AEAD as well.
• The NaCl library and its more popular derivative Libsodium implement a combination of XSalsa20 (a Salsa20 variant) that provides authenticated encryption, but without associated data. So it's an AE but not an AEAD.
• If you "roll your own" it would be very easy to, for example, end up with a flawed combination where an adversary can combine authentic AD and Salsa20 output with a false nonce and the honest parties will not detect it. (The RFC 7539 construction avoids this by deriving a one-time MAC key for each cipher key + nonce pair; another approach would be to incorporate the cipher nonce into the MAC input).

So the answer to your question is yes, but only if the combination is correct.

Answer 4

There is not a clear cut answer. The whole point of "pure" AEAD algorithms like GCM is to avoid all the pitfalls in manually combining a encryption algorithm with a MAC. (It calso also be argued that GCM is simply a combination of CTR with GMAC)

However, it also makes sense to standardize a combination of those, like Salsa20 + Poly1305. As long as the combination itself is well specified (say in a RFC or some standard), then those pitfalls are also avoided.