4 ms·
Efficiently Generating Python Hash Collisions
- punnerud 7y agoHow is it fixed in Python 3.3+?
- brian_spiering 7y ago"hash randomization is enabled by default" https://docs.python.org/3/whatsnew/3.3.html https://docs.python.org/3/whatsnew/3.3.html
- mcintyre1994 7y agoI think it's this: > Note: By default, the __hash__() values of str, bytes and datetime objects are “salted” with an unpredictable random value. Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python. > This is intended to provide protection against a denial-of-service caused by carefully-chosen inputs that exploit the worst case performance of a dict insertion, O(n^2) complexity. See http://www.ocert.org/advisories/ocert-2011-003.html http://www.ocert.org/advisories/ocert-2011-003.html for details. > Changing hash values affects the iteration order of sets. Python has never made guarantees about this ordering (and it typically varies between 32-bit and 64-bit builds). > See also PYTHONHASHSEED. -- From https://docs.python.org/3/reference/datamodel.html#object.__hash__ https://docs.python.org/3/reference/datamodel.html#object.__... (linked from https://docs.python.org/3/whatsnew/3.3.html https://docs.python.org/3/whatsnew/3.3.html)
- H8crilA 7y agoYup, don't ever rely on any random hash function, even if widely used, to be repeatable between processes. I've seen a deployment of a small caching system that used the Python's built in hash function. The author of the code was wondering why does he get a ~zero hit rate (processes were short lived in that setup). Related: iterating over hash maps is a very common way to get nondeterministic output. I've removed a lot of inconsistency bugs by fixing the hash map iteration order. Usually by just using the sorted map, since the performance of a randomly chosen piece of code in a large system is almost irrelevant.
- osandov 7y agoIt was actually fixed in Python 3.4 with the switch to use SipHash, as the randomization introduced in Python 3.3 was still susceptible to some attacks. See https://www.python.org/dev/peps/pep-0456/ https://www.python.org/dev/peps/pep-0456/
- rurban 7y agoStill not secure if you can read out the seed. Brute forcing SipHash collisions with the known seed is also just a matter of seconds to minutes. http://perl11.org/blog/seed.html http://perl11.org/blog/seed.html A proper security fix can only be to fix the collision resolution, never using a slower hash function. It's also 10x faster then.
- tromp 7y agoFinding (cycles of) collisions in siphash is used as a memory-hard Proof-of-Work: https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo
- rurban 7y agoOnly for hash tables which use all bits. (e.g. prime sized). Almost nobody does. For normal power-of-2 hash tables finding collisions in the lowest bits leading to a successful amplification is trivial by brute-force. Since Siphash is so slow it can last up to 4 minutes, for smaller tables still < 5s.
- minitech 7y ago> Still not secure if you can read out the seed. Which you do as an attacker by… asking politely? Or is it easy to leak the seed by accident? In other news, there’s a relatively low-cost attack on AES when you know the key.
- rurban 7y agoWith dynamic languages like python it's trivial. Calculate the position and peek it. With static languages it's still easy when you got enough information: source code, timing info and ordering (e. g JSON). With a proper SAT solver doable. Leaking by accident is e.g even more trivial in perl, just set a magic ENV var. But peeking the fixed offset is easiest. It's all just security theatre. There's no real use-case for something so slow as Siphash.
- jshowa3 7y agoWow. This is an awesome article. Very well put together and explained step by step with pictures. Wish all articles were like this.
- ErikCorry 7y agoWhy is the running time of the attacked python process exponential? I would expect quadratic.
- petters 7y agoI think that the author is mistaken or careless when making that particular statement.
- 6gvONxR4sf7o 7y agoIt's probably using the colloquial version of the word (which I hate). "Exponentially" = "hugely, but I want to sound technical." Or the still frustrating but more acceptable "exponentially" = "by orders of magnitude."
- sansnomme 7y agoMaybe OP should use P and NP instead.
- mehrdadn 7y agoWas wondering the same thing. My guess is he just meant 1000 -> 100 -> 10 -> 1 -> exponential.
- rurban 7y agoIt's actually linear. It's searching a key in a linked list O(n), instead of constant access O(1). Still the amplification factor is big enough.
- svat 7y agoAlthough this article is about collisions in the hash function applied to strings, for numeric values Python uses a hash() function that is not only easy to generate collisions for but actually to invert (and find all inverses). I learned about this when writing this answer: • https://stackoverflow.com/questions/56227419/why-does-pythons-hash-of-infinity-have-the-digits-of-π/56227918#56227918 https://stackoverflow.com/questions/56227419/why-does-python... and details and code on how to invert are here: • https://stackoverflow.com/a/56248241/4958 https://stackoverflow.com/a/56248241/4958 (Needless to say, this is quite straightforward and trivial compared to collisions on strings; nevertheless it may be of some interest to someone.)