[security] Widespread Timing Vulnerabilities in OpenID implementations

Andrew Arnott andrewarnott at gmail.com
Sat Jul 17 03:50:36 UTC 2010


Answers inline...

On Thu, Jul 15, 2010 at 4:20 PM, Nate Lawson <nate at rootlabs.com> wrote:

> Andrew Arnott wrote:
> > These six lines of code turn out to be ~*100 times slower* than the
> built-in
> > .NET String.Equals function.  I don't know why there is such a perf
> > difference, but apparently .NET has some serious string equality check
> > optimizations in their native code.  Has anyone else compared the
> > performance of their language's native string equality check function and
> > this hand-written alternative?
>
> We're doing that as part of our talk. Did you compare 100% correct
> strings or were they different? Obviously, a compare that terminates
> early will be faster for non-matching input.
>

I test two strings.  One is a total mismatch (which means only one character
is compared in the insecure case), and the other is a match except for the
very last character (so all characters are compared, but it still fails).


>
> When you say 100x slower, what are your actual numbers in terms of
> nanoseconds per byte for each version?
>

Upon measuring again, I see it is 30X slower rather than 100X I don't know
if it was a timing difference or a miscalculation the first time.  In .NET
String.Equals, each character takes .39 nanoseconds, in the bitwise XOR
operation each character takes 11.88 nanoseconds.  Just to double-check my
math conversion routine, here are the numbers again in scientific notation:
String.Equals: 3.912E-10 seconds per character
XOR method: 1.189E-08 seconds per character

My method of measure was to compare 5000 character strings 4000 times, then
to divide the elapsed time for each method by 5000*4000.

I tried "more obvious" implementations that just did == and set boolean
flags, but they were even slower than XOR, and had a greater time variation
depending on how closely the string matched than the XOR method did.  So I
guess the XOR method is the way to go (at least for .NET).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openid.net/pipermail/openid-security/attachments/20100716/20ad8c67/attachment.html>


More information about the security mailing list