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 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.

share|improve this question
    
Good question! There are the types of hash functions used in programming languages for string hashing (e.g. Java), but there is is not that hard to find collisions. –  Paŭlo Ebermann Sep 23 '11 at 21:42
    
I have an idea by myself: Could one use exponentiation modulo something as a hash function? –  FUZxxl Sep 23 '11 at 21:59
    
This could work ... but you'll have to adapt the parameters (modulus, generator, padding?) so it is neither trivial to break nor too hard to compute by hand. –  Paŭlo Ebermann Sep 23 '11 at 22:24
    
Another thing would be squaring modulo somthing - solving this is NP-hard, but i doubt that it is impossible to find collisions. –  FUZxxl Sep 23 '11 at 22:25
3  
Squaring modulo something wouldn't be NP-hard; if modulo a prime, we know how to compute square roots efficiently, and if modulo a composite reduces to factorization, which is not known to be in NP-hard or NP-complete. –  Samuel Neves Sep 23 '11 at 23:12

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
1  
Great idea! I like it, but first I have to Google all those terms. –  FUZxxl Nov 5 '11 at 8:56
    
You can improve your chance of picking a prime by using the 6k±1 rule. Note that this rule only applies one way - all primes fit the rule, but not all numbers that fit the rule are primes. –  Polynomial Jun 6 '12 at 17:45
1  
The 6k$\pm$1 rule doesn't help much: every integer is between -2 and 3 mod 6. Half of these are even and therefore obviously composite; one is an odd divisible by 3, which is quickly found out. The last 2 satisfy the 6k$\pm$1 rule, so it tells you nothing further. –  Fixee Jun 7 '12 at 6:40

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.

share|improve this answer
1  
This method is not good for my application (commitment schemes). If alice wants to get a collision, she could simply create an output by herself without having throwing a coin. –  FUZxxl Sep 24 '11 at 15:55
    
Yes, RO schemes typically require a trusted third party to keep the table of inputs and outputs and to generate new outputs. –  Ethan Heilman Sep 24 '11 at 21:39
1  
If I had a trusted third party, the whole commitment scheme would be completely pointless. –  FUZxxl Sep 24 '11 at 21:50
    
Variation: In addition to forcing every entry in the input column to be unique, also force every entry in the output column to be unique. I.e.: After writing new input on the paper, flip a quarter 8 times, writing the output on scratch paper. If the scratch 8-bit output pattern is already in the output column, to prevent collisions, repeat flipping the quarter 8 more times. When you eventually get a scratch 8-bit output pattern not already in the output column, copy it to the output column. Alas, this variant is awkward for more than 128 unique inputs, and fails after 256. –  David Cary Jul 30 '12 at 10:40

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.

share|improve this answer

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.