Prúdová šifra

Autor: Leandro Alegsa Dátum vytvorenia: 11. októbra 2021

V kryptografii je prúdová šifra šifra so symetrickým kľúčom, pri ktorej sa bity otvoreného textu kombinujú s pseudonáhodným prúdom šifrových bitov (kľúčovým prúdom) pomocou operácie exkluzívneho alebo (xor). V prúdovej šifre sa číslice otvoreného textu šifrujú po jednej a transformácia po sebe nasledujúcich číslic sa počas stavu šifrovania mení. Alternatívny názov je stavová šifra, pretože šifrovanie každej číslice závisí od aktuálneho stavu. V praxi sú číslice zvyčajne jednotlivé bity alebo bajty.

Prúdové šifry predstavujú iný prístup k symetrickému šifrovaniu ako blokové šifry. Blokové šifry pracujú s veľkými blokmi pevnej dĺžky. Prúdové šifry sa zvyčajne vykonávajú vyššou rýchlosťou ako blokové šifry a majú nižšie hardvérové požiadavky. Prúdové šifry však môžu byť náchylné na vážne bezpečnostné problémy, ak sa používajú nesprávne; napríklad najmä sa nikdy nesmie použiť dvakrát ten istý počiatočný stav.

Prúdová šifra využíva oveľa menší a pohodlnejší kryptografický kľúč, napríklad 128-bitový kľúč. Na základe tohto kľúča generuje pseudonáhodný prúd kľúčov, ktorý možno kombinovať s číslicami otvoreného textu podobne ako pri šifrovacom algoritme s jednorazovou podložkou. Pretože je však prúd kľúčov pseudonáhodný, a nie skutočne náhodný, nie je možné uplatniť bezpečnosť spojenú s jednorazovým blokom a je celkom možné, že prúdová šifra bude úplne nezabezpečená.

Činnosť generátora prúdu kľúčov v A5/1, prúdovej šifre založenej na LFSR, ktorá sa používa na šifrovanie hovorov mobilných telefónov.

Typy prúdových šifier

Prúdová šifra generuje postupné prvky kľúčového prúdu na základe vnútorného stavu. Tento stav sa aktualizuje dvoma spôsobmi:

Ak sa stav mení nezávisle od otvoreného textu alebo šifrových správ, šifra sa klasifikuje ako synchrónna prúdová šifra.
Ak sa stav aktualizuje na základe predchádzajúcich zmien číslic šifrového textu, šifra sa klasifikuje ako samosynchronizujúca prúdová šifra.

Synchrónne prúdové šifry

V synchrónnej prúdovej šifre sa generuje prúd pseudonáhodných číslic nezávisle od otvoreného a zašifrovaného textu a potom sa kombinuje s otvoreným textom (na šifrovanie) alebo so zašifrovaným textom (na dešifrovanie). V najbežnejšej forme sa používajú binárne číslice(bity) a prúd kľúčov sa kombinuje s otvoreným textom pomocou operácie exkluzívneho alebo (XOR). Toto sa označuje ako binárna aditívna prúdová šifra.

Pri synchrónnej prúdovej šifre musia byť odosielateľ a príjemca synchrónne, aby bolo dešifrovanie úspešné. Ak sa počas prenosu pridajú alebo odstránia číslice zo správy, synchronizácia sa stratí. Na obnovenie synchronizácie sa môžu systematicky skúšať rôzne posuny, aby sa dosiahlo správne dešifrovanie. Ďalším prístupom je označenie šifrového textu značkami v pravidelných bodoch výstupu.

Ak sa však číslica pri prenose poškodí, a nie pridá alebo stratí, ovplyvní sa len jedna číslica v otvorenom texte a chyba sa nerozšíri do ostatných častí správy. Táto vlastnosť je užitočná, keď je chybovosť prenosu vysoká; znižuje však pravdepodobnosť, že by sa chyba odhalila bez ďalších mechanizmov. Navyše, kvôli tejto vlastnosti sú synchrónne prúdové šifry veľmi náchylné na aktívneútoky - ak útočník dokáže zmeniť číslicu v šifrovom texte, môže byť schopný vykonať predvídateľné zmeny v zodpovedajúcom bite otvoreného textu; napríklad prevrátenie bitu v šifrovom texte spôsobí prevrátenie(Toggled) toho istého bitu v otvorenom texte.

Samosynchronizujúce prúdové šifry

Samosynchronizujúce prúdové šifry sú ďalšou technikou, ktorá na výpočet kľúčového prúdu využíva časť z predchádzajúcich N číslic šifrového textu. Takéto schémy sú známe aj ako asynchrónne prúdové šifry alebo šifrové textové autokey (CTAK). Myšlienka autosynchronizácie bola patentovaná v roku 1946 a jej výhodou je, že prijímač sa po prijatí N číslic šifrového textu automaticky synchronizuje s generátorom prúdu kľúčov, čo uľahčuje obnovu, ak sa číslice vynechajú alebo pridajú do prúdu správy. Účinok jednociferných chýb je obmedzený, ovplyvňujú len do N číslic otvoreného textu. Aktívne útoky na samosynchronizujúce prúdové šifry je o niečo ťažšie vykonať ako na synchrónne náprotivky.

Príkladom samosynchronizujúcej sa prúdovej šifry je bloková šifra v režime spätnej väzby šifry (CFB).

Prúdové šifry s lineárnou spätnou väzbou založené na posuvnom registri

Binárne prúdové šifry sa často konštruujú pomocou lineárnych posunovacích registrov so spätnou väzbou (LFSR), pretože sa dajú ľahko implementovať v hardvéri a rýchlo matematicky analyzovať. Použitie iba LFSR však nestačí na zabezpečenie dobrej bezpečnosti. Na zvýšenie bezpečnosti LFSR boli navrhnuté rôzne schémy.

Nelineárne kombinačné funkcie

Keďže LFSR sú vo svojej podstate lineárne, jednou z techník na odstránenie linearity je privádzať výstupy skupiny paralelných LFSR do nelineárnej booleovskej funkcie na vytvorenie generátora kombinácií. Rôzne vlastnosti takejto kombinačnej funkcie sú dôležité na zaistenie bezpečnosti výslednej schémy, napríklad na zabránenie korelačným útokom.

Generátory riadené hodinami

Normálne sa LFSR pravidelne krokujú. Jednou z techník zavedenia nelinearity je nepravidelné taktovanie LFSR riadené výstupom druhého LFSR. Medzi takéto generátory patrí generátor zastavenia a chodu, generátor striedavého kroku a generátor zmenšovania.

Generátor stop-and-go (Beth a Piper, 1984) pozostáva z dvoch LFSR. Jeden LFSR je taktovaný, ak je výstup druhého "1", inak opakuje svoj predchádzajúci výstup. Tento výstup sa potom (v niektorých verziách) kombinuje s výstupom tretieho LFSR taktovaného pravidelnou rýchlosťou.

Zmenšovací generátor používa inú techniku. Používajú sa dva LFSR, oba pravidelne taktované nasledujúcim spôsobom:

Ak je výstup prvého LFSR "1", výstup druhého LFSR sa stane výstupom generátora.
Ak je výstup prvého LFSR "0", výstup druhého sa zahodí a generátor nevytvorí žiadny bit.

Táto technika trpí útokmi na časovanie druhého generátora, pretože rýchlosť výstupu sa mení spôsobom, ktorý závisí od stavu druhého generátora. To sa dá zlepšiť vyrovnávacou pamäťou na výstupe.

Generátor filtrov

Ďalším prístupom k zlepšeniu bezpečnosti LFSR je odovzdanie celého stavu jedného LFSR do nelineárnej filtračnej funkcie.

Ostatné vzory

Namiesto lineárneho riadiaceho zariadenia možno použiť nelineárnu aktualizačnú funkciu. Klimov a Shamir napríklad navrhli trojuholníkové funkcie (T-funkcie) s jedným cyklom na n bitových slovách.

Zabezpečenie

Aby bol prúd kľúčov bezpečný, musí byť perióda prúdu kľúčov (počet číslic, ktoré sa vypíšu, kým sa prúd kľúčov zopakuje) dostatočne veľká. Ak sa postupnosť opakuje, potom sa prekrývajúce sa šifrové texty môžu navzájom "do hĺbky" vyrovnať a existujú techniky, ktoré umožňujú extrakciu otvoreného textu zo šifrových textov vytvorených týmito metódami.

Použitie

Prúdové šifry sa často používajú v aplikáciách, kde sa otvorený text dodáva v množstvách neznámej dĺžky, ako napríklad v bezpečných bezdrôtových spojeniach. Ak by sa bloková šifra mala použiť v tomto type aplikácie, návrhár by si musel vybrať buď účinnosť prenosu, alebo zložitosť implementácie, pretože blokové šifry nemôžu priamo pracovať s blokmi kratšími, ako je ich veľkosť. Ak by napríklad 128-bitová bloková šifra prijímala oddelené 32-bitové dávky otvoreného textu, tri štvrtiny prenášaných údajov potrebujú vypchávku. Blokové šifry sa musia používať v režime kradnutia šifrového textu alebo v režime ukončenia zvyškového bloku, aby sa zabránilo vypĺňaniu, zatiaľ čo prúdové šifry tento problém eliminujú tým, že pracujú na najmenšej prenášanej jednotke (zvyčajne bajtoch).

Ďalšou výhodou prúdových šifier vo vojenskej kryptografii je, že prúd šifier môže byť vygenerovaný šifrovacím zariadením, ktoré podlieha prísnym bezpečnostným opatreniam, a potom odovzdaný ďalším zariadeniam, napr. rádiovému prijímaču, ktoré vykonajú operáciu xor ako súčasť svojej funkcie. Iné zariadenie môže byť určené na použitie v menej bezpečnom prostredí.

RC4 je najrozšírenejšia prúdová šifra v softvéri; medzi ďalšie patria: Šifry A5/1, A5/2, Chameleon, FISH, Helix, ISAAC, MUGI, Panama, Phelix, Pike, SEAL, SOBER, SOBER-128 a WAKE.

RC4 je jednou z najpoužívanejších prúdových šifier.

Porovnanie prúdových šifier

StreamCipher	CreationDate	Rýchlosť (cykly/byte)	(bitov)			Útok
StreamCipher	CreationDate	Rýchlosť (cykly/byte)	Účinné Dĺžka kľúča	Inicializačný vektor	InternalState	Najznámejšie	Výpočtová zložitosť
A5/1	1989	Hlas (Wphone)	54	114	64	Aktívny KPA alebo Kompromis medzi časom a pamäťou KPA	~2 sekundy OR239^.91
A5/2	1989	Hlas (Wphone)	54	114	64?	Aktívne	4,6 milisekundy
RYBY	1993	Pomerne rýchlo (Wsoft)	Obrovské			Útok známym textom	²¹¹
Obilie	Pred rokom 2004	Rýchle	80	64	160	Deerivácia kľúča	²⁴³
HC-256	Pred rokom 2004	4 (_WP4)	256	256	65536
ISAAC	1996	2.375 (W64-bit) -4.6875 (W32-bit)	8-8288obvykle 40-256	NEUPLATŇUJE SA	8288	(2006) Prvé kolo - slabá vnútorná stavová deerivácia	4.67×101240 (2001)
MUGI	1998-2002		128	128	1216	NEUPLATŇUJE SA (2002)	~282
PANAMA	1998	2	256	128?	1216?	Hash Collisions (2001)	²⁸²
Phelix	Pred rokom 2004	až 8 (Wx86)	256 + 128-bitová kódová značka	128?		Diferenciál (2006)	²³⁷
Pike	1994	0,9 x FISH (Wsoft)	Obrovské			NEUPLATŇUJE SA (2004)	NEUPLATŇUJE SA (2004)
Py	Pred rokom 2004	2.6	8-2048? zvyčajne 40-256?	64	8320	Teória kryptoanalýzy (2006)	²⁷⁵
Králik	2003-február	3,7(_WP3)-9,7(_WARM7)	128	64	512	NEUPLATŇUJE SA (2006)	NEUPLATŇUJE SA (2006)
RC4	1987	Pôsobivé	8-2048obvykle 40-256	8	2064	Shamir Initial-Bytes Key-Derivation OR KPA	²¹³ ALEBO ²³³
Salsa20	Pred rokom 2004	4,24 (_WG4) -11 ,84 (_WP4)	128 + 64-bitový kód Nonce	512	512 + 384 (kľúč+IV+index)	Diferenciál (2005)	NEUPLATŇUJE SA (2005)
Výkrik	2002	4 - 5 (Wsoft)	128 + 128-bitová kódová značka	32?	64-bitová zaokrúhľovacia funkcia
SEAL	1997	Veľmi rýchle (W32-bit)		32?
SNOW	Pred rokom 2003	Veľmi dobré (W32-bit)	128 ALEBO 256	32
SOBER-128	2003		až 128			Správa Forge	2−6
SOSEMANUK	Pred rokom 2004	Veľmi dobré (W32-bit)	128	128
Trivium	Pred rokom 2004	4 (Wx86) - 8 (WLG)	80	80	288	Útok hrubou silou (2006)	²¹³⁵
Turing	2000-2003	5.5 (Wx86)		160
VEST	2005	42 (_WASIC) -64 (WFPGA)	Variabilnéobvykle 80-256	Variabilnéobvykle 80-256	256 - 800	NEUPLATŇUJE SA (2006)	NEUPLATŇUJE SA (2006)
WAKE	1993	Rýchle			8192	CPA & CCA	Zraniteľné
StreamCipher	CreationDate	Rýchlosť (cykly/byte)	(bitov)			Útok
StreamCipher	CreationDate	Rýchlosť (cykly/byte)	Účinné Dĺžka kľúča	Inicializačný vektor	InternalState	Najznámejšie	Výpočtová zložitosť

Súvisiace stránky

eSTREAM

Otázky a odpovede

Otázka: Čo je to prúdová šifra?

Odpoveď: Prúdová šifra je šifra so symetrickým kľúčom, pri ktorej sa bity otvoreného textu kombinujú s pseudonáhodným prúdom šifrových bitov (prúdom kľúčov) pomocou operácie exkluzívneho alebo (xor).

Otázka: Ako sa líši od blokových šifier?

Odpoveď: Prúdové šifry sa zvyčajne vykonávajú vyššou rýchlosťou ako blokové šifry a majú nižšie hardvérové požiadavky. Blokové šifry pracujú s veľkými blokmi pevnej dĺžky, zatiaľ čo prúdové šifry šifrujú číslice po jednej a transformácia po sebe nasledujúcich číslic sa počas stavu šifrovania mení.

Otázka: Aký typ kľúčov sa používa?

Odpoveď: Prúdové šifry využívajú oveľa menšie a výhodnejšie kryptografické kľúče, napríklad 128-bitové kľúče.

Otázka: Ako sa generuje prúd kľúčov?

Odpoveď: Tok kľúčov sa generuje na základe použitého kryptografického kľúča podobne ako pri šifrovacom algoritme s jednorazovým blokom. Pretože je však tok kľúčov pseudonáhodný a nie skutočne náhodný, nie je možné použiť zabezpečenie spojené s jednorazovým blokom.

Otázka: Prečo nikdy nesmiete použiť ten istý počiatočný stav dvakrát?

Odpoveď: Použitie rovnakého počiatočného stavu dvakrát môže viesť k vážnym bezpečnostným problémom, pretože útočníkom uľahčuje dešifrovanie údajov bez toho, aby poznali váš kryptografický kľúč alebo k nemu mali prístup.

Otázka: Sú s používaním prúdových šifier spojené nejaké riziká?

Odpoveď: Áno, ak sa používajú nesprávne alebo bez vykonania náležitých bezpečnostných opatrení, potom je s používaním prúdových šifier spojené riziko, pretože pri nesprávnom zaobchádzaní môžu byť úplne nezabezpečené.