New submission from Devin Jeanpierre <jeanpierr...@gmail.com>:
`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.
----------
components: Library (Lib)
messages: 370053
nosy: Devin Jeanpierre
priority: normal
severity: normal
status: open
title: hmac.compare_digest could try harder to be constant-time.
versions: Python 3.10, Python 3.5, Python 3.6, Python 3.7, Python 3.8, Python
3.9
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue40791>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
