Is it possible that to sign a message with a PGP key in a way that leakes the key

Question

Alice provides a software for signing messages. The software runs in a airgapped enviroment.

The software is given the message that's to be signed and the private key. The software then produces a signed signed PGP message with the shows the correct public key. Is it possible that the software hides the private key somewhere in the message signature?

Answer 1

PGP signatures, like most modern signature schemes, are not deterministic: that is, signing the same message twice will not result in the same signature. To do this, a random nonce (number used once) is used. The nonce needs to LOOK random, but there is no way of guaranteeing that it is: you could encrypt some data you want to exfiltrate with a fixed key, and it would be indistinguishable from a proper nonce. The signature would still verify, but someone "in the know" could decrypt the nonce to recover the exfiltrated data.

That being said, nonces aren't usually big enough to hold a full private key. You could easily mitigate this by exfiltrating a random segment of the private key with each message; the recipient could then piece back together the key after seeing enough messages.

Edit to follow up: the naive method described above produces the same signature each time, a dead giveaway. It's pretty easy to fix though. The nonce in a protocol is usually long enough to provide cryptographic strength, which is more than enough to include a few random bits to ensure the malicious signature can't be detected. For example, you could split the nonce in half; the first half could be truly random, and the last half could be a portion of the private key encrypted with using the first half as an IV. As a further improvement, the first byte or so of the exfiltrated data could be used as an offset, showing which piece of the key is being leaked in that message.

Answer 2

Yes it is possible. Consider:

signature = sign_message(message, private_key)
// super secret sneaky private key theft
signature = signature + "/" + base64(private_key) 
signed_message = embed_signature(message, signature)

If you want the signature to still validatewith standard gpg --verify, you can alternatively use a Comment or MessageID signature header.

Answer 3

The Debian RNG/DSA flaw actually did exactly allow to do this.

If you use bad random numbers (eg., out of a small range as happened in the Debian flaw) the private key can be calculated out of the signature (by brute-forcing through all possible random numbers). sesse.net has a nice explanation of how it works exactly.

So, use a bad random number generator (for example, returning a constant value instead of a random number) together with DSA keys, and you actually hide the key in the signature. This is possible by performing some minor change in GnuPG and recompiling.

(Comic from XKCD)