classification
Title: multiprocessing module performs a time-dependent hmac comparison
Type: Stage: resolved
Components: Library (Lib) Versions:
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Jon.Oberheide, haypo, hynek, loewis, ncoghlan, neologix, pitrou, python-dev, r.david.murray, sbt
Priority: normal Keywords: patch

Created on 2012-04-08 20:27 by Jon.Oberheide, last changed 2012-06-14 11:48 by hynek. This issue is now closed.

Files
File name Uploaded Description Edit
hmac-time-independent-v1.patch Jon.Oberheide, 2012-04-12 04:44 review
hmac-time-independent-v2.patch Jon.Oberheide, 2012-04-12 21:23 review
hmac-time-independent-v3.patch Jon.Oberheide, 2012-04-18 20:22 review
hmac-time-independent-v4.patch Jon.Oberheide, 2012-04-30 06:06 review
Messages (34)
msg157809 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-08 20:27
The multiprocessing module performs a time-dependent comparison of the HMAC digest used for authentication:

def deliver_challenge(connection, authkey):
    import hmac
    assert isinstance(authkey, bytes)
    message = os.urandom(MESSAGE_LENGTH)
    connection.send_bytes(CHALLENGE + message)
    digest = hmac.new(authkey, message).digest()
    response = connection.recv_bytes(256)        # reject large message
    if response == digest:
        connection.send_bytes(WELCOME)
    else:
        connection.send_bytes(FAILURE)
        raise AuthenticationError('digest received was wrong')

This comparison should be made time-independent as to not leak information about the expected digest and allow an attacker to derive the full digest.

More info on such timing attacks:

http://rdist.root.org/2009/05/28/timing-attack-in-google-keyczar-library/
http://rdist.root.org/2010/07/19/exploiting-remote-timing-attacks/
msg157837 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2012-04-09 10:52
I only looked quickly at the web pages, so I may have misunderstood.

But it sounds like this applies when the attacker gets multiple chances to guess the digest for a *fixed* message (which was presumably chosen by the attacker).

That is not the case here because deliver_challenge() generates a new message each time.  Therefore the expected digest changes each time.
msg157981 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2012-04-10 20:41
> Therefore the expected digest changes each time.

Exactly.
Timing attacks (which aren't really new :-) depend on a constant digest to successively determine the characters composing the digest. Here, that won't work, because the digest changes every time.
msg158012 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2012-04-11 08:47
if response == digest:
can be replaced by:
    if sum(x^y for x, y in itertools.zip_longest(response, digest,
fillvalue=256)) == 0:

I hope that zip_longest() does not depend too much on response and digest.
msg158021 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2012-04-11 11:25
> if response == digest:
> can be replaced by:
>    if sum(x^y for x, y in itertools.zip_longest(response, digest,
> fillvalue=256)) == 0:

Yeah, sure, but is it useful at all?
The digest changes at every connection attempt, so this should not be
exploitable.
msg158032 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-11 13:51
Ah yeah, I suppose it's not be exploitable in this case due to the challenge nonce.

However, it might still be a good thing to fix for to set an example for other hmac module users (internal or external) that might not have the same situation.
msg158033 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-11 13:53
In fact, it'd probably be useful to have a time_independenct_comparison() helper function somewhere in general.
msg158034 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2012-04-11 14:18
I don't see the point of obfuscating the code to avoid a vulnerability
to which the code is not even vulnerable, just so that it can be used
as example...
There are *thousands* of ways to introduce security flaws, and the
Python code base if not a security handbook ;-)
msg158035 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-11 14:27
You call it obfuscating, I call it security correctness and developer education. Tomayto, tomahto. ;-)

Anywho, your call of course, feel free to close.
msg158038 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2012-04-11 14:41
> You call it obfuscating, I call it security correctness and developer education. Tomayto, tomahto. ;-)

Well, I'd be prompt to changing to a more robust digest check
algorithm if the current one had a flaw, but AFAICT, it's not the case
(but I'm no security expert).

> Anywho, your call of course, feel free to close.

Being a core Python developer doesn't mean I'm right ;-)

I just don't think that "set an example for other hmac module users"
is a good reason on its own to complicate the code, which is currently
readable and - AFICT - safe (complexity usually introduces bugs).
Furthermore, I somehow doubt that hmac users will go and have a look
at the multiprocessing connection challenge code when looking for an
example.

One thing that could definitely be interesting is to look through the
code base and example to see if a similar - but vulnerable - pattern
is used, and fix such occurrences.
msg158040 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2012-04-11 14:53
I think it would be reasonable to add a safe comparison function to hmac.
Its documentation could explain briefly when it would be preferable to "==".
msg158044 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2012-04-11 15:11
It would also be reasonable to add a comment to the code mentioning why this particular (security) comparison is *not* vulnerable to a timing attack, which would serve the education purpose if someone does look at the code.
msg158045 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-11 15:29
> One thing that could definitely be interesting is to look through the
> code base and example to see if a similar - but vulnerable - pattern
> is used, and fix such occurrences.

Based on some quick greps, I didn't see many internal users of hmac and the current users don't seem to use it in a scenario that would be at risk (eg. attacker supplied digest compared against an expected digest).

Given that this issue has affected a lot of security-sensitive third-party code (keyczar, openid providers, almost every python web service that implements "secure cookies" [1] or other HMAC-based REST API signatures), I do like the idea of adding a warning in the relevant documentation as sbt proposed.

The only reason I'd recommend _not_ putting a time_independent_comparison() function in the hmac module is that it's not really HMAC-specific. In practice, any fixed-length secrets should be compared in a time-independent manner. It just happens that HMAC verification is a pretty common case for this vulnerable construct. :-)

[1] https://github.com/facebook/tornado/blob/master/tornado/web.py#L1981
msg158075 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2012-04-11 21:18
> Given that this issue has affected a lot of security-sensitive third-party code (keyczar, openid providers, almost every python web service that implements "secure cookies" [1] or other HMAC-based REST API signatures), I do like the idea of adding a warning in the relevant documentation as sbt proposed.

This does sound reasonable, along with the addition of a comparison
function immune to timing attacks to the hmac module (as noted, it's
not specific to hmac, but it looks like a resonable place to add it).
Would you like to submit a patch (new comparison function with
documentation and test)?
msg158083 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-11 22:06
Will do!
msg158103 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-12 04:44
Here's a v1. Works with both str and bytes types for Python 3.x.

Not sure I'm completely happy with the docs, but I'd appreciate any feedback on them!
msg158105 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2012-04-12 06:41
+def time_independent_equals(a, b):
+    if len(a) != len(b):
+        return False

This is not time independent. Is it an issue?

+    if type(a[0]) is int:

It's better to write isinstance(a, bytes). You should raise a
TypeError if a is not a bytes or str.
msg158129 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-12 13:59
> This is not time independent. Is it an issue?

You're correct, the length check does leak the length of the expected digest as a performance enhancement (otherwise, your comparison runtime is bounded by the length of the attackers input).

Generally, exposing the length and thereby potentially the underlying cryptographic hash function (eg. 20 bytes -> hmac-sha1) is not considered a security risk for this type of scenario, whereas leaking key material certainly is. I considered including this nuance in the documentation and probably should.

> It's better to write isinstance(a, bytes). You should raise a
> TypeError if a is not a bytes or str.

Ack, thanks.
msg158131 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-04-12 14:08
You could rewrite:

    result |= x ^ y

as:

    result |= (x != y)

Of course, this assumes that the "!=" operator is constant-time for 1-element strings.
msg158133 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-12 14:18
> You could rewrite:
> 
>     result |= x ^ y
> 
> as:
> 
>     result |= (x != y)

You could, but it's best not to introduce any conditional branching based if at all possible. For reference, see:

http://rdist.root.org/2009/05/28/timing-attack-in-google-keyczar-library/#comment-5783
msg158134 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2012-04-12 14:20
Why not just

    def time_independent_equals(a, b):
        return len(a) == len(b) and sum(x != y for x, y in zip(a, b)) == 0
msg158170 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-12 21:23
Here's a v2 patch. Changes include checking the input types via isinstance, test cases to exercise the type checking, and a note documenting the leak of the input length.
msg158656 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-18 20:22
v3 patch, based on feedback from the review here: http://bugs.python.org/review/14532/show
msg158745 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2012-04-19 20:49
> v3 patch, based on feedback from the review here: http://bugs.python.org/review/14532/show

Looks good to me.
One last thing (sorry for not bringing this up earlier): I don't like
bikeshedding, but at least to me, `time_independent_equals` is a bit
too long to type, and sounds reductive (we don't want to specifically
avoid only timing attacks, but provide a way to compare digests
securely).
What do you (all) think of something shorter, like `secure_compare`,
`secure_equals`, or something along those lines?
Note that I'm not good at finding names, so if others are fine with
the current one, I won't object ;-)
msg158747 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-19 20:55
I have used the name "secure_compare" in the past for such a function. That said, I don't have strong feelings either way about the naming, so I'll yield to the others.
msg158963 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2012-04-22 14:02
> I have used the name "secure_compare" in the past for such a function. That
> said, I don't have strong feelings either way about the naming, so I'll
> yield to the others.

I prefer this name too.
Wait one day or two (to let others chime in if they want), and upload
a new patch with that change :-)
msg159668 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-04-30 06:06
Ok, patch v4 uploaded. Only change is the rename to "secure_compare".
msg159747 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2012-05-01 08:52
> However, this generally is not a security risk.

You should explain what you already said: it is not a risk because the
length of a HMAC is fixed.
msg159759 - (view) Author: Jon Oberheide (Jon.Oberheide) Date: 2012-05-01 15:40
> You should explain what you already said: it is not a risk because the
> length of a HMAC is fixed.

Well, that's not entirely accurate. Exposing the length of the HMAC can expose what underlying hash is being used (eg. HMAC-SHA1 has different length than HMAC-MD5). It's generally not considered a risk since exposing the algorithm being used shouldn't impact your security (unless you're doing it very wrong).
msg160537 - (view) Author: Roundup Robot (python-dev) Date: 2012-05-13 17:53
New changeset ddcc8ee680d7 by Charles-François Natali in branch 'default':
Issue #14532: Add a secure_compare() helper to the hmac module, to mitigate
http://hg.python.org/cpython/rev/ddcc8ee680d7
msg160598 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2012-05-14 07:50
Committed.
Jon, thanks for your patch and your patience!
msg162587 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-06-10 15:16
A comment above the length check referring back to this issue and the deliberate decision to allow a timing attack to determine the length of the expected digest would be handy.

I was just looking at hmac.secure_compare and my thought when reading the source and the docstring was "No, it's not time-independent, you can still use a timing attack to figure out the expected digest length".
msg162772 - (view) Author: Martin v. Löwis (loewis) * (Python committer) Date: 2012-06-14 11:16
I recommend to revert the addition of this function. It's not possible to implement a time-independent comparison function, as demonstrated in issues 14955 and 15061
msg162774 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-06-14 11:20
How is it "not possible"? The implementation may be buggy, but it's possible to write a C version that does the right thing.
History
Date User Action Args
2012-06-14 11:48:10hyneksetnosy: + hynek
2012-06-14 11:20:40pitrousetmessages: + msg162774
2012-06-14 11:16:10loewissetnosy: + loewis
messages: + msg162772
2012-06-10 15:16:25ncoghlansetnosy: + ncoghlan
messages: + msg162587
2012-05-14 07:50:22neologixsetstatus: open -> closed
resolution: fixed
messages: + msg160598

stage: commit review -> resolved
2012-05-13 17:53:27python-devsetnosy: + python-dev
messages: + msg160537
2012-05-01 15:40:55Jon.Oberheidesetmessages: + msg159759
2012-05-01 08:52:03hayposetmessages: + msg159747
2012-04-30 17:02:06neologixsetstage: commit review
2012-04-30 06:06:49Jon.Oberheidesetfiles: + hmac-time-independent-v4.patch

messages: + msg159668
2012-04-22 14:02:46neologixsetmessages: + msg158963
2012-04-19 20:55:03Jon.Oberheidesetmessages: + msg158747
2012-04-19 20:49:15neologixsetmessages: + msg158745
2012-04-18 20:22:17Jon.Oberheidesetfiles: + hmac-time-independent-v3.patch

messages: + msg158656
2012-04-12 21:23:41Jon.Oberheidesetfiles: + hmac-time-independent-v2.patch

messages: + msg158170
2012-04-12 14:20:05sbtsetmessages: + msg158134
2012-04-12 14:18:09Jon.Oberheidesetmessages: + msg158133
2012-04-12 14:08:35pitrousetnosy: + pitrou
messages: + msg158131
2012-04-12 13:59:58Jon.Oberheidesetmessages: + msg158129
2012-04-12 06:41:11hayposetmessages: + msg158105
2012-04-12 04:44:03Jon.Oberheidesetfiles: + hmac-time-independent-v1.patch
keywords: + patch
messages: + msg158103
2012-04-11 22:06:54Jon.Oberheidesetmessages: + msg158083
2012-04-11 21:18:57neologixsetmessages: + msg158075
2012-04-11 15:29:26Jon.Oberheidesetmessages: + msg158045
2012-04-11 15:11:07r.david.murraysetnosy: + r.david.murray
messages: + msg158044
2012-04-11 14:53:01sbtsetmessages: + msg158040
2012-04-11 14:41:04neologixsetmessages: + msg158038
2012-04-11 14:27:48Jon.Oberheidesetmessages: + msg158035
2012-04-11 14:18:22neologixsetmessages: + msg158034
2012-04-11 13:53:31Jon.Oberheidesetmessages: + msg158033
2012-04-11 13:51:58Jon.Oberheidesetmessages: + msg158032
2012-04-11 11:25:59neologixsetmessages: + msg158021
2012-04-11 08:47:27hayposetmessages: + msg158012
2012-04-11 07:22:31neologixsetstatus: open
2012-04-11 07:22:18neologixsetstatus: open -> (no value)
nosy: + haypo
2012-04-10 20:41:02neologixsetnosy: + neologix
messages: + msg157981
2012-04-09 10:52:42sbtsetmessages: + msg157837
2012-04-08 21:45:50pitrousetnosy: + sbt
2012-04-08 20:27:42Jon.Oberheidecreate