Prüfsummen sind keine Hashes: CRC-32, Adler-32 und wofür sie da sind

Drei Aufgaben, die alle eine kurze Zahl liefern

Die Verwirrung beginnt bei der Ausgabe. CRC-32, Adler-32, FNV-1a, MurmurHash3, MD5 und SHA-256 nehmen beliebige Bytes und liefern eine Zahl fester Größe — in einer API wirken sie austauschbar. Sind sie nicht. Sie wurden gegen drei völlig verschiedene Bedrohungsmodelle entworfen, und die falsche Familie erzeugt Fehler, die still bleiben, bis sie katastrophal werden.

Eine Prüfsumme beantwortet: Haben sich diese Daten unterwegs zufällig verändert? Dein Gegner ist ein kosmisches Teilchen, ein grenzwertiges Kabel, ein abgebrochener Schreibvorgang, ein schwächelnder Plattensektor. Dieser Gegner ist zufällig und passt sich nicht an. CRC-32 und Adler-32 sind Prüfsummen. Ein kryptografischer Hash beantwortet eine härtere Frage: Kann jemand mit aller Zeit und Hardware, die er kaufen kann, eine zweite Eingabe mit derselben Ausgabe finden? Sein Gegner ist ein Mensch mit Budget. MD5, SHA-1 und SHA-256 sind Versuche dazu — mit unterschiedlichem Erfolg, den der Begleitartikel zur Hash-Wahl behandelt.

Die dritte Aufgabe wird vergessen. Ein Hashtabellen-Hash beantwortet: Wie mache ich aus diesem Schlüssel schnell und gleichmäßig einen Bucket-Index? Sein Gegner ist nominell niemand — bis die Schlüssel aus HTTP-Anfrageparametern stammen, dann ist der Gegner, wer sie schickt. FNV-1a und MurmurHash3 wohnen hier. Sie sind hervorragend in ihrer Aufgabe und bieten bei den anderen beiden keinerlei Schutz.

CRC-32 ist linear, und hier ist die Kollision

CRC-32 ist Polynomdivision über GF(2), und Division ist linear. Konkret gilt für drei beliebige gleich lange Nachrichten: crc(a XOR b XOR c) = crc(a) XOR crc(b) XOR crc(c). An fünf zufälligen 32-Byte-Tripeln geprüft, stimmte es jedes Mal exakt — ein Tripel ergab etwa auf beiden Seiten 8975e151. Kein kryptografischer Hash besitzt eine solche Identität, und diese eine algebraische Tatsache ist der ganze Unterschied zwischen den beiden Familien.

Linearität heißt, dass man eine Kollision lösen statt suchen kann. Nimm eine Nachricht, die ein Angreifer ändern will, gib ihr irgendwo ein paar Byte Spielraum — Füllbytes, ein Kommentarfeld, einen reservierten Header, abschließende Leerzeichen — und der nötige Spielraumwert ist die Lösung eines linearen Systems mit 32 Unbekannten über GF(2). Gauß-Elimination erledigt das in Mikrosekunden.

Wirklich durchgeführt: Die Originalnachricht lautete config: mode=safe, retries=3, pad=...... mit CRC-32 78aa94ad. Die Fälschung sollte config: mode=open, retries=9, pad= lauten, gefolgt von sechs noch zu bestimmenden Füllbytes. Deren Lösung ergab config: mode=open, retries=9, pad=!9[noI — dieselbe Länge von 40 Byte, 11 abweichende Bytes und dieselbe CRC-32 78aa94ad. Fünfundzwanzig Füllkandidaten wurden probiert, bis einer vollständig druckbar herauskam; das ganze Programm lief in 0,11 Sekunden. Die SHA-256-Digests der beiden Nachrichten beginnen mit d9cddeec und 6b7bdc0c — so sieht eine Funktion ohne Linearitätsidentität aus.

Nichts davon brauchte Kryptoanalyse, GPU oder Wörterbuch. Es brauchte das Wissen, dass CRC-32 eine lineare Abbildung ist, und sechs Byte der Nachricht. Deshalb beweist ein CRC, der eine Datei über einen unsicheren Kanal begleitet, nichts gegen Manipulation: Wer die Datei ändern kann, kann den CRC mitändern, und selbst wenn der CRC getrennt geliefert und unantastbar ist, lässt sich immer noch eine andere Datei bauen, die ihn erzeugt.

Worin CRC-32 wirklich hervorragend ist

Nichts davon macht CRC-32 zu einer schlechten Funktion. Es macht sie zu einer Funktion mit einer anderen Aufgabe, und darin ist sie nahezu optimal. Deine Garantien sind nicht statistisch, sondern bewiesen: Sie erkennt jeden Einbitfehler, jeden Zweibitfehler innerhalb einer enormen Nachrichtenlänge, jeden Fehler, der eine ungerade Anzahl Bits betrifft, und jeden Bündelfehler bis 32 Bit — die Länge der Prüfsumme selbst.

Gemessen statt behauptet: In einer 200-Byte-Nachricht änderten alle 1 600 möglichen Einbit-Kippungen den CRC, und alle 1 279 200 möglichen Zweibit-Kippungen ebenfalls — keine entkam. Auf einem 1500-Byte-Rahmen in Ethernet-Größe wurden 200 000 zufällige Bündelfehler bei je sechs Breiten (8, 16, 32, 33, 40 und 64 Bit) sämtlich erkannt. Bündel über 32 Bit sind nicht garantiert, nur überwältigend wahrscheinlich: Die Entkommenswahrscheinlichkeit liegt bei etwa 2 hoch minus 32, also eins zu 4,29 Milliarden — deshalb fand keiner der 200 000 Versuche etwas.

Deshalb steckt CRC-32 in Ethernet-Rahmen, in gzip-Trailern, in PNG-Chunks, in ZIP-Einträgen und in SATA. Das sind alles Kanäle, deren Fehlermodus eine physische Störung ist, die einen zusammenhängenden Lauf verfälschter Bits erzeugt — genau die Fehlerklasse, die CRC-Polynome mit Sicherheit fangen sollen. Ein kryptografischer Hash finge sie auch, aber zu mehrfachen Kosten und ohne bewiesene, nur mit probabilistischer Garantie.

Adler-32: billiger zu berechnen, schwächer beim Erkennen

Adler-32, in RFC 1950 für das zlib-Format definiert, besteht aus zwei laufenden Summen modulo 65 521: einer einfachen Summe der Bytes und einer Summe dieser Teilsummen. Es sollte deutlich billiger sein als ein CRC und dabei die meisten derselben Fehler erkennen — keine Tabelle, nur Additionen. In der Praxis kostet die Modulo-Operation so viel, dass der versprochene Vorteil oft verpufft: In derselben JavaScript-Laufzeit auf demselben 64-MB-Puffer gemessen lief Adler-32 mit 174 MB/s gegen 262 MB/s bei CRC-32. Adler-32 war langsamer.

Es hat außerdem einen blinden Fleck, den man beweisen statt schätzen kann. Der Modul 65 521 ist die größte Primzahl unter 65 536. Erhöht man ein Byte um d und senkt ein anderes um d, bleibt die erste Summe unverändert, und die zweite ändert sich um d mal den Abstand zwischen beiden — was modulo 65 521 genau dann verschwindet, wenn dieser Abstand 65 521 beträgt. Jede Nachricht über rund 64 Kilobyte hat also kompensierende Änderungspaare, die Adler-32 überhaupt nicht sieht.

An einem 70 000-Byte-Puffer vorgeführt: Byte 100 um 7 erhöhen und Byte 65 621 um 7 senken ließ Adler-32 bei 3fee717c, Byte für Byte identisch mit dem sauberen Wert, während CRC-32 von abc586b8 auf 43c209f4 wechselte. Adler-32 ist auch bei kurzen Eingaben schwach — 200 000 zufällige Vier-Byte-Eingaben ergaben nur 152 364 verschiedene Adler-32-Werte, wo eine ideale 32-Bit-Funktion etwa 199 995 geliefert hätte. RFC 1950 vermerkt die Schwäche bei kurzen Nachrichten selbst, weshalb zlib-Ströme sie über ganze Ströme statt winziger Datensätze führen.

FNV-1a und MurmurHash3: die dritte Kategorie

FNV-1a und MurmurHash3 sind weder Prüfsummen noch kryptografische Hashes. Sie sind nichtkryptografische Hashes für Hashtabellen, Bloomfilter und Sharding, wo gleichmäßige Verteilung zu geringstmöglichen Kosten pro Byte gefragt ist. Das leisten sie. In derselben Laufzeit und auf demselben Puffer lief MurmurHash3 mit 730 MB/s und FNV-1a mit 520 MB/s, gegen 262 MB/s bei CRC-32.

Kollisionen darin sind trivial zu finden, und die Übung dauert unter zwei Sekunden. Beim Durchzählen siebenstelliger Zeichenketten kollidierte FNV-1a 32 bei 7yzlaaa und e6apaaa, die beide auf 15111984 hashen, nach 700 997 Kandidaten und 680 Millisekunden. MurmurHash3 mit Seed 0 kollidierte bei rynbaaa und ciaabaa, beide auf e5407f96, nach 1 679 907 Kandidaten und 1,6 Sekunden. Das ist zu erwarten — 32 Bit bedeuten eine Geburtstagskollision um 77 163 Elemente — und kein Mangel. Zum Mangel wird es, wenn jemand die Schlüssel wählt.

Hash Flooding ist der daraus folgende Angriff, und er lässt sich leicht reproduzieren. 20 000 Schlüssel zu sammeln, deren FNV-1a-Wert in Bucket 0 einer Tabelle mit 4 096 Buckets fällt, kostete den Bruchteil einer Sekunde Probedivision. Ihr Einfügen ließ die Tabelle zu einer einzigen Kette mit 20 000 Einträgen kollabieren, während gewöhnliche Schlüssel eine längste Kette von 12 ergaben. Zwanzigtausend Nachschlagevorgänge dauerten dann 1 397,9 statt 11,5 Millisekunden — eine 121-fache Verlangsamung, von konstanter zu linearer Zeit. Jede Anfrage, die eine solche Tabelle berührt, wird zum Verstärker: genau die Denial-of-Service-Klasse, die Sprachlaufzeiten zu zufällig geseedetem SipHash für ihre eingebauten Wörterbücher trieb.

Wählen, in einer Frage

Frage, wer profitiert, wenn zwei verschiedene Eingaben denselben Wert liefern. Lautet die Antwort niemand — du fängst abgebrochene Kopien, wackelige Kabel, beschädigte Archive, Bitfäule auf einer Sicherungsplatte —, ist eine Prüfsumme richtig und CRC-32 der vernünftige Standard. Sie ist klein, sie ist überall, sie hat bewiesene Garantien gegen genau die Fehlerformen, die Hardware erzeugt, und native Implementierungen sind extrem schnell: Nodes zlib-CRC-32 erreichte auf demselben Puffer 2 248 MB/s, dreimal die 763 MB/s von SHA-256.

Lautet die Antwort jemand — ein Download über ein Netz, das du nicht kontrollierst, eine Signatur, eine Lizenzdatei, eine Update-Nutzlast, Deduplizierung nutzergelieferter Objekte, ein Cache, dessen Schlüssel ein Nutzer beeinflussen kann —, brauchst du einen kryptografischen Hash, und das heißt heute SHA-256. Die Kosten sind real, aber gering: 763 MB/s ist immer noch schneller als die meisten Platten und Netze, und es ist die einzige Familie in diesem Vergleich, bei der sich eine zweite Eingabe mit derselben Ausgabe nicht einfach ausrechnen lässt.

Und wenn der Wert deinen Prozess nie verlässt — Bucket-Index, Bloomfilter, Shard-Auswahl —, nimm einen Hashtabellen-Hash, aber stelle eine Anschlussfrage: Kann ein Angreifer die Schlüssel wählen? Wenn ja, willst du eine geschlüsselte, zufällig geseedete Funktion wie SipHash, kein FNV-1a mit festem Seed. Die meisten modernen Sprachlaufzeiten tun das für ihre eingebauten Maps bereits; die Gefahr ist eine selbstgebaute Tabelle im Anwendungscode, die es nicht tut.

Häufige Fragen

Ist CRC-32 eine Hashfunktion?

Im weitesten Sinne ja — sie bildet beliebige Eingaben auf eine feste 32-Bit-Ausgabe ab —, doch sie so zu nennen lädt zu genau dem Fehler ein, dessentwegen dieser Artikel existiert. CRC-32 ist eine lineare Funktion, berechnet als Rest einer Polynomdivision über GF(2). Diese Linearität liefert die Identität crc(a XOR b XOR c) = crc(a) XOR crc(b) XOR crc(c), hier an zufälligen Tripeln geprüft, und aus ihr folgt eine Kollision durch Lösen eines linearen Systems mit 32 Unbekannten statt durch Suchen. Ein kryptografischer Hash wird gezielt so gebaut, dass es keine solche algebraische Abkürzung gibt; das leistet das Wort kryptografisch. CRC-32 ist also eine Prüfsumme, und das brauchbare Denkmodell lautet sehr guter Fehlererkennungscode statt schwacher Hash. Nennt eine Bibliothek, eine API oder ein Code-Review sie Hash, prüfe, auf welche Eigenschaft tatsächlich gebaut wird: Eindeutigkeit gegen einen Gegner ist die eine, die sie nicht liefern kann, und genau die wird unterstellt.

Kann ich mit einem CRC-32 einen Download prüfen?

Das hängt ganz davon ab, wogegen du prüfst. Kontrollierst du, ob die angekommenen Bytes den abgesandten entsprechen — dass die Verbindung nicht mittendrin abriss, das Archiv nicht abgeschnitten ist, die Platte schrieb, was sie bekam —, ist ein CRC-32 genau das richtige Werkzeug und fängt jeden realistischen Transportfehler. Deshalb trägt jeder ZIP-Eintrag und jeder gzip-Strom einen. Fragst du dagegen, ob die Datei die vom Herausgeber gemeinte ist, beantwortet ein CRC-32 gar nichts. Wer die Datei austauschen kann, kann auch den CRC austauschen, und selbst wo der CRC getrennt veröffentlicht und unantastbar ist, lässt sich eine andere passende Datei bauen — dieser Artikel hat genau das in 0,11 Sekunden getan. Für die Prüfung des Herausgebers brauchst du einen kryptografischen Digest, veröffentlicht über einen Kanal, den der Angreifer nicht kontrolliert, und idealerweise eine Signatur darüber statt nur des Digests.

Warum nutzt gzip CRC-32 und zlib Adler-32?

Beide Formate umhüllen dieselben DEFLATE-komprimierten Daten und unterscheiden sich hauptsächlich im Container. RFC 1952 schreibt einen CRC-32 im gzip-Trailer vor, RFC 1950 einen Adler-32 im zlib-Trailer. Die damalige Begründung war Tempo: Adler-32 braucht nur Additionen und ein Modulo, keine 256-Einträge-Tabelle, war auf den Prozessoren der frühen 1990er also spürbar billiger pro Byte, und zlib zielte auf Kontexte, in denen die Prüfsummenkosten gegenüber der Kompression ins Gewicht fielen. Dieser Vorteil ist weitgehend verpufft. Moderne CRC-32-Implementierungen nutzen Slicing-by-8-Tabellen oder eigene CPU-Befehle, und in den Messungen hier erreichte Nodes nativer CRC-32 2 248 MB/s, während ein direkter Adler-32 in derselben JavaScript-Laufzeit bei 174 MB/s gegen 262 MB/s für CRC-32 blieb. Die Formate bleiben wie spezifiziert, weil ein Algorithmuswechsel jeden bestehenden Leser bricht, und beide reichen für ihre Aufgabe, zufällige Korruption in einem komprimierten Strom zu erkennen.

Wie wahrscheinlich ist eine zufällige CRC-32-Kollision?

Für eine einzelne beschädigte Nachricht ist die Antwort hervorragend: Bündel bis 32 Bit werden nie übersehen, darüber hinaus liegt die Entkommenswahrscheinlichkeit bei etwa eins zu 4 294 967 296. Für eine Dateisammlung ist es viel schlechter, als die Intuition nahelegt, denn der Geburtstagseffekt greift. Zwei zufällige 32-Bit-Werte kollidieren mit Wahrscheinlichkeit eins zu 4,29 Milliarden, aber eine Menge von n Werten enthält n(n−1)/2 Paare, sodass die 50-Prozent-Marke bei 77 163 Elementen liegt. Zehntausend Dateien tragen schon 1,16 Prozent Chance, dass ein Paar denselben CRC-32 hat, hunderttausend tragen 68,8 Prozent. Das zählt, wenn du CRC-32 als Deduplizierungsschlüssel oder inhaltsadressierten Bezeichner über ein großes Korpus verwendest, wo eine Kollision still eine von zwei verschiedenen Dateien verwirft. Für eine Integritätsprüfung Datei für Datei gegen Transportschäden ist der Geburtstagseffekt irrelevant, denn du vergleichst einen Wert mit einem erwarteten, statt eine Population nach Treffern zu durchsuchen.

Sind FNV-1a und MurmurHash3 bei nutzergelieferten Schlüsseln sicher?

Ohne zufälligen Seed nein. Beide sind standardmäßig schlüssellos, ihre Ausgabe ist also eine öffentliche Funktion, die jeder offline berechnen kann. Damit kann ein Angreifer Schlüssel vorberechnen, die im selben Bucket landen, und sie alle auf einmal schicken — Hash Flooding. Hier auf einer Tabelle mit 4 096 Buckets reproduziert: 20 000 gefertigte Schlüssel hashten alle in Bucket 0, machten aus einer längsten Kette von 12 eine einzige Kette von 20 000 und ließen 20 000 Nachschlagevorgänge 1 397,9 statt 11,5 Millisekunden dauern — 121-mal langsamer, und das Sammeln dieser Schlüssel kostete weniger als eine Sekunde Aufwand. Die Lösung ist kein stärkerer schlüsselloser Hash, sondern ein geschlüsselter mit zufälligem Seed pro Prozess, der Vorberechnung unmöglich macht. SipHash ist die Standardwahl und wird von den meisten Sprachlaufzeiten intern für Wörterbücher genutzt. Kommen deine Schlüssel aus Konfiguration, aus deiner eigenen Datenbank oder von irgendwo, wo ein Angreifer nichts beeinflussen kann, bleiben seedlose FNV-1a und MurmurHash3 völlig in Ordnung und sehr schnell.

Was sollte ich für Cache-Schlüssel und Deduplizierung nehmen?

Entscheide danach, wer den Inhalt liefert und was eine falsche Antwort kostet. Für einen In-Memory-Cache, dessen Schlüssel du selbst erzeugst — eine Query-Form, ein gerenderter Templatename, ein interner Bezeichner —, ist ein schneller nichtkryptografischer Hash richtig, und MurmurHash3 mit 730 MB/s ist eine gute Wahl. Für Deduplizierung über ein Korpus, das du kontrollierst, wo eine Kollision stillschweigend eines von zwei verschiedenen Objekten behält, sind 32 Bit zu schmal: Der 50-Prozent-Geburtstagspunkt liegt bei 77 163 Elementen. Wechsle zu einem 64- oder 128-Bit-Hash oder zu einem gekürzten SHA-256. Überall dort, wo Nutzer den Inhalt liefern — hochgeladene Dateien, nutzergenerierte Objekte, ein inhaltsadressierter Speicher, ein von mehreren Mandanten geteilter Cache —, nimm SHA-256 in voller Länge. Dort ist eine Kollision kein Unfall, sondern eine Fähigkeit: Sie erlaubt, ein gewähltes Objekt unter einen bereits existierenden Bezeichner zu legen, und nur ein kryptografischer Hash macht das undurchführbar. Die Kosten sind gering: Die hier gemessenen 763 MB/s übertreffen die Speicherschicht, in die du schreibst.