Possibly incorrect counter overflow handling for AES-GCM

[Jussi Kivilinna]

Hello,

On 29.01.2018 19:03, Clemens.Lang at bmw.de wrote:
> 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.

You're right, counter overflow is handled wrong and this can be seen with
non-12-byte IVs. Input plaintext length is limited to 2^32-2 blocks, so
overflow does not happen with 12-byte IV.

> 
> 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.

Following key/iv gives overflow after 16 bytes of input and encryption
goes wrong after that.

AES256, ctr_low: ffffffff
 key: 0000000000000000000000000000000000000000000000000000000000000000
 iv: 00000000000000000000000086dd40e7

-Jussi