Subject: RE: [Cfrg] OpenPGP security analysis

From: Trevor Perrin <[email-masked]>
Date: Mon, 16 Sep 2002 19:48:15 -0700

>-----Original Message-----
>From: David Wagner [mailto:[email-masked]]
>
>Unfortunately, Hash-then-Encrypt has known security weaknesses, in
>general.  For instance, there is a chosen-plaintext attack that 
>lets you truncate a ciphertext without detection.  See, e.g.,
>http://www.cs.berkeley.edu/~daw/my-posts/mdc-broken

I don't see any complications that would trip this attack up in OpenPGP's
encryption/integrity packet type.  If you try to place M anywhere else
within M' besides the beginning, however, you'd have to guess at and prepend
duplicate prefix bytes to M, and snip so as to include the block previous to
these, and the attack would only have a 2^-16 probability of success because
the guessed duplicate prefix bytes probably won't match whatever the initial
prefix bytes turn out to be.

It seems like this could be fixed by using HMAC-SHA1 instead of just SHA1,
with a key derived by some function of the encryption key, but I'm not
sure..

Trevor

---

From: "Michael Young" <[email-masked]>
Date: Tue, 17 Sep 2002 11:20:08 -0400

Subject: Re: [Cfrg] OpenPGP security analysis

Trevor Perrin <[email-masked]> forwarded a note from...
> >http://www.cs.berkeley.edu/~daw/my-posts/mdc-broken
[quoted here for those new to the conversation:]
    I'm not sure I understand what you mean, but there's an attack.
    Suppose you want to make the receiver think message M was sent,
    even thought the sender would never authorize this.  Then you
    should construct M' = M || H(M) || X, where X is arbitrary and
    where || denotes concatenation (it better be at block boundaries).
    Ask the sender to transmit M'; he will form M' || H(M'), encrypt
    it with CBC mode, and transmit the result.  Now you can truncate
    the ciphertext, snipping it just before the "X" part, and the
    receiver will think M was sent, which is an integrity failure.

First, I should point out that, M *was* "sent", just not by the
apparent sender.  An MDC is not a signature.  The receiver should
not treat it as such.

Trevor went on to write:
> encryption/integrity packet type.

Assuming the usual PGP public key model, the attacker doesn't need the
sender to participate in this plan.  In this scenario, the attacker
can alter message traffic from sender to receiver, so he could simply
replace a message with is own well-formed PGP message.  Nothing new here.

This assumes that the receiver's public key is really public.
If it's not, but you can convince the sender to encrypt arbitrary
messages to it, then it's not really very private anyway.

But if this is the scenario, then two facts complicate the attack:
    M and M' must be formatted as OpenPGP packets; and,
    the OpenPGP OFB scheme includes two redundant check bytes.
(I'll explain in more detail in a separate note when I get time.)

The MDC in OpenPGP is really no more than a checksum, intended to
detect accidental damage.  (In fact, during the discussion, I believe
that some folks suggested that it be just a checksum.)  Before the
MDC, there was little ability to detect *any* sort of accident -- not
just truncation, but fairly arbitrary internal damage as well.  (When
the payload is a compressed packet, the decompression might discover
damage, but then again, it might not.)  There was discussion of a
stronger MAC, but I think this was dropped given that OpenPGP has a
strong signature mechanism.

---

From: Jon Callas <[email-masked]>
Date: Wed, 18 Sep 2002 20:25:59 -0700

> strong signature mechanism.

Yes, and no. The MDC is supposed to detect intentional damage as well as
accidental damage. While a checksum was suggested, it was rejected because
it's pretty obvious that would not have the desired characteristics.

It *is* true that the MDC is not and was never intended to be a MAC. The
goal of the MDC is to reliably detect modification of the data in the
envelope, whether by insertion, deletion, or changing it. If an attacker can
do that, then then MDC has failed and we need a new mechanism.

Also note that the MDC's hash is weakly keyed, as there is an "IV" for it
inside the envelope.

If we need to, there are ways we could turn this into a MAC, including a
function over the key, or key+hashkey, or even including an extra MAC key
inside the ESK.

I think there are a number of separate questions around this that include:

(1) Is there a security problem in the MDC as in bis-06?

(2) Should we change it regardless?

Each of those is important. If the answer to (1) is yes, then we need
something. (2) needs to balance existing deployment and so on.

    Jon