In the current implementation of GnuPG, multiple packets of Symmetric-Key Encrypted Session Key Packet are not handled very well.

It only uses the first Symmetric-Key Encrypted Session Key Packet which looks good. "Looks good" means, the first byte of generated/decrypted session key is valid OpenPGP algo number. This detection method is not perfect.

For correct implementation, it should collect all possible DEKs, not only the first one, to try decryption if one of DEKs can decrypt encrypted data packet.

@gniibe Thanks for explaining the background. Are there any ideas for fixing? (e.g. the decrypted content could be checked for a valid packet structure or at least for starting with a valid packet header)

I attached another example, where no session key is encrypted (second variant allowed by RFC 4880). Unfortunately, this results in the same error as reported above.

The corresponding password is "ZXReJSFCQxnf".

The problem here is that trial decryption may cost a lot of time because of the passphrase KDF function which, on purpose, takes long. There is one exception: A simple S2K (algo 0) takes no time and its use makes sense iff the passphrase has been created directly as a random string. However, I do not see the use cases for of a set of many passphrases compared to just use public key crypto.

But that's exactly my use case in DOTS: an easily to create 'decryption puzzle' (including the hardness of iterated and salted S2K) for the serving party in order to make DoS harder. I don't see how public-key crypto can help here. Moreover, I would keep the user interaction as cheap as possible, i.e., copy'n'paste an ASCII-armored message and passwort to GnuPG without importing public keys etc.

What's about adding an option (e.g. --decryption-trials) and a reasonable default value that defines an upper limit on the number of trial decryptions to address your concerns?

Is it possible for your application (DOTS), to specify the packet number for SKESKP, not trying all SKESK packets?

I re-use the option --passphrase-repeat which comes with the integer to specify SKESK packet in question.

I mean, if all SKESK packets should be tried, we need some larger surgery of current implementation.

Unfortunately, for my use case the corresponding SKESK packet number is not known when calling GnuPG.

The idea of such a 'decryption puzzle' as kind of DoS protection relies on the fact, that the decrypting party does not know which of the 256 SKESK packets is valid for the given password. DOTS chooses the postion within the 256 packets uniform at random, i.e., on average 256/2 packets must be decrypted.

If the use of GnuPG (current implementation) is a condition, I think that you could improve the generation of SKESK packets, so that no other passphrase can let gpg misunderstand as it may decrypt encrypted packet.

(1) Use the SKESK packet with encrypted session key (in the format of skesks,asc)
(2) Generate a SKESK packet in the following way

• Generate a session key: SESKEY (= ALGO + real session key)
• Generate a salt: SALT
• Given a passphrase, compute KEK by S2K function to encrypt SESKEY, then we have encrypted SESKEY
• By all other passphrases:
  • Compute its KEK by S2K function using the passphrase and the SALT
  • Decrypt encrypted SESKEY by KEK in the last step
    • In the decrypted bytes, check ALGO is valid OpenPGP algo for encryption
    • Also, check ALGO and the length of SESKEY matches
    • If looks "good" unfortunately (i.e., valid ALGO and meaningful length), go back to generating another SALT

Well, I push a change rG44be675b759d: gpg: More check for symmetric key encryption., and it can be backported to 2.2 branch.

Sorry, perhaps, I misunderstood how SKESK packets are generated in your application.
I was considering there were 256 recipients.

IIUC, there is only a single recipient, but it has 256 SKESK packets, while only a single SKESK is valid and others are all dummy, right?

If it is the case, the following improvement in your application could work. (You need to use full SKESK with encrypted session key.)

• Generate a valid SKESK packet with a passphrase (with some salt, using S2K function to get KEK, and then encrypt the session key by KEK)
• loop to generate other 255 dummy SKESK packets
  • LABEL_AGAIN:
  • for a single dummy SKESK packet, fill random bytes into SKESK packet. Let's call ENC-SESKEY for the part of encrypted session key in this dummy SKESK packet.
  • decrypt the ENC-SESKEY by KEK of valid packet to see if
    • ALGO (the first byte) in decrypted result is 9 (AES-256) or 13 (Camellia-256) (Here, I assume you are using AES-256 for valid SKESK)
    • if yes, go LABEL_AGAIN, we are unlucky
  • Good, use the result as a dummy SKESK packet

IIUC, there is only a single recipient, but it has 256 SKESK packets, while only a single SKESK is valid and others are all dummy, right?

Yes.

If it is the case, the following improvement in your application could work. (You need to use full SKESK with encrypted session key.)

Unfortunately, if I understand correctly, the symmetric-key decryption of ENC-SESKEY by KEK must be called at least 255 times.

I guess that a change of GnuPG's decryption validation will break backward-compatibility with insecure SED packets. Right?

Does encapsulating the above message (i.e. 256 SKESK + 1 SEIPD) into a another short message containing only one valid SKESK and corresponding SEIPD packet may help here? A SEIPD packet could be an indication for the packet parser to switch the decryption validation strategy to a strict mode.

Yes: at least 255 times.

No: if encapsulating helps.

I don't think the change of decryption validation breaks backward-compatibility; It does such a validation anyway, in a different place at "key setup". The change introduces this validation earlier.

The point is: in the current implementation of GnuPG, there is no place to collect&use multiple DEKs, it assumes only a single DEK. And the strategy is picking up the first DEK.

Changing GnuPG to collect multiple DEKs could be done.
But, using multiple DEKs to decrypt a SEIPD/SED packet requires larger surgery, I think. We don't have good internal infrastructure in GnuPG to do that yet. And I don't know how it should work (there is still possibility multiple DEKs decrypt SEIPD successfully. Well, SED always gets success).