Mental hash function

Posted on by John

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

a0 a1 a2 … an.

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, b0, is given by

b0 = g( (a0 + an) % 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,

bk = g( (bk−1 + ak) % 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?

5 thoughts on “Mental hash function”

  1. >>> print(hash(“hello”))
    1971
    >>> print(hash(“error”))
    1971
    >>> print(hash(“alongertestdemonstratingtheproblem”))
    19761976197619761976197619761976197

    So.

  2. John

    Thanks!

    I had accidentally written f('c') rather than f(c), so the code was turning every letter into a c.

    The bug is fixed, but this still shows a weakness in the algorithm: repetitive input can lead to repetitive output, and so the method is vulnerable to a chosen cleartext attack.

  3. I’m afraid it’s much worse than that. This “secure hash” is trivial to crack. I’ll post an explanation to my own site in the next couple of days, but here’s some code:

    “`

    def myhash(fs, gs, text):
  out = [0] * len(text)
  out[0] = gs[(fs[text[0]] + fs[text[-1]]) % 10]
  for i in range(1, len(out)):
    out[i] = gs[(out[i-1] + fs[text[i]]) % 10]
  return "".join(str(d) for d in out)

letters = 'abcdefghijklmnopqrstuvwxyz'

def crack(c):
  out = []
  s = c * 10
  hs = hash(s)
  for fc in range(10):
    n = ord(hs[0]) - ord('0')
    fs = { c: fc }
    gs = {}
    zi = -1
    for i in range(1, len(hs[1:])):
      cc = hs[i]
      if zi == -1 and cc == '0':
        zi = i
      gs[(n + fc) % 10] = ord(cc) - ord('0')
      n = ord(cc) - ord('0')
    if zi != -1:
      gps = { v: k for k, v in gs.items() }
      for cc in letters:
        gfcc = ord(hash(s[:zi + 1] + cc + c)[-2]) - ord('0')
        if gfcc in gps:
          fs[cc] = gps[gfcc]
    out.append((fs, gs))
  return out

def merge(a, b, testData):
  (afs, ags) = a
  (bfs, bgs) = b
  fs = afs | bfs
  for k, v in fs.items():
    if k in afs and afs[k] != v:
      return None
  gs = ags | bgs
  for k, v in gs.items():
    if k in ags and ags[k] != v:
      return None
  if len(fs) == len(letters) and len(gs) == 10:
    for s, hs in testData:
      if myhash(fs, gs, s) != hs:
        return None
  return (fs, gs)
  
data = [(letters, hash(letters))]
o = crack(letters[0])
for l in letters[1:]:
  if len(o) == 1 and len(o[0][0]) == len(letters) and len(o[0][1]) == 10:
    break
  o2 = crack(l)
  o3 = []
  for a in o:
    for b in o2:
      m = merge(a, b, data)
      if m is not None:
        o3.append(m)
  o = o3


fs, gs = o[0]
print(hash('hello'))
print(myhash(fs, gs, 'hello'))

Comments are closed.