Join Log in
Score:4
hlayhel avatar Crypto

Is GCM with zero-length AAD less secure?

in flag
hlayhel

In a previous question, it was made clear that in the case of GCM, there is no distinction between "no AAD" and "zero-length AAD". Since I have noticed "zero-length AAD" in several implementations, my question is, does that render such AE schemes less secure?

In the various papers that treat AE security, I think the paper Reconsidering Generic Composition by Namprempre, Rogaway and Shrimpton might have been the most explicit in this regard. According to their nAE scheme enumeration, the first scheme that shows weaker security bounds is A9 where A (i.e. AAD) is dropped from the Tag computation (see Fig. 5). Now of course, they do mention that it's a borderline case (transitional). But they make it clear that its security is not as tight as the A1-A8 schemes (all of which include A in the tag calculation). I have tried to survey other papers on the topic, but I haven't found a paper that gives a similar treatment.

So if AAD is missing from GCM (or if |AAD|=0), is GCM security downgraded in any way or is our security proof a bit weaker? Or, is that not a conclusion we should take from Namprempre's paper above (assuming their results were accepted by the crypto community)?

161
0 + 0
gcm
kelalaka avatar
in flag
kelalaka
As [noted](https://chat.stackexchange.com/transcript/message/59377989#59377989): GCM is A5 on the paper.
0
Reply
kelalaka avatar
in flag
kelalaka
GCM doesn't support noAAD. In GCM, the AAD with zero-length is converted to 128 zeroes. This is clear from the previous answer and NIST's doc. **There is always an AAD! in GCM** The recipient, therefore, can reject any empty AAD as a forgery. This provides an additional check since AAD is authenticated but not encrypted. If you are asking to modify the CGM to remove AAD, then this is a different scheme.
0
Reply
hlayhel avatar
in flag
hlayhel
I'm reading the previous answer differently. For example, he says, "If the AAD is zero-length, then zero bits of padding are added and no time is spent hashing any AAD or AAD padding". From that I conclude that AAD with zero-length is converted to zero bits of zeros, not 128 bits of zeros. I think the rest of his answer makes it clearer. If |AAD|=0, then len(A)=0, v=0, and 0^v=0, "**thus the number of ‘0’ bits appended is 0**". He then concludes that "if A is empty, then the prefix A∥0^v is also empty." This means that all the A-components in creating GHASH are empty (A, 0^v, len(A)).
0
Reply
kelalaka avatar
in flag
kelalaka
Yes, that is correct, $A || 0^v$ is empty, however, the length is encoded in 64 bits so that one can decode it as empty AAD. So, still, there is always AAD in GCM.
1
Reply
kelalaka avatar
in flag
kelalaka
Even empty AAD gives a little halt option against AAD removal from an adversary. So effectively, they are not.
0
Reply
hlayhel avatar
in flag
hlayhel
I see. So it's the component [len(A)]64 that remains. I checked the NIST doc; they define [x]64 as the binary representation of integer x (in this case, x=0) as a string of 64 bits. So I guess I have to agree. One more clarification from the author of the previous answer if you can, I was a bit confused about his first statement "AES-GCM does not support ‘no AAD’ as distinct from ‘zero-length AAD’". I sort of read it as, in the case of GCM we don't make a distinction between 'no AAD' and 'zero-length AAD'. Did I read wrong?
0
Reply
kelalaka avatar
in flag
kelalaka
No ADD should be something like that; there is no information available about AAD, even length or single bit. However, in this case, the non-existence of AAD may indicate that it is erased or already noAAD. The scheme should distinguish this. GCM simply encodes the length and doesn't allow noAAD ( or we can say converts noADD into zero-length AAD).
1
Reply
hlayhel avatar
in flag
hlayhel
Got it. So no-AAD here means no information about AAD, not that AAD logic is dropped. I think we're in total agreement now. Thanks for your time!
1
Reply
Score:1
kelalaka avatar Crypto
in flag
kelalaka

AES-GCM falls category A5 in the paper. In AES-GCM doesn't support $\texttt{no-AAD}$, even you don't use AAD during encryption, AES-GCM convert his as a $\texttt{zero-length-AAD}$.

See in the NIST Special Publication 800-38d, page 15;

Algorithm 4: $GCM-AE_K (IV, P, A)$
…
4. Let $u = 128\cdot\lceil\operatorname{len}(C)/128\rceil - \operatorname{len}(C)$ and let $v = 128\cdot\lceil\operatorname{len}(A)/128\rceil - \operatorname{len}(A)$.
5. Define a block, $S$, as follows: $$S = \operatorname{GHASH}_H(\mathbf{A \mathbin\| \mathtt 0^v} \mathbin\| C \mathbin\| \mathtt 0^u \mathbin\| \mathbf{[\operatorname{len}(A)]_{64}} \mathbin\| [\operatorname{len}(C)]_{64}).$$ …
In Steps 4 and 5, the AAD and the ciphertext are each appended with the minimum number of ‘$\mathtt 0$’ bits, possibly none, so that the bit lengths of the resulting strings are multiples of the block size (The bolds, are mine).

$A$ is associated data, $len(A) = 0$ therefore, $\mathtt{v} = 0$. Even in this case, we have $[\operatorname{len}(A)]_{64}$, this 64-bit encoding of the length of th associated data and this will always indicate the exsitance of AAD, zero-length or not!.

If an attacker, removes the associated data, to make it seem like zero-length, during the decryption, one must halt with the tag mismatch ( Always halt and stop the decryption at once).

A scheme that supports no-AAD, must not carry information about the missing AAD, otherwise, it falls into zero-length AAD.

In the end, we have extra protection against forgeries with zero-length AAD.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.