Jonas' blog

IT security & forensics

RSSTwitterGithub

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])