Mental hash function

A few years ago I wrote about Manual Blum's proposed method for mentally computing a secure hash function. He proposed using this method as a password manager, using the hash of a web site's name as the password for the site.

I first wrote about Blum's method on the Heidelberg Laureate Forum blog, then wrote some footnotes to the post here.

NB: This method is insecure for reasons Rob Shearer describes in the comments.

Algorithm

Blum's algorithm requires creating and memorizing two things: a random map from letters to digits, and a random permutation of digits.

Let f be a function that maps the set {A, B, C, ..., Z} to the set {0, 1, 2, ..., 9} created by a random number generator, and let g be a random permutation of {0, 1, 2, ..., 9}.

Start with the text you want to hash. Then use f to convert the text to a sequence of digits, replacing each character c with f(c). Label this sequence of digits

a₀ a₁ a₂ ... a_n.

To create the first digit of your hash value, add the first and last digits of your sequence of digits, take the last digit of the sum, and apply the permutation g to it. In symbols, the first digit of the output, b₀, is given by

b₀ = g( (a₀ + a_n) % 10 )

where a % 10 is the remainder when a is divided by 10.

For the rest of the digits, add the previous output to the current input, take the last digit, and apply the permutation. That is, for k > 0,

b_k = g( (b_k-1 + a_k) % 10 ).

A few years ago Blum recommended using at least 12 characters.

Python code

Here's some Python code to implement the method above and make all the details explicit.

 from numpy.random import default_rng rng = default_rng(20220516) fdata = rng.integers(10, size=26) def f(ch): ch = ch.lower() return fdata[ord(ch) - ord('a')] gdata = rng.permutation(10) def g(n): i = list(gdata).index(n) return gdata[(i+1) % 10] def hash(text): digits = [f(c) for c in text] N = len(text) out = [0] * N out[0] = g((digits[0] + digits[-1]) % 10) for i in range(1, N): out[i] = g((out[i-1] + digits[i]) % 10) return "".join(str(d) for d in out) print(hash("hello"))

This prints 26752.

Is mental cryptography hopeless?

It's been eight years since I talked to Manuel Blum. Perhaps he realized years ago that this system is flawed. But I still find his initial question interesting: are there encryption algorithms that humans can execute mentally that cannot be easily broken by computers?

It would be interesting if such an algorithm could at least put up a good fight. Cryptographic algorithms are considered broken if they can be compromised given a few weeks of computing. Could a mental hashing algorithm at least withstand an hour of computer attack?

The post Mental hash function first appeared on John D. Cook.