Create nice gpg keys part 2
My goal is to create a nice key id like 0x33333333 for my new pgp fingerprint.
This key id is the last 4 byte (=32 bit) of the SHA1 hash over the public key packet. For the structure of a pgp packet see this post.
Calculate nice key id
Ok in the first try I could generate about 1.25 pgp keys per second on my machine. Which is slow! Really slow! But after some time I got it up 75000 pgp keys per second.
The problem in the first try was that I created a new key pair on every try. This creation is quite slow. Faster is keeping all the RSA configurations and only to change the creation date. This way we can get to the amount of thousands of key calculations per second till I find a nice key.
The problem is that you change the date all the time, so you might calculate a key for 1992 or any point in the past. I choose to calculate keys for the last 10 years. If you are not happy with the results you can create a single new key via gpg and than start over changing the creation date again for more results.
Signature
The problem with having a new creation date, is that the signature packet must be recalculated.
You need to decrypt you private RSA key, which was encrypted with the CAST5 cipher in my case. Afterwards you need to assemble the right information to be signed and calculate the signature. I described the calculation of the signature in an earlier post.
Script & my new key
I wrote a some python scripts to create those keys semi automatically. See below for the code.
Finally I calculated my own new pgp key: 0x22222222
gpg_key_gen.py
from subprocess import Popen, PIPE
gen_str = '''Key-Type: default
Subkey-Type: default
Name-Real: Cugu
Name-Email: cugu@cugu.eu
Expire-Date: 2014-06-30
Passphrase: 1234password
%pubring foo.pub
%secring foo.gpg
%commit
'''
Popen(['gpg', '--status-fd', '1', '--no-tty', '--batch', '--gen-key'],
stdout=PIPE,
stdin=PIPE
).communicate(input=gen_str)
gpg_forge.py
# Requires:
# ========
# - python-pgpdump (https://github.com/toofishes/python-pgpdump)
# - pycrypto (https://www.dlitz.net/software/pycrypto/)
# Usage:
# ========
# 1. Create a pgp key:
# > python gpg_key_gen.py
# 2. Find a timestamp for a nice key id:
# > python gpg_forge.py find foo.gpg
# 3. Create valid gpg key for the given date:
# > python gpg_forge.py create foo.gpg PASSWORD DATE
# 4. Import forged key into keyring:
# > gpg --import KEYID.gpg
# 5. Create new subkeys for the key in gpg keyring.
# Known issues:
# ========
# - Length of auth_packet (name + email) is fixed to 19 (0x13)
# - Messy, uncommented code
# - No parallelization
import time
import sys
import binascii
import os
from Crypto.Cipher import CAST
import hashlib
import pgpdump
def get_packets(filename):
with open(filename, 'rb') as fileobj:
rawdata = fileobj.read()
data = pgpdump.BinaryData(rawdata)
return list(data.packets())
def new_public_key(new_ts, old_pk_data):
content = "\x04" + new_ts + old_pk_data
content = content.split("\xFE\x03\x03\x02")[0]
pk = "\x99\x01\x0D" + content
return pk
def new_secret_key_packet(new_ts, old_pkt):
pk = "\x95\x03\xBE\x04" + new_ts + old_pkt.data[5:]
return pk
def fingerprint(key):
return hashlib.sha1(key).hexdigest()
def create_sig_hash(auth_packet, new_ts, pk_packet, sub_exp):
auth = "\xB4\x00\x00\x00\x13" + auth_packet
#auth = "\xB4\x00\x00\x00\x1E" + auth_packet
data = "\x04" + "\x13" + "\x01\x0A" + "\x00\x27" + "\x05\x02" + new_ts + "\x02\x1B\x03" + "\x05\x09" + sub_exp + "\x05\x0B\x09\x08\x07\x03" + "\x05\x15\x0A\x09\x08\x0B" + "\x05\x16\x02\x03\x01\x00" + "\x02\x1E\x01" + "\x02\x17\x80"
#print ''.join('{:02x}'.format(x) for x in data)
trailer = "04" + "FF" + ("%0.8X" % len(data))
data = pk_packet + auth + data + binascii.unhexlify(trailer)
h = hashlib.sha512(data).hexdigest()
return h
def create_sig(auth_packet, new_ts, pk_packet, n, d, sub_exp):
hx = "0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003051300d060960864801650304020305000440" + create_sig_hash(auth_packet, new_ts, pk_packet, sub_exp) + "L"
m = eval(hx)
sig = pow(m, d, n)
#print sig.bit_length()
hexsig = hex(sig)[2:-1]
if not len(hexsig)%2 == 0:
hexsig = '0' + hexsig
return bytearray.fromhex(hexsig)
def create_new_sig(new_ts, new_id, old_pkt, auth_packet, pk_packet, n, d):
sub_exp = old_pkt.subpackets[2].data
sig = create_sig(auth_packet, new_ts, pk_packet, n, d, sub_exp)
siglength = int(''.join('{:02x}'.format(x) for x in sig),16).bit_length()
#print siglength
s = "\x89\x01\x3D" + old_pkt.data
ct = bytearray.fromhex(hex(old_pkt.raw_creation_time)[2:])
s = s.replace(ct, new_ts)
s = s.replace(old_pkt.subpackets[-1].data, new_id)
s = s.split(new_id + old_pkt.hash2)[0] + new_id + old_pkt.hash2
s += binascii.unhexlify("%0.4X" % siglength)
s += sig
return s
def create_key(filename, passwd, date):
packets = get_packets(filename)
d = get_d(packets[0], passwd)
n = packets[0].modulus
new_ts = bytearray.fromhex(date)
pk = new_public_key(new_ts, get_packets(filename)[0].data[5:])
new_long_id = hashlib.sha1(pk).digest()[-8:]
s = new_secret_key_packet(new_ts, packets[0])
auth_packet = packets[1].data
s += "\xB4\x13" + auth_packet
#s += "\xB4\x1E" + auth_packet
s += create_new_sig(new_ts, new_long_id, packets[2], auth_packet, pk, n, d)
s += "\x9D\x03\xBE" + packets[3].data + "\x89\x01\x25" + packets[4].data
x = binascii.hexlify(new_long_id)
with open(x + ".gpg", 'w') as f:
f.write(s)
f.close()
print "created " + x + ".gpg"
def count(i):
expbias = 6;
return (16 + (i & 15)) << ((i >> 4) + expbias);
def get_d(pkt, passwd):
key = passwd.encode('utf-8')
ls = pkt.data.split(pkt.s2k_iv)[0][-1:]
ct = count(int(''.join('{:02x}'.format(x) for x in ls),16))
sa = pkt.data.split(pkt.s2k_iv)[0][-9:-1]
salt = ''.join('{:02x}'.format(x) for x in sa)
h = binascii.unhexlify(salt) + key
isp = []
while (len(isp) * len(h) < ct):
isp.append(h)
h = ''.join(isp)
h = h[:ct]
ciphertextba = pkt.data.split(pkt.s2k_iv)[1]
ciphertexths = ''.join('{:02x}'.format(x) for x in ciphertextba)
ciphertext = binascii.unhexlify(ciphertexths)
hexkey = hashlib.sha1(h).hexdigest()[:32]
key = binascii.unhexlify(hexkey)
pos = 0
plaintext = ''
iv = ''.join('{:02x}'.format(x) for x in pkt.s2k_iv)
blockp = binascii.unhexlify(iv)
cipher = CAST.new(key)
while len(ciphertext) > (8 * pos):
decblock = cipher.encrypt(blockp)
blockp = ciphertext[pos * 8: pos * 8 + 8]
for i in range(len(blockp)):
plaintext += chr(ord(blockp[i]) ^ ord(decblock[i]))
pos+=1
return int(binascii.hexlify(plaintext[2:258]), 16)
def find_dates(filename):
packets = get_packets(filename)
old_pk_data = get_packets(filename)[0].data[5:]
old_ts = packets[0].raw_creation_time
old_ts = binascii.unhexlify("%0.4X" % old_ts)
nice = ['00000000', '11111111', '22222222', '33333333', '44444444', '55555555', '66666666', '77777777', '88888888', '99999999', 'AAAAAAAA', 'BBBBBBBB', 'CCCCCCCC', 'DDDDDDDD', 'EEEEEEEE', 'FFFFFFFF', '13371337', 'DEADBEEF', '63756775', '1253D4C3', '4D11B685', '12345678', '01234567', '6B49EF8F', '5E056DAA', 'B830021B', '2D1A1B1B']
starttime = time.time()
i = 0
findings = []
while i < 10*365*24*60*60:
hexts = binascii.hexlify(old_ts)
pk = new_public_key(old_ts, old_pk_data)
sk = hashlib.sha1(pk).hexdigest()[-8:]
if(sk in nice):
findings.append((sk, hexts))
print "################## Found fingerprint %s" % sk
print "################## for timestamp %s" % hexts
os.system('say fingerprint found')
if i % pow(10,6) == 0: # print info every 10 billion keys
print "%s keys created in %s seconds (%s, %s)" % (i, int(time.time()-starttime), hexts, sk)
i += 1
old_ts = int(hexts, 16)-1
old_ts = binascii.unhexlify("%0.4X" % old_ts)
print "%s: %s " % (i, time.time()-starttime)
if __name__ == "__main__":
if len(sys.argv) > 2:
if sys.argv[1] == "find":
find_dates(sys.argv[2])
if len(sys.argv) > 3:
if sys.argv[1] == "create":
# filename, passwd, date
create_key(sys.argv[2] , sys.argv[3], sys.argv[4])