Is there a simple hash function that one can compute without a computer?

Question

I am looking for a hash function that is computable by hand (in reasonable time). The function should be at least a little bit secure: There should be no trivial way to find a collision (by hand). For instance, a simple cross-sum is not meeting this criteria since one can easily construct a number with the same hash than another.

Is there a (simple) function? I am interested in this for a presentation about commitment schemes in my CS class at school.

Answer 1

Well, depending on what's reasonable and what you can compute reliably by hand, you MIGHT be able to compute modular exponents in a moderate-size group (like $Z_n$ for moderate $n$). Exponentiation via repeated squaring is doable I think.

Probably more practical would be a MD5-like ad hoc confusion-diffusion primitive. You'd need to make the input large enough to make exhaustive search impractical by hand (32 bits should do it I would think?) and then make a round-function that was simple enough to compute by hand but had empirically-good collision-resistance. Finally apply Merkle-Damgaard for a "few" rounds.

I would expect this to work reasonable well with a random crypto classmate. If you're playing against Adi Shamir, you're probably screwed.

Edit: For in-person commitment schemes, you can get rid of hash functions altogether. Just write a string of random bits on a folded paper and hand it to your partner to commit those bits. But the more interesting scenario is doing this through a prison wall, over a phone, or over the internet... then you really need something mathematical.

Let's take the prison-wall example: you want to commit to another inmate some integer $x$ and you have no computational resources but can communicate with tapping (no paper). Here's what I would do: pick a 64-bit number $x$ that you want to commit. Make sure you can't factor it (it might be prime, but verifying primality is going to be tedious by hand). Then choose another, larger, 64-bit number $y$ that is also hard to factor by hand.

Now compute $p=xy$ (easy) and send $p$ to your buddy. If $x$ and $y$ were both hard to factor, $p$ is as well, so he can't extract $x$ or $y$ from $p$. Now for the reveal, you send $x$ and $y$; he verifies that $p = xy$ and that $x$ is the smaller integer.

It's important that both are 64-bits (or both the same size) to prevent you from changing to $x'$ after the commit where $p = x' (k y)$. This doesn't happen if $x$ and $y$ are prime, of course, but large primes aren't easy to generate by hand.

Answer 2

I don't know of any secure cryptographic hash function that you could easily perform without a computer. If you are unable to find a hash function I suggest you use a random oracle. A random oracle is the construct on which hash functions attempt to approximate. It is very simple to implement a random oracle without a computer. All you need is a piece of paper, a pen and a quarter.

Lets say you want a random oracle that maps all binary strings to 8-bit outputs. $$RO : \{0, 1\}^{0 \text{ or } 1 \text{ or } 2 \text{ or } ... \text{ or } k} \rightarrow \{0,1\}^8$$

Ask someone for an binary input string:

1. Look for the input on the paper, if it is already on the paper return the corresponding output.
2. If this input isn't on the paper, generate an output for it by flipping the quarter 8 times (heads are 1, tails are 0). Write the new input/output pair on the paper.

After a few inputs you're paper should look like:

|           inputs             |           outputs             |
+------------------------------+-------------------------------|
|           101                |           00111011            |
|           1111111111111      |           10010010            |
|           101010101010111    |           01101100            |
|           1                  |           00101011            |

After about 16 inputs you should start getting collisions.

Answer 3

The following simple "check" algorithms are popular for detecting accidental errors. The following algorithms are "position sensitive", allowing them to detect the common error of accidentally swapping 2 consecutive digits (an error that a simple checksum -- adding up the digits -- can't detect).

In increasing order of complexity (and resistance to finding collisions):

• All credit cards use the Luhn algorithm to calculate the final check digit. (But it's only 1 digit, so you will expect collisions after 3 messages, and are guaranteed a collision, in the "best" case, by the 10th message).
• Luhn mod N algorithm (can be adapted to calculate a "check digit" that is any number of decimal digits or any number of binary bits). Alas, it's pretty easy to deliberately construct a collision from a known message -- simply swap any two digits that are both in odd positions of the message; or any two digits that are both in even positions of the message.
• a Fletcher checksum with a sufficient number of bits (perhaps Fletcher-64 ?).

To calculate a Fletcher checksum, we start with:

• Initialize the primary checksum P1 = 0, and the simple secondary checksum S2 = 1.
• Break up the message to be hashed into "blocks". (Fletcher-64 uses 32-bit blocks, but perhaps something like blocks of 3 letters where A=01 and Z=26 would be easier to work with by hand, so the block ZAB becomes decimal 260102).
• For each block: add the block to the simple secondary checksum and then (to make it position sensitive) add the secondary checksum to the primary checksum, before going on the next block.
• P1 and S2 summarize the message. For your demo, perhaps you could use { P1 concatenate S2 } directly as a simple hash, skipping the "Further calculations" step.
• Further calculations reduce P1 and S2 to a Fletcher checksum or an Adler checksum.

The Fletcher checksum is nowhere near a cryptographically secure hash, but perhaps it's adequate for a quick paper-and-pencil demo.