2010-02-06

Chinese CRC In Operation Aurora

Google "Operation Aurora: Clues in the Code" for a cool writeup by secureworks about a CRC algorithm found in the trojan used against Google.

CRC lookup tables normally store a precomputed value for each byte, and thus their tables have 256 entries. This one has only 16, how? If you look closely, the temporary value used to hold the result of the current division is shifted by 4, not 8. Division is done twice. What is going on?

This code is using a nibble lookup table. Two nibbles per byte processed. This optimization has decreased the size of the table by a factor of 16, but only decreased the code speed by a factor of 2, a very cool trade off!

Also notice the direction of the shift, this implementation treats higher significance bits as higher order terms (unlike the typical crc-32, which does the opposite). You can thus find all coefficients except a_16 of the divider polynomial at entry 0x01 (instead of 0x80 in the crc-32 ordering). The polynomial is 0x1021 representing x^16 + x^12 + x^5 + 1. (The a_16 * x^16 term is implicit). The wikipedia page calls this CRC-16-CCITT.

With a little care, we can recreate how this nibble lookup table was generated:

WORD table[16];
for(INT i=0; i<16; ++i) {
WORD crc = i<<12;
for(INT j=0; j<4; ++j) { // for each of 4 possible nibble terms
if(crc & 0x8000) { // high order term present?
crc <<= 1; // term=0 (by implied x^16 divider term)
crc ^= 0x1021; // subtract rest of poly
}
else
crc <<= 1;
}
table[i] = crc;
}

When more spare time arrives, I'll adapt a crc-32 implementation to use this trick! Also add it to your bag of tricks to be on the lookout for when reversing!

Feb 09th, 2010 EDIT: check out the current file archive for the source to an adapted crc-32! It was more difficult than expected to get it to work!

6 comments:

  1. Mr. Stewart's "China code" claim seems to have some problem:

    1) A follow-up published by The Register on 1/26 contradicted the claim the CRC algorithm was not known outside China. The 4-bit CRC code has been around for over a decade in the device application arena. Once this fact is public, several code samples outside China have been located by bloggers discussing this issue.

    2) Mr. Stewart seems to have neglected the fact variable names are stripped out during code compilation when he alluded to a variable name in the Aurora machine code. There is absolutely no link between the "crc_ta[16]" variable he identified as Chinese, and the machine code in Aurora.

    Google "crc_table[16]" turns up examples outside China, what does that prove?

    3) Upon closer examination of Mr. Stewart's citations, the alleged Chinese white paper containing the algorithm, and code snip found by Googling the identified variable name, both turned up different code than what's in Aurora.

    Specifically, the Aurora code contains a 12-bit shift optimization (found as early as 1988 according to The Register article):

    t = crc16 >> 12

    however the code passed around in Chinese sites is unoptimized code using two divisions:

    da=((uchar)(crc/256))/16

    ReplyDelete
  2. bobby fletcher:

    Thank you for your post. I read some of your blogs and see what your intention is (after down-playing Tainanmen, perhaps you can argue that lead in my childrens' toys is not so harmful?)

    You are misprepresenting Stewart's line of reasoning, but I cannot engage in a political debate with you, . Perhaps it was too early to name my post "Chinese CRC...", and I will try to keep aware of the news and see what information is found. Your comment stays, and if some news results appear exhonerating China, I'll correct the post, fair?

    About the code: The line "da=crc>>12;" is simply choosing the top 4 bits of the running quotient value; I don't consider it an optimization. Even if author explicitly writes "da=(crc&0xFF00)>>12;" no real compiler should produce an unnecessary AND. Yes, source-level variable names like "crc_ta" have no place inside the machine code. But how then can you not see that da=((uchar)(crc/256)/16 == crc/4096 == crc >> 12? Even MSVC with /Od generates SAR's (China pun, see? :)), and anyone writing code like this is putting integer division fully aware that the shift is occurring (treating the extension field element as an integer is nonsense).

    And Crank Yankers was a very good show :)

    ReplyDelete
  3. staying updated...

    "2 China Schools Said to Be Tied to Online Attacks"

    http://www.nytimes.com/2010/02/19/technology/19china.html

    ReplyDelete
  4. staying updated...

    "BUSTED! Google Hackers Linked To Chinese Government"

    http://www.ft.com/cms/s/0/4a6c8332-1f52-11df-9584-00144feab49a.html

    ReplyDelete
  5. Dude try google "crc_table[16]" and see whay get, and if they prove any govt connection.

    ReplyDelete
  6. Fact check time. The Chinese school claim haz been debunked. Google "Lanxiang hairdresser" - the school is diploma mill for beautician & mechanics.

    ReplyDelete

thanks for commenting!