{"thread":{"id":"53204","subject":"[PATCH] builtin/receive-pack: use constant-time comparison for HMAC value","startedAt":"2020-04-09T23:37:43Z","lastAt":"2020-04-22T15:57:21Z","messageCount":6,"participants":["brian m. carlson","Junio C Hamano","SZEDER Gábor"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"395155","messageId":"20200409233730.680612-1-sandals@crustytoothpaste.net","threadId":"53204","inReplyTo":null,"subject":"[PATCH] builtin/receive-pack: use constant-time comparison for HMAC value","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2020-04-09T23:37:30Z","receivedAt":"2020-04-09T23:37:43Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"When we're comparing a push cert nonce, we currently do so using strcmp.\nMost implementations of strcmp short-circuit and exit as soon as they\nknow whether two values are equal.  This, however, is a problem when\nwe're comparing the output of HMAC, as it leaks information in the time\ntaken about how much of the two values match if they do indeed differ.\n\nIn our case, the nonce is used to prevent replay attacks against our\nserver via the embedded timestamp and replay attacks using requests from\na different server via the HMAC.  Push certs, which contain the nonces,\nare signed, so an attacker cannot tamper with the nonces without\nbreaking validation of the signature.  They can, of course, create their\nown signatures with invalid nonces, but they can also create their own\nsignatures with valid nonces, so there's nothing to be gained.  Thus,\nthere is no security problem.\n\nEven though it doesn't appear that there are any negative consequences\nfrom the current technique, for safety and to encourage good practices,\nlet's use a constant time comparison function for nonce verification.\nPOSIX does not provide one, but they are easy to write.\n\nThe technique we use here is also used in NaCl and the Go standard\nlibrary and relies on the fact that bitwise or and xor are constant time\non all known architectures.\n\nWe need not be concerned about exiting early if the actual and expected\nlengths differ, since the standard cryptographic assumption is that\neveryone, including an attacker, knows the format of and algorithm used\nin our nonces (and in any event, they have the source code and can\ndetermine it easily).  As a result, we assume everyone knows how long\nour nonces should be.  This philosophy is also taken by the Go standard\nlibrary and other cryptographic libraries when performing constant time\ncomparisons on HMAC values.\n\nSigned-off-by: brian m. carlson <sandals@crustytoothpaste.net>\n---\nWhen I was writing this, I determined that this doesn't have any\nsecurity impact, but Dscho suggested I send it to the security list\nanyway to be sure.  That was a good idea, so I did it, and folks there\nagreed that there's no viable attack we can think of.  Therefore, this\npatch is purely precautionary.\n\nThis came to my attention as I was looking into similar problems in\nother software and thought about what we do in Git as well.\n\n builtin/receive-pack.c | 21 ++++++++++++++++++++-\n 1 file changed, 20 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex 2cc18bbffd..2c26ef9132 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -499,12 +499,25 @@ static char *find_header(const char *msg, size_t len, const char *key,\n \treturn NULL;\n }\n \n+/*\n+ * Return zero if a and b are equal up to n bytes and nonzero if they are not.\n+ * This operation is guaranteed to run in constant time to avoid leaking data.\n+ */\n+static int constant_memequal(const char *a, const char *b, size_t n)\n+{\n+\tint res = 0;\n+\tfor (size_t i = 0; i < n; i++)\n+\t\tres |= a[i] ^ b[i];\n+\treturn res;\n+}\n+\n static const char *check_nonce(const char *buf, size_t len)\n {\n \tchar *nonce = find_header(buf, len, \"nonce\", NULL);\n \ttimestamp_t stamp, ostamp;\n \tchar *bohmac, *expect = NULL;\n \tconst char *retval = NONCE_BAD;\n+\tsize_t noncelen;\n \n \tif (!nonce) {\n \t\tretval = NONCE_MISSING;\n@@ -546,8 +559,14 @@ static const char *check_nonce(const char *buf, size_t len)\n \t\tgoto leave;\n \t}\n \n+\tnoncelen = strlen(nonce);\n \texpect = prepare_push_cert_nonce(service_dir, stamp);\n-\tif (strcmp(expect, nonce)) {\n+\tif (noncelen != strlen(expect)) {\n+\t\t/* This is not even the right size. */\n+\t\tretval = NONCE_BAD;\n+\t\tgoto leave;\n+\t}\n+\tif (constant_memequal(expect, nonce, noncelen)) {\n \t\t/* Not what we would have signed earlier */\n \t\tretval = NONCE_BAD;\n \t\tgoto leave;\n"},{"id":"395159","messageId":"xmqqr1wwkxqe.fsf@gitster.c.googlers.com","threadId":"53204","inReplyTo":"20200409233730.680612-1-sandals@crustytoothpaste.net","subject":"Re: [PATCH] builtin/receive-pack: use constant-time comparison for HMAC value","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-10T00:09:29Z","receivedAt":"2020-04-10T00:09:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n\n> When we're comparing a push cert nonce, we currently do so using strcmp.\n> Most implementations of strcmp short-circuit and exit as soon as they\n> know whether two values are equal.  This, however, is a problem when\n> we're comparing the output of HMAC, as it leaks information in the time\n> taken about how much of the two values match if they do indeed differ.\n>\n> In our case, the nonce is used to prevent replay attacks against our\n> server via the embedded timestamp and replay attacks using requests from\n> a different server via the HMAC.  Push certs, which contain the nonces,\n> are signed, so an attacker cannot tamper with the nonces without\n> breaking validation of the signature.  They can, of course, create their\n> own signatures with invalid nonces, but they can also create their own\n> signatures with valid nonces, so there's nothing to be gained.  Thus,\n> there is no security problem.\n>\n> Even though it doesn't appear that there are any negative consequences\n> from the current technique, for safety and to encourage good practices,\n> let's use a constant time comparison function for nonce verification.\n> POSIX does not provide one, but they are easy to write.\n\nDevil's advocate mode on.\n\nIf the HMAC plus digital signature are the real security, even\nthough writing this patch may be a nice mental exercise, is there a\nmerit in deliberately adding more code and making the code\nimmesurably slower by applying it? \n\nYou just established in the previous paragraph that \"for safety\" is\na red herring.\n"},{"id":"395160","messageId":"xmqqmu7kkx70.fsf@gitster.c.googlers.com","threadId":"53204","inReplyTo":"xmqqr1wwkxqe.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] builtin/receive-pack: use constant-time comparison for HMAC value","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-10T00:21:07Z","receivedAt":"2020-04-10T00:21:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> \"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n>\n>> When we're comparing a push cert nonce, we currently do so using strcmp.\n>> Most implementations of strcmp short-circuit and exit as soon as they\n>> know whether two values are equal.  This, however, is a problem when\n>> we're comparing the output of HMAC, as it leaks information in the time\n>> taken about how much of the two values match if they do indeed differ.\n>>\n>> In our case, the nonce is used to prevent replay attacks against our\n>> server via the embedded timestamp and replay attacks using requests from\n>> a different server via the HMAC.  Push certs, which contain the nonces,\n>> are signed, so an attacker cannot tamper with the nonces without\n>> breaking validation of the signature.  They can, of course, create their\n>> own signatures with invalid nonces, but they can also create their own\n>> signatures with valid nonces, so there's nothing to be gained.  Thus,\n>> there is no security problem.\n>>\n>> Even though it doesn't appear that there are any negative consequences\n>> from the current technique, for safety and to encourage good practices,\n>> let's use a constant time comparison function for nonce verification.\n>> POSIX does not provide one, but they are easy to write.\n>\n> Devil's advocate mode on.\n>\n> If the HMAC plus digital signature are the real security, even\n> though writing this patch may be a nice mental exercise, is there a\n> merit in deliberately adding more code and making the code\n> immesurably slower by applying it? \n>\n> You just established in the previous paragraph that \"for safety\" is\n> a red herring.\n\nOoops, sorry, I sent it a bit too soon.\n\n\"They are easy to write\" is one thing, but there is cost for keeping\ntwo variants of memcmp() and forcing the users to choose which one\nto call.  If we were to encourage good practices, what we would\nencourage would not be \"when in doubt, always use this pessimized\nversion.\", but \"analyse the risk, and when there can be a valid\ntiming analysis threat, use this one.\"  And to lead by example, we\nwould *not* be calling it in this codepath.\n\nA patch that adds constant_memequal() *without* calling it from\ncheck_nonce(), because we realize that there is no legitimate threat\nthat deserves to be protected by a call to it in this codepath,\nwould be a very good thing to have, in other words, as that does\nencourage good practices.\n\nEnd of \"Devil's advocate mode\".\n\nIt's not like we have audited _other_ codepaths that may benefit by\nhaving this helper, so if we were to add constant_memequal(), let's\ndo so in a more library-ish place, in wrapper.c perhaps.\n\nThanks.\n\n"},{"id":"395162","messageId":"20200410005603.GC6639@camp.crustytoothpaste.net","threadId":"53204","inReplyTo":"xmqqr1wwkxqe.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] builtin/receive-pack: use constant-time comparison for HMAC value","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2020-04-10T00:56:03Z","receivedAt":"2020-04-10T00:56:11Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2020-04-10 at 00:09:29, Junio C Hamano wrote:\n> \"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n> \n> > When we're comparing a push cert nonce, we currently do so using strcmp.\n> > Most implementations of strcmp short-circuit and exit as soon as they\n> > know whether two values are equal.  This, however, is a problem when\n> > we're comparing the output of HMAC, as it leaks information in the time\n> > taken about how much of the two values match if they do indeed differ.\n> >\n> > In our case, the nonce is used to prevent replay attacks against our\n> > server via the embedded timestamp and replay attacks using requests from\n> > a different server via the HMAC.  Push certs, which contain the nonces,\n> > are signed, so an attacker cannot tamper with the nonces without\n> > breaking validation of the signature.  They can, of course, create their\n> > own signatures with invalid nonces, but they can also create their own\n> > signatures with valid nonces, so there's nothing to be gained.  Thus,\n> > there is no security problem.\n> >\n> > Even though it doesn't appear that there are any negative consequences\n> > from the current technique, for safety and to encourage good practices,\n> > let's use a constant time comparison function for nonce verification.\n> > POSIX does not provide one, but they are easy to write.\n> \n> Devil's advocate mode on.\n> \n> If the HMAC plus digital signature are the real security, even\n> though writing this patch may be a nice mental exercise, is there a\n> merit in deliberately adding more code and making the code\n> immesurably slower by applying it?\n> \n> You just established in the previous paragraph that \"for safety\" is\n> a red herring.\n\nHere's the thing: I'm pretty sure there's not a security issue, but I'm\nnot a cryptologist and can't speak for certain.  We didn't think TLS had\nall of the issues it did, until we determined that it did.  If someone\nwho is a cryptologist comes up with an attack scenario we hadn't\nconsidered, we're covered.\n\nAlso, if we ever use this HMAC implementation for something else in the\nfuture, that use might be vulnerable.  So it makes sense to always use a\nconstant time comparison for HMAC so it looks wrong not to.  I think\nit's a good idea to make people feel icky about doing things like\nnon-constant HMAC comparisons or using MD5 even in the rare case where\nit doesn't matter because almost all of the time, it does.\n\nIf we were using a language like C++ or Rust that returned a typed value\nfor our results, we'd get this behavior for free, and we wouldn't know\nor care about the extremely minor performance impact.  The cost of using\na constant time comparison instead of an optimized strcmp is going to be\na handful of cycles and be dwarfed by the fact that we're forking and\nexecing a process (and moreover, probably a shell) to verify the push\ncert.\n\nSo I think this is valuable, although I understand if you don't want to\ntake it.\n-- \nbrian m. carlson: Houston, Texas, US\nOpenPGP: https://keybase.io/bk2204\n"},{"id":"395892","messageId":"20200422102734.GA3063@szeder.dev","threadId":"53204","inReplyTo":"20200409233730.680612-1-sandals@crustytoothpaste.net","subject":"Re: [PATCH] builtin/receive-pack: use constant-time comparison for HMAC value","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-04-22T10:27:34Z","receivedAt":"2020-04-22T10:28:40Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Thu, Apr 09, 2020 at 11:37:30PM +0000, brian m. carlson wrote:\n> +/*\n> + * Return zero if a and b are equal up to n bytes and nonzero if they are not.\n> + * This operation is guaranteed to run in constant time to avoid leaking data.\n> + */\n> +static int constant_memequal(const char *a, const char *b, size_t n)\n> +{\n> +\tint res = 0;\n> +\tfor (size_t i = 0; i < n; i++)\n> +\t\tres |= a[i] ^ b[i];\n> +\treturn res;\n> +}\n\n    CC builtin/receive-pack.o\nbuiltin/receive-pack.c: In function ‘constant_memequal’:\nbuiltin/receive-pack.c:509:2: error: ‘for’ loop initial declarations are only allowed in C99 mode\n  for (size_t i = 0; i < n; i++)\n  ^\n"},{"id":"395909","messageId":"xmqqo8rjjyxy.fsf@gitster.c.googlers.com","threadId":"53204","inReplyTo":"20200422102734.GA3063@szeder.dev","subject":"Re: [PATCH] builtin/receive-pack: use constant-time comparison for HMAC value","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-22T15:57:13Z","receivedAt":"2020-04-22T15:57:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Subject: receive-pack: compilation fix\n\nWe do not use C99 \"for loop initial declaration\" in our codebase\n(yet), but one snuck in.\n\nReported-by: SZEDER Gábor <szeder.dev@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/receive-pack.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex 45e2dd2a65..66149777a0 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -505,7 +505,9 @@ static char *find_header(const char *msg, size_t len, const char *key,\n static int constant_memequal(const char *a, const char *b, size_t n)\n {\n \tint res = 0;\n-\tfor (size_t i = 0; i < n; i++)\n+\tsize_t i;\n+\n+\tfor (i = 0; i < n; i++)\n \t\tres |= a[i] ^ b[i];\n \treturn res;\n }\n-- \n2.26.2-108-g048abe1751\n\n"}]}