Subject: Strawman for adding a MDC to encrypted data

From: [email-masked] (Peter Gutmann)
Date: Fri, 08 Dec 2006 19:36:31 +1300

Over the years there have been various papers published on messing with CBC-
encrypted data to perturb the plaintext in a predictable way.  The OpenPGP
folks addressed this issue fairly quickly by adding an MDC to their encrypted
content, but S/MIME doesn't address it at all.  What makes this issue a lot
more troublesome is that the public perceives encryption as providing data
integrity protection, a service it in fact doesn't provide (they also perceive
signing as providing no data integrity protection, see Garfinkel 2006).  Short
of educating the entire world's email-using population about cryptographic
security issues, the other possible alternative is to make the encryption act
in the way they think it acts.

(There are other useful applications of the added MDC as well, e.g. when
 wrapping private keys for storage the MDC protects against the Klima-Rosa
 attack, which OpenPGP keys are protected against but S/MIME ones aren't).

A simple fix for the problem is to add an MDC to EnvelopedData.  There are
alternatives, but none are practical: wrapping the EnvelopedData in
AuthenticatedData collapses under the weight of key management and
implementation issues, using a combined encrypt+authenticate mode is either
impractical due to patent concerns or has severe implementation problems
because these new modes will take an arbitrarily long amount of time to become
widely supported, etc etc.

The MDC approach is a relatively straightforward change that simply runs a
hash over the ciphertext and attaches the encrypted form of the hash (using
the content-encryption key used to encrypt the rest of the content) to the
EnvelopedData as UnprotectedAttributes.  So the process becomes:

  ciphertext = encrypt( plaintext );
  MDC = encrypt( hash( ciphertext ) );

Hashing the ciphertext protects against other attacks relating to manipulating
of PKCS #5 padding content.  The use of the content-encryption key/cipher for
the MDC tag avoids key management issues.  The OpenPGP folks have been doing
this for some years now, and it has the approval of the crypto community.

The only problematic issue is how to indicate the use of the MDC algorithm.
Some options are:

  Use a version number of 5 to indicate (implicitly) the use of a SHA-1 MDC.

  Add something to the RecipientInfos as an OtherRecipientInfo that simply
  contains the hash algorithm details.

  (As above, but with OriginatorInfos).

The second option is a bit of a kludge, but seems to be the cleanest way to do
it.  The overall changes are very minimal, a new UnprotectedAttribute type
with the MDC, a new OtherRecipientInfo type, and a bit of code to run a hash
alongside the en/decrypt.  In my trial implementation (excluding the
attribute-handling) there were only about a dozen lines of code required
because the hashing is already performed for SignedData so all it required was
turning on the hash flag if an MDC was specified in the RecipientInfo.

Is there any support for adding this?  I should be able to get a draft out
fairly quickly, and from a check with two other implementors producing
interoperable implementations should be fairly easy.

Peter.

---

From: Daniel Brown <[email-masked]>
Date: Fri, 8 Dec 2006 10:23:45 -0500

Peter Gutman wrote on 12/08/2006 01:36:31 AM:

> because these new modes will take an arbitrarily long amount of timeto 
become
>   MDC = encrypt( hash( ciphertext ) );

Hmm ... I vaguely recall some problems with using a unkeyed hash, e.g. 
SHA-1, to protect integrity.  Here's what I can remember at the moment, 
sorry if I'm making a mistake.

Presumably encrypt does not protect integrity, so, the attacker may be 
able to change ciphertext to ciphertext', and further know that the 
corresponding decryption plaintext' has some meaningful relationship to 
plaintext.  Now the attacker can compute hash(ciphertext') and if the 
encrypt function has sufficiently poor integrity, the attacker can use 
this knowledge of MDC to compute MDC' = encrypt(hash(ciphertext')).

An example of an encrypt function that is vulnerable to this any stream 
cipher, such as RC4.  Specifically, let ciphertext' = ciphertext xor delta 
= (rc4-stream xor plaintext) xor delta, giving plaintext' = plaintext xor 
delta.  Now MDC' = MDC xor hash(ciphertext) xor hash(ciphertext').

Even if S/MIME does not allow stream ciphers, they demonstrate that the 
construction above presumes that the encrypt function must have some kind 
of integrity properties.  I'm not sure if AES-CBC, for example, has the 
requisite integrity-protection property for the construction above.

An alternative construction may work, though:

MDC = MAC (ciphertext);

where MAC could be HMAC and the key would be the CEK, or a derivative 
thereof.  Using a MAC in this way has precedent in a scheme like 
DHAES/ECIES.  The scheme DHAES has a published security proof, so it has, 
to a significant extent, precedent in the academic crypto community.

Admittedly, the alternative construction, however, might require more 
implementation work than hash based construction, since some S/MIME 
implementations may not have code for computing a MAC (unless they 
implemented AuthenticatedData).  Even so, it doesn't really take too much 
work to implement HMAC given a hash function implementation.

Dan Brown
(905) 501-3857
http://www.certicom.com

> The second option is a bit of a kludge, but seems to be the cleanestway 
to do

---

From: [email-masked] (Peter Gutmann)
Date: Sat, 09 Dec 2006 05:18:53 +1300

Daniel Brown <[email-masked]> writes:

>Presumably encrypt does not protect integrity, so, the attacker may be able
>to change ciphertext to ciphertext', and further know that the corresponding
>decryption plaintext' has some meaningful relationship to plaintext.  Now the
>attacker can compute hash(ciphertext') and if the encrypt function has
>sufficiently poor integrity, the attacker can use this knowledge of MDC to
>compute MDC' = encrypt(hash(ciphertext')).

The assumption is that they're using a 64- or 128-bit block cipher, so
something like RC4 would be a MUST NOT.

(In fact I don't know if RC4 has been used at all with CMS.  That is, there's
nothing preventing its use, but even when RC4 was still popular what got used
in PKCS #7 was the block cipher RC2 and not the stream cipher RC4).

>construction above presumes that the encrypt function must have some kind of
>integrity properties.  I'm not sure if AES-CBC, for example, has the

Note that this isn't meant to be a high-integrity, provably-secure solution.
It's meant to be a low-effort fix for the problem that users expect CMS
encryption to exhibit a property that it doesn't currently have.  I'd be
interested to see any real attacks on this, since it would mean OpenPGP's MDC
(which AFAIK has passed crypto scrutiny) would also be vulnerable.

>thereof.

This won't work, for the key-management reasons mentioned in my previous
message - crypto libraries and devices like smart cards and HSMs typically
implement hybrid encryption as "unwrap a CEK (e.g.for 3DES) with a private
key", but don't support "unwrap a CEK for 3DES and also feed it into a PRF to
suitably diversify it for use with HMAC".  If it's an implementation where
keys can't leave the protected boundary, all you can get out of the unwrap is
a handle to a 3DES object, not even a key.

>implemented AuthenticatedData).

It's not the HMAC implementation that's the problem, it's that the key
management is impossible in some (many?) cases.  There are a pile of kludges I
thought of (e.g. unwrap the 3DES key, then encrypt 128 bits of zeroes to get
an HMAC key, which gets around not having access to the CEK) but no matter how
you fiddle it it's an awful kludge, and I'm not sure that it doesn't
potentially introduce vulnerabilities of its own.

Peter.

---

From: Daniel Brown <[email-masked]>
Date: Fri, 8 Dec 2006 12:08:21 -0500

> >Presumably encrypt does not protect integrity, so, the attacker may be 
able
> something like RC4 would be a MUST NOT.

Okay, so you would add a MUST NOT to your ID, just in case somebody later 
on adds a stream cipher to CMS.
 
> ...

I don't know exactly what OpenPGP does, so maybe it's fine.  However, let 
me describe an example demonstrating why one may want to be careful, even 
with AES-CBC. Suppose hash = MD5, or any other 128-bit hash, such SHA-256 
truncated to 128 bits.   We're not signing, so arguably, we don't need to 
worry about the collision attacks, and this may be reasonable.  Suppose 
the encrypt function used to compute the MDC is AES-CBC with a random IV. 
Then,

MDC = IV || AES_CEK ( IV xor MD5(ciphertext)) = IV || B

The Adversary first swaps ciphertext with ciphertext', and then sets

MDC' = IV'  || B

where IV' = IV xor MD5(ciphertext) xor MD5(ciphertext').  Now MDC' is 
valid for ciphertext', which is presumably undesirable.   Such problems 
could perhaps be fixed by setting IV to the last block of the ciphertext, 
or fixing it to zero, which may be how OpenPGP works, or by insisting that 
hash has more than 128 bits. 

To make this a more meaningful attack, it helps to show that plaintext' 
and plaintext can somehow be related.  This is a well-known result.  By 
modifying ciphertext block C_b to C'_b = C_b xor delta, the adversary 
modifies the subsequent plaintext block P_(b+1) to P'_(b+1) = P_(b+1) xor 
delta, while the corresponding plaintext block P_b becomes P'_b = random. 
This gives a somewhat meaningful relationship between plaintext' and 
plaintext. 

> ...

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: Russ Housley <[email-masked]>
Date: Fri, 08 Dec 2006 11:10:31 -0500

Peter:

I have no objection to the proposed unauthenicated attribute.  It 
seems like a straightforward addition.

I think that authenticated encryption (like AES-CCM and AES-GCM) are 
also highly desirable solutions.  I would like to see a CMS 
protection content type that supports these.  The AES-CCM and AES-GCM 
algorithms are not encumbered, but as you say, other authenticated 
encryption modes are.

I have thought about support for AES-CCM and AES-GCM with 
EnvelopedData, but these algorithms have the cool feature that they 
can authenticate some data that is not encrypted.  This is not one of 
your concerns, but it seems desirable to support both authenticated 
and unauthenticated attributes as is done with SignedData.

Russ

---

From: [email-masked] (Peter Gutmann)
Date: Mon, 11 Dec 2006 16:05:09 +1300

Russ Housley <[email-masked]> writes:

>I have no objection to the proposed unauthenicated attribute.  It seems like
>a straightforward addition.

OK, I'll get to work on it.

>I think that authenticated encryption (like AES-CCM and AES-GCM) are also
>highly desirable solutions.  I would like to see a CMS protection content
>type that supports these.  The AES-CCM and AES-GCM algorithms are not
>encumbered, but as you say, other authenticated encryption modes are.

In the long run using encrypt+authenticate modes would definitely be
preferable, and I'll get this sentiment into the text.  The reason I went for
the MDC approach is because (hopefully) anything that can understand
EnvelopedData with version number 2 or 3 will be able to process (or at least
not break when it encounters) the MDC, so it can be introduced right now
without causing too much breakage.  AES-CCM/GCM are definitely the better
longer-term solutions, but then the other problem there is that support for
these modes could take awhile to appear, particularly in HSMs.  PKCS #11 (the
litmus paper for crypto hardware support) has only just added AES-CTR in the
latest draft amendment and doesn't do -CCM or -GCM at all, so it could be
quite awhile before we see these modes widely deployed.

Peter.

---

From: [email-masked] (Peter Gutmann)
Date: Mon, 11 Dec 2006 16:38:20 +1300

Daniel Brown <[email-masked]> writes:

>Okay, so you would add a MUST NOT to your ID, just in case somebody later on
>adds a stream cipher to CMS.

Sure.

>I don't know exactly what OpenPGP does, so maybe it's fine.

It encrypts the SHA-1 hash in CFB mode.  Unfortunately the only analysis I'm
aware of (I've just asked on the OpenPGP list) is by Hungarian cryptographer
Daniel Nagy:

  I have just discussed this issue with my students at our cryptography
  seminar. The general consensus is that MDCs do not need collision
  resistance. Thus, SHA1 is secure with a huge security margin. The recent
  weakening of SHA1 means that finding a pre-image takes approx 2^138
  attempts, which is still comfortably beyond reach for today's and tomorrow's
  technology. Introducing longer hashes would make it slower, while not
  improving security. If you insist, I can provide the complete reasoning why
  collision-resistance is not required for MDC.

>However, let me describe an example demonstrating why one may want to be
>careful, even with AES-CBC. Suppose hash = MD5, or any other 128-bit hash,
>such SHA-256 truncated to 128 bits.   We're not signing, so arguably, we
>don't need to worry about the collision attacks, and this may be reasonable.
>Suppose the encrypt function used to compute the MDC is AES-CBC with a random
>IV. Then,
>
>where IV' = IV xor MD5(ciphertext) xor MD5(ciphertext').  Now MDC' is valid
>for ciphertext', which is presumably undesirable.   Such problems could
>perhaps be fixed by setting IV to the last block of the ciphertext, or fixing
>it to zero, which may be how OpenPGP works, or by insisting that hash has
>more than 128 bits.

I think the last step was implied, the MDC should be covered by at least two
cipher blocks (that is, with an SHA-1 hash and any current CMS cipher it's
automatic, and with the even larger SHA-2 family hashes there's no way to
avoid it).  In addition OpenPGP (implicitly) sets the IV to the last block of
ciphertext because it simply jams the MDC onto the end of the encrypted data.
In this case I think either fixing the IV for the MDC at zeroes or using the
last ciphertext block would be the best option - it's mostly an implementation
thing, some implementations don't allow an explicit IV reload, but then you
can get around this by treating the IV as an additional data block.  Thanks
for bringing this up, I'll mention these issues in the security considerations
section to warn people if they try and "optimise" things in the future.

(I always put a rationale in my docs, it's amazing how much of this stuff
seems obvious when you write it but probably isn't when someone else has to
implement it :-).

Peter.

---

From: "Bonatti, Chris" <[email-masked]>
Date: Fri, 15 Dec 2006 16:22:52 -0500

> It encrypts the SHA-1 hash in CFB mode.  Unfortunately the only analysis I'm >
aware of (I've just asked on the OpenPGP list) is by Hungarian cryptographer > Daniel
>   collision-resistance is not required for MDC.

Peter,

   I don't know what the above rationale is.  However, there is 
a real-world consideration that is often overlooked in purely 
mathematical analyses of hash function shortcomings.  In order 
for an attacker to successfully exploit a hash collision it is 
necessary not only to find a collision, but to find one that 
yields a meaningful message.  Especially in applications such 
as S/MIME where the payload is often a formatted text message, 
just finding ANY arbitrary collision wouldn't work.  It would 
be likely to corrupt the message format, or otherwise cause 
the receiving client to display gibberish.  I suspect that this 
is true for a lot of applications.  So above and beyond the 
probability of finding a collision, you have to factor in the 
probability of finding a meaningful message (and presumably 
harmful) message that collides.  I suspect that number is MUCH 
smaller.

   I wouldn't even BEGIN to know how to quantify all the factors 
in this for a probability calculation.  Perhaps that is why it 
is so seldom mentioned.  ;-)

Best regards,
Chris B.