Message Authentication Codes

GHASH / Galois/Counter Mode (GCM) / GMAC

The Galois/Counter Mode is a very well-known mode of operation for block ciphers which was specified in [MV04]. GMAC is a authentication-only variant of the algorithm.

While the original specification only considers block ciphers, GCM can also be specified in terms of the Counter mode (CTR) of the block cipher. The counter mode transforms a block cipher into a stream cipher. This allows it to replace the block cipher by any stream cipher while preserving all security guarantees; thereforce fastd allows to use GMAC with any supported stream cipher.

One particular issue with GCM/GMAC is that it is hard to implement in software. Usually it is implemented using lookup table, which might exhibit cache timing side channels. This issue doesn’t affect modern x86 CPUs providing the PCLMUL instruction, as PCLMUL allows performing carry-less multiplications without a lookup table.

UHASH / UMAC

The UMAC message authentication code defined in [RFC4418] is a strongly universal hash function, which is formed by defining a universal hash function UHASH and XORing it with a pad generated by a block cipher like AES.

In fastd, the pad can be generated by any supported stream cipher, and the key derivation function specified in the RFC has been replaced by HKDF.

The UHASH function is optimized for efficient implementation in software on 32bit CPUs. Therefore UMAC is much more performant than GMAC, especially on embedded systems, and doesn’t exhibit any timing side channels.

Bibliography

[MV04]D. McGrew and J. Viega, “The Galois/counter mode of operation (GCM)”, Submission to NIST Modes of Operation Process, 2004.
[RFC4418]T. Krovetz, “UMAC: Message Authentication Code using Universal Hashing”, RFC4418 (Informational), Internet Engineering Task Force, 2006. [Online] http://www.ietf.org/rfc/rfc4418.txt