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

I don't think RC4-based constructs were mentioned yet, it would be fairly trivial to implement with a deck or two of playing cards or self-made cards. It has only modular sums and swaps, and only two state variables i and j :)

It is known to be weak but shouldn't be crackable without a calculator.

Edit: Yes, the message would be used to seed the cipher and a chosen length of stream output is the hash. A nonce can be generated by flipping a coin or shuffling the deck so we get unique hashes for identical messages.

Oh Wikipedia says max key length is 256, so maybe long messages can be split on smaller chunks. Each chunk seeds an RC4 instance and output of that + next chunk is used to key the next one. The final instance is used for hash generation.

I wonder how insecure this non-standard construct has already become, especially given the need for collision resistance.

Edit 2: a relevant RC4-Hash paper:

In this paper we presented a new hash function RC4-Hash, and claim that it is secure as well as very fast. This hash function is based on the simple structure of RC4. This proposed hash function generate variable size hash outputs (like a family of hash functions e.g., SHA family). It’s structure is different from that of many well known hash functions. Due to its completely new internal structure and huge size of internal state (approximately 1700 bits) it resists all generic attacks as well as path breaking attacks by Wang et al.

Answer 4

How about using something similar to Zobrist hashing and generate the look-up table by coin flips?

Let's say you want to commit to a 64-bit integer and you are able to deliver the look-up table in person and later communicate a 256-bit hash.

Flip the coin 256 x 64 times, with 2 seconds / flip it takes 9.1 hours so you might not want to do it every day :) Or you could have 64 people doing it in parallel at under 9 minutes.

The result is 64 random 256-bit integers $r_0, r_1, ..., r_{63}$. To commit to a 64-bit value $v$ you express it in binary ($i_n < i_{n+1}$): $$ v = 2^{i_0} + 2^{i_1} + 2^{i_2} + ... + 2^{i_n} $$

and calculate the hash $h(v)$ as $$ h(v) = r_{i_0} \oplus r_{i_1} \oplus r_{i_2} \oplus ... \oplus r_{i_n} $$ which is communicated to the other party.

To commit to a boolean value you might want to generate 63 random bits for $v$ and choose 64th bit to encode commitment as its parity.

Actually both parties could generate their own look-up tables and exchange them, they could be merged via xorin or appending with each other. This should diminish the chance of malicious tables.

This is based on following assumptions which might be incorrect:

• Given $v$ it is easy to calculate $h(v)$
• Given $h(v)$ it is difficult to recover $v$
• The table is legit and values are "linearly" independed in mod 2 sense so collisions are impossible (not sure how easy this is to check by hand and didn't simulate how likely it is)

I think similar algorithm is used in secret sharing, homomorphic encryption or something related. Naturally the used values 64 and 256 can be adjusted as seen fit. I forgot how big effort it is to "invert" $h(v)$.

Edit: fixed "256 random 64-bit integers" to "64 random 256-bit integers"

Edit 2: Can this be solved by finding 64 "independent" bits from each $r$, form 64 x 64 "linear" equation (mod 2) and solving $\mathbf{A} \vec{x} = \vec{b}$? It would probably take $O(n^3)$ time, n being 64 in this instance (Gaussian elimination).

Anyway it can be midigated against "manual" attacks by using more bits as calculating $h(v)$ is only $O(n)$. But $r$ needs to have sufficiently many bits to be confident that they are "independent" even when randomly generated.

Answer 5

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.

Answer 6

Anagrams were used by scientists centuries ago to publicly prove when they discovered something without revealing exactly what they discovered. It's basically a count of how many unique characters were used in a sentence. The method doesn't produce fixed-length strings as cryptographic digests like SHA-256 but they are doable by pen and paper.

Create a unique sentence that describes the fact that you want to commit. Sort all characters alphabetically so their order is lost but character counts remain the same. Publish the alphabetised character list.

Example:

today on the twenty first day of may in the year twenty twenty i posted an answer to a question that fuzxxl published on stack exchange about how anagrams may be used to prove the existence of statements

a16,b3,c3,d5,e21,f4,g2,h7,i6,j0,k1,l2,m4,n13,o12,p3,q1,r5,s11,t23,u5,v1,w5,x4,y8,z1

aaaaaaaaaaaaaaaabbbcccdddddeeeeeeeeeeeeeeeeeeeeeffffgghhhhhhhiiiiiikllmmmmnnnnnnnnnnnnnoooooooooooopppqrrrrrssssssssssstttttttttttttttttttttttuuuuuvwwwwwxxxxyyyyyyyyz

Answer 7

Sorry for spamming answers but this is an interesting and practical topic :)

I think it is viable to execute GSM's A5/1 algorithm manually by preparing roughly 40 to 50 pieces of 1s and 0s or 80 to 100 in total (assuming that out of 64 bits of state roughly 50% are 1s and 50% 0s).

The 64-bit commitment would be used as the initial state (19 + 22 + 23 = 64) and the revealed value is for example 128 bits of the steam output. Perhaps first 128 or 256 bits should be discarded to hide the internal state better and make it more costly to find a collision.

This is still quite verbose algorithm to run by hand and mistakes are easy to make. Also I have no clue about its pre-image resistance. Other (ad-hoc?) LFSR-based system would be easier to simulate but wouldn't be as secure.

Answer 8

DISCLAIMER: this is NOT a mathematical/cryptographic hash function, but it is a one-way commitment scheme that does have SOME cryptographic attributes (pre-image resitasnce, collision-resistance):

Write your text in a piece of paper, sign it, and tear the paper, ensuring the tear splits the text in 2. Then hand over one half to the other party.

To verify the "hash", you need both halfs, and check that they match. It is ultimately secure, at the molecular level. Of course it is not flexible, nor extendable, but it may well serve as an example for a CS lesson on commitment schemes.