3 ms·

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 bitwis

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.
- ectoplasm 11y ago
  Let's assume you're right. Why can't you choose characters to compare randomly, until you've compared them all?
  - TheLoneWolfling 11y ago
    You can still do a timing attack against that. Suppose the password is "password". You do a timing attack to find the correct length, then you start trying "aaaaaaaa", "bbbbbbbb", "cccccccc", ... The ones that take less time on average are the ones that contain a letter from the password. You can go from there. Ever played mastermind? It's a mitigation but it doesn't prevent the attack. Not to mention: how exactly will you check that you've compared them all?
    - ectoplasm 11y ago
      Ah, mastermind. I think you mean the ones that take more time on average contain a letter from the password, not less. Anyway, good point. I was thinking you could maintain an array of flags to indicate whether you've compared a certain position before, and a count of all the compared positions so far. Alright, here are my other ideas: 1) Properly chosen 8-character passwords are pretty strong, right? So why not copy all of the 8-bit chars into a u64 and compare that directly? You can treat longer passwords as a series of 8-char passwords. Assumes a machine that won't short circuit on u64_a == u64_b. Less effective for 32-bit. The compiler won't undo this since it's an optimization (1x aligned 64-bit compare is more efficient than 8x 8-bit compares, seven of which are unaligned). 2) Introduce a random delay after the byte-wise comparison is done that is up to 10x the length of the comparison. The comparison variance gets lost in delay variance. I know, a mitigation, but it's effective. Combine with random selection of characters for more effectiveness. 3) Use a perfect hash of the password. You don't need to compare keys after a perfect hash. Thanks for humoring me.
      - TheLoneWolfling 11y ago
        Whoops, yep, that is incorrect. Should be more time, as you said. 1) That causes massive problems for people (like me) who use passphrases. (I use diceware passwords for anything I don't use a password manager for. So things like "corn umpire khaki dow heave hiatt sis steal". That's ~103 bits of entropy (massive overkill for most things), and yet is a whole lot easier to remember than, say, "FlyaJdqJW6kvyUQeE" - which is ~101 bits of entropy (17 random upper/lower/digit characters). It also assumes that the machine doesn't short-circuit, as you say. And, again, you're assuming that the compiler doesn't undo it. Just because it won't be undone by optimizations on current machines doesn't mean it won't be undone by optimizations on future ones. On a RISC architecture, for instance, a 64-bit compare may not even exist - it may be implemented by 8-bit compares. Or 16, or 32. Whatever. 2) Ever heard of the german tank problem? That will not drown out the comparison, not at all. I can defeat your example (10x noise as comparison time) with >90% accuracy with 100 samples. (Just take samples, and take the mean of the sample minimum and maximum.) 3) Without leaking other people's passwords every time you generate a password for someone? I find this sort of conversation intriguing. I want things to be more secure, I just don't know of a good way to do so.

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.

ectoplasm 11y ago
Let's assume you're right. Why can't you choose characters to compare randomly, until you've compared them all?
- TheLoneWolfling 11y ago
  You can still do a timing attack against that. Suppose the password is "password". You do a timing attack to find the correct length, then you start trying "aaaaaaaa", "bbbbbbbb", "cccccccc", ... The ones that take less time on average are the ones that contain a letter from the password. You can go from there. Ever played mastermind? It's a mitigation but it doesn't prevent the attack. Not to mention: how exactly will you check that you've compared them all?
  - ectoplasm 11y ago
    Ah, mastermind. I think you mean the ones that take more time on average contain a letter from the password, not less. Anyway, good point. I was thinking you could maintain an array of flags to indicate whether you've compared a certain position before, and a count of all the compared positions so far. Alright, here are my other ideas: 1) Properly chosen 8-character passwords are pretty strong, right? So why not copy all of the 8-bit chars into a u64 and compare that directly? You can treat longer passwords as a series of 8-char passwords. Assumes a machine that won't short circuit on u64_a == u64_b. Less effective for 32-bit. The compiler won't undo this since it's an optimization (1x aligned 64-bit compare is more efficient than 8x 8-bit compares, seven of which are unaligned). 2) Introduce a random delay after the byte-wise comparison is done that is up to 10x the length of the comparison. The comparison variance gets lost in delay variance. I know, a mitigation, but it's effective. Combine with random selection of characters for more effectiveness. 3) Use a perfect hash of the password. You don't need to compare keys after a perfect hash. Thanks for humoring me.
    - TheLoneWolfling 11y ago
      Whoops, yep, that is incorrect. Should be more time, as you said. 1) That causes massive problems for people (like me) who use passphrases. (I use diceware passwords for anything I don't use a password manager for. So things like "corn umpire khaki dow heave hiatt sis steal". That's ~103 bits of entropy (massive overkill for most things), and yet is a whole lot easier to remember than, say, "FlyaJdqJW6kvyUQeE" - which is ~101 bits of entropy (17 random upper/lower/digit characters). It also assumes that the machine doesn't short-circuit, as you say. And, again, you're assuming that the compiler doesn't undo it. Just because it won't be undone by optimizations on current machines doesn't mean it won't be undone by optimizations on future ones. On a RISC architecture, for instance, a 64-bit compare may not even exist - it may be implemented by 8-bit compares. Or 16, or 32. Whatever. 2) Ever heard of the german tank problem? That will not drown out the comparison, not at all. I can defeat your example (10x noise as comparison time) with >90% accuracy with 100 samples. (Just take samples, and take the mean of the sample minimum and maximum.) 3) Without leaking other people's passwords every time you generate a password for someone? I find this sort of conversation intriguing. I want things to be more secure, I just don't know of a good way to do so.