PGP CTO Blog

OpenPGP flaw prompts quick fix
10 Feb 2005

Today, cryptographers Serge Mister and Robert Zuccherato from Entrust released a paper outlining an attack on the way OpenPGP does symmetric cryptography. They have been kind enough to give the OpenPGP community advance notice of their paper, and it is thus the subject of this CTO Corner article, which I'm writing in cooperation with David Shaw of Gnu Privacy Guard (GnuPG), Brian Smith of Hush Communications, Derek Atkins of the OpenPGP Working Group, and Phil Zimmermann. In it, we'll discuss:

• What this discovery means to OpenPGP users
• Details of the attack and how it works
• What software and standards developers are doing about it

We in the OpenPGP community feel strongly about the quality of our work and appreciate the trust the world places in us. OpenPGP is arguably the most used and most relied-upon cryptosystem for messages and files. Consequently, it is our obligation to describe any problems with the standard and proposed resolution of those problems.

What does this discovery mean to OpenPGP users?
If you use an OpenPGP-based program such as PGP® solutions, Gnu Privacy Guard, or Hushmail to encrypt and decrypt emails or files, Mister's and Zuccherato's discovery does not affect you. If you use related systems such as PGP® Disk, it also does not affect you because PGP Disk does not use the OpenPGP encryption format for disk volumes.

We know of no real-world application that is affected by this type of attack. It is an attack that requires the active participation of someone who holds the actual key required to decrypt a message. Thus, it is not something you are likely to see.

If, however, you are using an OpenPGP-based program that is part of an automated system that takes encrypted data, decrypts the data block, and gives feedback to the submitter about whether the data block was properly decrypted, then you may be affected. Again, we know of no real-world systems that are affected, but we can mentally construct applications that might be affected.

How does the attack work?
When an OpenPGP program encrypts bulk data, it encodes a "quick check" in the encrypted data so that when the data is decrypted, it can tell that the key it is using to decrypt is (probably) the correct one. The encryption starts with some random bytes, 16 of them for AES and Twofish and 8 for other ciphers. The last 2 bytes of this "initialization vector" are repeated as the quick check. So if those random bytes in the initialization vector were "12345678," then there would be another "78" after them. When the message gets decrypted, the OpenPGP program checks for that 2-byte stutter. If they aren't there, then it knows the symmetric key being used is not the right one.

This quick check is a handy thing to have in a cryptosystem, particularly one that is used to encrypt large amounts of data and particularly if the data is encrypted with a passphrase. If you have a gigabyte of data, it's handy to know that the wrong key is being used a few bytes into the process. This quick check, however, leaks information to a suitable attacker, and it is this information leak that Mister and Zuccherato brilliantly exploit.

Their attack makes use of a metaphorical entity called an "oracle." An oracle is some entity that answers questions about a security system. For example, let's take the case of a website that accepts a username and password. Let's suppose that you're trying to use it and you try some users and passwords. After you try the user of "Alice," you get the error message, "No such user Alice." The same thing happens when you try "Bob." But when you try "Charlie," you get the error message, "Bad password for user Charlie." Ah hah! You now know there is no Alice or Bob on this website but there is a Charlie. The oracle has told you that through its overly helpful error message.

Oracles constructed via overly helpful error messages are the bane of many security systems. A few years ago, there was an SSL problem caused by overly helpful error messages. Mister's and Zuccherato's attack uses an oracle that takes an OpenPGP message and replies back about whether the quick check worked or not.

Suppose you have a message encrypted to me that you want to attack. You take the message and make some changes to it, but keep the session key of the message. You then send that message to me. When I try to decrypt it, it will probably fail the quick check (the odds are 1 in 65,536 that it will pass the quick check). Let's suppose that I reply back to you, telling you that the message you sent to me failed its quick check. Suppose you then send me another message and another. After a few of these, let's suppose I respond that the message you sent me successfully decrypted, but that it's complete garbage. Like the overly helpful website, I've just told you something interesting. I've told you that the message you just sent me passed its quick check.

Mister and Zuccherato use this information leak to pry 2 bytes out of the message. They can then slide forward to the next cipher block (either 8 or 16 bytes) and repeat the attack, prying out another 2 bytes. In their work on a single 1.8GHz Pentium computer, they can get 2 bytes with about 2 hours of CPU time and repeat the attack. A different implementation of the attack would depend on network delays and so on for the amount of actual effort needed to mount the attack effectively.

If you are interested in the details of how they cleverly construct these messages, read their paper (for a link, see "Background Reading"). It's excellent cryptanalytic work.

How practical is this attack?
In the case where the oracle is a human being, this isn't a practical attack. That is why we started off by telling you it probably doesn't affect you. Let's face it: If someone starts sending me lots of bogus emails in the hope that I'll let them know which ones pass the quick check and which don't, they sorely overestimate my patience and underestimate the size of my to-do list. I'll get tired long before they get to a dozen of these messages, let alone the 30,000+ typically needed (or 65,536 needed to guarantee the success). The same is probably true for you, too.

Also remember that the attack requires the participation of someone who has the key to the message under attack. If someone finds a discarded OpenPGP-encrypted file (or intercepts an email), that person cannot attack the message by itself. Instead, the attacker must persuade an entity that can decrypt the message to leak information about damaged copies of it. Consequently, your files and emails are safe unless you're somehow conned into being an oracle.

However, it is possible that an automated system could supply the required oracle. For example, consider a hypothetical mailing list server that allowed messages to the list to be encrypted to a list key. If the mailing list server supplies the right information, it's possible that you could pry out information about one of the messages someone else sent to the list.

A particularly clever part of this attack is that it's possible to use timing as the oracle. Suppose that when this mailing list server was given a tampered message it always replied "bad message," but most of the time took 5 seconds to reply and occasionally replied in a tenth of a second. This timing difference is the information leak needed to be an oracle.

However, even in this case, there is still more protection. OpenPGP typically compresses messages. (This attack bootstraps itself by looking for the headers of compressed data.) Therefore, even when someone has part of a message, it is not likely to be useful because it is merely a snippet of a compressed message.

The bottom line is that this is an important cryptanalytic attack. It is important enough that we are going to the trouble of telling you about it. It is important enough that we're going to fix it in software and propose changes to OpenPGP. It is not so important, however, that you need to worry about the safety of your encrypted data because it relies on using someone who has the key to the message to be the required oracle.

What are we going to do about it in software?
Mister and Zuccherato offer a simple way to defend against their attack: don't do the quick check. If there is no quick check, there is no oracle, and thus no problem.

On the other hand, the quick check is there for a reason: If there is a lot of encrypted data, it's nice to know up front that you have a bad key. However, in the case of an OpenPGP message that is encrypted using a public key (which then has symmetric data), there's no need to do the quick check because the symmetric key comes from a public key encryption. OpenPGP encrypts the bulk of the message with a symmetric key and then encrypts that symmetric key with a public key. When the process is reversed, we don't really need the quick check. Its value comes when data is directly encrypted with a symmetric key, such as one created from a passphrase.

Consequently, PGP Corporation, GnuPG, and Hush Communications are all disabling the quick check for all public key-encrypted messages and files. However, we are all presently leaving it in for symmetric (passphrase) encrypted messages and files because we believe the benefit of the quick check is greater than the security risk from it. You will see this change in the next software release from each group.

What are we going to do in the standard?
When the OpenPGP group started in 1997, we improved the cryptosystem based on what had gone before, particularly in demoting MD5 as the hash function we used and shifting instead to SHA-1. We improved the protocol in 1999, and years later were glad we did. Last summer, in 2004, when MD5 was thoroughly broken, we were glad again that we'd changed hash functions.

In our discussions with Mister and Zuccherato about their attack, we asked if they thought we should revise the protocol to address the problem. They told us they didn't think it was necessary-that an explanation of the issue and how to avoid it was good enough.

As implementers of OpenPGP systems, however, we think we should update the protocol. People trust OpenPGP because we handle issues before they become real-world problems. We are suggesting in the working group that we amend OpenPGP so there is a new symmetric encryption system that has a secure quick check. We are suggesting a roll-forward mechanism as well so that when you install a new package that has the revised cryptosystem, you will automatically start using it. We firmly believe in solving problems while they are still impractical, before they become practical attacks. We know that you rely on OpenPGP for information safety and security, and we must therefore be vigilant with your trust.

Jon Callas, PGP Corporation
David Shaw, Gnu Privacy Guard
Brian Smith, Hush Communications
Derek Atkins, IETF OpenPGP Working Group Chair
Phil Zimmermann

Background Reading

Mister, Serge and Robert Zuccherato, "An Attack on CFB Mode Encryption As Used By OpenPGP," Cryptology ePrint Archive: Report 2005/033, 8 Feb 2005