Drak (š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. ledna 2020; kontroly vyžadují 2 úpravy .

Dragon  je proudová šifra , poprvé představená [1] na výroční mezinárodní konferenci ICISC v roce 2003. V dubnu 2005 byl přihlášen do soutěže eSTREAM , jejímž cílem bylo identifikovat proudové šifry vhodné pro obecné použití v aplikacích s vysokými požadavky na výkon.

Dragon vyvinuli Ed Dawson, Kevin Chen, Matt Henricksen, William Millan, Leonie Simpson, HoonJae Lee a SangJae Moon.

Úvod

Návrh proudových šifer byl tradičně založen na provozu lineárních zpětnovazebních posuvných registrů , protože ty jsou dobře srozumitelné a splňují obecně přijímaná statistická kritéria. Nelinearita v gama šifře může být reprezentována buď působením nelineárního filtru, nebo nepravidelnými obvodovými hodinami, nebo obojím. Když jsou implementovány v hardwaru, bitstreamové šifry vykazují vysoký výkon, ale jsou poměrně pomalé, když jsou implementovány v softwaru . Šifry založené na posuvných registrech s lineární zpětnou vazbou a využívající malý počet zpětných vazeb mohou být náchylné k útokům, ale zvýšení počtu těchto zpětných vazeb může nepříznivě ovlivnit účinnost šifry. Při použití algebraických útoků je navíc zpochybňována spolehlivost šifer s funkcí lineární změny stavu. [2]

Šifry založené na slovech mohou překonat bitové šifry v hardwarových i softwarových implementacích. Šifrují několikanásobně více dat na iteraci než šifry pomocí jednobitových lineárních zpětnovazebních posuvných registrů. Pokud jsou implementovány v softwaru, dokážou překonat i rychlé blokové šifry , jako je AES, téměř o řád [3] . Ačkoli je snadné měřit výkon slovních šifer, je obtížné přesně posoudit jejich sílu.

Dragon byl navržen s ohledem na výkon i bezpečnost. Využívá nelineární zpětnovazební posuvný registr spolu s nelineárním filtrem pro generování šifry gama ve formě 64bitových slov. Dragon má výkon v řádu několika gigabitů za sekundu a vyžaduje asi 4 kilobajty paměti.

Specifikace

Dragon lze použít se 128bitovým klíčem a inicializačním vektorem nebo s 256bitovým klíčem a inicializačním vektorem. Tyto verze se nazývají Dragon-128 a Dragon-256. Fungují téměř identicky, s výjimkou procesu inicializace klíče.

Obě verze šifry Dragon jsou sestaveny pomocí jednoho 1024bitového nelineárního zpětnovazebního posuvného registru a 64bitové paměti M. Počáteční stav je vytvořen pomocí klíče a inicializačního vektoru, podporovaného funkcí změny stavu F. Změna funkce se také používá při generování klíčového proudu.

F-funkce

Dragon-128 a Dragon-256 používají stejnou funkci F. F je reverzibilní mapování ze 192 bitů na 192 bitů: jako vstup potřebuje 6 x 32 bitů (označeno a, b, c, d, e, f) a výstupy 6 x 32 bitů (označeno a', b', c', d', e', f'). Síť se skládá ze tří vrstev: počáteční směšovací vrstva, vrstva S-boxu a konečná směšovací vrstva. Míchací vrstvy využívají přídavek modulo 2 32 a přídavek modulo 2 (⊕). Vrstva S-boxu se skládá z G- a H-funkcí, které zase obsahují 8 × 32 S-boxů.

G- a H-funkce

Funkce G a H jsou nelineární virtuální 32 x 32 S-boxy postavené ze dvou 8 x 32bitových S-boxů. 32 vstupních bitů je rozděleno do čtyř bajtů, x = x 0 ‖ x 1 ‖ x 2 ‖ x 3 , kde a ‖ b značí zřetězení a a b.

Inicializace

Pro inicializaci klíče je nelineární zpětnovazební posuvný registr rozdělen do osmi 128bitových slov, označených W 0 ... W 7 . Inicializace probíhá ve dvou fázích.

Fáze 1: "Propagace" stavu šifry : Během první fáze je počáteční stav 1024bitového nelineárního zpětnovazebního posuvného registru a 64bitové paměti M "propagován" pomocí klíče (K) a inicializačního vektoru ( IV).

Dragon-128 vezme 128bitový klíč a 128bitový IV a „vynásobí“ stav nelineárního zpětnovazebního posuvného registru tak, aby (W 0 ‖ … ‖ W 7 ) = (K ‖ K ' ⊕ IV ' ‖ IV ‖ K ⊕ IV ' ‖ K ' ‖ K ⊕ IV ‖ IV ' ‖ K ' ⊕ IV), kde prvočíslo označuje, že horní a dolní 64bitová polovina byla prohozena.

Dragon-256 bere 256bitový klíč a 128bitový IV a „vynásobí“ stav nelineárního zpětnovazebního posuvného registru tak, že (W 0 ‖ … ‖ W 7 ) = (K ‖ K ⊕ IV ‖ ~( K ⊕ IV) ‖IV).

V obou případech je 64bitová paměť M předem vyplněna konstantní hodnotou 0x0000447261676F6E, což je ASCII reprezentace slova „Dragon“.

Fáze 2: Zamíchání stavu šifry : Během druhé fáze se funkce změny stavu použije 16krát, aby se prohodil obsah nelineárního zpětnovazebního posuvného registru a 64bitové paměti M. Argument 128bitové funkce F je vytvořené jako lineární kombinace tří slov posuvného registru s nelineární zpětnou vazbou, přesně a ‖ b ‖ c ‖ d = (W 0 ⊕ W 6 ⊕ W 7 ). Navíc e‖ f = M.

Obvod je taktován tak, že W 7 je přeskočeno v čase t, a tedy W i t+1 = W t i-1 , 0 ≤ i ≤ 7. 128bitové zpětnovazební slovo tvořící obsah W 0 t+1 je získané přidáním modulo 2 W 0 t 0 c (a ' ‖ b ' ‖ c ' ‖ d ' ). Zbývající dvě 32bitová slova jsou zřetězena a použita k aktualizaci paměti: e ' ‖ f ' = M.

Pro ochranu před útoky, které vyžadují znalost velkého počtu prvků klíčového toku, a před neznámými budoucími útoky nelze pro každý pár K a IV vytvořit více než 2 64 bitů toku klíčů.

Generování klíčového proudu

Během generování toku klíčů je 1024bitový nelineární zpětnovazební posuvný registr rozdělen na 32 32bitových slov Bi , 0 ≤ i ≤ 31. V procesu je také použita funkce F.

V každé iteraci jsou čtyři 32bitové vstupní argumenty F vybrány z nelineárního zpětnovazebního posuvného registru slov Bo , B9 , B16 a B19 . Zbývající dva argumenty jsou výsledkem modulo 2 sčítání slov B 30 a B 31 s ML a MR , v tomto pořadí, kde M L a MR jsou nízká a vysoká slova paměti M, v tomto pořadí.

Nelineární zpětnovazební posuvný registr je posunut o dva bity a Bo a B1 jsou vyplněny zpětnovazební akcí z výstupů b' a c' F- funkce v tomto pořadí . 64bitové slovo z klíčového toku je tvořeno zřetězením a ' a e ' . 64bitová paměť M funguje jako čítač během generování toku klíčů a každým cyklem se zvyšuje.

Implementace a výkon

Šifra Dragon byla navržena s ohledem na hardware i software.

Implementace softwaru

Byla provedena hodnocení výkonu [4] , která ukazují, že Dragon je poměrně efektivní jak z hlediska výkonu, tak nákladů na paměť.

Implementace hardwaru

Implementace Dragonu na hardwarové úrovni umožňuje dosáhnout vysokého stupně paralelismu. Operace se šesti vstupními argumenty F-funkce lze rozdělit do tří skupin, z nichž každá používá dva argumenty. Pre-mix a post-mix jsou implementovány pomocí 32bitových modulo sčítaček. Funkce G a H byly implementovány pomocí tabulek LUT a operátorů XOR. Při výrobě pomocí technologie Samsung 0,13um ASIC při taktovací frekvenci 2,6 GHz je minimální latence 2,774 ns při výkonu 23 Gbps.

Pro zvýšení rychlosti implementace hardwaru byla navržena speciální výpočetní struktura [5] . Na zařízení Altera FPGA dosahuje efektivní implementace Dragonu propustnost 1,06 Gbps.

Kryptoanalýza

V roce 2005 provedli Hakan Englund a Alexander Maximov studie spolehlivosti Dragonu [6] a odhalili v něm zranitelnost. V témže roce autoři šifry publikovali článek [7] popírající možnost efektivního využití této zranitelnosti. V roce 2007 však Joo Yeon Cho a Josef Pieprzyk zdokonalili dříve navrženou techniku ​​útoku [8] . A ačkoliv je takový útok v praxi prakticky neproveditelný, reputaci šifry to nezvýšilo.

Závěr

Po absolvování dvou fází soutěže eSTREAM se šifra Dragon nedostala do finále a prohrála se silnějšími konkurenty.

Viz také

Poznámky

  1. ↑ Chen, K., Millan, W., Fuller, J., Simpson, L., Dawson, E., Lee, H., Moon, S.:Dragon: A Fast Word Based Stream Cipher. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, sv. 3506, str. 33-50. Springer, Heidelberg (2005) ( [1] Archivováno 1. července 2012 na Wayback Machine )
  2. ↑ Courtois, N.: Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt. In: Lee, P., Lim, C. (eds.) ICISC 2002. LNCS, sv. 2587, str. 182-199. Springer, Heidelberg (2003)
  3. ↑ Národní institut pro standardy a technologie. Federal Information Processing Standards Publication 197 (2001)
  4. ↑ Projekt eSTREAM – eSTREAM Fáze 3 . Získáno 28. října 2011. Archivováno z originálu 31. října 2011.
  5. ↑ Lee, H., Moon, S.: Paralelní streamovací šifra pro bezpečné vysokorychlostní komunikace. Signal Processing 82(2), 137-143 (2002)
  6. ↑ Hakan Englund a Alexander „Útok na draka“ . Datum přístupu: 28. října 2011. Archivováno z originálu 27. května 2011.
  7. ↑ Ed Dawson, Matt Henricksen, Willam Millan a Leonie Simpson, „Drak je naživu a dobře“ [2] Archivováno 27. května 2011 na Wayback Machine
  8. ↑ Joo Yeon Cho a Josef Pieprzyk, „Vylepšený rozlišovací prostředek pro draka“ [3] Archivováno 27. září 2011 na Wayback Machine

Literatura

Odkazy