Suggested modification to AES privacy draft

[Scott Fluhrer <sfluhrer@cisco.com>]

Hello,

  I have a modification to draft-ietf-ipsec-ciph-aes-cbc-03.txt
that I would recommend.  The text under consideration (in section 3)
currently reads:

   The IV field MUST be the same size as the block size of the cipher
   algorithm being used. The IV MUST be chosen at random. Common
   practice is to use random data for the first IV and the last block
   of encrypted data from an encryption process as the IV for the next
   encryption process. 

My objection is with the last sentence -- with this common practice,
an attacker who can select packets to be sent through the SA can
verify the plaintext of blocks he did not originate, allowing him to
read low entropy messages that he should not have access to.  My
suggestion for revising the paragraph is:

   The IV field MUST be the same size as the block size of the cipher
   algorithm being used. The IV MUST be chosen at random, and MUST be
   unpredictable.


Here are the details of an attack against privacy that is possible if
the next IV is the last ciphertext block (or, by extension, if the IV
is predictable):

- Suppose the attacker (Eve) can send packets through the SA.  This
  attacker may be a legitimate user that is not authorized to read
  all the traffic that is routed through the SA.

- Suppose that the attacker has a line monitor that can read the
  encrypted packets.

- Suppose that Bob (an innocent user) telnets to computer system
  Alice via the SA, and enters his password.  His password is sent
  to Alice as a series of TCP packets, with each TCP packet holding
  one character of the password.

- Further suppose that Eve knows Bob's TCP stack, and so she can
  guess everything within the TCP header except the data being
  transmitted (or at least, that part of the header that is
  encrypted within the same block).

Now, Eve considers an encrypted TCP packet that contains a password
character.  Let us call the ciphertext block that contains that
actual password character C_n, and the ciphertext block immediately
previous to that as C_{n-1}.  If we call the (unknown) plaintext
block that contains the password character P_n, then by how CBC mode
works:

   C_n = E_k( P_n ^ C_{n-1} )

where E_k is the AES encryption of a block using the SA's key, and
^ is xor.

Now, Eve guesses the value of the password character.  Since she
knows the rest of the TCP header, she can form the value Q_n which
is the value of the plaintext block (that is, P_n = Q_n) if her
guess is value.

To validate her guess, she examines the last ciphertext block of
the last packet, which will be used as the IV for the next
ciphertext block, which we will denote as IV.  Then, she forms
a packet whose first block is the value:

   IV ^ C_{n-1} ^ Q_n

(Note that she may not be able to transmit that as the first
block of an IP packet or transport header -- constraints (such
as the IP version number being either 4 or 6) may prevent her
from using that.  When this happens, she can either attack a
different password character, or send an arbitrary packet to
reset the IV.  That has the effect of causing this attack
require Eve send more packets to perform this attack).  She
sends the packet through the SA, and so the encrypted first
block (which she can see) is:

  D_0 = E_k( IV ^ C_{n-1} ^ Q_n ^ IV )
      = E_k( Q_n ^ C_{n-1} )

If her guess is correct, that is, if P_n = Q_n, then C_n = D_0.
Because both C_n and D_0 appear in the encrypted text, she can
verify whether this occurs, and so she knows her guess of the
password character is correct.  If there are 96 possibilities
for a password character, then by transmitting 96 such packets,
Eve can rederive a single password character.  Hence, if Bob
uses a 10 character password, then only 960 packets are
required for Eve to rederive the entire password.


I would claim that this attack on privacy is unacceptable, as
none of the assumptions that this attack makes are about things
that the security of IPSec should rely on.  Therefore, I claim
that the common practice of reusing the previous ciphertext
block (which allows this attack), or otherwise selecting IVs
in a predictable manner, should be prohibited.


-- 
scott