[Fwd: Re: Incrementing IV: is it safe?]

[Sandy Harris]

[Sandy, even though this is your message that I'm forwarding, I'm cc'ing you
anyway so other people's replies will go to you as well.  There is already a
thread on the e-lang list spawned by this discussion.  The two messages so
far are http://eros.cis.upenn.edu/%7Emajordomo/e-lang/1086.html and
http://eros.cis.upenn.edu/%7Emajordomo/e-lang/1087.html .  Thanks for the
info.  --MarkM]


One message in this thread suggests that it is one of your protocols
under discussion, so I'm forwarding one that shows why the counter IV
is a flaw.

-------- Original Message --------
Subject: Re: Incrementing IV: is it safe?
Date: Thu, 04 Nov 1999 21:53:37 -0500
From: "Theodore Y. Ts'o" <tytso@MIT.EDU>
To: Jack Lloyd <lloyd@chimera.acm.jhu.edu>
CC: coderpunks@toad.com

    Date: Thu, 4 Nov 1999 21:01:22 -0500 (EST)
    From: Jack Lloyd <lloyd@chimera.acm.jhu.edu>

    >In a proposed protocol, communication is with 3DES in CBC mode, across a
    >TCP channel (providing reliable, sequenced delivery).  The IV for the
    >first packet, as well as the key, are based on hashing a Diffie Hellman
    >shared secret.  Nothing special here so far.

    Why didn't you just say, "In IPSec"?

Umm... because it isn't?

AC wrote:

 >However the IV for the next message is gotten by incrementing the IV from
 >the first message, and likewise for each successive message.

IPSEC does *not* do this.

To quote RFC 2406:

       "Common practice is to use random data for the first IV and the
       last 8 octets of encrypted data from an encryption process as the
       IV for the next encryption process; this logically extends the CBC
       across the packets. It also has the advantage of limiting the
       leakage of information from the random number genrator. No matter
       which mechnism is used, the receiver MUST NOT assume any meaning
       for this value, other than that it is an IV."

    And perhaps more obviously, it *is* in IPSec. If someone hasn't found a
    hole it, I'm willing to believe that it's not a problem. More paranoid
    members of the list might be want to look into it, I don't know.

No, it's not in IPSEC, and the IPSEC documents specifically talk about
*why* this is a bad idea.  Quoting again from RFC 2406:

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

Put another way, consider that in many protocols, the first 8 bytes of
the protocol may be constant, because it's some kind of header (i.e.,
source/destination IP addresses, etc.).  If the successive IV's have a
low hamming distance between them, then you can have a large number of
known plaintext/ciphertext pairs where the plaintexts only differ in
just one or two bit positions.  This is extremely useful for
differential crypto and other related attacks.

There may be some IPSEC implementations that use a counter as an IV; it
violates the IPSEC RFC's, and they are broken and vulnerable to
cryptanalysis.

							- Ted