3
$\begingroup$

In GCM mode of authenticated encryption, is it a security concern if the GHASH implementation timing can vary?

If the timing varies according to the AAD/ciphertext data, it looks as though that doesn't matter because that data is public anyway. But if the timing varies according to the GHASH key, does that reduce security?

$\endgroup$
5
$\begingroup$

If the timing varies with public information, then it's not a problem. If the timing varies with secret information like the key in GCM, it is a problem. (While GCM feeds only AAD and ciphertext to GHASH, other AEAD schemes like GCM-SIV feed the plaintext to GHASH/POLYVAL; timing dependent on any secret information is a problem.)

It's hard to make a fast software implementation of GCM that does not vary with the key, since you're evaluating a polynomial in $\operatorname{GF}(2^{128})$ at the GHASH key. (t is tempting to make a much faster software implementation that does vary with the key by using variable-time table lookups.) Worse, each block of the message (AAD or ciphertext) figures into the GHASH formula exactly once, but the key, and its square, and its cube, etc., figures in many times.

And CPU instruction sets and programming languages are historically designed to support integer arithmetic, not Galois field arithmetic, so even on a CPU that does support Galois field arithmetic natively, reliably taking advantage of it requires nontrivial engineering effort.

$\endgroup$
  • 2
    $\begingroup$ It should be noted that it is possible to leverage integer multiplications with masking to implement GHASH in constant-time. Performance is certainly not up to what can be done with pclmulqdq, but it can be quite decent (e.g. on my laptop I get 276 MB/s for GHASH, while a classic table-based AES tops at 170 MB/s). See: bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/hash/… $\endgroup$ – Thomas Pornin May 29 '18 at 19:51
  • $\begingroup$ If a timing attack successfully determined the GHASH key H, is it feasible for an attacker to get the encryption key from that? The GHASH key is created by encrypting an all-zeroes block with the encryption key, so that becomes a known plaintext, known ciphertext problem. With AES that's an infeasible problem to crack isn't it? $\endgroup$ – Craig McQueen May 29 '18 at 21:45
  • 1
    $\begingroup$ @CraigMcQueen Recovering the GHASH key doesn't help to recover the AES key, but (a) forgery is already a powerful tool in many applications, and (b) if your software has exploitable GHASH timing side channels it probably also has exploitable AES timing side channels. $\endgroup$ – Squeamish Ossifrage May 29 '18 at 22:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.