5 ms·

And then your compiler will optimize it to this: int token_length = strlen(token); // Just get this out of the way now; no need to dawdle // (

And then your compiler will optimize it to this: int token_length = strlen(token); // Just get this out of the way now; no need to dawdle // (because the length of a token is generally known) if (token_length != strlen(input)) { return false; } // No need to worry about mismatched buffer lengths at this point for(int i=0; i<token_length; i++) { if (token[i] != input[i]) { return false; } } return true; And all of a sudden the timing attack is back. You cannot write a constant-time function in portable C / C++, and trying to do so is a fool's game.

cybojanek 11y ago
Yes you can - take the hash of the input and token, and compare those. Now you're trying to cause a sha256 collision. Good luck!
- delinka 11y ago
  You still have to perform the byte-by-byte comparison and this is where TheLoneWolfling alleges the optimizations kick in and give away secrets. However, from my testing, the variations in timing are unpredictable (I get variations on compare speed on different runs of the same program with the same input) and small and would be swallowed up by variations in network latency.
  - rb12345 11y ago
    You could probably do that relatively safely with bit operations, but I expect to be proved wrong. Something like this should work: /* Swap char for uint<register_size> for speed */ #define CMP_TYPE char /* Assuming char* sha256(char* input); */ CMP_TYPE* input_hash=(CMP_TYPE*) sha256(input); CMP_TYPE* token_hash=(CMP_TYPE*) sha256(token); /* Precomputed? */ /* max_pos=32 for char on most systems */ int max_pos=256 >> (3 + sizeof(CMP_TYPE)); char cmp=0; for (int i=0;i<max_pos;i++) { cmp = cmp | (token_hash[i] ^ input_hash[i]); } return (cmp != 0); The reason for the CMP_TYPE #define is so that you can optimise the comparison by replacing char with uint32 or uint64.
    - TheLoneWolfling 11y ago
      Again, the compiler is free to optimize that to data-dependent time. It's relatively unlikely to do so on current machines (the time saved is unlikely to be worth the potential of a pipeline stall), but it's free to do so. For instance, it's legal for the compiler to insert a strcmp fallthrough (`if input == token: return true`, or rather the strcmp equivalent) at the start, I'm pretty sure.
  - georgerobinson 11y ago
    Since an optimizing compiler is free to go to town on functions such as string comparison, are these functions typically written in assembler per-architecture? I.e. one for x86 and x86-64, another for MIPS, RISC, etc?
  - TheLoneWolfling 11y ago
    I have a bunch of other replies in this thread that touch on this, but suffice to say it's not just the comparison that matters. For one thing, you have to assume that the SHA function is data-independent time (which, again, good luck doing in C / C++). For another thing, noise in timing attacks doesn't prevent them. Even at levels of noise that seemingly obscure everything. And it's a very bad thing to rely on network latency being unpredictable enough.
- TheLoneWolfling 11y ago
  a) You're just punting the timing attack off to the SHA algorithm. b) There is no SHA algorithm in the C / C++ standard library (that I know of), muchless a guaranteed constant-time (or rather, data-independent) one. c) The compiler is well within its rights to insert "busy_loop_for_ms(input_char);" anywhere it wishes. It is unlikely to do so, but it is allowed to. As I said: C and C++ don't have any notion of constant or variable time.
- TheLoneWolfling 11y ago
  Except that that still leaves you open to a dictionary attack. Or rather, it accelerates a dictionary attack from O(sizeof(dictionary)) tries to O(length(hash)) tries. (Let's suppose you are comparing by hex digits. You try 16 dictionary "words" whose hashes start with 0...f. One of those should take slightly longer. You then try 16 dictionary "words" whose hashes start with the digit found previously with different second digits. (Skip any digits that you don't have a word for.) One of those should take slightly longer... Repeat until found.) This can be mitigated with a salt - if and only if you manage to prevent the user from figuring out how your salting scheme works.
delinka 11y ago
I was willing to concede your point, but I tested first. Using clang to compile, I did some profiling on my function optimized to various levels (-O0...-O3, -Os, -Ofast) with various inputs. The variation in timing is noise (I get the same variation on the same test inputs in different runs of the program.) I'd be curious to know whether you can provide a combination of compiler and compiler options that do indeed produce noticeable variations in timing as a function of the inputs. "You cannot write a constant-time function in portable C / C++..." perhaps you mean that we can't outsmart compiler optimizations. Without optimizations ("Debug" configuration), the code runs exactly as written. Ultimately, I'm going to prefer code with obvious intent regardless of how the compiler will optimize the thing. We'll just have to find a way around this timing attack business.
- TheLoneWolfling 11y ago
  I would be very surprised if a compiler on a modern high-performance processor actually did this optimization - as deep pipelines and speculative execution mean that the additional conditional branch per loop may hurt more than it helps. That being said, on a simple architecture - namely a shallow pipeline - this sort of thing is an "obvious" optimization. And w.r.t. "without optimizations" - there is no such thing at the C / C++ level. There are computer architectures where optimizations pretty much have to be done, for instance. (Many architectures with compile-time scheduling, for instance.) For instance, if you have a dataflow machine it may end up running this in non-constant time. And I'll note that modern x86 processors are looking more and more like dataflow machines.
mikeash 11y ago
What if you mark token, input, and match_count as volatile?
- TheLoneWolfling 11y ago
  In practice, it'd probably work. In theory? The compiler is still free to add data-dependent delays. For an "evil" example, a compiler could do this: ... for(int i=0; i<token_length; i++) { char temp = input[i]; if (token[i] == temp) { match_count++; } wait_for_ns(temp); } It wouldn't make sense for a compiler to do so - but it is allowed. It
  - mikeash 11y ago
    That's a good point. However, even if you wrote the routine in assembly, the CPU could pull a similar trick. At some point you have to give up and trust the tool not to do something too catastrophically stupid. Whether that point is at the CPU or the C compiler (with sufficiently paranoid C code) or elsewhere, I'm not sure.
    - TheLoneWolfling 11y ago
      Yep. A classic example is multiplication - which isn't constant-time on modern machines but was on many older ones. Currently, CMOV is looking like it could become the same thing. It currently takes data-independent time. But is not guaranteed to do so, and very well may not in the future. The distinction is that hardware tends to change slower than software. You generally have multiple compiler versions per hardware version (possible exception of embedded processors, but even then...).
ectoplasm 11y ago
Why can't you just set a bit for each non-match and then bitwise-or them all together, returning false if non-zero? I don't think a compiler can optimize that away.
- TheLoneWolfling 11y ago
  It's the exact same optimization either way. One is just relying on adding a positive number never makes a number > 0 0 again. The other is just relying on oring a bit to a non-zero number never makes it zero again.
  - ectoplasm 11y ago
    I don't understand. I thought the timing attack was because the logic short circuits when it finds a non-match. How does the compiler short circuit the bitwise-or? At first I was thinking you could write the bits out to a separate word, but I think this suffices: uint result = 0; for (i = 0; i < length; i++) result |= notmatch (i); return result == 0; You would need value range analysis for the use of result in addition to the insertion of an extra test and branch to short circuit the loop, plus a model of what |= does to values. Do any compilers actually do this? But, actually I'm kind of confused about your first point. What optimizations did your compiler use to eliminate the match_count++ and hoist the return into the loop?
    - TheLoneWolfling 11y ago
      As I've said elsewhere, current compilers are unlikely to do so. Current processors have too deep a pipeline to make it worth it. But on an architecture with a short pipeline it can be worth it for a compiler to do so. And it's simple, in theory if nothing else. Note that once result has a bit set, result cannot ever return to zero. Hence, if result has a bit set, one can return false immediately. And all of a sudden you lose the constant-time part. As for how a current compiler could do so? Look at what happens if/when the loop is unrolled. That current compilers don't tend to do this sort of optimization makes it only more dangerous - because people do not go back and re-examine old code nearly as often as they should. Much less check the assembly every time they update the compiler.

cybojanek 11y ago

Yes you can - take the hash of the input and token, and compare those. Now you're trying to cause a sha256 collision. Good luck!

delinka 11y ago
You still have to perform the byte-by-byte comparison and this is where TheLoneWolfling alleges the optimizations kick in and give away secrets. However, from my testing, the variations in timing are unpredictable (I get variations on compare speed on different runs of the same program with the same input) and small and would be swallowed up by variations in network latency.
- rb12345 11y ago
  You could probably do that relatively safely with bit operations, but I expect to be proved wrong. Something like this should work: /* Swap char for uint<register_size> for speed */ #define CMP_TYPE char /* Assuming char* sha256(char* input); */ CMP_TYPE* input_hash=(CMP_TYPE*) sha256(input); CMP_TYPE* token_hash=(CMP_TYPE*) sha256(token); /* Precomputed? */ /* max_pos=32 for char on most systems */ int max_pos=256 >> (3 + sizeof(CMP_TYPE)); char cmp=0; for (int i=0;i<max_pos;i++) { cmp = cmp | (token_hash[i] ^ input_hash[i]); } return (cmp != 0); The reason for the CMP_TYPE #define is so that you can optimise the comparison by replacing char with uint32 or uint64.
  - TheLoneWolfling 11y ago
    Again, the compiler is free to optimize that to data-dependent time. It's relatively unlikely to do so on current machines (the time saved is unlikely to be worth the potential of a pipeline stall), but it's free to do so. For instance, it's legal for the compiler to insert a strcmp fallthrough (`if input == token: return true`, or rather the strcmp equivalent) at the start, I'm pretty sure.
- georgerobinson 11y ago
  Since an optimizing compiler is free to go to town on functions such as string comparison, are these functions typically written in assembler per-architecture? I.e. one for x86 and x86-64, another for MIPS, RISC, etc?
- TheLoneWolfling 11y ago
  I have a bunch of other replies in this thread that touch on this, but suffice to say it's not just the comparison that matters. For one thing, you have to assume that the SHA function is data-independent time (which, again, good luck doing in C / C++). For another thing, noise in timing attacks doesn't prevent them. Even at levels of noise that seemingly obscure everything. And it's a very bad thing to rely on network latency being unpredictable enough.
TheLoneWolfling 11y ago
a) You're just punting the timing attack off to the SHA algorithm. b) There is no SHA algorithm in the C / C++ standard library (that I know of), muchless a guaranteed constant-time (or rather, data-independent) one. c) The compiler is well within its rights to insert "busy_loop_for_ms(input_char);" anywhere it wishes. It is unlikely to do so, but it is allowed to. As I said: C and C++ don't have any notion of constant or variable time.
TheLoneWolfling 11y ago
Except that that still leaves you open to a dictionary attack. Or rather, it accelerates a dictionary attack from O(sizeof(dictionary)) tries to O(length(hash)) tries. (Let's suppose you are comparing by hex digits. You try 16 dictionary "words" whose hashes start with 0...f. One of those should take slightly longer. You then try 16 dictionary "words" whose hashes start with the digit found previously with different second digits. (Skip any digits that you don't have a word for.) One of those should take slightly longer... Repeat until found.) This can be mitigated with a salt - if and only if you manage to prevent the user from figuring out how your salting scheme works.

delinka 11y ago

I was willing to concede your point, but I tested first. Using clang to compile, I did some profiling on my function optimized to various levels (-O0...-O3, -Os, -Ofast) with various inputs. The variation in timing is noise (I get the same variation on the same test inputs in different runs of the program.) I'd be curious to know whether you can provide a combination of compiler and compiler options that do indeed produce noticeable variations in timing as a function of the inputs. "You cannot write a constant-time function in portable C / C++..." perhaps you mean that we can't outsmart compiler optimizations. Without optimizations ("Debug" configuration), the code runs exactly as written. Ultimately, I'm going to prefer code with obvious intent regardless of how the compiler will optimize the thing. We'll just have to find a way around this timing attack business.

TheLoneWolfling 11y ago
I would be very surprised if a compiler on a modern high-performance processor actually did this optimization - as deep pipelines and speculative execution mean that the additional conditional branch per loop may hurt more than it helps. That being said, on a simple architecture - namely a shallow pipeline - this sort of thing is an "obvious" optimization. And w.r.t. "without optimizations" - there is no such thing at the C / C++ level. There are computer architectures where optimizations pretty much have to be done, for instance. (Many architectures with compile-time scheduling, for instance.) For instance, if you have a dataflow machine it may end up running this in non-constant time. And I'll note that modern x86 processors are looking more and more like dataflow machines.

mikeash 11y ago

What if you mark token, input, and match_count as volatile?

TheLoneWolfling 11y ago
In practice, it'd probably work. In theory? The compiler is still free to add data-dependent delays. For an "evil" example, a compiler could do this: ... for(int i=0; i<token_length; i++) { char temp = input[i]; if (token[i] == temp) { match_count++; } wait_for_ns(temp); } It wouldn't make sense for a compiler to do so - but it is allowed. It
- mikeash 11y ago
  That's a good point. However, even if you wrote the routine in assembly, the CPU could pull a similar trick. At some point you have to give up and trust the tool not to do something too catastrophically stupid. Whether that point is at the CPU or the C compiler (with sufficiently paranoid C code) or elsewhere, I'm not sure.
  - TheLoneWolfling 11y ago
    Yep. A classic example is multiplication - which isn't constant-time on modern machines but was on many older ones. Currently, CMOV is looking like it could become the same thing. It currently takes data-independent time. But is not guaranteed to do so, and very well may not in the future. The distinction is that hardware tends to change slower than software. You generally have multiple compiler versions per hardware version (possible exception of embedded processors, but even then...).

ectoplasm 11y ago

Why can't you just set a bit for each non-match and then bitwise-or them all together, returning false if non-zero? I don't think a compiler can optimize that away.

TheLoneWolfling 11y ago
It's the exact same optimization either way. One is just relying on adding a positive number never makes a number > 0 0 again. The other is just relying on oring a bit to a non-zero number never makes it zero again.
- ectoplasm 11y ago
  I don't understand. I thought the timing attack was because the logic short circuits when it finds a non-match. How does the compiler short circuit the bitwise-or? At first I was thinking you could write the bits out to a separate word, but I think this suffices: uint result = 0; for (i = 0; i < length; i++) result |= notmatch (i); return result == 0; You would need value range analysis for the use of result in addition to the insertion of an extra test and branch to short circuit the loop, plus a model of what |= does to values. Do any compilers actually do this? But, actually I'm kind of confused about your first point. What optimizations did your compiler use to eliminate the match_count++ and hoist the return into the loop?
  - TheLoneWolfling 11y ago
    As I've said elsewhere, current compilers are unlikely to do so. Current processors have too deep a pipeline to make it worth it. But on an architecture with a short pipeline it can be worth it for a compiler to do so. And it's simple, in theory if nothing else. Note that once result has a bit set, result cannot ever return to zero. Hence, if result has a bit set, one can return false immediately. And all of a sudden you lose the constant-time part. As for how a current compiler could do so? Look at what happens if/when the loop is unrolled. That current compilers don't tend to do this sort of optimization makes it only more dangerous - because people do not go back and re-examine old code nearly as often as they should. Much less check the assembly every time they update the compiler.