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: [email protected]
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
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: [email protected]
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