AES-GEM maximum messages

[Panos K.]

Hi, 

This message is regarding AES-GEM, the scheme Scott presented in the Accordion Mode workshop last month. 

It looks to me the claimed 2^112 maximum messages with 2^-32 collision probability is optimistic. In essence, the collision probability is 2^-32 for a 256-bit random IV, but the collision for a (derived subkey, part of the IV) pair is much less.

The 256-bit variant of AES-GEM uses CBC-MAC to derive 256 bits of the subkey from 192-bits of the random nonce with an additional static 64 bits. Using CBC-MAC or CMAC or any AES based PRF with two 128-bit block inputs can lead to collisions after trying multiple nonces

Subkey= CBC-AES256-MAC_k(192-bit Nonce || "AES-256") ||
                CBC-AES256-MAC_k(192-bit Nonce || "AES-GEM")

After n subkey derivations the collision probability for each half of the subkey becomes n^2/2^129. Given that there are two in the 256-bit subkey, the collision probability for both 128-blocks of the subkey to collide is (n^2/2^129)(n^2/2^129)=n^4/2^258.

AES-GEM also uses the 64 left bits of the nonce as IV in a tweaked version of AES-GCM with a larger internal counter. That means that the collision probability of the IV after n encryptions will be n^2/2^65.

Treating the derived subkey and the IV as two independent, uncorrelated variables (that they are because each half of the subkey has gone through a PRF), the (Subkey, IV) collision probability is the product of the two (n^4/2^258)(n^2/2^65)=n^6/2^323.

That means that for a >2^-32 collision probability, we would need 2^49 messages. That is way less than the 2^112 claimed messages if we only consider the 256-bit IV collision probability.

Note that this issue does not exist in the 128-bit version of AES-GEM because the subkey ends up coming from two AES() calls which will not have collisions. 

[Panos K.]

Sorry for responding to my own message. 

Please disregard the previous analysis. n^4/2^258 should have been n^2/2^257 and  n^6/2^323 should have been  n^2/2^322. So the 2^112 maximum number of messages is the lower bound for a collision probability in the IV of 2^-32. I apologize for the confusion.