IV generation

Steve Bellovin <smb@research.att.com> Tue, 09 December 1997 18:18 UTC

Received: (from majordom@localhost) by portal.ex.tis.com (8.8.2/8.8.2) id NAA04511 for ipsec-outgoing; Tue, 9 Dec 1997 13:18:26 -0500 (EST)
Message-Id: <199712091824.NAA03610@smb.research.att.com>
From: Steve Bellovin <smb@research.att.com>
To: ipsec@tis.com
Subject: IV generation
Date: Tue, 09 Dec 1997 13:24:05 -0500
Sender: owner-ipsec@ex.tis.com
Precedence: bulk

There's an attack I've heard about that's worth mentioning.  The current
relevant drafts (draft-ietf-ipsec-ciph-des-expiv-01.txt and
draft-ietf-ipsec-ciph-cbc-01.txt) suggest the proper behavior, but
don't describe the attack, and don't bar the dangerous behavior.
It would be useful to describe the attack, if for no other reason than
to warn other implementors.

The problem arises if you use a counter as an IV, or some other source with
a low Hamming distance between successive IVs, for encryption in CBC mode.
In CBC mode, the "effective plaintext" for an encryption is the
XOR of the actual plaintext and the ciphertext of the preceeding block.
Normally, that's a random value, which means that the effective plaintext
is quite random.  That's good, because as I demonstrated in a paper last
February, many blocks of actual plaintext don't change very much
from packet to packet, either.

For the first block of plaintext, though, the IV takes the place of
the previous block of ciphertext.  If the IV doesn't differ much from
the previous IV, and the actual plaintext block doesn't differ much
from the previous packet's, then the effective plaintext won't differ
much, either.  This means that you have pairs of ciphertext blocks
combined with plaintext blocks that differ in just a few bit positions.
This can be a wedge for assorted cryptanalytic attacks.

So -- I suggest that the following text be added to the two documents
cited above:

        To avoid ECB encryption of very similar plaintext blocks in
        different packets, implementations MUST NOT use a counter or
        other low-Hamming distance source for IVs.

(I don't like the same text being in two different documents, but both
of these are on CBC encryption.  Arguably, those shouldn't have been
different documents, but I *don't* want to merge them now...  Neither
the architecture document nor the ESP document discuss IV selection,
so it can't go in them.)