Proudová šifra

Činnost proudové šifry A5/1, která slouží k zašifrování komunikace mobilním telefonem.

Proudová šifra je v kryptografii typ symetrické šifry, kde vstupní datový tok je kombinován (typicky pomocí funkce XOR) s pseudonáhodným proudem bitů (anglicky keystream) vytvořeným z šifrovacího klíče a šifrovacího algoritmu.[1] Výsledkem je zašifrovaný datový tok (proud), který je šifrován neustále se měnící transformací (na rozdíl od blokové šifry, kde je transformace konstantní). Proudové šifry jsou typicky rychlejší než blokové šifry a pro implementaci potřebují jednodušší hardware. Naopak jsou na rozdíl od blokových šifer náchylnější ke kryptoanalytickým útokům, pokud jsou nevhodně implementovány (počáteční stav nesmí být použit dvakrát).

Inspirace Vernamovou šifrou

Na proudovou šifru může být nahlíženo jako na implementaci neprolomitelné Vernamovy šifry. Tato jednorázová tabulková šifra používá šifrovací klíč zcela náhodných čísel. Šifrovací klíč je kombinován pomocí jednoduché funkce se vstupním textem a tak je vytvořen šifrovaný tvar. Principiální nerozluštitelnost Vernamova konceptu dokázal Claude E. Shannon v roce 1949. Avšak šifrovací klíč musel být (alespoň) o stejné délce jako šifrovaný text a musel být generován úplně náhodně. Systém tak byl velmi těžkopádný, než aby byl zaveden do běžné praxe. Byl používán jen na kritické aplikace.

Proudová šifra využívá mnohem menší klíč, se kterým se lépe pracuje (např. 128bitový). Principem využití tohoto klíče je generování pseudonáhodného proudu bitů (anglicky keystream), který nahrazuje původní jednorázový klíč, který musel být dlouhý jako šifrovaný text. Odstranil se tak problém nutnosti existence dlouhého jednorázového klíče, avšak vznikl jiný problém, protože šifrovací klíč je nyní pseudonáhodný, není opravdu náhodný. Tyto systémy na rozdíl od původního Vernamova lze v principu "rozlomit".

Typy proudových šifer

Proudová šifra generuje pseudonáhodný proud bitů (anglicky keystream), který je vytvořen z šifrovacího klíče a šifrovacího algoritmu, takže výstup je závislý na změnách vnitřního stavu šifry. Aby pokaždé nebyla generována stejná posloupnost, což by snižovalo kvalitu šifry, je vnitřní stav navíc modifikován dalším zdrojem, což se může dít dvěma způsoby. Pokud se tak děje nezávisle na vstupním textu nebo zašifrované zprávě, je šifra hodnocena jako synchronní proudová šifra. Naproti tomu samosynchronní proudová šifra svůj stav mění na základě dat z předešlé části zašifrované zprávy.

Synchronní proudové šifry

V synchronní proudové šifře je proud pseudonáhodných čísel generován nezávisle na vstupním textu nebo zašifrované zprávě. Potom dojde ke kombinaci vygenerovaných čísel se vstupujícím textem (k zakódování) nebo se šifrovaným textem (k dekódování). Nejběžnější formou kombinace keystreamu a vstupního textu je použití logické funkce XOR, což je označováno jako binární doplňková proudová šifra.

V synchronní proudové šifře odesílatel a příjemce musí být přesný v krocích rozkódování, aby to bylo úspěšné. Pokud jsou čísla přidána nebo odebrána ze zprávy v průběhu přenosu, synchronizování je ztraceno. K obnově synchronizace různých offsetů se můžeme pokusit systematicky získat správné dešifrování. Další možností je označit si šifrovaný text značkami v pravidelných intervalech při výstupu.

Pokud je číslo porušeno přenosem (přidáním nebo ztrátou) pouze u jedné z číslic v holém textu, je ovlivněno, ale chyba se nešíří do dalších částí zprávy. Tato vlastnost je užitečná. Když je vysoká míra přenosových chyb, způsobuje to menší pravděpodobnost, že by byla chyba zjištěna bez dalších mechanismů. Navíc jsou kvůli této vlastnosti synchronní proudové šifry velmi náchylné k útokům — pokud útočník může vyměnit jedno číslo v šifrovaném textu, mohl by být schopen provést předvídatelné změny na odpovídajícím bitu otevřeného textu; např. přehodit bit v šifrovém textu způsobující překlápění v otevřeném textu.

Samosynchronní proudové šifry

Jiný přístup používá několik předchozích N čísel šifrovaného textu k vypočítání šifrovacího klíče. Podobná schémata jsou známá jako samosynchronní proudové šifry, asynchronní proudové šifry nebo šifrovaný text automatickým klíčem (CTAK). Tato myšlenka samosynchronních šifer byla patentována v roce 1946, a má tu výhodu, že příjemce bude automaticky synchronizován s generátorem šifrovacích klíčů po obdržení N čísel zašifrovaného textu. Ovlivňuje to jednodušší obnovu, pokud jsou čísla ztracena nebo přidána do zprávy proudu. U jednočíselných chyb je jejich vliv omezen pouze do výše N čísel otevřeného textu.

Příkladem sebesynchronní proudové šifry je bloková šifra v režimu šifrovací zpětné vazby (anglicky Cipher feedback (CFB) mode).

Blokové šifrování otevřené posloupnosti

Z hlediska požadovaného výsledku, tj. pseudonáhodné posloupnosti bitů nebo bloků, lze v širokém smyslu lze za proudovou šifru považovat blokové šifrování nějaké posloupnosti. V nejjednodušším případě to může být posloupnost za sebou jdoucích čísel (s periodou danou velikostí bloku), kde klíč je první člen posloupnosti. Vhodnější je vygenerovaná posloupnost pseudonáhodných čísel, která má velkou periodu.

Lineární posuvné registry se zpětnou vazbou proudových šifer

Lineární zpětná vazba posuvných registrů (anglicky linear feedback shift registers (LFSR)). Binární proudové šifry jsou často stavěny pomocí lineární zpětné vazby posuvných registrů (LFSR), protože mohou být jednoduše implementovány do hardwaru a lze je snadno matematicky analyzovat. Použití LFSR samo o sobě je však nepostačují k zajištění dobrého zabezpečení. Různé systémy byly navrženy pro zvýšení bezpečnosti LFSR.

Nelineární kombinační metody

Protože LFSR jsou ze své podstaty lineární, jedna technika pro odstranění linearity je naplnit výstupy několika paralelními LFSR → do nelineární logické funkce formou kombinačního generátoru. Různé vlastnosti takové kombinační funkce jsou rozhodující k zajištění bezpečnosti výsledného systému, například aby se zabránilo srovnávacím útokům.

Generátory ovládané hodinovým vstupem

Normálně LFSRy fungují pravidelně. První přístup zavádí nelinearitu LFSR, tj. nepravidelnost taktování → kontrolující druhý výstup LFSR. Mezi takové generátory patří stop-and-go generátor, střídavý krokový generátor a komprimační generátor. Střídavý krokový generátor se skládá ze tří lineárních posuvných registrů se zpětnou vazbou, které budeme pro přehlednost nazývat LFSR0, LFSR1 a LFSR2. Výstup jednoho z registrů rozhoduje o tom, který ze zbylých dvou bude používán; například pokud LFSR2 výstup je 0, LFSR0 je synchronní, a pokud výstup je 1, LFSR1 pracuje místo něho (LFSR2). Výstupem exkluzivního ORu jsou poslední bity tvořené LFSR0 a LFSR1. Počáteční stav tří LFSR je klíčem.

Stop-and-go generátor (Beth a Piper, 1984) tvoří dva LFSR. Jeden LFSR je synchronní, pokud výstup druhého je „1“, jinak opakuje svůj předchozí výstup. Tento výstup je pak (v některých verzích) v kombinaci s výstupem třetího LFSR dosahujícího pravidelné úrovně.

Dvě LFSR používají synchronizaci. Pokud je výstup prvního „1“, výstup druhého LFSR se stává výstupem generátoru. Pokud je výstup prvního LFSR „0“, avšak výstup druhého je vyřazen, tak výstupem generátoru není žádný bit. Tento mechanizmus trpí načasováním od druhého generátoru, jelikož rychlost výstupu je variabilní a to způsobem, který závisí na stavu druhého generátoru. Toto může být zmírněno tím, že ukládáme do vyrovnávací paměti na výstupu.

Bezpečnost

Pro bezpečnost proudové šifry je důležité, aby šifrovací klíč měl velikost periody a musí být nemožné jeho obnovení nebo zjištění vnitřního stavu šifrovacího klíče. Kryptografici také požadují, aby šifrovací klíč byl nepředpojatý a rozdílný tak, aby útočníci rozlišili proud od náhodného šumu. Také aby byl snadno zjistitelný vztah mezi šifrovacími klíči, které odpovídají souvisejícím klíčům nebo souvisí s kryptografickými příležitostmi. To by mohlo platit pro všechny klíče, které nejsou slabými klíči, a platí v případě, jestliže útočník může znát nebo vybrat nějaký jednoduchý text či šifrovaný text.

Stejně jako u ostatních útoků v kryptografii, může být proudová šifra napadena osvědčeně, což znamená, že nejsou nutné běžné způsoby, jak rozluštit šifru, ale naznačují, že šifry mohou mít jiné nedostatky.

Bezpečné použití zabezpečené synchronní proudové šifry vyžaduje, aby člověk nikdy používal stejné šifrovací klíče dvakrát. Aplikační návrháři si musí také uvědomit, že většina proudových šifer neposkytuje věrohodnost. Soukromé zašifrované zprávy mohou být změněny v průběhu přenosu.

Krátké období proudových šifer bylo praktickým zklamáním. Například 64bit blokové šifry, jako je DES, lze použít ke generování šifrovacího klíče v OFB režimu. Nicméně, když nepoužíváte plnou zpětnou vazbu, výsledný proud má podobu asi 232 bloků v průměru. Pro mnoho aplikací je toto období příliš krátké. Například pokud je šifrování vykonáváno ve výši 8 MB za sekundu, tak při proudovém období 232 se budou bloky opakovat asi po dobu půl hodiny.

Některé aplikace využívající proudovou šifru RC4 jsou napadnutelné kvůli nedostatkům v klíčových nastaveních. RC4 je rutinní, nové aplikace by měly být schopné buď se vyhnout RC4 nebo se ujistěte, že všechny klíče jsou jedinečné a ideálně nesouvisející (např. generované kryptografické hashovací funkce) a že první bajty šifrovacího klíče jsou zahozeny.

Použití v protokolech

Proudové šifry lze použít jako část řešení v nějakém složitějším protokolu, který zmenšuje nebo odstraňuje jejich nevýhody. Například se proudová šifra používá na krátké úseky, které mají samostatný klíč šifrovaný bezpečnější hierarchicky nadřazenou šifrou. Toto řešení může mít velkou celkovou délku periody a při rozlomení klíče proudové šifry je dešifrován pouze jeden úsek a není přímo narušena bezpečnost sousedních úseků šifry.

Reference

  1. Sloučení proudu bitů se zprávou lze přirovnat k modulaci, kde šifrovací klíč je nosným signálem a zpráva je modulační signál. Zašifrovaný výstup je pak obdobou modulovaného signálu.

Související články

Média použitá na této stránce

Emblem-question.svg
Derivative of and .
A5-1 GSM cipher.svg
A5-1 GSM encryption stream cypher diagram with the three shift register. One register is shifted when the orange bit has the majority over the three orange bits. Then one bit is inserted to a XOR between the blue bits.