How exactly would someone crack a private key passphrase?

Question

Lets say for a PGP/GPG pair with a passphrase.

Answer 1

The OpenPGP standard (RFC 4880) defines in section 3.7 a number of String-to-Key (S2K) conversion functions, which are used for password-encrypted messages (i.e. ones without using a public key scheme), as well as for (the secret part) in private keyrings.

Most probably the Iterated and Salted S2K will be used. Its specification includes a hash function algorithm identifier, an 8-byte salt, and a count (encoded in a custom one-byte floating point format, a number between $16 ·2^{6} = 1024$ and $31·2^{21} = 65011712$).

To create the key from a passphrase, salt and passphrase will be alternatedly concatenated until a string of length count is reached (but at least once), and this will be hashed using the hash function. (If the output length of the hash is shorter than the needed key length, multiple such hashes are run, where the data is prefixed with one or more zero bytes.) Of course, the larger count is, the longer this takes (both for legitimate use as well for cracking).

The format of the private key rings itself is not documented there, though it is sensible to assume the format given in section 5.5.3.

Assuming the private key is encrypted (otherwise there would be nothing to crack), look at the S2K specifier byte to know which key derivation function is used, and also which salt (if any).

Now you take your dictionary of passwords (or passphrases, or program which generates candidates), and with each candidate password do this:

• Pass the password together with the salt to the key derivation function to get a key for the used encryption algorithm.
• This key you use with the encryption algorithm to decrypt the private key data.
• Look at the private key - is it a valid private key, and does it fit to the accompanying public key?
• If so, you won, you have the passphrase, and you have the private key. If not, repeat with the next password.

Mikeazo's answer includes some ideas on which passphrases to try.

If the passphrase is any good (and the key derivation algorithm is "Salted and Iterated" with an appropriate high count), you will need a long time for this.

---

Related to this, I found a description of an attack on signature keys stored in this format. It does not need to crack the encryption, but instead does modify the stored (encrypted) private key and then observes one message signed with the modified key.

This does not work on encryption keys (or actually, decryption), and as this attack was from 2001/2002, I suppose it is fixed until now. (I didn't do detailed research on this, comments are welcome.)

Answer 2

Typical ways include

1. Dictionary attack
2. Common modifications of dictionary words
3. Concatenation of dictionary words
4. Brute force