from Hacker News

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

by tgamblin on 4/5/23, 5:47 AM with 2 comments

• by dalke on 4/5/23, 8:48 AM

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

• by yunohn on 4/5/23, 5:51 AM

  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…