0

I have the sha256 hash for Hello World! which is 7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069 and I want to use this hash with the reverse input which is !dlroW olleH to get to the initial state of the hash (ie. when the input is empty; that is, the hash of the empty input) which is apparently the hash of no bytes(ie. when the input is 0 bytes) which is this: e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855.

In other words: I want to go backwards from the final hash, by feeding it the reversed input bytes and get the initial state of the hash before the normal(non-reversed) input was fed to it.

Here's what I mean in code:

#!/usr/bin/python3

import hashlib

#This is what currently exists:
m = hashlib.sha256()
print(m.hexdigest())  #e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
m.update(b"Hello ")
m.update(b"World!")
print(m.hexdigest())  #7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069

m2 = hashlib.sha256()
m2.update(b"Hello World!")
print(m2.hexdigest()) #7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069

assert m.hexdigest() == m2.hexdigest()


#Looking for something like this:
r = hashlib.sha256rev("7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069")
r.update(b"!dlroW")
r.update(b" olleH")
print(r.hexdigest())  #e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

r2 = hashlib.sha256rev("7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069")
r2.update(b"!dlroW olleH")
print(r2.hexdigest()) #e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

assert r.hexdigest() == r2.hexdigest()

Note that the input has to be reversed. So I'm not looking to feed it the same input, but the reversed input.
So it does the hashing in reverse order, somehow, at the implementation level. I don't know how it does it already though.

So maybe there's already a function to do this? (seems unlikely though)
If not, say whether or not it can be done?
If it can be done, maybe give some hints if not the actual code that does it?
otherwise, by at least knowing it can be done, I should be able to figure out how to do it by looking at the python source code ... and then I'll add my own answer with the code.

Why do I need this ?
I want to check that a singly-linked list of values between [0..9] is a palindrome in O(1) space complexity (and O(n) time) without modifying the linked list(!) but rather just by hashing the first half of it(minus the element in the middle, if any) and then reverse-hashing(or how would you call this? subtract-hashing?), from the first hash, the second half of the linked list to see if I get that e3b0...55 hash which would mean it is a palindrome. It's this question here: https://leetcode.com/problems/palindrome-linked-list/

correabuscar
  • 33
  • 3
  • 2
    Why don't you just reverse the second half of the list and just see if it's equal to the first? This is trivial in Python. – Dennis Williamson Sep 20 '22 at 13:40
  • @DennisWilliamson That's how most(if not all?) are doing it, but I want to assume that the linked list is read only. – correabuscar Sep 20 '22 at 13:48
  • 1
    There's no change to the list necessary. – Dennis Williamson Sep 20 '22 at 13:54
  • @DennisWilliamson but doesn't that change the space complexity from O(1) to O(n) though? because if you don't change the input single-linked list, you'd need to store its reversed second half somewhere. – correabuscar Sep 20 '22 at 20:13
  • @DennisWilliamson oh I think I see the solution that you had in mind,that satisfies my two conditions: 1. to not modify the input list, 2. to be O(1) space complexity. But honestly it feels like a trick because the algorithm depends on knowing that the linked list can contain a maximum of X number of elements, where X is 10^5 in this case. Thus if the algorithm always allocates 10^5/2 ie. 50k bytes to store each element(aka digit ~ [0..9]) of the reversed second half of the linked list, it's still considered O(1), right? and it doesn't risk being wrong due to sha256 hash collisions. Thank you! – correabuscar Sep 20 '22 at 21:45
  • Secure hashes (including sha256) don't work that way, there's no such that as "going backwards" by hashing the input bytes in the reverse order. Hashing the bytes in the reverse order gives a completely different, unrelated hash output. – President James K. Polk Sep 20 '22 at 21:57
  • I envision using slices, which are very powerful in Python, for this comparison, but there is [additional memory allocated](https://stackoverflow.com/a/5131563/26428) for the references to the list items. – Dennis Williamson Sep 21 '22 at 00:03

0 Answers0