Slashdot Log In
PGP Vulnerability Discovered
from the keep-an-eye-on-your-key-ring dept.
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.
Re:Question (Score:3)
Only if somebody gets ahold of your public key while you're not looking and modifies it to include the additional decryption key.
Extending the situation, does this problem have any effect if keys are exchanged via some secure channel, where no potentially untrusted third party has access to the keys (and the chance to add an ADK to them)? So, don't trust the keyservers (which I never use) and you'll pretty much be OK as long as you get the public key directly from the person it belongs to?
Sure, so long as that person keeps perfect control of the key. However, if he goes away for the weekend and a spook enters his house and modifies your public key on his machine, you're hosed.
...phil
ADK: Retroactive Detection (Score:3)
ADKs *have* to leave additional encrypted content within the final package--somewhere, they've got to leave the decryption key in a detectable form for an attacker to come in and use to decrypt the one-time 3DES/Twofish/Other Symmetric Cipher Key. Now, it's possible that this internal key material could be stripped from the entire message and a valid hash reconstructed, much as the ADK can be added to a key without changing the overall key hash. But this would surprise and disappoint me--at that point, intent becomes a real question.
I have not intensively analyzed the PGP block format--I've been too busy working on SSH as of late--but it's necessary that *something* new is going to be added to the overall package, and that it's is going to be detectable, possibly without decryption, possibly without even the original public key. Whether it's strippable or not is a question mark, but people shouldn't be saying this is an invisible attack. It can't be.
Brutal, yes. Invisible, no.
Yours Truly,
Dan Kaminsky
DoxPara Research
http://www.doxpara.com
Re:That's why I'm part of the GNU Generation. . . (Score:3)
From what I can make of the section regarding GnuPG, it doesn't warn about the presence of the ADK. However, it places but one session key in the cryptogram, a key only recoverable using the user's private key.
But if you get a contaminated version-4 public key, GnuPG will not warn you about it. You should check any and all public keys that you use as decribed in the article. I'm sure the GnuPG team will not be long in adding functionality to do this automatically.
--
"Where, where is the town? Now, it's nothing but flowers!"
Re:Stand back... Squint... (Score:3)
If you're referring to the fact that the vulnerable versions of PGP were tested running on Windows, you're not seeing a pattern. PGP-5.5.3i and PGP-6.5.1i running on Unix are just as vulnerable.
Hold on (Score:3)
"the sender who is responsible for encrypting to the ADKs, not the recipient."
Thus, if someone with a broken version of PGP sends me encrypted email, they might also encrypt to an adversary. Am I missing something?
Response from a PGP engineer (Score:3)
We're looking into it. I can't say much more than that at this point. As soon as more information is known, I will post it as a reply to this thread. Hopefully, you'll see some official word on it here soon.
-- Rob
Re:Open Source at it's best (Score:3)
GPG, the GNU equivalent of PGP _is_ open source, and does not have this vunerability.
As for the police here in the UK, thats a whole other story, and if you ask me Mr Straw has no idea what problems he is creating for the police in the long term with his RIP bill either... but that's another story for another day.
A couple questions for Mr. Simpson (Score:3)
In your opinion what is a good possible solution for this? Is NAI likely to release a patch? What about a new version which does not include the ADK feature? I can also see how this might be a desired feature for corporations who want to use the ADK's for thier intended use. Is it likely NAI would release a kludge in a vain attempt to keep this feature in the code? What is your opinion of NAI and do you think they'll do the "right" thing?
Obviously with the growing popularity or PKI this can be seen as a good thing or a bad thing. Good in the fact that it exposes an inherent flaw in public key cryptography and might make some people seriously think about the implications of a public key infrastructure. Bad in the fact that a widely used version of PGP has a potentialy serious hole in it. I wonder how long the NSA has known about this one.
How appropriate this quote of yours seems.
"Mary had a crypto key, she kept it in escrow, and everything that Mary said, the Feds were sure to know."
-- Sam Simpson, July 9, 1998
LiNT
Read the entire analysis (Score:3)
Re:ADK? Disturbing. (Score:3)
I just looked in PGP Help. Here's what the item on 'additional decryption keys' says:
Re:So just use "authorized" keys. (Score:3)
ARRGH! Wrong!
This is a hole, a bug, a failiure. It's easily countered by including ADK information in the hashed/signed portion of the key.
This discovery means that EVERY key on public key servers is potentially broken. Hell, any naive users key could have this ADK packet and not even be aware! Using "authorised" keys, whatever that means, isn't a solution.
Sounds like a good job for a virus or IRC bot (Score:3)
It can't really be a virus or IRC bot, but why not a snipped of open source code. Get it out, and everyone scan every key they hold. Scan every key that you know you've put somewhere. Scan every key you use to send. Scan every key you touch.
For that matter, wrap it in with GPG.
While we're at it, send upgrade notices back to anyone who uses the wrong version of PGP to send us mail. Stomp it from the face of the Earth.
So just use "authorized" keys. (Score:3)
I agree this is a problem, but it doesn't render PGP useless.
Just make sure, when you get someone's public key, that it comes from an "authentic" source.
Sue Him ! (Score:3)
Worse even, sites such as Slashdot freely link to this information, destroying a successful business model (namely e-commerce) !
Don't let him get away with it, protect our right to profit !
And while you are at it, imprison all mathematicians who might find ways to break our precious cipher systems by finding a way to factor large numbers
(Sounds stupid, but wouldn't there be legal action in such a case ?
Re:Look at the name (Score:3)
While there haven't been any real structural attacks to PGP, up until this, it is theoretically more likely that structural attacks will work against PGP than standard crypto. Perhaps the NSA has already found a way? Also, traditional PGP uses the RSA encryption algorithm, which, if you follow Distributed.net, gets brute-forced regularly. If you really are scared of the government reading your email, then I doubt PGP will put your fears to rest.
Re:So what's the answer (Score:4)
The problem is that anyone can add an ADK to a public key without affecting the key's fingerprint. In other words, it is perfectly possible for someone to set up a keyserver that adds an ADK for themselves to each key uploaded, and no-one will by any the wiser, unless they examine the key closely.
How they get their hands on the mail encrypted using those keys is of course outside the scope of this post.
Idea: A company could set up an internal auto-ADK-adding keyserver for its employees to use, and of course they have access to the outgoing mail spool.
--
"Where, where is the town? Now, it's nothing but flowers!"
Re:GPG? (Score:4)
GPG [gnupg.org] is based on the OpenPGP standard ( RFC 2440 [isi.edu] ) which doesn't, AFAIK, include "Key Escrow" or "ADK". PGP [pgp.com] seemes to have "added" this feature, perhaps this is what the mean by "multiple recipents" in the E-business product. [pgp.com]
Of course I could be wrong, but that's the way it looks to me
Trust goes one way (Score:4)
This sentence is meaningless. Trust goes only one way. It doesn't mean anything if someone you don't know has signed a key.
I only added signers of keys to until the database was 4000 keys or so.
You're going the wrong way. You should trace the web of trust by looking for keys that are SIGNED BY that key, not keys that SIGN IT. Yes, I know, it's a little more difficult to find all the keys signed by a particular key. You need to download the entire database for that.
The only solution to this is a certified key authority.
According to your logic I could discredit the certificate authority by creating a bogus key and signing the CA's key with it...
----
Re:This is no surprise (Score:4)
Not new or secret (Score:4)
There was a great deal of arguing and discussion in cryptographic circles when this came out. The gist of it is that when you email something from work, you're employer can get sued for it, so employers want the capability to read that email, they are legally entitled to in the US. So they added "enterprise" or "corporate" support to PGP. In the business world it makes more sense then you think, they can also recover messages if you're harddrive crashes and takes your secret key away. If PGP is to ever take hold in that market, and PGP is about making money anymore, then it needs this so called ADK feature.
DO NOT FEAR. KEEP USING PGP and GPG if you're one of the 2% who do! If they include the ADK within the key signature then the problem goes away and it works as designed. ADK is a good thing because it makes the product usable in markets it would otherwise never make it. My fear is that this will be treated like Clipper was, and for some reason people get paranoid about having encryption where an authoirzed third party can decrypt your transimition so the proper thing to do is keep using no encryption because that is some how better.
As a former one of the original cipherpunks and a crypto freak I'm also beginning to come around on escrow and key certifcation services. I've built a key database starting with my keys and the linux kernel key. I only added signers of keys to until the database was 4000 keys or so. "The web of trust" doesn't work, there are lot's of fraudulent and dead keys in there and they are signed by someone who was trusted enough to sign the kernel key, or someone who was trusted enough to sign the key of one of the signers of the kernel key. I only went out 3 hops from the kernel key when I was making the database. If you play 6 degrees of Kevin Bacon with PGP keys and start with Linus and the kernel key you get to a bunch of trash really quickly. (this was all done with keyserver.net) Example: Gandhi (yes, at nonviolent.org) has signed Dave Del Torto's key who has signed Theo Ts'o's key who is a kernel hacker and has signed the Kernel key. There is nothing that prohibits anyone from signing another key, so essentially you can't trust a key simply because it was signed by somebody. The web is a direct graph and the arrows point the wrong way, you can only trust keys you trust enough to sign and you can't draw any conclusion from someone else's signature being on a key. There is also a tremendous amount of garbage in the web of trust.
The only solution to this is a certified key authority. The problem with that is they are a business (better than a governement agency) and they will want to use ADK to cover their ass. I think the risk can be managed to a reasonable point by having multiple companies with checks and balances. I would use a key authority if, a) it was seemless and all my email was encrypted with said key and b) key authority couldn't decrypt my key but a 3 party might be able to with a court order. I still wouldn't use it for encrypting my confessions of sexual peccadillos or my plans to over throw the government but it would be more than acceptable for email which is largely unencrypted now. (So not just can the govenrnment read it but your neighbors, your employer and foreign governments can all read it too.) As it stands, if I was told by a court to decrypt my email and there wasn't an ADK capability, I would go to jail for contempt until I did, so when it comes down to it, if some one wants to forcably read your email and a court agrees you're going to lose that battle either by decrypting it or by going to jail and testing your will.
This isn't a real problem (Score:4)
It's only keyservers that this could occur on. Personally I keep mine on my web pages [a2000.nl], anyone who wants to mail me securely uses that, or the one I mail them...
Rule: Only use keyserver keys for verification of an unknown source, and even then, if it's important don't trust it...
EG I get the CERT key from their web site [cert.org]
It's your security people, don't give it to someone else...
Re:GPG? (Score:4)
Can we ask someone within PGP? (Score:4)
Hans Voss
---
Re:GPG? (Score:4)
ADK? Disturbing. (Score:4)
This is no surprise (Score:4)
PGP 5.x was, is, and will continue to be a screwup.
They deliberately changed the command line interface to break every PGP-interoperable tool out there.
They released the Windows version months before the UNIX version.
When they finally were releasing the UNIX versions, they were binary-only.
Eventually, they got around to releasing the source code to the world. This was supposedly because of legal concerns, but that explanation doesn't really hold water. The binaries were released and restricted to the U.S. The source code was written in book form and exported, then to be scanned in, which was legal. Of course, the binaries made it out of the U.S. in about 45 minutes. The source code could have easily been released and restricted to the U.S., but wasn't. This didn't sound right at the time either.
They deliberately broke interoperability with older versions of PGP, which in effect forced people to upgrade. Because they didn't release source code, people were upgrading with binary-only versions.
Anybody searching the Cypherpunks archives from around the time PGP 5.0 was released can find several large threads on these topics.
So, again, it doesn't come as a surprise that PGP Incorporated is a government shill organization, particularly after they joined the KRAp.
Screw them. They and the government can go fuck themselves.
Re:Can we ask someone within PGP? (Score:4)
Will Price, Director of Engineering, PGP Security, Inc. has been alerted and is looking into it - he expects to report back to PGP-USERS mailing list Thursday.
Re:GPG? (Score:4)
This doesn't apply at all to GnuPG - it doesn't recognise the ADK packet (and it shouldn't - RFC2440 specifies that this packet is simply "placeholder for backward compatibility".
This is worrying, but: (Score:4)
GNUPG [gnupg.org] isn't affected - so those of us who like a software free-as-in-speech don't have an problem.
It can only affect you if you get a key from an untrusted source. For most /.ers this won't be an issue.
So basically, don't panic just yet. Of course, this will no doubt start a number of 'many eyes of open-source' arguments.
Would Updating Keyservers Help? (Score:5)
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. (Score:5)
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 (Score:5)
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:
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 (Score:5)
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 (Score:5)
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 (Score:5)
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 (Score:5)
MIB