ŽRALOK

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é 5. listopadu 2019; kontroly vyžadují 3 úpravy .

ŽRALOK
Tvůrce	Vincent Rayman , Joan Dymen , Bart Presnel , Antun Bossalers a Eric de Veen
Vytvořeno	1996 _
zveřejněno	1996 _
Velikost klíče	128 bit
Velikost bloku	64 bit
Počet kol	6 [1] (8 [2] )
Typ	Substitučně-permutační síť

SHARK ( anglicky Secure Hash Algorithm Regenerative Keys – bezpečný hashovací algoritmus s obnovenými klíči) je symetrický blokový šifrovací algoritmus vyvinutý skupinou kryptografů, včetně Vincenta Raymana , autora šifry AES . Teoreticky umožňuje použití bloků a klíčů různých délek, nicméně autorská implementace používá 128bitový klíč a 64bitové bloky. Struktura je podobná struktuře permutační sítě .

Historie SHARK

Šifra SHARK je první ze série algoritmů vyvinutých jako součást studie k vytvoření bezpečných a účinných blokových šifer založených na strategii návrhu Wide Trail [3] . Výsledkem výzkumu bylo později vytvoření standardní šifry AES [2] .

Autoři umístili SHARK jako algoritmus navržený tak, aby nahradil tehdy rozšířenou šifru DES . Novému algoritmu byly předloženy následující požadavky:

vysoký výkon - malý počet nábojů. Pro srovnání, šifra DES používala 16 kol. Podle autora se jim podařilo dosáhnout více než čtyřnásobného zrychlení ve srovnání se šiframi SAFER a IDEA ;
nezranitelnost vůči lineární a diferenciální kryptoanalýze, vůči níž byl DES zranitelný [1] .

Přestože šifry založené na SP-net ( MMB, SAFER , 3-Way ) již existovaly dříve , SHARK byl první, kdo pro lineární transformaci použil kódy MDS [4] , konkrétně kódy Reed-Solomon [1] .

Existují dvě verze šifry SHARK : SHARK-A ( angl. affine transform ) a SHARK-E ( ang. exor ), pojmenované podle různých způsobů zavádění kulatých klíčů [5] .

Návrh algoritmu

Algoritmus SHARK se skládá ze tří částí:

nelineární vrstva - založená na S-boxech ;
difúzní vrstva - na základě kódů MDS [4] ;
klíčový plán pro odvození kruhových klíčů ze zdrojového klíče [1] .

Každá součást algoritmu je uvažována samostatně a každá musí mít určité vlastnosti. Difúzní vrstva by tedy měla mít jednotné a dobré difúzní vlastnosti. Nelineární vrstva musí mít také jednotné nelineární vlastnosti a komponenty algoritmu jsou nezávislé v následujícím smyslu: pokud se změní implementace např. nelineární vrstvy (některé S-boxy jsou nahrazeny jinými S-boxy se stejnými vlastnostmi), bezpečnost algoritmu zůstává nezměněna. Taková strategie je variantou strategie Wide trail [3] popsané v doktorské práci Joan Dymen [1] .

SHARK se skládá z nábojů, další vrstvy pro přidání klíče a další vrstvy obrácené difúze. Každé kolo zase sestává z přidání klíče, nelineární náhrady a difúzní vrstvy. Je potřeba další vrstva přidání klíče, aby se zabránilo útočníkovi oddělit poslední kolo. Pro zjednodušení dešifrovací operace je zapotřebí další vrstva obrácené difúze [1] . $R$

Nelineární substituční vrstva se skládá z S-boxů, z nichž každý je -bitová permutace. Algoritmus je tedy schopen zašifrovat bloky délky [1] . $n$ $m$ $m\cdot n$

Difúzní vrstva

Difúzní vrstva přijímá -bitová čísla, která lze považovat za prvky nad polem . Dotyčná vrstva je nezbytná pro vytvoření lavinového efektu . Tento efekt se projevuje v lineárních a rozdílových kontextech: $n$ $m$ $GF(2^{m})$

Lineární kontext - Neexistuje žádná korelace mezi lineární kombinací malé sady -bitových vstupů a lineární kombinací malé sady ( -bitových) výstupů. $m$ $m$
Rozdílový kontext - malá změna vstupních dat s sebou nese výraznou změnu výstupních dat a naopak pro malou změnu výstupních dat je potřeba výrazně změnit vstupní data [1] .

Nechť je vratná lineární transformace , je prvek pole , je Hammingova vzdálenost , pak se kvantitativně lavinový efekt odhaduje podle čísla skoku ( angl. číslo větve ) [1] . $\theta$ $A$ $GF(2^{m})$ $w_{h}(a)$ $B(\theta )={\overset {}{\underset {a\neq 0}{min}}}({\displaystyle w_{h}(a)}+{\displaystyle w_{h}(\ theta(a))})$

Pokud , tak . se nazývá optimální číslo skoku ( ang. optimální číslo větve ). V hlavním článku autoři ukázali, že pomocí MDS kódů je možné sestrojit reverzibilní lineární transformaci s optimálním počtem skoků. Implementace využívá Reed-Solomonovy kódy [1] . $w_{h}(a)=1$ $B\leq n+1$ $B=n+1$ $(2n,n,n+1)$

Nelineární vrstva (substituční bloky)

Nelineární S-boxy poskytují ochranu proti lineární a diferenciální kryptoanalýze. Jednou z důležitých číselných charakteristik bezpečnosti šifry je matice exkluzivních zobrazení OR ( anglicky exor table ) , jejíž prvky jsou určeny vzorcem , kde - označuje počet prvků splňujících podmínku, - prvky oboru . Velké hodnoty maticových prvků mohou vést k náchylnosti šifry k diferenciálnímu útoku [1] . $E$ $\gamma$ $E_{ij}=\ostrý (x|\gamma (x)\oplus \gamma (i\oplus x)=j)$ $\ostrý$ $x,i,j$ $GF(2^{m})$

Autoři zvolili S-boxy na základě mapování nad polem . V tomto případě, když je sudý, má matice následující vlastnosti: ${\displaystyle F(x)=x^{-1))$ $GF(2^{m})$ $m$ $E$

Diferenciální 4-stabilita - všechny prvky matice nepřesahují 4. Ve skutečnosti je v každém řádku takové matice přesně jeden prvek roven 4 a zbytek je roven 2 nebo 0.
Minimální vzdálenost afinní funkce je . $2^{m/2}$
Nelineární pořadí libovolné lineární kombinace výstupních bitů je [1] . $m+1$

Pro odstranění pevných bodů a je použita invertibilní afinní transformace výstupních bitů [1] . $0\rightarrow 0$ $1\rightarrow 1$

Klíčový plán

Plánování klíčů vám umožňuje rozšířit původní klíč získáním kulatých klíčů . Dobré plánování vám umožní získat kulaté klíče s maximální entropií. Autoři navrhují dva způsoby, jak zadat kulatý klíč: $K$ $R+1$ $K_{i}$

Exor je jednoduchý XOR se vstupy v každém kole. Odpovídající algoritmus je SHARK-E.
Afinní transformace je afinní transformace vstupních dat, která závisí na klíči. Odpovídající algoritmus je SHARK-A [1] .

Exor

Vypočítá se jednoduchý XOR vstupních bitů kola a podklíče. Výhody metody jsou rychlost a stabilita: žádný klíč není silnější nebo slabší než jiný. Nevýhodou metody je, že entropie kulatého klíče nepřesahuje [1] . $m\cdot n$ $m\cdot n$ $m\cdot n$

Afinní transformace

Nechť je nesingulární matice nad polem , v závislosti na klíči (přesněji na jeho rozšíření). Uveďme klíčovou operaci se vstupními daty takto: . Jedná se o lineární operaci, takže nezavádí slabé klávesy. Navíc se entropie kulatých kláves zvýší na . Tato operace je však z hlediska výkonu poměrně nákladná, takže autoři navrhují omezit podprostor diagonálních matic . V tomto případě se entropie kulatých klíčů blíží [1] . $k_i$ $n\krát n$ $GF(2^{m})$ $K$ ${\displaystyle Y(X)=k_{i}\cdot X\oplus K_{i))$ $O(mn^{2})$ $k_i$ $2 min$

Generování podklíče

V algoritmu SHARK jsou kulaté klíče generovány následovně:

$R+1$ round - bit klíče jsou inicializovány prvními položkami v substituční tabulce . $m\cdot n$ $K_{i}$ $R+1$
Matice jsou inicializovány pomocí matic identity . $k_i$
Uživatelem vybraný klíč je zřetězen sám se sebou, dokud není bit dlouhý. $2(R+1)mn$
Algoritmus SHARK je aplikován na sekvenci získanou v kroku 3 v režimu CFB .
První bity výstupu se používají k vytvoření kulatých klíčů . $(R+1)mn$ $K_{i}$
Poslední bity výstupních dat jsou interpretovány jako prvky pole a tvoří diagonální prvky matic . Je-li některý prvek roven nule, je vyřazen a všechny následující prvky jsou posunuty o jedničku dolů. Další zašifrované nulové řetězce jsou přidány na konec, aby se vyplnily zbývající diagonální prvky [1] . $(R+1)mn$ $(R+1)n$ $GF(2^{m})$ $k_i$

Mechanismus generování podklíče v zásadě umožňuje použití klíče bitové délky, autoři však doporučují použít klíč nepřesahující 128 bitů [1] . $2(R+1)mn$

Poznámky k implementaci

Náhradní tabulky

Pro dosažení vysokého výkonu jsou difúzní vrstva a substituční bloky kombinovány v jedné operaci [1] . Nechť označí vstupní data kola; - výstup; — permutační matice (S-boxy); je matrice definující difúzní vrstvu; a - označují sčítání a násobení přes pole . Pak $X_{1},...,X_{n}$ ${\displaystyle Y_{1},...,Y_{n))$ $S_{1},...,S_{n}$ $A$ $\oplus$ $\cdot$ $GF(2^n)$

${\begin{pmatrix}Y_{1}\\...\\Y_{n}\end{pmatrix}}=A\cdot {\begin{pmatrix}S_{1}[X_{1}] \\...\\S_{n}[X_{n}]\end{pmatrix}}={\begin{pmatrix}a_{11}\\...\\a_{n1}\end{pmatrix} }\cdot S_{1}[X_{1}]\oplus ...\oplus {\begin{pmatrix}a_{1n}\\...\\a_{nn}\end{pmatrix}}\cdot S_ {n}[X_{n}]={\begin{pmatrix}a_{11}\cdot S_{1}[X_{1}]\\...\\a_{n1}\cdot S_{1}[ X_{1}]\end{pmatrix}}\oplus ...\oplus {\begin{pmatrix}a_{1n}\cdot S_{n}[X_{n}]\\...\\a_{nn }\cdot S_{n}[X_{n}]\end{pmatrix}}$

Pomocí rozšířených substitučních tabulek dimenze , určených vzorcem , můžeme zapsat transformaci v jednoduchém tvaru: $T_{i}$ $m\times mn$ $T_{i}[X]={\begin{pmatrix}a_{1i}\cdot S_{i}[X_{i}]\\...\\a_{ni}\cdot S_{i} [X_{i}]\end{pmatrix}}$ ${\begin{pmatrix}Y_{1}\\...\\Y_{n}\end{pmatrix}}=T_{1}[X_{1}]\oplus T_{2}[X_{ 2}]\oplus ...\oplus T_{n}[X_{n}]$

Jedno kolo tedy vyžaduje vyhledávání v tabulce a binární operace. Avšak vzhledem k tomu, že bity tabulky zabírají bajt délky bloku, algoritmus pro bloky o délce 128 bitů nebo více se ukázal být neefektivní pro většinu procesorů té doby (1996), proto existující omezení na délka bloku 64 bitů ( ) [2] . $n$ $n-1$ $8n$ $n^{2}\times 256$ $n=8,m=8$

Matice kódů MDS

Pro , lze sestavit matici, která definuje difúzní vrstvu na základě Reed-Solomonova kódu [2] . $n=8$

$A={\begin{pmatrix}CE&E7&B9&D0&52&87&74&0B\\95&FE&DA&9D&A9&28&51&31\\57&05&4D&26&07&3A&15&7F\\82&D2&D1&2C&6C&5A&CF&86\\8A&52&9E&5D&B9&F4&09&BE\\19&C1&17&9F&8F&33&A4&05\\B0&88&83&6D&70&0B&62&83\\01&F1&86&75&17&6C&09&34\end{pmatrix}}$

Dešifrování

Pro popis dešifrování zvažte 2kolovou verzi SHARK [1] . Dovolit být lineární operace, být nelineární náhrada a být operace sčítání klíče pro kulatou klávesu . Šifrovací funkce je v tomto případě rovna , kde je operace kombinovaná z difúzní vrstvy a S-boxů. Protože operace přidání klíče a operace difúze jsou lineární operace, jejich pořadí může být obráceno [1] : $l$ $s$ $a_{k_{i))$ $k_i$ $Y=(l^{-1}\circ a_{k_{3}}\circ l\circ s\circ a_{k_{2}}\circ \underbrace {l\circ s} _{r} \circ a_{k_{1}})(X)$ $r$

$(l\circ a_{k})(X)=A\cdot (k\cdot X\oplus K)=(A\cdot k\cdot X)\oplus (A\cdot K)=((A \cdot k\cdot A^{-1})\cdot (A\cdot X))\oplus (A\cdot K)=(a_{k'}\circ l)(X)$ ,

kde je zápis $a_{k'}(X)=k'\cdot X\oplus K'=(A\cdot k\cdot A^{-1})\cdot X\oplus (A\cdot K)$

Výsledný vzorec aplikujeme na [1] : $l^{-1}\circ a_{k_{3))$

$Y=(a_{k_{3}'}\circ l^{-1}\circ l\circ s\circ a_{k_{2}}\circ r\circ a_{k_{1}}) (X)=(a_{k_{3}'}\circ s\circ a_{k_{2}}\circ r\circ a_{k_{1}})(X)$

Ukažme nyní, že operace dešifrování má stejnou strukturu. Chcete-li to provést, nejprve změňte operaci šifrování [1] :

$X=(a_{k_{1}^{-1}}\circ s^{-1}\circ l^{-1}\circ a_{k_{2}^{-1}}\circ s^{-1}\circ l^{-1}\circ a_{k_{3}^{-1}}\circ l)(Y)$

Prohozením operace přidání klíče a operace difúze získáme stejnou strukturu jako v operaci šifrování [1] :

$X=(a_{k_{1}^{-1}}\circ s^{-1}\circ a_{k_{2}^{-1'}}\circ \underbrace {l^{- 1}\circ s^{-1}} _{r'}\circ a_{k_{3}^{-1'}})(Y)$

Pozoruhodné útoky

V současné době nebyly nalezeny žádné zranitelnosti klasické implementace algoritmu. Existují útoky pouze na varianty algoritmu:

V roce 1997 Thomas Jacobsen a Lars Knudsen ukázali, že 64bitová implementace SHARK-E ( SHARK se strategií vkládání klíče exor round) je teoreticky zranitelná vůči interpolačnímu útoku , když je omezena na 5 kol, stejně jako 128 -bitová implementace − omezena na 8 kol. Ale také ukázaly, že pro dostatečné zabezpečení je potřeba alespoň 6 nábojů [6] .
V roce 2013 Yang Shi a Hongfei Fan ukázali , že implementace White-Box [ 7] SHARK není dostatečně bezpečná a lze ji prolomit s pracovním faktorem přibližně 1,5*(2^47) [8] .

Poznámky

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Vincent Raymen , Joan Dymen , Bart Presnel , Antun Bossalers, Eric de Vin. The Cipher SHARK : PDF .
↑ 1 2 3 4 Vincent Raymen , Joan Dymen . Návrh Rijndaela : PDF . - S. 161-165 .
↑ 1 2 Joan Dymen . Strategie návrhu šifrovacích a hashovacích funkcí založené na lineární a diferenciální kryptoanalýze : PDF . Archivováno z originálu 16. května 2018.
↑ 1 2 MDS kódy - kódy s největší kódovou vzdáleností
↑ Naskenujte záznam pro Shark . Získáno 16. prosince 2017. Archivováno z originálu 28. ledna 2012. (neurčitý)
↑ Thomas Jacobsen , Lars Knudsen . Interpolační útok na blokové šifry . Springer International Publishing AG (17. května 2006). Získáno 9. února 2018. Archivováno z originálu 14. prosince 2017. (neurčitý)
↑ White-box attack kontext – útočník má plný přístup k softwarové implementaci šifry.
↑ Yang Shi, fanoušek Hongfei. O bezpečnosti implementace White-Box programu SHARK . Získáno 14. prosince 2017. Archivováno z originálu 14. prosince 2017. (neurčitý)

Literatura

Vincent Rijmen, Joan Daemen, Bart Preneel, Antoon Bosselaers, Erik De Win The Cipher SHARK. — Šifra SHARK Archived 14. prosince 2017 na Wayback Machine .
Joan Daemen, Vincent Rijmen Návrh Rijndaela. — The Design of Rijndael Archived 14. prosince 2017 na Wayback Machine .
Thomas Jakobsen, Lars R. Knudsen Interpolační útok na blokové šifry. — Interpolační útok na blokové šifry Archivováno 14. prosince 2017 na Wayback Machine .
Yang Shi, fanoušek Hongfei o bezpečnosti implementace SHARK v bílé krabici. — O bezpečnosti implementace SHARK pomocí White-Box Archivováno 14. prosince 2017 na Wayback Machine .
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Příručka aplikované kryptografie . - CRC Press, 1996. - S. 281. - 810 s. — ISBN 9781439821916 .

Odkazy

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