RE: [Cfrg] OpenPGP security analysis

Trevor Perrin <> Wed, 18 September 2002 20:43 UTC

Received: from ( []) by (8.9.1a/8.9.1a) with ESMTP id QAA29478 for <>; Wed, 18 Sep 2002 16:43:19 -0400 (EDT)
Received: by (8.11.6/8.11.3) id g8IKVjE12946 for ietf-openpgp-bks; Wed, 18 Sep 2002 13:31:45 -0700 (PDT)
Received: from ( []) by (8.11.6/8.11.3) with SMTP id g8IKVek12932 for <>; Wed, 18 Sep 2002 13:31:40 -0700 (PDT)
Received: from ( by (Sigaba Gateway v3.5) with SMTP; Wed, 18 Sep 2002 13:25:07 -0700
Received: from ( []) by (8.12.2/8.12.2) with ESMTP id g8IKVZE3016724; Wed, 18 Sep 2002 13:31:37 -0700
Received: by with Internet Mail Service (5.5.2653.19) id <TA7Z61TG>; Wed, 18 Sep 2002 13:31:28 -0700
Message-id: <>
From: Trevor Perrin <>
To: Trevor Perrin <>, 'Michael Young' <>, 'David Wagner' <>, "''" <>, "''" <>
Subject: RE: [Cfrg] OpenPGP security analysis
Date: Wed, 18 Sep 2002 13:31:27 -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
Precedence: bulk
List-Archive: <>
List-Unsubscribe: <>
List-ID: <>
Content-Transfer-Encoding: 7bit

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