classification
Title: hmac.compare_digest could try harder to be constant-time.
Type: security Stage: patch review
Components: Library (Lib) Versions: Python 3.10, Python 3.9, Python 3.8, Python 3.7
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: christian.heimes Nosy List: Devin Jeanpierre, christian.heimes, gregory.p.smith, miss-islington, rhettinger
Priority: normal Keywords: patch

Created on 2020-05-27 07:41 by Devin Jeanpierre, last changed 2020-05-28 12:10 by miss-islington.

Pull Requests
URL Status Linked Edit
PR 20444 open Devin Jeanpierre, 2020-05-27 09:00
PR 20456 merged christian.heimes, 2020-05-27 16:12
PR 20461 merged christian.heimes, 2020-05-27 19:51
Messages (8)
msg370053 - (view) Author: Devin Jeanpierre (Devin Jeanpierre) * Date: 2020-05-27 07:41
`hmac.compare_digest` (via `_tscmp`) does not mark the accumulator variable `result` as volatile, which means that the compiler is allowed to short-circuit the comparison loop as long as it still reads from both strings.

In particular, when `result` is non-volatile, the compiler is allowed to change the loop from this:


```c
for (i=0; i < length; i++) {
    result |= *left++ ^ *right++;
}
return (result == 0);
```

into (the moral equivalent of) this:


```c
for (i=0; i < length; i++) {
    result |= *left++ ^ *right++;
    if (result) {
        for (; ++i < length;) {
            *left++; *right++;
        }
        return 1;
    }
}
return (result == 0);
```

(Code not tested.)

This might not seem like much, but it cuts out almost all of the data dependencies between `result`, `left`, and `right`, which in theory would free the CPU to race ahead using out of order execution -- it could execute code that depends on the result of `_tscmp`, even while `_tscmp` is still performing the volatile reads. (I have not actually benchmarked this. :)) In other words, this weird short circuiting could still actually improve performance. That, in turn, means that it would break constant-time guarantees.

(This is different from saying that it _would_ increase performance, but marking it volatile removes the worry.)

(Prior art/discussion: https://github.com/google/tink/commit/335291c42eecf29fca3d85fed6179d11287d253e )


I propose two changes, one trivial, and one that's more invasive:

1) Make `result` a `volatile unsigned char` instead of `unsigned char`. 

2) When SSL is available, instead use `CRYPTO_memcmp` from OpenSSL/BoringSSL. We are, in effect, "rolling our own crypto". The SSL libraries are more strictly audited for timing issues, down to actually checking the generated machine code. As tools improve, those libraries will grow to use those tools. If we use their functions, we get the benefit of those audits and improvements.
msg370094 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2020-05-27 15:26
+1 for both of these suggestions
msg370108 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2020-05-27 16:05
Christian - Devin could likely use some help with the build/ifdef plumbing required for (2) to use CRYPTO_memcmp from Modules/_operator.c when OpenSSL is available.
msg370109 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2020-05-27 16:14
GPS, I got you covered :)

CRYPTO_memcmp() was on my TODO list for a while. Thanks for nagging me.

_operator is a built-in module. I don't want to add libcrypto dependency to libpython. I copied the code, made some adjustments and added it to _hashopenssl.c.
msg370121 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2020-05-27 19:18
Greg, is GH-20456 a bug fix / security enhancement or a new feature? I'm hesitant to backport it to 3.7 and 3.8. 3.9 might be ok.
msg370122 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2020-05-27 19:46
I'd feel fine doing that for 3.9 given 3.9.0 is only in beta and this changes no public APIs.  For 3.8 and 3.7 i wouldn't.

Be sure to update the versionchanged in the docs if you choose to do it for 3.9.
msg370124 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2020-05-27 19:50
New changeset db5aed931f8a617f7b63e773f62db468fe9c5ca1 by Christian Heimes in branch 'master':
bpo-40791: Use CRYPTO_memcmp() for compare_digest (#20456)
https://github.com/python/cpython/commit/db5aed931f8a617f7b63e773f62db468fe9c5ca1
msg370195 - (view) Author: miss-islington (miss-islington) Date: 2020-05-28 12:10
New changeset 8183e11d87388e4e44e3242c42085b87a878f781 by Christian Heimes in branch '3.9':
[3.9] bpo-40791: Use CRYPTO_memcmp() for compare_digest (GH-20456) (GH-20461)
https://github.com/python/cpython/commit/8183e11d87388e4e44e3242c42085b87a878f781
History
Date User Action Args
2020-05-28 12:10:04miss-islingtonsetnosy: + miss-islington
messages: + msg370195
2020-05-27 19:51:51christian.heimessetpull_requests: + pull_request19714
2020-05-27 19:50:11christian.heimessetmessages: + msg370124
2020-05-27 19:46:01gregory.p.smithsetmessages: + msg370122
2020-05-27 19:18:24christian.heimessetmessages: + msg370121
2020-05-27 16:14:21christian.heimessetmessages: + msg370109
2020-05-27 16:12:11christian.heimessetpull_requests: + pull_request19711
2020-05-27 16:05:20gregory.p.smithsetassignee: christian.heimes
messages: + msg370108
2020-05-27 15:26:51rhettingersetversions: - Python 3.5, Python 3.6
nosy: + rhettinger

messages: + msg370094

type: security
2020-05-27 15:25:47zach.waresetnosy: + gregory.p.smith, christian.heimes
2020-05-27 09:00:48Devin Jeanpierresetkeywords: + patch
stage: patch review
pull_requests: + pull_request19700
2020-05-27 07:41:07Devin Jeanpierrecreate