PGP Example -- Decrypting a Secret Key
As implied in my previous post, I am investigating how to decrypt PGP messages without using OpenPGP.
I have written a python script that parses a secret key message – that’s the binary PGP message that gpg exports when you run “gpg –export-secret-key ‘Your Name’”.
This script only works with secret keys with the following specs:
- Passphrase hashed with SHA-1
- Secret exponent encrypted with TripleDES
- TripleDES key is ‘salted + iterated’ passphrase.
- Key type is DSA+Elgamal
This is just an adventure in understanding PGP messages. It splits a message into packets, and decrypts the secret keys.
There were two interesting finds here which seem to be undocumented/underdocumented.
Interesting Thing 1 – SHA-1 Hash As TripleDES Key
SHA-1 produces a 20-byte output. TripleDES takes a 24-byte key. OpenPGP dictates that the SHA-1 hashed salt+passphrase be used as the key in TripleDES.
I couldn’t find any explanation of how that’s supposed to work. Not in the RFC, and not anywhere else. So I stepped through the algorithm in gpg2 using gdb and figured out what they do.
UPDATE 2011/11/08: Found this in the RFC, section 3.7.1.1. It’s in a section that I hadn’t read because I implemented the more involved S2K format.
First of all, you have to know that my test key uses the ‘iterated + salted’ method. That means that you read the randomly-generated 8-byte salt from the packet, and concatenate your passphrase:
salt+passphrase buffer: [s0,s1,s2,s3,s4,s5,s6,s7,p0,p1,p2,p3,…,pn]
Then you read the ‘count’ byte from the packet and pass it through the forumla defined in the OpenPGP standard to determine how many bytes you should hash. gpg2 defaults to a count byte of ‘96’, which turns into 65536 bytes to hash.
So you copy your salt+passphrase buffer over and over again:
hashed buffer = [salt+passphrase+salt+passphrase+salt+passphrase….]
The byte count does not have to be a multiple of your salt+passphrase buffer. The last iteration is probably truncated:
truncated ending: [s6,s7,p0,p1…,pn,s0,s1,s2,s3,s4,s5,s6,s7,p0,p1,p2]
And now you run a SHA1 hash on that 65536 byte buffer to get your 20-byte key.
But wait! We need 24 bytes. Where do we get the extra 4 from? Well, here’s what GPG does: add a ‘0’ to the front of the buffer. New buffer is 65537 bytes in this example – identical to the one above, plus a NIL byte at the front.
Hash this second buffer to get another 20 bytes. Take the first 4 bytes of that, append them to the end of the first 20-bytes. 24-byte key is produced.
Interesting Thing 2 - Incompatible With PyCrypto’s TripleDES Implementation
The second finding is that PGP implements TripleDES in some way that is apparently different from how everyone else implements it. I’ve seen this mentioned, but have never found any detailed explanation.
I found that passing the key, initial vector, and encrypted data into PyCrypto’s 3DES function does not work. The decrypted data is invalid.
I wrote a C-extension for Python that passes those same buffers into libgcrypt’s 3DES implementation, and it DOES work.
I did no further investigation into this, other than trying PyCrypto’s MODE_PGP in addition to MODE_CFB. Neither work.
Source Code
If you are interested in such things, the source code for my test is here:
Secret key decrypter (pgp_key_extract.py)
libgcrypt extension (spam.c)
distutils script (setup.py)
Run ‘python setup.py build’, then ‘python setup.py install’. Then run ‘python pgp_key_extract.py <path to secret key file>’.