Windows PE Checksum Algorithm

[Jeffrey Walton]

Hi All,

I just wanted to post the general results. Nothing in too much detail
just in case (I glossed over some linear transformations). This does
not appear to be a CRC at all. It is a Summation of DWORDs accumulated
in EAX.

My BaseLine File Statistics:
Base Address: 0xB70000
File Size: 0x010E00

The Library is ImageHlp.dll, Functions of interest:
CheckSumMappedFile
ChkSum (called by CheckSumMappedFile)

PIMAGE_NT_HEADERS CheckSumMappedFile(
PVOID BaseAddress,
DWORD FileLength,
PDWORD HeaderSum,
PDWORD CheckSum
);

******************************
Setup
******************************
imagehlp!CheckSumMappedFile:
76c96f01 - 76c946c9 SEH Setup...
76c96f13 8b450c mov eax,dword ptr [ebp+0Ch]
76c96f16 d1e8 shr eax,1
76c96f18 50 push eax
76c96f19 ff7508 push dword ptr [ebp+8]
76c96f1c 6a00 push 0
76c96f1e e856d6ffff call imagehlp!ChkSum (76c94579)

76c96f18 (push eax) pushes the file's length. For some reason it came
in as File Size/2 (hence shr eax, 1).
76c96f19 (push dword ptr [ebp+8] ) pushes the Base Address
76c96f1c (push 0) pushes the Intialized Sum

Below is Cleanup from calling ChkSum.

******************************
Return/Cleanup
******************************
76c96f23 8bf8 mov edi,eax
76c96f25 897de4 mov dword ptr [ebp-1Ch],edi
76c96f28 8365fc00 and dword ptr [ebp-4],0
76c96f2c ff7508 push dword ptr [ebp+8]
76c96f2f e81ed2ffff call imagehlp!RtlpImageNtHeader (76c94152)
76c96f34 8945e0 mov dword ptr [ebp-20h],eax
76c96f37 834dfcff or dword ptr [ebp-4],0FFFFFFFFh
76c96f3b eb1d jmp imagehlp!CheckSumMappedFile+0x4f (76c96f5a)

And Mr. ChkSum:

******************************
ChkSum
******************************
76c94579 56 push esi
76c9457a 8b4c2410 mov ecx,dword ptr [esp+10h]
76c9457e 8b74240c mov esi,dword ptr [esp+0Ch]
76c94582 8b442408 mov eax,dword ptr [esp+8]
76c94586 d1e1 shl ecx,1

Save ESI
ECX: Size of File
ESI: Base Address
EAX: Running Total

Next, ECX is tested against values 2, 4, ... 0x20, 0x40. None of the
tests triggered code execution other that a jump to the next test.
Perhaps this is an obfuscation??? To be determined.

Next, some meat and potatoes:
76c94661 0306 add eax,dword ptr [esi]
76c94663 134604 adc eax,dword ptr [esi+4]
76c94666 134608 adc eax,dword ptr [esi+8]
76c94669 13460c adc eax,dword ptr [esi+0Ch]
76c9466c 134610 adc eax,dword ptr [esi+10h]
...
76c946b1 13466c adc eax,dword ptr [esi+6Ch]
76c946b4 134670 adc eax,dword ptr [esi+70h]
76c946b7 134674 adc eax,dword ptr [esi+74h]
76c946ba 134678 adc eax,dword ptr [esi+78h]
76c946bd 13467c adc eax,dword ptr [esi+7Ch]

Get the Flags Register in Order:
c946c0 83d000 adc eax,0

And Finally, adjust some Counters (to account for consumption of DWORDS):
76c946c3 81c680000000 add esi,80h // Base Address += 0x80
76c946c9 81e980000000 sub ecx,80h // File Size -= 0x80

A jump again occured into _SAME_ summation routine:
76c94661 0306 add eax,dword ptr [esi]
76c94663 134604 adc eax,dword ptr [esi+4]
76c94666 134608 adc eax,dword ptr [esi+8]
76c94669 13460c adc eax,dword ptr [esi+0Ch]
76c9466c 134610 adc eax,dword ptr [esi+10h]
...
76c946b1 13466c adc eax,dword ptr [esi+6Ch]
76c946b4 134670 adc eax,dword ptr [esi+70h]
76c946b7 134674 adc eax,dword ptr [esi+74h]
76c946ba 134678 adc eax,dword ptr [esi+78h]
76c946bd 13467c adc eax,dword ptr [esi+7Ch]

Set Flags/Adjust Counter and Pointer
76c946c0 83d000 adc eax,0
76c946c3 81c680000000 add esi,80h
76c946c9 81e980000000 sub ecx,80h

Jump Again:
76c946cf 7590 jne imagehlp!ChkSum+0xe8 (76c94661)

Basically, this is summing 0x80 bytes at a time. Finally, return EAX &
0xFFFF (discard high order 2 bytes).

Later, after returning from ChkSum:
76c96f73 754b jne imagehlp!CheckSumMappedFile+0xb5 (76c96fc0)
76c96f75 8d4858 lea ecx,[eax+58h]
76c96f78 8b11 mov edx,dword ptr [ecx]
76c96f7a 8916 mov dword ptr [esi],edx

76c96f75 (lea ecx,[eax+58h]) loads the effective address of the
Checksum Header Field. In this example, Base Address = B70000, so ECX
= B70138. So, this is fetching HeaderSum and writing it to the PDWORD
HeaderSum.

And the following writes the calculated (ECX=0 from the prologue) to
PDWORD CheckSum:
76c96fb1 03d1 add edx,ecx
76c96fb3 8b4d14 mov ecx,dword ptr [ebp+14h]
76c96fb6 8911 mov dword ptr [ecx],edx

Finally, PIMAGE_NT_HEADERS is returned in EAX.

Jeff

[Jeffrey Walton]

Hi All,

An additional note thanks to Peter Bell for leading me down the path.
This is an fairly well known Additive Checksum.

He brought to my attention the instruction at 76c96f16 (shr ecx, 1).
It is complimented by 76c94586 in ChkSum (shl ecx,1) - mentioning he
suspected the algorithm was 16 bit word oriented before the shift.

It now appears this is a modification of RFC 1071 - Computing the
Internet Checksum. http://www.faqs.org/rfcs/rfc1071.html

Jeff

[Jeffrey Walton]

Hi All,

A few corrections based on misinterpretations (and worse, bad
recolection)... The execution path I observed never jumped into the
code described below, so it probably still has misinterpretations.

> Next, ECX is tested against values 2, 4, ... 0x20, 0x40. None of the
> tests triggered code execution other that a jump to the next test.
> Perhaps this is an obfuscation??? To be determined.

EDI = ESI at this point. So EDI is a scratch register used once.

This appears to be working on a combination of:
* alignment of the file mapping (ensureing a 4 byte alignment?)
* file sizes which are not a multiple of 0x80

Consider the first test:
76c9458e f7c602000000 test esi,2

if [br=1] (branch = true), jump to the next test.
76c94594 7410 je imagehlp!ChkSum+0x2d (76c945a6)

Otherwise:
76c94596 2bd2 sub edx,edx // Zero EDX
76c94598 668b16 mov dx,word ptr [esi] // set up for
addition
76c9459b 03c2 add eax,edx // Add 1 DWORD to eax (4 =
sizeof(DWORD) )
76c9459d 83d000 adc eax,0
76c945a0 83c602 add esi,2 // adjust ESI

Then into the next test (test esi, 8) at 76c945b3.

76c945b3 f7c108000000 test ecx,8
if [br=1] (branch = true), jump to the next test.

Otherwise:
76c945b9 7414 je imagehlp!ChkSum+0x56 (76c945cf)
76c945bb 0306 add eax,dword ptr [esi]
76c945bd 134604 adc eax,dword ptr [esi+4]
76c945c0 83d000 adc eax,0
76c945c3 83c608 add esi,8
76c945c6 83e908 sub ecx,8

Same story here: Add and Adjust pointers. An observation from above is
sizeof( 2 DWORDS ) = 8.

Next, another test/branch. The code of interest is:

76c945cf f7c110000000 test ecx,10h
76c945d5 741a je imagehlp!ChkSum+0x78 (76c945f1)
76c945d7 0306 add eax,dword ptr [esi]
76c945d9 134604 adc eax,dword ptr [esi+4]
76c945dc 134608 adc eax,dword ptr [esi+8]
76c945df 13460c adc eax,dword ptr [esi+0Ch]
76c945e2 83d000 adc eax,0

Again, Add and Adjust pointers. An observation from above is sizeof( 4
DWORDS ) = 16 = 10h.

Following this pattern (before the main loop), up to and including
'test ecx,40h' will cause ECX % 0x80 == 0. So the main loop executes
and the remaining files size to be processed is a multiple 0x80.

Jeff

[Parch]

Just as a suggestion - could all the tests against 0x2, 0x4, 0x8, etc.
be something like Duff's Device for loop unrolling?

[Jeffrey Walton]

Hi Parch,

I'm not sure what that is. Sorry.

Jeff

[Parch]

It's only a google search away: http://en.wikipedia.org/wiki/Duff's_device

On Jun 25, 9:26 am, "Jeffrey Walton" <noloa...@gmail.com> wrote:
> Hi Parch,
>
> I'm not sure what that is. Sorry.
>
> Jeff
>

[Jeffrey Walton]

Hi Parch,

Beat you to it... I also cited you and Peter Bell.
http://www.codeproject.com/useritems/PEChecksum.asp

Jeff