Cyclic Redundancy Checks

First of all, I want to apologise for not posting for a long time. I’ve been very busy with work at college, I’ll try to post more regularly.

In this post I want to talk about Cyclic Redundancy Checks, and what they are. In the most basic form, CRCs are an error checking method for digital transmission of data. In short, they use polynomial division to check for inconsistencies within data. As you know, data is in the form of binary, which has base two, so the bit is either 0 or 1. As well as the message, which is a series of bits, there is a check word value which is added as well as the message, this number is the divisor. The transmitter and receiver both have the value of the divisor, which is used to check for errors in the bits. When the message is sent, the receiver divides the divisor from dividend (message), if the remainder is the same, then the data should be intact.

The key word (divisor) is usually presented in the form of a generator polynomial, the coeffecients of this number will be the binary bits of K. This is probably difficult to picture, so I’ll explain more. So suppose we want to use the number 36 as K. This number is written as 100100 in binary, and as x^5 + x^2 + 1 as a polynomial expression. The bits of the remainder left of K will usually lead to k-1, so in this case, we are left with a 6 bit CRC. The higher the value of the divisor, the chances of a false positive occurring are much more slim.

Alright, so suppose we want to send message M, which has the value of 110101101000101100010111. We then perform long division on the bits by our generator polynomial K = 100100.  All we need to know is the XOR method, which essentially means if two bits are the same, they equal zero, and if they are different, they equal one.

0/0 = 0    1/0 = 1    0/1= 1    1/1= 0

binary crc

So here in this picture, I’ve used binary long division to work out the remainder, and this remainder is the CRC. So when a message is sent M, K is also added on to create a divisor which should have a specific remainder. When the data doesn’t match up, the remainder will be different to what it should be, thus the integrity of the data has been compromised.

So what happens if something like occurs in Windows? Well in the following scenario, there’s a bugcheck that keeps occurring, but the cause isn’t a driver, it’s a ahrdware component.

3: kd> .bugcheck
Bugcheck code 0000007A
Arguments fffff6fc`00e500a0 ffffffff`c000003f 00000003`182a3860 fffff801`ca014d84

//Kernel inpage error, kernel data couldn’t be brought in from disk

3: kd> !error ffffffffc000003f
Error code: (NTSTATUS) 0xc000003f (3221225535) – {Bad CRC}  A cyclic redundancy check (CRC) checksum error occurred.

//Here’s out redundancy check, the data is corrupt, it doesn’t match what was originally written.

3: kd> k
Child-SP          RetAddr           Call Site
ffffd000`3cd0d5c8 fffff803`881ade2f nt!KeBugCheckEx //Data is corrupt, bugcheck
ffffd000`3cd0d5d0 fffff803`8806a0ac nt!MiWaitForInPageComplete+0x3177f //Wait for the data to be paged in
ffffd000`3cd0d6c0 fffff803`88081c44 nt!MiIssueHardFault+0x184 //Data isn’t present in memory, hard fault, page //in from disk
ffffd000`3cd0d780 fffff803`8817642f nt!MmAccessFault+0x524 //Incur the memory manager page fault handler
ffffd000`3cd0d930 fffff801`ca014d84 nt!KiPageFault+0x12f //Hit a page fault
ffffd000`3cd0dac8 fffff801`c9ff4b92 dxgkrnl!DxgkMiracastQueryMiracastSupport
ffffd000`3cd0dad0 fffff803`881779b3 dxgkrnl!DxgkNetDispQueryMiracastDisplayDeviceSupport+0x1a //Internal DirectX functions
ffffd000`3cd0db00 00007ff8`bc8b15ea nt!KiSystemServiceCopyEnd+0x13 //Transition to kernel mode
000000e3`3521e508 00000000`00000000 0x00007ff8`bc8b15ea //User mode

fffff801ca0148d4-fffff801ca01491a  71 bytes – dxgkrnl!DxgkHandleMiracastEscape+380 (+0x06)
[ 85 c9 74 2e ff c9 74 15:00 c7 84 24 08 02 00 00 ]
fffff801ca01491c-fffff801ca014951  54 bytes – dxgkrnl!DxgkHandleMiracastEscape+3c8 (+0x48)
[ 00 41 bd 40 00 00 00 45:41 89 cc 45 2b e3 41 89 ]
WARNING: !chkimg output was truncated to 50 lines. Invoke !chkimg without ‘-lo [num_lines]’ to view  entire output.
3988 errors : !dxgkrnl (fffff801ca014000-fffff801ca014fff)

So we can see all these errors, 3988 to be precise, now was it the RAM or the disk? Well, it’s difficult to say with one dump file, so I analysed a few more, although the error was different. It was a failing disk that simply disappeared, thus crashing the system. The error in this case was almost certainly due to part of the disk which had stopped functioning correctly, and therefore corrupting kernel data.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s