[tor-dev] memcmp() & co. timing info disclosures?

[Nick Mathewson]

On Sat, May 7, 2011 at 12:47 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On Fri, 6 May 2011 23:14:58 -0400
> Nick Mathewson <nickm at freehaven.net> wrote:
>
>> Also, as I said on the bug, doing a memcmp in constant time is harder
>> than doing eq/neq.  I *think* that all of the cases where we care
>> about memcmp returning a tristate -1/0/1 result, we don't need
>> data-independence... but in case we *do* need one, we'll have to do
>> some malarkey like
>>
>> int memcmp(const void *m1, const void *m2, size_t n)
>> {
>> /*XXX I don't know if this is even right; I haven't tested it at all */
>>   const uint8_t *b1 = m1, *b2 = m2;
>>   int retval = 0;
>>
>>   while (n--) {
>>     const uint8_t v1 = b1[n], v2 = b2[n];
>>     int diff = (int)v1 - (int)v2;
>>     retval = (v1 == v2) * retval + diff;
>>   }
>>
>>   return retval;
>> }
>>
>> which frankly makes me sad.  I bet there's a better way to go.
>
> See attached.  This one is also untested (and I didn't even put the
> “#include <stdint.h>” in the file), but it *should* work.
>
> My technique for calculating equal_p came from my uint32-based
> crypto_verify function in my previous message, which was in turn based
> partly on DJB's crypto_verify functions and partly on a disassembly of
> what GCC compiled DJB's functions to on a Fedora 12 AMD64 box.  But I
> couldn't tell that the technique was correct, so this time I added
> comments to it.

Clever!  It does look it *should* work.  Somewhere along the line we
should test the heck out of it and more sure it does.

(Also, Tor *does* assume that the arithmetic is two's complement: we
check for it in configure.in and die horribly in torint.h if it
isn't.)

Also, I suggest that we move as much of this as possible over to the
bugtracker: discussing this in two places is giving me whiplash.  I've
posted a suggested plan of attack there.

Now alas I should sleep.

yrs,
-- 
Nick