Here's the current code:
http://code.google.com/p/keyczar/source/browse/trunk/python/...
From the code:
correctMac = self.Sign(msg)
if len(sig_bytes) != len(correctMac):
return False
result = 0
for x, y in zip(correctMac, sig_bytes):
result |= ord(x) ^ ord(y)
return result == 0
This code performs the same ALU ops on every byte of the MAC, and does not perform any bytewise comparisons if the MACs aren't the same size. It's not timeable.There are no tests for it in the keyczar that I could find. I doubt they tested it.
The reasons are many... but this is python, so each operation is much more complicated than C/asm. There are lots of branches, memory usage and cache effects - so code is much more input dependant - especially the integer ops used here. Take a look at this code to see one of the reasons why this python code has variable timing depending on input(like most code does).
x,y = 3,3
id(x) == id(y) # python shares ints in different variables
Perhaps whatever you're doing to create the "off by one" case is disrupting the cache, and you're just seeing the effects of that.
Given the restrictions, this is actually impossible. (the operation has to be quick enough that it doesn't significantly erode user satisfaction, and the smallest possible "sleep" is a single machine instruction). Your adversary can easily collect millions of samples, or even a lot more. You cannot hide the latency difference well enough.
I just tested the keyczar routine, and it can still be found.
The sleep needs to be long enough, and random enough that it makes the other variance statistically insignificant.
cheers,