Riadky majú tvar „ALGORITMUS hodnota“ a za nimi nasleduje odsadený riadok parametrov, takže skopírovaný výsledok vždy hovorí, ktorá sada parametrov ho vytvorila.
CRC — cyklický redundančný súčet, vysvetlený od začiatku
Jednou vetou: CRC považuje dáta za jedno obrovské binárne číslo, delí ho pevným „generujúcim“ číslom pomocou XOR namiesto odčítania a vráti zvyšok — kompaktný odtlačok, ktorý sa dramaticky zmení pri zmene jediného bitu vstupu, preto ho má všetko od súborov PNG po vodiče Modbus.
Čo CRC naozaj je
Obraz delenia. Bajty sa zoradia ako jedno dlhé binárne číslo. Zvolí sa deliteľ — polynóm, napr. 0x04C11DB7 pre CRC-32. Vykoná sa binárne dlhé delenie, v ktorom je „odčítanie“ operácia XOR: vždy keď je vedúci bit bežiaceho zvyšku 1, urobí sa XOR s deliteľom, posun doľava a opakovanie. Keď prejde celá správa, to, čo zostane v registri, je CRC. Definícia nepotrebuje žiadne kľúče ani tabuľky — len delenie so zvyškom.
Päť parametrov. Dva systémy môžu obe tvrdiť „CRC-32“ a stále sa nezhodovať, pretože samotný názov nič nepevne nezafixuje. Úplný postup potrebuje päť hodnôt: poly (deliteľ), init (počiatočná hodnota registra — samé nuly nechajú zmiznúť úvodné nulové bajty, samé jednotky nie), refin/refout (či sa každý vstupný bajt — a konečný register — obracia bitovo, dedičstvo sériového hardvéru, ktorý posielal bity od najmenej významného), a xorout (konečná maska XOR, takže séria koncových núl stále mení výsledok). Táto stránka vypíše všetkých päť pri každom výsledku presne z tohto dôvodu.
Prečo zachytáva chyby. Dobre zvolený deliteľ spôsobí, že zvyšok správy a zvyšok tej istej správy s niekoľkými prevrátenými bitmi sa s prevažujúcou pravdepodobnosťou líšia: dobré CRC-32 zachytí všetky 1-bitové a 2-bitové chyby, všetky nepárne počty bitových chýb a každý zhluk až 32 po sebe idúcich poškodených bitov — zaručene, nie pravdepodobnostne. Táto záruka sa týka náhodného poškodenia a práve preto sú CRC správnym nástrojom pre hlučné vodiče a nespoľahlivé disky.
Čím CRC nie je
Nie je to kryptografický hash. Nie je tu žiadne tajomstvo ani jednosmernosť: ktokoľvek, kto pozná parametre, môže sfalšovať správu s ľubovoľným CRC, v milisekundách, pripojením štyroch opravných bajtov. CRC zachytí náhody, nikdy protivníkov. Pri sťahovaní súborov, ktoré sa overujú voči cudzím zdrojom, záleží na podpisoch; na tento účel slúži Generátor hashu (MD5/SHA/BLAKE2). Táto stránka tiež vysvetľuje, prečo sú MD5 a SHA-1 vyradené pre nepriateľské prostredie, zatiaľ čo SHA-256 obstojí.
Nie je to kód na opravu chýb. CRC povie, že sa niečo zmenilo, nie čo sa zmenilo. Oprava chýb za behu je úloha kódov ako Reed–Solomon alebo Hamming, ktoré zámerne ukladajú redundantnú štruktúru, ktorú dekodér dokáže obrátiť.
Nie je to kompresia ani šifrovanie. Zvyšok má niekoľko bajtov bez ohľadu na veľkosť vstupu a z neho sa vstup obnoviť nedá — ale na rozdiel od kryptografického hashu je to len preto, že informácia bola zahodená, nie preto, že inverzia je ťažká.
Rodiny na tejto stránke
Štvorica CRC-32. Štyri položky tejto stránky zdieľajú polynóm 0x04C11DB7 a predsa dávajú rozdielne hodnoty: ISO-HDLC (odzrkadlený, init/xorout samé jednotky) je „ten“ CRC-32 zlib, gzip, PNG a ZIP; BZIP2 je tá istá matematika neodzrkadlená; MPEG-2 je BZIP2 bez konečného XOR; POSIX začína od nuly a je základom príkazu cksum (ktorý navyše pripája dĺžku súboru k deleniu, takže cksum súboru a CRC-32/POSIX nad rovnakými bajtmi sa líšia). CRC-32C (Castagnoli, poly 0x1EDC6F41) je piaty súrodenec: iný polynóm zvolený pre lepší výkon pri detekcii chýb, a ten, ktorý moderné procesory x86 a ARM dokážu počítať rýchlosťou pamäte jednou inštrukciou.
Štvorica CRC-64. XZ používa polynóm ECMA-182 v odzrkadlenej forme so samými jednotkami v init a xorout; ECMA-182 je samotný neodzrkadlený pôvodný variant s nulovým init z pásky DLT-1; GO-ISO je crc64.ISO z Go, malý poly 0x1B, stále odzrkadlený; REDIS používa poly zvolený pre dobrý lavínový efekt pri priraďovaní slotov hashu. Šesťdesiatštyri bitov je veľkosť, pri ktorej sa CRC začína používať ako hashovacia funkcia (zoskupovanie), nie ako čisté kontrolné súčty.
Adler-32 je outsider: vôbec nejde o delenie. Sčíta bajty (A, začína od 1) a sčíta aj tieto súčty (B), oboje modulo 65521, a spojí oba 16-bitové súčty. V softvéri je rýchlejší ako CRC-32 a zlib ho používa pre prúdy deflate — pri krátkych vstupoch (pod niekoľko stoviek bajtov) však súčet nesie príliš málo informácií, a práve preto zlib pri malých blokoch prechádza späť na CRC-32.
CRC-8 a CRC-16 prežívajú tam, kde sú bajty drahé: CRC-8/CCITT (poly 0x07) chráni jednotlivé bajty hlavičky v protokoloch SMBus a mobilných rádií; CRC-16/CCITT-FALSE chráni bloky čipových kariet; CRC-16/MODBUS je kontrolný súčet každého rámca Modbus RTU v továrňach po celom svete.
Kde sa každé používa
| Sada parametrov | Nájde sa v |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), mnoho archívnych formátov |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, hardvérová inštrukcia CRC32C v SSE4.2/ARMv8 |
| CRC-32/BZIP2 | prúd archívu .bz2 |
| CRC-32/MPEG-2 | prúdy transportu MPEG-2 |
| CRC-32/POSIX & cksum | výstup príkazu POSIX cksum (cksum file.txt) |
| CRC-16/MODBUS | rámce Modbus RTU (priemyselné PLC, merače, meniče) |
| CRC-16/CCITT-FALSE | čipové karty, spoje podobné X.25, niektoré protokoly GPS |
| CRC-8/CCITT | SMBus (bajt PEC), hlavičky mobilných rádií |
| CRC-64/XZ | kontrola integrity kontajnera .xz |
| CRC-64/ECMA-182 | ECMA-182 / štandard pásky DLT-1 |
| CRC-64/GO-ISO | Štandardná knižnica Go crc64.ISO |
| CRC-64/REDIS | Priraďovanie slotov hashu v klastri Redis |
| Adler-32 | prúdy zlib (deflate), ďalšie kontexty rýchleho kontrolného súčtu |
Kotvový prehľad — check(„123456789“)
Konvencia katalógu CRC je zverejniť výsledok pre reťazec ASCII 123456789 (9 bajtov). Každá hodnota nižšie je na tejto stránke reprodukovateľná: do poľa Text sa zadá 123456789, zaškrtne sa algoritmus a klikne sa na Vypočítať.
| Sada parametrov | Šírka | Hodnota kontroly (hex) |
|---|
| 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 |
Zdroje: každá hodnota bola skontrolovaná nezávislou bitovou referenčnou implementáciou a tam, kde existuje, aj voči systémovej knižnici, ktorá algoritmus obsahuje (zlib pre CRC-32 a Adler-32; katalóg CRC od Grega Cooka pre ostatné).
Časté chyby
- „CRC-32“ bez parametrov. Medzi ISO-HDLC, BZIP2, MPEG-2, POSIX a CRC-32C koluje päť rôznych hodnôt pod rovnakým názvom. Vždy sa má zaznamenať poly/init/refin/refout/xorout spolu s výsledkom — táto stránka ich vypisuje sama.
- Porovnanie CRC-32 súboru s jeho výstupom
cksum. Rôzne algoritmy: cksum pridáva dĺžku a používa iný init. Čísla sa nezhodujú a obe sú „správne“.
- Dôvera v CRC pri manipulácii. Sfalšovanie zhodného CRC je učebnicová úloha (oprava posledných 4 bajtov). Keď môže byť druhá strana nepriateľská, treba použiť kľúčový MAC (HMAC) alebo podpis.
- Očakávanie lavínového efektu. CRC je lineárne: príbuzné správy dávajú príbuzné CRC. Vhodné na šum, nevhodné na hashovanie — ak je potrebné zoskupovanie, bezpečnejší je CRC-64 alebo skutočný hash než CRC-32.
- Hex text verzus bajty. Reťazec
"123456789" (9 bajtov ASCII, 31 32 33 34 35 36 37 38 39) a číslo 0x123456789 sú rozdielne vstupy s rozdielnymi CRC. Záložka Hex bajty sa používa vtedy, keď sú zdrojové dáta naozaj binárne.
FAQ
Prečo sa CRC-32 nezhoduje s tým v súbore ZIP? CRC-32 v ZIP je ISO-HDLC nad nekomprimovanými dátami. Treba sa uistiť, že sa hashovali rovnaké bajty (nie komprimovaný prúd), rovnaký režim (Text alebo Hex) a rovnaká sada parametrov — riadok parametrov vypísaný pod každým výsledkom slúži na to, aby sa táto kontrola dala urobiť hneď.
Ktoré je lepšie, CRC-32C alebo CRC-32? Na zisťovanie náhodných chýb obe zachytia všetky zhluky až do 32 bitov; CRC-32C sa pri niektorých vzoroch chýb správa lepšie a je to ten, ktorý má inštrukcie v procesore — prakticky zadarmo pri gigabitových rýchlostiach. Dôvod, prečo CRC-32/ISO-HDLC prežíva, je kompatibilita: tridsať rokov archívov ním „hovorí“.
Je CRC-64 silnejší ako CRC-32? Zachytí dlhšie zhluky (až 64 bitov) a pri zoskupovaní sa výrazne menej zráža, ale dá sa rovnako sfalšovať — šírka prináša záruky detekcie, nie bezpečnosť.
Dá sa CRC obrátiť a odhaliť vstup? Nie — nekonečne veľa vstupov zdieľa rovnaké CRC. Na rozdiel od kryptografického hashu však útočník vie zostrojiť vstup s ľubovoľným CRC, v tom zmysle, že nie je vôbec jednosmerné.
