Subject: Re: [PATCH] builtin/receive-pack: use constant-time comparison for HMAC value

From: "brian m. carlson" <[email-masked]>
Date: Fri, 10 Apr 2020 00:56:03 +0000

On 2020-04-10 at 00:09:29, Junio C Hamano wrote:
> "brian m. carlson" <[email-masked]> writes:
> 
> > When we're comparing a push cert nonce, we currently do so using strcmp.
> > Most implementations of strcmp short-circuit and exit as soon as they
> > know whether two values are equal.  This, however, is a problem when
> > we're comparing the output of HMAC, as it leaks information in the time
> > taken about how much of the two values match if they do indeed differ.
> >
> > In our case, the nonce is used to prevent replay attacks against our
> > server via the embedded timestamp and replay attacks using requests from
> > a different server via the HMAC.  Push certs, which contain the nonces,
> > are signed, so an attacker cannot tamper with the nonces without
> > breaking validation of the signature.  They can, of course, create their
> > own signatures with invalid nonces, but they can also create their own
> > signatures with valid nonces, so there's nothing to be gained.  Thus,
> > there is no security problem.
> >
> > Even though it doesn't appear that there are any negative consequences
> > from the current technique, for safety and to encourage good practices,
> > let's use a constant time comparison function for nonce verification.
> > POSIX does not provide one, but they are easy to write.
> 
> Devil's advocate mode on.
> 
> If the HMAC plus digital signature are the real security, even
> though writing this patch may be a nice mental exercise, is there a
> merit in deliberately adding more code and making the code
> immesurably slower by applying it?
> 
> You just established in the previous paragraph that "for safety" is
> a red herring.

Here's the thing: I'm pretty sure there's not a security issue, but I'm
not a cryptologist and can't speak for certain.  We didn't think TLS had
all of the issues it did, until we determined that it did.  If someone
who is a cryptologist comes up with an attack scenario we hadn't
considered, we're covered.

Also, if we ever use this HMAC implementation for something else in the
future, that use might be vulnerable.  So it makes sense to always use a
constant time comparison for HMAC so it looks wrong not to.  I think
it's a good idea to make people feel icky about doing things like
non-constant HMAC comparisons or using MD5 even in the rare case where
it doesn't matter because almost all of the time, it does.

If we were using a language like C++ or Rust that returned a typed value
for our results, we'd get this behavior for free, and we wouldn't know
or care about the extremely minor performance impact.  The cost of using
a constant time comparison instead of an optimized strcmp is going to be
a handful of cycles and be dwarfed by the fact that we're forking and
execing a process (and moreover, probably a shell) to verify the push
cert.

So I think this is valuable, although I understand if you don't want to
take it.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204