There is a security flaw in the current version of the Google Keyczar
library. The impact is that an attacker could forge signatures for
data that was "signed" with the SHA-1 HMAC algorithm (the default
algorithm).
Firstly, I'm really glad to see more high-level libraries being
developed so that programmers don't have to work directly with
algorithms. Keyczar is definitely a step in the right direction.
Thanks to all the people who developed it.
The problem is that the HMAC verify function (python src/keyczar/
keys.py, Java src/org/keyczar/HmacKey.java) leaks timing information
based on how long a verify operation takes to fail. The function is
defined as follows for the HMAC mode:
Python:
def Verify(self, msg, sig_bytes):
return self.Sign(msg) == sig_bytes
Java:
return Arrays.equals(hmac.doFinal(), sigBytes);
Since the return value is a SHA-1 hash string, the operation devolves
to a byte-by-byte compare against sig_bytes. In both python and Java,
this is a classic sequence comparison that terminates early once an
incorrect match is found. This allows an attacker to iteratively try
various HMAC values and see how long it takes the server to respond.
The longer it takes, the more characters he has correct.
It may be non-intuitive, but the symmetric nature of MACs means the
correct MAC value for an arbitrary message is a secret on-par with key
material. If the attacker knows the correct MAC for a message of his
choosing, he can then send that value to forge authentication of the
message to the server.
I've implemented a simple test server using the python version of
Keyczar. It verifies an HMAC and sends back "yes" or "no" if the value
is correct. I then wrote a client in C that connects to the server and
tries various values for the HMAC. It tries each value multiple times
and records a set of TSC differences for each. These can be fed to a
program like ministat to decide when a significant difference has been
confirmed (based on mean and stddev).
http://www.freebsd.org/cgi/man.cgi?query=ministat&apropos=0&sektion=0&manpath=FreeBSD+8-current&format=html
I can confirm that localhost tests have a discernible difference,
based on whether the first byte is correct. I have not optimized the
attack to work over a LAN or the Internet yet. However, this does not
mean remote attacks are infeasible. Where jitter and other noise is
present in the samples, an attacker just needs to collect more data to
average it out. Remote timing attacks on SSL have been demonstrated
where the timing difference was only a few native multiplies.
http://crypto.stanford.edu/~dabo/abstracts/ssl-timing.html
I recommend changing the verify function to use a timing-independent
compare, such as the following. A similar change should be made to the
Java library.
###
correctMac = self.Sign(msg)
if len(correctMac) != len(sig_bytes):
return False
result = 0
for x, y in zip(correctMac, sig_bytes):
result |= ord(x) ^ ord(y)
return result == 0
###
This function is data-independent, except for revealing the total
length of the correctMac string. Since this is not considered
important to security, it is acceptable. Of course, this might not be
true for another use of this same code, so it cannot be blindly used
in other applications. Crypto flaws are subtle.
Please let me know if you have any questions. I hope this feedback can
help improve Keyczar.
Thanks,
Nate
--
Nate Lawson
Root Labs ::
www.rootlabs.com
Solving embedded security, kernel and crypto challenges