Why LevelDB and RocksDB need a `masked CRC32`

user_7197834 0
Viewed 317

From the crc32.h of leveldb or rocksdb, we can find a comment saying: 

static const uint32_t kMaskDelta = 0xa282ead8ul;

// Return a masked representation of crc.
//
// Motivation: it is problematic to compute the CRC of a string that
// contains embedded CRCs.  Therefore we recommend that CRCs stored
// somewhere (e.g., in files) should be masked before being stored.
inline uint32_t Mask(uint32_t crc) {
  // Rotate right by 15 bits and add a constant.
  return ((crc >> 15) | (crc << 17)) + kMaskDelta;
}

So, what does it mean? Why we need a mask?

leveldb rocksdb crc crc32
1 Answers

mask

The "mask" is explained in the comments and the one line of code. It modifies a 32 bit CRC by rotating it right 15 bits and adding a constant.

Why we need a mask?

The mask isn't "needed", but recommended to make the CRC a bit more complicated than a standard CRC, when storing the CRCs. I don't know why it is recommended to "protect" stored CRCs in this manner. If the "masking" process is fixed and known, then I don't see how it helps with "protecting" stored CRCs. I assume the mask is custom and unknown to others for actual usage.

it is problematic to compute the CRC of a string that contains embedded CRCs

It's not clear to me what the comment is getting at. It's not that difficult to generate data that can go anywhere in a string so that the calculated CRC is valid. Typically a CRC is appended to a message, but it can be cycled backwards n bits by multiplying the CRC by (1/(2^(n))) (in the proper Galois field), with a carryless multiply, which can be sped up using an instruction such as X86's pclmulqdq (it uses xmm registers). For example, say a 32 bit CRC is to be stored at bit index j of a string with m bits, including both data and the CRC. The 32 bits at index j are zeroed, then a standard CRC is used to compute the CRC as if it was going to be appended at bit index m. Then the CRC is cycled backwards m - j bits and stored at bit index j.

Having multiple CRCs embedded in a string will make it difficult to reverse engineer, but I've seen cases where savefiles used for games had two CRCs, both embedded, and hackers were able to reverse engineer the twin CRC method.

user_32820560
Related