Duplicating PGP Key Signature IDs
#1
I was reading through Phracked magazine (First post in 4 years, jesus it has been a while).

Either way I came across an article that I thought was very interesting.  The original author is f1los0tt1l3 and I'm just sharing/giving my two cents on the article.

Basically you create a keypool with the key information you want, a target's name and email, or just your own information.  Then after creating quite a few keys you run them through his python script that brute forces the signature via the creation time.  After this the key has the uid removed and is patched to make it a valid key.

This key can now be used for things like "signed" phishing emails that are actually valid or even forging git repo commit signatures.  Basically where ever PGP signatures are looked at with short hand you can manipulate.  This can also be used to just have a cool hex code at the end of your own PGP sig.  Either way this puts a hole in PGP v4 and should probably be invalidated like PGP v3.

Well, I back off to go read more Phrack.  Hope all is well and enjoy the article!



|=[ 0x04 ]=---=[ Personalized PGP Key IDs - f1los0tt1l3 ]=---------------=|


|=-----------------------------------------------------------------------=|
|=-----------=[ Personalized PGP Key IDs for fun and profit ]=-----------=|
|=-----------------------------------------------------------------------=|
|=---------------------------=[ f1los0tt1l3 ]=---------------------------=|
|=-----------------------------------------------------------------------=|


---[ Contents

 1 - Introduction
  1.1 - Prior work
 2 - The spec
 3 - The attack
  3.1 - Preparation
  3.2 - The crash
   3.2.1 - Runtime stats
  3.3 - The patch
 4 - Conclusion
 5 - References
 6 - Code

---[ 1 - Introduction

Everybody should be allowed to have his (or someone's) own PGP key ID. Who
doesn't want his PGP key to match his favorite hex nickname or his
target's key for some cheap social engineering? I certainly want, so I
started researching how they are derived and if they could be bruteforced.

Note: when we speak about key IDs here we mean the 4-byte short ones that
everybody love to use. However, given enough processing power (or maybe a
SHA1 ASIC|preimage attack) the process can obviously scale to any key ID
length.

-----[ 1.1 - Prior work

GIYF, right? Well, a couple people tried this and lived to tell the tale
(or, well, decided to make it public) but none of them permitted me to get
a 4096 bit RSA key as I wanted it.

In May 2010, halfdog posted on full-disclosure [1] some Java code that
worked on DSA keys. Not exactly fast or customizable, but hey, it was 3
years ago.

Then, in Dec 2011, Asheesh, a Debian dev particularly fond of his key ID,
found a way to create a new RSA 4096 key with that ID (and a bug in GnuPG
handling of duplicate keys) [2]. He highlighted the disruptive potential
of that and decided not to release the code. Bummer.

But the keyservers carry even older evidence (even if one shouldn't trust
the key creation field, especially on these keys): the first example of
custom IDs I could find is

   pub  1024R/A69AB99CDEADBEEF 1995-09-28

that actually employs a old packet type.

So we are not doing anything truly new, but there's still not a public
method to get an arbitrary key with an arbitrary key ID.

---[ 2 - The spec

So, let's get our hands dirty: grab the OpenPGP spec, RFC 4880 [3], and
look up how are those key IDs derived [RFC 4880 - 12.2].

--------------[ RFC 4880 - 12.2.  Key IDs and Fingerprints ]---------------

  For a V3 key, the eight-octet Key ID consists of the low 64 bits of
  the public modulus of the RSA key.

---------------------------------------------------------------------------

Woah, that easy? No, it's not. Version 3 keys are deprecated [RFC 4880 -
5.5.2], for a bad reason - key IDs collisions, ahem - and a good reason -
MD5. So, as we don't want to build our new shiny RSA 4098 on MD5, let's
move on to V4 keys.

--------------[ RFC 4880 - 12.2.  Key IDs and Fingerprints ]---------------

  A V4 fingerprint is the 160-bit SHA-1 hash of the octet 0x99,
  followed by the two-octet packet length, followed by the entire
  Public-Key packet starting with the version field.  The Key ID is the
  low-order 64 bits of the fingerprint.

---------------------------------------------------------------------------

Great, so what's in a Public-Key packet?

-------------[ RFC 4880 - 5.5.2.  Public-Key Packet Formats ]--------------

  A version 4 packet contains:

    - A one-octet version number (4).

    - A four-octet number denoting the time that the key was created.

    - A one-octet number denoting the public-key algorithm of this key.

    - A series of multiprecision integers comprising the key material.

---------------------------------------------------------------------------

Note: numbers are big-endian [RFC 4880 - 3.1]

So the variable parts are the creation timestamp and the key material. The
key material is a bunch of algorithm-specific MPI [RFC 4880 - 3.2] which
can't be tampered with without changing their value.

One might also try to add garbage to the packet, but implementations strip
it. Bummer.

---[ 3 - The attack

Great, we know what constitutes the key ID, and we know that we can tamper
with the key creation value and/or with the RSA/DSA/Elgamal parameters. I
decided to only loop through the key creation field for a simple reason: I
don't trust a crappy tool written by me with RSA primes selection, in
particular in a scenario like this where a lot of different primes are
needed, as skews can lead to disastrous consequences [4].

After all entropy usage couldn't be optimized much and at least this way
we have the peace of mind of GnuPG generated keys.

So we will simply build a bruteforce on the key creation timestamp value.

-----[ 3.1 - Preparation

Ok, let's dive in. First of all fence your GnuPG env, to avoid cluttering
or damaging your own.

   $ mkdir -m 700 GNUPGHOME && export GNUPGHOME=`pwd`/GNUPGHOME

Now we need to generate a pool of enough keys to have a fair chance of
finding a match, but how many? Well, obviously it depends on the number of
seconds in the time frame we consider acceptable for the key creation time.

Let's dive into some math. Since SHA1 is unbiased each try is independent
and for each try we have a fixed probability of finding a match: one into
the number of different possible suffixes = 1 / 2^32.

So, the only thing that matters is how many tries we can do. This number
is s (seconds in the time frame) * x (number of keys in the pool).

The probability of finding a match in k tries is 1 less the probability of
failing all of them [5] and this last is (prob of failing one) ^ k =
((2^32 - 1) / 2^32) ^ k.

Here are the final formula and a handy table:

           2^32 - 1   s * x          s = seconds in the time frame
 y = 1 - ( -------- )                x = number of keys in the pool
             2^32                    y = probability of a success

 +--------------+------+------+------+------+------+
 | frame \ prob | 0.50 | 0.75 | 0.90 | 0.95 | 0.99 |
 +--------------+------+------+------+------+------+
 |         past |    3 |    5 |    8 |   10 |   15 |
 +--------------+------+------+------+------+------+
 |           5y |   19 |   38 |   63 |   82 |  126 |
 +--------------+------+------+------+------+------+
 |           1y |   95 |  189 |  314 |  408 |  628 |
 +--------------+------+------+------+------+------+

For a fancy 3D graph you can plot the probability on a (years in the time
frame X keys in the keypool) space [6]:

 y = 1 - ((2 ^ 32 - 1) / 2 ^ 32) ^ (60 * 60 * 24 * 365 * a * x)

GnuPG has a convenient function to generate keys in batch mode:

   $ gpg --no-default-keyring --secret-keyring ./secpool.gpg \
   --keyring ./pubpool.gpg --trustdb-name ./trustpool.gpg \
   --gen-key --batch batchfile.txt

   # batchfile.txt
   Key-Type: RSA
   Key-Length: 4096
   Name-Real: Filippo Valsorda
   Name-Comment: f1los0tt1l3
   Name-Email: f1los0tt1l3@phrack.com
   Expire-Date: 0

Note: it does not matter what you set in the Name-* fields, as we are
going to discard the uid to create a validly signed one later.

Set it to run the number of times you want, maybe plug in haveged [7], a
Geiger or a radio producing white noise and... uh, go grab a coffee.

-----[ 3.2 - The crash

Well, now we have our keypool and we need to bruteforce the key ID out of
it. I wrote a Python 3 + Cython parallelizable implementation, crash.py.

Compile the Cython module with (you'll need Cython and OpenMP):

   $ python3 setup.py build_ext --inplace

Note: clang and old gcc versions panicked, I used gcc 4.7.

Then start the bruteforce with

   $ python3 crash.py pubpool.gpg NEWKEYID [0xTIMESTAMP]

where 0xTIMESTAMP is the lowest limit to the creation time, if any.

Want to know something cool? The only thing needed to do the bruteforce is
the pubpool, so you can export it out of your crappy airgapped system and
perform the number crushing on some powerful untrusted machine.

You will hopefully get a result like this

 Current fingerprint: 9b179a2af2f8a744b2214de4eec578f57e61d52a
 Current timestamp: 0x512187c9
 NEW fingerprint: d8efd70f8479432e9158ac27eb56af7c42424242
 RESULT timestamp: 0x1b550652

------[ 3.2.1 - Runtime stats

The bulk of the heavy-lifting involved in this bruteforce is making the
SHA1 hashes, and one of them is done for each timestamp tried. The number
of tries is clearly independent of the width of the time frame, and grows
with the probability of finding a match. The two - probability and tries -
are bound by a simplified version of the formula above.

           2^32 - 1   x
 y = 1 - ( -------- )                x = tries / SHA1 hashes
             2^32                    y = probability of a success

So what matters here is what SHA1 hashrate we manage to get. The crash.py
Cython implementation is quite fast, and achieves 3.0 * 10^6 h/s on a
quad-core 2.3 GHz i7 or 8.3 * 10^6 h/s on a AWS EC2 cc2.8xlarge instance.

Note: this means that a matching key would cost you $0.50 of Spot Instance
as of April 2013.

However, much better can be done: the oclHashcat-plus guys claim a 3.081 *
10^9 SHA1/s on a AMD hd6990 GPU [8]. With an hashrate like that, a match
can be found in a matter of seconds. Writing a high-performance CUDA or
OpenGL implementation is left as an exercise to the reader Wink

Here is a reference table of running times:

 +----------------+------+------+------+------+------+
 |    probability | 0.50 | 0.75 | 0.90 | 0.95 | 0.99 |
 +----------------+------+------+------+------+------+
 |   tries / 10^9 |  2.9 |  5.9 |  9.8 | 12.8 | 19.7 |
 +----------------+------+------+------+------+------+
 |  runtime on i7 |  17m |  33m |  55m |  71m | 110m |
 +----------------+------+------+------+------+------+
 | runtime on EC2 |   6m |  12m |  20m |  26m |  40m |
 +----------------+------+------+------+------+------+
 | runtime on GPU |   1s |   2s |   3s |   4s |   6s |
 +----------------+------+------+------+------+------+

-----[ 3.3 - The patch

Now we have to patch the key. patch.py, incredibly, does exactly so.

First, export the secret key for which you had the match

   $ gpg --no-default-keyring --secret-keyring ./secpool.gpg \
   --keyring ./pubpool.gpg --export-secret-keys OLDKEYID > privkey.gpg

Then run patch.py on it, passing it the "RESULT timestamp" from crash.py:

   $ python3 patch.py privkey.gpg TIMESTAMP > resultkey.gpg

Finally, force gpg to import the key even if the (invalid) bounding
signature has been stripped:

   $ gpg --allow-non-selfsigned-uid --import resultkey.gpg

And restore the bounding signature by creating a new uid:

   $ gpg --edit-key NEWKEYID

   gpg> adduid
   gpg> uid 1
   gpg> deluid
   gpg> trust
   gpg> check
   gpg> save

Note: don't create the new uid as an exact copy of the old, otherwise
deluid will delete both of them from the secret key - it's a GnuPG bug.

Done! You now have your new shiny PGP key with a personal key ID. Export
it to your main GnuPG env or whatever.

---[ 4 - Conclusion

Have fun, there are still many interesting uncatched key IDs out there:
0x11111111, 0xabaddeed, 0xaaaaaaaa, 0xg00d1dea, 0x27182818, 0x14142135...
Please just leave 0x31415926, 0x42424242 and 0x13371337 for me Wink and
don't (publicly) duplicate other people's keys.

Finally, I know what you are searching for: the option is --keyid-format
long Wink

---[ 5 - References

[1] "PGP CPU time wasta (never refer to pgp key using 32bit key-id)"
http://seclists.org/fulldisclosure/2010/May/120
[2] "Short key IDs are bad news (with OpenPGP and GNU Privacy Guard)"
http://www.asheesh.org/note/debian/short...-news.html
[3] "OpenPGP Message Format" - Callas, et al - November 2007
https://tools.ietf.org/html/rfc4880
[4] "Cryptanalysis of RSA with Small Prime Difference" - B de Weger - 2002
http://www.enseignement.polytechnique.fr...ois.Morain
/Master1/Crypto/projects/Weger02.pdf
[5] Complementary event - Wikipedia
https://en.wikipedia.org/w/index.php?tit...did=545752
375#Example_of_the_utility_of_this_concept
[6] y = 1 - ((2 ^ 32 - 1) / 2 ^ 32) ^ (60 * 60 * 24 * 365 * a * x) with a
from 1 to (2013 - 1970) with x from 1 to 200 - Wolfram|Alpha
http://wolfr.am/YxKsTU
[7] haveged - A simple entropy daemon
http://www.issihosts.com/haveged/
[8] oclHashcat-plus - advanced password recovery | Performance section
http://hashcat.net/oclhashcat-plus/
Reply
#2
That's actually really interesting, thank you for sharing.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  AlphaBay Arrests via PGP key Doxing NO-OP 6 10,139 08-16-2017, 02:14 PM
Last Post: Cypher