ECDH with AES-128 decryption failure when fully padded
Closed, ResolvedPublic

Description

GPG fails to decrypt a message that was encrypted using

  • an ECC key with Curve 25519
  • AES-128 symmetric encryption
  • padded to 40 bytes

The error message is strongly misleading (at least was misleading us for a while):

gpg: public key decryption failed: Wrong secret key used
gpg: decryption failed: No secret key

We would like to pad to 40 as allowed by RFC 6637, section 8:

The input to the key wrapping method is the value "m" derived from
   the session key, as described in Section 5.1 of [RFC4880], "Public-
   Key Encrypted Session Key Packets (Tag 1)", except that the PKCS #1.5
   (Public-Key Cryptography Standards version 1.5) padding step is
   omitted.  The result is padded using the method described in [PKCS5]
   to the 8-byte granularity.  For example, the following AES-256
   session key, in which 32 octets are denoted from k0 to k31, is
   composed to form the following 40 octet sequence:

       09 k0 k1 ... k31 c0 c1 05 05 05 05 05

   The octets c0 and c1 above denote the checksum.  This encoding allows
   the sender to obfuscate the size of the symmetric encryption key used
   to encrypt the data.  For example, assuming that an AES algorithm is
   used for the session key, the sender MAY use 21, 13, and 5 bytes of
   padding for AES-128, AES-192, and AES-256, respectively, to provide
   the same number of octets, 40 total, as an input to the key wrapping
   method.

Obviously, if the sender MAY pad up to a total of 40 bytes, this means that the recipient MUST take this into account and process such a padding properly. In addition to that, a padding of up to 40 bytes should be possible so the encrypted payload would not broadcast any information about the key size. That is why we consider this a bug in GnuPG.

Let me know if you want me to provide any example data.

Note that it seems this problem has been describe before in https://dev.gnupg.org/T3763 but it seems it wasn't rated a bug under the given circumstances which it should be. Indeed, I must admit that I don't really understand the conclusions made in the other issue as being "a bug in the spec not GnuPG".

Edit:
I should add that GnuPG pads AES-128 to only 24 bytes which, in the light of the above said about not making the key size obvious, IMO should be changed as well.

Broccoli created this task.Apr 6 2020, 10:37 AM
Broccoli updated the task description. (Show Details)Apr 6 2020, 10:39 AM
werner added a subscriber: werner.Apr 6 2020, 12:21 PM

EdDSA is sign only - how do you want to encrypt to such a key? Did you mean cv25519 and ECDH?

Of course, you are absolutely correct. I'll update the text accordingly. I thought EdDSA and EcDSA would be expressing differences between Cv25519 and NIST-256. I am not an expert. :-)

FYI, this how the key was generated:

$ gpg --expert --full-gen-key
gpg (GnuPG/MacGPG2) 2.2.17; Copyright (C) 2019 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
   (7) DSA (set your own capabilities)
   (8) RSA (set your own capabilities)
   (9) ECC and ECC
  (10) ECC (sign only)
  (11) ECC (set your own capabilities)
  (13) Existing key
Your selection? 9
Please select which elliptic curve you want:
   (1) Curve 25519
   (3) NIST P-256
   (4) NIST P-384
   (5) NIST P-521
   (6) Brainpool P-256
   (7) Brainpool P-384
   (8) Brainpool P-512
   (9) secp256k1
Your selection? 1
Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 0
Key does not expire at all
Is this correct? (y/N) y
Broccoli renamed this task from EdDSA with AES-128 decryption failure when fully padded to ECDH with AES-128 decryption failure when fully padded.Apr 6 2020, 1:55 PM
Broccoli updated the task description. (Show Details)
gniibe triaged this task as Normal priority.Apr 8 2020, 2:20 AM
gniibe claimed this task.
gniibe changed the task status from Open to Testing.

Thanks for your report. The problem of GnuPG was that it mandated padding length < 16 bytes, which is wrong.

Fixed in master and 2.2 branch.

werner added a comment.Apr 8 2020, 4:07 PM

FWIW, the code was written by the author of the specs and he note in his original patch (rGe0972d3d96) :

/* Allow double padding for the benefit of DEK size concealment.
  * Higher than this is wasteful.  
 */

That's odd. :-)

Could you guide me to where I find the beta or snapshot, so I could test it and give you feedback? I seem to be unable to find it on my own.

werner added a comment.Apr 9 2020, 6:44 PM

There are no betas; either you apply the patch mentioned above ( rG2f08a4f25df7) to a stock 2.2.20 or you build from the Git repo (STABLE-BRANCH-2-2, see https://gnupg.org/download/git.html).

werner closed this task as Resolved.Jul 9 2020, 1:15 PM