💻 CRC-Prüfsumme

Die GF(2)-Arithmetik hat keine Überträge, was die CRC-Berechnung in Hardware und Software extrem effizient macht: Addition wird zu XOR, Multiplikation wird zu UND, und Polynomdivision kann als linear rückgekoppeltes Schieberegister (LFSR) implementiert werden, das einmal pro Bit getaktet wird. Die algebraische Struktur von GF(2)-Polynomen macht auch formale Fehlererkennungsbeweise mit Codierungstheorie handhabbar.

CRC-32 erkennt: alle Einzelbitfehler; alle Doppelbitfehler (für Nachrichten kürzer als 2³² − 1 Bit); alle ungeraden Anzahlen von Bitfehlern (weil 0x04C11DB7 durch (x+1) teilbar ist); alle Bündelfehler der Länge ≤ 32 Bit; und einen großen Anteil (1 − 2⁻³²) längerer Bündelfehler. Es garantiert NICHT die Erkennung aller zufälligen Mehrbitfehler — dafür werden stärkere Codes wie Reed-Solomon verwendet.

Ein LFSR ist eine Kette von Flipflops, deren Rückkopplungsabgriffe den 1-Bits des Generatorpolynoms entsprechen. Jeder Taktzyklus schiebt ein Eingabebit ein und XOR-verknüpft es mit der Rückkopplung von den Abgriffen. Nachdem alle Datenbits durchgetaktet wurden, ist der Registerinhalt der CRC-Rest. Dies verarbeitet ein Bit pro Zyklus bei voller Leitungsgeschwindigkeit — Milliarden von Bits pro Sekunde in modernen Ethernet-ASICs.

Es gibt mehrere CRC-32-Varianten: die Ethernet/ZIP/PNG-Variante (Polynom 0x04C11DB7, Anfangswert 0xFFFFFFFF, gespiegelte Ein-/Ausgabe, abschließendes XOR 0xFFFFFFFF) und die Castagnoli-Variante CRC-32C (Polynom 0x1EDC6F41), verwendet in iSCSI, SCTP und ext4. Das Mischen von Varianten verursacht Prüfsummenabweichungen. Das Rocksoft-Modell definiert 7 Parameter, die einen CRC-Algorithmus vollständig spezifizieren.

Nein. CRC ist ein einfacher fehlererkennender Code, kein kryptografischer Hash. Ein Angreifer, der eine Nachricht ändern kann, kann trivial den CRC neu berechnen und eine gültige Prüfsumme fälschen. Für Manipulationserkennung in Sicherheitskontexten verwenden Sie einen Nachrichtenauthentifizierungscode (MAC) wie HMAC-SHA256 oder einen kryptografischen Hash wie SHA-3. CRC ist nur für die Erkennung zufälliger Beschädigungen in vertrauenswürdigen Kanälen geeignet.

Bitweise Verarbeitung ist in Software langsam. Stattdessen wird eine Nachschlagetabelle mit 256 Einträgen vorberechnet: table[b] = CRC eines einzelnen Bytes b, gefolgt von Nullauffüllung. Die Verarbeitung jedes Eingabebytes erfordert dann nur einen Tabellenzugriff, ein XOR und eine Verschiebung — was tabellenbasiertes CRC-32 auf modernen CPUs mehrere GB/s erreichen lässt. x86-Prozessoren mit dem SSE4.2-Befehlssatz haben einen dedizierten CRC32-Befehl für CRC-32C.

Die Zahl gibt den Grad des Generatorpolynoms und die Breite der Prüfsumme in Bit an. CRC-8 (8-Bit-Rest) wird in eingebetteten Protokollen wie SMBus und 1-Wire verwendet, wo Codegröße knapp ist. CRC-16 (16-Bit) ist in seriellen Protokollen (MODBUS, USB-Datenpakete) üblich und erkennt alle Bündelfehler bis zu 16 Bit. CRC-32 (32-Bit) gibt eine Falsch-Negativ-Wahrscheinlichkeit von 1 zu 4 Milliarden und ist der Standard für Dateisysteme und Netzwerkpakete.

Ja — Kollisionen existieren, weil CRC beliebig lange Nachrichten auf eine Prüfsumme fester Länge abbildet (z. B. 32 Bit). Bei einem gültigen Paar aus Nachricht und CRC kann man immer eine andere Nachricht mit derselben CRC konstruieren, indem man sorgfältig gewählte Bits anhängt. Die Wahrscheinlichkeit, dass eine zufällige Beschädigung dieselbe CRC-32 ergibt, ist 2⁻³² ≈ 2,3×10⁻¹⁰, was für Kommunikation vernachlässigbar ist, aber nicht für gegnerische Szenarien.

Das Generatorpolynom g(x) bestimmt die Fehlererkennungseigenschaften der CRC. Ein gutes Generatorpolynom muss primitiv sein (um alle Fehler mit ungerader Bitzahl zu erkennen) oder mindestens (x+1) als Faktor enthalten. Das CRC-32-Polynom 0x04C11DB7 wurde entworfen, um die Bündelfehlererkennung für Ethernet-Rahmenlängen zu maximieren. Die Auswahl optimaler Polynome für bestimmte Codelängen und Fehlermodelle ist ein aktives Forschungsgebiet der Codierungstheorie.