Is there a feasible preimage attack for any hash function today?

(I notified Martin and the FitNesse user mailing list about this back in 2010. I assume their threat model is that the default hash function is about the same as a closed office door - a request to stay out, or at least knock first - rather than a strong preventative measure.)

In this comment I'll demonstrate that 1) there is a hash function, 2) in use, 3) with a successful preimage attack.

"Uncle" Bob Martin's "FitNesse", see https://en.wikipedia.org/wiki/FitNesse and http://fitnesse.org/ , uses its own hash function, at https://github.com/unclebob/fitnesse/blob/master/src/fitness... .

The Python equivalent is:

    import base64

    repetitions = 3
    lock_bytes = b"Like a long-leggedfly upon the stream\nHis mind moves upon silence."

    def encrypt(value):
      result = [0] * 15
      for i, byte in enumerate(lock_bytes):
          result[i%15] += (byte + repetitions*ord(value[i%len(value)]))
      s = bytes([(i % 256) for i in result])
      return base64.b64encode(s)

Here's an example:

  >>> encrypt("Swordfish")
  b'YW5a6EcE5U6LOQbfTb+M'
  >>> encrypt("Too many secrets")
  b'2fNpXgkyNCrUJArsdIat'

This is a very weak hash function. With a bit of tweaking the above function is:

    init_result = [0] * 15
    for i, byte in enumerate(lock_bytes):
        init_result[i%15] += byte
    init_result = [value % 256 for value in init_result]
    # init_result = [163, 198, 30, 15, 204, 206, 32, 11, 156, 182, 183, 219, 109, 169, 163]

    def encrypt(value):
        N = len(value)
        result = [None] * 15
        for b in range(15):
            result[b] = (init_result[b] + (3 * sum(ord(value[i%N]) for i in range(b, 66, 15)))) % 256
        return base64.b64encode(bytes(result))

where the lock_bytes is not used during the encoding.

To simplify preimage construction, the generated preimage will have 66 bytes, matching len(lock_bytes). We need to find values for positions 0, 15, 30, 45, and 60 such that their value, plus the initial value for hash[0], adds up to the expected value for hash[0], and so on. One such solution is:

    import itertools
    def get_preimage(expected):
        result = base64.b64decode(expected)
        assert len(result) == 15, result
        input_bytes = bytearray(b"A" * 66) # start with all 'A's
        for b, needed_value in enumerate(result):
            offsets = list(range(b, 66, 15))
            needed_value = (needed_value - init_result[b] + 256) % 256

            # Adjust the characters one-by-one until finding a match.
            # This works because 3 and 256 are relatively prime, finding
            # a solution within 256 update attempts.
            # (There's probably a more elegant solution.)
            positions = range(b, 66, 15)
            for change_pos in itertools.cycle(positions):
                value = (3*sum(input_bytes[pos] for pos in positions)) % 256
                if value == needed_value:
                    break
                input_bytes[change_pos] += 1

        return "".join(map(chr, input_bytes))

To demonstrate:

  >>> h = encrypt("Swordfish")
  >>> h
  b'YW5a6EcE5U6LOQbfTb+M'
  >>> s = get_preimage(h)
  >>> s
  'brkdojfqjarkhmibrkdojfpi`qkhmibrjdojfpi`qkhlibqjdnjepi`qkhlhbqjcnj'
  >>> encrypt(s)
  b'YW5a6EcE5U6LOQbfTb+M'
  >>> encrypt(s) == h
  True

For example, the documentation at http://fitnesse.org/FitNesse.UserGuide.AdministeringFitNesse... shows how to generate password hashes. I'll follow those steps:

  % env CLASSPATH=fitnesse-standalone.jar java fitnesse.authentication.Password Leonardo
  Be advised, the password will be visible as it is typed.
  enter password for Leonardo: katana
  confirm password: katana
  password saved in passwords.txt
   % cat passwords.txt
  !fitnesse.authentication.HashingCipher
  Leonardo:rMN4+vDv6OWafpHZNYOh

(The documentation says "katana" hashes to "VEN4CfBvGCSafZDZNIKh", which is incorrect.)

I'll now use the above Python code to verify that it matches the FitNesse hash, and that it generates a successful preimage:

  >>> encrypt("katana")
  b'rMN4+vDv6OWafpHZNYOh'
  >>> get_preimage(b"rMN4+vDv6OWafpHZNYOh")
  'ggmeiifhkfhkfhkgfmeiifhkfhkfhkgfleiifgjfgjfgjgfleihfgjfgjfgjgflehh'
  >>> encrypt("ggmeiifhkfhkfhkgfmeiifhkfhkfhkgfleiifgjfgjfgjgfleihfgjfgjfgjgflehh")
  b'rMN4+vDv6OWafpHZNYOh'

Remember, leave cryptographic hashing to the experts. ;)

It was even worse back in 2010 because the FitNesse web server allowed a path traversal attack, making it possible to request "../passwords.txt" and get the default password file for the server. This has since been fixed.

Question:

> Is there a feasible preimage attack for any hash function?

Answer:

> Yes, certainly

> memory requirements make it impractical

I’d like to think feasible != impractical…