Possibly incorrect counter overflow handling for AES-GCM

[Clemens.Lang at bmw.de]

Hi,

I believe we have found what seems to be a bug in counter overflow
handling in AES-GCM in libgcrypt's implementation. This leads to
incorrect results when using a non-12-byte IV and decrypting payloads
encrypted with other AES-GCM implementations, such as OpenSSL.

According to the NIST Special Publication 800-38D "Recommendation for
Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC",
section 7.1, algorithm 4, step 3 [NIST38D], the counter increment is
defined as inc_32. Section 6.2 of the same document defines the
incrementing function inc_s for positive integers s as follows:

| the function increments the right-most s bits of the string, regarded
| as the binary representation of an integer, modulo 2^s; the remaining,
| left-most len(X) - s bits remain unchanged

(X is the complete counter value in this case)

This problem does not occur when using a 12-byte IV, because AES-GCM has
a special case for the inital counter value with 12-byte IVs:

| If len(IV)=96, then J_0 = IV || 0^31 || 1

i.e., one would have to encrypt (UINT_MAX - 1) * blocksize of data to
hit an overflow. However, for non-12-byte IVs, the initial counter value
is the output of a hash function, which makes hitting an overflow much
more likely.

In practice, we have found that using

 iv = 9e 79 18 8c ff 09 56 1e c9 90 99 cc 6d 5d f6 d3
 key = 26 56 e5 73 76 03 c6 95 0d 22 07 31 5d 32 5c 6b a5 54 5f 40 23 98 60 f6 f7 06 6f 7a 4f c2 ca 40

will reliably trigger an overflow when encrypting 10 MiB of data. It
seems that this is caused by re-using the AES-CTR implementation for
incrementing the counter.

I am attaching a small utility to encrypt and decrypt data with both
OpenSSL and libgcrypt using AES-256-GCM while allowing to pass in the
key and IV. The problem can be demonstrated as follows:

$ openssl dgst -sha1 payload
SHA1(payload)= 33354423e3e0df0c306ba35bb3d7c720deeccd2a
$ ./cryptohelper libgcrypt encrypt payload key.bin iv.bin encrypted-libgcrypt
$ ./cryptohelper openssl decrypt encrypted-libgcrypt key.bin iv.bin decrypted-payload
$ openssl dgst -sha1 decrypted-payload
SHA1(decrypted-payload)= 7c57a358f8d9d63a69055ae32dd1e78ae068ebbe

Can anybody confirm our findings? Should I file a ticket for this?

[NIST38D]: http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf

-- 
Clemens Lang • Development Specialist
BMW Car IT GmbH • Lise-Meitner-Str. 14 • 89081 Ulm • http://bmw-carit.com
-------------------------------------------------------------------------
BMW Car IT GmbH
Geschäftsführer: Kai-Uwe Balszuweit und Christian Salzmann
Sitz und Registergericht: München HRB 134810
-------------------------------------------------------------------------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cryptohelper.cpp
Type: application/octet-stream
Size: 9244 bytes
Desc: cryptohelper.cpp
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20180129/c800151f/attachment.obj>