Memory Integrity Checks with CRC/Hashing

1. The "Why": Ensuring Runtime Integrity

Imagine a common scenario in an automotive ECU: a block of critical calibration data is stored in non-volatile memory (like EEPROM or Flash). This data defines how the system behaves—think engine timing maps or ADAS sensor parameters. If a single bit in this data flips due to hardware degradation or electrical noise, the consequences could be severe.

A software integrity check is a mechanism to detect such corruption. The general process is:

1. Calculate: When the data is known to be good (e.g., at the factory or after a secure update), you compute a checksum or hash over that memory region.
2. Store: You store this calculated "fingerprint" in a reliable location.
3. Validate: Periodically during runtime (e.g., at startup or during idle loops), you recalculate the fingerprint for the current data and compare it to the stored one. A mismatch indicates that the data has been corrupted.

The diagram below illustrates this exact process for validating an EEPROM memory region.

The two most common families of algorithms for this are Cyclic Redundancy Checks (CRCs) and cryptographic hash functions. Let's examine each.

2. Cyclic Redundancy Check (CRC): Detecting Accidental Errors

A CRC is an error-detecting code specifically designed to be robust against common forms of accidental data corruption, like single-bit errors or burst errors (a sequence of flipped bits). It's extremely fast and widely used in communication protocols (like CAN, Ethernet, and PCIe) and storage systems.

The mathematics behind CRC involves polynomial division in a special kind of arithmetic called a finite field (GF(2)). This sounds complex, but it has a wonderful property: the math can be implemented very efficiently using simple bitwise operations, primarily XORs and shifts.

To build a solid intuition for how CRCs work, let's turn to a fantastic video from Ben Eater.

Implementing CRC in C

While the theory involves polynomial division, a software implementation rarely performs it bit-by-bit as it's too slow. The standard, highly efficient method is the table-driven approach. This technique pre-calculates the results for every possible 8-bit input value and stores them in a 256-entry lookup table. The CRC of a large data block can then be calculated one byte at a time using table lookups and XOR operations, which is significantly faster.

The following article from Barr Group provides one of the clearest guides to implementing CRC in C.

Here is a practical C implementation of the CRC-32 standard (commonly used in Ethernet and SATA) using the table-driven method from the article.

#include <stdio.h>
#include <stdint.h>

// CRC-32 standard parameters
#define CRC32_POLYNOMIAL 0x04C11DB7
#define CRC32_INITIAL_REMAINDER 0xFFFFFFFF
#define CRC32_FINAL_XOR_VALUE 0xFFFFFFFF

// Type definition for the CRC result
typedef uint32_t crc;

// Lookup table
static crc crcTable[256];

/**
 * @brief Initializes the CRC-32 lookup table.
 * This function must be called once before any CRC calculations.
 */
void crcInit(void) {
    crc remainder;
    for (int dividend = 0; dividend < 256; ++dividend) {
        remainder = dividend << 24; // Align dividend to the MSB
        for (uint8_t bit = 8; bit > 0; --bit) {
            if (remainder & 0x80000000) { // Check MSB
                remainder = (remainder << 1) ^ CRC32_POLYNOMIAL;
            } else {
                remainder = (remainder << 1);
            }
        }
        crcTable[dividend] = remainder;
    }
}

/**
 * @brief Calculates the CRC-32 of a data block using the lookup table.
 * @param message Pointer to the data block.
 * @param nBytes  Number of bytes in the data block.
 * @return The 32-bit CRC value.
 */
crc crcFast(const uint8_t message[], int nBytes) {
    crc remainder = CRC32_INITIAL_REMAINDER;
    for (int byte = 0; byte < nBytes; ++byte) {
        uint8_t data = message[byte] ^ (remainder >> 24); // XOR with the top byte of the remainder
        remainder = crcTable[data] ^ (remainder << 8);    // Lookup and shift
    }
    return (remainder ^ CRC32_FINAL_XOR_VALUE);
}

int main() {
    // Sample data (e.g., a block of calibration data)
    uint8_t cal_data[] = { '1', '2', '3', '4', '5', '6', '7', '8', '9' };
    int data_len = sizeof(cal_data);

    // 1. Initialize the CRC table
    crcInit();

    // 2. Calculate the CRC of the original data
    crc original_crc = crcFast(cal_data, data_len);
    printf("Original Data CRC-32: 0x%08X\n", original_crc); // Expected: 0xCBF43926

    // 3. Simulate a single-bit error in the data
    printf("Introducing a single-bit error...\n");
    cal_data[4] ^= 0x01; // Flip one bit in the character '5'

    // 4. Recalculate the CRC and check for a mismatch
    crc corrupted_crc = crcFast(cal_data, data_len);
    printf("Corrupted Data CRC-32: 0x%08X\n", corrupted_crc);

    if (original_crc != corrupted_crc) {
        printf("Integrity check FAILED! Data corruption detected.\n");
    } else {
        printf("Integrity check PASSED. This should not happen.\n");
    }

    return 0;
}

3. Cryptographic Hash Functions: Detecting Malicious Modifications

While CRCs are excellent for detecting accidental errors, they provide no security. It is trivial for an attacker to modify a message and then calculate a new CRC for that modified message.

This is where cryptographic hash functions like SHA-256 (Secure Hash Algorithm 256-bit) come in. They are designed to be one-way functions, creating a fixed-size "fingerprint" that is computationally infeasible to reverse or forge.

Implementing Hash Functions

Implementing a cryptographic hash function like SHA-256 from scratch is a complex task involving specific padding schemes, message scheduling, and a series of complex bitwise operations executed in rounds.

Given this complexity, it is a security best practice not to write your own cryptographic functions. Instead, you should always use a well-vetted, peer-reviewed library like OpenSSL, mbed TLS, or a vendor-specific library that leverages hardware acceleration. In the context of our previous lesson, you would use a driver API to command the HSM to perform the hash calculation, which is both faster and more secure.

4. CRC vs. Hash: Which One to Use?

The choice between CRC and a cryptographic hash depends entirely on your threat model.

Given your experience, you've likely seen CRCs protecting data payloads in communication stacks and hashes being used to verify entire software images during a secure flashing or boot process.

5. Interview Corner

Q1: What is the purpose of a software integrity check? Give an example of where you would use one in an automotive system.
A: A software integrity check is a process used to verify that a block of code or data has not been altered. It works by calculating a "fingerprint" (a checksum or hash) of the data at a known-good state and then recalculating it at runtime to check for changes. A great automotive example is verifying the integrity of critical calibration data stored in EEPROM at every ECU startup to protect against data corruption.

Q2: What is the fundamental difference between a CRC and a cryptographic hash like SHA-256? When would you choose one over the other?
A: The key difference lies in the threat model they address. A CRC is designed to detect accidental errors (like bit flips from noise) and is computationally very fast but offers no security. I would use it for checking communication data integrity or detecting memory degradation. A cryptographic hash like SHA-256 is designed to be secure against malicious modification. It's computationally intensive but provides properties like collision resistance. I would use it for security-critical tasks like verifying firmware signatures during secure boot.

Q3: You need to implement a CRC-32 check in a resource-constrained embedded system. What is the most efficient software implementation method, and what is its trade-off?
A: The most efficient method is a table-driven implementation. Instead of calculating the polynomial division bit-by-bit for the entire message, you pre-calculate the CRC results for all 256 possible byte values into a lookup table. The main CRC loop then processes the message a full byte at a time using table lookups and XORs, which is much faster. The trade-off is memory for speed: you sacrifice 1KB of ROM or RAM (256 entries * 4 bytes/entry for CRC-32) to store the lookup table, but you gain a significant performance improvement in CPU cycles.

Q4 (Advanced): During runtime, your ECU needs to periodically verify the integrity of its own 4MB application firmware stored in flash. A full SHA-256 hash is too slow to run frequently. How could you design a robust and performant integrity check?
A: This is a classic trade-off between security and performance. A robust solution could be a hybrid approach.

1. Full Hash at Boot: Perform a full SHA-256 hash verification of the entire application firmware once at boot time, potentially accelerated by an HSM if available. This provides a strong guarantee that the application is authentic before it starts executing.
2. CRC for Runtime Checks: For the periodic runtime checks, use a much faster CRC-32. Since the firmware is in flash and shouldn't change during runtime, the primary threat is accidental bit-flipping, which CRC is perfect for detecting.
3. Hierarchical Check (Optional): To make the check even faster, you could divide the 4MB firmware into smaller blocks (e.g., 4KB each) and store a CRC-32 for each block. The periodic check can then iterate through these blocks over time, so you're not even calculating a CRC over the full 4MB in one go. This distributes the already low CPU load even further.

Conclusion

Today we've distinguished between integrity checks for detecting accidental errors versus those for providing security. You now understand the principles and trade-offs of using CRC and cryptographic hash functions. Most importantly, you can implement an efficient, table-driven CRC in C—a fundamental skill for any low-level driver developer.

Key Takeaways:

• CRC is for detecting accidental errors. It's fast, simple, but not secure.
• Cryptographic Hashes (like SHA-256) are for detecting malicious modifications. They are secure but computationally expensive.
• The most efficient software implementation for CRC is the table-driven method, which trades memory for a significant speed increase.
• For security-critical hashing, always use a vetted library or hardware accelerator (HSM).

Next Lesson Preview

We have now learned how to detect if a memory region has been tampered with or corrupted. But what if we could prevent unauthorized access in the first place? In our next lesson, we will do just that by exploring the Memory Protection Unit (MPU). We will learn how to configure an MPU to create isolated memory regions, a cornerstone of building safe and secure embedded systems.