The Security and Performance of 'GCM' when Short Multiplications Are Used Instead

摘要

We study the security and performance of an altered Galois/Counter Mode (GCM) of operation. Recent studies (e.g. Krovetz and Rogaway FSE 2011) show that GCM performs rather poorly in modern software implementation because of polynomial hashing in the large field GF(2~n) (n denotes the block size of the underlying cipher). This paper investigates whether we can use polynomial hashing in the ring GF(2~(n/2)) × GF(2~(n/2)) instead. Such a change would normally compromise the level of security down to θ(2~(n/4)). Nonetheless, our security proofs show that we can avoid such degradation by masking and then encrypting the hash result, guided by the tentative suggestion made by Ferguson in 2005. We also provide experimental data showing that the modified GCM runs at 1.777 cycles per byte on an Intel Sandy Bridge processor. This makes about 31% reduction from 2.59 cycles per byte of Gueron's GCM implementation presented at Indocrypt 2011.