Proudová šifra

Typy proudových šifer

Proudová šifra generuje po sobě jdoucí prvky proudu klíčů na základě vnitřního stavu. Tento stav se aktualizuje dvěma způsoby:

1. Pokud se stav mění nezávisle na zprávách otevřeného nebo šifrového textu, je šifra klasifikována jako synchronní proudová šifra.
2. Pokud je stav aktualizován na základě předchozích změn číslic šifrového textu, je šifra klasifikována jako samosynchronizující proudová šifra.

Synchronní proudové šifry

V synchronní proudové šifře se generuje proud pseudonáhodných číslic nezávisle na zprávách otevřeného a zašifrovaného textu a poté se kombinuje s otevřeným textem (k zašifrování) nebo se zašifrovaným textem (k dešifrování). V nejběžnější podobě se používají binární číslice(bity) a proud klíčů se kombinuje s otevřeným textem pomocí operace exkluzivní nebo (XOR). Taková šifra se označuje jako binární aditivní proudová šifra.

U synchronní proudové šifry musí být odesílatel a příjemce synchronní, aby bylo dešifrování úspěšné. Pokud jsou během přenosu do zprávy přidány nebo z ní odstraněny číslice, synchronizace se ztratí. K obnovení synchronizace lze systematicky zkoušet různé posuny, aby se dosáhlo správného dešifrování. Dalším přístupem je označit šifrový text značkami v pravidelných bodech výstupu.

Pokud je však číslice při přenosu poškozena, nikoli přidána nebo ztracena, je ovlivněna pouze jedna číslice v otevřeném textu a chyba se nešíří do dalších částí zprávy. Tato vlastnost je užitečná při vysoké chybovosti přenosu; snižuje však pravděpodobnost, že by chyba byla bez dalších mechanismů odhalena. Navíc jsou synchronní proudové šifry díky této vlastnosti velmi náchylné k aktivnímútokům - pokud útočník dokáže změnit číslici v šifrovém textu, může být schopen provést předvídatelné změny odpovídajícího bitu otevřeného textu; například převrácení bitu v šifrovém textu způsobí převrácení(Toggled) téhož bitu v otevřeném textu.

Samosynchronizující se proudové šifry

Další technikou jsou samosynchronizující proudové šifry, které k výpočtu proudu klíčů používají část z předchozích N číslic šifrového textu. Taková schémata jsou známá také jako asynchronní proudové šifry nebo automatický šifrový text (CTAK). Myšlenka autosynchronizace byla patentována v roce 1946 a její výhodou je, že po přijetí N číslic šifrového textu se přijímač automaticky synchronizuje s generátorem proudu klíčů, což usnadňuje obnovu v případě, že dojde k vypuštění nebo přidání číslic do proudu zprávy. Účinek jednociferných chyb je omezený a týká se pouze N číslic otevřeného textu. Aktivní útoky na samosynchronizující proudové šifry je poněkud obtížnější než na synchronní protějšky.

Příkladem samosynchronizující se proudové šifry je bloková šifra v režimu zpětné vazby šifry (CFB).

Proudové šifry s lineární zpětnou vazbou založené na posuvném registru

Binární proudové šifry se často konstruují pomocí registrů s lineární zpětnou vazbou (LFSR), protože je lze snadno implementovat v hardwaru a lze je rychle matematicky analyzovat. Pouhé použití LFSR však k zajištění dobré bezpečnosti nestačí. Pro zvýšení bezpečnosti LFSR byla navržena různá schémata.

Nelineární kombinační funkce

Vzhledem k tomu, že LFSR jsou ze své podstaty lineární, je jednou z technik odstranění linearity vložení výstupů skupiny paralelních LFSR do nelineární booleovské funkce a vytvoření generátoru kombinací. Různé vlastnosti takové kombinační funkce jsou důležité pro zajištění bezpečnosti výsledného schématu, například pro zamezení korelačních útoků.

Generátory řízené hodinami

Obvykle jsou LFSR pravidelně krokovány. Jednou z technik zavedení nelinearity je nepravidelné taktování LFSR řízené výstupem druhého LFSR. Mezi takové generátory patří generátor stop-and-go, generátor střídavých kroků a generátor smršťování.

Generátor stop-and-go (Beth a Piper, 1984) se skládá ze dvou LFSR. Jeden LFSR je taktován, pokud je výstupem druhého "1", jinak opakuje svůj předchozí výstup. Tento výstup je pak (v některých verzích) kombinován s výstupem třetího LFSR taktovaného pravidelnou rychlostí.

Generátor zmenšování používá jinou techniku. Používají se dva LFSR, oba pravidelně taktované následujícím způsobem:

1. Pokud je výstup prvního LFSR "1", výstup druhého LFSR se stane výstupem generátoru.
2. Pokud je výstup prvního LFSR "0", výstup druhého je vyřazen a generátor nevysílá žádný bit.

Tato technika trpí útoky na časování druhého generátoru, protože rychlost výstupu se mění v závislosti na stavu druhého generátoru. To lze zlepšit vyrovnávací pamětí na výstupu.

Generátor filtrů

Dalším přístupem ke zvýšení bezpečnosti LFSR je předání celého stavu jednoho LFSR do nelineární filtrační funkce.

Další návrhy

Místo lineárního řídicího zařízení lze použít nelineární aktualizační funkci. Například Klimov a Shamir navrhli trojúhelníkové funkce (T-funkce) s jedním cyklem na n bitových slovech.

Zabezpečení

Aby byl proud klíčů bezpečný, musí být perioda proudu klíčů (počet číslic, které jsou vypsány, než se proud zopakuje) dostatečně velká. Pokud se posloupnost opakuje, pak lze překrývající se šifrové texty vzájemně "do hloubky" vyrovnat a existují techniky, které umožňují extrakci otevřeného textu ze šifrových textů generovaných těmito metodami.

Použití

Proudové šifry se často používají v aplikacích, kde se otevřený text vyskytuje v množstvích neznámé délky, jako je tomu například u zabezpečených bezdrátových spojení. Pokud by se bloková šifra měla použít v tomto typu aplikace, musel by návrhář zvolit buď účinnost přenosu, nebo složitost implementace, protože blokové šifry nemohou přímo pracovat s bloky kratšími, než je jejich velikost. Například pokud by 128bitová bloková šifra přijímala oddělené 32bitové dávky otevřeného textu, bylo by třeba vyplnit tři čtvrtiny přenášených dat. Blokové šifry musí být použity v režimu kradení šifrového textu nebo v režimu ukončení zbytkového bloku, aby se vyhnuly vycpávkám, zatímco proudové šifry tento problém odstraňují tím, že pracují s nejmenší přenášenou jednotkou (obvykle bajty).

Další výhodou proudových šifer ve vojenské kryptografii je, že proud šifer může být generován šifrovacím zařízením, které podléhá přísným bezpečnostním opatřením, a poté předán dalším zařízením, např. radiostanici, která v rámci své funkce provede operaci xor. Jiné zařízení může být určeno pro použití v méně bezpečném prostředí.

RC4 je nejpoužívanější proudovou šifrou v softwaru; mezi další patří: Šifry A5/1, A5/2, Chameleon, FISH, Helix, ISAAC, MUGI, Panama, Phelix, Pike, SEAL, SOBER, SOBER-128 a WAKE.

RC4 je jednou z nejpoužívanějších proudových šifer.

Porovnání proudových šifer

StreamCipher	CreationDate	Rychlost (cykly/byte)	(bity)			Útok
			Efektivní Délka klíče	Inicializační vektor	InternalState	Nejznámější	Výpočetní složitost
A5/1	1989	Hlas (Wphone)	54	114	64	Aktivní KPA NEBO Kombinace času a paměti KPA	~2 sekundy OR239.91
A5/2	1989	Hlas (Wphone)	54	114	64?	Aktivní	4,6 milisekundy
RYBA	1993	Poměrně rychle (Wsoft)	Obrovské			Útok známým textem	211
Zrno	Před rokem 2004	Rychle	80	64	160	Derivace klíče	243
HC-256	Před rokem 2004	4 (WP4)	256	256	65536
ISAAC	1996	2.375 (W64-bit) -4.6875 (W32-bit)	8-8288obvykle 40-256	NEUPLATŇUJE SE	8288	(2006) Slabé vnitřní rozdělení v prvním kole	4.67×101240 (2001)
MUGI	1998-2002		128	128	1216	NEUPLATŇUJE SE (2002)	~282
PANAMA	1998	2	256	128?	1216?	Hash Collisions (2001)	282
Phelix	Před rokem 2004	až 8 (Wx86)	256 + 128bitová kódová značka	128?		Diferenciál (2006)	237
Pike	1994	0,9 x FISH (Wsoft)	Obrovské			NEUPLATŇUJE SE (2004)	NEUPLATŇUJE SE (2004)
Py	Před rokem 2004	2.6	8-2048? obvykle 40-256?	64	8320	Teorie kryptoanalýzy (2006)	275
Králík	2003-únor	3,7(WP3)-9,7(WARM7)	128	64	512	NEUPLATŇUJE SE (2006)	NEUPLATŇUJE SE (2006)
RC4	1987	Působivé	8-2048obvykle 40-256	8	2064	Shamirova počáteční bajtová derivace klíčů NEBO KPA	213 NEBO 233
Salsa20	Před rokem 2004	4,24 (WG4) -11 ,84 (WP4)	128 + 64bitová kódová značka	512	512 + 384 (klíč+IV+index)	Diferenciál (2005)	NEUPLATŇUJE SE (2005)
Scream	2002	4 - 5 (Wsoft)	128 + 128bitová kódová značka	32?	64bitová funkce round
SEAL	1997	Velmi rychlý (W32-bit)		32?
SNOW	Před rokem 2003	Velmi dobré (W32-bit)	128 NEBO 256	32
SOBER-128	2003		až 128			Message Forge	2−6
SOSEMANUK	Před rokem 2004	Velmi dobré (W32-bit)	128	128
Trivium	Před rokem 2004	4 (Wx86) - 8 (WLG)	80	80	288	Útok hrubou silou (2006)	2135
Turing	2000-2003	5.5 (Wx86)		160
VEST	2005	42 (WASIC) -64 (WFPGA)	Proměnnáobvykle 80-256	Proměnnáobvykle 80-256	256 - 800	NEUPLATŇUJE SE (2006)	NEUPLATŇUJE SE (2006)
WAKE	1993	Rychle			8192	CPA & CCA	Zranitelné
StreamCipher	CreationDate	Rychlost (cykly/byte)	(bity)			Útok
			Efektivní Délka klíče	Inicializační vektor	InternalState	Nejznámější	Výpočetní složitost

Související stránky

• eSTREAM