Topic created on: April 14, 2007 02:59 CDT by bushing  .
I'm trying to reverse-engineer the firmware files loaded onto my AVIC car GPS unit; my goal is to eventually be able to modify the code on the unit, but I'd settle for being able to edit the strings file. I can't seem to generate a valid checksum for the files.
The file format used has been easy enough to decode -- both code and data files use the same format with a 64-byte header, and the last 16 bits of each file appear to be a checksum. (The gruesome details are in this forum post, if anyone's interested... it seems like I went a bit beyond the scope of that board, but oh well). I was also able to determine that the header isn't included in the checksum.
Here's what I have to work with:
* Several files with valid checksums.
* An "oracle" -- I can burn a DVDRW and use a service menu to force the unit to reflash using my modified files, but if the checksum fails, when it next starts it demands that I insert a DVD with a valid firmware image so that it can reflash. So, it's not possible to automatically test for checksum collisions.
* The binary which contains the code that checks this firmware; I have about 400k of program data for the unit's NEC V830 microcontroller, and the fact that the failure messages are embedded tells me I should be able to figure it out by analyzing this file. However, this is an obscure processor for which no good disassemblers exist; I have a partially-working IDA processor module, but it doesn't work well enough to figure out what code references what strings.
All that I've been able to do is try common 16-bit checksum algorithms on the data between the end of header and the checksum on some of the files, hoping that something will match. I've tried:
* Summing each byte into a 16-bit variable, both big and little-endian
* Summing each halfword, both big and little-endian
* The above, using XOR instead of addition
* 16 bit CRC (CRC-16-CCITT, CRC-16-IBM)
* 1's complement of all of the above.
Nothing has matched. Can anyone suggest a better approach? (16-bit checksum algorithms don't seem to lend themselves to obvious magic lookup tables...)
did you check if it is maybe 2 bytes of a hash function ( md5, sha1, sha256, ... )?
or 2 bytes of a crc32? or 2 bytes of a 32bit sum?
did you also calculate the checksum/crc including your checksum byte, maybe the total result is a constant value?
maybe something like the ppp frame checksum, which is a crc16 with polynomial 0x8408, where the frame crc always is supposed to be 0xf0b8
or maybe one byte is the sum of the odd bytes, the other the sum of the even bytes?
|
I apologize upfront for not being familiar with the NEC V820 microcontroller.
Checks in firmware are always an interesting adventure. There are several problems, that you generally run into:
1) Which algorithm? (This is of course the captain obvious one you have already done an excellent job of commenting!)
2) Where is the checksum _actually starting_ its' calculation from? You mentioned the header was not included in the checksum, but I have seen instances where there the actual files checksumming did not begin until well after the header file - I was only assuming this was for some kind of future expansion or patching facility in these instances.
3) Is it really a 16bit checksum or simply a larger checksum that was truncated?
These are only a handful of course. My next question would be does the device have JTAG exposed? If so, you might be able to perform some kind of debugging on the unit.
|
> itsme: did you check if it is maybe 2 bytes of a hash function ( md5, sha1, sha256, ... )?
>or 2 bytes of a crc32? or 2 bytes of a 32bit sum?
I don't *think it's a complicated hash function, because I ran Ilfak's findcrypt2 plugin on it and it didn't find any magic constants. Still, it's a possibility. I'll update my little test program to generate those sums and print them out.
>did you also calculate the checksum/crc including your checksum byte, maybe the total result is a constant value?
Hmm... ok, I'll add that too
>maybe something like the ppp frame checksum, which is a crc16 with polynomial 0x8408, where the frame crc always is supposed to be 0xf0b8
I've been afraid it might be something like that -- how would I find the polynomial if I can't find the crc routine in the firmware? Then again, if there are only 2^16 different polynomials, I could always brute-force it and try them all. (I have several files with the same kind of checksum, so I can make sure it matches all files.)
>or maybe one byte is the sum of the odd bytes, the other the sum of the even bytes?
If it's a simple sum (and not a checksum), I should be able to swap bytes (or halfwords?) and not make the checksum fail, so I will try that, too.
> aeppert: I apologize upfront for not being familiar with the NEC V820 microcontroller.
>
> Checks in firmware are always an interesting adventure. There are several problems, that you generally run into:
>
> 1) Which algorithm? (This is of course the captain obvious one you have already done an excellent job of commenting!)
>
> 2) Where is the checksum _actually starting_ its\' calculation from? You mentioned the header was not included in the checksum, but I have seen instances where there the actual files checksumming did not begin until well after the header file - I was only assuming this was for some kind of future expansion or patching facility in these instances.
I changed some bytes in the header and verified that it still loaded, but I didn't try more than that. I'll try changing some of the bytes immediately after the header to see if that causes a failure.
>
> 3) Is it really a 16bit checksum or simply a larger checksum that was truncated?
No clue. I had looked at some 32bit cksums and didn't see anything, then I somehow decided that the V820 was a 16-bit processor, and so probably wouldn't be doing a full checksum. (You'd think that the 32-bit opcodes would have clued me in there ... I'll go back and look again at the 32-bit numbers.)
> These are only a handful of course. My next question would be does the device have JTAG exposed? If so, you might be able to perform some kind of debugging on the unit.
That's a different idea entirely! There's a connector, but you have to take apart the unit to reach it; it would probably be easier / better for me to fix my IDA module to correctly calculate memory references so I could find the routines.
Thanks for all of the great ideas -- that's why I came here :) I'll post my IDA module in case it helps anyone.
|
Here's another "different" (but obvious) idea: You mentioned that there was an error message on the next bootup. Is this message in the firmware? I would think it likely that some sort of boot loader in Flash is generating this error, but it's worth a look.
On a related note, if there is a mechanism to update the boot loader (and you have such a file), reversing that code would give you the answer. I found some cases where the checksum routine was carried in a boot loader as well as in the main firmware, but unless there are strings it is a needle-in-the-haystack type of problem.
There was an interesting discussion spawned from a cracker about finding such "atypical" code (in that case serial number generation routines, in this case, a checksum routine). Some sort of histogram of opcodes to detect routines with an abnormal concentration of shifts and other bitwise math might help... I don't know of anything like this publicly available, but it seems like a good idea.
|
Okay, I ended up deciding that the best use of my time would be to work on my V830 module... and I think, at last, I found the checksumming code.
I'm still trying to work through the specifics of this, but does this algorithm (or more likely, the lookup table) look familiar to anyone?
(Pardon the wonky disassembly, this is my first try at writing a processor module.)
checksum_func:
ld.w r11, 0(r6) ; r11 = buf?
ld.w r12, 4(r6) ; r12 = len?
cmp r12, 0 ; is len <= 0?
ble return_error
mov r13, #FFFFFFFFh
shr r13, #8
movea r14, lookup_table
br loc_40AE9C
loop:
mov r15, r13
shr r15, #8 ; r15 = r13 >> 8
ld.b r16, 0(r11) ; r16 = *buf
add r11, #1 ; buf++
xor r16, r13 ; *buf ^= r13
andi r16, #FFh ; *buf &= 0xFF
shl r16, #1 ; *buf << 1
add r14, r16
ld.h r17, 0(r16) ; r17 = lookup_table [((*buf ^ r13) & 0xFF))]
xor r17, r15
andi r13, r17, #FFFFh
loc_40AE9C:
add r12, -1 ; len--
cmp r12, 0
bge loop
xori r13, #FFFFh ; r13 ^= 0x0000FFFF
st.h 0(r7), r13 ; *r7 holds checksum?
mov r10, 0 ; r10 = 0 -> success?
ret
return_error:
mov r10, #D00Ah
ret
lookup_table:
.word 0000h, 1189h, 2312h, 329Bh, 4624h, 57ADh, 6536h, 74BFh
.word 8C48h, 9DC1h, AF5Ah, BED3h, CA6Ch, DBE5h, E97Eh, F8F7h
.word 1081h, 0108h, 3393h, 221Ah, 56A5h, 472Ch, 75B7h, 643Eh
.word 9CC9h, 8D40h, BFDBh, AE52h, DAEDh, CB64h, F9FFh, E876h
.word 2102h, 308Bh, 0210h, 1399h, 6726h, 76AFh, 4434h, 55BDh
.word AD4Ah, BCC3h, 8E58h, 9FD1h, EB6Eh, FAE7h, C87Ch, D9F5h
.word 3183h, 200Ah, 1291h, 0318h, 77A7h, 662Eh, 54B5h, 453Ch
.word BDCBh, AC42h, 9ED9h, 8F50h, FBEFh, EA66h, D8FDh, C974h
.word 4204h, 538Dh, 6116h, 709Fh, 0420h, 15A9h, 2732h, 36BBh
.word CE4Ch, DFC5h, ED5Eh, FCD7h, 8868h, 99E1h, AB7Ah, BAF3h
.word 5285h, 430Ch, 7197h, 601Eh, 14A1h, 0528h, 37B3h, 263Ah
.word DECDh, CF44h, FDDFh, EC56h, 98E9h, 8960h, BBFBh, AA72h
.word 6306h, 728Fh, 4014h, 519Dh, 2522h, 34ABh, 0630h, 17B9h
.word EF4Eh, FEC7h, CC5Ch, DDD5h, A96Ah, B8E3h, 8A78h, 9BF1h
.word 7387h, 620Eh, 5095h, 411Ch, 35A3h, 242Ah, 16B1h, 0738h
.word FFCFh, EE46h, DCDDh, CD54h, B9EBh, A862h, 9AF9h, 8B70h
.word 8408h, 9581h, A71Ah, B693h, C22Ch, D3A5h, E13Eh, F0B7h
.word 0840h, 19C9h, 2B52h, 3ADBh, 4E64h, 5FEDh, 6D76h, 7CFFh
.word 9489h, 8500h, B79Bh, A612h, D2ADh, C324h, F1BFh, E036h
.word 18C1h, 0948h, 3BD3h, 2A5Ah, 5EE5h, 4F6Ch, 7DF7h, 6C7Eh
.word A50Ah, B483h, 8618h, 9791h, E32Eh, F2A7h, C03Ch, D1B5h
.word 2942h, 38CBh, 0A50h, 1BD9h, 6F66h, 7EEFh, 4C74h, 5DFDh
.word B58Bh, A402h, 9699h, 8710h, F3AFh, E226h, D0BDh, C134h
.word 39C3h, 284Ah, 1AD1h, 0B58h, 7FE7h, 6E6Eh, 5CF5h, 4D7Ch
.word C60Ch, D785h, E51Eh, F497h, 8028h, 91A1h, A33Ah, B2B3h
.word 4A44h, 5BCDh, 6956h, 78DFh, 0C60h, 1DE9h, 2F72h, 3EFBh
.word D68Dh, C704h, F59Fh, E416h, 90A9h, 8120h, B3BBh, A232h
.word 5AC5h, 4B4Ch, 79D7h, 685Eh, 1CE1h, 0D68h, 3FF3h, 2E7Ah
.word E70Eh, F687h, C41Ch, D595h, A12Ah, B0A3h, 8238h, 93B1h
.word 6B46h, 7ACFh, 4854h, 59DDh, 2D62h, 3CEBh, 0E70h, 1FF9h
.word F78Fh, E606h, D49Dh, C514h, B1ABh, A022h, 92B9h, 8330h
.word 7BC7h, 6A4Eh, 58D5h, 495Ch, 3DE3h, 2C6Ah, 1EF1h, 0F78h
|
Googled some of the constants and this was the first link i clicked.
http://mypage.bluewin.ch/horo/tech/ppp-fcs/fcs.html
and here's the rfc it references
http://www.faqs.org/rfcs/rfc1662.html
|
|
Haha argh. It was so late that I was googling "1189 2312 239b" ... which wasn't helping much. Thanks. :)
|
|
Congrats on the find, and as for your "Googling typo", I think we've ALL been there at least once! :) Good work - processor modules are fun, huh?
|
Yeah, I guess. I'm finding the processor module frustrating, because I know there's so much more analysis I could be doing, but having trouble figuring out how to do it within the context of a processor module. Having figured out the checksum algorithm allows me to patch the application code on this box ... but I still need to figure out what to actually change. I'll start up another thread about that, though.
The fruits of this specific labor: http://www.avic411.com/forum/viewtopic.php?p=47930&sid=9262a6ec948ab54f529c2d4746ea0a73#47930
Thanks to all for their help!
|
Note: Registration is required to post to the forums.
|
![[+] expand](/imagery/files/soysauce_blueprint.gif){kind=link}