Announcement of the ---------------PGP multiple user ID attack--------------- -----summary: This announcement describes a practical attack on PGP. The attack allows an attacker to make a public key appear under an invalid name in the PGP keyring. The attacker can use this to forge signatures, and in the right circumstances to read messages sent to that name. The attack is not a 'life-threatening danger', but can compromise the web of trust system. One should check all keys one imports for unusual extra names. ---name: PGP multiple user ID attack ---discovered by: Sieuwert van Otterloo ---date: september 4 2001 ---Affected: All versions of PGP after PGP 5.0 on all platforms (confirmed with PGP 7.0 on Windows 98 an NT, and PGP 6.0.2 on Win98) ---further info: www.bluering.nl/pgp PGP is a program that delivers privacy by implementing public key cryptography. To communicate, PGP users need each others public keys. PGP implements a web of trust where users can rely on other users signatures to know whether a certain key belongs to a person. Two concepts are very important in this 'web': trust and validity. Trust is about persons: you trust a person if you believe that that person would not cheat on you, will not make any false statement, and will be very careful what she signs. Validity is about keys and the names on it. A key with one name on it is valid if it indeed belongs to the person whose name is on it. Other people can sign such key, and that means that the signer is sure that that key belongs to that name. Validity and trust are completely different concepts. You can trust Alice very much but at the same time doubt whether the key you have was made by her. In this case PGP does not allow you to set the trust value: You can only slide the trust bar if the key is valid. This makes sense, because you cannot say whether you trust the key owner if you are not sure who the key owner is. You can also be certain that a certain key belongs to a person Eve, but at the same distrust her. In that case the key is valid, but untrusted. If a key has two user ID's, there is a problem with determining its validity. One cannot speak about the validity of the key anymore: Both names on the key can be valid independently of another. One should speak about the validity of the two key-name combinations separately, not about the validity of the key. For instance: Suppose a key has two names on it: "Alice " and "Alice ". One could say that the key is valid if the Alice that created the key is the owner of both email addresses. If on the other hand the creator of the key owns neither email address, and is not even called "Alice", then the key is clearly invalid. Things get interesting if the owner of the key owns one of the email addresses, but not the other, and sometimes calls herself Alice. One of the key-userID links is valid, and the other key-userID link is invalid. If this is the case, the key is not completely invalid and not completely valid. It is then not meaningful to speak about the key validity. PGP does not use the concept of key validity internally, and the openPGP standard also does not assume it. All signatures are valid for just one user ID. But the user interface tries to make things simpler than they are: There is a green/gray light indicating the 'key validity', and there is a slider in the key properties window giving the key validity. They use different heuristics to communicate validity to the user: 1) The first strategy is that the first user ID is the most important, and use the properties of this key as the properties of the key. For instance PGP uses the first user ID as the name of the key. 2) The second strategy is to use the most valid user ID. This makes sense: PGP simply ignores the user ID's it knows nothing about. It turns out the PGP mixes these strategies in a very unlucky way, and one can confuse users with this property. To exploit the confusion, a key with two user ID's is needed. Below is a recipe for making such keys. It describes what Eve must do to cheat on Bob. She needs a little assistance from Carol. Carol is a close friend of Bob, and Carol's key is listed as trusted in Bob's keyring. It is a complicated procedure, but it can be done without diving into file format details. The file name suggestions are there to make it easier to refer back to files. It works with any new PGP version: 5,6 and 7. Eve generates a key with the name Alice on it, with Alice's email address, or an address that appears to be Alice's. Eve adds her own name and email address as a second user ID to the key. (click on the key, select keys/add/name) Eve exports the key including the private key somewhere on the computer, under the name temp1.asc. Eve deletes the Alice user ID from the key, and exports the key, now having the name Eve as its only name, without the private key, in the file tocarol.asc. Then Eve deletes her key from her keyring. Eve personally goes to Carol with her public key file tocarol.asc. Carol sees that the key indeed belongs to Eve, so she signs it (,makes the signature exportable), and gives the public key with the signature back to Eve, so she can use the signature to convince other people she is Eve (filename fromcarol.asc). By setting the signature Carol did not declare she trusts Eve, she only declared that the key indeed belongs to Eve. Eve first imports temp1.asc. Then she imports fromcarol.asc. Now she again has one key, with two user ID's. The first one is Alice, so the key has Alice as primary name in the PGP keyring view. The second user ID, Eve, has Carol's signature. Eve exports this key under the name Alice.asc without the private key, and tries to give it to Bob when he is looking for Alice's key. If Bob imports this key into PGP, and tries to verify a signature made with the key, he will see something weird. Please check the screenshot. The dark validity lights are green on a computer screen, and mean valid. The lighter ones are also gray on color screens and mean invalidity. The signature is considered valid, and the signature seems to be made by Alice. What happens is that the key verification window name field uses strategy 1, and gives the first name of the key. The validity light in this window however uses strategy 2, and reasons using the most valid user ID: the second. Bob now falsely believes that the file comes from Alice. We have successfully forged a signature! The other windows also show interesting things. The PGPKeys window shows exactly what it should show: The first user ID is not valid, the second is, and if one takes Alice as the name of the key, then the key is not valid. The properties window however is confused and/or confusing. It shows the name Alice, but the Eve properties: It thinks the key is valid. It even allows raising the trust bar. If Bob raises the trust bar, because he trusts Alice, the first user ID becomes also valid (it is signed by a trusted key, namely itself) and Bob will start encrypting his secret messages to Alice with Eve's key. Eve can now read everything Bob sends to Alice! PGP normally does not allow setting the trust of invalid keys, but here it does. So both the validity and the trust slider are wrong (or one can say the properties window should show a different name. It is the mixing of the two strategies that creates the problem). Experienced and careful PGP users can discover this attack easily. It is also a very daring attack: Eve identifies herself to Carol, and Bob knows her name immediately. For this reasons it is not very likely that someone will do this attack for real. Nevertheless, if someone decided to try it, he or she has a fair chance to get away with it. And once you have fooled Bob, he might sign the key and give it to his friends. If there is one gap in the web of trust, it can spread and infect the whole system (again, it is not likely to happen in real life, but it neither completely unlikely). I think it is an attack with a very good effort/effect ratio: the attackers needs no computing power at all, just a little bit of luck and carelessness. ---Vendor response (Network Associates Incorporated): PGPsdk Key Validity Vulnerability A vulnerability in PGP's display of key validity has been discovered that could allow an attacker to fool users into thinking that a valid signature was created by what is actually an invalid user ID. If the attacker can obtain a signature on their key from a trusted third party, they can then add a second user ID to their key which is unsigned. The attacker must then switch the unsigned false user ID to primary and convince the victim to place the key on their keyring. In such a case, some of the displays in PGP do not properly identify the false user ID as invalid because the second user ID is fully valid. Whenever PGP displays validity information on a per-user ID basis, the display is correct. Thus, attentive users who examine the user IDs of all public keys which they import to their keyrings will immediately notice this problem before it could have any impact. This issue was discovered and reported to Network Associates/PGP Security, Inc. by Sieuwert van Otterloo. This issue has been corrected such that all key validity displays in PGP will properly mark the unsigned user ID as invalid. Hotfixes are now available for the following products: PGP Corporate Desktop v7.1 (MacOS9/Win32) PGP Personal Security v7.0.3 (MacOS9/Win32) PGP Freeware v7.0.3 (MacOS9/Win32) PGP E-Business Server v7.1 (Linux/Solaris/AIX/HPUX/Win32) Product upgrades are available for the following products: PGP E-Business Server v6.5.8x (OS/390) PGP E-Business Server v7.0.4 (Linux/Solaris/AIX/HPUX/Win32) The hotfixes and upgrades can be found at: http://www.pgp.com/naicommon/download/upgrade/upgrades-patch.asp Network Associates/PGP Security Inc. has published the PGPsdk source code in electronic form for academic and cryptographic peer review. The source packages can be downloaded from: http://www.pgp.com/downloads/default.asp ---Recommendations: Check keys you import. Check both the slider and the validity column. If they disagree, something is wrong. Distrust keys with multiple user ID's that are very different. Also check who signed which user ID. If one does this, the attack above will be detected. If so, Bob can ask Carol who Eve is and the attacker's identity will be discovered. For this reason it is unlikely government agencies and secret services will use this attack. But hackers might take the risk. ---More information This attack has been discovered by Sieuwert van Otterloo, mathematics student at the university of Utrecht, the Netherlands. Current homepages are go.to/sieuwert and www.bluering.nl. My email address is sieuwert@bluering.nl. Phone +31 6 155 24 227 The attack is described in my paper: "A security analysis of PGP" This paper is a full report on the inner workings of PGP and describes all known PGP bugs and the outcomes of a source code analysis. It is available at www.bluering.nl/pgp .