hmac.compare_digest could try harder to be constant-time.

[ssbr]

BPO	40791
Nosy	@rhettinger, @gpshead, @tiran, @benjaminp, @ssbr, @ned-deily, @mgorny, @miss-islington
PRs	bpo-40791: Make compare_digest more constant-time. #20444 bpo-40791: Use CRYPTO_memcmp() for compare_digest #20456 [3.9] bpo-40791: Use CRYPTO_memcmp() for compare_digest (GH-20456) #20461 [3.9] bpo-40791: Make compare_digest more constant-time. (GH-20444) #23436 [3.8] bpo-40791: Make compare_digest more constant-time. (GH-20444) #23437 [3.7] bpo-40791: Make compare_digest more constant-time. (GH-20444) #23438 [3.6] bpo-40791: Make compare_digest more constant-time. (GH-23438) #23767

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/tiran'
closed_at = <Date 2020-11-22.17:34:28.761>
created_at = <Date 2020-05-27.07:41:07.020>
labels = ['type-security', '3.8', '3.9', '3.10', '3.7', 'library']
title = 'hmac.compare_digest could try harder to be constant-time.'
updated_at = <Date 2020-12-14.17:11:27.035>
user = 'https://github.com/ssbr'

bugs.python.org fields:

activity = <Date 2020-12-14.17:11:27.035>
actor = 'ned.deily'
assignee = 'christian.heimes'
closed = True
closed_date = <Date 2020-11-22.17:34:28.761>
closer = 'benjamin.peterson'
components = ['Library (Lib)']
creation = <Date 2020-05-27.07:41:07.020>
creator = 'Devin Jeanpierre'
dependencies = []
files = []
hgrepos = []
issue_num = 40791
keywords = ['patch']
message_count = 15.0
messages = ['370053', '370094', '370108', '370109', '370121', '370122', '370124', '370195', '381530', '381531', '381533', '381624', '382972', '382993', '382995']
nosy_count = 8.0
nosy_names = ['rhettinger', 'gregory.p.smith', 'christian.heimes', 'benjamin.peterson', 'Devin Jeanpierre', 'ned.deily', 'mgorny', 'miss-islington']
pr_nums = ['20444', '20456', '20461', '23436', '23437', '23438', '23767']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'security'
url = 'https://bugs.python.org/issue40791'
versions = ['Python 3.6', 'Python 3.7', 'Python 3.8', 'Python 3.9', 'Python 3.10']

[ssbr]

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:

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

into (the moral equivalent of) this:

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: tink-crypto/tink@335291c )

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.

[rhettinger]

+1 for both of these suggestions

[gpshead]

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.

[tiran]

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.

[tiran]

Greg, is #64655 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.

[gpshead]

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.

[tiran]

New changeset db5aed9 by Christian Heimes in branch 'master':
bpo-40791: Use CRYPTO_memcmp() for compare_digest (bpo-20456)
db5aed9

[miss-islington]

New changeset 8183e11 by Christian Heimes in branch '3.9':
[3.9] bpo-40791: Use CRYPTO_memcmp() for compare_digest (GH-20456) (GH-20461)
8183e11

[gpshead]

New changeset 3172936 by Devin Jeanpierre in branch 'master':
bpo-40791: Make compare_digest more constant-time. (GH-20444)
3172936

[miss-islington]

New changeset 97136d7 by Miss Islington (bot) in branch '3.8':
bpo-40791: Make compare_digest more constant-time. (GH-20444)
97136d7

[miss-islington]

New changeset c1bbca5 by Miss Islington (bot) in branch '3.9':
bpo-40791: Make compare_digest more constant-time. (GH-20444)
c1bbca5

[benjaminp]

New changeset db95802 by Miss Islington (bot) in branch '3.7':
bpo-40791: Make compare_digest more constant-time. (GH-23438)
db95802

[mgorny]

Any reason this wasn't backported to 3.6? FWICS it's supposed to be security supported still.

[ned-deily]

New changeset 8bef9eb by Miss Islington (bot) in branch '3.6':
bpo-40791: Make compare_digest more constant-time. (GH-23438) (GH-23767)
8bef9eb

[ned-deily]

Any reason this wasn't backported to 3.6?

Just an oversight. Thanks for pointing it out.

[samueloph]

CVE-2022-48566 was assigned to this.

I wasn't involved in the assignment, posting here for reference only.

[neilpvirtualitics]

Also seems to be this: GHSA-cgfh-jp5w-8cmx
Which really has no info.