Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Python: Bugs

[issue14532] multiprocessing module performs a time-dependent hmac comparison

 

 

First page Previous page 1 2 Next page Last page  View All Python bugs RSS feed   Index | Next | Previous | View Threaded


report at bugs

Apr 8, 2012, 1:27 PM

Post #1 of 35 (273 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison

New submission from Jon Oberheide <jon [at] oberheide>:

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/

----------
components: Library (Lib)
messages: 157809
nosy: Jon.Oberheide
priority: normal
severity: normal
status: open
title: multiprocessing module performs a time-dependent hmac comparison

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 8, 2012, 2:45 PM

Post #2 of 35 (260 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Changes by Antoine Pitrou <pitrou [at] free>:


----------
nosy: +sbt

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 9, 2012, 3:52 AM

Post #3 of 35 (256 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

sbt <shibturn [at] gmail> added the comment:

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.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 10, 2012, 1:41 PM

Post #4 of 35 (257 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Charles-François Natali <neologix [at] free> added the comment:

> 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.

----------
nosy: +neologix

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 12:22 AM

Post #5 of 35 (256 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Changes by Charles-François Natali <neologix [at] free>:


----------
nosy: +haypo
status: open ->

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 12:22 AM

Post #6 of 35 (259 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Changes by Charles-François Natali <neologix [at] free>:


----------
status: -> open

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 1:47 AM

Post #7 of 35 (256 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

STINNER Victor <victor.stinner [at] gmail> added the comment:

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.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 4:25 AM

Post #8 of 35 (256 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Charles-François Natali <neologix [at] free> added the comment:

> 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.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 6:51 AM

Post #9 of 35 (255 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

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.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 6:53 AM

Post #10 of 35 (256 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

In fact, it'd probably be useful to have a time_independenct_comparison() helper function somewhere in general.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 7:18 AM

Post #11 of 35 (257 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Charles-François Natali <neologix [at] free> added the comment:

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 ;-)

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 7:27 AM

Post #12 of 35 (259 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

You call it obfuscating, I call it security correctness and developer education. Tomayto, tomahto. ;-)

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

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 7:41 AM

Post #13 of 35 (257 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Charles-François Natali <neologix [at] free> added the comment:

> 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.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 7:53 AM

Post #14 of 35 (259 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

sbt <shibturn [at] gmail> added the comment:

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 "==".

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 8:11 AM

Post #15 of 35 (257 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

R. David Murray <rdmurray [at] bitdance> added the comment:

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.

----------
nosy: +r.david.murray

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 8:29 AM

Post #16 of 35 (258 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

> 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

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 2:18 PM

Post #17 of 35 (258 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Charles-François Natali <neologix [at] free> added the comment:

> 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)?

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 3:06 PM

Post #18 of 35 (257 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

Will do!

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 9:44 PM

Post #19 of 35 (255 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

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!

----------
keywords: +patch
Added file: http://bugs.python.org/file25186/hmac-time-independent-v1.patch

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 11, 2012, 11:41 PM

Post #20 of 35 (258 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

STINNER Victor <victor.stinner [at] gmail> added the comment:

+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.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 12, 2012, 6:59 AM

Post #21 of 35 (260 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

> 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.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 12, 2012, 7:08 AM

Post #22 of 35 (254 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Antoine Pitrou <pitrou [at] free> added the comment:

You could rewrite:

result |= x ^ y

as:

result |= (x != y)

Of course, this assumes that the "!=" operator is constant-time for 1-element strings.

----------
nosy: +pitrou

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 12, 2012, 7:18 AM

Post #23 of 35 (259 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

> 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

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 12, 2012, 7:20 AM

Post #24 of 35 (256 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

sbt <shibturn [at] gmail> added the comment:

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

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Apr 12, 2012, 2:23 PM

Post #25 of 35 (256 views)
Permalink
[issue14532] multiprocessing module performs a time-dependent hmac comparison [In reply to]

Jon Oberheide <jon [at] oberheide> added the comment:

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.

----------
Added file: http://bugs.python.org/file25197/hmac-time-independent-v2.patch

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14532>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

First page Previous page 1 2 Next page Last page  View All Python bugs RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.