Score:0

Security level of Poly1305 and GMAC

eg flag

The Libsodium docs list the AEAD forgery limits for ChaCha20Poly1305 and AES-GCM which seems like a < 128-bit security level but says that it's not a practical concern. I've seen other people say Poly1305 has a 128-bit security level but haven't found much about the security level of either. There's also mixed information on the post-quantum security of both.

What's the security level of Poly1305 and GMAC? Are they post-quantum secure?

kelalaka avatar
in flag
Realted [Poly1305-AES vs AES-GCM](https://crypto.stackexchange.com/q/43112/18298). [Does GCM (or GHASH) only provide 64-bit security against forgeries?](https://crypto.stackexchange.com/q/67261/18298)
Score:2
my flag

I've seen other people say Poly1305 has a 128-bit security level but haven't found much about the security level of either.

Well, in terms of security level, there are two potential attacks:

  • One in which you attempt as an evesdropper to recover the secret key; the security of both Poly1305 and GMAC is essentially the same as the underlying block cipher.

  • One where you inject a forgery and hope you get lucky - in both cases, once you have find a forgery that gets accepted (and has a nonce that you have the valid tag for), you can deduce the internal $H$ value (and which would allow you to make changes for other messages as well). This has a somewhat less than 128 bits of security (assuming a 128 bit tag) for both - on the other hand, executing such an attack would require sending a lot of traffic to the receiver, and the receiver just might not be willing to put up with exabytes of invalid messages.

What's the security level of Poly1305 and GMAC? Are they post-quantum secure?

Well, it is known that if you can send entangled plaintext messages to Poly1305 (or GMAC), and get an entangled encrypted message, you can easily break either. On the other hand, I (and many others) find this an extremely exotic scenario, and one which is quite easy to avoid (in fact, we currently don't know how not to avoid it - that is, we don't know how to deliberately set up a system where the attack can be performed).

Apart from that rather exotic scenario, we're left with the same two attacks in the quantum realm as we had in the classical - we could try Grover's algorithm to attempt to break the underlying block cipher - however that's easy to defend - either use a 256 bit key there, or just note that using Grover's algorithm against a 128 bit is still extremely difficult...

eg flag
Thank you for this excellent answer!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.