19 ms·

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.
    - ectoplasm 11y ago
      A perfect hash is a function in the mathematical sense in that there is a unique output for each input. So, hash the stored password ahead of time, and hash the challenge password after receiving it, and then compare the two hashes. You don't need collision detection, since a match can only come from two identical keys. You don't generate passwords for people, although you could, as long as you don't reveal your hash function. There are useless perfect hashes, like "password + 1", and there are much better ones that produce near-random output.
      - TheLoneWolfling 11y ago
        I know what a perfect hash is. But a) pigeonhole principle (you need an output at least as long as the longest string you'll encounter), and b) I was under the impression that perfect hash schemes require you to know the set of strings encountered ahead-of-time. Could you give me an example of a perfect hash function that is suitable and secure enough for password use? I do not know of any.
        ectoplasm 11y ago
        You're right, there's a hard limit on password length. That might be fatal if you're using diceware, I don't know if you could accommodate passwords that big. As for the set of strings, just assume it's every string possible, so 256^8 strings for an 8 byte password. That's only 16384 petabytes. All of the perfect hash functions I've found require knowing all of the keys ahead of time. You might not be able to fit 16384 PB on your hard drive or in memory. (Hey, I don't know. You could work at LLNL.) But I think that if you knew you might use any key in the space, and you didn't insist on a minimal perfect hash, i.e. one where there is a 1:1 mapping from hashes back to keys, that you could write such a function without having all of the keys. If you did this, you'd also need to prove you were generating a unique and effectively random hash. If I was a crypto academic, that might be an interesting line of research. I'd be kind of surprised if nobody ever tried this though, and there's probably a decent amount of literature to pore over. I guess most people use perfect hashes for hashtables and not as a defense against timing attacks.

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.
  - ectoplasm 11y ago
    A perfect hash is a function in the mathematical sense in that there is a unique output for each input. So, hash the stored password ahead of time, and hash the challenge password after receiving it, and then compare the two hashes. You don't need collision detection, since a match can only come from two identical keys. You don't generate passwords for people, although you could, as long as you don't reveal your hash function. There are useless perfect hashes, like "password + 1", and there are much better ones that produce near-random output.
    - TheLoneWolfling 11y ago
      I know what a perfect hash is. But a) pigeonhole principle (you need an output at least as long as the longest string you'll encounter), and b) I was under the impression that perfect hash schemes require you to know the set of strings encountered ahead-of-time. Could you give me an example of a perfect hash function that is suitable and secure enough for password use? I do not know of any.
      - ectoplasm 11y ago
        You're right, there's a hard limit on password length. That might be fatal if you're using diceware, I don't know if you could accommodate passwords that big. As for the set of strings, just assume it's every string possible, so 256^8 strings for an 8 byte password. That's only 16384 petabytes. All of the perfect hash functions I've found require knowing all of the keys ahead of time. You might not be able to fit 16384 PB on your hard drive or in memory. (Hey, I don't know. You could work at LLNL.) But I think that if you knew you might use any key in the space, and you didn't insist on a minimal perfect hash, i.e. one where there is a 1:1 mapping from hashes back to keys, that you could write such a function without having all of the keys. If you did this, you'd also need to prove you were generating a unique and effectively random hash. If I was a crypto academic, that might be an interesting line of research. I'd be kind of surprised if nobody ever tried this though, and there's probably a decent amount of literature to pore over. I guess most people use perfect hashes for hashtables and not as a defense against timing attacks.