builtin/receive-pack: use constant-time comparison for HMAC value

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.

The technique we use here is also used in NaCl and the Go standard
library and relies on the fact that bitwise or and xor are constant time
on all known architectures.

We need not be concerned about exiting early if the actual and expected
lengths differ, since the standard cryptographic assumption is that
everyone, including an attacker, knows the format of and algorithm used
in our nonces (and in any event, they have the source code and can
determine it easily).  As a result, we assume everyone knows how long
our nonces should be.  This philosophy is also taken by the Go standard
library and other cryptographic libraries when performing constant time
comparisons on HMAC values.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 20 insertions, 1 deletions

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 411e0b4d99..45e2dd2a65 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -498,12 +498,25 @@ static char *find_header(const char *msg, size_t len, const char *key,
 	return NULL;
 }
 
+/*
+ * Return zero if a and b are equal up to n bytes and nonzero if they are not.
+ * This operation is guaranteed to run in constant time to avoid leaking data.
+ */
+static int constant_memequal(const char *a, const char *b, size_t n)
+{
+	int res = 0;
+	for (size_t i = 0; i < n; i++)
+		res |= a[i] ^ b[i];
+	return res;
+}
+
 static const char *check_nonce(const char *buf, size_t len)
 {
 	char *nonce = find_header(buf, len, "nonce", NULL);
 	timestamp_t stamp, ostamp;
 	char *bohmac, *expect = NULL;
 	const char *retval = NONCE_BAD;
+	size_t noncelen;
 
 	if (!nonce) {
 		retval = NONCE_MISSING;
@@ -545,8 +558,14 @@ static const char *check_nonce(const char *buf, size_t len)
 		goto leave;
 	}
 
+	noncelen = strlen(nonce);
 	expect = prepare_push_cert_nonce(service_dir, stamp);
-	if (strcmp(expect, nonce)) {
+	if (noncelen != strlen(expect)) {
+		/* This is not even the right size. */
+		retval = NONCE_BAD;
+		goto leave;
+	}
+	if (constant_memequal(expect, nonce, noncelen)) {
 		/* Not what we would have signed earlier */
 		retval = NONCE_BAD;
 		goto leave;