10 ms·

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

2 points by tgamblin 4y ago

yunohn 4y ago
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…
dalke 4y ago
(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 https://en.wikipedia.org/wiki/FitNesse and http://fitnesse.org/ http://fitnesse.org/ , uses its own hash function, at https://github.com/unclebob/fitnesse/blob/master/src/fitnesse/authentication/HashingCipher.java 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.PasswordFile 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.

2 points by tgamblin 4y ago

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…

dalke 4y ago

(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 https://en.wikipedia.org/wiki/FitNesse and http://fitnesse.org/ http://fitnesse.org/ , uses its own hash function, at https://github.com/unclebob/fitnesse/blob/master/src/fitnesse/authentication/HashingCipher.java 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.PasswordFile 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.