PDA

View Full Version : Black box algorithm with some known good keys

Osiris
October 24th, 2007, 23:52
I've been working on this for about 1.5 weeks and have been stuck and getting nowhere for the last 5 days so I'm posting in hopes that someone will have a hint or maybe I'm a total newb and am overlooking something.

The software in question is uses a USB interface (the black box) to communicate with embedded systems. To use the program, a 35 character alphanumeric key is entered which tells the interface which devices it will allow communication with. This key is independant of the key which was previously in use (all required information is contained in a single key). When the key is changed, only functionality related to that single key can be used.

My objective is to determine what data these keys contain and be able to create my own.

What I've done so far:
The software does a preliminary verification on the key before sending it to the black box.
- Each character has 32 possible values
- These characters translate to a 5-bit number equivalent by lookup table
- I have recreated the lookup table, I will present keys in number form only
- The data is then XOR-encrypted with a 5-bit value, each bit is taken from a different location within the key
- If the XOR value is even, the first 4 characters must be an even value, the 5th char must be odd. The opposite is true for an odd XOR value.
- Interface serial IDs are stored as 4-6 bit decimal strings (e.g. 123 = 01 02 03), the bits are spread out among the characters
- There is a 16-bit checksum of the key, again the bits are separated and stored in different characters
- The checksum calculation algorithm is sum(char[n]) * 0x3B, interestingly it masks out the bits that contain the checksum AND another 16 bits
- I believe the unidentified 16 bits form another WORD value, possibly another checksum? When the bits are sequenced in the same order as the checksum bits, I get a value that is always a multiple of 0xFF. If it is indeed a checksum, I have no clue how to get the algorithm. My guesses haven't gotten anywhere.

So in total:
- There are 175 data bits
- I've identified 107
- There is another suspicious group of 16 that is possible a checksum
- 52 bits remaining to be ID'd

I believe the remaining bits contain 2-4 numbers, say n1 to n4. Possible values range from 0-999+. Values could represented as 4-bits or a min. 3-char, 4-bit string of the number, example from above: 123 = 01 02 03

Now, if I still make sense after all that, I have 3 valid keys that work with the hardware. I also made my own keys that pass the software check, but fail the black box check.

So here they are in number form, with corresponding known n values, and sum values (sum2 is the unknown algorithm)
Code:


n1 = 8, n2 = 0, sum1 = 3629, sum2 = 12ED { 06 06 16 16 07   1E 1C 04 07 0E   06 17 0C 0A 06   0A 04 06 0C 04   06 14 15 13 07   0A 12 04 0F 0A   07 0E 01 0C 0D }

n1 = 9, n2 = 0, sum1 = 36DA, sum2 = EF1 { 0E 06 1C 1E 0F   1E 15 0D 0C 07   0E 1E 05 0B 0B   01 0C 0F 05 0B   0F 1C 1F 03 08   03 1B 0D 06 03   0A 0B 09 07 04 }

n1 = 10, n2 = 0, sum1 = 3750, sum2 = CF3 { 06 06 14 06 07   1E 1C 14 05 0E   06 17 04 00 04   08 14 0F 04 06   06 11 17 0B 01   02 16 04 0F 0A   03 06 00 0A 0D }


These are the bit sequences for known data (my notation is char.bit, zero-based hex, bit 0 = LSB):
Code:


XORVal = 10.0, 12.0, 16.0, 19.0  // For n1 = 8 key, XORVal = 0110 = 6



// These values are constant

IDString1[0] = 0.3, 1.4, 1.1, 2.4 

IDString1[1] = 2.2, 3.3, 3.1, 4.4 

IDString1[2] = 4.1, 5.4, 5.0, 6.3 

IDString1[3] = 7.3, 8.3, 9.1, A.3 

IDString1[4] = B.1, C.1, D.0, E.3 

IDString1[5] = F.3, 10.2, 11.1, 12.1 

IDString1[6] = 13.4, 14.3, 15.1, 16.2 

IDString1[7] = 17.1, 18.0, 19.2, 1A.4 

IDString1[8] = 1B.0, 1C.4, 1D.3, 1E.1 

IDString1[9] = 1F.1, 20.2, 21.0, 22.3 



// 6-bit chars for IDString2

IDString2[0] = 2.3, 4.2, 5.1, 6.4, 6.0, 7.2

IDString2[1] = 7.0, 7.2, 7.0, 9.4, A.1, B.1

IDString2[2] = C.2, D.4, E.4, F.4, 10.1, 11.2

IDString2[3] = 12.4, 13.0, 14.2, 15.4, 16.4, 17.2

IDString2[4] = 18.4, 19.1, 1A.0, 1B.3, 1C.0, 1D.4

IDString2[5] = 1E.3, 1F.4, 20.3, 21.3, 22.4, 22.0



// Some other 5-bit ID number, must = 3 to pass software check

nID = 18.3, 1B.3, 1D.0, 1E.0, 20.1



// 16-bit Checksum, = sum of bytes * 0x3B, doesn't sum nChkSum2 bits

nChkSum1 = 3.2, 5.2, 7.1, 9.3, A.3, D.2, F.2, 11.3, 13.2, 15.0, 17.4, 18.1, 1A.2, 1C.1, 1F.2, 21.1



// Unknown 16-bit value, possibly a checksum

nChkSum2 = 13.3, 14.1, 15.3, 16.1, 17.3, 18.2, 19.3, 1A.3, 1B.1, 1C.3, 1D.2, 1E.2, 1F.3, 20.0, 21.2, 22.1


And lastly, the remaining bit values which I have not identified (all sequenced together in binary format):
Code:


for key n1 = 8  { 0000 0010 1010 0000 0001 0010 1000 0000 0001 0100 0000 0000 0000 }

for key n1 = 9  { 0001 0110 0010 0100 0011 0010 0010 0010 0001 0000 0000 0000 0000 }

for key n1 = 10 { 0000 0100 1011 0100 0001 0000 0101 0101 0010 0000 1000 0000 0000 }


I've tried a few operations (xor, and, or) to compare the 3 sets of unknown bits but no patterns have shown up that are apparent to me. I can't bruteforce because the USB must be unplugged/replugged to try a new key.

Any ideas?
dELTA
October 25th, 2007, 02:10
This kind of situation is often very problematic, and especially with the extremely limited brute-force possibilities you describe.

Even if the entire problem would be the "possible 16-bit checksum" that you have already guessed is there, this would be enough to create a formidable obstacle under these circumstances. Not to mention if they were smart enough to put even more "device-side checks" of this kind in there.

If you'd still want to pursuit this, disregarding the odds, the best strategy I can think of (except for hardware hacking based strategies) would be to bet on the laziness of the designers, thus hope that 1) This 16-bit checksum is the only remaining obstacle, and 2) They have made the algorithm for it somewhat similar to the algorithm of the other checksum, possibly varying the input data and possibly also just somewhat the algorithm.

Based on this, I'd try to "brute-force the algorithm" of the second checksum on the computer-side (i.e. bypassing the limited brute-force possibilities of the device itself, until you have a few candidates to check), based on the valid keys you already have. I.e., start with as similar algorithms as possible to the first one, varying the input data as completely as possible, and then modify the algorithm more and more. Be warned though, that the time complexity of such a feat explodes to intractable proportions quite quickly.
janus68
October 25th, 2007, 13:41
Hi,
Not sure,but everything that seem to be very close to usb raw data protocol,i.e 5 bit data unit, checksumming and so forth.There are involved NRZI and bit stuffing algorithms,5 and 16 bit crc with reversed bit order.Check atmel appnote AVR309 for more info.
Osiris
October 26th, 2007, 02:41
Well, I think I've confirmed that the mystery checksum is the only remaining obstacle.

Along the lines of your post, dELTA, I was able to bruteforce 4 new keys out of the thing. I set the unknown bits to a constant value and varied the mystery checksum in increments of 0xFF. So every set of data I've tried so far has a single checksum that will work. Strangely, all new keys had n1 = 3, n2 = 0.

Here's the data I tried which worked, I only changed one bit each time
Code:


n1 = 3, sum = 45BA  { 0001011010010100001000101111010100110100100000000000 }

n1 = 3, sum = 4AB5  { 0001011010010100001000101111010100110100000000000000 }

n1 = 3, sum = 3FC0  { 0001011010010100001000101111010100110000000000000000 }

n1 = 3, sum = 2BD4  { 0001011010010100001000101111010100100000000000000000 }


The bruteforce method is slow, but enough to get somewhere! I am able to try all checksums for a dataset in one hour. Maybe I can write a small program to try different multipliers and offsets on the dataset and see which creates a matching checksum for all 7 keys so far.

I had a look at AVR309 but maybe it isn't as revelant because they are using an FTDI chip to simulate the USB interface. Then they just use COM port-style functions in the software. I checked the EEPROM user data on the chip but it was blank.
Osiris
October 26th, 2007, 05:01
It's over. I got it, or almost. My objective is accomplished, but there is one loose end.

The algorithm appears to be this:
Code:


Checksum 2 = (sum of all byte inc. 1st CRC) & 0xFF * 0xFF


However, occasionally the calculated value is 0xFF too low (basically, off by one). I haven't figured out why yet, but the black box accepts keys generated by this method with a high success rate. If the first key doesn't work, I just add 0xFF and its good to go. I'm now able to go through and change each bit to see the result.
dELTA
October 26th, 2007, 12:48
Cool, I'm glad my idea helped.
LLXX
October 27th, 2007, 01:15
Quote:
[Originally Posted by Osiris;69820]However, occasionally the calculated value is 0xFF too low (basically, off by one). I haven't figured out why yet, but the black box accepts keys generated by this method with a high success rate. If the first key doesn't work, I just add 0xFF and its good to go. I'm now able to go through and change each bit to see the result.
You're propagating a carry somewhere in the algorithm that should not have been propagated.
abuse007
October 27th, 2007, 23:28
Quote:
[Originally Posted by Osiris;69793]
I've tried a few operations (xor, and, or) to compare the 3 sets of unknown bits but no patterns have shown up that are apparent to me. I can't bruteforce because the USB must be unplugged/replugged to try a new key.

Any ideas?


I know you have pretty much cracked the algorithim however I had this thought.

Would it be possible to shutdown (power-off) the USB port via sofware somehow and then start-up (power-on) the USB port, instead of unplugging and plugging back in the USB device?

This might then allow an automated method to brute-force keys without requiring manual intervention. Although it might be fairly slow due to the overhead of powering off and on the USB port.

Again not sure if its possible, but just a thought.