RE: [Cfrg] OpenPGP security analysis

Trevor Perrin <Tperrin@sigaba.com> Tue, 17 September 2002 19:16 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 PAA26763 for <openpgp-archive@lists.ietf.org>; Tue, 17 Sep 2002 15:16:12 -0400 (EDT)
Received: by above.proper.com (8.11.6/8.11.3) id g8HJ8OT03526 for ietf-openpgp-bks; Tue, 17 Sep 2002 12:08:24 -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 g8HJ8Nk03522 for <ietf-openpgp@imc.org>; Tue, 17 Sep 2002 12:08:23 -0700 (PDT)
Received: from bsd.sigaba.com (67.113.238.131) by bulwinkle.sigaba.com (Sigaba Gateway v3.5) with SMTP; Tue, 17 Sep 2002 12:01:52 -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 g8HJ8KE3007255; Tue, 17 Sep 2002 12:08:20 -0700
Received: by exchange.sigaba.com with Internet Mail Service (5.5.2653.19) id <TA7Z6D1Z>; Tue, 17 Sep 2002 12:08:16 -0700
Message-id: <2129B7848043D411881A00B0D0627EFEBFB18B@exchange.sigaba.com>
From: Trevor Perrin <Tperrin@sigaba.com>
To: Trevor Perrin <Tperrin@sigaba.com>, "'Michael Young'" <mwy-opgp97@the-youngs.org>, "'David Wagner'" <daw@cs.berkeley.edu>, "'ietf-openpgp@imc.org'" <ietf-openpgp@imc.org>, "'cfrg@ietf.org'" <cfrg@ietf.org>
Subject: RE: [Cfrg] OpenPGP security analysis
Date: Tue, 17 Sep 2002 12:08:15 -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


Another attack, based on the fact that the last block containing part of the
hash is subject to bit-flipping, as David Wagner points out:

Suppose a 16-byte block size is being used, so the last 16 bytes of the SHA1
hash are subject to modification.  This means the attacker can make targeted
changes to the ciphertext, and if he is able to predict what effect these
changes have on the corresponding plaintext, then he can compute what the
new SHA1 hash should be.  If this new hash collides with the old hash in the
first 4 bytes, then he can bit-flip the last 16 bytes of the SHA1 hash to
match.  So the attacker can experimentally try around 2^31 ciphertext
modifications, and odds are one of them will collide with the unmodifiable 4
bytes of the hash, and he'll be able to make a forgery.

With CFB (which PGP uses) and known plaintext, the attacker can make
computable alterations in the plaintext by changing the ciphertext.
Px     (the xth plaintext block)
Px+1   (the x+1th plaintext block)
Py     (the yth plaintext block)
.
..

He can change the ciphertext with predictable results on the plaintext by
setting Cy=Cx.  Then he can compute:
Py   = (Py xor Cy) xor Cx
Py+1 = (Px+1 xor Cx+1) xor Cy+1

Note that the attacker can't control Py or Py+1 with precision, because if
he did targeted bit-flipping on the ciphertext he wouldn't know what that
block was encrypted as.  So this would mostly be useful for overwiting a
particular section of incriminating evidence with random data, or somesuch.


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.

Trevor