Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add hmakholm/smhasher LongNeighborTest #58

Open
rurban opened this issue Mar 18, 2019 · 1 comment
Open

Add hmakholm/smhasher LongNeighborTest #58

rurban opened this issue Mar 18, 2019 · 1 comment

Comments

@rurban
Copy link
Owner

rurban commented Mar 18, 2019

Good test esp. for long blocks (Spooky), and the separate byte-wise processing of unaligned rest parts.
https://github.com/hmakholm/smhasher/blob/master/src/LongNeighborTest.md

This test uses a meet-in-the-middle approach to look for hash collisions between messages with low Hamming distances.

Developing the test was prompted by the discovery that SpookyHash V2 has lots of 3-bit collisions due to insufficient diffusion between the processing of the last full input block and the partial block at the end of the input. The goal of the test is to discover similar trouble in other hashes.

Because Spooky has an unusually large block size of 96 bytes (=768 bits), and it uses a completely different algorithm for messages shorter than 2 blocks, this problem only shows up for messages of length 281 to 287 bytes, and then again from 377 to 383 bytes, etc. Notably, messages of any "nice" length are not affected, which means that we need to test for all possible message lenghts.

Just need permission from Semmle Ltd

@rurban rurban self-assigned this Mar 18, 2019
@rurban
Copy link
Owner Author

rurban commented Mar 18, 2019

See the branch: https://github.com/rurban/smhasher/tree/LongNeighborTest
I've added --verbose support.

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

No branches or pull requests

1 participant