Hey all,
I'm working on this problem to reverse a hash. I've got a solution, but I think it's a bit of a hack and I'd like to see what I'm missing. This is a (broken) hash function that accepts a 16-byte input (16 integers in range(256)). A value of zero is assumed for hash[0] (message[-1] = 0).
Hash function is:
hash[i] = ((129 * message[i]) XOR message[i-1]) % 256
def hashme(message):
return [(((129 * m) ^ (0 if i is 0 else message[i-1]))%256) for (i, m) in enumerate(message)]
def _gcd(a,b):
while b:
a, b = b, a % b
return abs(a)
def unhashme(digest):
msg = [0] * len(digest)
lastbyte = 0
for (i, ch) in enumerate(digest):
newchar = (ch ^ (lastbyte * 129))
if _gcd(ch, 256) is 1:
newbyte += 128
newbyte = newbyte % 256
msg[i] = newbyte
lastbyte = newbyte
return msg
The above 'unhashme' function works, but it feels inelegant. When run without the GCD calculation (and thus not offsetting the value by m/2 = 128), every other element seems to reverse correctly, but the others are off by 128. Multiplying by 19 will reverse the multiplication by 129 (modulo 256), but I'm not sure how/where to work it in. I feel like adding 128 here-and-there is hacky, or at best, missing the underlying intent. I'm going in circles between rings, cyclic groups, multiplicitive inverses, etc.
Can anyone explain what I'm missing, or give me a direction to search?
Input: 0,129,5,141,25,137,61,149,113,145,53,157,233,185,109,165
-------------------------------------------------------------------
No GCD: 0,129,4,137,16,153,36,177,64,209,100,249,144,41,196,97
-------------------------------------------------------------------
Expected: 0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225
Test data:
test1_input = [0, 129, 3, 129, 7, 129, 3, 129, 15, 129, 3, 129, 7, 129, 3, 129]
test1_output = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
test2_input = [0, 129, 5, 141, 25, 137, 61, 149, 113, 145, 53, 157, 233, 185, 109, 165]
test2_output = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225]
