Információbiztonság a bitek szintjén

Az információbiztonság elég összetett téma. Ebből adódóan nem csak azzal foglalkozik az informatika ezen területe, hogy jobbnál jobb titkosítási módszereket fejlesszen ki, hanem azzal is, hogy A pontból B pontba zökkenőmenetesen, zavar nélkül megérkezzen a küldendő adatunk. Első információbiztonsági írásomban ezen területet boncolgatom.

Alapok

A számítógépünk kettes számrendszerben dolgozik, vagyis minden adatunk, képünk, filmünk végső soron egy, az adott formátumra jellemző bitek sorozataként áll elő. Ezen bitek sorozata igencsak sérülékeny, mivel egy bit megváltozása már komoly hibákat tud okozni az adatátvitel során. Példaképpen a 14-es szám 4 biten ábrázolva 1110. Ebből a 4 bitből, ha a legnagyobb helyi értéken lévő bit sérül, akkor az átvitt adat nem 1110 lesz, hanem 0110, ami  10-es számrendszerben a 6-os számot adja.

Ezért az átviteli rendszerekben az átvitel előtt valamilyen extra kódolással látják el a bináris számokat. Ez a kódolás lehet hibafelismerő kódolás vagy hibajavító kódolás.

Hibafelismerő kódolások

A legegyszerűbb hibafelismerő kódolási módszer az, hogy paritásbitet vezetünk be a kódba. Ez azt jelenti, ha 4 bites adatokat akarok továbbítani, akkor valójában 5 bit adatot továbbítok. Az 5. bit azt fogja leírni, hogy a 4 bit adatban szereplő egyesek száma páros, vagy páratlan. Ezáltal felismerhetővé válik az átviteli hiba, és újra lehet küldeni az adatot. A paritásbit elhelyezkedhet a legnagyobb helyiértéken vagy a legkisebb helyiértéken is. Valamint lehet 0-val jelölni a páros értéket és 1-el is. Rendszer függő a tényleges megvalósítás. Az előzőleg bemutatott példa számot és átviteli hibát fogja bemutatni a példa ismét, csak paritásbit bevezetésével. A paritásbit jelen rendszerben a legkisebb helyiértéken helyezkedik el, értéke 1, ha a kódban szereplő egyesek száma páros.

A 14 binárisan: 1110. Az egyesek száma 3db, ezért a paritásbitem 0 értékű lesz. Az átvitelre szánt kód: 11100. Ez a vevő oldalon 01100 kódszóként érkezik meg. A fogadó rendszer megszámolja az egyesek számát, ami 2, tehát a paritás bit értékének 1-nek kellene lennie. A rendszer viszont 0 paritást kapott, így tudja, hogy az adott átvitel helytelen.

A paritásbit nem univerzális megoldás, mivel csak fix hosszúságú kódszavak esetén működik jól, illetve egy paritásbit nem feltétlenül fedi le a teljes átvitelt, mivel ha több bit is sérül, akkor előfordulhat az az eset, hogy a paritás bit alapján jónak ítéli meg a rendszer az adatot, közben pedig nem jó. Példaképpen ha a 11100 kódszóból az első kettő egyes érték 0 értékkel érkezik meg, akkor a kapott kód 00100, ami a paritás bit alapján helyes, de valójában nem ezt akartuk továbbítani.

Egy másik, jobb megoldás a ciklikus redundancia vizsgálat, röviden CRC. Ezen eljárás lényege az, hogy az üzenethez hozzáteszünk egy ellenőrző értéket, ami alapján megállapítható, hogy az adat helyes, vagy helytelen.

Az ellenőrző érték fix hosszúságú, míg az a bemeneti adat változó hosszúságú lehet. Az ellenőrző összeg meghatározó algoritmus tervezése esetén cél, hogy minimalizálják az ütközések valószínűségét, mivel csak akkor jó az algoritmus. Rengeteg ilyen algoritmus létezik, például a CRC család tagjai. Ebből a legnépszerűbb a CRC-32, ami 32 bites ellenőrző összegeket gyárt.

Számos helyen alkalmazzák. Megtalálható az IP kommunikációban, a SATA vezérlőkben, a ZIP és a PNG formátumokban is.

Hibajavító kódolások

Számos gyakorlati példa mondható arra, hogy nem minden esetben megoldható az adat újraküldése hibajavításképpen. Ilyen esetekre találták ki a hibajavító kódokat.

A hibajavító kódok jóságát a Hamming korlát és a Hamming távolság mutatják meg. Ezek Richard Hamming matematikusról lettek elnevezve. A Hamming távolság azt mutatja meg, hogy egy n bites kódszavakat alkalmazó rendszerben mennyi a kódszavak minimális bit eltérése egymáshoz viszonyítva.

A bit eltérések száma azért fontos, mert ebből megállapítható, hogy a rendszerben hány átviteli hiba észlelhető extra bitek beiktatása nélkül, illetve azt is, hogy mennyi bit hiba javítható. Ha egy rendszer minimális Hamming távolsága k, akkor k-1 bithiba észlelhető és k/2 bithiba javítható.

Az előző módszerekben tárgyalt paritásbit hozzáadása a kódhoz eggyel megnöveli a minimális Hamming távolságot.

A Hamming korlát pedig a kódrendszer hatékonyságát mutatja meg. Az olyan rendszereket, amelyek elérik a Hamming korlátot, tökéletes rendszernek nevezzük, kérdés az, hogy hogyan dolgozunk ki egy tökéletes kódot ?

Hamming erre szolgáltatott egy algoritmust, amit ma Hamming kódnak nevezünk. Ebből a legáltalánosabb a Hamming(7,3) felépítésű kód. Ez azt jelenti, hogy a kód 7 bites, amiből 3 bit paritás szerepet tölt be. Segítségével egy bithiba a kód bármelyik pozíciójában észlelhető és javítható is újraküldés nélkül.

A kódban a paritás bitek kettő hatványainak megfelelő bit pozíciókban vannak elhelyezve. A 7 bites változatban az 1., 2. és a 4. bit.

Hamming kódban a paritás és adatbitek helyzetei. Zöld színnel a paritásbit jelölt. Az X-el jelölt részek azt fejezik ki, hogy az adott paritásbit számításánál melyik bit pozíciókat kell figyelembe venni. Kép forrása: wikipedia

A módszer azonban tetszőlegesen nagy bithosszra átültethető a képzési algoritmus lapján. Így ma számos helyen használva van ez a hibavédelmi rendszer. Csak pár példa: Online Stream-ek, CD lemezek, ECC memóriák, stb…

Persze a hibavédelmet ilyen módszerekkel egy bizonyos határ fölé nem lehet vinni, de igazából olyan megoldás nincs, ami önmagában mindenre jó lenne. Ezért a gyakorlatban több hibavédelmi rendszer kombinációját alkalmazzák.

“Analóg” hibavédelem

A digitális jeleket továbbítás céljából fizikailag is mérhető mennyiséggé kell konvertálni, mivel másképpen nem igazán továbbíthatóak. Itt a konverzió szintjén is szoktak beiktatni némi tűrést, hibavédelem szempontjából. Ez a tűrés például egy feszültség alapú rendszernél jelentheti azt, hogy az 1-es értékhez nem fixen 5V feszültségszintet rendelünk, hanem ha a jel 4 és 5,5V között van, akkor 1-esnek tekintjük az értéket, ha pedig 0 és 1,5V között van, akkor pedig 0 értéknek tekintett.

Hasonló analógiával megvan a hibavédelem a CD, DVD lemezek sávjaiban, csak ott mikrométer szintű toleranciáról beszélünk. Illetve minden más rendszerben is. Feszültség alapú átvitelek esetén számos hibaészlelő kódolást találtak ki különböző rendszerekhez, különböző igényekhez igazodva. Az alapvető igény az, hogy az “analóg” világunkban a logika nem két diszkrét értékkel rendelkezik. Lehet egy eldöntendő kérdés eredménye, Igaz, Hamis és nem ismert.

A nem ismert állapot átvitel során a kábel szakadás esete. Ha csak két feszültségszintet alkalmaznánk átvitel során, mondjuk 0 és 5V szinteket, akkor a kábelszakadás esetén nagy valószínűséggel folyamatosan 0 értékeket kapnánk. Így a rendszer nem lenne képes észlelni azt, hogy azért nem megy a kommunikáció, mert nincs kapcsolat. Egy jobb megoldás az, ha három feszültségszintet alkalmazunk. Mondjuk 0, 1 és 5V jeleket, annyi módosítással, hogy az 1 volt jelenti a 0 állapotot. Örülhetnénk, de a a helyzet az, hogy ez sem a legjobb megoldás. Mivel a kábelen folyamatos 0 állapotban is 1 volt feszültség van. Ahol pedig feszültség van, ott vesztéség is keletkezik a vezetők ellenállásából fakadóan.

Szóval a jó megoldás az, ha a körülmények figyelembe vételével egy speciális kódolási sémát választunk. Ilyenre példaként a Manchester kódolást említeném. Ezt az Ethernet rendszerekben alkalmazzák. Lényege, hogy a 0 értéket egy 1->0 váltás jelzi az átvitel során, az egyes értéket pedig egy 0->1 váltás. További előnye a kódnak, hogy nem kell hozzá külön órajel, ami meghatározza azt, hogy az egyes bitek meddig tartanak. Ez egy úgynevezett ön órajelező kódolás.

Manchester kódolás. Kép forrása: wikipedia

Számos példa említhető lenne még, azonban némi további olvasnivaló ajánlásával le is zárom ezt a cikket.

Kiegészítő olvasnivalók