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.)