High Performance GHASH Function for Long Messages

摘要

This work presents a new method to compute the GHASH function involved in the Galois/Counter Mode of operation for block ciphers. If X = X_1 ... X_n is a bit string made of n blocks of 128 bits each, then the GHASH function effectively computes X_1H~n + X_2H~(n-1) + ... X_nH, where H is an element of the binary field F2i28. This operation is usually computed by using n successive multiply-add operations over F_2128. In this work, we propose a method to replace all but a fixed number of those multiplications by additions on the field. This is achieved by using the characteristic polynomial of H. We present both how to use this polynomial to speed up the GHASH function and how to efficiently compute it for each session that uses a new H.