TLDR. It's easy to generate collisions for phash and phash2 when hashing binaries. Erlang dict uses phash so if its possible to generate quadratic slow down by triggering collisions. ETS uses phash2 so its possible to generate quadratic slow down by triggering collisions in ETS. The good news is that even though erlang maps uses phash2 and its possible to generate collisions it does not seem easy to trigger a quadratic slow down because the hash array mapped trie implementation rehashes the input with a different prefix when it can't find a unique position in the trie and it looks like it is difficult to generate inputs that collide over multiple different prefixes.
This review is going to focus on taking the hash of binaries because this is the most likely user controllable input to the hash functions.
The erlang.phash/2 function calculates the hash of a binary by contructing a polynomial where the bytes are the coefficients of a polynomial P(X). This polynomial is evaluated at the prime X=268440163. The hash function then takes this result and multiplies it by the prime 268436141 and adds the length + 1. All of these operations are performed in Z/2^32Z (ie: 32 bit unsigned arithmetic).
Because the polymial is evaluated modulo a power of 2 it is easy to create two binaries that will hash to the same value. This is done by using the Thue-Morse sequence (https://en.wikipedia.org/wiki/Thue–Morse_sequence).
The Thue-Morse sequence is a binary sequence that starts with 0 and is extended by adding the compliment of the sequence so far.
Here are the sequences of length 1, 2, 4 and 8:
Length 1: 0
Length 2: 0|1
Length 4: 01|10
Length 8: 0110|1001
Wikipedia has a section called 'infinite product' that shows the polynomial:
(-1)^t_j . x^j
where t_j is thue-morse element can be factorized using the terms:
(1 - x^2^i)
where the number of terms in the product is k st. 2^k = length of the sequence
but (1 - x^2^i) can be factored again into two terms:
(1 - x^2^[i-1]) . (1 + x^2^[i-1]) [(x^2 - 1) = (x - 1) * (x + 1)]
looking at the right term because x is prime, we know (x^n) is odd and (x^n) + 1 must be even
and looking at the left term we can see it is in the same form as the original term except the power is (i - 1) instead of i
ie: we can write
FACTOR_i = FACTOR_i-1 * (2 * ...)
we also know the base case is (1 - x^2^0) = (1 - x) which is even because x is prime
so the factorization becomes k terms of the form:
2 . (...), 2 . 2 . (...), 2 . 2 . 2 . (....), 2^k . (....)
if we multiply the factors of 2
= 2^(1 + 2 + 3 + 4 .. k)
= 2^(k . (k + 1) / 2)
so a sequence of length 2^k will be divisible by 2^(k . (k + 1 )/2)
for example a sequence of length 256, k = 8 will be divisible by all powers of 2 <= 2^36 which is enough to create a polynomial that evaluate to 0 when the full 32 bit output of the hash is used.
this polynomial of the form (-1)^t_j . x^j is not directly constructible from the hash because it has coefficients of -1 which are not possible to create from a byte value that only ranges from 0 to 255. however, if we take the difference of two different polynomials then the difference polynomial can contain coefficients which have the value of -1 and if two polynomials have a difference of 0 then they will evaluate to the same value and we will have a collision.
For example we can substitute -1 for 65 ('A') and 1 for 66 ('B') for the coefficients in one polynomial and the opposite for another polynomial. Then when we have 'A' - 'B' it will produce the -1 coefficient and where we have 'B' - 'A' it will produce the 1 coefficient. Also, if we have larger differences for example 'A'/'D' which produces coefficients of -3/3 then this is the same as multiplying the polynomial through by a constant of 3 so we can just ignore the constant factor and treat it the same as the -1/+1 result.
phash is used in the erlang dict module and uses increasing powers of 2 from 2^4. So if you wanted to hash-dos using 100,000 elements then length 64, k = 6 ensures divisibility by at least 2^21. however, in this case length 32, k = 5 also works even though it only guarantees divisibility by at least 2^15.
iex(10)> :erlang.phash("ABBABAABBAABABBABAABABBAABBABAAB", 1<<<17) == :erlang.phash("BAABABBAABBABAABABBABAABBAABABBA", 1<<<17)
in order to generate 100,000 collisions you can just generate 17 colliding pairs and then take all the bitstrings of length 17 and generate a multicollision from the bitstring by choosing either the left or right collision from the pair depending on which bit is set.
it might be possible to generate shorter collisions by random search or another method especially when the truncated range is small.
The erlang.phash2/2 function calculates the hash of a binary in a way that looks similar to a Merkle–Damgård construction.
There is a 96 bit state that consists of three 32 bit words. The state is initialized to constant values. There is a MIX function that takes a state and produces another state. This function is invertible. Hashing is done over 12 byte blocks. The bytes from the block are added to the state and then the MIX function is applied. Once all the blocks have been processed the length is added to the state and the MIX function is applied again. The 'c' state word is then returned as the hash value.
Because the MIX function and all the operations are 'invertible' it is easy to generate single 12 bytes collisions.
- Calculate the hash for a block
- Create a new state
{a = random, b = random, c = hash}as long as a/b are different from the original hash state - Calculate:
state' = INV_MIX(INV_MIX(state) - LENGTH)) - Calculate:
colliding block = state' - intitial_state
iex(3)> :erlang.phash2("123456789012", 0xFF_FF_FF_FF + 1) == :erlang.phash2(<<5, 233, 120, 82, 83, 16, 30, 22, 228, 149, 49, 249>>, 0xFF_FF_FF_FF + 1)
In order to generate multi-collisions you can just vary the state values a and b. This allows you to create very short binaries that collide compared to the original phash. One problem is the actual number of 'usable' binaries for collision purposes might be small due to ascii encoding issues so it might be necessary to generate a large number of colliding binaries to find valid ones and then use the 2^n multicollision trick to generate a larger number of collisions from the smaller number of valid binaries.
ETS uses phash2 for hashing (or ETS using the same internal function that phash2 uses). This makes it possible to denial of service ETS that accepts user input.
The new erlang maps also use phash2 for hashing. However, they don't seem vulnerable to a quadratic slow down. The erlang map implementation is based on hash array mapped trie with a branching factor of 16. The erlang map implementation will hash the value then takes the first 4 bits from the hash and then choose an array slot based on that hash. it will continue going down a tree consuming 4 bits from the hash until it can find an empty slot. If it is unable to find an empty slot after consuming 32 bits it appends a 'prefix' to the value being hashed and rehashes and continues searching. This rehashing makes it difficult to force the map to do quadratic work because you need to find collisions across a large number of prefixes.
For example if you could easily do:
HASH(PREFIX1 || INPUT1) == HASH(PREFIX1 || INPUT2)
HASH(PREFIX2 || INPUT1) == HASH(PREFIX2 || INPUT2)
...
HASH(PREFIXN || INPUT1) == HASH(PREFIXN || INPUT2)
Then it would be easy to make the map do quadratic work since with two fully colliding inputs you could force the map to evaluate the hash function LENGTH/8 times and it iterates over LENGTH bytes giving you LENGTH^2 work. If it were possible to generate internal collisions in the state for the same input but different prefixes then generating collisions across multiple prefixes would be easy but because the MIX function is invertible this is not possible.
ie:
STATE(PREFIX1 || INPUT1) == STATE(PREFIX2 || INPUT2)
But this implies MIX(STATE) = MIX(STATE') when STATE =/= STATE' which is not possible when MIX is invertible
I mostly wrote this post because maybe someone has an idea on how to hash-dos the hash map array trie. Maybe there is a trick that takes advantage of the structure of the mix function that makes it easy to collide different prefixes in the end result.