Skip to content

Instantly share code, notes, and snippets.

@defuse
Last active May 26, 2018 10:02
Show Gist options
  • Save defuse/14a24fffe484198b957ad5903e07c547 to your computer and use it in GitHub Desktop.
Save defuse/14a24fffe484198b957ad5903e07c547 to your computer and use it in GitHub Desktop.
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
Copy link
Author

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
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment