From: daw@mozart.cs.berkeley.edu (David Wagner) Newsgroups: sci.crypt Subject: Re: CTR Mode and AES Date: Mon, 12 Aug 2002 02:47:20 +0000 (UTC) Message-ID: Brian Gladman wrote: >"David Wagner" wrote: >> By the way, is it clear what this "generic composition" term refers to? >> If not, I'd be glad to elaborate. > >I would ceertainly find this helpful. Ok, here's the deal. The encrypt-then-authenticate generic composition method refers to what you think it does. You first encrypt your message, say C = Encrypt_K1(M). Then, you authenticate the result, T = MAC_K2(C). Finally, you transmit the concatenation of the two, C || T. For example, you might instantiate Encrypt() with CBC mode encryption using a random IV and instantiate MAC() with SHA1-HMAC (or, one of the variants of CBC-MAC that is secure for variable-length messages). One can prove a security theorem saying roughly that the composition is secure against adaptive chosen-plaintext/ciphertext attacks, if several conditions are met: 1. Encrypt() should be a stateless encryption scheme satisfying IND-CPA. Roughly speaking, IND-CPA refers to security against adaptive chosen-plaintext attacks (also known as "semantic security"). 2. MAC() should form a "strong MAC", i.e., no adaptive chosen-message attack can come up with a valid (message, MAC) pair except by repeating some previously transmitted pair. 3. K1 and K2 must be chosen independently. If these conditions are met, then the composition is IND-CCA2 secure, i.e., it achieves both privacy and integrity against adaptive chosen-plaintext/ciphertext attacks. The bound is security-preserving: the security level achieved by the composition is closely related to the security level of the individual components. Hugo Krawczyk showed that the order is important. Authenticate-then-encrypt (AtE) isn't generically secure: there is no corresponding security theorem for this approach. Also, encrypt-and-authenticate (E&A) -- where you apply the encryption and MAC in parallel -- is also not generically secure. In particular, Krawczyk also showed that, for any particular choice of Encrypt() and MAC(), AtE or E&A might happen to be secure, or they might be insecure. For some common choices, they are secure, but for others, they could also be insecure. In short, AtE and E&A are fragile, while EtA is more robust. In retrospect, the intuition for why encrypt-then-authenticate is good is not too hard to see. Asking for the decryption of chosen ciphertexts doesn't give the attacker any new power: if the pair C || T is new (not produced by the legitimate transmitter) and if the MAC is secure, then C || T will be rejected by the recipient; on the other hand, if C || T is a ciphertext produced by a legitimate transmitter, the adversary learns nothing more than what the legitimate sender wanted sent this time. Consequently, chosen-plaintext/ciphertext attacks are no more powerful than chosen-plaintext attacks, and if Encrypt() is secure against chosen-plaintext attacks, the composition will be secure against chosen-plaintext/ciphertext attacks. That's an intuitive view, anyway. The proof follows this basic reasoning quite closely. The lesson I take away from this is that, when designing new systems, encrypt-then-authenticate is probably the right way to go. (One exception is when you're using some mode designed to provide IND-CCA2 security directly, such as OCB mode.)