[Top] [All Lists]

RE: [Cfrg] OpenPGP security analysis

2002-09-18 14:41:28

Here's something important.  The latest version of the OpenPGP-bis draft
has got an error with regard to the MDC feature.  In section 5.13 it

   The plaintext of the data to be encrypted is passed through the
   SHA-1 hash function, and the result of the hash is appended to the
   plaintext in a Modification Detection Code packet.  Specifically,
   the input to the hash function does not include the prefix data
   described above;

This is wrong; the input to the hash function DOES include the prefix
data.  This is how it is implemented in the commercial PGP version 7.X
(which only reads but does not yet create this packet), and in GnuPG,
which can both create and read it.  I checked interoperability on this
feature with Werner Koch a long time ago and we are both doing it the
same way.  I also just downloaded GPG and looked at the code to make
sure, and it does hash the prefix.

The error is repeated a couple of paragraphs later,

   During decryption, the plaintext data should be hashed with SHA-1,
   not including the prefix data 

The reason this is important is that it can help to prevent these attacks
which involve controlled modification to the plaintext.  Since the hash
includes the block of prefix data, which is hidden to the attacker,
he cannot predict what the hash is before his modifications, even if he
knows the entire message; and nor can he predict what the hash should be
after modification.  So he can't do as Trevor Perrin describes below,
rearranging blocks, or XORing data into an existing message, and then
compensating for his changes by XORing an appropriate value into the hash.

Guessing the prefix block will only have success 2^128 for the AES and
Twofish ciphers where we mostly use the MDC, or 2^64 for the older ciphers
if it is used there.  In either case this is a very low chance of success.

We should correct the draft to accurately reflect the behavior of the
implementations in the field.  Hashing the prefix data improves the strength
of the MDC construction so it is important for security.

Hal Finney

From: Trevor Perrin <Tperrin(_at_)sigaba(_dot_)com>
Subject:  RE: [Cfrg] OpenPGP security analysis
Date:  Wed, 18 Sep 2002 13:31:27 -0700
List-Archive: <>
List-ID: <>

[I apologize for holding a monologue here, just wanted to close this up]

From: Trevor Perrin 

There may other ways of making predictable modifications of 
the plaintext, which can also take advantage of the fact that 
you only need to find a collision on 4 bytes of the hash, then 
can bit-flip the rest.

For example, copying-and-pasting a sequence of ciphertext blocks, or
deleting a sequence, will cause a scrambled block just after each splice
point, but these scrambled blocks will be predictable by an attacker who
knows the plaintext, because CFB mode lets an attacker with known plaintext
reconstruct the keystream block that follows each ciphertext block.  Thus
the situation is similar to Bellovin's cut-and-paste attacks against
non-integrity-protected CBC, with the caveats:

 - the attack requires the attacker know the entire plaintext string, so he
can compute the hash value of the modified plaintext that corresponds to his
ciphertext modifications

 - the attack depends on the attacker trying out a large number of potential
modifications, until he finds one that collides with the first X bytes of
the current hash, where X is the number of hash bytes that reside in all but
the last encryption block, (with a 16-byte block size and 20-byte hash,
X=4,5,6,..,19 with probability 1/16th each)

So in practice the attacker would choose a targeted modification he wanted
to make, then choose some imperceptible modifications that he can make in an
out-of-the-way corner of the document, and search through their permutations
until he finds a collision.