Subject: RE: [Cfrg] OpenPGP security analysis
From: Trevor Perrin <[email-masked]>
To: Trevor Perrin <[email-masked]>, "'Michael Young'" <[email-masked]>, "'David Wagner'" <[email-masked]>, "[email-masked]'" <[email-masked]>, "[email-masked]'" <[email-masked]>
Date: Wed, 18 Sep 2002 13:31:27 -0700
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