Skip to content

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

Comments

(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.

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.