GCM is designed to use a 96-bit nonce, which can be generated either randomly or deterministically. If you use a nonce that isn't 96 bits then it is padded and hashed with GHASH to create a pseudorandom nonce (and block counter) instead. For example, suppose that you generated uniformly random 128-bit nonces, these would be hashed with GHASH and converted into a 96-bit nonce and 32-bit random block counter. Given that GHASH is not collision resistant, is this significantly more likely to result in nonce reuse than generating a random 96-bit nonce directly?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Does the answers to this question AES-GCM recommended IV size: Why 12 bytes? satisfy you? $\endgroup$– kelalakaMay 1, 2020 at 17:56
-
$\begingroup$ No, although the Bootnote at the end of this answer is along the lines of what I’m asking. I’m specifically interested in how the (lack of) collision resistance of GHASH impacts the chance of reuse - collisions can be constructed, but are they likely to occur by chance? And weighing that against the fact that it also randomizes the block counter so in effect you get a larger nonce size. $\endgroup$– Neil MaddenMay 1, 2020 at 18:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
If you insist on random nonces, 128 bit random nonces are safer than 96 bit random nonces (but not as good as 96 bit counter-based nonces - I presume that is infeasible in your scenario).
The 128 bit random nonce is transformed (via GHash) into what is effectively a 96 bit nonce and a 32 bit counter; in the 96 bit case, the 96 bit nonce is used directly, and we use a fixed 32 bit counter value value $1$. If this (96, 32) bit value is $(X, Y)$, then an encryption of an $N$ block message uses the values $(X, Y)$ through $(X, Y+N+1)$ (and the addition is done modulo $2^{32}$)
Now, GCM runs into trouble if either a used range contains the value $(0, 0)$ (which can't happen with 96 bit nonces), or two separate encryptions (with their nonces) use a value in common.
As for the first possible case (using a value $(0, 0)$ somewhere in the range), that happens with probability $2^{-128}(N+2)$ for an $N$ block message - obviously, 96 bit nonces are better there.
As for the second possible case (using two ranges that interest), 128 bit nonces are clearly better. After all, for two ranges to interest, they must share the same $X$ component; for 96 bit nonces, that is sufficient; for 128 bit nonces, the $Y$ components also need to intersect, and unless $N$ is near the maximum, that has a probability less than 1.
If we model the prohibition on the $(0, 0)$ value as a single message that just happens to use that single value, then that falls in line with the 'no two messages can use intersecting ranges'. Then, it is easy to see that encrypting $M$ messages with 128 bit random nonces must be at least as secure as encryption $M+1$ messages with 96 bit random nonces, and actually, because of the observation that two 128 bit nonces that happen to map to the same 96 bit space will generally not intersect, it is actually considerably better.
In addition, you claimed that GHASH was not collision resistant, and Woodstock claimed that GHASH output was likely not uniform. Actually, if $H \ne 0$, then with 128 bit inputs, GHASH is a permutation, hence it is collision resistant, and the output is uniform.
-
$\begingroup$ Thanks, that’s a useful answer. I picked a 128-bit random nonce fairly arbitrarily, as a size somebody might pick based on the block size. If the random nonce was significantly larger than 128 bits, would that impact the collision resistance and/or uniformity of the output of GHASH? My claim that GHASH is not collision-resistant is based on this answer that shows how to calculate collisions for a known/fixed H. Does that impact the chance of random collisions for larger nonces? Apparently not for the case of 128-bit exactly. $\endgroup$ May 1, 2020 at 19:14
-
$\begingroup$ @NeilMadden: I can't think of any reason you'd use a random nonce larger than 128 bits; it gets mapped to a 128 bit in the end, and the output wouldn't be precisely uniform (although it would be close). In any case, collision attacks against GHASH assume the collider knows the value of $H$ (which a random nonce generator would not), and in any case, requires multiple blocks (and a 128 bit nonce fits in one). $\endgroup$– ponchoMay 1, 2020 at 19:32
-
$\begingroup$ Also, when the nonce (IV) is 128 bits then it will be padded with 64 zero bits and then the nonce length as a 64-bit integer before being hashed, so the input to GHASH will be 256-bits in that case and not a permutation. $\endgroup$ May 1, 2020 at 19:33
-
$\begingroup$ PS this isn’t purely academic. I am reviewing a bit of code that uses 256-bit random nonces with GCM $\endgroup$ May 1, 2020 at 19:46
-
1$\begingroup$ @NeilMadden: actually, the 0 bits and the nonce length is fixed; what we have is, if $X$ is a 128 bit value, then $GHASH(X) = H^2 \cdot X + C$ (where $H$ is the internal GCM value, and $C = H \cdot 128$, which is a key dependent constant. If $H \ne 0$, this is a permutation. And, if $X || Y$ is a 256 bit value, then $GHASH(X || Y) = H^3 \cdot X + H^2 \cdot Y + C$; if $X, Y$ are random, this is also uniformly distributed (again, if $H \ne 0$); not any worse, but also not any better... $\endgroup$– ponchoMay 1, 2020 at 19:55