A5 (titkosító algoritmus)

Az A5  egy adatfolyam- titkosítási algoritmus , amelyet a telefon és a bázisállomás között továbbított adatok titkosságának biztosítására használnak az európai mobil digitális kommunikációs GSM rendszerben ( Groupe Spécial Mobile ).

A titkosítás a generált pszeudo-véletlenszerű sorozat és a titkosítandó információ bitenkénti összeadásán alapul (boolean XOR művelet). Az A5-ben egy pszeudo-véletlen sorozatot valósítanak meg három lineáris visszacsatolásos eltolási regiszter alapján . A regiszterek 19, 22 és 23 bitesek. Az eltolásokat egy speciális áramkör vezérli, amely minden lépésben legalább két regiszter eltolását szervezi, ami egyenetlen mozgáshoz vezet. A sorozatot a regiszterek kimeneti bitjein végzett XOR művelet alkotja.

Teremtés és fejlődés története

Kezdetben egy adatfolyam-rejtjelet fejlesztettek ki francia katonai kriptográfusok, amelyeket kizárólag katonai célokra használnak. A 80-as évek végén a GSM szabvány új, modern biztonsági rendszer létrehozását követelte meg. Három titkos algoritmuson alapult: hitelesítés - A3 , adatfolyam titkosítás - A5, munkamenet kulcs generálása - A8 . A5-ös algoritmusként egy francia fejlesztést használtak. Ez a titkosítás meglehetősen jó biztonsági adatfolyamot és ezáltal a beszélgetés bizalmasságát biztosította. Kezdetben nem számítottak a szabvány exportjára Európából, de hamarosan felmerült az igény. Ezért az A5-öt átnevezték A5 / 1-re, és Európában és az Egyesült Államokban is elkezdték terjeszteni. Más országok (köztük Oroszország) esetében az algoritmust módosították, jelentősen csökkentve a titkosítás kriptográfiai erősségét. Az A5/2-t kifejezetten az EU-n kívüli országok exportálására tervezték. Az A5/2 kriptográfiai erősségét csökkentették egy másik regiszter (17 bites) hozzáadásával, amely vezérli a többi eltolódását. Az A5 / 0-ban egyáltalán nincs titkosítás. A Kasumi algoritmuson alapuló A5/3 algoritmust szintén kifejlesztették és jóváhagyták a 3G hálózatokban való használatra. Ezeket a módosításokat A5/x-nek nevezzük.

Nyilvános megjelenés

Hivatalosan ezt a titkosítási sémát nem tették közzé, és a szerkezetét sem hozták nyilvánosságra. Ennek az az oka, hogy a fejlesztők a biztonságra hagyatkoztak az ismeretlenség rovására , ami azt jelenti, hogy az algoritmusokat nehezebb feltörni, ha a leírásuk nem nyilvános. A GSM szolgáltatók csak szükség esetén kaptak adatot. 1994-re azonban az A5-ös algoritmus részletei ismertek voltak: a British Telecom brit telefontársaság a szabványra vonatkozó összes dokumentációt átadta a Bradfordi Egyetemnek elemzés céljából anélkül , hogy titoktartási megállapodást kötött volna . Emellett az egyik kínai konferencián is megjelentek a szabványról szóló anyagok. Ennek eredményeként a terve fokozatosan széles körökbe szivárgott ki. Ugyanebben az évben Ross Anderson (Ross Anderson) és Michael Roe (Michael Roe) cambridge-i tudósok közzétettek egy ezekből az adatokból visszaállított kriptográfiai sémát, és felmérték annak kriptográfiai erejét [1] . A végső algoritmust Jovan Golic munkájában mutatta be az Eurocrypt'97 konferencián.

A5-ös szerkezet

Az A5 algoritmus jelenleg rejtjelek egész családja. Leírásként vegyük az A5/1-et e család ősének. A derivált algoritmusok változásait külön ismertetjük.

Adatfolyam titkosítás

Ebben az algoritmusban minden egyszerű szöveges karakter egy titkosított szöveg karakternek felel meg. A szöveg nincs blokkokra osztva (mint a blokk titkosításnál ), és nem változik a mérete. A hardveres implementáció egyszerűsítésére és ezáltal a teljesítmény növelésére csak a legegyszerűbb műveleteket alkalmazzuk: modulo 2 addíció (XOR) és regisztereltolás.

A kimeneti sorozat úgy jön létre, hogy a forrásszövegfolyamot hozzáadjuk a generált sorozathoz (gamma). Az XOR művelet sajátossága, hogy páros számú alkalommal alkalmazva a kezdeti értékhez vezet. Ezért az üzenet dekódolása a titkosított szövegnek egy ismert sorozathoz való hozzáadásával történik.

Így a rendszer biztonsága teljes mértékben a sorozat tulajdonságaitól függ. Ideális esetben a gamma minden bitje független valószínűségi változó, és maga a sorozat véletlenszerű. Egy ilyen rendszert Vernam talált ki 1917-ben, és róla nevezték el. Amint azt Claude Shannon 1949-ben bebizonyította , ez abszolút biztonságot nyújt. A véletlenszerű sorrend használata azonban a sima szöveggel megegyező hangerősségű üzenet biztonságos csatornán történő továbbítását jelenti, ami nagymértékben megnehezíti a feladatot, és gyakorlatilag sehol sem használják.

A valós rendszerekben egy adott méretű kulcs jön létre, amely könnyen továbbítható privát csatornán. A sorozat ez alapján jön létre, és álvéletlen. Az adatfolyam-rejtjelek nagy csoportja (beleértve az A5-öt is) olyan titkosítók, amelyek pszeudo-véletlen sorrendgenerátora lineáris visszacsatolású eltolási regisztereken alapul.

RSLOS

A lineáris visszacsatolásos eltolási regiszter magából a regiszterből (adott hosszúságú bitek sorozatából) és a visszacsatolásból áll. Minden ciklusban a következő műveletek történnek: a bal szélső bitet (legmagasabb bitet) kinyerjük, a sorozatot balra toljuk, és a visszacsatolási függvény értékét az üres jobboldali cellába írjuk (legkisebb jelentőségű bit). Ez a függvény a regiszter bizonyos bitjeinek modulo két összege, és polinomként van felírva, ahol a kitevő a bitszámot jelöli. A kivont bitek alkotják a kimeneti sorozatot.

Az LFSR esetében a fő mutató a pszeudo-véletlen sorozat periódusa. Akkor lesz maximális (és egyenlő 2 n − 1-gyel), ha a visszacsatoló polinom primitív modulo 2 . A kimeneti sorozatot ebben az esetben M-sorozatnak nevezzük.

LFSR rendszer A5-ben

Maga az LFSR könnyen alkalmas a kriptográfiai elemzésre, és nem elég erős a titkosításhoz. Gyakorlati alkalmazások a változó órajel-regiszterek különböző hosszúságú és visszacsatoló funkciójú rendszerei.

Az A5 algoritmus felépítése a következő:

  • Három regiszter (R1, R2, R3) 19, 22 és 23 bites hosszúságú,
  • Visszajelzési polinomok:
    • X 19 + X 18 + X 17 + X 14 + 1 R1 esetén,
    • X 22 + X 21 + 1 R2 és
    • X 23 + X 22 + X 21 + X 8 + 1 R3 esetén,
  • Az órajelet egy speciális mechanizmus vezérli:
    • minden regiszternek vannak szinkronbitjei: 8 (R1), 10 (R2), 10 (R3),
    • az F = x&y|x&z|y&z függvény kiszámítása, ahol & a logikai ÉS, | - logikai VAGY, és x, y és z az R1, R2 és R3 szinkronizációs bitek,
    • csak azok a regiszterek tolódnak el, amelyek szinkronbitje egyenlő F-vel,
    • valójában azok a regiszterek, amelyek szinkronbitje a többséghez tartozik, eltolódnak,
  • A rendszer kimeneti bitje a regiszterek kimeneti bitjein végzett XOR művelet eredménye.

Az A5 algoritmus működése

Tekintsük az algoritmus működésének jellemzőit az ismert séma alapján. Az adatátvitel strukturált formában – keretekre lebontva (114 bit) történik. Inicializálás előtt a regiszterek alaphelyzetbe állnak, az A8 által alkotott munkamenet kulcs (K - 64 bit) és a keretszám (Fn - 22 bit) bekerül az algoritmusba . Ezután a következő lépéseket kell végrehajtani egymás után:

  • Inicializálás:
    • 64 ciklus, amelyben a kulcs következő bitjét az egyes regiszterek legkisebb szignifikáns bitjével XOR-beírják, miközben a regiszterek minden cikluson eltolódnak,
    • a 22 ciklushoz hasonlóan csak az XOR műveletet hajtják végre a keretszámmal,
    • 100 ciklus regisztereltolás vezérléssel, de sorozatgenerálás nélkül,
  • 228 (114 + 114) ciklus működik, a továbbított keret titkosítva van (az első 114 bit) és a fogadott keret dekódolva (az utolsó 114 bit),
  • a további inicializálás újból történik, új keretszám kerül felhasználásra.

Különbségek a származtatott algoritmusokban A5/x

Egy másik 17 bites regiszter (R4) került az A5 / 2 algoritmusba , amely a többi mozgását szabályozza. A szerkezeti változások a következők:

  • hozzáadott 17 bites R4 regiszter,
  • visszacsatoló polinom R4-hez: ,
  • Az órajelet az R4 vezérli:
    • Az R4-nek 3., 7., 10. szinkronbitje van,
    • a többségi függvény kiszámítása F = x&y|x&z|y&z (egyenlő a többséggel), ahol & logikai ÉS, | - logikai VAGY, és x, y és z az R4(3), R4(7) és R4(10) szinkronizálási bitek,
    • R1 eltolódik, ha R4(10) = F,
    • R2 eltolódik, ha R4(3) = F,
    • R3 eltolódik, ha R4(7) = F,
  • a rendszer kimeneti bitje a regiszterek magas bitjein végzett XOR művelet eredménye és a regiszterek bizonyos bitjeiből származó többségi függvények:
    • R1 - 12, 14, 15,
    • R2 - 9, 13, 16,
    • R3 - 13, 16, 18.

A működésben bekövetkezett változások nem olyan jelentősek, és csak az inicializálást érintik:

  • 64+22 ciklus van kitöltve munkamenetkulccsal és keretszámmal, szintén R4-gyel,
  • 1 ciklus R4(3), R4(7) és R4(10) 1,
  • 99 ciklus regisztereltolás vezérléssel, de sorozatgenerálás nélkül.

Látható, hogy az inicializálás ugyanannyi időt vesz igénybe (100 generálás nélküli ciklus két részre oszlik).

Az A5/3 algoritmust 2001 -ben fejlesztették ki, és fel kell váltania az A5/1-et a mobil rendszerek harmadik generációjában. Kasumi algoritmusnak is nevezik . Létrehozásakor a Mitsubishi Corporation MISTY titkosítását vették alapul. Jelenleg az A5/3 biztosítja a szükséges ellenállást.

Az A5/0 algoritmus nem tartalmaz titkosítást.

Biztonság

A GSM szabvány kifejlesztése egy erős titkosítógépet jelentett, amelyet nem lehetett feltörni (főleg valós időben). Az alkalmazott fejlesztések megfelelő megvalósítás mellett a továbbított adatok minőségi titkosítását biztosították. Ez az a fajta információ, amely a szabványt terjesztő cégektől szerezhető be. De érdemes megjegyezni egy fontos árnyalatot: a beszélgetések hallgatása a speciális szolgáltatások által használt szerves tulajdonság. Érdekelte őket a saját célú lehallgatási lehetőség. Így változtatásokat hajtottak végre az algoritmuson, lehetővé téve a feltörést elfogadható időn belül. Ezenkívül az A5 módosult, hogy A5 / 2-re exportálja. A MoU (Memorandum of Understand Group Special Mobile szabvány) elismeri, hogy az A5/2 fejlesztésének célja a titkosítás kriptográfiai erősségének csökkentése volt, azonban a hivatalos teszteredmények szerint az algoritmusnak nincs ismert hiányossága [2] .


Ismert sebezhetőségek

Az A5 szabványra vonatkozó adatok megjelenésével megindultak az algoritmus feltörésére irányuló kísérletek, valamint a sebezhetőségek keresése. Hatalmas szerepet játszottak a szabvány jellemzői, amelyek élesen gyengítik a védelmet, nevezetesen:

  • a kulcs 10 bitje nullára kényszerül,
  • a regiszterek közötti keresztkötések hiánya (kivéve a műszakvezérlést),
  • a kriptoanalitikus által ismert szolgáltatási információk titkosítása,
  • a kulcsok több mint 40%-a a generált sorozat periódusának minimális hosszához vezet, nevezetesen [3]
  • a munkamenet elején null üzenetet cserélnek (egy képkocka egyszerre),
  • ugyanaz a párnázás minden csomaghoz,
  • Az A5/2-ben a mozgást egy különálló, 17 bites regiszter végzi.

Az algoritmus ezen "lyukak" alapján feltörő sémák épülnek fel.

Figyelemre méltó támadások

A kulcs egy 64 bites munkamenetkulcs, a keretszámot ismertnek feltételezzük. Így a nyers erejű támadás összetettsége 2 64 .

A rejtjel első áttekintései (Ross Anderson munkája) azonnal felfedték az algoritmus sebezhetőségét - az effektív kulcshossz csökkenése (10 bites nullázás) miatt a komplexitás 2 45 -re esett (egyszerre 6 nagyságrenddel). ). Anderson támadása a rövid regiszterek kezdeti kitöltésének feltételezésén és a harmadik kitöltésének megszerzésének kimenetén alapul.

1997-ben Jovan Golic publikálta az A5 elemzés eredményeit. Javaslatot tett a regiszterek kezdeti kitöltésének meghatározására a gamma ismert, mindössze 64 bites szegmenséből. Ez a szegmens nulla üzenetből származik. A támadás átlagos nehézsége 2 40 .

1999-ben Wagner és Goldberg könnyedén bebizonyította, hogy a rendszer megnyitásához elegendő az R4 kezdeti kitöltést felsorolással meghatározni. Az ellenőrzés a nulla képkockák rovására történik. A támadás összetettsége 2 17 , így egy modern számítógépen néhány másodpercbe telik a titkosítás feltörése.

1999 decemberében izraeli tudósok egy csoportja ( Adi Shamir , Alex Biryukov , majd az amerikai Wagner nagyon nem triviális, de elméletileg nagyon hatékony módszert az A5/1 kinyitására:

Ez egy nagyon összetett ötlet, amelyet több fronton támadunk, hogy felhalmozzunk néhány apró előnyt, de együttvéve nagy különbséget jelentenek.Adi Shamir

Jegyzetek

  1. ↑ Anderson, Ross A5 – A GSM titkosítási algoritmus  (eng.) (txt)  (a hivatkozás nem elérhető) . sci.crypt (1994. június 7.). Letöltve: 2009. november 24. Az eredetiből archiválva : 2011. szeptember 21..
  2. ↑ Quirke, Jeremy Security a GSM rendszerben (hivatkozás nem elérhető) . AusMobile (2004. május 1.). Az eredetiből archiválva: 2004. július 12. 
  3. ↑ Preneel, Bart Gyors szoftveres titkosítás  ( google könyv) (1994. december). – (26. oldal). Letöltve: 2009. november 24.

Linkek


 Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam
Feistel hálózat
SP hálózat
Egyéb