Cyclic Redundancy Check Example

What is Cyclic Redundancy Check?

A cyclic redundancy check (CRC) is a type of error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated, and in the event, if the check values do not match, corrective action can be taken against data corruption.

CRC is a type of hash function that is used to produce a checksum, which is a small number of bits, from a larger block of data, such as a packet of network traffic or a block of a computer file. The checksum is calculated by applying a mathematical algorithm to the data, and it is designed to detect any changes to the data that occur during transmission or storage.

The most common algorithm used in a CRC is a polynomial function, which operates on the binary data as if it was a single large binary number. The data is divided by a fixed polynomial, and the remainder is used as the checksum. When the data is received or read, the same polynomial is used to perform the division again, and the remainder is compared to the original checksum. If the remainder is different, it indicates that the data has been corrupted.

CRCs are widely used in digital communications, such as in Ethernet and other networking protocols, as well as in storage devices like hard drives and flash drives. Because of their simplicity and efficiency, they are also used in many other applications such as in digital audio and video, financial transactions, and industrial control systems.

CRCs are not foolproof and can't guarantee error-free data transfer, but they significantly increase the chances of detecting errors and can be very useful in detecting accidental errors caused by noise on a communication channel or other sources.

Data Integrity in CRC

CRCs are often used to ensure the integrity of data, which means that the data has not been tampered with or corrupted during transmission or storage. By attaching a checksum to the data and then checking the checksum when the data is received or read, a CRC can detect any changes to the data that have occurred during transmission or storage.

However, the data integrity provided by CRCs can be limited in some ways. For example, if an attacker knows the algorithm used to calculate the checksum, they can potentially change the data in such a way that the checksum still matches the original, meaning the integrity check would pass despite the data being tampered. This is known as a "CRC attack" or "CRC collision". To mitigate this issue, a more secure hash function such as SHA-256 is often used in conjunction with the CRC to ensure the integrity of the data.

Another limitation of the CRC is that it can only detect errors, it can't correct them. The receiver must request retransmission of the corrupted data. Additionally, the length of the check value is typically much smaller than the data, which means that it is not guaranteed to detect all errors. The longer the check value, the more errors it can detect, but also the more storage space it will take.

It is also worth noting that a CRC is not a cryptographic hash function, it is a checksum algorithm, meaning that it is not designed to be resistant to tampering, but to detect accidental errors. For cryptographic purposes, it is recommended to use cryptographic hash functions such as SHA-256, SHA-512, etc.

Examples of CRC

There are many examples of the use of cyclic redundancy check (CRC) in different types of systems and protocols. Some common examples are as follows:

• Ethernet: The most common use of CRC is in Ethernet networks, where the CRC is used to detect errors in packets of data that are transmitted over the network.
• USB: USB flash drives and other USB storage devices use CRCs to detect errors in the data that is written to and read from the device.
• File formats: Some file formats, such as PNG and Gzip, use CRCs to detect errors in the data that makes up the file.
• Disk storage: Hard drives and other types of disk storage use CRCs to detect errors in the data that is written to and read from the disk.
• Industrial control systems: In many industrial control systems, such as those used in factories and power plants, CRCs are used to detect errors in the data that is sent between different components of the system.
• Digital audio and video: Some digital audio and video formats use CRCs to detect errors in the data that makes up the audio or video file.
• Financial transactions: Some financial transaction systems use CRCs to detect errors in the data that is sent between different components of the system.

Algorithm of CRC

The following steps are used in CRC algorithm:

• The data to be transmitted or stored is divided into a number of fixed-size blocks.
• A fixed-size check value, or "CRC code," is calculated for each block of data using a polynomial function. This is typically done by performing a bitwise exclusive-or (XOR) operation on the data and a predefined polynomial.
• The calculated check value is appended to the end of each block of data.
• The data, including the check value, is transmitted or stored.
• When the data is received or read, the check value is recalculated using the same polynomial function.
• The recalculated check value is compared to the original check value. If the two values are the same, the data is considered to be intact and error-free. If the two values are different, it indicates that an error has occurred and corrective action can be taken.

The polynomial function and length of the check value can vary depending on the specific implementation of the CRC algorithm. Some of the most commonly used polynomial functions include the following:

• CRC-16 (16-bit),
• CRC-32 (32-bit) and
• CRC-64 (64-bit)

These polynomials are widely used and standardized, and the choice of polynomial can affect the probability of undetected errors. Additionally, some implementations include additional steps such as bit-reversal or complementing the data before the CRC calculation.