GHASH with a finite field multiplication algorithm in reverse order

Question

NIST SP 800-38D § 6.4 GHASH Function describes the GHASH algorithm thusly:

Prerequisites: block $H$, the hash subkey.

Input: bit string $X$ such that len($X$) = $128m$ for some positive integer m.

Output: block $GHASH_H$ ($X$).

Steps:

1. Let $X_1$, $X_2$, ... , $X_{m-1}$, $X_m$ denote the unique sequence of blocks such that $X$ = $X_1$ || $X_2$ || ... || $X_{m-1}$ || $X_m$.

2. Let $Y_0$ be the "zero block," $0^{128}$.

3. For $i$ = $1$, ..., $m$, let $Y_i$ = ($Y_{i-1}$ ⊕ $X_i$) • $H$.

4. Return $Y_m$.

The multiplication algorithm works in "little endian" order. Quoting NIST SP 800-38D § 6.3 Multiplication Operation on Blocks, "The convention for interpreting strings as polynomials is "little endian": i.e., if $u$ is the variable of the polynomial, then the block $x_0x_1...x_{127}$ corresponds to the polynomial $x_0 + x_1u + x_2u^2 + ... + x_{127}u^{127}$" (emphasis mine).

So let's say I have an existant multiplication method that operates in big endian order instead of little endian order and that this existant method is significantly faster than the method proposed in NIST SP 800-38D. My question is... what's the most effective way to utilize this existant method?

The best that I've been able to come up with thus far is this:

$Y_i$ = reverseEndianness(reverseEndianness($Y_{i-1}$ ⊕ $X_i$) • reverseEndianness($H$))

reverseEndianness($H$) can be precomputed but idk it just seems like there has to be a better way that doesn't require so many endianness reversals idk. I mean, even with the endian reversal (which can be done surprisingly quickly) it's still a lot faster than the method proposed in NIST SP 800-38D but I'd still like to minimize how many are performed.

The reason I have an existant multiplication method operating in big endian order is because that's the order you're supposed to do it in for elliptic curves in $F_{2^m}$. Per SEC 1 § 2.3.5 Field-Element-to-Octet-String Conversion, where elliptic curves are concerned, one should "view the coefficients of the polynomial as a bit string with the highest degree term on the left and convert the bit string to an octet string".

Answer 1

My question is... what's the most effective way to utilize this existant method?

Well, you could rearrange things to take 1 reverseEndianness operation per block, plus 1 reverseEndianness operation per GCM operation (plus 1 per key setup).

1. Let $X_1$, $X_2$, ... , $X_{m-1}$, $X_m$ denote the unique sequence of blocks such that $X$ = $X_1$ || $X_2$ || ... || $X_{m-1}$ || $X_m$.

2. Let $Y_0$ be the "zero block" $0^{128}$.

3. For $i$ = $1, ..., m$, let $Y_i = (Y_{i-1} \oplus \text{ReverseEndianness}(X_i)) \cdot H_{\text{reverse}}$.

4. Return $\text{ReverseEndianness}(Y_m)$.

where $H_{\text{reverse}}$ is the precomputed $\text{ReverseEndianness}(H)$ value.

This is essentially the same as what you had, except we keep the intermediate $Y_i$ values in bigendian format