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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
up vote 11 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
    
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
2  
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

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.

A5/1

share|improve this answer

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.

share|improve this answer
    
It might be possible to apply Gaussian elimination on the 256 x 64 matrix representation of "r"s without much effort :/ Brain not quite co-operating at the moment. – NikoNyrh Jan 5 at 18:58
    
As pointed in comment above, Gaussian elimination allows to find a preimage (if there is one), and that implies this is not collision-resistant. – fgrieu Jan 6 at 16:39
1  
True, but O(n^3) makes it quite tedious for larger instances. Not sure how large it should be to satisfy the condition "There should be no trivial way to find a collision (by hand)". – NikoNyrh Jan 6 at 21:11

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.

share|improve this answer
    
Are you suggesting using the message as RC4 key? How are you handing messages with length >256 bytes? What about the trivial collision between a and aa? – CodesInChaos Jan 4 at 14:26
2  
The linked RC4-Hash is broken: Collisions for RC4-Hash - Sebastiaan Indesteege, Bart Preneel. The paper even includes example collisions. – CodesInChaos Jan 4 at 17:54
1  
Interesting, but that was kind of expected with RC4. The work of 2^9 is even doable without a calculator! – NikoNyrh Jan 4 at 19:19

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

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

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.