Subject: [Cfrg] OpenPGP security analysis

From: David Wagner <[email-masked]>
Date: Sat, 14 Sep 2002 22:02:16 -0700 (PDT)

Greetings,

I've been reading the OpenPGP RFC's, and I noticed a few areas where the
design uses some cryptographic practices that look a bit dubious to me.
I'd like to propose that we ask the ITRF Crypto Forum Research Group
(CFRG; see http://www.irtf.org/cfrg/) to help with analyzing whether
these could pose security issues in practice for OpenPGP.

In particular, I have some concerns about message integrity issues in
OpenPGP's symmetric-key encryption formats.  This issue has bitten PGP in
the past.  Witness Gary Howland's attack (Aug 1997), the "Czech attack"
(2001), and Jallad, Katz, and Schneier's attack (2002).  It has also
bitten other standards: lack of message integrity created exploitable
security holes in IPSec (e.g., Bellovin's troubling cut-and-paste attacks)
and in 802.11 WEP.  It's a subtle area where it is easy to make mistakes,
and I suggest we ask for help from the cryptographers understanding
whether this is ought to be a concern for OpenPGP.

The aforementioned attacks exploit the complete lack of message integrity
in PGP's earlier encryption formats.  The latest OpenPGP RFC (2440bis)
proposes using Hash-then-Encrypt as a defense, with an unkeyed SHA-1
hash as the MDC.  See Section 5.13 of RFC2440bis.  In other words,
the plaintext is encrypted to something like
    CFB-encrypt(random || plaintext || SHA1(plaintext)).

Unfortunately, Hash-then-Encrypt has known security weaknesses, in
general.  For instance, there is a chosen-plaintext attack that lets
you truncate a ciphertext without detection.  See, e.g.,
  http://www.cs.berkeley.edu/~daw/my-posts/mdc-broken
Other attacks are known.  See the readings below.

For this reason, the usual advice today is to use Encrypt-then-MAC (or
some other IND-CCA2-secure scheme).  Unfortunately, back in 1999 when
message integrity was discussed, people on the OpenPGP mailing list
didn't seem to realize that a MAC is needed or that an unkeyed hash
(MDC) is insufficient.  However, we've had sufficient warning of the
need for message integrity (since 1997 or so), so we might as well get
it right now.

It is not clear to me whether the weaknesses of Hash-then-Encrypt apply to
OpenPGP, or even if they do, whether they will have any practical impact
on OpenPGP.  It is entirely possible that OpenPGP might be perfectly safe.
However, I think this could use some further analysis.  What do you say?

Other security concerns:
  -  The receiver is not required to check that the MDC is correct.
     This could expose implementations to the JKS attack.
  -  If the received MDC is invalid, the receiver is not required
     to warn the user or to drop the packet.  This could expose
     implementations to the JKS attack.
  -  If no MDC packet is present (which should be a fatal security
     error), the receiver is allowed to ignore this.  This could
     expose implementations to the Howland or JKS attack.
These can be fixed by changing a few "SHOULD"s to "MUST"s, and I propose
making this change to the RFC.

(In addition, I noticed that in CFB mode, the last block is completely
unprotected against bit-flipping attacks.  The last block is used to
encrypt the SHA1 hash of the plaintext, and of course the SHA1 hash
is longer than the last block, so there doesn't seem to be any obvious
way to exploit this.  I don't see any attacks based on this property,
but I thought I'd point it out in case anyone else does.)

In summary, I'd like to suggest we encourage cryptographers to analyze the
new OpenPGP encryption format to analyze whether it provides sufficient
message integrity protection to prevent future attacks.

Further reading, for the interested:
  http://www.ietf.org/internet-drafts/draft-ietf-openpgp-rfc2440bis-06.txt
  http://www.cs.berkeley.edu/~daw/my-posts/use-a-mac
  http://www.cs.berkeley.edu/~daw/my-posts/mdc-broken
  http://www.cs.berkeley.edu/~daw/my-posts/mdc-broken2
  http://www.cs.berkeley.edu/~daw/my-posts/use-etm
  http://www.usenix.org/publications/library/proceedings/sec02/black.html
  http://www.imc.org/ietf-openpgp/mail-archive/msg02177.html
  http://cert.uni-stuttgart.de/archive/ietf-openpgp/2001/03/msg00033.html
  http://www.imc.org/ietf-open-pgp/mail-archive/msg01756.html
  http://www.imc.org/ietf-openpgp/mail-archive/msg01670.html

Thanks for your attention.

-- David Wagner
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Trevor Perrin <[email-masked]>
Date: Tue, 17 Sep 2002 09:49:55 -0700

>From: Michael Young [mailto:[email-masked]]
>
>[snip]
>
>Assuming the usual PGP public key model, the attacker doesn't need the
>sender to participate in this plan.  In this scenario, the attacker
>can alter message traffic from sender to receiver, so he could simply
>replace a message with is own well-formed PGP message.  
>Nothing new here.

Good point.  If the message is being secured with a passphrase instead of
the recipient's public key, however (which OpenPGP supports), the attack is
more serious, since the attacker would not normally be able to forge
passphrase-encrypted messages.

>
>This assumes that the receiver's public key is really public.
>If it's not, but you can convince the sender to encrypt arbitrary
>messages to it, then it's not really very private anyway.

The messages might not be totally arbitrary.  You might send a seemingly
innocuous (Word or PDF or XML or JPEG or whatever) document to Alice, and
say "forward this to Bob".  Alice reads the document and it looks fine, but
in some hidden field you've squirrelled away a more insidious message which
you plan on cutting out and using later.

>
>But if this is the scenario, then two facts complicate the attack:
>    M and M' must be formatted as OpenPGP packets; and,
>    the OpenPGP OFB scheme includes two redundant check bytes.

I believe the redundant check bytes reduce the probability of this attack
succeeding to 2^-16 when the insidious message is not located at the
beginning of the innocuous-looking message.  The attacker would have to cut
out the ciphertext block previous to where he spliced in his evil message,
and claim this is the ciphertext of the prefix block.  When the legitimate
recipient decrypts this first block, using CFB with an IV of 0, it will
produce bytes that are random from the attacker's perspective, and thus the
attacker won't have been able to anticipate and set the check bytes
appropriately.  If the attacker tries to modify the check bytes by bit
flipping the ciphertext and then submitting multiple tries to the recipient
until they match the prefix bytes, these modifications will be fed into CFB
and will destroy the next block of plaintext, thus invalidating the MDC
(even though the check bytes themselves aren't part of the MDC).

If the attacker places the evil message bytes at the very beginning of the
innocuous-looking message, then this caveat doesn't apply cause the sender
will set the check bytes appropriately, and the attacker just needs to
truncate.

>(I'll explain in more detail in a separate note when I get time.)
>
>The MDC in OpenPGP is really no more than a checksum, intended to
>detect accidental damage.  (In fact, during the discussion, I believe
>that some folks suggested that it be just a checksum.)  Before the
>MDC, there was little ability to detect *any* sort of accident -- not
>just truncation, but fairly arbitrary internal damage as well.  (When
>the payload is a compressed packet, the decompression might discover
>damage, but then again, it might not.)  There was discussion of a
>stronger MAC, but I think this was dropped given that OpenPGP has a
>strong signature mechanism.

The security note at the bottom of page 65 in the current draft indicates
that this MDC is a security feature, and is intended to provide message
integrity.
http://www.ietf.org/internet-drafts/draft-ietf-openpgp-rfc2440bis-06.txt

It stills seems like switching from SHA1 to HMAC-SHA1 would yield the
desired level of security, possibly using a key derivation function on the
session key to generate seemingly-independent encryption and authentication
keys, though I'm not sure if that's necessary.

Trevor

---

From: Trevor Perrin <[email-masked]>
Date: Tue, 17 Sep 2002 10:24:39 -0700

>    M and M' must be formatted as OpenPGP packets; and,

you're right, this does complicate the attack - it means that in the simple
truncation attack (where the evil message ciphertext is just a truncation of
the innocuous message ciphertext) the decrypted literal packet data length
will be wrong.

Unless there's a way to get around that, the only attack I see, then,
requires the attacker to inject make-believe check bytes and OpenPGP packet
formatting, and thus will succeed with probability only 2^-16 cause the
check bytes will probably turn out wrong. 

Trevor

---

From: Trevor Perrin <[email-masked]>
Date: Tue, 17 Sep 2002 12:08:15 -0700

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

---

From: Trevor Perrin <[email-masked]>
Date: Wed, 18 Sep 2002 13:31:27 -0700

[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

---

From: Trevor Perrin <[email-masked]>
Date: Wed, 18 Sep 2002 16:18:09 -0700

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:[email-masked]]
Sent: Wednesday, September 18, 2002 2:41 PM
To: [email-masked]; [email-masked]; [email-masked];
[email-masked]; [email-masked]
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 <[email-masked]>
> 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>
>
>
>

---

From: Trevor Perrin <[email-masked]>
Date: Thu, 19 Sep 2002 12:21:21 -0700

To keep picking at this, the "chosen-ciphertext" attack of Jallad, Katz, and
Schneier could be used in conjunction with a downgrade attack to discover
the prefix block.  The attacker takes the ciphertext of the prefix block
from an integrity-protected message, then incorporates it into a
non-integrity-protected message, preceding it with a block of zeros.  The
receiver naively responds with "what the heck is this", and the decrypted
prefix block.

Now, the attacker can go ahead with his attack of "shuffling" the ciphertext
blocks around, and then recomputing the hash until he finds a collision on
the first bytes of the existing hash, then bit-flipping the last bytes to
match.  There's a lot of caveats to this attack, so it's probably not
anything to seriously worry about:
 - only works if attacker knows all plaintext
 - only works if data is uncompressed
 - only works if data is encrypted with passphrase
   - if public-key signed, it fails
   - if public-key encrypted, then forgeries are trivial anyways
 - only works if preceded by JKS attack
 - only works if the attacker has resources to find collisions on the first
X bytes of the hash, where X could be as low as 4 with probability 1/16, but
would average 11.
 - only allows attacker to move ciphertext blocks around, not to XOR new
strings into the ciphertext (because doing so would introduce a ciphertext
block which the attacker hasn't seen before and thus can't recover the next
CFB keystream block for, so the change would be unpredictable)
 - requires the attacker to make several other changes to the plaintext,
besides his targeted modification, so that he can search for collisions

The "cut-out" attack is where the attacker embeds a PGP literal data packet
+ MDC packet in a larger plaintext, and then cuts out the corresponding
ciphertext after encryption and uses that.  This attack is tripped up by the
prefix block, and by the check bytes with probability 2^-16.  The JKS
attack, as mentioned, could recover the prefix block's plaintext for one of
these illicit ciphertexts.  However then a shuffling attack would be needed
to make the hash match.  And the check bytes are still a problem.  But an
attacker could embed many illicit plaintexts in a single larger plaintext,
and check for many prefix/check bytes matches in a single JKS attack, so the
probability of 2^-16 could be increased.  For example, if an attacker embeds
1000 illicit plaintexts in a larger plaintext, and then cuts out and submits
1000 prefix block / check block pairs in a single JKS attack for matching,
he increases the odds of finding a match, and thus a successful forgery, to
2^-6.

Both the "shuffling" and "cut-out" attacks would be completely foiled by
using a MAC instead of an MDC, since the session key cannot be recovered in
a JKS attack like the prefix block can, and without it an attacker would not
be able to modify things and then recompute the MAC, as he can do with an
MDC.  Also, there may be other ways of stealing the prefix block;
implementors may not realize that integrity depends on its secrecy, so may
be careless with it.

The JKS attack on integrity-protected data would be foiled by using a Key
Derivation Function to derive a new encryption key from the session key, so
that integrity-protected ciphertext could not be "downgraded" and used in a
non-integrity-protected context with the same session key.  John Kane
suggested (off-list) something like:

Version = Sym. Encrypted Integrity Protected Data Packet Version Number
EncKey  = KDF(SessionKey, Version, 0)
AuthKey = KDF(SessionKey, Version, 1)

The version would be revved to 2, and would be incorporated into the KDF to
prevent rollbacks.  For version 2 and higher, a new type of MDC Packet would
be defined that contains an HMAC-SHA1 instead of SHA1.

Trevor

-----Original Message-----
From: Jon Callas [mailto:[email-masked]]
Sent: Wednesday, September 18, 2002 8:26 PM
To: Michael Young; Trevor Perrin; 'David Wagner'; OpenPGP; [email-masked]
Subject: Re: [Cfrg] OpenPGP security analysis

> strong signature mechanism.

Yes, and no. The MDC is supposed to detect intentional damage as well as
accidental damage. While a checksum was suggested, it was rejected because
it's pretty obvious that would not have the desired characteristics.

It *is* true that the MDC is not and was never intended to be a MAC. The
goal of the MDC is to reliably detect modification of the data in the
envelope, whether by insertion, deletion, or changing it. If an attacker can
do that, then then MDC has failed and we need a new mechanism.

Also note that the MDC's hash is weakly keyed, as there is an "IV" for it
inside the envelope.

If we need to, there are ways we could turn this into a MAC, including a
function over the key, or key+hashkey, or even including an extra MAC key
inside the ESK.

I think there are a number of separate questions around this that include:

(1) Is there a security problem in the MDC as in bis-06?

(2) Should we change it regardless?

Each of those is important. If the answer to (1) is yes, then we need
something. (2) needs to balance existing deployment and so on.

    Jon