News:Reverse-engineering the CRC function for UpdateInventoryItem
From libsecondlife
This article was written in September of 2006 by libsecondlife developer bushing. It has been salvaged from an old database and presented here for your reading pleasure
I've always been a big fan of IDA Pro, and have often just disassembled random binaries with the thing to see what it could come up with. When I saw the bounty posted, I sprung at the chance to actually do something useful with it.
As you may have guessed, I do my primary development on a PowerPC Mac, which means I end up running IDA under VirtualPC (which sucks) or on a x86 Linux box running VMWare (which sucks a little less). I ended up having to borrow a Windows-running laptop to do this, though.
Part 1: CRC table
IDA 5.0 took a while to load up "Second Life.exe" (v1.10.5.1), but it lets you start playing while it continues to process in the background. I gave it a 20-minute head start before I started to poke around.
One nice thing about trying to take apart CRC or hash functions (MD5, SHA, etc), is that they all use tables (of various sizes) which you are guaranteed to find in a binary that uses that function (assuming there's no packing or encryption -- which is the case here). CRC32's table is contained in libsecondlife in SecondLife.cs:
private readonly static uint[] crcLookup = new uint[] {
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
So, I went into IDA and searched for "96 30 07 77" (since
we're on a little-endian platform). (I later found a plugin which
automates this -- http://www.hexblog.com/2006/01/findcrypt.html --
the author of that blog is the main author of IDA Pro.)
I found two copies of that table at 0xCBAC28 and and 0xDCCA88 -- which IDA was able to tell me were called only by sub_810CA0 and sub_97B3B0, respectively.
Neither of these seemed very promising, however, because when I searched for the string "UpdateInventoryItem", I found "Got a UpdateInventoryItem for the wrong agent." at 0xC7083C, which was printed by sub_551665. It's reasonable to assume that the compiler will group methods for an object together, so this didn't seem promising.
I just get a kick out of taking shit apart, so I happened to know that Linden doesn't bother to strip the debugging info out of the Linux or Mac clients. So, I turned to the Linux client.
Part 2: Find functions in the Linux client, match them to the Windows version
(Let me admit right here that letting IDA run through a binary completely is not a fast process. It took over 6 hours of CPU time on an Athlon 1800 to fully process the Linux version, using the Linux version of IDA -- but you can get a lot of meaningful data before it's done processing.)
Following the same steps in the Linux version told me that I had found LLCRC::Update, which is actually not involved at all here and would have not been helpful.
I searched for "CRC" in the function names and came up with LLInventoryItem::getCRC32, which seemed much more likely. Looking at it in the Linux version, I saw that it added up some parts of a struct and called two child functions -- LLPermissions::getCRC32 and LLSaleInfo::getCRC32. Name aside, this is not much of a CRC32 algorithm!
I would have loved to be able to stop here and write up an answer, but the problem is that without knowing the exact way that the LLInventoryItem is laid out in memory, I couldn't know what bits of data it was actually using. It was time ... to bust out the debugger.
Part 3: Ben tries to figure out how to use Windows
I don't currently have a Windows box set up, so I had to borrow my fiancee's laptop to install the SL client, IDA Pro and snowcrash -- which I have never before actually used. It's a neat little utility, and sure beats trying to stare at hex dumps from tcpdump like I had been doing. The one problem I had with it was that I couldn't find any way to redirect its output to a file -- I had to be very lucky to actually catch the packet I was looking for so I could cut and paste it into NotePad. (I know I could have rebuilt a new version, but I was in a hurry here -- I didn't know if anyone else was working on the problem, and it wasn't my computer anyway, no dev environment...)
Having found the right functions in the Linux client, I had to find them in the Windows version so I could place a breakpoint. The easiest way was to take advantage of the fact that LLSaleInfo::getCRC32 uses an odd constant -- 0x07073096 -- which I searched for and found in the Windows version.
IDA's not perfect -- it sometimes misses code sections, leaving you to manually flag them as such -- so it didn't know how or where that got called, and I couldn't immediately find LLInventoryItem::getCRC32. No matter -- I put the cursor on the start of LLSaleInfo::getCRC32 and set a breakpoint, and then attached to an already-running copy of SL. (It would have taken forever if it had to load SL itself, so this was faster.) Once you attach, it immediately pauses the program, so hit F9 really quickly to resume it. I pulled up the edit panel for my inventory item and made a change, and landed back in the debugger at the start of LLSaleInfo::getCRC32. Hitting Ctrl-F7 (run until function returns) landed me back in a region of "unexplored" binary data -- so I went back a page or two and hit "C" to tell IDA to turn it into code, which it did. Now that I had found LLInventoryItem::getCRC32, I stopped IDA, moved my breakpoint there, and repeated the above.
Part 4: Decoding memory
When I landed back in the debugger, I got a chance to see what the LLInventoryItem looked like in memory. It looked like this:
debug269:0DD11998 dd offset off_C86BC0
debug269:0DD1199C dd 1
debug269:0DD119A0 dd 6208A13Bh
debug269:0DD119A4 dd 0B4F5275Ah
debug269:0DD119A8 dd 186EA5AFh
debug269:0DD119AC dd 2029BA2h
debug269:0DD119B0 dd 2E8B8A1Ch
debug269:0DD119B4 dd 744EFF24h
debug269:0DD119B8 dd 23161C81h
debug269:0DD119BC dd 8D16F30Fh
debug269:0DD119C0 dd 6
debug269: 0DD119C4 dd offset dword_540020
debug269:0DD119C8 dd offset aTokinMouthpiece2 ; "Tokin' Mouthpiece 2"
debug269:0DD119CC dd 6E0069h
debug269:0DD119D0 dd offset unk_200067
debug269:0DD119D4 dd offset unk_6F0074
debug269:0DD119D8 dd 13h
debug269:0DD119DC dd 1Fh
debug269:0DD119E0 dd offset off_C4EAD4
debug269:0DD119E4 dd 0A8036470h
debug269:0DD119E8 dd 3B4D7843h
debug269:0DD119EC dd 29CC689Eh
debug269:0DD119F0 dd 9E29D3Dh
debug269:0DD119F4 dd 5BB4CE41h
debug269:0DD119F8 dd 8D42D552h
debug269:0DD119FC dd 5492E59Ch
debug269:0DD11A00 dd 9B5764F9h
debug269:0DD11A04 dd 0
debug269:0DD11A08 dd 0
debug269:0DD11A0C dd 0
debug269:0DD11A10 dd 0
debug269:0DD11A14 dd 0
debug269:0DD11A18 dd 0
debug269:0DD11A1C dd 0
debug269:0DD11A20 dd 0
debug269:0DD11A24 dd 581632
debug269:0DD11A28 dd 581632
debug269:0DD11A2C dd 0
debug269:0DD11A30 dd 573440
debug269:0DD11A34 dd 581632
debug269:0DD11A38 dd offset unk_330000
debug269:0DD11A3C dd 0B95EBB8Eh
debug269:0DD11A40 dd 3FF4B4FBh
debug269:0DD11A44 dd 26F912F2h
debug269:0DD11A48 dd 0B4931D0Ch
debug269:0DD11A4C dd 630000h
debug269:0DD11A50 dd offset aNoDescriptionXxxx ; "(No Description) xxxx"
debug269:0DD11A54 dd offset unk_360037
debug269:0DD11A58 dd 640037h
debug269:0DD11A5C dd offset unk_610036
debug269:0DD11A60 dd 21
debug269:0DD11A64 dd 31
debug269:0DD11A68 dd 0
debug269:0DD11A6C dd 10
debug269:0DD11A70 dd 6
debug269:0DD11A74 dd 262400
debug269:0DD11A78 dd 1151398498
debug269:0DD119C4 dd offset dword_540020
debug269:0DD119C8 dd offset aTokinMouthpiece2 ; "Tokin' Mouthpiece 2"
debug269:0DD119CC dd 6E0069h
debug269:0DD119D0 dd offset unk_200067
debug269:0DD119D4 dd offset unk_6F0074
debug269:0DD119D8 dd 13h
debug269:0DD119DC dd 1Fh
debug269:0DD119E0 dd offset off_C4EAD4
debug269:0DD119E4 dd 0A8036470h
debug269:0DD119E8 dd 3B4D7843h
debug269:0DD119EC dd 29CC689Eh
debug269:0DD119F0 dd 9E29D3Dh
debug269:0DD119F4 dd 5BB4CE41h
debug269:0DD119F8 dd 8D42D552h
debug269:0DD119FC dd 5492E59Ch
debug269:0DD11A00 dd 9B5764F9h
debug269:0DD11A04 dd 0
debug269:0DD11A08 dd 0
debug269:0DD11A0C dd 0
debug269:0DD11A10 dd 0
debug269:0DD11A14 dd 0
debug269:0DD11A18 dd 0
debug269:0DD11A1C dd 0
debug269:0DD11A20 dd 0
debug269:0DD11A24 dd 581632
debug269:0DD11A28 dd 581632
debug269:0DD11A2C dd 0
debug269:0DD11A30 dd 573440
debug269:0DD11A34 dd 581632
debug269:0DD11A38 dd offset unk_330000
debug269:0DD11A3C dd 0B95EBB8Eh
debug269:0DD11A40 dd 3FF4B4FBh
debug269:0DD11A44 dd 26F912F2h
debug269:0DD11A48 dd 0B4931D0Ch
debug269:0DD11A4C dd 630000h
debug269:0DD11A50 dd offset aNoDescriptionXxxx ; "(No Description) xxxx"
debug269:0DD11A54 dd offset unk_360037
debug269:0DD11A58 dd 640037
debug269:0DD11A5C dd offset unk_610036
debug269:0DD11A60 dd 21
debug269:0DD11A64 dd 31
debug269:0DD11A68 dd 0
debug269:0DD11A6C dd 10
debug269:0DD11A70 dd 6
debug269:0DD11A74 dd 262400
debug269:0DD11A78 dd 1151398498
I compared it to SnowCrash's output:
----- UpdateInventoryItem -----
InventoryData
GroupOwned: False
CRC: 2381809515
CreationDate: 1151398498
SaleType: 0 BaseMask: 581632
Name: Tokin' Mouthpiece 2
InvType: 6 Type: 6
AssetID: 8ebb5eb9fbb4f43ff212f9260c1d93b4
GroupID: 00000000000000000000000000000000
SalePrice: 10 OwnerID: 41ceb45b52d5428d9ce59254f964579b
CreatorID: 706403a843784d3b9e68cc293d9de209
ItemID: 3ba108625a27f5b4afa56e18a29b0202
FolderID: 1c8a8b2e24ff4e74811c16230ff3168d
EveryoneMask: 0 Description: (No Description) xxxx
Flags: 262400 NextOwnerMask: 581632
GroupMask: 573440 OwnerMask: 581632
AgentData
AgentID: 41ceb45b52d5428d9ce59254f964579b
And came up with the following guess at the struct format for LLInventoryItem:
00000000 LLInventoryItem struc ; (sizeof=0xE4)
00000000 field_0 dd ?
00000004 field_4 dd ?
00000008 itemID1 dd ?
0000000C itemID2 dd ?
00000010 itemID3 dd ?
00000014 itemID4 dd ?
00000018 folderID1 dd ?
0000001C folderID2 dd ?
00000020 folderID3 dd ?
00000024 folderID4 dd ?
00000028 invtype_or_type dd ?
0000002C field_2C dd ?
00000030 field_30 dd ?
00000034 field_34 dd ?
00000038 field_38 dd ?
0000003C field_3C dd ?
00000040 field_40 dd ?
00000044 field_44 dd ?
00000048 LLPermissions dd ?
0000004C creatorID1 dd ?
00000050 creatorID2 dd ?
00000054 creatorID3 dd ?
00000058 creatorID4 dd ?
0000005C ownerID1 dd ?
00000060 ownerID2 dd ?
00000064 ownerID3 dd ?
00000068 ownerID4 dd ?
0000006C zero1 dd ?
00000070 zero2 dd ?
00000074 zero3 dd ?
00000078 zero4 dd ?
0000007C zero5 dd ?
00000080 zero6 dd ?
00000084 zero7 dd ?
00000088 zero8 dd ?
0000008C owner_mask dd ?
00000090 nextowner_mask dd ?
00000094 everyone_mask dd ?
00000098 group_mask dd ?
0000009C field_9C dd ?
000000A0 field_A0 dd ?
000000A4 assetID1 dd ?
000000A8 assetID2 dd ?
000000AC assetID3 dd ?
000000B0 assetID4 dd ?
000000B4 field_B4 dd ?
000000B8 field_B8 dd ?
000000BC field_BC dd ?
000000C0 field_C0 dd ?
000000C4 field_C4 dd ?
000000C8 field_C8 dd ?
000000CC field_CC dd ?
000000D0 sale_type dd ?
000000D4 sale_price dd ?
000000D8 type_or_invtype dd ?
000000DC flags dd ?
000000E0 creationdate dd ?
000000E4 LLInventoryItem ends
This let me annotate LLInventoryItem::getCRC32. It probably took me about 3 hours to get to this point, and then I spent another hour or two writing up the solution and convincing myself that I was correct. Here's the final output:
;=========================================================================
; This file is generated by The Interactive Disassembler (IDA)
; Copyright (c) 2005 by DataRescue sa/nv, <<a href="mailto:ida@datarescue.com">ida@datarescue.com</a>>
;=========================================================================
.text:008E5C40 ; --------------- S U B R O U T I N E ---------------------------------------
.text:008E5C40 LLInventoryItem::getCRC32 proc near
.text:008E5C40 push esi
.text:008E5C41 mov esi, ecx
.text:008E5C43 mov eax, [esi+LLInventoryItem.folderID3]
.text:008E5C46 mov edx, [esi+LLInventoryItem.folderID2]
.text:008E5C49 mov ecx, [esi+LLInventoryItem.itemID4]
.text:008E5C4C push edi
.text:008E5C4D mov edi, [esi+LLInventoryItem.folderID4]
.text:008E5C50 add edi, eax
.text:008E5C52 mov eax, [esi+LLInventoryItem.itemID3]
.text:008E5C55 add edi, edx
.text:008E5C57 mov edx, [esi+LLInventoryItem.itemID2]
.text:008E5C5A add edi, ecx
.text:008E5C5C mov ecx, [esi+LLInventoryItem.folderID1]
.text:008E5C5F add edi, eax
.text:008E5C61 mov eax, [esi+LLInventoryItem.itemID1]
.text:008E5C64 add edi, edx
.text:008E5C66 add edi, ecx
.text:008E5C68 lea ecx, [esi+LLInventoryItem.LLPermissions]
.text:008E5C6B add edi, eax
.text:008E5C6D call LLPermissions::getCRC32
.text:008E5C72 mov ecx, [esi+LLInventoryItem.type_or_invtype]
.text:008E5C78 mov edx, [esi+LLInventoryItem.assetID4]
.text:008E5C7E add edi, eax
.text:008E5C80 mov eax, [esi+LLInventoryItem.flags]
.text:008E5C86 add eax, ecx
.text:008E5C88 mov ecx, [esi+LLInventoryItem.assetID3]
.text:008E5C8E add eax, edx
.text:008E5C90 mov edx, [esi+LLInventoryItem.assetID2]
.text:008E5C96 add eax, ecx
.text:008E5C98 mov ecx, [esi+LLInventoryItem.invtype_or_type]
.text:008E5C9B add eax, edx
.text:008E5C9D mov edx, [esi+LLInventoryItem.assetID1]
.text:008E5CA3 add eax, ecx
.text:008E5CA5 add eax, edx
.text:008E5CA7 lea ecx, [esi+LLInventoryItem.sale_type]
.text:008E5CAD add edi, eax
.text:008E5CAF call LLSaleInfo::getCRC32
.text:008E5CB4 add edi, eax
.text:008E5CB6 mov eax, [esi+LLInventoryItem.creationdate]
.text:008E5CBC add eax, edi
.text:008E5CBE pop edi
.text:008E5CBF pop esi
.text:008E5CC0 retn
.text:008E5CC0 LLInventoryItem::getCRC32 endp
.text:008E5CC0
.text:008E5CC0 ; ---------------------------------------------------------------------------
.text:008E3790 ; --------------- S U B R O U T I N E ---------------------------------------
.text:008E3790 LLPermissions::getCRC32 proc near ; CODE XREF: LLInventoryItem::getCRC32+2Dp
.text:008E3790 mov edx, [ecx+3Ch] ; if you bother to count on your fingers
.text:008E3793 mov eax, [ecx+40h] ; this is really just a stupid way of
.text:008E3796 add eax, edx ; writing sum from ecx+4 to ecx+50h
.text:008E3798 add eax, [ecx+38h] ; and put it into eax
.text:008E379B add eax, [ecx+30h]
.text:008E379E add eax, [ecx+2Ch] ; ecx+4 = creatorID1
.text:008E37A1 add eax, [ecx+28h] ; ecx+14h = ownerID
.text:008E37A4 add eax, [ecx+50h] ; ecx+24h = zeros?
.text:008E37A7 add eax, [ecx+4Ch] ; ecx+34h=zeros?
.text:008E37AA add eax, [ecx+20h] ; ecx+38h=owner_mask
.text:008E37AD add eax, [ecx+48h] ; ecx+3Ch=nextowner_mask
.text:008E37B0 add eax, [ecx+1Ch] ; ecx+40h=everyone_mask
.text:008E37B3 add eax, [ecx+44h] ; ecx+44h=group_mask
.text:008E37B6 add eax, [ecx+18h]
.text:008E37B9 add eax, [ecx+10h]
.text:008E37BC add eax, [ecx+0Ch]
.text:008E37BF add eax, [ecx+8]
.text:008E37C2 add eax, [ecx+34h]
.text:008E37C5 add eax, [ecx+24h]
.text:008E37C8 add eax, [ecx+14h]
.text:008E37CB add eax, [ecx+4]
.text:008E37CE retn
.text:008E37CE LLPermissions::getCRC32 endp
.text:008E37CE ; ---------------------------------------------------------------------------
.text:008E9D00 ; --------------- S U B R O U T I N E ---------------------------------------
.text:008E9D00 LLSaleInfo::getCRC32 proc near ; CODE XREF: LLInventoryItem::getCRC32+6Fp
.text:008E9D00 mov eax, [ecx] (sale_type)
.text:008E9D02 mov edx, [ecx+4] (sale_price)
.text:008E9D05 imul eax, 7073096h
.text:008E9D0B add eax, edx
.text:008E9D0D retn
.text:008E9D0D LLSaleInfo::getCRC32 endp
.text:008E9D0D ; ---------------------------------------------------------------------------
--
You have my permission to redistribute this as you see fit, with my name attached. Nothing I did here was especially clever, but I hope that this inspires someone else and would welcome any questions or suggestions for a better approach. (I learned everything I know from "case studies" like this one.)