News for hackers. Stuff that matters.
Re:Why you should never use hash functions for message authe... by tptacek on Saturday June 09, 2012 @03:08PM (#4088975)
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.
Re:Why you should never use hash functions for message authe... by blutonium on Saturday June 09, 2012 @03:45PM (#4089084)
Yeah, the Rails code is pretty easy to follow too: https://github.com/rails/rails/blob/f3e1b21ca91afbd97f33d1e5...
Re:Why you should never use hash functions for message authe... by marshray on Saturday June 09, 2012 @05:22PM (#4089331)
> 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.

Re:Why you should never use hash functions for message authe... by reitzensteinm on Saturday June 09, 2012 @06:27PM (#4089517)
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.

Re:Why you should never use hash functions for message authe... by gchpaco on Saturday June 09, 2012 @06:36PM (#4089538)
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.
Re:Why you should never use hash functions for message authe... by reitzensteinm on Saturday June 09, 2012 @10:18PM (#4089973)
Ah, that does make sense. Thanks!