Are there cryptographic hash functions that can be computed using only paper and pen without leaking any information about the plaintext?

Question

I am looking for a cryptographic hash function that can be computed by a human using only paper and pen without ever leaking any information about the plaintext on the paper.

The cryptographic hash function should be computable by an algorithm satisfying the following properties:

• Input/output: Any input/output set is acceptable as long as a human can represent and convert between that and text (e.g., base-2 <-> ASCII is acceptable).
• Memory: Keeping in mind that humans can hold about 7±2 objects in working memory, the algorithm must require no more than 11 chunks (e.g., 11 digits, letters, or common words) of secure memory at any time. Data that do not need to be kept private can be offloaded to paper. Assume that the plaintext can be randomly accessed from secure read-only memory stored in the mind of the human.
• Speed: The hash should be computable for a short input (say, 16 ASCII characters) in under a day. Under an hour would be great. Under a minute, fantastic.
• Materials: Assume access to pen and paper. Precomputed tables (e.g., for S-boxes) are undesirable but acceptable; better would be tables that can be recomputed from easily-memorized compressed representations. Same goes for magic numbers or other precomputed data.
• Security: The hash function should be preimage resistant. Second preimage resistance and collision resistance would be nice bonuses.
• Side-channel attacks: The paper (or any medium other than the brain) must not at any time contain data that leaks information about the plaintext (burning the paper afterward is insufficient; assume that the state of the paper is monitored by an adversary throughout the computation).
• Instruction set: The processing instrument is a human brain and operations must be executable by, say, a typical math/CS grad student (with practice). It may be useful to assume that the human can perform single-digit base-64 arithmetic (a set of $64^2$ mappings can be learned easily within a year through spaced repetition).
• Description: It would be great if the algorithm can be memorized (along with representations of all precomputed tables and magic numbers). Otherwise, it would be best if a description fits on two sides of A4 paper (in words, diagrams, or anything else).

Current mainstream cryptographic hash functions are of course acceptable as long as there are algorithms that compute them satisfying the listed properties.

Esoteric instructions are acceptable. For example, if some part of the algorithm that requires a lot of secure memory can be done under a homomorphic scheme that requires little secure memory to execute (the idea being that everything can then be offloaded to paper without risk of leaking the plaintext), then go for it. (Something like this would presumably require a source of cryptographic randomness. That is okay: the human can memorize a high-entropy string known to no one else.)

For a less restrictive version of this problem, allow access to a modern computer, but assume that all input, output, memory, and instructions are monitored by an adversary (so entering sha512sum <plaintext> is not allowed because that leaks the plaintext). Use any standard Unix tool or language. Input and output are guaranteed to be untampered with.

I am looking for such an algorithm so that I can (re)generate high-entropy passphrases at will—even when I don't have privacy nor access to a secure computer—by memorizing a single high-entropy key and computing $\operatorname{hash}(\text{key}\mathbin{\|}\text{salt})$, where $\text{salt}$ is an easily guessable string unique to each passphrase.

There have been a few similar questions here on crypto.SE. Below I outline how this question is different from each of them:

Is there a simple hash function that one can compute without a computer?
Is there any strong enough pen-and-paper or mind cipher?
I am concerned more about security and side-channel attacks, and less about speed and simplicity.

Is there a secure cryptosystem that can be performed mentally?
I am looking for a hash function, not an encryption protocol.

Pen-and-paper one-way function for externally-anonymous survey
This question was asking for a fast and simple trapdoor function, which I am not looking for.

Answer 1

Check out Manuel Blum's human computable hash function. He calls it HCMU for Human Computable Machine Unbreakable.

He claims you have to spend an hour memorizing the technique and then you can apply the hash function in about 20 seconds without even using pencil and paper.

The memorization required is to remember a random mapping of each letter of the alphabet to a digit in the range 0 to 9. You also need to remember a random permutation of the numbers 0 through 9. These stay the same for each string you want to hash so you only have to memorize them once. It's well within the ability of the average person to remember.

The hash function involves mapping the input string to digits, doing simple addition functions and then looking up values in the random permutation you memorized. He has a proof that it should be difficult for a computer to break the hash.

http://www.heidelberg-laureate-forum.org/blog/video/lecture-monday-september-22-2014-manuel-blum/

Answer 2

This requirement is a killer:

The paper (or any medium other than the brain) must not at any time contain data that leaks information about the plaintext.

Almost any security proof for a hash assumes an adversary only gets to see digests, not any mid-state. Mid-state has not had enough confusion and diffusion, so it leaks information.

This means that all secret state has to be kept in the mind, and all computations on the secret state have to be done mentally. Honestly, I think I can remember at most 8 numerical digits while doing a complex crypto routine on them (with pen and paper tracking progress throughout the routine). This means a security of ~26 bits max, so this can not possibly be secure.

And all that is assuming someone can actually describe a secure hashing scheme that can be done using mental operations.

Answer 3

I still don't understand your desire for a hash, especially considering (as already stated at other places in this forum) that you don't gain any entropy by subjecting a PW to a deterministic function like a hash. So, when decrypting your ciphertext, you will be as secure with a H(key) as with (key), thus you might as well just memorize a good long passphrase + a random string for a good measure. I strongly feel that with such complex requirements and somewhat obscure thoughts one needs to meet face-to-face to really understand the nuances of the desired application.

With that said, I will now attempt to propose an algorithm that you may find useful to whatever you are trying to accomplish. It is not really a hash, but it may hopefully provide the mechanism you are looking for. I am using your terminology here - "key" as the input string and "passphrase" as the output string:

(Note: I will list the decryption phase only, working against an adversary. Encryption would be similar, but can be computerized as stated in the question)

Initialization:

• Put a square matrix of random characters, 16 rows by 16 columns, totalling 256 chars, on a piece of paper
• Memorize a good key containing 2 distinct logical parts with equal length, e.g "Johnny%rides || yellow+zebra" (Alternatively, memorize 2 separate keys of equal length). I use here a short weak key just for demo purposes.
• Memorize one random string (preferably containing some high ASCII characters e.g. foreign currency symbols)
• Learn and memorize the 7-bit decimals (or hex) ANSI equivalent of the 95 char sets (I assume you use the English language for your passphrase). Easy to do since they are sequential (can put the full ASCII table lookup on paper)
• Learn and memorize the 7-8-bit decimals (or hex) representation of the characters in the random string (can put the full extended ASCII lookup table on paper).

Decryption (doing a streaming OTP + substitution):

• Mentally split the key into its 2 distinct logical parts e.g Part A: "Johnny%rides" and Part B: "yellow+zebra"
• Mentally take one character, at the same position in each Part, and convert to its hex equivalent. e.g. convert "J" and "y" to 0x4A and 0x79 respectively. (it might have been easier to memorize the decimal equivalents, so in that case you should also go through the mental step of decimal -> hex)
• Mentally take the hex value of the character of Part B, namely 0x79, and use its 2 hex elements as a (x,y) index into the written random table. Mentally pull out the random character from the cell and convert it to a hex equivalent.
• Mentally take the hex value of the character of Part A, namely 0x4A, and perform XOR with the hex representation of the pulled cell value. In essence, doing OTP encryption between Part A of the key and a random value.
• Use that hex value as the first character of your desired passphrase, writing it down and freeing your brain from remembering it.
• Repeat the process with the next character of each part of the key, but with each successive character you need to increment the row from which you pull the random cell from, to thwart frequency analysis due to english words which are present in Part B - the index into the random table.

The above process requires minimal memory and mental load. When you are done, you will have your full passphrase. You can increase the size of the passphrase to double (or more) your Part A size by adding to each pulled cell value another cell value, say selected by a "knight move" from the first landing cell - as in a chess game.

Application Notes:

You can increase security if you prepare larger random matrix, and use 2 successive characters of Part B (mod table size) as an index. Also, if practical, you should prepare several random tables and use them in succession - each associated with a different key. The one random string you initially memorized can be used in a creative way - as an another index into the random table, concatenating or XORing with the results due to Part A etc.

Caveat: I hope that what I proposed here is to some extent what you were looking for. I haven't spent time analyzing the cryptographic strength of this proposal. It may have sever flaws, but this is the best I could come up with at a reasonable time. Before putting it into practical use, you must evaluate its security, deficiency and usefulness.

Answer 4

No, there aren't any cryptographic hash functions like this. I'm pretty confident you're not going to find one. I have yet to see a white-box secure hash function that remains secure against dedicated attack, let alone one that you can implement securely on pencil and paper. Since this is a practical problem, I suggest finding another solution -- like hashing your passphrase on a computer you trust.

Answer 5

I'm not sure how secure this is (posting here will probably reduce its security at least a little), or whether it would necessarily even be called a hash function, but in terms of input/output (keyboard keys), memory (I think about 3 chunks beyond the piece being manipulated at a time), speed (a couple minutes to produce around 8-16 characters), materials (keyboard), side-channel attacks (only the output is ever written down), instruction set (visual manipulation in your head), I think this algorithm I came up with a few years ago for generating passwords is hard to beat.

There are 26 letters in the English alphabet, which just so happens to be 1 less than 3³. Look down at your (QWERTY) keyboard. Now look at me. What you just saw were three rows of letters, containing 10, 9, and 7 letters each. Mentally move the "P" down to where the "," is, and now each row has 9 or fewer keys in it. Now mentally separate the keyboard into 3 regions containing 3 columns. Every key can now be denoted by a base-3 3-tuple specifying row, section, and column within the section. Don't worry, you will never need to write down the 3-tuple, or even know what a tuple is; that bit is for explanation purposes only. Basically, you want to create this mental image:

The other thing you will need is a seed word. For passwords, 5 characters will generate 5 letter-number combinations for 10 digits (if you don't mind hashing only partway through your input); if you want to hash something longer, you will obviously need a longer seed.

Now, for the algorithm:

For each pair of letters from the input and the seed, find the letters on the keyboard. I am using "D" and "B" for the input and seed, respectively.

Now, you don't need to convert the letters into coordinates! You only need to figure out one coordinate at a time. And don't think of them as 1,2,3, think of them as (left, middle, right), and (top, middle, bottom) - or better yet, don't think of them at all; just picture their locations. For the purposes of explanation, I am going to convert them anyway:

• B is in the middle section, in the middle column, on the bottom row.
• D is in the left section, in the right column, on the middle row.

Now, to reassemble the output, we're going to need to map pieces of each of the inputs to our output. How exactly this is done is to be determined by the user; just make sure you always map the same way every time. And make sure you use at least one component from the input and at least one component from the seed.

An example mapping could be (input column -> output section, seed row -> output column, input section -> output row). An easy and more memorable way to work this in your head is to picture each input piece rotating/sliding to where it maps to on the output (starting with whatever maps to the output section will usually be the easiest to do first, regardless of what maps to what).

So (since animations are beyond what I can do right now):

1. Input (D) column (right): A, S, and D expand out to correspond to the left, middle, and right sections. Picture subsequent steps happening in the right section.
2. Seed (B) row (bottom): T, G, and B rotate to the horizontal and slide over to the right section, where they correspond to the columns headed by U, I, and O. Picture the last step happening in the O column.
3. Input (D) section (left): The left, middle, and right sections shrink and rotate vertically to overlay O, L, and P (which was borrowed from the top row). The output letter is O.

Now, I promised that the output would be a letter and a number. Don't forget that we have used only 3 of the 6 available coordinates. You can map two of the remaining three coordinates to the number row, which is divided into 3 rows of 3 numbers (ignoring the 0 or any other number you don't happen to like). This leaves one remaining coordinate, which you can use to determine whether you should hold Shift when you're hitting a letter, or a number, or both, or neither (only 3 of the 4 options will be available, so choose wisely). I do recommend having that coordinate come from the seed, so you can choose a seed word that will ensure password suitability if you are using this for that purpose.

I do see some potential problems with reverse-engineering your algorithm/seed if someone can get a hold of enough input/output pairs; but hopefully the method used will obscure it enough to make it difficult. You can always use a different coordinate mapping or seed word if concerned. Like I said, I don't know if this would be secure enough for anything other than passwords, but it is potentially useful for people who might have trouble doing more complex calculations in their heads. And no intermediate steps are ever recorded!