Trivium (š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é 31. prosince 2018; kontroly vyžadují 4 úpravy .

Trivium je symetrický synchronní streamovací šifrovací algoritmus primárně zaměřený na hardwarovou implementaci s flexibilní rovnováhou mezi rychlostí a počtem prvků, který má také možnost poměrně efektivní softwarové implementace.

Šifra byla představena v prosinci 2008 jako součást portfolia evropského projektu eSTREAM , profil 2 (hardwarově orientované šifry). Autory šifry jsou Christophe De Kannier a Bart Prenel.

Tato proudová šifra generuje až bitů výstupního proudu z 80 bitů klíče a 80 bitů IV (inicializační vektor). Jedná se o nejjednodušší šifru projektu eSTREAM, která vykazuje vynikající výsledky z hlediska kryptografické stability. $2^{64}$

Trivium je součástí normy ISO/IEC 29192-3 jako odlehčená proudová šifra.

Popis

Počáteční stav Trivium jsou 3 posuvné registry o celkové délce 288 bitů. Každý cyklus hodin mění bity v posuvných registrech pomocí nelineární kombinace dopředné a zpětné vazby. Pro inicializaci šifry se klíč K a inicializační vektor IV zapíší do 2 ze 3 registrů a algoritmus se provede 4x288 = 1152 krát, což zaručuje, že každý bit počátečního stavu závisí na každém bitu klíče a každém bitu. inicializačního vektoru.

Po absolvování inicializační fáze se v každém cyklu vygeneruje nový člen toku klíčů Z , který projde procedurou XOR s dalším členem textu. Procedura dešifrování probíhá v obráceném pořadí - každý člen šifrovaného textu je XORed s každým členem toku klíčů Z . [jeden]

Algoritmus

Proudové šifry

Trivium generuje Z sekvenci , tzv. keystream, až bitů dlouhou. Pro zašifrování zprávy je nutné XOR zprávu a tok klíčů. Dešifrování se provádí podobným způsobem, operace XOR se provádí ze šifrového textu a toku klíčů. $N\leq 2^{64}$

Inicializace

Algoritmus se inicializuje načtením 80bitového klíče a 80bitového inicializačního vektoru do 288bitového počátečního stavu. Inicializace může být popsána následujícím pseudokódem .

(s_{1},s_{2},...,s_{93})\leftarrow (K_{1},...,K_{80},0,...,0)

(s_{94},s_{95},...,s_{177})\leftarrow (IV_{1},...,IV_{80},0,...,0)

(s_{178},s_{179},...,s_{288})\leftarrow (0,...0,1,1,1)

{\mbox{for}}\ i=1\ {\mbox{to}}\ 4\cdot 288\ {\mbox{do}}

{\displaystyle t_{1}\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171))

{\displaystyle t_{2}\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264))

{\displaystyle t_{3}\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69))

(s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})

(s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})

(s_{178},s_{179},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})

{\mbox{end for))

Inicializační procedura zajišťuje, že každý bit počátečního stavu závisí na každém bitu klíče a každém bitu inicializačního vektoru. Tohoto efektu je dosaženo již po 2 úplných průchodech (2*288 provedení cyklů). Další 2 průchody jsou navrženy tak, aby zkomplikovaly bitové vztahy. Například prvních 128 bajtů toku klíčů Z , získaných z nulového klíče a inicializačního vektoru, má přibližně stejný počet rovnoměrně rozložených 1s a 0s. I s nejjednoduššími a identickými klíči vytváří algoritmus Trivium sekvenci čísla, která se blíží náhodě.

Prvních 128 bajtů toku klíčů, generovaných z nul K a IV v šestnáctkové soustavě 0000000 e0 fb 26 bf 59 58 1b 05 7a 51 4e 2e 9f 23 7f c9 0000010 32 56 16 03 07 19 2d cf a8 e7 0f 79 b2 a1 cd e9 0000020 52 f7 03 92 68 02 38 b7 4c 2b 75 1a a2 9a 9a 59 0000030 55 28 98 49 74 6e 59 80 80 03 4c 1a a5 b5 f2 d4 0000040 34 69 bb 86 cca 52 15 b3 ae 80 12 69 73 55 9a 31 0000050 b2 6c 0e f5 16 40 20 d6 30 7f 4e 3f 48 16 dc 24 0000060 25 5c ad c4 10 a1 c9 1b bb e8 01 4e dc fc 2e 27 0000070 9e fa ae 02 a2 48 05 b2 2e fb f4 4f 27 76 56 27 0000080 3e 5e b7 06 4e e6 4a 57 7b ad a2 3a 1c 52 ff 48 0000090 f3 92 f8 87 ff 98 aa 87 e6 bf f6 19 38 3c ff 19 00000a0 3f 0a a5 fd 01 ec d0 d8 fa f0 fa 87 09 a1 4e ee 00000b0 63 29 9f 9b 31 ef 95 a5 c7 76 19 8d c7 e0 df 55 00000c0 1b 0f 50 e9 b8 91 85 ea 06 7b d5 2a ad 2b 77 f4 00000d0 ac 84 9b 6d 3f 2e a9 85 99 d7 04 95 02 33 fd f0 00000e0 b7 f8 5b 6e b7 c8 f0 b4 46 aa 20 cd a0 dd dd 4f

Jak vidíte, po 4 inicializačních cyklech se jednotky zapsaly do buněk a ovlivnily všechny ostatní bity počátečního stavu, takže i s nejjednoduššími a identickými klíči bude každý bajt zprávy změněn v důsledku šifrování. algoritmus. $s_{286}$ $s_{287}$ $s_{288}$

Operace algoritmu

Generátor proudu používá 15 bitů z 288bitového počátečního stavu ke změně 3 bitů stavu a k výpočtu 1 bitu toku klíčů . V důsledku algoritmu lze získat až bitů toku klíčů . Algoritmus lze popsat následujícím pseudokódem. $z_{i}$ $N\leq 2^{64}$

{\mbox{for}}\ i=1\ {\mbox{to}}\ N\ {\mbox{do}}

{\displaystyle t_{1}\leftarrow s_{66}+s_{93))

{\displaystyle t_{2}\leftarrow s_{162}+s_{177))

t_{3}\leftarrow s_{243}+s_{288}

{\displaystyle z_{i}\leftarrow t_{1}+t_{2}+t_{3))

{\displaystyle t_{1}\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171))

{\displaystyle t_{2}\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264))

{\displaystyle t_{3}\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69))

(s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})

(s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})

(s_{178},s_{179},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})

{\mbox{end for))

V tomto pseudokódu jsou všechny výpočty prováděny modulo 2. To znamená, že operace sčítání a násobení jsou operace XOR a AND .

Období

Klíčové období toku je obtížné určit kvůli nelineární povaze změn počátečního stavu. I když jsou všechny spouštěče spojeny AND, což má za následek zcela lineární obvod, lze ukázat, že jakýkoli pár klíče a inicializačního vektoru povede ke generování toku klíčů s periodou pořadí (která již překračuje požadovanou délku toku klíčů ). $2^{96-3}-1$ $2^{64}$

Pokud předpokládáme, že Trivium začne generovat náhodný klíčový proud po malém počtu iterací, pak všechny vygenerované sekvence až do délky budou stejně pravděpodobné. Stejně jako pravděpodobnost, že pár klíč/inicializační vektor vygeneruje klíčový proud s periodou menší než přibližně [2] . $2^{288}$ $2^{80}$ $2^{-208}$

Šifry rodiny Trivium

Modifikace této šifry se liší počtem posuvných registrů a jejich délkou.

Univium

Proudová šifra Univium se skládá z jediného posuvného registru a pro kódování je potřeba pouze klíč, který není delší než délka registru. [jeden]

Bivium

Spolu s Triviem jeho autoři navrhli šifru Bivium, která implementuje pouze 2 posuvné registry o celkové délce 177 bitů. Proces inicializace je podobný jako u Trivium. Každý cyklus se změní 2 stavové bity a vygeneruje se nový bit toku klíčů. Podle generace klíčového proudu Z existují 2 verze: Bivium-A a Bivium-B (Bivium). V Bivium-A je implementována přímá závislost nového členu Z na změněném stavovém bitu z rozdílu od něj v Bivium-B (Bivium) . [3] ${\displaystyle z_{i}\leftarrow t_{1))$ $z_{i}\leftarrow t_{1}+t_{2}$

Trivium-toy a Bivium-toy

Verze hraček byly získány snížením délek registrů, což snížilo výpočetní složitost algoritmu při zachování všech matematických vlastností. Délka každého rejstříku se zkrátila 3krát a Bivium-toy se také skládala pouze ze dvou rejstříků.

Každá modifikace šifry Trivium byla vytvořena za účelem zjednodušení jejího matematického popisu, který má spíše vzdělávací účel než účel použití v nástrojích bezpečnosti informací. [čtyři]

Výkon

Standardní hardwarová implementace algoritmu vyžaduje 3488 hradel a produkuje 1 bit keystreamu na takt. Ale protože se každý nový stav bitu nezmění po dobu alespoň 64 kol, lze paralelně vygenerovat dalších 64 stavů, když se počet logických prvků zvýší na 5504. V závislosti na počtu prvků jsou také možné různé variace výkonu. použitý.

Softwarová interpretace tohoto algoritmu je také poměrně účinná. Implementace Trivium C na AthlonXP 1600+ poskytuje více než 2,4 Mbps šifrování

Zabezpečení

Na rozdíl od raných proudových šifer, jako je RC4 , má algoritmus Trivium kromě soukromého klíče ( K ) také inicializační vektor ( IV ), což je veřejný klíč. Použití IV umožňuje více nezávislých šifrovacích/dešifrovacích relací pomocí pouze 1 klíče a více inicializačních vektorů (jeden pro každou relaci). Je také možné použít více inicializačních vektorů pro stejnou relaci s použitím nového IV pro každou novou zprávu.

V tuto chvíli nejsou známy žádné metody útoku na tento algoritmus, které by byly efektivnější než sekvenční výčet . Složitost tohoto útoku závisí na délce zprávy a je v řádu . $2^{120}$

Existují studie metod útoku (například kubický útok [5] ), které se účinností blíží výčtu. Kromě toho existuje metoda útoku, která vám umožní obnovit K z IV a keystream. Složitost tohoto útoku je stejná a mírně klesá s nárůstem počtu inicializačních vektorů použitých s jednou klávesou. Útoky jsou také možné při studiu pseudonáhodné sekvence toku klíčů za účelem nalezení vzorů a predikce následných bitů toku, ale tyto útoky vyžadují řešení složitých nelineárních rovnic. Nejmenší výsledná složitost takového útoku je [6] [7] $2^{135}$ $2^{164}$

Metody výzkumu

Téměř všechny hackerské úspěchy Trivium jsou pokusy o použití úspěšně provedených útoků na zkrácené verze algoritmu [1] . Často se jako studovaná verze používá verze algoritmu Bivium, která využívá pouze 2 posuvné registry o celkové délce 192 bitů [1] .

Poznámky

↑ 1 2 3 4 Archivovaná kopie . Získáno 23. prosince 2009. Archivováno z originálu dne 25. září 2018. (neurčitý)
↑ Archivovaná kopie . Získáno 23. prosince 2009. Archivováno z originálu dne 20. října 2016. (neurčitý)
↑ Dva triviální útoky na Trivium | SpringerLink . Získáno 27. července 2018. Archivováno z originálu dne 27. července 2018. (neurčitý)
↑ Archivovaná kopie . Získáno 10. března 2017. Archivováno z originálu 12. března 2017. (neurčitý)
↑ Archivovaná kopie . Získáno 23. prosince 2009. Archivováno z originálu 17. května 2017. (neurčitý)
↑ Archivovaná kopie . Získáno 23. prosince 2009. Archivováno z originálu dne 26. srpna 2016. (neurčitý)
↑ Archivovaná kopie . Získáno 23. prosince 2009. Archivováno z originálu dne 30. července 2016. (neurčitý)

Odkazy

Trivium na stránce projektu eSTREAM Archivováno 23. září 2015 na Wayback Machine
Popis algoritmu na stránce projektu eSTREAM Archivováno 20. září 2015 na Wayback Machine
Principy konstrukce proudových šifer

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) nafukovací ryba 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ůsob 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