3 ms·

Why do people consider GCM difficult to implement in software? (disclaimer: I worked for a company that sold a GCM implementation)

by mentat 13y ago

tel 13y ago
My understanding is that fast implementations in software require look up tables which are susceptible to timing attacks.
- sweis 13y ago
  OpenSSL has a GCM implementation which is very fast and I believe is not susceptible to timing attacks due to using vpclmulqdq: http://git.openssl.org/gitweb/?p=openssl.git;a=blob;f=crypto/modes/asm/aesni-gcm-x86_64.pl;h=3781933917227dd127352fa8d7d066804dacba13;hb=HEAD http://git.openssl.org/gitweb/?p=openssl.git;a=blob;f=crypto... You can debate whether it's a "software implementation" since it's using AESNI and PCLMULQDQ.
  - tptacek 13y ago
    I think PCLMULQDQ is noncontroversial, but also considered "hardware supported".
- mentat 13y ago
  So cache timing attacks increasing with table size? I thought the table was only for the authentication section. I guess that would be reversible to the key. Are there any papers on this?
  - nightcracker 13y ago
    I'm not exactly sure on the details of AES-GCM, but in general if you use secret data to influence either the data path (indexing tables), code path (branches) or timing (either branches or non-constant instructions) then your secret data should be considered compromised in a model allowing side channel attacks.
tptacek 13y ago
GHASH requires carryless multiplication of large numbers, and fast software implementations of that operation involve lookup tables, which leak memory timing.
- rainsford 13y ago
  And large lookup tables create potential performance problems for large numbers of simultaneous connections. Plus there is non-trivial per-key setup time for the GHASH tables, which hurts key agility. Both of these things tend not to be measured well in benchmarks, which makes even "fast" GCM software implementations somewhat slower in practice than might be expected.

Why do people consider GCM difficult to implement in software? (disclaimer: I worked for a company that sold a GCM implementation)

by mentat 13y ago

Why do people consider GCM difficult to implement in software? (disclaimer: I worked for a company that sold a GCM implementation)

tel 13y ago

My understanding is that fast implementations in software require look up tables which are susceptible to timing attacks.

sweis 13y ago
OpenSSL has a GCM implementation which is very fast and I believe is not susceptible to timing attacks due to using vpclmulqdq: http://git.openssl.org/gitweb/?p=openssl.git;a=blob;f=crypto/modes/asm/aesni-gcm-x86_64.pl;h=3781933917227dd127352fa8d7d066804dacba13;hb=HEAD http://git.openssl.org/gitweb/?p=openssl.git;a=blob;f=crypto... You can debate whether it's a "software implementation" since it's using AESNI and PCLMULQDQ.
- tptacek 13y ago
  I think PCLMULQDQ is noncontroversial, but also considered "hardware supported".
mentat 13y ago
So cache timing attacks increasing with table size? I thought the table was only for the authentication section. I guess that would be reversible to the key. Are there any papers on this?
- nightcracker 13y ago
  I'm not exactly sure on the details of AES-GCM, but in general if you use secret data to influence either the data path (indexing tables), code path (branches) or timing (either branches or non-constant instructions) then your secret data should be considered compromised in a model allowing side channel attacks.

tptacek 13y ago

GHASH requires carryless multiplication of large numbers, and fast software implementations of that operation involve lookup tables, which leak memory timing.

rainsford 13y ago
And large lookup tables create potential performance problems for large numbers of simultaneous connections. Plus there is non-trivial per-key setup time for the GHASH tables, which hurts key agility. Both of these things tend not to be measured well in benchmarks, which makes even "fast" GCM software implementations somewhat slower in practice than might be expected.