I'm trying to get a better understanding of cryptographic hashing. Take the example transformation function below, is it possible to reverse this formula to solve/isolate for message[i]?

digest [i] = ((129 * message[i]) XOR message[i-1]) % 256

Here is my attempt in python. I Assume both digest and message are 16 bytes in length. It should return the message used to create the digest but is not working. I don't think my operations (a,b,c) are sound.

def answer(digest):
    message = [0] 
    for i,x in enumerate(digest):
        a = digest[i] * 129
        b = a ^ message[i]
        c = b % 256
        print "%d * 129 \t->\t %d ^ %d  \t->\t %d MOD 256 \t->\t %d " % (digest[i], a, message[i], b, c) 

    return message[1:]
  • $\begingroup$ What is the value of digest[0]? $\endgroup$ Dec 2 '14 at 5:48
  • $\begingroup$ Oh, and why do you think your python code should work? Are you under the impression 129 is multiplicative inverse for 129? Don't you think the order of xor and multiply should be reversed if you're trying to invert the digest? $\endgroup$ Dec 2 '14 at 6:14
  • $\begingroup$ This comment was also very helpful. The correct operations to solve for message [i] is the following order of operations: digest[i] ^ message[i-1] * 129 % 256 $\endgroup$
    – Vaughn
    Dec 3 '14 at 2:24

Your bad hash computes each byte of digest from only two bytes of message, resulting in very few small equations which can be solved by many automated tools.

I've made the assumption that digest[0] = (129*msg[0]) XOR msg[15]. Expressing this hash in Cryptol we get:

badHash : [16][8] -> [16][8]
badHash msg = [ x ^ y | x <- mul | y <- (msg @@ ([15]#[0..14] : [_][8]))]
  mul = [ m * 129 | m <-  msg ]

Now we can use Cryptol to leverage modern SMT solvers and find your message. However, there are many collisions with this hash function so to get a particular pre-image we need to solve for all satisfying solutions or know at least some of the pre-image of interest.

For example, say we have the hash for [255,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]:

Main> let x = badHash [255,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
Main> x
[0x71, 0xff, 0x81, 0x03, 0x81, 0x07, 0x81, 0x03, 0x81, 0x0f, 0x81,
 0x03, 0x81, 0x07, 0x81, 0x03]

We can feed the digest into an SMT (in this case CVC4):

Main> :sat \msg -> badHash msg == x
(\msg -> badHash msg == x) [0xf2, 0x8d, 0x0c, 0x8f, 0x0e, 0x89,
                            0x08, 0x8b, 0x0a, 0x85, 0x04, 0x87, 0x06, 0x81, 0x00, 0x83]
                                = True

And we could look for pre-images that start with the value 255:

Main> :sat \msg -> badHash msg == x && msg@0 == 255
(\msg -> badHash msg == x && msg @ 0 == 255) [0xff, 0x00, 0x01
                                             ,0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09
                                             ,0x0a, 0x0b, 0x0c, 0x0d, 0x0e] = True

Easy as the press of a button.

  • $\begingroup$ It helps to notice that when working on bytes, multiplication by 129 is always exactly undone by a further multiplication by 19, because $19\cdot129\equiv1\pmod{256}$ $\endgroup$
    – fgrieu
    Dec 2 '14 at 7:23
  • $\begingroup$ @fgrieu did you mean to comment on the question? This is somewhat unrelated to the answer. $\endgroup$ Dec 2 '14 at 7:28
  • 1
    $\begingroup$ I added this in hope that it could help simplify the answer. In particular, msg[i+1] is (digest[i+1] XOR msg[i])*19 MOD 256 or something on that tune. I do realize that it makes use of an SMT solver less useful. $\endgroup$
    – fgrieu
    Dec 2 '14 at 8:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.