
Efficiently Generating Python Hash Collisions - ssully
https://www.leeholmes.com/blog/2019/07/23/efficiently-generating-python-hash-collisions/
======
svat
Although 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-
python...](https://stackoverflow.com/questions/56227419/why-does-pythons-hash-
of-infinity-have-the-digits-of-π/56227918#56227918)

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

------
ErikCorry
Why is the running time of the attacked python process exponential? I would
expect quadratic.

~~~
6gvONxR4sf7o
It'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
Maybe OP should use P and NP instead.

------
jshowa3
Wow. This is an awesome article. Very well put together and explained step by
step with pictures.

Wish all articles were like this.

------
punnerud
How is it fixed in Python 3.3+?

~~~
mcintyre1994
I 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.__...](https://docs.python.org/3/reference/datamodel.html#object.__hash__)
(linked from
[https://docs.python.org/3/whatsnew/3.3.html](https://docs.python.org/3/whatsnew/3.3.html))

~~~
H8crilA
Yup, 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.

