RE: [Cfrg] OpenPGP security analysis

["Hal Finney" <[e-mail]>]

Here's something important.  The latest version of the OpenPGP-bis draft
http://www.ietf.org/internet-drafts/draft-ietf-openpgp-rfc2440bis-06.txt
has got an error with regard to the MDC feature.  In section 5.13 it
says,

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

> From: Trevor Perrin <[e-mail]>
> Subject:  RE: [Cfrg] OpenPGP security analysis
> Date:  Wed, 18 Sep 2002 13:31:27 -0700
> List-Archive: <http://www.imc.org/ietf-openpgp/mail-archive/>
> List-ID: <ietf-openpgp.imc.org>
>
>
>
> [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.
>
> Trevor