{{ message }}

Instantly share code, notes, and snippets.

# defuse/hash-function.md

Last active May 26, 2018
Hash Function

For a 512-bit input x, the 256-bit hash of x, H(x) is defined as follows. Simulate a frictionless table on which disks may slide around and collide with the sides of the table as well as other disks according to Newton's laws (elastic collisions). The simulated box is 32m by 32m subdivided into a 16x16 grid of squares. At the center of each square place a 1m-radius disk with unit mass and 1m/s velocity in a direction that encodes the next two bits of x: 00=up, 01=down, 10=left, 11=right. Simulate this state's evolution for T=1024 seconds. Now generate the output as follows. Starting with an empty output, enumerate all of the disks (in the same order they were generated) and append a 0 to the output if the velocity vector has a positive upwards component or a 1 otherwise. The simulation must be as precise as necessary for the output to be correct.

Is H collision-resistant? Can you break it? If you can't, what's the largest value of T for which you can?

See breaks and patches in the comments below.

### defuse commented Jul 11, 2017

 ...and if you do find a collision, can you think of a different procedure for generating the initial state that makes it harder to find collisions?

### defuse commented Jul 11, 2017

 Broken by mongo: https://twitter.com/mongobug/status/884797392847024128 Patch: When generating the output, change "positive upwards component" to "positive 45 degree up-left component."