1

I'm trying to solve a Crackme challenge. It takes my input password and makes the following operations.

Finally, it compares the output with 0x1928F914

How to reverse this algorithm to get a valid password.

  Result = 0;
  for ( counter = 0; counter < 10; ++counter )
    Result = __ROR4__(Result, 9) ^ *(counter + Passwd);
  return Result;
5
  • The xor calculation may flip some bits multiple times so there is a chance that multiple solutions for a valid password exist. If you have a calculation that has 10 * 6 bits as input (assuming that an ASCII char has about 6 bit of data effectively) and the output value has 32 bit, so you make 60 bit to 32 bits which means that multiple input value may be mapped to your output value.
    – Robert
    Nov 4, 2021 at 20:02
  • If @HKOFBKA@@ works I'll write up a proper answer.
    – Ian Cook
    Nov 4, 2021 at 22:57
  • @Robert Thanks for replying. I quite understand you but I don't know how to get mulitiple input values. I need another hint
    – Raafat
    Nov 5, 2021 at 3:49
  • 1
    If the math behind a problem is too big for you a computer scientist simply switches to try-and-error mode. I would try to just pick a password and try it out. To avoid flipping bits multiple times I would prefer ASCII characters as password that have only one bit set. Then compare the result you get and the result you want on bit level. Try out what happens if you set another bit in the input and thus generate a pattern of how the output changes if you change one bit in input (or to be precise which input bit affects which output bit). If you got this matrix you can reverse the algorithm.
    – Robert
    Nov 5, 2021 at 8:20
  • Thanks a lot for your advice.
    – Raafat
    Nov 6, 2021 at 3:22

1 Answer 1

1

It's not reversible in the sense that you can calculate one single input for the given target number due to loss of information as the rotation will overlap, but you can find inputs resulting in that number.

I like to approach challenges like this by getting a feel for the dependencies of the input and output bits. For this, I typically write scripts that symbolically run the algorithm and print a textual repesentation of what happened.

For the challenge here, I wrote the following Python script:

#!/usr/bin/env python3
def ror9_list(l):
    return l[9:] + l[:9]

def getbit(d,n):
    return (d & (1 << n)) != 0

def gen():
    target = 0x1928F914

    bits = []
    for i in range(32):
        bits.append("0")

    for i in range(10):
        # ror
        bits = ror9_list(bits)
        
        # then xor in new char
        for n in range(8):
            bits[n] += "^ C(%d,%d) " % (i,n)

    for i in range(32):
        print("bit %2d = %-30s must be %d" % (i,bits[i][3:],getbit(target,i)))

gen()

which generates the following text:

bit  0 = C(5,4) ^ C(9,0)                must be 0
bit  1 = C(2,0) ^ C(5,5) ^ C(9,1)       must be 0
bit  2 = C(2,1) ^ C(5,6) ^ C(9,2)       must be 1
bit  3 = C(2,2) ^ C(5,7) ^ C(9,3)       must be 0
bit  4 = C(2,3) ^ C(9,4)                must be 1
bit  5 = C(2,4) ^ C(6,0) ^ C(9,5)       must be 0
bit  6 = C(2,5) ^ C(6,1) ^ C(9,6)       must be 0
bit  7 = C(2,6) ^ C(6,2) ^ C(9,7)       must be 0
bit  8 = C(2,7) ^ C(6,3)                must be 1
bit  9 = C(6,4)                         must be 0
bit 10 = C(3,0) ^ C(6,5)                must be 0
bit 11 = C(3,1) ^ C(6,6)                must be 1
bit 12 = C(3,2) ^ C(6,7)                must be 1
bit 13 = C(3,3)                         must be 1
bit 14 = C(3,4) ^ C(7,0)                must be 1
bit 15 = C(0,0) ^ C(3,5) ^ C(7,1)       must be 1
bit 16 = C(0,1) ^ C(3,6) ^ C(7,2)       must be 0
bit 17 = C(0,2) ^ C(3,7) ^ C(7,3)       must be 0
bit 18 = C(0,3) ^ C(7,4)                must be 0
bit 19 = C(0,4) ^ C(4,0) ^ C(7,5)       must be 1
bit 20 = C(0,5) ^ C(4,1) ^ C(7,6)       must be 0
bit 21 = C(0,6) ^ C(4,2) ^ C(7,7)       must be 1
bit 22 = C(0,7) ^ C(4,3)                must be 0
bit 23 = C(4,4) ^ C(8,0)                must be 0
bit 24 = C(1,0) ^ C(4,5) ^ C(8,1)       must be 1
bit 25 = C(1,1) ^ C(4,6) ^ C(8,2)       must be 0
bit 26 = C(1,2) ^ C(4,7) ^ C(8,3)       must be 0
bit 27 = C(1,3) ^ C(8,4)                must be 1
bit 28 = C(1,4) ^ C(5,0) ^ C(8,5)       must be 1
bit 29 = C(1,5) ^ C(5,1) ^ C(8,6)       must be 0
bit 30 = C(1,6) ^ C(5,2) ^ C(8,7)       must be 0
bit 31 = C(1,7) ^ C(5,3)                must be 0

The script emulates the hashing algorithm for a 10 character long input, where C(x,y) is the bit y of character x both starting at 0.

For example, the last line

bit 31 = C(1,7) ^ C(5,3)                must be 0

says that the 8th bit of the 2nd character xored with the 4th bit of the 6th character has to be 0 in order to match the 32nd bit of the target number, which is 0. So that line tells you (due to the characteristics of xor) that these 2 bits simply must be equal but you're free to pick if both are 0 or 1.

The textual representation thus gives you the necessary constraints for your input characters in order to result in the proper number.

You could choose the correct characters by hand or write your own small program, but this is probably a nice exercise for a constraint solver like Z3.

Just give it the constraints and let the solver figure out a valid input. You may wanna add constraints that the input characters are printable ASCII so you can enter the solution via keyboard.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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