Hacker News new | ask | show | jobs
by spicyj 5122 days ago
> The easiest way to defeat this attack is, instead of directly comparing two strings, compare their mappings under a collision-resistant hash function.

Is this really the best way to compare strings without giving away timing info?
2 comments
tptacek 5122 days ago
No. It's A way to do it, but not the fastest or the simplest. An easier, faster way to do it is what Rails does (after Nate Lawson via Coda Hale told them how): accumulate the XORs of each offset of both strings and then verify that they add up to zero.
link
blutonium 5122 days ago
Yeah, the Rails code is pretty easy to follow too: https://github.com/rails/rails/blob/f3e1b21ca91afbd97f33d1e5...
link
marshray 5122 days ago
> accumulate the XORs of each offset of both strings and then verify that they add up to zero

If you do that in a language with an optimizing compiler or JIT runtime you'd better look at the generated code and/or do your own timing measurements. A sufficiently-smart optimizer could recognize that the first difference encountered allows for early loop termination.

link
reitzensteinm 5122 days ago
What's wrong with simply doing a traditional compare, but not exiting early when it's found the two strings don't match?

I see how the xor method works, but not why it's superior.

Also, it would seem that you'd be leaking information about the size of the other string with either method (whether you exit early or not when you run past the length of one of the strings) - not a problem when comparing hashes presumably, but is it never a concern?

I don't think you'd be leaking that information if you hashed both strings and compared the hash, because it wouldn't stop getting faster when the shorter string gets shorter.

link
gchpaco 5122 days ago
Compiler optimizations, CPU pipeline and branch prediction would be my guess, although I'm sure someone else can jump in with more detail. XOR is basically immune to optimized tricks.
link
reitzensteinm 5122 days ago
Ah, that does make sense. Thanks!
link
jcoglan 5122 days ago
Not the best, but most string comparison methods are designed to fail as soon as possible, which is not appropriate for this use case. Compare the entire input, or use some misdirection to destroy the relationship between correctness and time.

This is just one of the easier ways. It's effective and easy to code.

link