2 ms·

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

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); }
- sillysaurus3 13y ago
  Heh. My first answer was "copy paste the algorithm from tarsnap," but then I thought I'd better explain it directly. Thank you for pasting it.
- lotharrr 13y ago
  Might it be even safer to squash 'rc' down to a single pair of values (0 or 1), rather than leaving the caller with the responsibility of testing a byte for zeroness safely? By leaking the 255 possible values for "not equal" to the caller, we're kind of punting the (smaller) problem, and they might do something nutty like add it to some other constant (incurring timing-leaking carries) before comparing the result against something. Of course, we're not just defending against surprises from the calling code, we're defending against compiler behavior too. We're trying to constrain its options so tightly that it has no choice but to emit a series of machine instructions that we know will run in constant time. If it weren't such a hassle, we'd write crypto_verify_bytes() in x86 assembly. It'd be lovely if our languages had a way to express these constraints directly, instead of phrasing them with artificially small types and low-level logical operations.
- TheLoneWolfling 13y ago
  A question. What prevents a compiler from optimizing that function to non-constant time? For example, by inserting a bailout condition (rc == 255) into the loop? (I am aware that it probably wouldn't, but "probably" in cryptographic contexts isn't generally good enough...)
  - cperciva 13y ago
    Theoretically? Nothing at all. You could have a compiler which produces code which revs the CPU in such a way to output the complete works of Shakespeare in Morse code via the fluctuations in your laptop's fan speed, and it would be perfectly standard-compliant. Worse than that, there's things compilers actually do in practice, like optimizing away memset(sensitivedate, 0, sizeof(sensitivedata)) and you can't even protect yourself against that properly by using a (volatile *) cast since the compiler is perfectly within its rights to make extra copies of that data and even without optimization the memset will only zero one of the copies. (gcc in particular loves to copy data onto the stack, due to a broken register allocator.) I've been trying to convince some clang developers that we need to have a C language extension for "we're handling sensitive data here, don't optimize it in dangerous ways", but it's difficult to define exactly what optimizations could be problematic...
  - zAy0LfpBZLC8mAC 13y ago
    Also, in interpreted languages, it's difficult to know whether the primitive operations actually are constant time, which is why I think the better universal solution is to hash both the MAC from the untrusted input as well as your own computed MAC once more with the same HMAC with a random key and only then do the comparison on the result of that. The HMAC should be constant time anyhow, and with this construction, it shouldn't matter much whether the final comparison is constant time.

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); }

sillysaurus3 13y ago
Heh. My first answer was "copy paste the algorithm from tarsnap," but then I thought I'd better explain it directly. Thank you for pasting it.
lotharrr 13y ago
Might it be even safer to squash 'rc' down to a single pair of values (0 or 1), rather than leaving the caller with the responsibility of testing a byte for zeroness safely? By leaking the 255 possible values for "not equal" to the caller, we're kind of punting the (smaller) problem, and they might do something nutty like add it to some other constant (incurring timing-leaking carries) before comparing the result against something. Of course, we're not just defending against surprises from the calling code, we're defending against compiler behavior too. We're trying to constrain its options so tightly that it has no choice but to emit a series of machine instructions that we know will run in constant time. If it weren't such a hassle, we'd write crypto_verify_bytes() in x86 assembly. It'd be lovely if our languages had a way to express these constraints directly, instead of phrasing them with artificially small types and low-level logical operations.
TheLoneWolfling 13y ago
A question. What prevents a compiler from optimizing that function to non-constant time? For example, by inserting a bailout condition (rc == 255) into the loop? (I am aware that it probably wouldn't, but "probably" in cryptographic contexts isn't generally good enough...)
- cperciva 13y ago
  Theoretically? Nothing at all. You could have a compiler which produces code which revs the CPU in such a way to output the complete works of Shakespeare in Morse code via the fluctuations in your laptop's fan speed, and it would be perfectly standard-compliant. Worse than that, there's things compilers actually do in practice, like optimizing away memset(sensitivedate, 0, sizeof(sensitivedata)) and you can't even protect yourself against that properly by using a (volatile *) cast since the compiler is perfectly within its rights to make extra copies of that data and even without optimization the memset will only zero one of the copies. (gcc in particular loves to copy data onto the stack, due to a broken register allocator.) I've been trying to convince some clang developers that we need to have a C language extension for "we're handling sensitive data here, don't optimize it in dangerous ways", but it's difficult to define exactly what optimizations could be problematic...
- zAy0LfpBZLC8mAC 13y ago
  Also, in interpreted languages, it's difficult to know whether the primitive operations actually are constant time, which is why I think the better universal solution is to hash both the MAC from the untrusted input as well as your own computed MAC once more with the same HMAC with a random key and only then do the comparison on the result of that. The HMAC should be constant time anyhow, and with this construction, it shouldn't matter much whether the final comparison is constant time.