1

I've been wrestling with GPG lately, and I have just (finally!) got it working. I can now input an encrypted blob to gpg.exe and it will output the plaintext version, assuming that it's a valid encryption blob of course, meaning its decryption key is in my list of private keys/"crypto identifies".

My question is: how exactly does GPG determine which of these keys to try? Is that information somehow baked into the encryption blob? Or does it just blindly try them, one by one, until one successfully decrypts it?

It would be nice to finally get this question answered because I've been wondering about it for ages. It feels so "crude" and "low-tech" for it to just go through them all like that. Especially if, for example, I start hosting some kind of service where thousands of people's private keys have to go through to see if a new incoming message matches any of them. It just doesn't seem to "scale".

I sure hope that there's something about the encrypted text which clues GPG in on which key to try! Is that the case?

0

The resulting OpenPGP packet indeed contains the encryption subkey ID of the recipient that is supposed to be able to decrypt it. For example:

$ date | gpg --encrypt | pgpdump
Old: Public-Key Encrypted Session Key Packet(tag 1)(524 bytes)
    New version(3)
    Key ID - 0xCE7B0F19551034EF
    Pub alg - RSA Encrypt or Sign(pub 1)
    ...
New: Symmetrically Encrypted and MDC Packet(tag 18)(83 bytes)
    ...

If there are multiple recipients, then there will be multiple "Session Key" packets – one for each recipient, all of them holding differently encrypted versions of the same symmetric key.

(I think the next version of the specification, v5, is planning to have full subkey fingerprints instead. However, in this situation, the truncated key IDs are good enough.)


That being said, GnuPG does have an option called --throw-keyids, which causes all session key packets to have the same key ID 0x0000000000000000. When that happens, the recipient does indeed try to decrypt the packet by brute force, using all secret encryption-capable subkeys that they have.

There is also a --hidden-recipient option that allows hiding individual recipients the same way, so you can have a mix of null and non-null key IDs in the resulting message. This might be useful for implementing Bcc: carbon copies in email clients.

Both options can be used when you need to exchange messages through something like a public bulletin board / drop box / subreddit and do not want to reveal the intended recipient.

$ date | gpg -e --recipient Alice --hidden-recipient Robert | gpg --list-packets
gpg: anonymous recipient; trying secret key CE7B0F19551034EF ...
gpg: anonymous recipient; trying secret key DCDBB36BD91759A3 ...
gpg: okay, we are the anonymous recipient.
gpg: encrypted with 4096-bit RSA key, ID CE7B0F19551034EF, created 2009-10-31
gpg: encrypted with RSA key, ID 0000000000000000
# off=0 ctb=85 tag=1 hlen=3 plen=524
:pubkey enc packet: version 3, algo 1, keyid 0000000000000000
    data: [4095 bits]
# off=527 ctb=85 tag=1 hlen=3 plen=524
:pubkey enc packet: version 3, algo 1, keyid CE7B0F19551034EF
    data: [4092 bits]
# off=1054 ctb=d2 tag=18 hlen=2 plen=80 new-ctb
:encrypted data packet:
...
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.