3 ms·

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 loo

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.

3 ms·

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 loo

by TheLoneWolfling 13y ago

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.