-
Notifications
You must be signed in to change notification settings - Fork 102
AHash fallback algorithm
The fallback hash algorithm keeps a 64 bit state. That state is updated on every new chunk of data.
This is done based on a "folded multiply". A folded multiply consists of taking two 64 bit numbers and casting them to 128 bit numbers and multiplying them together to get a 128 bit result. (In hardware this is a single 64 bit multiply because the upper 64 bits of each side are zeros). Then the resulting 128 bit number is split into two 64 bit numbers which are xored together.
Unlike a standard multiply where the upper 64 bits are usually computed and thrown away, each input bit has the opportunity to affect each output bit. For example suppose two inputs differed in only the 5th bit. Then when the multiplication is performed the result will differ in bits 5-69. More specifically it will differ by 2^5 * MULTIPLE.
However in the next step bits 65-128 are turned into a separate 64 bit value. So the differing bits will be in the lower 6 bits of this value. The two intermediate values that differ in bits 5-63 and in bits 0-5 respectively get xored together. Producing an output that differs in every bit.
Updates to the state work as follows:
- The new data is xored with the current state.
- A folded multiply is performed with (A safe prime)
Or for larger updates:
- The update is broken into two halves
- Each half is xored with a key.
- They are then "folded multiplied" with each other.
- In parallel, another key is added to the prior state.
- Then the result of (3) and (4) are xored with each other to form the new state.
- A fixed rotation is applied to the new state.
(Despite the additional complexity this is actually faster than performing the simpler update twice, because it is able to incorporate 128 bits of new data with a single multiply.)
This has the goal of updating the buffer with a single multiply. FxHash does also uses a single multiply but is vulnerable to attack. To avoid this input needs to be masked to with an unpredictable value. This is what the xor in the first step achieves.
Other hashes such as murmurhash have taken this approach but were found vulnerable to attack. The attack was based on the idea of reversing the pre-mixing (Which is necessarily reversible otherwise bits would be lost which could also be used to create collisions) then placing a difference in the highest bit before the multiply used to mix the data. Because a multiply can never affect the bits to the right of it, a subsequent update that also differs in this bit could result in a predictable collision.
This version avoids this vulnerability while still only using a single multiply. It takes advantage
of the fact that when a 64 bit multiply is performed the upper 64 bits are usually computed and thrown away.
Instead these are used to ensure it is impervious to attack because every bit buffer at the end is dependent on every bit in
new_data ^ buffer or new_data ^ key.
The addition carries in the multiplication mean that the even if an attacker somehow knew part of (but not all) the contents of the buffer before hand, they would not be able to predict any of the bits in the buffer at the end.
This also makes a good scrambling function. It is similar to a it helps to understand multiply-with-carry PRNG If the multiple is chosen well, this creates a long period, decent quality PRNG. The update function is equivalent to this except the buffer/state is being xored with each new block of data. In the event that data is all zeros, it is exactly equivalent to a MWC PRNG.
After the input has all been read in, the finalization step proceeds by performing a folded multiply using a random 64 bit key. As outlined above this fully diffuses the state and the key across all bits of the output.
Finally a data dependent rotation is preformed. So in addition to having the state fully defused across the output, output bits from different inputs do not align across different inputs.