[Ur] openid fails to build on OS X

[austin seipp]

So I did a little bit of investigation on this. It's worth getting
right since I think security is such a compelling point of UrWeb. I
snipped Robin's original secCmp function out and looked at the ASM
output from GCC at various version/optimization levels.

Here's the TL;DR: On OS X, both GCC 4.2.1 and Clang (3.0svn, trunk
132702) exhibit predictable behavior that isn't susceptible to a
timing attack at -O0 to -O3 optimization levels. It's very typical of
what you would expect of the function. But with Linux & GCC 4.6.1,
while -O0 optimization is fine, the -O3 version generates a lot of SSE
SIMD based code speed. It's pretty complex. I don't want to decipher
it to the point to be able to trust it. I don't want anyone else to
either. But there's an simple solution that will kill optimization for
this one particular function, without much newer machinery and it
makes the results easy to see and verify.

Here's a version that produces predictable results:

uw_Basis_bool uw_OpenidFfi_secCmp(uw_context ctx, uw_Basis_string s1,
uw_Basis_string s2) {
  int i, x = 0, len1 = strlen(s1);
  if (len1 != strlen(s2)) return 0;
  for (i = 0; i < len1; ++i) {
        __asm__ __volatile__ ("");
        x |= s1[i] ^ s2[i];
  }
  return x == 0;
}

The volatile asm statement in the middle of the loop body is treated
like a black box by GCC - it can make absolutely 0 assumptions about
what is contained in it, so optimizations across the loop body (things
like peeling/unrolling) are inhibited as a result. The results seem
consistent across compilers, in 32bit and 64bit mode.

I'd advise this change me made to the source code, along with a very
hefty comment explaining the necessity of it (perhaps linking to this
thread or something through the mailing list web interface?)

I can provide some assembly results for completeness if necessary, but
I do believe this should inhibit all the optimizations possible for
the loop. Checking this for your favorite compiler is left as an
exercise to the reader. At -O3, GCC 4.6.1 generated code very similar
to GCC 4.2 or Clang for the loop body with this dummy statement
inserted - a consistent check of the strlen results for the fast-path
exit, followed by a simple loop that xor's 2 bytes, stores an or'd
result, and compares with 0 upon return (OK, all the compilers also
catch the special case that iff (strlen(s1) == strlen(s2) == 0) then
the result is trivially true and it can exit early - but that doesn't
otherwise change loop semantics or open any attack vector.)

On Sun, Jul 17, 2011 at 6:25 AM, Adam Chlipala <adamc at impredicative.com> wrote:
> Robin Green wrote:
>>
>> On Sat, 16 Jul 2011 17:01:12 -0500, austin seipp<as at hacks.yi.org>  wrote:
>>
>>>
>>> Robin, while I understand the principle behind the secure comparison
>>> function (to avoid a timing attack based on string length,) is there a
>>> particular reason you need GCC to optimize at level 0? Or is it just
>>> the fact you don't want anything happening under your nose?
>>>
>>
>> It's really just paranoia about future versions of GCC or other
>> compilers doing some clever optimisation that makes a timing attack
>> possible. I think you can just remove the GCC-specific attribute.
>>
>
> I'm happy to prepare a Mercurial changeset myself which removes that
> annotation, or to accept one from one of you.  Let me know how you'd like to
> proceed.
>
> I'm counting on y'all to make sure this change doesn't reopen the timing
> attack that motivated Robin's patch.
>
> _______________________________________________
> Ur mailing list
> Ur at impredicative.com
> http://www.impredicative.com/cgi-bin/mailman/listinfo/ur
>



-- 
Regards,
Austin