Incrementing IV: is it safe?

Bill Frantz frantz@netcom.com
Thu, 4 Nov 1999 23:37:53 -0800


At 2:57 PM -0800 11/4/99, Anonymous wrote:
>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.
>
>However the IV for the next message is gotten by incrementing the IV from
>the first message, and likewise for each successive message.
>
>Is there a risk here that if two messages have the same first 8-byte
>block, except that it differs in just the last bit, then this will be
>visible because the first ciphertext blocks are identical?  In CBC
>mode the first ciphertext block = Encrypt( IV xor Plaintext ).  If we've
>incremented the IV, half the time this will just change the low order
>bit.  If the plaintext also happens to match except for the low order
>bit, the same value will be encrypted for both packets.

This comment sounds like it is addressed to the E Pluribus protocol
(http://www.erights.org/to-be-sorted/DataComm_startup.html).  In that
protocol, some level of protection is acheived by having the SHA(1) hash of
the message and the shared secret authentication key be the first block of
each message.

       TCP Message format

       (n,totalLength) (20,SHA1_MAC) (n,msgLength1) (msgLength1,message)
       ... (n,pad)

       The totalLength and msgLength fields are sent in compressed format.
       For values between 0 and 127 (27-1), the value is sent as one byte
       (with one high zero bit). For values between 128 and 16,383 (214-1),
       the value is sent as 2 bytes (with two high zero bits). For values
       between 16,384 and 2,097,151 (221-1), the value is sent as 3 bytes
       (with three high zero bits). Since the maximum size message is
       1,048,576 (220), this encoding covers all the legal messages.

       The totalLength field is the length in bytes of the all the messages
       including their compressed length field. It does not include the 20
       byte Message Authentication Code (MAC), the pad, or the length of
       the totalLength field.

       The MAC is calculated using SHA1 and the authentication key generated
       as part of key generation. The MAC is the result of: SHA1( (64,MACKey )
       (n,msgLength1) (msgLength1,message) ... (64,MACKey ) ).

       After the TCP message is generated as above, it is encrypted using
       Triple DES EDE in Cypher Block Chaining mode. (See Applied Cryptography
       by Bruce Schneier for details.) The first Initialization Vector (IV)
       is calculated as part of key generation. The next TCP message uses an
       IV which is one higher than the previous one. The IV is considered to
       be an 8 byte unsigned integer in big endian format for this addition.

-------------------------------------------------------------------------
Bill Frantz       | Internet Explorer, the     | Periwinkle -- Consulting
(408)356-8506     | hacker's path to your      | 16345 Englewood Ave.
frantz@netcom.com | hard disk.                 | Los Gatos, CA 95032, USA