libgcrypt S2K (algo 3) doesn't match OpenPGP
Open, NormalPublic

Description

There is a discrepancy between the iterate-and-salt S2K algorithm in libgcrypt and the OpenPGP specification such that they do not compute the same encryption key for the same passphrase. This makes GnuPG incompatible with other OpenPGP implementations for anything involving itersalt S2K. The issue was first noticed back in 2001 by Keith Ray, but as far as I can tell nothing came of it:

https://lists.gnupg.org/pipermail/gnupg-devel/2001-January/016931.html

I discovered it again independently with my own (partial) OpenPGP implementation after noticing that GnuPG couldn't decrypt some keys depending on the passphrase length.

To review RFC 4880: The iterated S2K is computed concatenating salt+passphrase+salt+passphrase+... until reaching a specific number of octets. This count is encoded as a single byte and only a quantized set of counts can be expressed. If the salt+passphrase length is not congruent with the octet count, it's not to be truncated, the extra bytes are hashed:

The one exception is that if the octet count is less than the size of the salt plus passphrase, the full salt plus passphrase will be hashed even though that is greater than the octet count.

However, libgcrypt truncates it in openpgp_s2k() (cipher/kdf.c:88), resulting in a different key than OpenPGP.

I've crafted an example to demonstrate. This is an S2K-protected OpenPGP private key with the 7-byte passphrase "0123456". GnuPG is unable to import it or use it because of its differing S2K function:

-----BEGIN PGP PRIVATE KEY BLOCK-----
Comment: passphrase=0123456

xYYEXVCUtxYJKwYBBAHaRw8BAQdA3okaWvWpg89u8A7uTkobI/18EaRlik4ox/28
QGp0EcD+CQMI/uFRQCawprv/bl8gQlgtUPIphlnQOrEoh+NfVjkn/sDHHoFvhng+
gylOfYTo6E6bYC3AkEYbS96QQy7bv/ONUer00OpWSwiaQhhxcqDcf80HczJrIGJ1
Z8JhBBMWCAATBQJdUJS3CRA6Md4AMTgMWgIbAwAAANwBAOWUh1bu1EkjmHx3euVG
LgwXVoCDghjtpFZuQaBXK/VBAQCG80n6UKzoiBSozzBSjr+YZrnk5sns62oKLD2W
rzyzCg==
=0dQK
-----END PGP PRIVATE KEY BLOCK-----

The key should be:

f0 8b c6 10 5e 3e 4e d1 d4 99 c9 43 b8 03 34 d0
27 17 92 63 7a 7c 78 87 9d 32 79 2f ba d0 04 9b

But libgcrypt tries to use this key and fails:

b0 d0 dc d7 43 fb 0d 55 1b a8 76 00 49 0b cf ea
0e 32 a4 3b f1 17 6f 41 6c 8f 1e 79 4f 81 dd 51

This (probably incomplete) libgcrypt patch fixes the bug:

--- a/cipher/kdf.c
+++ b/cipher/kdf.c
@@ -75,8 +75,6 @@
           if (algo == GCRY_KDF_ITERSALTED_S2K)
             {
               count = iterations;
-              if (count < len2)
-                count = len2;
             }
 
           while (count > len2)
@@ -85,13 +83,10 @@
               _gcry_md_write (md, passphrase, passphraselen);
               count -= len2;
             }
-          if (count < saltlen)
-            _gcry_md_write (md, salt, count);
-          else
+          if (count > 0)
             {
               _gcry_md_write (md, salt, saltlen);
-              count -= saltlen;
-              _gcry_md_write (md, passphrase, count);
+              _gcry_md_write (md, passphrase, passphraselen);
             }
         }
       else

With this patch applied, the above key works.

If the passphrase just so happens to be the right length, it works out since there are no extra bytes. Here's the same exact key as before encrypted with the 8-byte passphrase "01234567", which, with the 8-byte salt, evenly divides the octet count. It's valid for both OpenPGP and GnuPG:

-----BEGIN PGP PRIVATE KEY BLOCK-----
Comment: passphrase=01234567

lIYEXVCUtxYJKwYBBAHaRw8BAQdA3okaWvWpg89u8A7uTkobI/18EaRlik4ox/28
QGp0EcD+BwMCGwRMmjD1LCn1D23jQawf3RcTQGSii5AZcvSZ16dWplinZBWkpjfi
U6yEVOyp5n21NJrUCtaAT2PAqM70M/wv2AQIEgzj7E6sfnigeYUu+7QHczJrIGJ1
Z4hhBBMWCAATBQJdUJS3CRA6Md4AMTgMWgIbAwAAANwBAOWUh1bu1EkjmHx3euVG
LgwXVoCDghjtpFZuQaBXK/VBAQCG80n6UKzoiBSozzBSjr+YZrnk5sns62oKLD2W
rzyzCg==
=hWlY
-----END PGP PRIVATE KEY BLOCK-----

At this point it's probably impossible to fix this discrepancy since it would break something for nearly every user. It doesn't just affect protection passphrases but GnuPG's symmetric encryption in general. The best you may be able to do is document that GnuPG's exported S2K differs from OpenPGP, and how it differs.

Details

Version
2.2.17
skeeto created this task.Aug 12 2019, 1:25 AM
werner added a subscriber: werner.Aug 12 2019, 10:30 AM

Re-reading the original report from 2001 it seems that PGP and PGP do the same. Back then these were the only OpenPGP implementations (except for that book with the OpenPGP tool based implementation). We did quite some interop testing in the early years by passing OpenPGP data back and forth. So one could assume this is a bug in the specs becuase the specs are for large parts derived from the PGP 5 code base.

Considering that early interop testing, you're probably right that this is a bug in the spec, not GnuPG. Otherwise this would have been pretty obvious long ago. The wording in RFC4880bis hasn't been corrected to match practice, so I should probably report this issue there.

Since posting this, I noticed that the official Golang OpenPGP implementation follows the de facto algorithm, and the commit mentions testing against GnuPG.

werner triaged this task as Normal priority.

I am in charge of editing the current OpenPGP draft, so I will for sure keep an eye on that issue. If would appreciate if you can post your report also to openpgp at ietf org.