Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I'm looking for a toy hash function, where the idea is to have high school students break (i.e. find a collision) a hash function by hand, in order to teach them how one way functions and hashing works.
Do you happen to know some function like that?
As for how hard I want it to be to breakable: Ideally a "sizeable" function so that depending on some variable it can be easier or harder, but overall I'm looking at something about between 10 and 30 minutes.
I like the didactic approach in this answer. But for something that behaves more like a hash function should, we might define $H$ for strings of digits $s$ as: $H(s)=(((1||s)\bmod 97)||s)\bmod 99991$ where $a||s$ is the number resulting from prepending the decimal representation of $a$ to the string $s$.
Worked out example for $H(012345678)$
$=(((1||012345678)\bmod 97)||012345678)\bmod 99991$
$=((1012345678\bmod 97)||012345678)\bmod 99991$
$=(37||012345678)\bmod 99991$
$=37012345678\bmod 99991$
$=77082$.
With some math insight and very little extra computational effort, one can exhibit a collision; a "brute force" search for collision is also feasible with simple use of a spreadsheet.
If you want to demonstrate the properties of a good cryptographically secure hash, you could start with a non-cryptographically secure hash, and show why collisions are bad, why reversibility is bad, and why allowing modifications is bad. Once they've learned the "bad", they should better understand why those properties make a cryptographic hash "good".
The Luhn algorithm would be a good choice for pencil and paper attacking. It's a real world hash algorithm used on credit cards and barcodes, and produces what is commonly called a "check digit". In reality, it's no more than a very simplistic hash of the previous digits, and was originally developed to help guard against keying errors. Collisions are easy to find. Depending on the length of the input, it's generally not reversible (however if you feed it only a one digit input, it's certainly 100% reversible.)
If you'd rather use a real cryptographic hash (one that will require a computer) you could artificially reduce the size of the produced digest using the modulo function. Take a SHA-2 hash and divide the digest modulo 256. That will give you a one-byte hash value, which should be trivial to find collisions for. Expand it to two bytes, and the students will see that it gets harder. Continue expanding it out to the full 32 bytes, and collisions will quickly stop being so easy.
