| Message ID | 20200409233730.680612-1-sandals@crustytoothpaste.net (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | builtin/receive-pack: use constant-time comparison for HMAC value | expand |
"brian m. carlson" <sandals@crustytoothpaste.net> 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.
Junio C Hamano <gitster@pobox.com> writes: > "brian m. carlson" <sandals@crustytoothpaste.net> 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. Ooops, sorry, I sent it a bit too soon. "They are easy to write" is one thing, but there is cost for keeping two variants of memcmp() and forcing the users to choose which one to call. If we were to encourage good practices, what we would encourage would not be "when in doubt, always use this pessimized version.", but "analyse the risk, and when there can be a valid timing analysis threat, use this one." And to lead by example, we would *not* be calling it in this codepath. A patch that adds constant_memequal() *without* calling it from check_nonce(), because we realize that there is no legitimate threat that deserves to be protected by a call to it in this codepath, would be a very good thing to have, in other words, as that does encourage good practices. End of "Devil's advocate mode". It's not like we have audited _other_ codepaths that may benefit by having this helper, so if we were to add constant_memequal(), let's do so in a more library-ish place, in wrapper.c perhaps. Thanks.
On 2020-04-10 at 00:09:29, Junio C Hamano wrote: > "brian m. carlson" <sandals@crustytoothpaste.net> 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.
On Thu, Apr 09, 2020 at 11:37:30PM +0000, brian m. carlson wrote: > +/* > + * 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; > +} CC builtin/receive-pack.o builtin/receive-pack.c: In function ‘constant_memequal’: builtin/receive-pack.c:509:2: error: ‘for’ loop initial declarations are only allowed in C99 mode for (size_t i = 0; i < n; i++) ^
Subject: receive-pack: compilation fix
We do not use C99 "for loop initial declaration" in our codebase
(yet), but one snuck in.
Reported-by: SZEDER Gábor <szeder.dev@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
builtin/receive-pack.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 45e2dd2a65..66149777a0 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -505,7 +505,9 @@ static char *find_header(const char *msg, size_t len, const char *key,
static int constant_memequal(const char *a, const char *b, size_t n)
{
int res = 0;
- for (size_t i = 0; i < n; i++)
+ size_t i;
+
+ for (i = 0; i < n; i++)
res |= a[i] ^ b[i];
return res;
}
diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c index 2cc18bbffd..2c26ef9132 100644 --- a/builtin/receive-pack.c +++ b/builtin/receive-pack.c @@ -499,12 +499,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; @@ -546,8 +559,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;
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> --- When I was writing this, I determined that this doesn't have any security impact, but Dscho suggested I send it to the security list anyway to be sure. That was a good idea, so I did it, and folks there agreed that there's no viable attack we can think of. Therefore, this patch is purely precautionary. This came to my attention as I was looking into similar problems in other software and thought about what we do in Git as well. builtin/receive-pack.c | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-)