The protecting data at rest problem (PGP and the like) is fundamentally different from protecting data in flight (TLS and the like). In the PGP case adversaries can not affect the choice of algorithm without breaking the fundamental public key cryptography (which is fixed).
Added: depreciated vs deprecated; Thanks. An error I have made before and hopefully will not make in the future.
> In the PGP case adversaries can not affect the choice of algorithm without breaking the fundamental public key cryptography (which is fixed).
Again, this is an error because you've not remembered that an adversary isn't obliged to do what a good actor should do.
Your article explains how Alice gets to be quite sure that Bob would prefer she use a good algorithm, and doubtless as a result the conscientious Alice will use a good algorithm when sending messages to Bob. But alas an impostor sending messages to Bob purporting to be from Alice needn't care about this.
For that impostor it only matters whether Bob's client will foolishly accept the bad algorithm they deliberately picked, not whether Alice might ever have chosen to use that algorithm. Even if it would be quite impossible for the attack to read or modify any messages Alice writes, in this way they may be able to send a message to Bob that seems to be from Alice.
Perhaps the message should say "Hi Bob. Sorry, dreadful problems with PGP again. I had to create a new account, see next mail" followed shortly thereafter by a nice shiny PGP mail from... the impostor's account.
Thus, to defeat such an impostor it is necessary to remove/ disable obsolete algorithms entirely. In principle we could imagine client software that securely separates messages received prior to some cut-off date and permits the use of an obsolete algorithm to read/ verify those messages only, but in practice you're asking far too much and this is likely just to add another exploitation avenue.
I am not sure I understand your scenario in enough detail to understand the actual attack. At any rate the identity is established on the basis of Alice's public key. That is the part that is fixed. If it is, say, 2048 bit RSA then that is what Bob uses to confirm that a particular message is from Alice.
> That is the part that is fixed. If it is, say, 2048 bit RSA then that is what Bob uses to confirm that a particular message is from Alice.
A public key algorithm like RSA doesn't actually operate on large data structures like a whole message. Instead it's used on a digest of the message, a hash.
But the decision of which algorithms to accept for such a digest is up to Bob. So even though Alice wouldn't send a new message using a long obsolete hash, the impostor can present a message which claims to be from Alice using that hash and you apparently are enthusiastic about Bob's client trusting this bogus message.
Because OpenPGP shoves the hash identifier into the structure that actually gets signed with RSA, the impostor cannot easily just mis-attribute a modern signature to an older hash, but they can re-use any signatures they do have with a suitable identifier.
OK, I think I have come up with something that could work here...
1. Alice sends messages signed with a currently good hash (say, SHA512 because that is the current default).
2. The attacker gets a copy of one of those messages (perhaps Alice sent him such a message)
3. SHA512 gets broken in the worst way possible: arbitrary hashes can be produced in a way that is not entirely obvious.
4. The attacker generates a new message. They do it so that the SHA512 hash is the same as the SHA512 hash in the saved message. They then reuse the signature from the saved message to make the new message seem to be signed by Alice.
So my original statement was wrong as you said. It was too general to be true in all cases.
Thank you for the insight. I will likely use it to improve my article(s).
Added: depreciated vs deprecated; Thanks. An error I have made before and hopefully will not make in the future.
Added2: I wrote an article that covers this: https://articles.59.ca/doku.php?id=pgpfan:downgrade