 |
|
 |
|
|
|||
| |||
OpenPGP flaw prompts quick fix
10 Feb 2005
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?
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?
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?
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?
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?
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
Background Reading
| |||
| |||
