2
$\begingroup$

Everything I've seen so far in modern implementations (the Linux Kernel AEAD API, JVM crypto provider (AES-GCM), RFC 8439, libsodium, etc) seems to imply that only symmetric key block ciphers are used in practice for AEAD. Are there asymmetric key algorithms that ensure authenticated encryption?

$\endgroup$
8
$\begingroup$

When people say "AEAD", they have symmetric schemes in mind. But conceptually, authenticated encryption is not restricted to symmetric keys. It is just the case that public key variants have not received much attention both in the literature and in practice. But there are implementations. For example, NaCl has an API for public-key authenticated encryption, based on security notions by Jee Hea An 2001. The construction is based on public-key encryption and MACs. This shows that AE in the asymmetric setting is fundamentally different from simply signing encrypted messages, as explained in the NaCL API docs:

The crypto_box function is not meant to provide non-repudiation. On the contrary: the crypto_box function guarantees repudiability. A receiver can freely modify a boxed message, and therefore cannot convince third parties that this particular message came from the sender. The sender and receiver are nevertheless protected against forgeries by other parties. In the terminology of https://groups.google.com/group/sci.crypt/msg/ec5c18b23b11d82c, crypto_box uses "public-key authenticators" rather than "public-key signatures."

Users who want public verifiability (or receiver-assisted public verifiability) should instead use signatures (or signcryption).

Apparently this API and the formalization in the paper do not include the "additional data" (AD) part of AEAD but I don't think there is a fundamental limitation. AEAD as a single primitive in the symmetric setting became popular only after 2001, so I believe Jee Hea An simply didn't think about "additional data" as a useful feature back in 2001.

I can only speculate but I believe one reason why authenticated public-key encryption has not received much attention is that (even unauthenticated) public-key encryption itself is a rarely used primitive. Public-key encryption is useful in a setting where the sender and the receiver are not online at the same time. The prominent example is e-mail encryption but unfortunately e-mail encryption never took off for various reasons (Johnny Still, Still Can't Encrypt), and protocols for e-mail security such as PGP/GPG and S/MIME conceptually separate confidentiality and authentication and implement them via public-key encryption and digital signatures (and not MACs!). Of course these can be combined ("sign-then-encrypt", "encrypt-then-sign" or "encrypt-and-sign") but the responsibility for doing so correctly is mostly pushed down to the user, and the 2001 paper shows that all of these constructions are insufficient. (One reason why PGP and S/MIME wanted signatures explicitly is that you can still have authentication for public emails, e.g., posts to public mailing lists.)

The success of the idea that we should consider authenticated encryption as single primitive with a single misuse-resistant API whose users do no need to be cryptography experts came only later in the symmetric setting after people screwed up in endless ways with constructions like "encrypt-then-MAC", "MAC-then-encrypt", "encrypt-and-MAC", which are the symmetric counterparts to the modes mentioned above. Note however that the symmetric and asymmetric settings are hard to compare when it comes to authentication, e.g., due to the mentioned subtleties with repudiability and public verifiability. MACs and signatures are very different beasts.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I felt like this should be the awarded answer due to pointing to a concrete implementation in NaCl that supports public-key authenticated encryption. Thanks for that! That said, it makes sense that in practice there are very few implementations for such because of how public key crypto is used as you pointed out as well as the additional inherent complexity (two keys, etc per @maarten-bodewes) and the pitfalls with EtM, MtE, EaM schemes. $\endgroup$ – Les Hazlewood Aug 23 at 17:47
  • $\begingroup$ That is why it is called mutual authentication. Only the parties that have the secret key can test of the authentication. Also, additional data is very useful in networking. $\endgroup$ – kelalaka Aug 24 at 12:38
4
$\begingroup$

AEADs are symmetric BY DEFINITION. What's more they are the base point from which we can argue the security of protocol designs.

Asymmetric authenticated encryptions schemes are known as signcrypt schemes, and PGP is probably the best-known example.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I could be wrong, but RFC 5116 is more about AEAD for network protocols rather than a formal definition/requirement for all AEAD implementations. Also, and not that Wikipedia is any authority of course, but the AEAD page mentions symmetric key ciphers, but not as a mandatory scheme, which led me to believe that asymmetric key authenticated encryption was feasible, albeit not common, and likely not as a primitive. In any event, I'm grateful for your answer! Thank you! $\endgroup$ – Les Hazlewood Aug 23 at 17:39
  • $\begingroup$ P.S. Thanks for the signcrypt pointer - that was helpful. $\endgroup$ – Les Hazlewood Aug 23 at 17:59
2
$\begingroup$

Do all AEAD implementations use symmetric key ciphers in practice?

Yes, but that's more by definition than because of unwillingness it seems.

Please note that you do require two key pairs, one for encryption and one for signing to achieve the confidentiality and message integrity / authenticity that an AEAD scheme offers. That means that any AEAD scheme for asymmetric ciphers needs to be significantly more complex than for the symmetric sense (the paper pointed to by real-or-random shows this complexity as well). Then there is the issue of trusting the public keys which may require an entire PKI. Therefore I think things like asymmetric encryption & signature generation are handled at the protocol level.

For symmetric ciphers it made sense to specify AEAD ciphers as some kind of secure drop: use this and you get authenticity for free, using a single key (mostly). Moreover, with an AEAD cipher such as GCM or one that uses Poly1305 you get a nice speedup compared to HMAC as well. That's a rather different proposition than what is required to perform authenticated encryption using asymmetric primitives.

| improve this answer | |
$\endgroup$
  • $\begingroup$ That's a good point about the two keys. As an implementor of the JWT RFC specifications (7515-7519), Encrypt-then-Mac is a supported algorithm per RFC 7516 Appendix B, and generated secure-random keys are double their usual length because they had to be split into two distinct keys: one for encryption, the other for hmac. (The alternative/preferred AES-GCM algorithm in those RFCs is obviously simpler and uses a single key, and is faster as you pointed out). $\endgroup$ – Les Hazlewood Aug 23 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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