3 ms·

Read the article[1] linked in yock's comment for the gory details, but to sum up: instead of having to calculate the entire set of possibilities for a given has

Read the article[1] linked in yock's comment for the gory details, but to sum up: instead of having to calculate the entire set of possibilities for a given hash, you only have to iterate just enough to get the first byte. Then you can do the same thing again for the next byte, and so on. You can't just fix this with some random timing or additional noise.. it's a very difficult problem to solve. It's telling that even the very smart person who did such a great write-up made a few mistakes again in initial attempts at demonstrating a corrected algorithm that actually blew the whole thing up again. Because it's so subtle, the odds are very good that most current systems are fallible to this. 1. https://codahale.com/a-lesson-in-timing-attacks/ https://codahale.com/a-lesson-in-timing-attacks/

SilasX 10y ago
I understand that much, but, as I said in my comment, that would only work if the partial match were informative about the full match. A partial password match is informative of what the full password is, but a partial hash collision is not informative about the full collision. By design, learning about one hash preimage tells you nothing about other hash preimages. By contrast, if you were comparing my submitted password to a stored password, I could use your response time to know that I got the first n characters right. Since n is a prefix of the password, I've learned something about the password, I can lock down those characters, and then guess more, etc. That much I understand. But the case you're talking about is a comparison of hashes. In that case, timing attacks can tell me that my guess's hash's first n characters match the password's hash's first n characters. So now what? How do I adapt future guesses to learn more characters? What have I learned about (a preimage of the hash of) the password? If partial hash collisions were, in any way, helpful in guessing the full collision, Bitcoin mining algorithms would adaptively change their guesses as they discovered that their nonces only led to a partial match.
- _asummers 10y ago
  Depending on the hash used, it could be subject to a length extension attack. That was one of the big engineering goals for SHA3, to not be susceptible to those. https://en.wikipedia.org/wiki/Length_extension_attack https://en.wikipedia.org/wiki/Length_extension_attack
- jamiesonbecker 10y ago
  To some extent, unless there is a flaw in the hash (fortunately, those are mythical;)), you're right, except leaking the hash itself can still leak useful data (here's a comment explaining how this can be used for an early-exit byte comparison[1]), and, for some hashes (such as MD5, SHA, etc) leaking the salt can significantly reduce the number of hashes that would need to be brute forced as well. Also, leaking the hash itself can provide a great deal of information about the scheme in use, which can either cause him to accelerate his attacks offline (DES!) or run away crying (bcrypt/scrypt!) :) 1. https://security.stackexchange.com/questions/111040/should-i-worry-about-remote-timing-attacks-on-string-comparison#comment198158_111046 https://security.stackexchange.com/questions/111040/should-i...

SilasX 10y ago

I understand that much, but, as I said in my comment, that would only work if the partial match were informative about the full match. A partial password match is informative of what the full password is, but a partial hash collision is not informative about the full collision. By design, learning about one hash preimage tells you nothing about other hash preimages. By contrast, if you were comparing my submitted password to a stored password, I could use your response time to know that I got the first n characters right. Since n is a prefix of the password, I've learned something about the password, I can lock down those characters, and then guess more, etc. That much I understand. But the case you're talking about is a comparison of hashes. In that case, timing attacks can tell me that my guess's hash's first n characters match the password's hash's first n characters. So now what? How do I adapt future guesses to learn more characters? What have I learned about (a preimage of the hash of) the password? If partial hash collisions were, in any way, helpful in guessing the full collision, Bitcoin mining algorithms would adaptively change their guesses as they discovered that their nonces only led to a partial match.

_asummers 10y ago
Depending on the hash used, it could be subject to a length extension attack. That was one of the big engineering goals for SHA3, to not be susceptible to those. https://en.wikipedia.org/wiki/Length_extension_attack https://en.wikipedia.org/wiki/Length_extension_attack
jamiesonbecker 10y ago
To some extent, unless there is a flaw in the hash (fortunately, those are mythical;)), you're right, except leaking the hash itself can still leak useful data (here's a comment explaining how this can be used for an early-exit byte comparison[1]), and, for some hashes (such as MD5, SHA, etc) leaking the salt can significantly reduce the number of hashes that would need to be brute forced as well. Also, leaking the hash itself can provide a great deal of information about the scheme in use, which can either cause him to accelerate his attacks offline (DES!) or run away crying (bcrypt/scrypt!) :) 1. https://security.stackexchange.com/questions/111040/should-i-worry-about-remote-timing-attacks-on-string-comparison#comment198158_111046 https://security.stackexchange.com/questions/111040/should-i...