PGP key fingerprint spoofing
Well we're all aware of the 0xDEADBEEF attack, right? (PGP keyids, are the 8 hex digit number which PGP recognizes a key by. The 0xDEADBEEF attack (so christened by Greg Rose one of the people who independently rediscovered this attack) is where you generate a PGP key which has the same key id as someone else's key. This could confuse a keyserver, or a user into using the wrong key. This attack is fairly easy to do, just choose p ending in 0xDEADBEEF (or whatever the desired key id is), then start with q ending in 0x00000001, and add some value larger than 0xFFFFFFFF at each iteration doing your primality test, the p and q will then multiply to have the desired least significant bits of n). You may also have noticed that Gary Howland has a keyid of 0xc001d00d ("cool dude", get it). Anyway it seems that you can spoof the finger print also indirectly, which is much less obvious, as the fingerprint is the MD5 hash of the RSA modulus concatenated with the RSA public exponent. This was described recently on coderpunks. (I was forced to eat my words on coderpunks after declaring this was impossible without an exploitable flaw in MD5 or brute force of 2**128 bit search space, when someone explained the concatenation weakness). I'm not sure who it was that discovered this attack, or which list/newsgroup this was announced on, but this was the first I had seen it discussed. The concatenation is the weakness, as if you have an RSA key of: n = 0x1234567 e = 0x11 Then you can try n = 0x12345, and e = 0x6711. So you try factoring each n of this form, and if it has two factors p and q, then you can construct a key with the same fingerprint, but with different key. Anyone who bothers to would be able to factor 0x1234567 also, so it is not secure, but if you can fool someone into using this key in place of the real one, you can get their communications. It will be much easier to fool someone to use this key as the fingerprint is the same! Here's an example... Say we have a 1024 bit key, say e is small ( < 256). That means n || e is 129 bytes long. The e value must be represented by a whole byte. n can't be smaller than 384 bits (or PGP will reject it as too small to hold the required idea message key and padding), so that will give us 80 possible values for e and n. Lets use my 1024 bit key for an example. n = 0x99d61071378ee2c0c8c9c4b7786b203dedf2d6e526f24f7e83f3e0f960fb66b9 cb81c04e89d70689a4866f21ad1bb5ba6aee51469e5b59b121ba6f3f8d776b62 7253ba5dc9fca8155a565b9893f695d83a0496eb977ee4659ee20e0f2eb49b25 93c11487b377cc5d767c79fb985b464d4ae94a5f45e42e3b29c8b89d556a4a67 e = 0x13 So we could try: e = 0x6713 e = 0x4a6713 e = 0x6a4a6713 ... n = 0x99d61071378ee2c0c8c9c4b7786b203dedf2d6e526f24f7e83f3e0f960fb66b9 cb81c04e89d70689a4866f21ad1bb5ba e = 0x6aee51469e5b59b121ba6f3f8d776b627253ba5dc9fca8155a565b9893f695d8 3a0496eb977ee4659ee20e0f2eb49b2593c11487b377cc5d767c79fb985b464d 4ae94a5f45e42e3b29c8b89d556a4a6713 Here's the first candidate I found with only two factors starting from the smallest n value (384 bit n) so that it would be quicker to factorize (anything that took a long time to factor I moved on to next value). n = 0x99D61071378EE2C0C8C9C4B7786B203DEDF2D6E526F24F7E83F3E0F960FB66B9 CB81C04E89D70689A4866F21AD1BB5BA6AEE51469E5B59B121BA6F3F8D776B62 7253BA5DC9FCA8155A565B9893F695D83A0496EB977EE465 e = 0x9EE20E0F2EB49B2593C11487B377CC5D767C79FB985B464D4AE94A5F45E42E3B 29C8B89D556A4A6713 p = 0x6D q = 0x1694DA7CA7DC9B69CD9ECAAC8BCDF6A41988A31132573CFD6EF72CC44FFF5330 69074D8CB3F0974586892A25D2F3A08C19173D406266A82CCA3C3F4D705CAF78 23922972C20D99D8DBF07E2DE20CB5B3B3F747797B3A8D9 n = 0x99D61071378EE2C0C8C9C4B7786B203DEDF2D6E526F24F7E83F3E0F960FB66B9 CB81C04E89D70689A4866F21AD1BB5BA6AEE51469E5B59B121BA6F3F8D776B62 7253BA5DC9FCA8155A565B9893F695D83A0496EB977EE465 d = 0x0455419C3B8CCE54710EC04F9FA61F83A5E2363BE0D2E361886080716E7B8886 EA62B748F20B9E9E7F93F768616D3AF5F8785D514A82EE41CB1FF251FFB053FA 173D0B239D7BD1995B4F7DE3B2B112F911BE1304453EAC53 u = 0x0162AC862E1D88F2ACC3230A4AED13AEC3EA4A978387684ADA099644FF9FAA3D D51F6BA831347C5D12AD1CDC72F5FE40F66228E54573373C4A0F255A091879BC F2EA9509D46B673CB7C4EB8EDA0D6754DC373EA911653504 (Factorization courtesy of pollard rho / trial division code in the factorization code which comes in ssh-1.2.20, which includes a modified gmp-2.0.2 which has the code in the demos directory.) I checked RSA operation (with my .sig rsa program which works with hex numbers rather than formatted pgp keys) -- it works!! % echo hello world | rsa -k=9EE20E0F2EB49B2593C11487B377CC5D767C79FB985B464D4AE94A5F45E42E3B29C8B89D556A4A6713 -n=99D61071378EE2C0C8C9C4B7786B203DEDF2D6E526F24F7E83F3E0F960FB66B9CB81C04E89D70689A4866F21AD1BB5BA6AEE51469E5B59B121BA6F3F8D776B627253BA5DC9FCA8155A565B9893F695D83A0496EB977EE465 > out % % rsa -k=0455419C3B8CCE54710EC04F9FA61F83A5E2363BE0D2E361886080716E7B8886EA62B748F20B9E9E7F93F768616D3AF5F8785D514A82EE41CB1FF251FFB053FA173D0B239D7BD1995B4F7DE3B2B112F911BE1304453EAC53 -n=99D61071378EE2C0C8C9C4B7786B203DEDF2D6E526F24F7E83F3E0F960FB66B9CB81C04E89D70689A4866F21AD1BB5BA6AEE51469E5B59B121BA6F3F8D776B627253BA5DC9FCA8155A565B9893F695D83A0496EB977EE465 < out hello world % I'm off to pack this up as a PGP key, to see if PGP likes it! Well here's that key as a pgp key. Under no circumstances use it to encrypt a message you care about. Here's the public key. Type Bits/KeyID Date User ID pub 704/977EE465 1997/06/08 Adam Back <spoofed fingerprint DO NOT USE> -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.6.3i mQCNAzObE60AAAECwJnWEHE3juLAyMnEt3hrID3t8tblJvJPfoPz4Plg+2a5y4HA TonXBomkhm8hrRu1umruUUaeW1mxIbpvP413a2JyU7pdyfyoFVpWW5iT9pXYOgSW 65d+5GUBSJ7iDg8utJslk8EUh7N3zF12fHn7mFtGTUrpSl9F5C47Kci4nVVqSmcT tCpBZGFtIEJhY2sgPHNwb29mZWQgZmluZ2VycHJpbnQgRE8gTk9UIFVTRT6JAG0D BRAzmxOtOgSW65d+5GUBAQ27ArwOTveQTs0kjzBEMa09yWFs5+jNjv5tzSCngzXO bRzvwhTwWz4voR3ov2o0bGTYZF1biKRKeKqZzHb4Oq4XhD4TADdlmsxA5gQgbYFN 5K+tbgWEDQD53KFv =rlth -----END PGP PUBLIC KEY BLOCK----- Here's the secret half: -----BEGIN PGP SECRET KEY BLOCK----- Version: 2.6.3i lQGhAzObE60AAAECwJnWEHE3juLAyMnEt3hrID3t8tblJvJPfoPz4Plg+2a5y4HA TonXBomkhm8hrRu1umruUUaeW1mxIbpvP413a2JyU7pdyfyoFVpWW5iT9pXYOgSW 65d+5GUBSJ7iDg8utJslk8EUh7N3zF12fHn7mFtGTUrpSl9F5C47Kci4nVVqSmcT AAK7BFVBnDuMzlRxDsBPn6Yfg6XiNjvg0uNhiGCAcW57iIbqYrdI8guenn+T92hh bTr1+HhdUUqC7kHLH/JR/7BT+hc9CyOde9GZW09947KxEvkRvhMERT6sUwAHbQK5 AWlNp8p9ybac2eyqyLzfakGYijETJXPP1u9yzET/9TMGkHTYyz8JdFhokqJdLzoI wZFz1AYmaoLMo8P01wXK94I5IpcsINmdjb8H4t4gy1s7P3R3l7Oo2QK5AWKshi4d iPKswyMKSu0TrsPqSpeDh2hK2gmWRP+fqj3VH2uoMTR8XRKtHNxy9f5A9mIo5UVz NzxKDyVaCRh5vPLqlQnUa2c8t8TrjtoNZ1TcNz6pEWU1BIRbtCpBZGFtIEJhY2sg PHNwb29mZWQgZmluZ2VycHJpbnQgRE8gTk9UIFVTRT4= =lE9S -----END PGP SECRET KEY BLOCK----- Here are the fingerprints of spoofed key as compared to real key. Type Bits/KeyID Date User ID pub 704/977EE465 1997/06/08 Adam Back <spoofed fingerprint DO NOT USE> Key fingerprint = 18 B8 A0 65 9D 38 14 83 61 5A E6 AC 91 8B 9E 57 pub 1024/556A4A67 1993/06/08 Adam Back <aba@dcs.ex.ac.uk> Key fingerprint = 18 B8 A0 65 9D 38 14 83 61 5A E6 AC 91 8B 9E 57 Note the identical fingerprints! (Awesome). Key id of course is different. Also note that you can't decrypt directly with PGP, as I suspected, because the chinese remainder theorem used in decrypt to speed up the works barfs on small p. You can hack around that if you're bothered. It might be possible to find a spoofed fingerprint key with large p and q, so that this was not a problem. Below this post is my real key. This is a major security flaw, and I take my hat off to the guy who discovered it. As others noted (who were aware of this flaw) the solution is to consider the keyid as part of the fingerprint. That reduces by a factor of 2^32 the likelihood of the attack succeeding. I suspect that rules out the attack working for most keys. Also be suspicous of odd sized keys. Now if someones 2048 bit key has a 1024 bit spoof, you're in trouble. I'd be interested in estimates of the likelihood of this being possible for a randomly selected key. You could construct a key where the keyid matched, and the fingerprint matched for two different keys, using a combination of dead beef attack, and brute force to find a key with the keyid appearing two places in the key, and then trying to factor the n value at that point. Shouldn't take long. As far as PGP format goes, adding the length field into the digest would go along way towards fixing it. (Length fields for pgp big int representation is big endian 16 bit word representing length of following big int in bits). There might still be a small chance of doing the fingerprint spoof where the length fields both happened to be right. As you require a specific length field it would seem this attack would be 2^32 times less likely to succeed. This would make most keys safe. I wonder if there exists a key out there which would fall to this attack. (btw for people playing with this stuff, a useful program is pgpacket.pl by Mark Shoulsen, which displays pgp packets as hex numbers, see ftp.ox.ac.uk/pgp somewhere under utils). Adam My real key, so you can compare fingerprints. Type Bits/KeyID Date User ID pub 1024/556A4A67 1993/06/08 Adam Back <aba@dcs.ex.ac.uk> -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.6.3i mQCNAiwUXUEAAAEEAJnWEHE3juLAyMnEt3hrID3t8tblJvJPfoPz4Plg+2a5y4HA TonXBomkhm8hrRu1umruUUaeW1mxIbpvP413a2JyU7pdyfyoFVpWW5iT9pXYOgSW 65d+5GWe4g4PLrSbJZPBFIezd8xddnx5+5hbRk1K6UpfReQuOynIuJ1VakpnAAUT tBxBZGFtIEJhY2sgPGFiYUBkY3MuZXguYWMudWs+iQCVAwUQMiDfwUZRiTErSPb1 AQF/yAP8D1X2eAhXSc0P/X7lCHyBhWCl3pxa6oyGxFBOmUeOGfYna8CpJeMiTmZm akRWDYmJUiXscQUfd9qRv8eAeOtbvM87olSjm56Dlh4gYJFZRxZ6IhHlFJx3mPmp q9PnL+pSC41IIheRBJFzpKGD3LW9+VQwRAx9bXFJYyOFpx7vGJqJAJUCBRAwLhaV fjuD7tLfgD0BAYnfA/0XByiiqDX/cxgWt9syiobJ0TrTKloJcEgzxnKmqHH7rhqn wWGQA2pbWPGW1AwLtkeE+JYyk21YQZZxYWerK3JUi8a/ye4EaaJSs8mcw9YCwdPC Xa0nlalh09/FBEt83l5auNbw+zl9AcrOIGsTQcAr0Vy5nnV9IEfi6WZ3/aQ734kB FQMFEC/gRoaxVzBJFqEkZQEBEXcIAI6z9nUinIomouzB/3v1Fu9+kLOLiva+7Mp1 8UT40FXvHSabXe/cSV1//lnlYHJnfpJCPFSEjGox1pVBp9pLmiJBmubLfUrojIAn FDB081n6kB0B4BKb2rUiNghvT4CzpBZ149g/2NGscRIeQOCYkA2cBxT44v2luuqN 3Ahg9bWu+kjnxUKIK9Da/8D0ur5HiinBDevPiVf3/uoOdZ8F7alxqitBcC5ctIYR tr8fgdQq8is6dbeNxDMraV5vEpEN27AU4xOetymdFUufbU1K6Riw5TVZni9qXAgU ZS3zyFw7wqJ/SWILMWp+99ss921b+GpL+/m6S4j7LTXvFvcfy9aJAJUDBRAv2A0p Kci4nVVqSmcBAcfoA/9Pt3BeJ3TdTtQzb9DNT7LoXiQesYG68lzIl7BZsRvXoi2Q yeCPNc/juTGBnKBHgxZezJCW8TaKdJjNEncv7p+1o+9fwmy9UKWXskh6N+Y0ZlhJ bD0T+8+L+Wxpr6k3dao/GfOnCvw8vpvzDV9lnjtqe2B1mU5eAY76FFtZXvM9xw== =xN9o -----END PGP PUBLIC KEY BLOCK-----
-----BEGIN PGP SIGNED MESSAGE----- I have a question for any of you that may know the answer. This is for a paper I am giving to the Social Security Administration on Tuesday, so I would appreciate any answer I get. If I generate a personal PGP keypair on some machine it takes a specific period of time to do the intensive calculations, let's assume ten minutes for this example. If I needed 10,000 such individual keyspairs for a unspecified authentication attack, does this have to take 10,000 times 10 minutes (over two months with this CPU), or is there a faster way to generate a large number of keypairs to appear to be a large number of people. The larger question is since 10,000 unique written signatures seems to indicate that 10,000 unique individuals exist, would 10,000 unique PGP signatures also seem to indicate that these are not from the same person? -----BEGIN PGP SIGNATURE----- Version: PGP for Personal Privacy 5.0 Charset: noconv iQBVAwUBM5s6qEGpGhRXg5NZAQG0ywIAwM3EOYMTvpxZEJqpsEqGvdAGA35Tjv0I ODzAbs/aoSQ6KWMwmw306GOvfSCGBQDgw5QJ/0ENxFwb+1OFkcA2BQ== =hVvI -----END PGP SIGNATURE----- -- Robert Costner Phone: (770) 512-8746 Electronic Frontiers Georgia mailto:pooh@efga.org http://www.efga.org/ run PGP 5.0 for my public key
-----BEGIN PGP SIGNED MESSAGE----- On Sun, 8 Jun 1997, Robert A. Costner wrote:
I have a question for any of you that may know the answer. This is for a paper I am giving to the Social Security Administration on Tuesday, so I would appreciate any answer I get.
If I generate a personal PGP keypair on some machine it takes a specific period of time to do the intensive calculations, let's assume ten minutes for this example. If I needed 10,000 such individual keyspairs for a unspecified authentication attack, does this have to take 10,000 times 10 minutes (over two months with this CPU), or is there a faster way to generate a large number of keypairs to appear to be a large number of people.
There are a few shortcuts you could take. For instance, instead of finding two random, prime numbers for every key, just keep one prime constant and generate another random prime for each key. This has the disadvantage that any one key factored would allow the other keys to be factored trivially. I know there are other ways, but I'm not very good with number theory. Using this technique, it would take about half as long to generate 10,000 public keys.
The larger question is since 10,000 unique written signatures seems to indicate that 10,000 unique individuals exist, would 10,000 unique PGP signatures also seem to indicate that these are not from the same person?
The basis of PGP is the web of trust. Keys are signed by people who are trusted to be competent and truthful, so the user can be sure to a certain degree that the key really is owned by the person listed in the ID field. There are problems that arise with this simplistic key management system, but I won't reiterate what has been discussed many times before. There are a few papers that discuss this in detail. Here are some pointers: ds.internic.net/internet-drafts/draft-ietf-spki-cert-req-00.txt draft-ietf-spki-cert-structure-01.txt research.att.com/dist/mab/policymaker.ps http://theory.lcs.mit.edu/~rivest/ So the simple answer to this question is that one would not be able to get all 10,000 keys signed, so there would only be one key that could be trusted to belong to that person. Mark -----BEGIN PGP SIGNATURE----- Version: 2.6.3 Charset: noconv iQEVAwUBM5teJSzIPc7jvyFpAQF68wf/YiMlEkZV0axYIAp+WNCGlhuG9JTmu5st 4YUXGvkxwg4icePatfz+yttWfpYEmnSKP/9ZiLAAegsfuWcaK9frnntguUsH5jxE SZMXVWQzIqjW8sTNWY5KtDLbAkNE99gLCbPGq4zaksryzWYwwqOukHFXHFZkKWF6 0sEk3H+AVY5SOCUf/MuNZACc1d6CLsWBHoUl2BFCi0seUcFqdBnEmydIaIyI4fee Kdezl/QPnVWQKBmZVuYfUtIrP+Kc1cD30D7LAqcPd+rr9UkstOv0rsRR5vH2SZwp 7T8MFCeRQx1gs/j4QUvKgS/Y+vYrewTUmjdpADBF70ck0io23z4JZQ== =n5hc -----END PGP SIGNATURE-----
There are a few shortcuts you could take. For instance, instead of finding two random, prime numbers for every key, just keep one prime constant and generate another random prime for each key. This has the disadvantage that any one key factored would allow the other keys to be factored trivially. I know there are other ways, but I'm not very good with number theory.
This would actually not save as much time as it trivially appears to, the main time eater in pgp key generation is a. getting random seeds and mixing to distill randomness, and b. executing the extended euclidean algorithm to find modular inverses. Does anyone know any other speedups? - I`m sure I could think of a few but I`m really not in the mood ;-)... Datacomms Technologies data security Paul Bradley, Paul@fatmans.demon.co.uk Paul@crypto.uk.eu.org, Paul@cryptography.uk.eu.org Http://www.cryptography.home.ml.org/ Email for PGP public key, ID: FC76DA85 "Don`t forget to mount a scratch monkey"
At 07:05 PM 6/8/97 -0400, Robert A. Costner wrote:
If I generate a personal PGP keypair on some machine it takes a specific period of time to do the intensive calculations, let's assume ten minutes for this example. If I needed 10,000 such individual keyspairs for a unspecified authentication attack, does this have to take 10,000 times 10 minutes (over two months with this CPU), or is there a faster way to generate a large number of keypairs to appear to be a large number of people.
The larger question is since 10,000 unique written signatures seems to indicate that 10,000 unique individuals exist, would 10,000 unique PGP signatures also seem to indicate that these are not from the same person?
If you're concerned about legitimacy, independence of keys, etc., then doing them one at a time is the way to go. However, if you're just trying to gen up a bunch of keys to fake your way through an authentication system that wants "different" keys, and you don't mind a bit of coding or code-borrowing, you can do far better. First of all, you can generate 10,000 different RSA keys by generating ~142 prime numbers and using combinations of two of them. Furthermore, you don't need to generate good random numbers to seed the prime number searcher, so you've gone from 10,000 randoms plus 10,000/P(prime) prime searches to 1 random plus 142/P(prime) prime searches. However, your RSA keys may not even need to be that good, depending on the authentication system you're trying to weasel into. RSA uses n=pq, p and q prime, and ed==1 mod (p-1)(q-1), where e and d are relatively prime to n (usually e is a small prime.) So you could pick _one_ pair of primes and 10,000 values of e, if the test doesn't mind that all the (e,n) pairs have the same n, and the e's can be a table of the first 10,000 primes. A cheap test might or might not notice, depending on whether it's using PGP KeyID or fingerprint or some other hash. (Since the keyID is "just the bottom few bits of the modulus", a test using the KeyID would notice -- so you've got to social-engineer them into using a "better" test with the length and fingerprint :-) # Thanks; Bill # Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com # You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp # (If this is a mailing list or news, please Cc: me on replies. Thanks.)
participants (5)
-
Adam Back -
Bill Stewart -
Mark M. -
Paul Bradley -
Robert A. Costner