Subject: digest-md5 and CBC

From: Sam Hartman <[email-masked]>
Date: Tue, 16 Nov 2004 17:36:59 -0500

Hi.  I'm sorry that this message has been delayed so long.

After IETf 60, Alexey and I (as chair) talked to Russ about
digest-md5's usage of CBC.

As the working group will recall, there are two proposals.  The first
proposal is that an explicit IV be included in every message.  The
second proposal is that there be two blocktypes.  The first includes
an explicit IV and the second includes a CBC block.  No requirement
would be made that every block be proceeded by a CBC block.

There are two advantages the the second proposal.  The first is that
it happens to fit the Cyrus code base better.  The second is that it
can avoid the expansion factor of the IV.  Russ didn't think much of
the first advantage; personally I agree.

My concern with this approach is that I believe it is vulnerable to an
attack where the CBC datastream can be used as an oracle to test
guesses of what previous ciphertext decrypts to.  The attack is
somewhat hard to construct and assumes that an attacker can observe
the generated ciphertext and can inject text to be encrypted directly.
So it is not completely clear that we must address this problem.

Russ instructed me to run the proposal by the CFRG and if they did not
raise strong objections the WG could take that approach if it desired.

The rest of this message is my opinion as an individual participant.

If our goal is the avoid expansion, there is a secure way to do that.
We can use counter mode instead of CBC.  That would make our AES mode
work a lot like our RC4 mode.  You need to be careful when using a
counter-mode cipher, but we already have this complexity for RC4.

We decided against counter mode for complexity reasons.  However if we
need the features of counter mode I'd rather see us take that
approach.

--Sam

---

From: Sam Hartman <[email-masked]>
Date: Tue, 16 Nov 2004 18:05:49 -0500

I failed to make one thing clear.  If the working group believes that
the second CBC proposal is the right approach, we can still go to the
CFRG and go down that path.

When reviewing the document for the IESG I'll want to understand why
the working group believes that CBC without explicit IVs is better
than counter mode if the group does take that approach.

---

From: Alexey Melnikov <[email-masked]>
Date: Wed, 17 Nov 2004 13:21:17 +0000

>So it is not completely clear that we must address this problem.
Can you give a bit more details on how this would work, maybe 
application guys will be able to understand ;-).

>need the features of counter mode I'd rather see us take that
I personally have no problem with the counter mode: the DIGEST-MD5 
deprecates all old ciphers in CBC mode (DES, 3DES) and AES is a new 
cipher, so it doesn't have to use CBC. I presume that there is another 
advantage of using the counter mode - the existing structure of 
DIGEST-MD5 security layer packets will remain the same, which is a good 
thing.
Due to my lack of experience with the counter mode, somebody has to help 
me out with the text.

One question remains though: do we want to allow for ciphers in CBC mode 
in the future? If we do, we still have to choose between two choices 
described in the draft.

Alexey

---

From: Sam Hartman <[email-masked]>
Date: Wed, 17 Nov 2004 13:30:18 -0500

>>>>> "Alexey" == Alexey Melnikov <[email-masked]> writes:

    >> My concern with this approach is that I believe it is
    >> vulnerable to an attack where the CBC datastream can be used as
    >> an oracle to test guesses of what previous ciphertext decrypts
    >> to.  The attack is somewhat hard to construct and assumes that
    >> an attacker can observe the generated ciphertext and can inject
    >> text to be encrypted directly.  So it is not completely clear
    >> that we must address this problem.
    >> 
    >> 
    Alexey> Can you give a bit more details on how this would work,
    Alexey> maybe application guys will be able to understand ;-).

I've got some client listening to an unencrypted stream and protecting
the results using digest-md5 in CBC mode.

An attacker sees the encrypted network traffic and controls the
unencrypted stream.

Previously in the same stream (before the attacker controlled it) was
some text.  The attacker believes he knows what the text is and wishes
to verify a guess.  The attacker can try sending the text over the
stream xored with the appropriate block based on the previous IV.  If
the guess is correct, the resulting encrypted block will be related to
the previous encrypted block.

    Alexey> I personally have no problem with the counter mode: the
    Alexey> DIGEST-MD5 deprecates all old ciphers in CBC mode (DES,
    Alexey> 3DES) and AES is a new cipher, so it doesn't have to use
    Alexey> CBC. I presume that there is another advantage of using
    Alexey> the counter mode - the existing structure of DIGEST-MD5
    Alexey> security layer packets will remain the same, which is a
    Alexey> good thing.  Due to my lack of experience with the counter
    Alexey> mode, somebody has to help me out with the text.
Understood.

    Alexey> One question remains though: do we want to allow for
    Alexey> ciphers in CBC mode in the future? If we do, we still have
    Alexey> to choose between two choices described in the draft.

I think the structure of the cipher packets should be cipher
dependent.

---

From: Russ Housley <[email-masked]>
Date: Wed, 17 Nov 2004 16:04:38 -0500

I would like to make two points.

First, AES-CBC with an explicit IV is always safe.  The WG needs to decide 
if the expansion caused by the IV is too much.  If so, then other 
approaches need to be considered, including AES-CTR.

Second, AES-CTR is sometimes used with an IV too.  When a constant encrypt 
time is important, an LFSR can be used instead of a counter.  This is very 
important in very high-speed implementations.  Again, the WG needs to 
determine if this is a concern in this context.

RFC 3686 provides the rationale for including an IV when AES-CTR is used in 
IPsec ESP.  It says:

    In the development of this specification, the use of the ESP sequence
    number field instead of an explicit IV field was considered.  This
    selection is not a cryptographic security issue, as either approach
    will prevent counter block collisions.

    In a very conservative model of encryption security, at most 2^64
    blocks ought to be encrypted with AES-CTR under a single key.  Under
    this constraint, no more than 64 bits are needed to identify each
    packet within a security association.  Since the ESP extended
    sequence number is 64 bits, it is an obvious candidate for use as an
    implicit IV.  This would dictate a single method for the assignment
    of per-packet value in the counter block.  The use of an explicit IV
    does not dictate such a method, which is desirable for several
    reasons.

    1. Only the encryptor can ensure that the value is not used for more
       than one packet, so there is no advantage to selecting a mechanism
       that allows the decryptor to determine whether counter block
       values collide.  Damage from the collision is done, whether the
       decryptor detects it or not.

    2. Allows adders, LFSRs, and any other technique that meets the time
       budget of the encryptor, so long as the technique results in a
       unique value for each packet.  Adders are simple and
       straightforward to implement, but due to carries, they do not
       execute in constant time.  LFSRs offer an alternative that
       executes in constant time.

    3. Complexity is in control of the implementer.  Further, the
       decision made by the implementer of the encryptor does not make
       the decryptor more (or less) complex.

    4. When the encryptor has more than one cryptographic hardware
       device, an IV prefix can be assigned to each device, ensuring that
       collisions will not occur.  Yet, since the decryptor does not need
       to examine IV structure, the decryptor is unaffected by the IV
       structure selected by the encryptor.  One cannot make use of the
       same technique with the ESP sequence numbers, because the
       semantics for them require sequential value generation.

    5.  Assurance boundaries are very important to implementations that
       will be evaluated against the FIPS Pub 140-1 or FIPS Pub 140-2
       [SECRQMTS].  The assignment of the per-packet counter block value
       needs to be inside the assurance boundary.  Some implementations
       assign the sequence number inside the assurance boundary, but
       others do not.  A sequence number collision does not have the dire
       consequences, but, as described in section 6, a collision in
       counter block values has disastrous consequences.

    6. Coupling with the sequence number is possible in those
       architectures where the sequence number assignment is performed
       within the assurance boundary.  In this situation, the sequence
       number and the IV field will contain the same value.

    7. Decoupling from the sequence number is possible in those
       architectures where the sequence number assignment is performed
       outside the assurance boundary.

    The use of an explicit IV field directly follows from the decoupling
    of the sequence number and the per-packet counter block value.  The
    overhead associated with 64 bits for the IV field is acceptable.
    This overhead is significantly less than the overhead associated with
    Cipher Block Chaining (CBC) mode.  As normally employed, CBC requires

    a full block for the IV and, on average, half of a block for padding.
    AES-CTR with an explicit IV has about one-third of the overhead as
    AES-CBC, and the overhead is constant for each packet.

    The inclusion of the nonce provides a weak countermeasure against
    precomputation attacks.  For this countermeasure to be effective, the
    attacker must not be able to predict the value of the nonce well in
    advance of security association establishment.  The use of long keys
    provides a strong countermeasure to precomputation attacks, and AES
    offers key sizes that thwart these attacks for many decades to come.

    A 28-bit block counter value is sufficient for the generation of a
    key stream to encrypt the largest possible IPv6 jumbogram [JUMBO];
    however, a 32-bit field is used.  This size is convenient for both
    hardware and software implementations.

Russ

---

From: Sam Hartman <[email-masked]>
Date: Tue, 16 Nov 2004 18:05:49 -0500

---

From: Alexey Melnikov <[email-masked]>
Date: Wed, 17 Nov 2004 13:21:17 +0000

Alexey

---

From: Sam Hartman <[email-masked]>
Date: Wed, 17 Nov 2004 13:30:18 -0500

---

From: Russ Housley <[email-masked]>
Date: Wed, 17 Nov 2004 16:04:38 -0500

Russ