Linjer har formen «ALGORITME verdi» etterfulgt av en innrykket parameterlinje, så et kopiert resultat sier alltid hvilket parametersett som produserte det.
CRC — syklisk redundanskontroll, forklart fra grunnen
Med én setning: en CRC behandler dataene som ett gigantisk binært tall, deler det på et fast «generator»-tall ved hjelp av XOR i stedet for subtraksjon, og rapporterer resten — et kompakt fingeravtrykk som endrer seg voldsomt selv om én bit i inndataene snur, og det er derfor alt fra PNG-filer til Modbus-ledninger bærer en.
Hva en CRC egentlig er
Divisjonsbildet. Still opp bytene som ett langt binært tall. Velg en divisor — polynomet, f.eks. 0x04C11DB7 for CRC-32. Utfør binær lang divisjon der «subtraksjon» er XOR-operasjonen: hver gang den ledende biten i den løpende resten er 1, XOR-er man inn divisoren, skifter til venstre og gjentar. Etter at hele meldingen er gjennomgått, er det som er igjen i registeret CRC-en. Ingen nøkler, ingen tabeller i definisjonen — bare divisjon med en rest.
De fem parameterne. To systemer kan begge si «CRC-32» og likevel være uenige, fordi navnet alene ikke fastsetter noe. Den fullstendige oppskriften trenger fem verdier: poly (divisoren), init (hva registeret starter som — nullstilt lar ledende nullbyte forsvinne, alle enere gjør ikke det), refin/refout (om hver inndatabyte — og det endelige registeret — er bitreversert, en arv fra seriell maskinvare som sendte bit minst-signifikant først), og xorout (en endelig XOR-maske, så en rekke etterfølgende nuller fortsatt endrer svaret). Denne siden skriver ut alle fem ved siden av hvert resultat nettopp av den grunnen.
Hvorfor den oppdager feil. En godt valgt divisor gjør at resten av en melding og resten av den samme meldingen med noen få snudde bit er ulike med overveldende sannsynlighet: en god CRC-32 fanger alle 1-bit- og 2-bit-feil, alle oddetall av bitfeil, og hvert utbrudd på opptil 32 sammenhengende ødelagte bit — garantert, ikke probabilistisk. Den garantien gjelder tilfeldig ødeleggelse, og det er den som gjør CRC-er til riktig verktøy for støyende ledninger og skjøre disker.
Hva en CRC ikke er
Ikke en kryptografisk hash. Det finnes ingen hemmelighet og ingen enveisegenskap: hvem som helst som kjenner parametrene kan forfalske en melding med hvilken som helst CRC de vil, på millisekunder, ved å legge til fire korrigerende byte. En CRC oppdager ulykker, aldri motstandere. For nedlastinger som verifiseres mot ukjente parter, er signaturer viktige — se i stedet Hash-generatoren (MD5/SHA/BLAKE2). Den siden forklarer også hvorfor MD5 og SHA-1 er pensjonert for fiendtlige sammenhenger, mens SHA-256 står.
Ikke en feilkorrigerende kode. En CRC forteller at noe endret seg, ikke hva som endret seg. Å reparere feil underveis er jobben til koder som Reed–Solomon eller Hamming, som bevisst lagrer overflødig struktur som en dekoder kan reversere.
Ikke komprimering eller kryptering. Resten er noen få byte uansett inndatastørrelse, og fra den kan man ikke gjenopprette inndataene — men i motsetning til en kryptografisk hash er det bare fordi informasjon ble kastet, ikke fordi invertering er vanskelig.
Familiene på denne siden
CRC-32-kvartettene. Fire av denne sidens oppføringer deler polyet 0x04C11DB7 og gir likevel ulike verdier: ISO-HDLC (reflektert, init/xorout alle enere) er «den» CRC-32 i zlib, gzip, PNG og ZIP; BZIP2 er den samme matematikken uten reflektering; MPEG-2 er BZIP2 uten endelig XOR; POSIX starter fra null og er grunnlaget for kommandoen cksum (som i tillegg legger filens lengde til divisjonen, så cksum av en fil og CRC-32/POSIX av de samme bytene er ulike). CRC-32C (Castagnoli, poly 0x1EDC6F41) er den femte søsken: et annet poly valgt for bedre feildeteksjonsytelse, og det moderne x86- og ARM-prosessorer kan beregne i minnehastighet med én instruksjon.
CRC-64-kvartetten. XZ bruker ECMA-182-polynomet i reflektert form med alle-enere-init og xorout; ECMA-182 selv er den ureflekterte originalen med null-init fra DLT-1-båndstandarden; GO-ISO er Gos crc64.ISO, et lite poly 0x1B, fortsatt reflektert; REDIS bruker et poly valgt for god lavinevirkning i tildeling av hash-spor. Sekstifire bit er størrelsen der CRC-er begynner å bli brukt som hashfunksjoner (bøttefordeling) heller enn rene kontrollsummer.
Adler-32 er utenforstående: den er ingen divisjon i det hele tatt. Den summerer bytene (A, som starter på 1) og summerer disse summene (B), begge modulo 65521, og setter sammen de to 16-bit-summene. Den er raskere enn CRC-32 i programvare, og zlib bruker den for deflate-strømmer — men for korte inndata (under noen få hundre byte) bærer summen for lite informasjon, og derfor bytter zlib tilbake til CRC-32 for små blokker.
CRC-8 og CRC-16 overlever der byte er dyre: CRC-8/CCITT (poly 0x07) beskytter enkeltbyte i headere i SMBus og mobilradioprotokoller; CRC-16/CCITT-FALSE beskytter blokker på smartkort; CRC-16/MODBUS er kontrollsummen i hver Modbus RTU-ramme på fabrikkgulv over hele verden.
Hvor hver av dem brukes
| Parametersett | Finnes i |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), mange arkivformater |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, SSE4.2/ARMv8 maskinvareinstruksjonen CRC32C |
| CRC-32/BZIP2 | .bz2-arkivstrøm |
| CRC-32/MPEG-2 | MPEG-2-transportstrømmer |
| CRC-32/POSIX & cksum | Utdata fra POSIX-kommandoen cksum (cksum file.txt) |
| CRC-16/MODBUS | Modbus RTU-rammer (industrielle PLS-er, målere, omformere) |
| CRC-16/CCITT-FALSE | smartkort, X.25-nære forbindelser, noen GPS-protokoller |
| CRC-8/CCITT | SMBus (PEC-byte), mobilradioheadere |
| CRC-64/XZ | .xz-containerens integritetskontroller |
| CRC-64/ECMA-182 | ECMA-182 / DLT-1-båndstandarden |
| CRC-64/GO-ISO | Go-standardbiblioteket crc64.ISO |
| CRC-64/REDIS | Redis-klyngens tildeling av hash-spor |
| Adler-32 | zlib-strømmer (deflate), andre sammenhenger med rask kontrollsum |
Ankertabellen — check(«123456789»)
Konvensjonen i CRC-katalogen er å publisere resultatet for ASCII-strengen 123456789 (9 byte). Hver verdi nedenfor kan reproduseres på denne siden: skriv 123456789 i tekstboksen, kryss av algoritmen, og klikk på Beregn.
| Parametersett | Bredde | Kontrollverdi (heks) |
|---|
| CRC-8/CCITT | 8 | 0xf4 |
| CRC-16/CCITT-FALSE | 16 | 0x29b1 |
| CRC-16/MODBUS | 16 | 0x4b37 |
| CRC-32/ISO-HDLC | 32 | 0xcbf43926 |
| CRC-32C | 32 | 0xe3069283 |
| CRC-32/BZIP2 | 32 | 0xfc891918 |
| CRC-32/MPEG-2 | 32 | 0x0376e6e7 |
| CRC-32/POSIX | 32 | 0x765e7680 |
| cksum (POSIX command) | 32 | 0x377a6011 |
| CRC-64/XZ | 64 | 0x995dc9bbdf1939fa |
| CRC-64/ECMA-182 | 64 | 0x6c40df5f0b497347 |
| CRC-64/GO-ISO | 64 | 0xb90956c775a41001 |
| CRC-64/REDIS | 64 | 0xe9c6d914c4b8d9ca |
| Adler-32 | 32 | 0x091e01de |
Kilder: hver verdi er krysssjekket med en uavhengig bitvis referanseimplementasjon og, der en finnes, mot systembiblioteket som leverer algoritmen (zlib for CRC-32 og Adler-32; Greg Cook CRC-katalogen for resten).
Vanlige feil
- «CRC-32» uten parametere. Mellom ISO-HDLC, BZIP2, MPEG-2, POSIX og CRC-32C sirkulerer fem ulike verdier under samme navn. Før alltid poly/init/refin/refout/xorout sammen med resultatet — denne siden skriver dem ut.
- Å sammenligne en fils CRC-32 med utdataene fra
cksum. Ulike algoritmer: cksum legger til lengden og bruker en annen init. Tallene vil ikke stemme, og begge er «riktige».
- Å stole på CRC mot manipulering. Å forfalske en matchende CRC er en klassisk øvelse (patch de siste 4 bytene). Bruk en nøklet MAC (HMAC) eller en signatur når den andre siden kan være fiendtlig.
- Å forvente lavinevirkning. En CRC er lineær: beslektede meldinger gir beslektede CRC-er. Greit for støy, feil for hashing — hvis det er behov for bøttefordeling, er CRC-64 eller en ekte hash tryggere enn CRC-32.
- Heks-tekst mot bytes. Strengen
"123456789" (9 ASCII-byte, 31 32 33 34 35 36 37 38 39) og tallet 0x123456789 er ulike inndata med ulike CRC-er. Bruk fanen for heksbyte når kildedataene virkelig er binære.
Ofte stilte spørsmål
Hvorfor stemmer ikke min CRC-32 med den i ZIP-filen? ZIPs CRC-32 er ISO-HDLC over de ukomprimerte dataene. Sørg for at man hashet de samme bytene (ikke den komprimerte strømmen), den samme modusen (tekst mot heks) og det samme parametersettet — parameterlinjen under hvert resultat er der for å gjøre den kontrollen øyeblikkelig.
Hva er best, CRC-32C eller CRC-32? For tilfeldig feildeteksjon fanger begge alle utbrudd på opptil 32 bit; CRC-32C presterer bedre på noen feilmønstre og er den som har CPU-instruksjoner — praktisk talt gratis i gigabithastigheter. Grunnen til at CRC-32/ISO-HDLC overlever, er kompatibilitet: tretti år med arkiver snakker den.
Er CRC-64 sterkere enn CRC-32? Den oppdager lengre utbrudd (opptil 64 bit) og kolliderer langt mindre når den brukes til bøttefordeling, men den er like lett å forfalske — bredde gir deteksjonsgarantier, ikke sikkerhet.
Kan en CRC reverseres for å avsløre inndataene? Nei — uendelig mange inndata deler en CRC. Men i motsetning til en kryptografisk hash kan en angriper konstruere et inndata med hvilken som helst CRC de velger, og det er i den forstand den ikke er enveis i det hele tatt.
