RE: [Cfrg] OpenPGP security analysis

Trevor Perrin <Tperrin@sigaba.com> Thu, 19 September 2002 19:33 UTC

Received: from above.proper.com (mail.proper.com [208.184.76.45]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA20023 for <openpgp-archive@lists.ietf.org>; Thu, 19 Sep 2002 15:33:27 -0400 (EDT)
Received: from localhost (localhost [[UNIX: localhost]]) by above.proper.com (8.11.6/8.11.3) id g8JJMEc22758 for ietf-openpgp-bks; Thu, 19 Sep 2002 12:22:14 -0700 (PDT)
Received: from bulwinkle.sigaba.com (bulwinkle.sigaba.com [67.113.238.132]) by above.proper.com (8.11.6/8.11.3) with SMTP id g8JJMCk22754 for <ietf-openpgp@imc.org>; Thu, 19 Sep 2002 12:22:12 -0700 (PDT)
Received: from bsd.sigaba.com (67.113.238.131) by bulwinkle.sigaba.com (Sigaba Gateway v3.5) with SMTP; Thu, 19 Sep 2002 12:15:03 -0700
Received: from exchange1.sigaba.com (exchange1.sigaba.com [10.10.10.10]) by bsd.sigaba.com (8.12.2/8.12.2) with ESMTP id g8JJLXE3022022; Thu, 19 Sep 2002 12:21:33 -0700
Received: by exchange.sigaba.com with Internet Mail Service (5.5.2653.19) id <TA7Z6F62>; Thu, 19 Sep 2002 12:21:23 -0700
Message-id: <2129B7848043D411881A00B0D0627EFEBFB195@exchange.sigaba.com>
From: Trevor Perrin <Tperrin@sigaba.com>
To: "'Jon Callas'" <jon@callas.org>, Michael Young <mwy-opgp97@the-youngs.org>, Trevor Perrin <Tperrin@sigaba.com>, "'David Wagner'" <daw@cs.berkeley.edu>, OpenPGP <ietf-openpgp@imc.org>, cfrg@ietf.org
Subject: RE: [Cfrg] OpenPGP security analysis
Date: Thu, 19 Sep 2002 12:21:21 -0700
MIME-Version: 1.0
X-mailer: Internet Mail Service (5.5.2653.19)
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Sender: owner-ietf-openpgp@mail.imc.org
Precedence: bulk
List-Archive: <http://www.imc.org/ietf-openpgp/mail-archive/>
List-Unsubscribe: <mailto:ietf-openpgp-request@imc.org?body=unsubscribe>
List-ID: <ietf-openpgp.imc.org>
Content-Transfer-Encoding: 7bit



To keep picking at this, the "chosen-ciphertext" attack of Jallad, Katz, and
Schneier could be used in conjunction with a downgrade attack to discover
the prefix block.  The attacker takes the ciphertext of the prefix block
from an integrity-protected message, then incorporates it into a
non-integrity-protected message, preceding it with a block of zeros.  The
receiver naively responds with "what the heck is this", and the decrypted
prefix block.

Now, the attacker can go ahead with his attack of "shuffling" the ciphertext
blocks around, and then recomputing the hash until he finds a collision on
the first bytes of the existing hash, then bit-flipping the last bytes to
match.  There's a lot of caveats to this attack, so it's probably not
anything to seriously worry about:
 - only works if attacker knows all plaintext
 - only works if data is uncompressed
 - only works if data is encrypted with passphrase
   - if public-key signed, it fails
   - if public-key encrypted, then forgeries are trivial anyways
 - only works if preceded by JKS attack
 - only works if the attacker has resources to find collisions on the first
X bytes of the hash, where X could be as low as 4 with probability 1/16, but
would average 11.
 - only allows attacker to move ciphertext blocks around, not to XOR new
strings into the ciphertext (because doing so would introduce a ciphertext
block which the attacker hasn't seen before and thus can't recover the next
CFB keystream block for, so the change would be unpredictable)
 - requires the attacker to make several other changes to the plaintext,
besides his targeted modification, so that he can search for collisions

The "cut-out" attack is where the attacker embeds a PGP literal data packet
+ MDC packet in a larger plaintext, and then cuts out the corresponding
ciphertext after encryption and uses that.  This attack is tripped up by the
prefix block, and by the check bytes with probability 2^-16.  The JKS
attack, as mentioned, could recover the prefix block's plaintext for one of
these illicit ciphertexts.  However then a shuffling attack would be needed
to make the hash match.  And the check bytes are still a problem.  But an
attacker could embed many illicit plaintexts in a single larger plaintext,
and check for many prefix/check bytes matches in a single JKS attack, so the
probability of 2^-16 could be increased.  For example, if an attacker embeds
1000 illicit plaintexts in a larger plaintext, and then cuts out and submits
1000 prefix block / check block pairs in a single JKS attack for matching,
he increases the odds of finding a match, and thus a successful forgery, to
2^-6.

Both the "shuffling" and "cut-out" attacks would be completely foiled by
using a MAC instead of an MDC, since the session key cannot be recovered in
a JKS attack like the prefix block can, and without it an attacker would not
be able to modify things and then recompute the MAC, as he can do with an
MDC.  Also, there may be other ways of stealing the prefix block;
implementors may not realize that integrity depends on its secrecy, so may
be careless with it.

The JKS attack on integrity-protected data would be foiled by using a Key
Derivation Function to derive a new encryption key from the session key, so
that integrity-protected ciphertext could not be "downgraded" and used in a
non-integrity-protected context with the same session key.  John Kane
suggested (off-list) something like:

Version = Sym. Encrypted Integrity Protected Data Packet Version Number
EncKey  = KDF(SessionKey, Version, 0)
AuthKey = KDF(SessionKey, Version, 1)

The version would be revved to 2, and would be incorporated into the KDF to
prevent rollbacks.  For version 2 and higher, a new type of MDC Packet would
be defined that contains an HMAC-SHA1 instead of SHA1.

Trevor


-----Original Message-----
From: Jon Callas [mailto:jon@callas.org]
Sent: Wednesday, September 18, 2002 8:26 PM
To: Michael Young; Trevor Perrin; 'David Wagner'; OpenPGP; cfrg@ietf.org
Subject: Re: [Cfrg] OpenPGP security analysis


On 9/17/02 8:20 AM, "Michael Young" <mwy-opgp97@the-youngs.org>; wrote:

> 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.

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