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!