Checksums zijn geen hashes: CRC-32, Adler-32 en waar ze voor zijn
Gepubliceerd op 16-5-2025 · 16 min leestijd · Ontwikkelaarstools
Daniel Okonkwo — Front-enddeveloper en techredacteur bij OneKitly
Webprestaties · Bestandsformaten
Getoetst aan 5 bronnen
Een checksum spoort toevallige corruptie op; een cryptografische hash weerstaat een doelbewuste aanvaller; een hashtabelhash spreidt sleutels gelijkmatig en goedkoop. CRC-32 is de eerste soort en is wiskundig lineair: voor berichten van gelijke lengte is crc(a XOR b XOR c) gelijk aan crc(a) XOR crc(b) XOR crc(c). Die identiteit, hier op vijf willekeurige drietallen nagerekend, laat iedereen een tweede bericht met dezelfde CRC-32 construeren door een klein stelsel over GF(2) op te lossen. Precies dat doen leverde twee leesbare tekenreeksen van 40 bytes op — „config: mode=safe, retries=3, pad=......” en „config: mode=open, retries=9, pad=!9[noI” — die in 11 bytes verschillen en de CRC-32-waarde 78aa94ad delen. De hele constructie kostte 0,11 seconde. Hun SHA-256-digests zijn natuurlijk volstrekt verschillend. Waar CRC-32 superb in is, is waarvoor hij is ontworpen: elk van de 1.600 enkelbitsomslagen en 1.279.200 dubbelbitsomslagen in een bericht van 200 bytes werd opgespoord, en 200.000 willekeurige burstfouten misten er geen een. Adler-32 is in principe sneller maar zwakker, met een aantoonbare blinde vlek bij een byte-afstand van 65.521. FNV-1a en MurmurHash3 zijn weer een derde categorie — hashtabelhashes, zonder seed en triviaal te overspoelen. Gebruik CRC-32 tegen ruis, SHA-256 tegen mensen.
Een checksum vangt ongelukken. Een cryptografische hash weerstaat een aanvaller. Een hashtabelhash spreidt sleutels. Drie verschillende taken, drie verschillende families — en hier is een CRC-32-botsing die in 0,11 seconde met de hand is geconstrueerd, om precies te laten zien waarom je de een niet door de ander kunt vervangen.
Drie taken die alle drie een kort getal opleveren
De verwarring begint bij de uitvoer. CRC-32, Adler-32, FNV-1a, MurmurHash3, MD5 en SHA-256 nemen allemaal willekeurige bytes en geven een getal van vaste grootte terug, dus zien ze in een API uitwisselbaar uit. Dat zijn ze niet. Ze zijn tegen drie volstrekt verschillende dreigingsmodellen ontworpen, en de verkeerde familie kiezen levert storingen op die stil blijven tot ze catastrofaal zijn.
Een checksum beantwoordt: is deze data onderweg hierheen per ongeluk veranderd? Zijn tegenstander is een kosmisch deeltje, een kabel op de grens, een afgebroken schrijfactie, een schijfsector die zacht wordt. Die tegenstander is willekeurig en past zich niet aan. CRC-32 en Adler-32 zijn checksums. Een cryptografische hash beantwoordt een zwaardere vraag: kan iemand, met zoveel tijd en hardware als hij kan kopen, een tweede invoer met deze uitvoer vinden? Zijn tegenstander is een persoon met een budget. MD5, SHA-1 en SHA-256 zijn pogingen daartoe — met wisselend succes, waar het bijbehorende stuk over hashkeuze op ingaat.
De derde taak is de taak die mensen vergeten. Een hashtabelhash beantwoordt: hoe zet ik deze sleutel snel en gelijkmatig om in een bucketindex? Zijn tegenstander is nominaal niemand — tot de sleutels uit HTTP-parameters komen, waarna de tegenstander is wie ze verstuurt. FNV-1a en MurmurHash3 wonen hier. Ze zijn uitstekend in hun taak en bieden bij de andere twee geen enkele bescherming.
CRC-32 is lineair, en hier is de botsing
CRC-32 is polynoomdeling over GF(2), en delen is lineair. Concreet: voor elke drie berichten van gelijke lengte is crc(a XOR b XOR c) gelijk aan crc(a) XOR crc(b) XOR crc(c). Dat op vijf willekeurige drietallen van 32 bytes testen gaf elke keer een exacte overeenkomst — één drietal gaf bijvoorbeeld 8975e151 aan beide zijden. Geen enkele cryptografische hash heeft zo'n identiteit, en dat ene algebraïsche feit is het hele verschil tussen de twee families.
Lineariteit betekent dat je een botsing kunt oplossen in plaats van ernaar te zoeken. Neem een bericht dat een aanvaller wil wijzigen, geef het ergens een paar bytes ruimte — opvulling, een commentaarveld, een gereserveerde header, witruimte aan het eind — en de vereiste opvulwaarde is de oplossing van een lineair stelsel met 32 onbekenden over GF(2). Gauss-eliminatie doet dat in microseconden.
Echt gedaan: het oorspronkelijke bericht was „config: mode=safe, retries=3, pad=......” met CRC-32 78aa94ad. De vervalsing moest „config: mode=open, retries=9, pad=” gaan luiden, gevolgd door zes nog te bepalen opvulbytes. Die bytes oplossen leverde „config: mode=open, retries=9, pad=!9[noI” op — dezelfde lengte van 40 bytes, 11 bytes anders, en dezelfde CRC-32 78aa94ad. Er waren vijfentwintig kandidaat-opvullingen geprobeerd voordat er een volledig afdrukbaar uitkwam; het hele programma liep in 0,11 seconde. De SHA-256-digests van de twee berichten beginnen met d9cddeec en 6b7bdc0c, en dat is hoe een functie zonder lineariteitsidentiteit eruitziet.
Hier was geen cryptanalyse, geen GPU en geen woordenlijst voor nodig. Er was voor nodig dat je weet dat CRC-32 een lineaire afbeelding is, en dat je zes bytes van het bericht bezit. Daarom bewijst een CRC die een bestand over een niet-vertrouwd kanaal begeleidt niets over manipulatie: een aanvaller die het bestand kan veranderen, kan de CRC laten kloppen, en zelfs als de CRC apart wordt geleverd en onaantastbaar is, kan hij nog altijd een ander bestand maken dat hem oplevert.
Waar CRC-32 werkelijk uitstekend in is
Niets van het bovenstaande maakt CRC-32 een slechte functie. Het maakt hem een functie die een andere taak doet, en in die taak is hij vrijwel optimaal. Zijn garanties zijn niet statistisch maar bewezen: hij spoort elke enkelbitsfout op, elke tweebitsfout binnen een enorme berichtlengte, elke fout die een oneven aantal bits raakt, en elke burstfout tot 32 bits — de lengte van de checksum zelf.
Gemeten in plaats van beweerd: bij een bericht van 200 bytes veranderden alle 1.600 mogelijke enkelbitsomslagen de CRC, en alle 1.279.200 mogelijke dubbelbitsomslagen ook — er ontsnapte er niet één. Op een frame ter grootte van een ethernetframe van 1.500 bytes werden 200.000 willekeurige burstfouten bij elk van zes breedtes (8, 16, 32, 33, 40 en 64 bits) alle opgespoord. Bursts langer dan 32 bits zijn niet gegarandeerd, alleen overweldigend waarschijnlijk: de ontsnappingskans is ongeveer 2 tot de macht min 32, ofwel één op 4,29 miljard, en daarom vonden 200.000 proeven niets.
Daarom zit CRC-32 in ethernetframes, in de staart van een gzip-stroom, in PNG-chunks, in ZIP-items en in SATA. Dat zijn alle kanalen waarvan de storingsvorm een fysieke hapering is die een aaneengesloten reeks verminkte bits oplevert — precies de foutklasse die CRC-polynomen met zekerheid moeten vangen. Een cryptografische hash zou ze ook vangen, maar tegen een paar keer de kosten en zonder bewezen garantie, alleen een waarschijnlijkheidsgarantie.
Adler-32: goedkoper te berekenen, zwakker in opsporen
Adler-32, gedefinieerd in RFC 1950 voor het zlib-formaat, is twee lopende sommen modulo 65.521: een gewone som van de bytes, en een som van die deelsommen. Hij is ontworpen om veel goedkoper te zijn dan een CRC terwijl hij de meeste van dezelfde fouten opspoort — geen opzoektabel, alleen optellen. In de praktijk kost de modulobewerking genoeg dat het beloofde voordeel vaak verdampt: gemeten in dezelfde JavaScript-runtime op dezelfde buffer van 64 MB liep Adler-32 op 174 MB/s tegen de 262 MB/s van CRC-32. Adler-32 was langzamer.
Hij heeft ook een blinde vlek die je kunt bewijzen in plaats van schatten. De modulus 65.521 is het grootste priemgetal onder 65.536. Verhoog je de ene byte met d en verlaag je een andere met d, dan blijft de eerste som onveranderd, en verandert de tweede som met d maal de afstand ertussen — en die verdwijnt modulo 65.521 precies wanneer die afstand 65.521 is. Elk bericht langer dan ongeveer 64 kilobyte heeft dus compenserende paren veranderingen die Adler-32 helemaal niet kan zien.
Gedemonstreerd op een buffer van 70.000 bytes: byte 100 met 7 verhogen en byte 65.621 met 7 verlagen liet Adler-32 op 3fee717c staan, byte voor byte identiek aan de schone waarde, terwijl CRC-32 van abc586b8 naar 43c209f4 bewoog. Adler-32 is ook zwak op korte invoer — 200.000 willekeurige invoeren van vier bytes leverden maar 152.364 verschillende Adler-32-waarden op, waar een ideale 32-bitsfunctie er ongeveer 199.995 zou hebben opgeleverd. RFC 1950 noemt die zwakte voor korte berichten zelf, en daarom dragen zlib-stromen hem over hele stromen in plaats van over kleine records.
FNV-1a en MurmurHash3: de derde categorie
FNV-1a en MurmurHash3 zijn geen checksums en geen cryptografische hashes. Het zijn niet-cryptografische hashes, ontworpen voor hashtabellen, bloomfilters en sharding, waar de eis een gelijkmatige verdeling tegen de laagst mogelijke kosten per byte is. Daar maken ze hun belofte waar. In dezelfde runtime en op dezelfde buffer liep MurmurHash3 op 730 MB/s en FNV-1a op 520 MB/s, tegen 262 MB/s voor CRC-32.
Botsingen erin zijn triviaal te vinden, en de oefening kost minder dan twee seconden. Bij het aflopen van tekenreeksen van zeven tekens botste FNV-1a 32 op „7yzlaaa” en „e6apaaa”, die beide op 15111984 uitkwamen, na 700.997 kandidaten en 680 milliseconden. MurmurHash3 met seed 0 botste op „rynbaaa” en „ciaabaa”, die beide op e5407f96 uitkwamen, na 1.679.907 kandidaten en 1,6 seconde. Dat is te verwachten — 32 bits betekent een verjaardagsbotsing rond 77.163 items — en het is geen gebrek. Het wordt een gebrek zodra iemand de sleutels kiest.
Hash flooding is de aanval die daaruit volgt, en ze is makkelijk na te doen. Twintigduizend sleutels verzamelen waarvan de FNV-1a-waarde in bucket 0 van een tabel met 4.096 buckets landt, kostte een fractie van een seconde proefdelen. Ze invoegen liet de tabel instorten tot één keten van 20.000 items, waar gewone sleutels een langste keten van 12 gaven. Twintigduizend opzoekingen kostten daarna 1.397,9 milliseconde in plaats van 11,5 — 121 keer langzamer, van constante tijd naar lineaire. Elk verzoek dat zo'n tabel raakt wordt een versterker, en dat is precies de klasse van denial-of-service die taalruntimes naar een willekeurig geseede SipHash voor hun ingebouwde woordenboeken heeft gedreven.
Kiezen, met één vraag
Vraag wie er baat bij heeft als twee verschillende invoeren dezelfde waarde opleveren. Is het antwoord niemand — je vangt afgebroken kopieën, wankele kabels, verminkte archieven, bitrot op een back-upschijf — dan is een checksum juist en is CRC-32 de verstandige standaard. Hij is klein, hij zit overal, hij heeft bewezen garanties tegen precies de foutvormen die hardware voortbrengt, en native implementaties zijn extreem snel: de CRC-32 van zlib in node haalde op dezelfde buffer 2.248 MB/s, drie keer de 763 MB/s van SHA-256.
Is het antwoord iemand — een download over een netwerk dat je niet beheert, een ondertekening, een licentiebestand, een update, deduplicatie van door gebruikers aangeleverde blobs, een cache met een sleutel die een gebruiker kan beïnvloeden — dan heb je een cryptografische hash nodig, en vandaag betekent dat SHA-256. De kosten zijn echt maar klein: 763 MB/s is nog steeds sneller dan de meeste schijven en de meeste netwerken, en het is de enige familie in deze vergelijking waarbij een tweede invoer met dezelfde uitvoer niet iets is wat iemand simpelweg kan oplossen.
En verlaat de waarde nooit je proces — een bucketindex, een bloomfilter, een shardkeuze — gebruik dan een hashtabelhash, maar stel een vervolgvraag: kan een aanvaller de sleutels kiezen? Kan hij dat, dan wil je een functie met sleutel en een willekeurige seed, zoals SipHash, en geen FNV-1a met een vaste seed. De meeste moderne taalruntimes doen dit al voor hun ingebouwde maps; het gevaar is een zelfgebouwde tabel in de applicatiecode die dat niet doet.
| Functie | Categorie | Uitvoer | Waarde voor de vossenzin | Doorvoer | Weerstaat een opzettelijke botsing? |
|---|---|---|---|---|---|
| CRC-32 | Checksum | 32 bits | 414fa339 | 262 MB/s in JS, 2.248 MB/s native | Nee — hier in 0,11 s opgelost |
| Adler-32 | Checksum | 32 bits | 5bdc0fda | 174 MB/s in JS | Nee — plus een blinde vlek bij 65.521 bytes |
| FNV-1a 32 | Hashtabelhash | 32 bits | 048fff90 | 520 MB/s in JS | Nee — botsing gevonden in 680 ms |
| MurmurHash3 32 | Hashtabelhash | 32 bits | 2e4ff723 | 730 MB/s in JS | Nee — botsing gevonden in 1,6 s |
| MD5 | Cryptografische hash (gebroken voor botsingen) | 128 bits | 9e107d9d372bb6826bd81d3542a419d6 | 483 MB/s native | Nee — botsingen sinds 2004 |
| SHA-256 | Cryptografische hash | 256 bits | d7a8fbb307d7809469ca9abcb0082e4f… | 763 MB/s native | Ja — er is nooit een botsing gevonden |
Veelgestelde vragen
- Is CRC-32 een hashfunctie?
- In de ruimste zin ja — hij zet willekeurige invoer om in een vaste uitvoer van 32 bits — maar hem zo noemen lokt precies de fout uit die dit hele artikel moet voorkomen. CRC-32 is een lineaire functie, berekend als de rest van een polynoomdeling over GF(2). Die lineariteit geeft hem de identiteit crc(a XOR b XOR c) = crc(a) XOR crc(b) XOR crc(c), hier op willekeurige drietallen nagerekend, en uit die identiteit volgt een botsing door een lineair stelsel met 32 onbekenden op te lossen in plaats van te zoeken. Een cryptografische hash is er juist op gebouwd dat zo'n algebraïsche sluiproute niet bestaat; dat is wat het woord cryptografisch doet. CRC-32 is dus een checksum, en het nuttige beeld is een heel goede foutopsporende code en niet een zwakke hash. Noemt een bibliotheek, een API of een codereview hem een hash, kijk dan welke eigenschap er werkelijk op wordt gebouwd: uniciteit tegen een aanvaller is de eigenschap die hij niet kan leveren, en het is de eigenschap die mensen aannemen.
- Kan ik een CRC-32 gebruiken om een download te verifiëren?
- Dat hangt volledig af van waartegen je verifieert. Controleer je of de bytes die zijn aangekomen overeenkomen met de bytes die zijn vertrokken — dat de verbinding niet halverwege wegviel, dat het archief niet is afgekapt, dat de schijf heeft geschreven wat hij kreeg — dan is een CRC-32 precies het juiste instrument en vangt hij elke realistische transportfout. Daarom draagt elk ZIP-item en elke gzip-stroom er een. Vraag je in plaats daarvan of het bestand het bestand is dat de uitgever bedoelde, dan beantwoordt een CRC-32 niets. Een aanvaller die het bestand kan vervangen, kan de CRC ook vervangen, en zelfs waar de CRC apart wordt gepubliceerd en niet te wijzigen is, kan hij een ander bestand construeren dat erop uitkomt — dit artikel deed precies dat in 0,11 seconde. Voor verificatie van de uitgever heb je een cryptografische digest nodig, gepubliceerd over een kanaal dat de aanvaller niet beheert, en bij voorkeur een ondertekening over die digest en niet de digest alleen.
- Waarom gebruikt gzip CRC-32 terwijl zlib Adler-32 gebruikt?
- Beide formaten verpakken dezelfde met DEFLATE gecomprimeerde data en verschillen vooral in hun omhulsel. RFC 1952 schrijft een CRC-32 in de staart van gzip voor; RFC 1950 schrijft een Adler-32 in de staart van zlib voor. De redenering was destijds de snelheid: Adler-32 heeft alleen optellingen en een modulo nodig, geen opzoektabel van 256 ingangen, dus op de processoren van het begin van de jaren negentig was hij merkbaar goedkoper per byte, en zlib was gericht op omgevingen waar de kosten van de checksum ten opzichte van de compressie meetelden. Dat voordeel is grotendeels verdampt. Moderne CRC-32-implementaties gebruiken tabellen met slicing-by-8 of speciale processorinstructies, en in de metingen hier haalde de native CRC-32 van node 2.248 MB/s terwijl een rechttoe rechtaan Adler-32 in dezelfde JavaScript-runtime op 174 MB/s kwam tegen de 262 MB/s van CRC-32. De formaten blijven zoals ze zijn gespecificeerd, want een checksumalgoritme wijzigen breekt elke bestaande lezer, en beide zijn sterk genoeg voor hun taak: toevallige corruptie in een gecomprimeerde stroom vangen.
- Hoe waarschijnlijk is een toevallige CRC-32-botsing?
- Voor één verminkt bericht is het antwoord uitstekend: bursts tot 32 bits worden nooit gemist, en daarboven is de ontsnappingskans ongeveer één op 4.294.967.296. Voor een verzameling bestanden is het veel slechter dan de intuïtie suggereert, want het verjaardagseffect geldt. Twee willekeurige waarden van 32 bits botsen met een kans van één op 4,29 miljard, maar een verzameling van n waarden bevat n(n−1)/2 paren, dus komt de grens van 50% bij 77.163 items. Tienduizend bestanden dragen al een kans van 1,16% dat een paar een CRC-32 deelt, en honderdduizend dragen 68,8%. Dat doet ter zake als je CRC-32 als deduplicatiesleutel of als inhoudsgeadresseerde identificatie over een groot corpus gebruikt, waar een botsing stilletjes een van twee verschillende bestanden weggooit. Voor een integriteitscontrole per bestand tegen transportschade is het verjaardagseffect irrelevant, want je vergelijkt één waarde met één verwachte waarde en zoekt niet in een populatie naar overeenkomsten.
- Zijn FNV-1a en MurmurHash3 veilig op door gebruikers aangeleverde sleutels?
- Niet zonder willekeurige seed, nee. Beide zijn standaard zonder sleutel, dus is hun uitvoer een publieke functie die iedereen offline kan uitrekenen. Daardoor kan een aanvaller sleutels voorberekenen die in dezelfde bucket landen en ze allemaal tegelijk versturen, en dat is hash flooding. Hier nagedaan op een tabel met 4.096 buckets: 20.000 gemaakte sleutels hashten alle naar bucket 0, waardoor een langste keten van 12 een enkele keten van 20.000 werd en 20.000 opzoekingen 1.397,9 milliseconde kostten in plaats van 11,5 — 121 keer langzamer, en het verzamelen van die sleutels kostte de aanvaller minder dan een seconde. De oplossing is niet een sterkere hash zonder sleutel; het is een hash met sleutel en een willekeurige seed per proces, waardoor voorberekenen offline onmogelijk wordt. SipHash is de standaardkeuze en is wat de meeste taalruntimes nu intern voor woordenboeken gebruiken. Komen je sleutels uit configuratie, uit je eigen database, of van ergens waar een aanvaller geen invloed heeft, dan blijven FNV-1a en MurmurHash3 zonder seed volkomen goed en heel snel.
- Wat moet ik gebruiken voor cachesleutels en deduplicatie?
- Beslis op wie de inhoud aanlevert en op hoeveel een verkeerd antwoord kost. Voor een cache in het geheugen waarvan je de sleutels zelf genereert — de vorm van een query, de naam van een gerenderde template, een interne identificatie — is een snelle niet-cryptografische hash juist, en is MurmurHash3 op 730 MB/s een goede keuze. Voor deduplicatie over een corpus dat je beheert, waar een botsing betekent dat je stilletjes een van twee verschillende objecten houdt, is 32 bits te smal: het verjaardagspunt van 50% komt bij 77.163 items. Ga naar een niet-cryptografische hash van 64 of 128 bits, of naar een afgekapte SHA-256. Voor alles waar een gebruiker de inhoud aanlevert — geüploade bestanden, door gebruikers gemaakte blobs, een inhoudsgeadresseerde opslag, een gedeelde cache die meerdere klanten bedient — gebruik SHA-256 in zijn geheel. Daar is een botsing geen ongeluk maar een vermogen, waarmee iemand een gekozen object onder een al bestaande identificatie kan plaatsen, en alleen een cryptografische hash maakt dat onhaalbaar. De kosten zijn bescheiden: de 763 MB/s die hier is gemeten, is sneller dan de opslaglaag waarnaar je schrijft.
Artikelen die je misschien interesseren
Alle gidsen →Vergelijkbare tools
Bronnen
- IETF — RFC 1950 — ZLIB Compressed Data Format Specification version 3.3 (defines Adler-32 and its 65521 modulus)
- IETF — RFC 1952 — GZIP file format specification version 4.3 (defines the CRC-32 in the gzip trailer)
- IETF — RFC 3385 — Internet Protocol Small Computer System Interface (iSCSI) Cyclic Redundancy Check (CRC)/Checksum Considerations
- W3C — Portable Network Graphics (PNG) Specification — CRC-32 algorithm and chunk integrity
- USENIX — Crosby and Wallach, Denial of Service via Algorithmic Complexity Attacks, USENIX Security Symposium (the original hash-flooding paper)
Een fout in dit artikel gezien?