1
$\begingroup$

I read here:

https://www.researchgate.net/publication/220335697_GCM_GHASH_and_Weak_Keys

how GHASH works. So we have $m$ 128-bit blocks $X_{i}$ and we compute in $GF(2^{128})$:

$Y_{m} = \sum_{i=1}^{m} X_{i} \times H^{m-i+1}$

$H$ is a key. Am I see right there that $H$ is raised to the power? Is there method to do it fast in $GF(2^{128})$ or it is just standard exponentiation modulo with fast exponentiation? I thought there is one multiplication in $GF(2^{128})$ on one 128-bit block, but if $H$ is raised to the power, there is much more.

How fast is GHASH itself compared to AES? I mean if AES can achieve $n$ cycles per byte, how fast is GHASH alone? Is perfmormance of GHASH comparable just to one multiplication in $GF(2^{128})$ on every 128 bits of plaintext or is it much complicated?

$\endgroup$
10
  • 1
    $\begingroup$ How fast it is depends on hardware features. It can be really fast if the CPU has pclmulqdq. $\endgroup$
    – forest
    May 13 at 2:10
  • $\begingroup$ @forest my question was about GHASH with pclmulqdq, becuase today it seem to be standard implementation of GCM. I know it can be fast, but let's say AES can achevie 1 cycle per byte, what GHASH takes in this 1 cycle per byte? $\endgroup$
    – Tom
    May 13 at 2:15
  • 3
    $\begingroup$ crypto.stackexchange.com/a/60109/54184 shows benchmarks with and without various hardware acceleration features for both GHASH and AES in CTR mode. AES with full hardware acceleration achieves 5307.37 MB/s. GHASH with full hardware acceleration achieves 4795.76 MB/s. $\endgroup$
    – forest
    May 13 at 2:16
  • 1
    $\begingroup$ You evaluate the polynomial using Horner's method -- one multiplication and one addition for each coefficient of the polynomial. $\endgroup$
    – Mikero
    May 13 at 3:03
  • 1
    $\begingroup$ @Tom Modern CPUs have very deep pipelines and can effectively execute multiple instructions at once as long as they don't both require using the same execution units (i.e. they don't cause port conflicts) and as long as neither instruction depends on the other having finished first. AES-NI and CLMUL both run on different execution units (port 0 vs port 5 respectively on Skylake, see Table 11.1 in Agner Fog's CPU microarchitecture optimization document), so they'll be executed concurrently. $\endgroup$
    – forest
    May 13 at 21:43

0

Your Answer

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

Browse other questions tagged or ask your own question.