PGP Vulnerability Discovered

Bruce Schneier, of Counterpane, sent in the word that a vulnerability has been found in PGP. He attached an explanation below of what's going on, as well as a paper concerning the risks of key escrow.

From Bruce:

PGP Vulnerability

A very serious PGP vulnerability was just discovered. Using this vulnerability, an attacker can create a modified version of someone's public key that will force a sender to encrypt messages to that person AND to the attacker.

Let me explain.

When Network Associates joined the Key Recovery Alliance, they modified PGP to allow for third-party key recovery. They did this by supporting something called an Additional Decryption Key (ADK). Normally, when a PGP user creates a PGP certificate, it contains a single public key (as well as identifying information as to who the key belongs to). PGP version 5 and 6 allow the user to add additional ADKs to the certificate. When a sender encrypts a message to that user, PGP will automatically encrypt the message in both the user's public key and the ADK. The idea is that the ADK belongs to the secret police, or the user's employer, or some organization, and that organization can intercept the encrypted message and read it.

A stupid idea, but that's the sort of thing that Key Escrow demands.

The flaw is that some version of PGP don't require the ADKs to be in the signed portion of the PGP certificate. What this means is that an organization can take a PGP certificate, append his ADK, and spread it out to the world. This tampered version of the certificate will remain unnoticed by anyone who doesn't manually examine the bytes, and anyone using that tampered version will automatically and invisibly encrypt all messages to the organization as well as the certificate owner.

Unfortunately, the problem won't go away until all vulnerable versions of PGP are eradicated: the sender who is responsible for encrypting to the ADKs, not the recipient.

Way back in 1998 a bunch of us cryptographers predicted that adding Key Escrow would make system design harder, and would result in even more security problems. This is an example of that prediction coming true.

Comments

Would Updating Keyservers Help?

[Brian Ristuccia]

Wouldn't the impact of this vunerability be reduced significantly if the various public keyservers were reconfigured to reject keys uploaded with unsigned ADK's?

Re:ADK? Disturbing.

[benedict]

You misread. PGP is not generating an ADK. PGP is *accepting* ADKs that are attached to public key certificates but not signed by the issuer of the certificate.

Here is the exploit sequence: you issue a PGP certificate, containing your public key. You may be not be running a version of PGP with the bug, it doesn't matter. Joe Evil attaches another public key to your certificate as an ADK, and passes it around. Someone who is running the vulnerable PGP uses your certificate to encrypt a message to you. However, they *also* make a copy encrypted with Joe Evil's public key! And they won't even know it unless they examined your certificate manually. Now Joe can read their message.

So the problem here isn't that PGP is attaching an ADK, but rather that someone could later attach an ADK and the tampering would be not detected by someone using the certificate to communicate with its issuer.

--

Explanation of the problem

[sde1000]

The reason that this vulnerability in PGP is serious is that you can't fix it by updating your copy: you have to ensure that everybody who might send you encrypted messages has a copy of PGP without the ADK bug. This is difficult, especially when you don't know who your correspondants are going to be ahead of time.

Here is a summary of Ralf's paper that I wrote while reading it yesterday:

When a PGP key-pair is generated, the public key is stored in a file as a number of typed 'packets': the key itself, a userid, etc. One of these packets is a signature of the previous packets made with the private key, to bind them together (so that, for example, the userid cannot be changed).

In PGP version 3 files, it's as simple as that.

In PGP version 4 files, the signature packet contains some extra fields: two sets of 'subpackets'. One set of subpackets is included in the hash, and therefore cannot be tampered with. The other is not included in the hash.

Some versions of PGP allow "Additional Decryption Keys" to be specified for public keys. They are specified by including the additional key identity in a subpacket in the signature. The idea is that when you create a key pair and sign the public part, you sign the identities of any ADKs that you want to use. This is supposed to prevent ADKs from being specified without the consent of the holder of the private key.

Unfortunately, some versions of PGP respond to ADK subpackets in the non-hashed part of the signature. This is a blatant bug. They treat them exactly as if they were hashed, i.e. they show up as ADKs in the list of 'key properties', and messages encrypted to the public key include packets allowing the session key to be obtained by holders of the ADKs.

Tested versions of PGP:

• PGP-2.6.3ia UNIX (not vulnerable - doesn't support V4 signatures)
• PGP-5.0i UNIX (not vulnerable)
• PGP-5.5.3i WINDOWS (VULNERABLE)
• PGP-6.5.1i WINDOWS (VULNERABLE)
• GnuPG-1.0.1 UNIX (not vulnerable - doesn't support ADKs)

The problem won't go away until all vulnerable versions of PGP are retired, since it's the sender who is responsible for encrypting to the ADKs, not the recipient.

As far as I can tell, nobody has done the experiment of uploading a modified signature packet to a keyserver yet - will it replace the existing signature packet, or be ignored? (Or possibly be stored in addition, in which case more experiments need to be done: what will various versions of PGP do if given keys with multiple self-signatures?)

More followup: I've found the bug in the PGP-6.5.1i-beta2 source code. I'm fairly sure it will be identical in all the other vulnerable versions.

In file libs/pgpcdk/priv/keys/keys/pgpRngPub.c, I see two functions: one called ringKeyFindSubpacket(), which finds a subpacket from a self-signature packet, and ringKeyAdditionalRecipientRequestKey(), which uses ringKeyFindSubpacket() to search for ADK subpackets.

ringKeyFindSubpacket() is declared as follows:

PGPByte const * ringKeyFindSubpacket (RingObject *obj, RingSet const *set, int subpacktype, unsigned nth, PGPSize *plen, int *pcritical, int *phashed, PGPUInt32 *pcreation, unsigned *pmatches, PGPError *error);

In particular, the "phashed" parameter is used to return whether the subpacket was in the hashed region. Now, looking at the call in ringKeyAdditionalRecipientRequestKey() I see this:

krpdata = ringKeyFindSubpacket (obj, set, SIGSUB_KEY_ADDITIONAL_RECIPIENT_REQUEST, nth, &krdatalen, &critical, NULL, NULL, &matches, error);

...the "phashed" value isn't checked (or even asked for)!

Ok - it's an obvious implementation bug, and the bug itself should be easy to fix. I won't comment on the wisdom of designing in ADKs in the first place; the problem now is, how do we get everyone to replace their vulnerable copies of PGP? And, since that won't ever happen completely, how do we minimise the remaining problem?

It should be easy to spot keys that have been tampered with: use gpg --list-packets and look for ADKs in the unhashed section of the self-signature. You can also check to see whether you are receiving messages that have been encrypted to more than one recipient: look for multiple session key packets.

Finally, I recommend that regular sweeps are made of the public key servers for keys that have been tampered with.

Close, but wrong on a couple of key points

[jedinite]

Read the #98 post a little farther down for a better (read: more detailed) summary. It DOES matter what version of PGP you create the key with, and thus your details of the exploit are a little off...

In short, the exploit sequence is as follows:

Alice creates a PGP certificate. This is composed of her public key plus a bunch of other "packets" containing info like UserID, etc. One of these packets is essentially a checksum, containing a signature of the previous packets. In NAI PGP version 5, the ADK packet is included OUTSIDE of the checksum (so you can attach an ADK packet without affecting the checksum (and thus without generating an error message that the key has been tampered with). Alice then uploads her PGP public certificate to the pgp root server.

Carol wants to read any messages to Alice, so she goes out, pulls down Alice's certificate, and adds an ADK packet featuring her own public key. Then Carol uploads the new copy of Alice's key. Because the ADK packet is not included in (not checked by) the signed hash packet, this addition is not noticed as making the certificate invalid.

Now Bob decides he wants to send an encrypted message to Alice, so he pulls her public key from the pgp root server. He gets the latest copy, which is the version with Carol's ADK packet. So when Bob encrypts a message to Alice, it's just like he selected to encrypt the message to Alice and to Carol. So Carol can then intercept the email and decrypt it using her own private key.

---------

Lawsuit

[bwt]

I have copyrighted works under protected with PGP. I did not concent to the TPM I use being circumvented. Bruce's description of this vulnerability is clearly a circumvention technology that will be used to pirate my work and is thereby illegal under the DMCA.

I'm going to file a lawsuit against Bruce and Slashdot and anyone who links to Slashdot and anyone who reads the article and anyone who points at or otherwise refers to a person who reads the article. In fact, Bruce himself is circumvention technology, so I'm suing his parents, too, along with the major airlines, both of which have distributed Bruce.

Re:This is no surprise

[the_quark]

As the programmer largely responsible for 5.0 Unix (flaws and all), I've got to respond to some of this. Some of it is simply not factual, other parts of it contain opinion which I consider to be incorrect. Disclaimer, first - I do not work for NAI or PGP, Inc., and my words are most certainly my own and not theirs.

Point-by-point:

1) "PGP 5.x was, is, and will continue to be a screwup". Your opinion, obviously. I agree some things could have been better with it (especially the Unix version).

2) "They deliberately changed the command line interface to break every PGP-interoperable tool out there." No. *I* deliberately changed the command line interface (with much deliberation) for two reasons: Once Unix development started, we were on a very tight schedule, as the Windows and Mac versions had already been released (see blow). The primary goal was to make it possible for Unix to decrypt the new key formats as quickly as possible. There was not time, under the schedule, to reimplement the 2.x command line item-for-item. Given that we were creating a security application, my opinion was that it was much better to create a new interface and break everything than to try to emulate the old interface and perhaps subtly break other things without complaint. The secondary goal was to improve the interface to be more Unix-like and less DOS-like (note, for example, that under 2.6.2, you can't do something like "pgp -ea president@whitehouse.gov *.txt"). In the end, I suspect my interface failed; I know I didn't have time to think about it, design it or get the input I would've liked. So, it is technically acurate that the change was "to break every...tool out there," but the intent was to prevent subtle security flaws in programs that interoperate with PGP.

3) "They released the Windows version months before the UNIX version." True enough. We were a startup, in those days, and, if you look at Wired Magazine from the same time period, youll find we did significant layoffs at the company around that time. As 5.0 was rolling out, PGP, Inc. was realizing that it didn't really have enough funding to keep going as an independent entity. As a result, we didn't have any resources to devote to Unix. Windows and Mac were our focus because that was what was needed for the corporate clients we needed to keep the business going. Once Windows 5.0 shipped (I was a developer on that, as well), work was begun on 5.0 for Unix. I was the only person on the non-crypto team (who were now busy working on 5.5) who had any knowledge of Unix, so I got to do it all by myself, with essentially no other resources. So, yes, it came out later. We didn't have the people to do it any sooner.

4) "When they finally were releasing the UNIX versions, they were binary-only." In July of 1996, we published the first source-code books, containing the PGP 5.0 source code from the late June releases of 5.0 for Windows and Mac. Our intent with these books was to make the source code available for international review within the constraints of US export law at the time. It took about a month to get them together, as we had to write code to format the books correctly, etc. With every subsequent book, it took less time for the code to be released, as we improved the process. In the July book, we included the "alpha" version of PGP 5.0 for Unix that I was developing, at the time. It had a lot of flaws, but let people see the code. This was scanned in and became available online in late July or early August (if memory serves). Once the final Unix version was released, the code was available in the next source code book. I know we discussed publishing an addendum with the 5.0 Unix code, final version in it, but I don't recall if that happened. The 5.0 Unix source-code book may have been delayed because PGP, Inc. was running out of money, that fall. As I recall, the code itself was completed in September, but it may be true that the code was not actually published for some months, afterward. Again, this was not due to a conspiracy, but due to a lack of funds.

5) [Long rant about publishing the books not making sense]. We did not publish the source code electronically for very specific export-control reasons. At the time, it was illegal (punishable with jail time) to let that type of stuff out of the country. We felt that, as a company, we had a big, fat target on us, and we had to do everything in a completely legal fashion. As I said in number four, I agree that the Unix source code didn't come out as quickly as it could, but that had more to do with a lack of funds than anything else.

6) "They deliberately broke interoperability..." The answer to this one is really simple: Patents. We wanted to release a completely freeware version of PGP. We couldn't, as long as RSA was a requirement. Therefor, we had to move the product off of RSA.

Finally, you complain that "PGP Incorporated is a government shill organization..." Technically speaking, "PGP, Inc." doesn't really exist since they were purchased by Network Associates, Inc. in December of 1997. I'm going to assume what you're trying to get across here is that, earlier in 1997, PGP, Inc. was a government shill organization (as evidenced by its poor support of Unix, apparently).

This was an accusation frequently leveled against us at the time, but which we were not permitted, as employees, to counter. I've never really said anything about it, before, and certainly slashdot is not the kind of place where this is going to be widely read an understood, but:

PGP, Inc. was a lot of things. It was a startup with too much money, too fast, that burned that money too quickly on unimportant things. It made a lot of business decisions, some which I agree with (making Windows a priority, for example) and many of which I didn't. It was quite amusing, at the time, to see how everything we did was considered evidence of a government conspiracy. My wife was the build mistress, and she'd make some trivial change to a README and the next thing you'd know there would be people on Usenet analyzing the wording for proof that the NSA was controlling us.

In the end, PGP, Inc. lasted about a year and a half. I joined in November, 1996, when they had gotten their first financing. Like a lot of other people, I took a significant pay cut to come work on PGP, because of my love of the product and desire to help create a product that would help people protect their privacy and resist tryanny. Almost every employee there (and certainly all the engineers) were there for similar reasons. We did a lot of things that I think we'd change, in retrospect. But I personally lost thousands of dollars in lost wages working for PGP (and got basically nothing in the sale to NAI). The reason all of us were there was to build a company that could take encryption to the masses. The strategy we chose was to do that by selling a product to large corporations.

You may have complaints about what we did. I personally was never happy with PGP 5.0 for Unix, and can understand why others (especially those who actually paid for it) might have complaints about it. But to say that we did it in concert with the government or to aid the government in any way is not just ridiculous, it's offensive. Staring a company from the ground-up is hard, and it's not surprising that we made mistakes. But they were all honest ones.

You're too late

[Vanders]

We have already read all of your Emails. Thank you for your cooperation. Please stay in your seat, someone will soon arrive to collect you for processing. Yours,

MIB

Re:So what's the answer

[ssimpson]

If I read this correctly, only some versions of PGP have this problem with the ADKs. So does anyone know which ones have this problem? Or (better) which ones don't have this problem.

From the authors original message:

PGP-2.6.3ia UNIX (not vulnerable - doesn't support V4 signatures)

PGP-5.0i UNIX (not vulnerable)

PGP-5.5.3i WINDOWS (VULNERABLE)

PGP-6.5.1i WINDOWS (VULNERABLE)

GnuPG-1.0.1 UNIX (not vulnerable)

And am I correct in my assumption that PGP remains OK as long as you don't create an ADK? Or am I misreading the message?

NO! The problem is that ANYONE can create an ADK on the end of your existing PGP public key!

Re:ADK? Disturbing.

[ssimpson]

ADK has been a part of the NAI PGP implementation since v5 (e.g. 3 years ago).

There was a lot of arguing about including this feature, it's been documented in the user manual since v5, it's been talked about on newsgroups etc and it's been documented quite widely.

One saving grace is that the PGP standard (RFC2440) DOESN'T include this feature - so the problem should be fairly confined to users of NAI/PGP.

Again an example of Free OSS being better than the commerical alternatives? ;)

I'm really surprised that anyone who follows PGP to any degree has failed to notice? Anyway, it's documented in my PGP DH vs PGP RSA FAQ at: http://www.scramdisk.clara.net/

Rgds,

Sam

Answers about GnuPG

[ssimpson]

See below a message from A.Back. Basically GnuPG is NOT a victim of this "attack".

> -----Original Message-----
> From: Adam Back [mailto:adam@cypherspace.org]
> Sent: 24 August 2000 15:12
> To: Ross.Anderson@cl.cam.ac.uk
> Cc: ukcrypto@maillist.ox.ac.uk; ietf-openpgp@imc.org
> Subject: Re: Serious bug in PGP - versions 5 and 6
>
>
>
> Ross Anderson writes on uk-crypto:
> > Ralf Senderek has found a horrendous bug in PGP versions 5 and 6.
> >
> > [...]
> >
> > He's written a paper on his work and it's at
> >
> > http://senderek.de/security/key-experiments.html
> >
> > Since NAI joined the Key Recovery Alliance, PGP has supported
> > "Additional Decryption Keys" which can be added to a public key.
> >
> > The sender will then encrypt the session key to these as well as to
> > your main public key. The bug is that some versions of PGP respond
> > to ADK subpackets in the non-signed part of the public key data
> > structure. The effect is that GCHQ can create a tampered version of
> > your PGP public key containing a public key whose corresponding
> > private key is also known to themselves, and circulate it. People
> > who encrypt traffic to you will encrypt it to them too.
>
> Amazing, and really unfortunate. Those of us who invested large
> amounts of effort in ensuring the ADK subpackets were not included in
> the ietf openPGP standard can be pleased we succeeded -- otherwise
> gnuPG and other implementations may now also have contributed to this
> risk. As it is gnuPG doesn't honor ADK requests, and all the rfc2440
> says about them is:
>
> 10 = placeholder for backward compatibility
>
> At the time I was suggesting that if PGP really must insist on
> creating software to escrow communications (the primary argument being
> that people didn't want to lose access to the stored mail as opposed
> to being able to have designated third parties snooping mail in
> transit) they should use storage key escrow.
>
> My main premise was that communication key escrow is too risky because
> an outside attacker gets the plaintext:
>
http://www.cypherspace.org/~adam/cdr/

"Keys used to encrypt email which is transmitted over the Internet are
more valuable to an attacker than keys used to encrypt stored files
because of the relative ease with which an attacker can obtain copies
of emailed ciphertext. Stored encrypted files in contrast are
protected by all the physical security systems the company is relying
on to protect it's paper files, plaintext data stored on disks, and
backup tapes. [...]"

There was also lots of political discussion of how unwise it was for
PGP to create a escrow infrastructure which could as easily be used by
governments as by SEC companies to archive their employees
communications.

And people quoting Phil Zimmermann a few years earlier complaining
about ViaCrypt's PGP4 for business variant which had "escrow" in the
form of a third party "encrypt-to-self" config file setting.

And I believe I recall the NSA or some other US government body
picking up on the CMR / ADK mechanism and holding it up as evidence
against the claim that key recover was complex ... "see PGP did it,
this works".

> It's of scientific interest because it spectacularly confirms a
> prediction made by a number of us in the paper on `The Risks of Key
> Recovery, Key Escrow, and Trusted Third-Party Encryption'
> that key escrow would make it
> much more difficult than people thought to build secure systems.

Yes. It really highlights the truth in the statement about the
new risks introduced by adding key escrow.

Adam