Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
How hard to you want it to be to break? –  mikeazo Apr 29 '13 at 13:40
    
good question, I should have clarified on that. 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. –  Shaga Apr 29 '13 at 13:45
3  
Boy I wish I had you as my high school teacher –  rath Apr 30 '13 at 0:21
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
2  
Hmm, but attacking the truncated SHA hash is just brute force, not cryptanalysis. Maybe a reduced-round version would be better. –  Paŭlo Ebermann Apr 29 '13 at 20:22
1  
At this point the idea probably isn't to get students to cryptographically break a hash function, it's more likely intended to teach them "why it's important that it's hard to discover a collision" and "why it's important that you can't recover the original message from the digest". –  John Deters Apr 29 '13 at 20:51
    
Another good example of a practically used "check value" which is not a secure hash is the IBAN "mod 97" checksum. Giving an IBAN (for a fictional bank) passing this test, and asking for two similar ones (same fictional bank and format) passing this test and differing only by rotation of 3 consecutive digits might be a good exercise (bonus points if none of the digits is a 7). –  fgrieu May 1 '13 at 18:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.