Hi,

I'm trying to reverse an algorithm and find a valid input for it. Here is a quick explanation of the algorithms internals:

1. It accepts input of 12 (or more) groups of 4 digits or letters e.g. 1234-5678-90AB-CDEF-HIJK-LMNO-1234-5678-90AB-CDEF-HIJK-LMNO
-It also checks if all the elements in the input are digits or letters

2. The input is converted into an int[] by stripping the "-" and then taking the char values.
-If the char is a digit it will add 0x19
-If the char is not a digit it will subtract 0x41

3. The int[] is then passed into a method which does array[I] = array[I] xor array[i-1]
-This is done starting from the end of the array
-Passing in [1,2,3,4,5,6,7,8,9] is converted to [1,3,1,7,1,3,1,15,1]

4. The xored int[] is then passed into a method that will drop the 3 higher order bits of each int and spread the remaining bits (only the 1s) into a boolean array.
-A binary value looking like 10100111
-Will become 00111 and then the 1 bits will be stored in a bit array (the locations are not in order, they're calculated)
-The initially entered input of 12 groups with 4 digits/letters each is now stored in a bit[240] (48*5 == 240 as 3 bits for each byte have been dropped)

5. The result bit[240] is then processed in a loop that takes 5 bits from the array and reverses their order. The lower bits are turned into the higher ones.
- 10110 would become 01101
- The method returns a byte array converting 5 values of the reversed bit array at a time. When taking the 5 bit groups this leaves me to basically fill up the remaining 3 bits with dummy values (this could be part of my problem)

6. The values in the byte[] are then xored against an array of values

7. This is the final stage where the result of the previous operations is taken apart to check several values.


I have reversed the above process starting from the values I would like to see going back through all the steps to retrieve the correct input to satisfy the algorithm. My problem is now that I can't get past the first check for letters and numbers as my supposedly valid input does not satisfy the check for all characters being digits/letters (it more looks like a random ASCII string).

Skipping the input check and passing my values through the algorithm I see the expected behavior as my input passes all checks.

My question is now, is there any chance for me to generate a valid input by reversing the process above? How would I best go about satisfying the digit/letter check as I can't seem predict what the bytes will turn into after the xoring/bit manipulation.

Thanks
b3n

xor operations are your problem, but I think that the weakness of the algo is on this operation:
array[I] = array[I] xor array[i-1] when 'i' is '0' (array[0] = array[0])

Thanks Zairon,

but does that help me in finding a valid input though? I can't see how having the first byte not xored makes a difference to me determining a valid input containing only numbers and letters.

step_3:
array[0] = modified_array[0]
check if array[0] is a candidate digit or letter
if "array[0] is right" then array[1] = array[0] XOR modified_array[1]
check if array[1] is a candidate digit or letter
and so on...

I took a slightly different approach. Instead of trying to figure out what values would give me a valid input, I'm bruteforcing it now. I keep repeating the algorithm while trying different combinations for the 3 padding bits until the result only contains digits/letters. Takes a few seconds but hasn't failed yet.

If your skipping the input check allows your reversed key to pass the rest of the checks it would suggest that your problem is probably with converting the values after reversing step 3 to valid characters in step 2.

Before dealing with this it is worth checking step 5 as this could be causing problems later on. You mention having to add 3 bits of dummy values to convert your 5 bits to bytes, setting these to 000 will make reversing step 2 easier. These could be set to anything as they are thrown away in step 4 and the xor in step 3 means they do not effect the lower 5 bits, but setting them to 000 means you don't have to do anything to remove them in step 2.

Now for step 2. At this point all your values should be between 00000000 and 00011111 in binary or 0x00 and 0x1F. From here it should be easy to map these to the ASCII characters required to give you these values in step 2, however some of the larger values still appear to map to none letter values.

Hopefully i'm not repeating anything you've already figured out yourself.

hfm

You can ignore the upper 3 bits in all of your calculations. The XOR operation is bitwise, so the lower 5 bits won't interfere with the upper 3. Your post is a bit low on details but this it how it looks form here.

You start with a random bit[240] array, do the bit-reversing step from 5, calculate the indexes of step 4 to move the bits into the int array and do the XOR.



XXX and YYY are just random values (you can set them to zero). The lower 5 bits can be seen as integers in 0..31. The operation in step 2 maps '0'-'9' and 'A'-'Z' into 0..36 and throws away the upper 3 bits, turning them into numbers in 0..31 (truncating to 5 bits is the same as mod 32). To reverse this just fill the XXX and YYY so that the result is less than 37 and map them back (adding 0x19 or 0x41). That's why just using zeros for XXX and YYY should do the trick.



You didn't elaborate on the values of step 6 and the checks in 7. Keep in mind that your random array has to pass those.