Semi-closing a hole

Posted Apr 11, 2012 23:57 UTC (Wed) by man_ls (guest, #15091)
Parent article: Python 2.6.8, 2.7.3, 3.1.5, and 3.2.3 security release

I know that changing the default hashing algorithm would break some of my code, particularly my unit tests which compare the output of my program with correct test files. No problem, just regenerate the test files and rerun them; a bit obnoxious but easy. However, making the hashing order random would make it nearly impossible to keep static test files and my whole scheme would not so much fly but plummet.

Closing a security hole and making the fix optional (and not enabled by default) seems like a weird decision. It gets us the worst of both worlds: code cannot rely on hashing order since anyone can turn randomization on with a command line parameter. Meanwhile, insecure code can be run insecurely by a careless administrator, a recipe for disasters. That is why non-default behaviors are usually avoided for security fixes: to alleviate the burden on overloaded admins.

I would have very much preferred a default solution that didn't break things, such as limit the number of collisions in a hashing algorithm (to a crazy high number such as 100): after 100 collisions stop accepting elements. All code would be protected by default. I don't see what kind of code might break with this change other than crazy tests for the hashing algorithm itself, and anyway this collision check might be disabled using the means provided here.

It seems that the Python community often picks engineering choices which seem wrong from my point of view; and it is a pity because I really like the language.

to post comments

Semi-closing a hole

Posted Apr 12, 2012 0:13 UTC (Thu) by wahern (subscriber, #37304) [Link] (10 responses)

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.

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.

Semi-closing a hole

Posted Apr 12, 2012 0:13 UTC (Thu) by corbet (editor, #1) [Link] (2 responses)

I'm not yet sure I agree with the Python developers' decision. That said:

Yes, anybody can run with -R, in which case they only have themselves to blame for anything they break. Doesn't seem like a problem.
If you "stop accepting elements" into a dict, you're going to expose applications to a new exception that they weren't expecting before. That, too, could lead to all kinds of unpleasant behavior. To me, that seems like a more disruptive behavior change than randomizing the hash function.

Semi-closing a hole

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

I would assume that Python web servers are already prepared to deal with unexpected exceptions anywhere in the process: a simple try...except at the bottom of the request processing chain would be enough.

Perhaps my solution was too naïve, and a cleverer algorithm is required. The original LWN article back from January provided some interesting comments, besides a quickly escalating flame war about sorting algorithms. One of them was "change the hash function at run time if any of the hash chains exceeds a specified length". Or "switch to a balanced binary tree".

The downside would be that DoS prevention would be delegated to code which is seldom used, and which is therefore prone to breaking. But in these days of automated testing this problem could be easily managed by CPython devs. IMHO anything would be better than deferring the decision to the person running the code!

Semi-closing a hole

Posted Apr 12, 2012 14:56 UTC (Thu) by JanC_ (guest, #34940) [Link]

This does not only affect web servers, but any programs that get "untrusted input" in one way or another (which is the majority of all software out there).

Semi-closing a hole

Posted Apr 12, 2012 3:42 UTC (Thu) by willmo (subscriber, #82093) [Link] (6 responses)

Your tests are broken. Just sort the dict keys before comparing.

Semi-closing a hole

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

My tests are working fine, thanks for your concern. They will even continue working after this update, as the Python devs have acknowledged the use case (while deprecating it but still).

Let me give some details about my approach. My test suite is dead simple: simply a bash script that runs the Python program against a predefined collection of test documents. For each one it generates the result file and compares (using plain old diff) this result with a pre-generated correct file. No output means that the result is correct. If there is any justified change in the code, I just mv the test file to the correct file. It is fast and works great, but it does not allow for runtime munging of dict keys.

In my program sometimes (not often) elements are output in hash order. If runtime hash generation was random I would have to output elements always sorted, which would penalize performance without any user-visible gains. But I would prefer having to sort everything than changing my test suite. And I would prefer not to change element output order unless it was strictly necessary.

I am not complaining about the change in the Python runtime because it invalidates my testing techniques, but I worry about possible side-effects: someone running the test suite on their machines with PYTHONHASHSEED=random and seeing failures would have a hard time diagnosing these failures. Just one more pain point for Python development.

One of the principles of Test-Driven Development is "do the minimal thing that passes the tests". I do not fully agree with it, but it can be useful sometimes. And especially when writing tests!

Handling variability in test outputs

Posted Apr 12, 2012 9:57 UTC (Thu) by copsewood (subscriber, #199) [Link]

The testsuite I develop as part of PyLETS also has various hacks to cope with test results generating different files or strings than expected and still being valid results. E.G. auto-generated passwords, session cookies, date/time strings and related numeric values, URLs based on where the program is installed, and a growing list of other things. The approach my suite adopts is to normalise all of these values by using regexes and symbolic substitutions in both the expected stored values and actual values to replace variable expected values with symbolic constants prior to diff comparing actual against expected strings and files.

So I would also tend to regard this kind of breakage caused by an upstream dependancy as being the kind of thing I would expect to have to fix myself anyway in the course of upgrading the testsuite between major Python versions. Certainly wouldn't want the security of my application to depend upon whether I'd read and understood all the release notes of thousands of packages which run on my server.

Semi-closing a hole

Posted Apr 12, 2012 23:29 UTC (Thu) by joey (guest, #328) [Link] (1 responses)

Your tests are .. well, let's not say broken, let's say "fragile". Fragile tests are bad because they make it harder to make valid changes to the code of a program.

Semi-closing a hole

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

You are probably right, but still I don't see an easier way to test what I want to test. Just an excuse for my own lack of imagination, I know. Oh well.

Semi-closing a hole

Posted Apr 13, 2012 0:50 UTC (Fri) by mgedmin (guest, #34497) [Link] (1 responses)

Are you aware that string hashes differ on 32-bit and 64-bit machines? A test suite that only passes on one particular CPU architecture is a broken test suite, in my book.

Semi-closing a hole

Posted Apr 13, 2012 20:03 UTC (Fri) by man_ls (guest, #15091) [Link]

You are probably right. In that case I don't see how the Python tests referenced above can work on 32-bit and 64-bit machines.

Semi-closing a hole

Posted Apr 12, 2012 9:11 UTC (Thu) by intgr (subscriber, #39733) [Link] (3 responses)

> Closing a security hole and making the fix optional (and not enabled by default) seems like a weird decision

It *WILL* be the default in newer Python versions. Their decision makes very much sense: breaking existing applications in a security release is a no-no, since security updates in general need to be applied quickly -- without requiring all downstreams do a full new QA cycle.

If you start releasing security fixes that break applications by default, then distros will refuse to ship your security fixes and administrators will refuse to apply security fixes to their machines -- leading to worse security for everyone.

And let's admit it -- this denial-of-service problem has existed and has been known about for ages in most languages, it hasn't really been a problem in practice. It would be silly to rush it.

Semi-closing a hole

Posted Apr 12, 2012 11:56 UTC (Thu) by intgr (subscriber, #39733) [Link] (2 responses)

> It *WILL* be the default in newer Python versions

To be more specific, it will be the default in Python 3.3 and newer -- since it's a feature release, breaking compatibility is allowed.

Semi-closing a hole

Posted Apr 12, 2012 14:20 UTC (Thu) by cortana (subscriber, #24596) [Link] (1 responses)

So, we'll only need to wait 5-10 more years before it trickles down to end-users!

Semi-closing a hole

Posted Apr 12, 2012 14:35 UTC (Thu) by intgr (subscriber, #39733) [Link]

> So, we'll only need to wait 5-10 more years

No problem, we've waited ~20 years for people to fix this bug (hash table collision DoS is a pretty old and well-known problem). We can wait 10 more for the fix to reach users. ;)

Fixing tests

Posted Apr 12, 2012 12:45 UTC (Thu) by dskoll (subscriber, #1630) [Link] (11 responses)

However, making the hashing order random would make it nearly impossible to keep static test files and my whole scheme would not so much fly but plummet.

Surely your test code should not depend on the order of elements? The Perl module Test::Deep has routines for comparing hashes (equivalent of Python's dicts) that don't depend on the order of elements.

Fixing tests

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

I am not comparing dicts, but files. My package generates files so I compare those to canonical versions. You can check it out for yourself, it is called eLyXer. Perhaps it is not a canonical technique but it works well enough: less than a minute on a netbook for 48 rather sophisticated test files. Hash order has given me certain trouble in the past, but for a different task: parsing a config file and generating a Python preferences file. I am not even sure if my tests would run correctly or not, but I am not eager to try it.

And it seems that I am not alone: in the bug discussion people discuss about the change breaking a lot of the Python unit tests and their doctests. This kind of work is not hard to solve but a bit obnoxious; I would myself prefer to order all items instead of performing deep comparisons. With my testing technique of comparing result files I would have no choice anyway.

Fixing tests

Posted Apr 12, 2012 16:02 UTC (Thu) by dskoll (subscriber, #1630) [Link] (9 responses)

My package generates files so I compare those to canonical versions.

I see. Wouldn't it make sense, then, to modify the code that generates the files to sort the keys first so the generated files are always in a known order? This would cause some performance hit, I guess.

Fixing tests

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

Yes, that would be a good solution. The performance hit would be suffered by everyone but nice, ordered, predictable output is always a valuable thing, even when outputting a config file. Sigh. Better to bite the bullet and avoid random hash order whenever possible!

On this subject, I have been very surprised by javascript because it seems to output dict keys in alphabetical order. I don't know if it's only the Gecko and WebKit engines or it's a feature of the language though.

Fixing tests

Posted Apr 12, 2012 19:57 UTC (Thu) by dskoll (subscriber, #1630) [Link] (6 responses)

I believe it's an implementation artifact. I don't think JavaScript hashes guarantee any kind of order.

PHP (yuck) arrays do seem to guarantee an order. PHP is completely broken and confusingly combines hashes and arrays into the same data structure. Internally, it keeps extra pointers around so you can pull out elements in the same order you put them in. So a PHP hash bucket costs at least two pointers worth of space more than it should, not to mention the constant time overhead of maintaining the two extra pointers.

Fixing tests

Posted Apr 12, 2012 20:22 UTC (Thu) by man_ls (guest, #15091) [Link] (5 responses)

My mistake, Gecko and WebKit return keys in insertion order, not alphabetical. And it is not javascript arrays but objects; as you probably know, Javascript Does Not Support Associative Arrays

By the way, PHP also returns keys in insertion order, this time with real associative arrays. It is a nice feature IMHO; it may have some overhead but the results are much more intuitive than with Python's dicts. In a certain sense these other languages are hiding the details of the implementation, so that e.g. primitive testing schemes do not rely on the particular hashing function used.

Fixing tests

Posted Apr 12, 2012 20:41 UTC (Thu) by spaetz (guest, #32870) [Link] (2 responses)

Why dont you use OrderedDicts from python's collections module, if that is what you want?

Fixing tests

Posted Apr 12, 2012 20:50 UTC (Thu) by man_ls (guest, #15091) [Link] (1 responses)

Why, OrderedDicts didn't exist when I began coding eLyXer (and Python in general). Even if they had, they are new in Python 3.1 and I am still using Python 2. And I wanted to maintain compatibility back to Python 2.4 (Debian oldstable at the time), now back to Python 2.5.

Also, I did not know that I might eventually need insertion order at the time. I am guessing that also pure inertia might have played a role, although if OrderedDicts keep the same interface (and it appears that they do) that would make the switch quite painless. So I have at least three good reasons and two good excuses :)

Fixing tests

Posted Apr 13, 2012 6:54 UTC (Fri) by cathectic (guest, #40543) [Link]

There is a backport of it for older Python releases all the way back to 2.4:

http://pypi.python.org/pypi/ordereddict

Fixing tests

Posted Apr 13, 2012 13:10 UTC (Fri) by dskoll (subscriber, #1630) [Link] (1 responses)

By the way, PHP also returns keys in insertion order, this time with real associative arrays. It is a nice feature IMHO

I don't like the fact that PHP treats arrays and hashes as the same thing. I would prefer a different syntax for a numerically-indexed array than for an associative array. I would also rather that hashes don't return keys in insertion order by default. PHP should provide a separate data type similar to Python's OrderedDict for those times you want insertion order respected and are willing to pay the overhead.

Fixing tests

Posted Apr 13, 2012 14:17 UTC (Fri) by cortana (subscriber, #24596) [Link]

Let's not get ahead of ourselves. I'd much prefer that PHP provide basic things like a working < operator before moving on to such advanced features!

Fixing tests

Posted Apr 24, 2012 23:43 UTC (Tue) by steffen780 (guest, #68142) [Link]

The performance hit doesn't have to suffered by everyone. Either sort the hashes after the output is completed by using e.g. the sort utility, or add a test flag that then causes the hashes to be sorted before output. The latter will probably cause a little slow down due to the extra variable, parsing an extra CLI parameter and the necessary if - but the hit will be entirely negligible I should think.

Semi-closing a hole

Posted Apr 12, 2012 16:09 UTC (Thu) by iabervon (subscriber, #722) [Link] (1 responses)

I think the test repeatability issue would be best solved by having the test framework able to select the random hash. One of the biggest things that's made my test code easier to write is having the framework cause the function that returns the current time return a constant instead of the actual time. Then there's something to have the random password salt be a particular value. Along with those, it's quite reasonable to have the hash order be fixed. (For that matter, it would even be nice to tie all these together, so that your application generates obviously-wrong times if your hash isn't random, so you'll notice.)

Semi-closing a hole

Posted Apr 12, 2012 16:58 UTC (Thu) by dskoll (subscriber, #1630) [Link]

Even that might fail if newer versions of Python change the hash function. I think the only sane approach is for the test framework to sort the hash keys into a canonical order for comparison.