Semi-closing a hole

Posted Apr 12, 2012 0:13 UTC (Thu) by wahern (subscriber, #37304)
In reply to: Semi-closing a hole by man_ls
Parent article: Python 2.6.8, 2.7.3, 3.1.5, and 3.2.3 security release

Stop accepting elements? The hash collision attack is a denial of service attack. If a hash stopped accepting elements, presumably (hopefully) it would throw an error or abort the program. But that puts you back at square one: denial of service.

Python is the first language I've heard of where there was a guarantee about hashing order. Somehow other language communities get along just fine without this guarantee. People hem and haw, yet when circumstances come up which requires tweaking the hash, all of sudden people appreciate the discipline. Seems to me the problem here was that Python allowed people to depend on this behavior, and now they've pigeon-holed themselves.

to post comments

Python never guaranteed an order

Posted Apr 12, 2012 0:18 UTC (Thu) by david.a.wheeler (subscriber, #72896) [Link] (6 responses)

Python never guaranteed an order. The problem is that some programs may have presumed that it did anyway.

Python never guaranteed an order

Posted Apr 12, 2012 0:32 UTC (Thu) by dave_malcolm (subscriber, #15013) [Link]

Indeed, and although the ordering hasn't changed much over the years, typically it *has* been different between 32-bit and 64-bit CPU architectures.

Hence even without the randomization, Python code that erroneously has an implicit reliance on a dict ordering tends to break when run on a machine with a different word size to the one you wrote it on.

Python never guaranteed an order

Posted Apr 12, 2012 4:21 UTC (Thu) by theophrastus (guest, #80847) [Link] (4 responses)

I had no idea that there was any order there. So what order does it have? Just the same for each "for k in dict.keys():" or what? (i don't think it's alphabetical ...[checking]... nope)

Python never guaranteed an order

Posted Apr 12, 2012 8:41 UTC (Thu) by job (guest, #670) [Link] (3 responses)

It's just that the order is deterministic, it does not necessarily make any sense to a human observer. It all depends on how the internal hash function works.

Python never guaranteed an order

Posted Apr 12, 2012 17:11 UTC (Thu) by theophrastus (guest, #80847) [Link] (2 responses)

Oh... ok, thank you for that.

(must resist asking what isn't "deterministic" inside most computers if one has enough knowledge of their current state... must.... resist...)

Python never guaranteed an order

Posted Apr 12, 2012 19:13 UTC (Thu) by man_ls (guest, #15091) [Link]

I believe instead of "deterministic" you could use "consistent" or "always the same": the order doesn't change with time and is the same from one run to the next. Not everything inside a computer can be said to behave this way: for instance processes which change with absolute time, with durations or with user or device input. Or processes that have been made to depend on the above factors intentionally to avoid predictable behavior (as in the original security hole).

Python never guaranteed an order

Posted Apr 13, 2012 11:39 UTC (Fri) by dskoll (subscriber, #1630) [Link]

In theory, /dev/random is non-deterministic because it uses sources of entropy whose internal state is (for practical purposes) impossible to know well enough to make any predictions.

Semi-closing a hole

Posted Apr 12, 2012 8:00 UTC (Thu) by man_ls (guest, #15091) [Link] (2 responses)

The correct behavior would be to throw an exception, of course. Instead of collapsing the machine the program would just stop servicing that particular request which has the (n+1)th hash collision.

I don't know much about Python web servers, but I would presume that they are coded so that an exception in a request is caught somewhere and does not affect other requests. (Otherwise the server code is really, really broken: any silly coding mistake becomes a DoS.) If this is the case then you are not back at square one: instead of denying responses for all users you are denying service only to the malicious user, without affecting others. This technique might be called "denial of malicious service".

Semi-closing a hole

Posted Apr 12, 2012 9:58 UTC (Thu) by zuki (subscriber, #41808) [Link] (1 responses)

Actually, this idea was tried and rejected (see the discussion attached to the bug in the bug tracker).

The problem is that it is easy to prepare a scenario where the malicious request succeeds but subsequent benign requests fail. For example, the attacker adds 100 usernames which hash to the same value. This works fine because the whole list of usernames is not used during this operation. Then the administrator tries to generate a listing of all user names and hits the limit of 100 collisions and gets an exception in the display code which uses a dictionary to sort the usernames.

Starting to throw exceptions in basically unpredictable places would create a nightmare, where every operation involving a set or dict, which basically means every operation in Python, could potentially fail.

Semi-closing a hole

Posted Apr 12, 2012 12:10 UTC (Thu) by man_ls (guest, #15091) [Link]

Indeed, the bug discussion is very interesting: I just browsed it and people did debate many of the solutions proposed in the recent LWN article.

In the end the simplest solution won, which is not a bad thing in itself -- especially with a security fix, as others have remarked here.