Which is slower, AES or GCM hash (GHASH), if CPU has no special instructions?

Question

In an answer to this question: Security of GCM if Implemented with Stream Cipher instead of Block Cipher ...it was stated that:

The GHASH part of GCM is usually the problematic one when it comes to implementation, not the AES. GHASH is very fast on hardware platforms that have dedicated opcodes (x86 with AES-NI, POWER8...) but these platform also provide an AES hardware implementation that outperforms software-based stream ciphers.

Is this really true? Is GHASH really slower than AES, if the CPU has no special instructions for either?

Answer 1

First things first: the passage you quote does not claim that GHASH is slower than AES. What it says is that if you replace AES/CTR with a much faster stream cipher, then the GHASH part will be comparatively expensive.

---

There are many kinds of implementations, for both AES and GHASH; they have different performance characteristics, and they may be constant-time, or not. I'll use BearSSL here for most measures, because I know how that code works (I wrote it), and I can easily benchmark it. The measure platform here is my laptop (Intel i7-6567U at 3.3 GHz, in 64-bit mode):

AES-128 CTR (big)                170.67 MB/s
AES-128 CTR (ct64)               108.91 MB/s
AES-128 CTR (x86ni)             5307.37 MB/s
GHASH (ctmul)                    214.63 MB/s
GHASH (ctmul64)                  277.17 MB/s
GHASH (pclmul)                  4795.76 MB/s

For the AES implementations:

• "big" is a classic table-based implementation (not constant-time).
• "ct64" is a constant-time bitslice implementation that uses 64-bit registers and computes 4 AES instances in parallel (which works well with CTR mode).
• "x86ni" uses the AES-NI opcodes (it computes four instances in parallel, which maps well to the 4-cycle latency of these opcodes on a Skylake core).

For the GHASH part:

• "ctmul" uses 32x32→64 integer multiplications with masking to avoid trouble with carries. It is constant-time.
• "ctmul64" uses 64x64→64 integer multiplications with masking; it is also constant-time.
• "pclmul" uses the AES-NI opcodes.

The following extra notes apply:

• All GHASH implementations in BearSSL are constant-time. It is possible to make non-constant-time GHASH implementations which are faster, by using lookup tables, in particular dynamically generated tables for the specific secret $h$.

• There is a constant-time bitslice implementation of AES that leverages SSE2 opcodes, both for extra parallelism (128-bit registers) and more efficient implementation of the linear parts of the algorithm. It would go over 400 MB/s on this machine, and would outperform the constant-time GHASH implementations. Whether it qualifies as "not using special opcodes" is debatable: it is not using the AES-NI opcodes, but not all 64-bit architectures have something similar to SSE2 (it is part of the ABI on 64-bit x86, though).

• Combining AES and GHASH may offer speed-ups, if they do not exercise the same compute unit within the CPU. For instance, with the AES-NI opcodes, interleaving the AES/CTR encryption and the GHASH can yield better than the already quite decent 2.5 GB/s that the figures above promise.

An aggregate rule of thumb is that, when using only "basic" operations (i.e. those available in C without inline assembly or compiler intrinsics), you can keep the cost of GHASH to less than half the cost of AES/CTR (if using a non-constant-time AES, it makes more sense to measure against a non-constant-time GHASH).

---

Now let's compare with ChaCha20 and Poly1305:

ChaCha20 (ct)                    407.74 MB/s
ChaCha20 (sse2)                  590.59 MB/s
Poly1305 (ctmul)                1248.27 MB/s
Poly1305 (ctmulq)               1936.74 MB/s

The "ct" implementation of ChaCha20 uses only 32-bit integer operations; the "sse2" implementation uses SSE2 intrinsics. For Poly1305, the "ctmul" implementation uses basic 32x32→64 multiplications, while the "ctmulq" implementation uses 64x64→128 multiplications (which require some compiler intrinsics or extensions). All of these are constant-time.

What this says to us is the following:

• Without AES-NI, ChaCha20 outperforms AES. Actually, constant-time ChaCha20 substantially outperforms all AES, even non-constant-time.
• Without AES-NI, Poly1305 is much faster than GHASH.
• If you want to make an hybrid out of ChaCha20 and GHASH (this is the context of the previous question that you want to discuss), then the GHASH part is going to be more expensive than ChaCha20, except if you use the AES-NI opcodes for GHASH; but then, if AES-NI opcodes are available, why would you use that ChaCha20 hybrid instead of standard AES/GCM?

Answer 2

I wrote a simple OpenSSL performance test program that creates an EVP_CIPHER_CTX in EVP_aes_128_gcm() mode, installs the key and initialization vector, feeds one block of authentication data, feeds million blocks of plaintext, and measures the performance of the encryption.

I tested the program with various values of OPENSSL_ia32cap environment variable. The used CPU was Intel Xeon E3-1220 running at 3.10 GHz and having support for both AES-NI and carry-less multiplication instructions.

With AES but without carry-less multiplication:

OPENSSL_ia32cap=0x200000000000000 ./a.out
2.1244 Gbps

With carry-less multiplication but without AES:

OPENSSL_ia32cap=0x201000000 ./a.out
0.79697 Gbps

With both instructions:

OPENSSL_ia32cap=0x200000201000000 ./a.out
5.00443 Gbps

With neither:

OPENSSL_ia32cap=0 ./a.out
0.660218 Gbps

So, the answer is that AES instructions help more than carry-less multiplication instructions, although selecting a CPU having both is the best approach.

Thus, the claim in the linked question that GHASH is the problematic one instead of AES was incorrect. The reason for this is that a lookup-table-driven implementation for GHASH is used by OpenSSL. There is no need to calculate the carry-less multiplication on a bit-by-bit basis if the CPU has no special instructions.

Edit: and I should also add the lookup table uses only 256 bytes of memory, meaning it can be implemented in embedded devices as well.