Streamová šifra

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. prosince 2020; kontroly vyžadují 2 úpravy .

Proud [1] [2] nebo proudová šifra [3] je symetrická šifra , ve které je každý znak otevřeného textu převeden na znak šifrovaného textu v závislosti nejen na použitém klíči, ale také na jeho umístění v proudu otevřeného textu. Proudová šifra implementuje odlišný přístup k symetrickému šifrování než blokové šifry .

Historie

Proudové šifry založené na posuvných byly aktivně používány během válečných let, dlouho před příchodem elektroniky. Bylo snadné je navrhnout a realizovat.

V roce 1965 Ernst Selmer, hlavní kryptograf norské vlády, vyvinul teorii sekvence posuvného registru . Později Solomon Golomb , matematik americké Národní bezpečnostní agentury , napsal knihu nazvanou „Sekvence posunového registru“, ve které nastínil své hlavní úspěchy v této oblasti, stejně jako úspěchy Selmera.

Dílo Clauda Shannona , vydané v roce 1949, přineslo velkou popularitu streamovým šifrám , ve kterých Shannon prokázal absolutní bezpečnost Vernamovy šifry (také známé jako jednorázová podložka). Ve Vernamově šifře má klíč délku rovnou délce přenášené zprávy samotné. Klíč se používá jako gama , a pokud je každý bit klíče vybrán náhodně, pak není možné šifru prolomit (protože všechny možné otevřené texty budou stejně pravděpodobné). K dnešnímu dni bylo vytvořeno velké množství algoritmů pro šifrování toku , jako jsou: A3 , A5 , A8 , MUGI , PIKE , RC4 , SEAL .

Režim gama pro proudové šifry

Nejjednodušší implementace proudové šifry je znázorněna na obrázku. Generátor gama vytváří klíčový proud (gama): . Označme bitový tok prostého textu jako . Poté se bitový proud šifrovaného textu získá použitím operace XOR : kde . $k_1,k_2,k_3,\tečky ,k_L$ $m_1, m_2, m_3,\tečky ,m_L$ $c_1,c_2,c_3,\tečky ,c_L$ $c_i=m_i\oplus k_i$

Dešifrování se provádí operací XOR mezi stejnou gama a šifrovým textem: . $m_i=c_i\oplus k_i$

Je zřejmé, že pokud sekvence gama bitů nemá periodu a je vybrána náhodně, pak není možné šifru prolomit. Ale tento režim šifrování má také negativní vlastnosti. Klíče, které jsou délkou srovnatelné s přenášenými zprávami, jsou tedy v praxi těžko použitelné. Proto se obvykle používá menší délka klíče (například 128 bitů). Pomocí něj se vygeneruje pseudonáhodná herní sekvence (musí splňovat Golombovy postuláty ). Pseudonáhodnost gama lze přirozeně využít při útoku na proudovou šifru.

Klasifikace proudových šifer

Předpokládejme například, že v režimu gama pro proudové šifry byl jeden znak šifrového textu zkreslen během přenosu komunikačním kanálem . Je zřejmé, že v tomto případě budou všechny znaky přijaté bez zkreslení správně dekódovány. Ztratí se pouze jeden znak textu. A nyní si představme, že jeden ze znaků šifrového textu byl ztracen během přenosu komunikačním kanálem. To povede k nesprávnému dekódování veškerého textu následujícího po ztraceném znaku.
Prakticky všechny kanály přenosu dat pro streamingové šifrovací systémy obsahují rušení . Proto, aby se zabránilo ztrátě informací, je vyřešen problém synchronizace šifrování a dešifrování textu. Podle způsobu řešení tohoto problému se šifrovací systémy dělí na synchronní a samosynchronizační.

Synchronní proudové šifry

Definice:

Synchronní proudové šifry (SPC) jsou šifry, ve kterých je proud klíčů generován nezávisle na otevřeném a šifrovaném textu.

Když je zašifrován, generátor toku klíčů vytváří bity toku klíčů, které jsou identické s bity toku klíčů při dešifrování. Ztráta znaku šifrovaného textu způsobí, že se oba generátory nesynchronizují, což znemožní dešifrování zbytku zprávy. Je zřejmé, že v této situaci se musí odesílatel a příjemce znovu synchronizovat, aby mohli pokračovat v práci.

Synchronizace se obvykle provádí vložením speciálních značek do přenášené zprávy. Výsledkem je, že znak ztracený během přenosu vede k nesprávnému dešifrování pouze do doby, než je přijat jeden z tokenů.

Všimněte si, že synchronizace musí být provedena tak, aby se žádná část toku klíčů neopakovala. Proto nemá smysl převádět generátor do dřívějšího stavu.

Výhody SPS:

žádný efekt šíření chyb (pouze zkreslený bit bude dekódován nesprávně);
zabránit jakémukoli vkládání a mazání šifrovaného textu, protože by způsobilo ztrátu synchronizace a bylo by odhaleno.

Nevýhody SPS:

zranitelný vůči změnám jednotlivých bitů šifrovaného textu. Pokud útočník zná prostý text , může tyto bity změnit tak, aby byly dešifrovány, jak chce.

Samosynchronizující proudové šifry

Základní myšlenka konstrukce byla patentována v roce 1946 v USA .

Definice:

Samosynchronizující proudové šifry (asynchronní proudové šifry (ATS)) jsou šifry, ve kterých je proud klíčů tvořen funkcí klíče a pevným počtem znaků šifrovaného textu.

Vnitřní stav generátoru toku klíčů je tedy funkcí předchozích N bitů šifrového textu. Proto je generátor dešifrovacího toku klíčů, který přijal N bitů, automaticky synchronizován s generátorem šifrování.

Implementace tohoto režimu je následující: každá zpráva začíná náhodnou hlavičkou o délce N bitů; hlavička je zašifrována, přenesena a dešifrována; dekódování je špatné, ale po těchto N bitech budou oba generátory synchronizovány.

Výhody APS:

Vzrušující statistiky v prostém textu. Protože každý znak otevřeného textu ovlivňuje další šifrovaný text, statistické vlastnosti otevřeného textu jsou rozšířeny na celý šifrovaný text. Proto může být PNW odolnější vůči útokům redundance prostého textu než PNW.

Nevýhody APS:

šíření chyb (každý chybný bit šifrového textu odpovídá N chybám v otevřeném textu);
citlivé na otevření opakovaným přenosem.

Proudové šifry založené na posuvných registrech s lineární zpětnou vazbou (LFSR)

Teoretický základ

Existuje několik důvodů pro použití lineárních posuvných registrů v kryptografii:

vysoce výkonné kryptografické algoritmy
použití pouze nejjednodušších operací sčítání a násobení, implementovaných hardwarově téměř ve všech výpočetních zařízeních
dobré kryptografické vlastnosti (vygenerované sekvence mají dlouhou periodu a dobré statistické vlastnosti)
snadnost analýzy pomocí algebraických metod díky lineární struktuře

Definice: Posuvný registr s lineární zpětnou vazbou délky L se skládá z L očíslovaných buněk , z nichž každá je schopna uložit 1 bit a má jeden vstup a jeden výstup; a hodinový signál , který řídí posun dat. Během každé jednotky času se provádějí následující operace: $0,1,2,\tečky L-1$

obsah buňky tvoří část výstupní sekvence; $L-1$
obsah -té buňky se přesune do buňky pro libovolné , . $i$ $i+1$ $i$ $0\leq i<L-1$
nový obsah buňky je určen bitem zpětné vazby, který je vypočítán sčítáním modulo 2 s určitými koeficienty bitů buňky . $0$ $0,1,2,\tečky L-1$

V prvním kroku: Ve druhém kroku: Následující vztah popisuje činnost LFSR obecně: Pokud do všech buněk zapíšeme bity rovné nule, pak systém vygeneruje sekvenci sestávající ze všech nul. Pokud zapíšeme nenulové bity, dostaneme polonekonečnou posloupnost. Posloupnost je určena koeficienty Podívejme se, jaká může být perioda takového systému: Počet nenulových plnění: Proto, . Po výskytu jedné náplně, která byla dříve, se proces začne opakovat. Proces plnění registru, jak je znázorněno výše, je reprezentován lineární diferenční rovnicí. Přeneseme všechny členy na jednu část rovnosti, dostaneme: . $S_L=c_1 \cdot S_{L-1}\oplus c_2 \cdot S_{L-2}\oplus \tečky \oplus c_L \cdot S_0.$

$S_{L+1}=c_1 \cdot S_L\oplus c_2 \cdot S_{L-1}\oplus \tečky \oplus c_L \cdot S_1.$

$S_j=c_1 \cdot S_{j-1}\oplus c_2 \cdot S_{j-2}\oplus \tečky\oplus c_L \cdot S_{jL}.$
$c_1,c_2,\tečky ,c_L.$
$T$
$2^{L}-1.$ $T\leqslant 2^L-1$

$S_{j}\oplus c_{1}\cdot S_{j-1}\oplus c_{2}\cdot S_{j-2}\oplus \dots \oplus c_{L}\cdot S_{jL }=0$

Označme: . Pak: ${\displaystyle S_{j}=D^{-j))$
$(1 \oplus c_1\cdot D \oplus c_2\cdot D^2 \oplus \dots \oplus c_L\cdot D^L )\cdot D^{-j}.$

$C(D) = 1 \oplus c_1\cdot D \oplus c_2 \cdot D^2 \oplus \dots \oplus c_L\cdot D^L.$

Důležitou vlastností tohoto polynomu je redukovatelnost.
Definice:
Polynom se nazývá redukovatelný , pokud jej lze reprezentovat jako součin dvou polynomů menších stupňů s koeficienty z daného oboru (v našem případě s binárními koeficienty). Pokud k takové reprezentaci nedojde, pak se o polynomu říká, že je neredukovatelný .
Pokud je polynom ireducibilní a primitivní , pak bude perioda stejná jako maximální možná perioda, rovna $C(D)$ $2^{L}-1.$

Příklad: Vezměte ireducibilní primitivní polynom Tento polynom lze zapsat jako - stupně, ve kterých existují nenulové koeficienty, jsou zapsány. Do buněk zapíšeme počáteční stav a určíme délku periody generátoru: $C(D)=D^{3}+D^{2}+1(c_{3}=1,c_{2}=1,c_{1}=0).$ $(3,2,0)$
$001$

Stůl. Stanovení periody generátoru

Zpětná vazba	Buňka0	Buňka1	buňka2
jeden	0	0	jeden
0	jeden	0	0
jeden	0	jeden	0
jeden	jeden	0	jeden
jeden	jeden	jeden	0
0	jeden	jeden	jeden
0	0	jeden	jeden
jeden	0	0	jeden

Perioda generátoru je Výstupem generátoru bude sekvence: Uveďme příklady některých primitivních polynomů modulo 2: $7(2^{3}-1=7).$ $1001011 1001011 1001011\tečky$

$(1.0), (2.1.0), (3.1.0), (4.1.0), (5.2.0), (6.1.0), (7.1 ,0), (7,3,0), (8 ,4,3,2,0), (9,4,0)\tečky$

Lineární složitost

Lineární složitost binární sekvence je jednou z nejdůležitějších charakteristik operace LFSR. Proto se tomuto tématu věnujeme podrobněji.
Před definicí lineární složitosti zavedeme nějakou notaci. - nekonečná posloupnost se členy - konečná posloupnost délky , jejíž členy jsou LFSR, se říká, že generuje posloupnost , pokud existuje nějaký počáteční stav, ve kterém se výstupní posloupnost LFSR shoduje s . Podobně se říká, že LFSR generuje konečnou sekvenci , pokud existuje nějaký počáteční stav, pro který má výstupní sekvence LFSR jako první členy členy sekvence . Nakonec uvedeme definici lineární složitosti nekonečné binární posloupnosti. Definice: Lineární složitost nekonečné binární posloupnosti je číslo , které je definováno takto:
$S$ $S1,S2,S3,\tečky$
$S_{n}$ $n$ $S_1,S_2,S_3,\tečky,S_{n-1}.$
$S$ $S$ $S_{n}$ $n$ $S_{n}$

$S$ $L(S)$

Pokud je nulová posloupnost , pak $S$ $S=0,0,0,0,\tečky ,$ $L(S)=0.$
Pokud neexistuje žádný LFSR, který generuje , pak se rovná nekonečnu . $S$ $L(S)$
Jinak existuje délka nejkratšího LFSR, který generuje . $L(S)$ $S$

Definice:
Lineární složitost konečné binární posloupnosti je číslo , které se rovná délce nejkratšího LFSR, který generuje posloupnost, která má jako první členy . Vlastnosti lineární složitosti: Nechť a být binární posloupnosti. Pak: 1. Pro libovolnou lineární složitost podposloupnosti vyhoví nerovnosti 2. právě tehdy, když je nulová posloupnost délky . 3. tehdy a jen tehdy, když . 4. Jestliže je periodické s periodou , pak 5. Účinným algoritmem pro určení lineární složitosti konečné binární posloupnosti je Berlekamp-Masseyův algoritmus . $S_{n}$ $L(S_n)$ $n$ $S_{n}$
$S$ $K$
$n>0$ $S_{n}$ $0\leqslant L(S_n) \leqslant n.$
$L(S_{n})=0$ $S_{n}$ $n$
$L(S_{n})=n$ $S_{n}=0,0,0,\tečky ,1$
$S$ $N$ $L(S_{n})\leqslant N.$
$L(S \oplus K)\leqslant L(S) + L(K).$

Proudové šifry založené na LFSR. Komplikace

Bohužel výstupní sekvence LFSR je snadno předvídatelná. Při znalosti 2L znaků výstupní sekvence je tedy snadné najít počáteční zaplnění registru řešením soustavy lineárních rovnic (viz odstavec „Streamové šifry založené na posuvných registrech s lineární zpětnou vazbou“).

Předpokládá se, že pro kryptografické použití musí mít výstupní sekvence LFSR následující vlastnosti:

velké období
vysoká lineární složitost
dobré statistické vlastnosti

Existuje několik metod pro návrh generátorů toku klíčů, které ničí lineární vlastnosti LFSR, a tím činí takové systémy kryptograficky bezpečnějšími:
1. pomocí nelineární funkce , která kombinuje výstupy několika LFSR,
2. pomocí funkce nelineárního filtrování pro obsah každé buňky jednoho LFSR
3. použití výstupu jednoho LFSR k řízení hodinového signálu jednoho (nebo několika) LFSR.

Nelineární kombinace generátorů

Je známo, že každou booleovskou funkci lze zapsat jako modulo 2 součet součinů řádů nezávislých proměnných , . Tento výraz se nazývá algebraická normální forma funkce . Nelineární řád funkce je maximální řád členů v zápisu její algebraické normální formy. Například booleovská funkce má nelineární řád 3. Maximální možné nelineární řád booleovské funkce je roven počtu proměnných Předpokládejme nyní, že máme lineární zpětnovazební posuvné registry, jejich délky jsou párově různé a větší než dva. Všechny registry jsou kombinovány s nelineární funkcí , jak je znázorněno na obrázku. Funkce je reprezentována v algebraické normální formě. Pak je lineární složitost toku klíčů . Jsou-li párová prvočísla, pak je délka periody toku klíčů rovna: . Například když , tak . A délka období klíčového proudu je . $f(x_{1},x_{2},\tečky ,x_{n})$ $m$ $0 \leqslant m \leqslant n$ $F$ $F$
$f(x_1,x_2,x_3,x_4 )=x_1 \oplus x_2 \oplus x_4 \oplus x_1 x_3 \oplus x_2 x_3 x_4$ $n.$
$n$ $L_1, L_2, L_3, \tečky, L_n$ $f(x_1,x_2,\tečky,x_n)$ $F$ $f(L_1,L_2,\tečky,L_n)$
$L_1, L_2,\tečky, L_n$ $(2^{L_1}-1)\cdot(2^{L_2}-1) \cdots (2^{L_n }-1)$ $L_{i}=10$ $(2^{L_1}-1)\cca 10^3$ $(10^{3})^{n}$

Příklad (Geffův generátor):
Tento generátor používá tři LFSR kombinované nelineárním způsobem. Délky těchto registrů jsou párová prvočísla. Nelineární funkci pro daný generátor lze zapsat takto: ${\displaystyle L_{1},L_{2},L_{3))$

$f(x_1, x_2, x_3 )=x_1 x_2 \oplus (1+x_2) x_3=x_1 x_2 \oplus x_2 x_3 \oplus x_3.$

Délka období: $(2^{L_1}-1)\cdot(2^{L_2}-1)\cdot(2^{L_3}-1).$

Lineární složitost: $L=L_{1}\cdot L_{2}+L_{2}\cdot L_{3}+L_{3}.$

Geffův generátor je kryptograficky slabý, protože informace o stavech generátorů LFSR 1 a LFSR 3 jsou obsaženy v jeho výstupní sekvenci. Abychom tomu porozuměli, označme -té výstupní bity LFSR 1,2,3 a tok klíčů . Pak pravděpodobnost korelace posloupnosti vzhledem k posloupnosti : $x_{1}(t),x_{2}(t),x_{3}(t),z(t)$ $t$ $x_1(t)$ $z(t)$

$P(z(t)=x_{1}(t))=P(x_{2}(t)=1)+P(x_{2}(t)=0)\cdot P(x_{ 3}(t)=x_{1}(t))=1/2+1/2\cdot 1/2=3/4.$

Podobně z tohoto důvodu, navzdory dlouhému období a poměrně vysoké lineární složitosti, se Geffův generátor hodí ke korelačním útokům. $P(z(t)=x_{3}(t))=3/4.$

Generátory na nelineárních filtrech

Výstup každé buňky je přiváděn na vstup nějaké nelineární booleovské filtrační funkce . Předpokládejme, že funkce filtrování je řádná , pak je lineární složitost toku klíčů nanejvýš . $F$ $m$ $L_m=\součet^{m}_{i=1} {L \vyberte i}$

Hodinové oscilátory

V nelineárních kombinacích oscilátorů a nelineárních filtrových oscilátorů je pohyb dat ve všech LFSR řízen jediným hodinovým signálem.
Hlavní myšlenkou fungování uvažovaného typu generátorů je zavést nelinearitu do provozu generátorů toku klíčů založených na LFSR řízením hodinového signálu jednoho registru výstupní sekvencí druhého.
Existují 2 typy oscilátorů založených na řízení hodin:
1. oscilátor s proměnnou výškou tónu
2. kompresní oscilátor.

Generátor proměnlivé výšky

Hlavní myšlenka:
LFSR 1 se používá k ovládání pohybu bitů dalších dvou LFSR 2 a 3.

Operační algoritmus:
1. Registr LFSR 1 je synchronizován externím hodinovým signálem
2. Pokud je výstup registru LFSR 1 jedna , pak je registr LFSR 2 napájen hodinovým signálem a LFSR 3 opakuje svůj předchozí výstupní bit (pro počáteční čas je předchozí výstupní bit LFSR 3 považován za rovný 0 )
3. Pokud je výstup registru LFSR 1 nula , pak se do registru LFSR 3 přivede hodinový signál a LFSR 2 zopakuje svůj předchozí výstup bit (pro počáteční dobu je předchozí výstupní bit LFSR 2 rovněž považován za rovný 0)
4. Výstupní bitová sekvence generátoru s proměnným krokem je výsledkem aplikace bitové operace XOR na výstupní sekvence LFSR 2 a LFSR 3 registrů.

Zvýšení bezpečnosti generátorů s proměnným sklonem:

délky registrů RLOS 1, RLLS 2, RLLS 3 je nutné volit ve dvojicích prvočísly
délky těchto registrů musí být blízká čísla.

Kompresní generátor

Řídicí registr LFSR 1 se používá k ovládání výstupu LFSR 2. Algoritmus:

Registry RLOS 1 a RLLS 2 jsou synchronizovány společným hodinovým signálem ;
Pokud je výstupní bit LFSR 1 roven 1, je výstup generátoru tvořen výstupním bitem registru LFSR 2;
Pokud je výstupní bit LFSR 1 0, výstupní bit LFSR 2 je vyřazen.

Generátor komprese je jednoduchý, škálovatelný a má dobré bezpečnostní vlastnosti. Jeho nevýhodou je, že rychlost generování klíčů nebude konstantní, pokud nebudou přijata určitá opatření.

Pro zvýšení bezpečnosti kompresního generátoru:

délky registrů LFSR 1 a LFSR 2 musí být hlavní čísla ;
mezi registry LFSR 1 a LFSR 2 je žádoucí použít skryté spojení.

Hlavní rozdíly mezi proudovými šiframi a blokovými šiframi

Většinu existujících šifrovacích tajných klíčů lze jednoznačně klasifikovat jako proudové šifry nebo blokové šifry . Teoretická hranice mezi nimi je ale dost nejasná. Algoritmy blokové šifry se například používají v režimu proudové šifry (příklad: pro algoritmus DES , režimy CFB a OFB ).

Zvažte hlavní rozdíly mezi proudovými a blokovými šiframi, a to nejen z hlediska jejich bezpečnosti a pohodlí, ale také z hlediska jejich studia ve světě:

Nejdůležitější výhodou proudových šifer oproti šifrám blokovým je vysoká rychlost šifrování, úměrná rychlosti vstupní informace; proto je poskytováno šifrování téměř v reálném čase bez ohledu na objem a bitovou hloubku převedeného datového toku.
v synchronních proudových šifrách (na rozdíl od blokových šifer) nedochází k žádnému efektu šíření chyb, to znamená, že počet zkreslených prvků v dešifrované sekvenci se rovná počtu zkreslených prvků v šifrované sekvenci, které přišly z komunikačního kanálu .
struktura klíče streamu může mít zranitelná místa, která umožňují kryptoanalytikovi získat další informace o klíči (například s malou periodou klíče může kryptoanalytik použít nalezené části toku klíče k dešifrování následného soukromého textu).
PN, na rozdíl od PN, lze často napadnout lineární algebrou (protože výstupy jednotlivých posuvných registrů lineární zpětné vazby lze korelovat s gama). Lineární a diferenciální analýza se také velmi úspěšně používá k prolomení proudových šifer .

Nyní o stavu světa:

většina práce na analýze a prolomení blokových šifer se zabývá šifrovacími algoritmy založenými na standardu DES ; pro proudové šifry neexistuje žádná vyhrazená oblast studia; hackerské metody jsou velmi rozmanité.
pro proudové šifry je stanovena sada požadavků, které jsou kritérii spolehlivosti (velké periody výstupních sekvencí, Golombovy postuláty , nelinearita); neexistují žádná taková jasná kritéria pro BS .
výzkum a vývoj proudových šifer provádějí především evropská kryptografická centra, blokové šifry - americká.
studium proudových šifer je dynamičtější než blokové šifry; v oblasti algoritmů DES nebyly v poslední době zaznamenány žádné pozoruhodné objevy, zatímco v oblasti proudových šifer došlo k mnoha úspěchům a neúspěchům (některá schémata, která se po dalším zkoumání zdála stabilní, nesplnila naděje vynálezců) .

Navrhování proudových šifer

Podle Rainera Rueppela existují čtyři hlavní přístupy k návrhu streamové šifry:

Systémově teoretický přístup je založen na vytvoření složitého, dříve neprozkoumaného problému pro kryptoanalytika.
Přístup založený na teorii složitosti je založen na složitém, ale dobře známém problému (např. faktorizace čísel nebo diskrétní logaritmus ).
Přístup informačních technologií je založen na snaze skrýt před kryptoanalytikem otevřený text – bez ohledu na to, kolik času stráví dešifrováním, kryptoanalytik nenajde jednoznačné řešení.
Randomizovaný přístup je založen na vytvoření velkého úkolu; kryptograf se tím snaží fyzicky znemožnit řešení problému dešifrování. Kryptograf může například zašifrovat článek a klíč bude indikovat, které části článku byly při šifrování použity. Kryptanalytik bude muset vyzkoušet všechny náhodné kombinace částí článku, než bude mít štěstí a určí klíč.

Teoretická kritéria Reinera Rüppela pro návrh řadových systémů:

dlouhá období výstupních sekvencí;
velká lineární složitost;
difuze - rozptyl redundance v podstrukturách, "rozmazávání" statistik v celém textu;
každý bit toku klíčů musí být komplexní transformací většiny bitů klíče;
kritérium nelinearity pro logické funkce.

Dosud se neprokázalo, že by tato kritéria byla nezbytná nebo dostatečná pro zabezpečení systému šifrování streamování. Za zmínku také stojí, že pokud má kryptoanalytik neomezený čas a výpočetní výkon, pak jediná realizovatelná proudová šifra, která je proti takovému protivníkovi bezpečná, je jednorázová podložka.

Kryptoanalýza. Útoky na proudové šifry

Všechny metody kryptoanalýzy proudových šifer se obvykle dělí na silové (útok „hrubá síla“), statistické a analytické.

Power Attacks

Tato třída zahrnuje útoky, které provádějí kompletní výčet všech možných možností. Složitost vyčerpávajícího vyhledávání závisí na počtu všech možných řešení problému (zejména na velikosti klíčového prostoru nebo prostoru otevřeného textu). Tato třída útoků je použitelná pro všechny druhy systémů šifrování proudu. Při vývoji šifrovacích systémů se vývojáři snaží, aby tento typ útoku byl co nejúčinnější ve srovnání s jinými existujícími metodami hackování.

Statistické útoky

Statistické útoky spadají do dvou podtříd:

metoda kryptoanalýzy statistických vlastností rozsahu šifrování : zaměřená na studium výstupní sekvence kryptosystému; kryptoanalytik se pomocí různých statistických testů pokouší nastavit hodnotu dalšího bitu v sekvenci s pravděpodobností větší, než je pravděpodobnost náhodného výběru.
Metoda kryptoanalýzy složitosti sekvence : Kryptanalytik se snaží najít způsob, jak vytvořit sekvenci podobnou gama, ale jednodušeji implementovatelným způsobem.

Obě metody využívají principu lineární složitosti.

Analytické útoky

Tento typ útoku je zvažován za předpokladu, že kryptoanalytik zná popis generátoru, veřejný text a odpovídající soukromý text. Úkolem kryptoanalytika je určit použitý klíč (počáteční naplnění registrů). Typy analytických útoků aplikovaných na synchronní proudové šifry:

korelace
kompromis "čas-paměť"
inverze
"navrhnout a určit"
pro načtení klíče a reinicializaci
XSL útok

Korelační útoky

Jsou to nejběžnější útoky na prolomení proudových šifer.

Je známo, že práce na otevření kryptosystému se může výrazně snížit, pokud nelineární funkce předá na výstup informace o vnitřních součástech generátoru. Proto, aby se obnovilo počáteční plnění registrů, korelační útoky zkoumají korelaci výstupní sekvence šifrovacího systému s výstupní sekvencí registrů.

Existují následující podtřídy korelačních útoků:

Základní korelační útoky
Útoky založené na kontrole parity s nízkou váhou
Útoky založené na použití konvolučních kódů
Útoky pomocí techniky turbo kódu
Útoky založené na obnově lineárních polynomů
Rychlé korelační útoky.

Základní korelační útoky

Vezměme si příklad Siegenthalerova základního korelačního útoku („split and open“), který je založen na konceptu Hammingovy vzdálenosti mezi dvěma binárními sekvencemi stejné délky. Použitelné pro kombinované generátory.

Pro odhalení vlivu j-tého lineárního posuvného registru (s výstupní sekvencí {x (j) } na šifru gama {g} je část generátoru modelována jako binární symetrický kanál (BSC). Algoritmus útoku se skládá ze dvou fází (někdy nazývaných fáze ):

výpočet korelační pravděpodobnosti na základě kombinační funkce a druhého stupně. $p_{j}=P(g={x^{(j)))$ $F$
výčet prvotních náplní rejstříku. V této fázi se přítomnost korelace daného fragmentu gama s odpovídajícím fragmentem z určuje výpočtem funkce vzájemné korelace a porovnáním této hodnoty s určitým číslem . $G$ ${\displaystyle x_{d}^{(j)))$ $C_{x^{j},{g}}(d)={\frac {1}{n}}\cdot \sum _{i=1}^{n}(-1)^{g_ {i}}\cdot (-1)^{x_{i+d}^{(j)}}$ $T$

Pokud je srovnání úspěšné, fáze se nazývá true a dojde k přechodu na další registr . V opačném případě se fáze nazývá neplatná a přejděte na . Výstupní hodnoty tohoto algoritmu jsou stavy , které přispívají informacemi do gama. $j+1$ $d=d+1,d=1,2,\tečky ,2^{L_{j))$ ${x_{0}^{j))$

Nyní něco málo o výběru prahové hodnoty a počtu gama bitů nezbytných pro úspěšnou kryptoanalýzu : $T$ $n$ $P_{f}=P(C_{x^{j},{g}}(d)\geq T|WrongPhase)$ $P_{m}=P(C_{x^{j},{g}}(d)<T|RightPhase)$

Vybrali jsme například , kde je délka registru. A pak z těchto podmínek najdeme a . $P_{m}=0,01,P_{f}=2^{-L}$ $L$ $T$ $n$

Útoky založené na kontrole parity s nízkou váhou

Příkladem této podtřídy útoků je Mayerův a Staffelbachův rychlý korelační útok. Je použitelný jak pro generátory filtrů, tak pro kombinované generátory a je základem pro všechny ostatní rychlé korelační útoky tohoto typu. Myšlenka útoku je založena na použití rovnic kontroly parity pro lineární polynom zpětné vazby registru.

Rychlé korelační útoky

Rychlé korelační útoky jsou chápány jako útoky, jejichž výpočetní náročnost je mnohem menší než výpočetní náročnost silových útoků.
Tento typ útoku redukuje problém dekódování v binárním symetrickém kanálu na problém kryptoanalýzy a je modelován jako dekódování náhodného lineárního kódu. Podobně jako základní korelační útoky tato podtřída používá pojem Hammingova vzdálenost . $(N,l)$

Kompromis mezi časem a pamětí

Účelem tohoto útoku je obnovit počáteční stav posuvného registru (nalezení klíče) pomocí známého schématu zařízení a fragmentu šifrovací sekvence. Složitost útoku závisí na velikosti šifry a délce zachyceného gama.

Skládá se ze dvou fází:

vytvoření velkého slovníku, ve kterém jsou zaznamenány všechny možné dvojice stav-výstup;
hádání počátečního naplnění posuvného registru, generování výstupu, prohlížení zachycené výstupní sekvence a hledání shody s vygenerovaným výstupem. Pokud existuje shoda, pak je tato odhadovaná náplň s vysokou pravděpodobností počáteční.

Příklady této třídy útoků jsou útok Steve Babbage a útok Biryukov-Shamir.

"Předpokládej a urči"

Útok je založen na předpokladu, že kryptoanalytik zná gama, zpětnovazební polynom, počet posunů registru mezi výstupy obvodu a funkci filtrování. Skládá se ze tří fází:

předpoklad o zaplnění některých buněk registru;
stanovení plného naplnění registru na základě předpokladu znalostí kryptanalytika;
generování výstupní sekvence; pokud se shoduje s gama, pak byl předpoklad v první fázi správný; pokud se neshoduje, vraťte se ke kroku 1.

Složitost algoritmu závisí na zařízení generátoru a na počtu předpokladů.

Poznámky

↑ Zdroj . Datum přístupu: 16. ledna 2016. Archivováno z originálu 15. února 2017. (neurčitý)
↑ Zdroj . Získáno 16. ledna 2016. Archivováno z originálu 14. února 2017. (neurčitý)
↑ Schneier B. Kapitola 16. Generátory pseudonáhodných sekvencí a proudové šifry // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .

Literatura

Ryabko B. Ya., Fionov AN Kryptografické metody ochrany informací. - Moskva. - Nakladatelství Goryach. Line-Telecom, 2005. - ISBN 5-93517-265-8 .

Bruce Schneier . Aplikovaná kryptografie, druhé vydání: Protokoly, algoritmy a zdrojový kód v C (látka). — John Wiley & Sons, Inc. - Nakladatelství zahraniční literatury, 1996. - ISBN 0471128457 .

A. Menezes, P. van Oorschot, S. Vanstone. Příručka aplikované kryptografie. — CRC Press, Inc. — 1997.

Přednášky E. M. Gabidulina , Moskevský institut fyziky a technologie , 2009

Odkazy

Matt JB Robshaw. Stream Ciphers Technical Report TR-701 (anglicky) , verze 2.0, RSA Laboratories, 1995.
Streamové šifry. Výsledky zahraniční otevřené kryptologie. . Nejúplnější kompilace a překlad moderního (do roku 1997) zahraničního výzkumu v oblasti tvorby a kryptoanalýzy proudových šifer.
BC Anashin , A.Yu. Bogdanov, I.S. Kizhvetov. eSTREAM: rychlé a silné proudové šifry .
JA Reeds a NJA Sloane. Syntéza Shift-Register .
A.V. Jakovlev, A.A. Bezbogov, V.V. Rodin, V.N. Shamkin. Kryptografická ochrana informací .
Metody a prostředky ochrany počítačových informací . Tutorial.
Obecné schéma pravděpodobnostního proudového šifrovacího systému
eSTREAM: Dítě lochnesské příšery
A. A. Menyashev, V. A. Monarev, B. Ya Rjabko, A. N. Fionov. Statistický útok .
S. Dorošenko, A. Fionov, A. Lubkin, V. Monarev, B. Ryabko, Yu. I Shokin. Experimentální statistické útoky na blokové a proudové šifry (nedostupný odkaz) .
Yu, V. Stasev, A. V. Potii, Yu, A. Izbenko. Studium metod kryptoanalýzy pro proudové šifry .

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) blowfish Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsobem ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher