9
$\begingroup$

Why are hash functions (e.g SHA-3) so complicated when GCM apparently provides secure hashing and has a relatively simple construction?

Is this purely about speed? I imagine that GMAC with a fixed key (GCM mode without ciphered data) is much slower, if you just need a key-less hash.

$\endgroup$
  • 2
    $\begingroup$ In general, unkeyed hashes are slower than keyed hashes, since the attacker isn't limited by not knowing the key. $\endgroup$ – CodesInChaos May 4 '17 at 14:13
  • 1
    $\begingroup$ GCM is only a mode of operation, which uses a blockcipher. That is on a different layer of abstraction than SHA-3. If you break down GCM with AES to the level of bytes and binary operations, SHA-3 might not look more complicated any more. $\endgroup$ – tylo May 4 '17 at 14:48
13
$\begingroup$

GCM does not provide secure hashing. In general, a MAC has all the properties of a hash only against an adversary who does not know the key. If you want to use the function as a MAC then the key has to be public and then A MAC is not a secure hash. With most common MAC constructions other than HMAC, if you know the key, you can easily construct, at least, a second preimage.

For example, look at how the authentication tag GHASH of GCM is calculated. I use the notations from the Wikipedia article; the plaintext is $A_1A_2A_3\ldots$ (split into blocks), $H$ is calculated from the key (so it would be some public constant to use GHASH as a hash) and the $X_i$ are calculated incrementally to produce the hash (so if $X_i = X'_i$ for some $i$ and two different messages then the hash will be the same). $$ \begin{align} X_0 &= 0 \\ X_1 &= A_1 \cdot H \\ X_2 &= (X_1 \oplus A_2) \cdot H = ((A_1 \cdot H) \oplus A_2) \cdot H \\ \end{align} $$ Let $A'_1 = A_2 \cdot H$ and $A'_2 = A_1 \cdot H$. Then $A_1A_2A_3\ldots$ and $A'_1A'_2A_3\ldots$ are (assuming that $A_2$ didn't happen to be equal to $A1 \cdot H$) two distinct messages with the same hash (and the same length, incidentally). And that's just from a trivial computation — with a bit more work first preimage can be broken too.

$\endgroup$
  • $\begingroup$ Actually, first preimages really doesn't take much more work at all $\endgroup$ – poncho May 4 '17 at 15:49
  • $\begingroup$ so why using a key if it can be broken so easily? Why doesn't GCM use an unkeyed hash? $\endgroup$ – David 天宇 Wong Mar 6 at 16:41
  • $\begingroup$ @David天宇Wong GCM doesn't use a hash because what it needs is a MAC, not a hash. The goal of GCM is that if you don't know the key, you can't produce data with a valid authentication tag. It achieves that goal. If it used a hash, then anyone could produce a valid tag for a message, even without knowing the key, so GCM would not guarantee the authenticity of a message. $\endgroup$ – Gilles 'SO- stop being evil' Mar 6 at 17:56
  • $\begingroup$ oh right, you could just XOR the tag with the hash of the ciphertext and then XOR it again with the hash of a new ciphertext $\endgroup$ – David 天宇 Wong Mar 6 at 18:04
4
$\begingroup$

GHASH/GMAC is a secure MAC which has different security properties than a generic hash construction; contrary to your assumption, it is not a secure hash.

For example, if you use GHASH/GMAC with a known key, the scheme would be trivially vulnerable to a length extension attack.

$\endgroup$
  • 1
    $\begingroup$ I've added a line explaining why the length extension attack (among other issues) prevents GHASH/GMAC to be used as a generic, secure hash. Hope that's OK, otherwise revert :) $\endgroup$ – Maarten Bodewes May 4 '17 at 11:34
  • $\begingroup$ That's fine, thanks for the addition @MaartenBodewes $\endgroup$ – mat May 4 '17 at 11:56
  • 2
    $\begingroup$ It's not just length extension, which could be fixed by appending the length to the hash. Like other common MAC apart from HMAC, if you know the key, you can forge preimages in many ways. $\endgroup$ – Gilles 'SO- stop being evil' May 4 '17 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.