RE: [Cfrg] OpenPGP security analysis

Trevor Perrin <Tperrin@sigaba.com> Wed, 18 September 2002 23:28 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 TAA03703 for <openpgp-archive@lists.ietf.org>; Wed, 18 Sep 2002 19:28:11 -0400 (EDT)
Received: from localhost (localhost [[UNIX: localhost]]) by above.proper.com (8.11.6/8.11.3) id g8INISx20099 for ietf-openpgp-bks; Wed, 18 Sep 2002 16:18:28 -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 g8INIQk20094 for <ietf-openpgp@imc.org>; Wed, 18 Sep 2002 16:18:26 -0700 (PDT)
Received: from bsd.sigaba.com (67.113.238.131) by bulwinkle.sigaba.com (Sigaba Gateway v3.5) with SMTP; Wed, 18 Sep 2002 16:11:47 -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 g8INIHE3021586; Wed, 18 Sep 2002 16:18:17 -0700
Received: by exchange.sigaba.com with Internet Mail Service (5.5.2653.19) id <TA7Z6195>; Wed, 18 Sep 2002 16:18:10 -0700
Message-id: <2129B7848043D411881A00B0D0627EFEBFB193@exchange.sigaba.com>
From: Trevor Perrin <Tperrin@sigaba.com>
To: "'Hal Finney'" <hal@finney.org>, cfrg@ietf.org, daw@cs.berkeley.edu, ietf-openpgp@imc.org, mwy-opgp97@the-youngs.org, Trevor Perrin <Tperrin@sigaba.com>
Subject: RE: [Cfrg] OpenPGP security analysis
Date: Wed, 18 Sep 2002 16:18:09 -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


This stops both attacks I mentioned, as far as I can tell.  It stops the
first attack (where the attacker embeds an illicit string in the plaintext,
and then later cuts out and uses the corresponding ciphertext), because the
attacker won't be able to predict or control the prefix bytes, so he can't
produce a valid MDC on his embedded string.

The one thing I still see to worry about, is the rollback attack where an
attacker embeds an illicit string in an integrity-protected packet, then
later cuts out and uses the ciphertext as a *non*-integrity-protected
packet.  This requires the attacker also cut out the previous blocksize+2
ciphertext bytes (cause of PGP's CFB resynchronization).  This attack will
only succeed in the 1/65,536 probability the check bytes happen to match.
An attacker could embed lots of illicit strings in a single file, to
increase the odds of this happening, but would have no way of knowing if he
succeeded short of submitting the illicit ciphertexts to the receiver and
observing if they decrypt successfully.

Using a key derivation function on the session key to derive the encryption
key in the integrity-protected case would prevent this attack.  Also
switching from an MDC to a MAC just to be safe still seems a good idea, if
it can be done in a backwards-compatible and rollback-proof way.  I heard a
good suggestion for this offlist, I assume the authors will present it
sometime.  

Trevor


-----Original Message-----
From: Hal Finney [mailto:hal@finney.org]
Sent: Wednesday, September 18, 2002 2:41 PM
To: cfrg@ietf.org; daw@cs.berkeley.edu; ietf-openpgp@imc.org;
mwy-opgp97@the-youngs.org; Tperrin@sigaba.com
Subject: RE: [Cfrg] OpenPGP security analysis


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 <Tperrin@sigaba.com>;
> 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