Score:3

What kind of hashing is GF multiplication in GCM cipher mode and GMAC?

jp flag

In GCM, GMAC, the additional associated data (AAD) (as well as outputs of subsequent blocks) is multiplied by a polynomial H in GF(2^128). This appears to be doing some secure hashing.

Is that what's happening, and if so, is this a general hashing method that's used elsewhere?

Score:4
my flag

In GCM, GMAC, the additional associated data (AAD) (as well as outputs of subsequent blocks) is multiplied by a polynomial H in GF(2^128).

Actually, it's the other way around; the AAD and the ciphertext is converted into a polynomial, and that polynomial is evaluated at a secret point H (in $GF(2^{128})$

This appears to be doing some secure hashing.

Nope, no secure hashing here; if someone knows what $H$ is, they can easily find collisions, preimages, etc. Hence, a full specification of the algorithm (including $H$) is not secure.

This is, instead, a similar sounding object known as an 'almost universal hash'; what that means is that, for any two distinct messages, they get mapped to the same point for only a tiny fraction of the keys (which is the $H$ value here) [1]

That's the sole property that an almost universal hash needs to satisfy; note that it may be easy (for example) to deduce the value $H$ by submitting a message and examining the hash value. Hence, by itself, it doesn't meet the criteria of a secure hash.

What are almost universal hashes good for? Well, they can be used as a component in a Message Authentication Code - in essence, the almost universal hash processes the message (based on a secret key), and then some object with real cryptographical properties (in the case of GCM/GMAC, AES) disguises that hash. This is known as the Carter Wegman construction, and is in common use (Poly1305 would be a second example).

And, one good thing about almost universal hashes is that we have constructions (of which GH is one) which provably meets the criteria.

[1]: Actually, for how GH is used within GCM/GMAC, you need a slightly stronger property; we'll skip this for now.

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.