Can the passphrase of a PGP key be deduced from an old backup?

Question

Let's assume that Bob, at some point in time, has created a PGP (key length and other parameters are not relevant at this point). For some reason, he has chosen a very poor passphrase, for instance lemon. Some time later, Bob realises his poor choice and decides to change his passphrase to something much more secure, for instance There is no doubt that a longer passphrase is more secure than a single word.

There's the catch: At some point before the passphrase was changed, the private key somehow leaked (e.g. due to a not appropriately secured backup scheme or some other mishap). Either way, Eve now has Bob's private key, but not its passphrase. Given the poor choice of the original passphrase, this will just be a matter of time, so for the sake of the discussion let's assume that Eve eventually manages to deduce the passphrase in some way. She thus has both the private key and its passphrase and will be able to decrypt it.

The key itself of course is compromised at this point, this is without question. Eve is certainly able to decrypt her (barely protected) copy of Bob's private key, even if Bob's copy is now encrypted in a different manner (read: new passphrase). So I guess this corresponds to a known plaintext attack on the private key. Will Eve be able to deduce Bob's /new/ passphrase (and thus possibly other keys where he used the same passphrase) in this scenario?

Answer 1

I'm assuming Bob uses the standard format, OpenPGP aka RFC4880, to store his private key in a private keyfile.

If the adversary Eve somehow obtains Bob's private keyfile, and the passphrase on that keyfile is so short and weak that the adversary breaks it with a dictionary attack or brute force, then -- Things are very bad for Bob.

Bob's best choice of action here is to generate a fresh new second private key, tell everyone (possibly by using messages signed by his original private key) to use the new public key and revoke his earlier key. (Yet how will people be able to tell that these messages really came from Bob? Perhaps those messages are actually from Eve, forged to appear as if they came from Bob, telling everyone to use a public key corresponding to a private key known only to Eve. All they can be sure of is that the original key has been compromised and should be revoked).

However, in this scenario Bob inexplicably keeps using his original private key, but re-encrypts it using a good passphrase.

Then Eve somehow obtains Bob's new private keyfile, including the original private key (which she somehow guesses is the same as the private key she extracted from the earlier keyfile) encrypted by Bob's new good passphrase.

Will Eve be able to deduce other secret information, decrypt other things encrypted with Bob's /new/ passphrase, or perhaps even deduce the passphrase itself?

Unlikely.

You are describing a known-plaintext attack: Eve has an encrypted text (the new private keyfile encrypted with the new passphrase) and the corresponding plaintext (the private keys extracted from the old keyfile), and is trying to use that to reveal further secret information.

The standard OpenPGP format encrypts the private keys with (a key formed from a hashed version of) the passphrase using one of several algorithms listed in RFC4880 section 9.2. "Symmetric-Key Algorithms", typically AES.

Known-plaintext attacks were well-known when those algorithms were written. All of those algorithms were specifically designed to be resistant to known-plaintext attacks. They are designed such that even after a Eve obtains hundreds of plaintext+ciphertext pairs, all the ciphertext encrypted using the same "good" passphrase, it is practically impossible for Eve to recover that passphrase or decrypt any other message.

Answer 2

Once Bob's private key is leaked, Bob is screwed. At that point it doesn't matter whether Eve knows Bob's passphrase or not: Eve can decrypt all messages sent to Bob. The only reason a passphrase exists is as a means to an end: to protect the private key. If the private key is leaked, the game is over. So, the question seems poorly motivated or perhaps confused about how passphrases and private keys work.