b3n_

December 10th, 2012, 08:27

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

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