4 ms·

Can anyone explain why GCM is more attackable than CTR+HMAC? Is it because the signature is encoded in the ciphertext and can't be verified until some or all of

Can anyone explain why GCM is more attackable than CTR+HMAC? Is it because the signature is encoded in the ciphertext and can't be verified until some or all of the decryption occurs?

pjscott 13y ago
At the time this article was written, AEAD modes were apparently still too new, and their implementations too untrustworthy: http://www.daemonology.net/blog/2009-06-24-encrypt-then-mac.html http://www.daemonology.net/blog/2009-06-24-encrypt-then-mac.... At the moment, the best-supported AEAD mode seems to be AES-GCM, which has received a fair bit of attention since then. Alternately, {Salsa20,ChaCha20}-Poly1305 has some good implementations, e.g. http://nacl.cr.yp.to/ http://nacl.cr.yp.to/ and in TLS: https://www.imperialviolet.org/2014/02/27/tlssymmetriccrypto.html https://www.imperialviolet.org/2014/02/27/tlssymmetriccrypto...
- cperciva 13y ago
  AEAD modes were apparently still too new, and their implementations too untrustworthy Also, using Encrypt-then-MAC allows you to discard inauthentic messages without ever decrypting anything, which protects you from side channels in your block cipher.
  - pjscott 13y ago
    It's bizarre that this is still something we have to worry about.
StavrosK 13y ago
The argument I saw was that GCM is really hard to implement securely.
tptacek 13y ago
It's not, really, but the problem people are referring to is actually not too hard to explain. An HMAC authenticator is conceptually very simple. You start with a secure hash (even MD5 still qualifies, barely, when we're talking about HMAC), and, given a "key" and a "message", apply the hash function twice: an inner hash of the key and the message, and an outer hash of the key and the inner hash (the inner and outer hashes are distinguished by an "inner pad" and "outer pad" constant). Doing this produces a secure message authenticator for a message assuming the hash and key is secure (with SHA3, you don't even need HMAC, and can create a secure authenticator out of a simple keyed hash). You understand a secure hash, you understand what a keyed hash is (concatenate the key and the message and now only people who know the key can replicate that hash), and now you get what HMAC is. GCM is CTR mode, like Colin says you should use with HMAC, plus a GHASH authenticator. GHASH is a little trickier to understand than HMAC, but you can get most of the way there by thinking of it as a thermonuclear CRC algorithm: it's (at root) polynomial multiplication and reduction. The problem with GCM is that fast polynomial multiplication and reduction in software is table-driven. When software verifies a GHASH MAC, it is forced to look up elements in a table at locations determined by a secret. Those lookups end up configuring the system's cache; future memory references at addresses that collide with the secret table indices will be measurably faster than references that don't collide. Attackers can write software that profiles cache hits and from that information potentially recover secrets. Modern implementations of GCM on X64 hardware get hardware-accelerated multiplication optimized for this operation, mitigating the table lookup problem. But GCM is still potentially a concern for platforms that don't have these instructions. The plus side of GCM is that you'll never implement it yourself: it's gnarly enough that everyone uses one of a few library implementations of it. As a library interface, GCM is very nice: you're getting a "seal" and "unseal" operation that securely verifies authentication and then handles decryption, in the correct order of operations. On recent server hardware, that implementation is likely not to have side channel problems; the same is rarely true of HMAC implementations, which tend (annoyingly) to be hand-hacked, particularly for verification. The "cool kids" replace GCM with Salsa20+Poly1305, which replaces AES-CTR with a native stream cipher (Salsa20, which is actually a hash core running in CTR mode) and a polynomial MAC that is very fast in secret-table-free software. If you use Nacl, that's what you're getting; it's something much closer to GCM than to AES-CTR+HMAC.
- cperciva 13y ago
  On recent server hardware, that implementation is likely not to have side channel problems; the same is rarely true of HMAC implementations, which tend (annoyingly) to be hand-hacked, particularly for verification. Disagree. Hashes and HMACs are very safe against side channel attacks. Heck, I don't think I could insert a side channel if I tried! On a 1-10 scale of side channel attackiness, hashes and HMACs are 0, block ciphers are 3-4, and asymmetric crypto is 6-8.
  - tptacek 13y ago
    Come on. You mean apart from virtually every web stack's implementation of HMAC? They all start with a version that uses string comparison.
    - sillysaurus3 13y ago
      In case anyone is wondering the proper way to compare two HMACs, it's to xor the strings and check whether the result is zero. If string A xor string B is zero, then they're equal. If it's nonzero, then they're not equal. This will prevent timing attacks, because the entirety of both strings are compared. When you compare the two HMACs using standard string comparison, you expose yourself to a timing attack because the algorithm will likely stop comparing after finding the first difference in the strings.
      - cperciva 13y ago
        In case anyone is wondering the proper way to compare two HMACs, it's to xor the strings and check whether the result is zero You've just punted the problem. How are you checking whether the result is zero? The correct code (copy and paste from libcperciva): /** * crypto_verify_bytes(buf0, buf1, len): * Return zero if and only if buf0[0 .. len - 1] and buf1[0 .. len - 1] are * identical. Do not leak any information via timing side channels. */ uint8_t crypto_verify_bytes(const uint8_t * buf0, const uint8_t * buf1, size_t len) { uint8_t rc = 0; size_t i; for (i = 0; i < len; i++) rc = rc | (buf0[i] ^ buf1[i]); return (rc); }
wbl 13y ago
If you reuse a nonce, even once, then any message can be forged with GCM. HMAC doesn't have this issue, but also doesn't handle nonces natively, which the confidentiality loss for both is the same. On devices which never reuse secret keys across power cycles this is probably not a problem, but it can be in some environments.
- tptacek 13y ago
  Colin recommends CTR+HMAC, which has exactly the same problem. I don't think that's what he's referring to.
  - wbl 13y ago
    They both have exactly the same confidentiality issue (because both use CTR mode) but the forgery issue is specific to GCM as a single successful forgery leads to infinitely many. With truncated tags this is a real issue. But with big tags both have pretty much the same "good for counting, terrible if you can't" behaviour.

Can anyone explain why GCM is more attackable than CTR+HMAC? Is it because the signature is encoded in the ciphertext and can't be verified until some or all of the decryption occurs?

pjscott 13y ago

At the time this article was written, AEAD modes were apparently still too new, and their implementations too untrustworthy: http://www.daemonology.net/blog/2009-06-24-encrypt-then-mac.html http://www.daemonology.net/blog/2009-06-24-encrypt-then-mac.... At the moment, the best-supported AEAD mode seems to be AES-GCM, which has received a fair bit of attention since then. Alternately, {Salsa20,ChaCha20}-Poly1305 has some good implementations, e.g. http://nacl.cr.yp.to/ http://nacl.cr.yp.to/ and in TLS: https://www.imperialviolet.org/2014/02/27/tlssymmetriccrypto.html https://www.imperialviolet.org/2014/02/27/tlssymmetriccrypto...

cperciva 13y ago
AEAD modes were apparently still too new, and their implementations too untrustworthy Also, using Encrypt-then-MAC allows you to discard inauthentic messages without ever decrypting anything, which protects you from side channels in your block cipher.
- pjscott 13y ago
  It's bizarre that this is still something we have to worry about.

StavrosK 13y ago

The argument I saw was that GCM is really hard to implement securely.

tptacek 13y ago

It's not, really, but the problem people are referring to is actually not too hard to explain. An HMAC authenticator is conceptually very simple. You start with a secure hash (even MD5 still qualifies, barely, when we're talking about HMAC), and, given a "key" and a "message", apply the hash function twice: an inner hash of the key and the message, and an outer hash of the key and the inner hash (the inner and outer hashes are distinguished by an "inner pad" and "outer pad" constant). Doing this produces a secure message authenticator for a message assuming the hash and key is secure (with SHA3, you don't even need HMAC, and can create a secure authenticator out of a simple keyed hash). You understand a secure hash, you understand what a keyed hash is (concatenate the key and the message and now only people who know the key can replicate that hash), and now you get what HMAC is. GCM is CTR mode, like Colin says you should use with HMAC, plus a GHASH authenticator. GHASH is a little trickier to understand than HMAC, but you can get most of the way there by thinking of it as a thermonuclear CRC algorithm: it's (at root) polynomial multiplication and reduction. The problem with GCM is that fast polynomial multiplication and reduction in software is table-driven. When software verifies a GHASH MAC, it is forced to look up elements in a table at locations determined by a secret. Those lookups end up configuring the system's cache; future memory references at addresses that collide with the secret table indices will be measurably faster than references that don't collide. Attackers can write software that profiles cache hits and from that information potentially recover secrets. Modern implementations of GCM on X64 hardware get hardware-accelerated multiplication optimized for this operation, mitigating the table lookup problem. But GCM is still potentially a concern for platforms that don't have these instructions. The plus side of GCM is that you'll never implement it yourself: it's gnarly enough that everyone uses one of a few library implementations of it. As a library interface, GCM is very nice: you're getting a "seal" and "unseal" operation that securely verifies authentication and then handles decryption, in the correct order of operations. On recent server hardware, that implementation is likely not to have side channel problems; the same is rarely true of HMAC implementations, which tend (annoyingly) to be hand-hacked, particularly for verification. The "cool kids" replace GCM with Salsa20+Poly1305, which replaces AES-CTR with a native stream cipher (Salsa20, which is actually a hash core running in CTR mode) and a polynomial MAC that is very fast in secret-table-free software. If you use Nacl, that's what you're getting; it's something much closer to GCM than to AES-CTR+HMAC.

cperciva 13y ago
On recent server hardware, that implementation is likely not to have side channel problems; the same is rarely true of HMAC implementations, which tend (annoyingly) to be hand-hacked, particularly for verification. Disagree. Hashes and HMACs are very safe against side channel attacks. Heck, I don't think I could insert a side channel if I tried! On a 1-10 scale of side channel attackiness, hashes and HMACs are 0, block ciphers are 3-4, and asymmetric crypto is 6-8.
- tptacek 13y ago
  Come on. You mean apart from virtually every web stack's implementation of HMAC? They all start with a version that uses string comparison.
  - sillysaurus3 13y ago
    In case anyone is wondering the proper way to compare two HMACs, it's to xor the strings and check whether the result is zero. If string A xor string B is zero, then they're equal. If it's nonzero, then they're not equal. This will prevent timing attacks, because the entirety of both strings are compared. When you compare the two HMACs using standard string comparison, you expose yourself to a timing attack because the algorithm will likely stop comparing after finding the first difference in the strings.
    - cperciva 13y ago
      In case anyone is wondering the proper way to compare two HMACs, it's to xor the strings and check whether the result is zero You've just punted the problem. How are you checking whether the result is zero? The correct code (copy and paste from libcperciva): /** * crypto_verify_bytes(buf0, buf1, len): * Return zero if and only if buf0[0 .. len - 1] and buf1[0 .. len - 1] are * identical. Do not leak any information via timing side channels. */ uint8_t crypto_verify_bytes(const uint8_t * buf0, const uint8_t * buf1, size_t len) { uint8_t rc = 0; size_t i; for (i = 0; i < len; i++) rc = rc | (buf0[i] ^ buf1[i]); return (rc); }

wbl 13y ago

If you reuse a nonce, even once, then any message can be forged with GCM. HMAC doesn't have this issue, but also doesn't handle nonces natively, which the confidentiality loss for both is the same. On devices which never reuse secret keys across power cycles this is probably not a problem, but it can be in some environments.

tptacek 13y ago
Colin recommends CTR+HMAC, which has exactly the same problem. I don't think that's what he's referring to.
- wbl 13y ago
  They both have exactly the same confidentiality issue (because both use CTR mode) but the forgery issue is specific to GCM as a single successful forgery leads to infinitely many. With truncated tags this is a real issue. But with big tags both have pretty much the same "good for counting, terrible if you can't" behaviour.