-1
$\begingroup$

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
        message.append(c)
        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:]
$\endgroup$

closed as unclear what you're asking by e-sushi, DrLecter, tylo, Seth, archie Dec 2 '14 at 23:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What is the value of digest[0]? $\endgroup$ – Thomas M. DuBuisson 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$ – Thomas M. DuBuisson 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
1
$\begingroup$

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]))]
  where
  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.

$\endgroup$
  • $\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$ – Thomas M. DuBuisson 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.