Trivium (cifr)

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 31 decembrie 2018; verificările necesită 4 modificări .

Trivium este un algoritm simetric de criptare în flux sincron concentrat în primul rând pe implementarea hardware cu un echilibru flexibil între viteză și numărul de elemente, care are și posibilitatea unei implementări software destul de eficiente.

Cifrul a fost introdus în decembrie 2008 ca parte a portofoliului proiectului european eSTREAM , profilul 2 (cifre orientate pe hardware). Autorii cifrului sunt Christophe De Kannier și Bart Prenel.

Acest cifru de flux generează până la biți din fluxul de ieșire din 80 de biți ai cheii și 80 de biți ai IV (vector de inițializare). Acesta este cel mai simplu cifru al proiectului eSTREAM, care arată rezultate excelente în ceea ce privește stabilitatea criptografică. $2^{64}$

Trivium este inclus în standardul ISO/IEC 29192-3 ca un cifru de flux ușor.

Descriere

Starea inițială a Trivium este de 3 registre de deplasare cu o lungime totală de 288 de biți. Fiecare ciclu de ceas schimbă biții din registrele de deplasare prin intermediul unei combinații neliniare de feed-forward și feedback. Pentru a inițializa cifrul, cheia K și vectorul de inițializare IV sunt scrise în 2 din 3 registre și algoritmul este executat de 4x288 = 1152 ori, ceea ce garantează că fiecare bit al stării inițiale depinde de fiecare bit al cheii și de fiecare bit. a vectorului de inițializare.

După trecerea etapei de inițializare, în fiecare ciclu este generat un nou membru al fluxului de chei Z , care trece procedura XOR cu următorul membru al textului. Procedura de decriptare are loc în ordine inversă - fiecare membru al textului cifrat este XOR cu fiecare membru al fluxului de chei Z. [unu]

Algoritm

Cifre de flux

Trivium generează o secvență Z , așa-numita keystream, lungă de până la biți. Pentru a cripta un mesaj, este necesar să XOR mesajul și fluxul de chei. Decriptarea se realizează într-un mod similar, operația XOR este efectuată din textul cifrat și fluxul de chei. $N\leq 2^{64}$

Inițializare

Algoritmul este inițializat prin încărcarea unei chei de 80 de biți și a unui vector de inițializare de 80 de biți într-o stare inițială de 288 de biți. Inițializarea poate fi descrisă de următorul pseudocod .

(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{pentru}}\ i=1\ {\mbox{la}}\ 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{sfârșit pentru))

Procedura de inițializare asigură că fiecare bit al stării inițiale depinde de fiecare bit al cheii și de fiecare bit al vectorului de inițializare. Acest efect este atins deja după 2 treceri complete (execuții de ciclu 2*288). Încă 2 treceri sunt concepute pentru a complica relațiile de biți. De exemplu, primii 128 de octeți ai fluxului de chei Z , obținuți din cheia nulă și vectorul de inițializare, au aproximativ același număr de 1 și 0 distribuiti uniform. Chiar și cu cheile cele mai simple și identice, algoritmul Trivium produce o secvență de numere care sunt aproape aleatorii.

Primii 128 de octeți ai fluxului de chei, generați de la zerourile K și IV în hexazecimal 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 ca 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

După cum puteți vedea, după 4 cicluri de inițializare, unitățile scrise în celule și au afectat toți ceilalți biți ai stării inițiale și astfel, chiar și cu cele mai simple și identice chei, fiecare octet al mesajului va fi modificat ca urmare a criptării. algoritm. $s_{286}$ $s_{287}$ $s_{288}$

Operațiunea algoritmului

Generatorul de flux folosește 15 biți dintr-o stare inițială de 288 de biți pentru a schimba 3 biți ai stării și pentru a calcula 1 bit din fluxul de chei . Ca rezultat al algoritmului, se pot obține până la biți din fluxul de chei . Algoritmul poate fi descris prin următorul pseudocod. $z_{i}$ $N\leq 2^{64}$

{\mbox{pentru}}\ i=1\ {\mbox{la}}\ N\ {\mbox{do}}

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

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

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

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{sfârșit pentru))

În acest pseudocod, toate calculele sunt efectuate modulo 2. Adică, operațiile de adunare și înmulțire sunt operații XOR și AND .

Perioada

Perioada de flux cheie este dificil de determinat din cauza naturii neliniare a schimbărilor de stare inițială. Chiar dacă toți declanșatorii sunt AND, rezultând un circuit complet liniar, se poate demonstra că orice pereche de cheie și vector de inițializare va avea ca rezultat generarea unui flux de chei cu o perioadă de ordin (care depășește deja lungimea necesară a fluxului de chei). ). $2^{96-3}-1$ $2^{64}$

Dacă presupunem că Trivium începe să genereze un flux de chei aleatoriu după un număr mic de iterații, atunci toate secvențele generate până la lungime vor fi la fel de probabile. Precum și probabilitatea ca perechea cheie/vector de inițializare să genereze un flux de chei cu o perioadă mai mică de aproximativ [2] . $2^{288}$ $2^{80}$ $2^{-208}$

Cifrele familiei Trivium

Modificările acestui cifr diferă în ceea ce privește numărul de registre de deplasare și lungimea acestora.

Univium

Cifrul de flux Unvium constă dintr-un singur registru cu deplasare și pentru codificare este necesară doar o cheie care nu depășește lungimea registrului. [unu]

Bivium

Împreună cu Trivium, autorii săi au propus cifrul Bivium, care implementează doar 2 registre de deplasare cu o lungime totală de 177 de biți. Procesul de inițializare este similar cu Trivium. În fiecare ciclu, 2 biți de stare sunt modificați și este generat un nou bit al fluxului de chei. În funcție de generarea fluxului de cheie Z , există 2 versiuni: Bivium-A și Bivium-B (Bivium). În Bivium-A, este implementată o dependență directă a noului membru Z de bitul de stare schimbat , din diferența față de acesta în Bivium-B (Bivium) . [3] $z_{i}\leftarrow t_{1)$ $z_{i}\leftarrow t_{1}+t_{2}$

Trivium-toy și Bivium-toy

Versiunile de jucărie au fost obținute prin reducerea lungimii registrului, ceea ce a redus complexitatea de calcul a algoritmului, păstrând în același timp toate proprietățile matematice. Lungimea fiecărui registru a fost redusă de 3 ori, iar jucăria-Bivium era, de asemenea, compusă din doar două registre.

Fiecare modificare a cifrului Trivium a fost creată pentru a simplifica descrierea sa matematică, care are mai mult un scop educațional decât scopul utilizării lor în instrumentele de securitate a informațiilor. [patru]

Performanță

Implementarea hardware standard a algoritmului necesită 3488 de porți și produce 1 bit din fluxul de chei pe ciclu de ceas. Dar, deoarece fiecare stare nouă a unui bit nu se schimbă timp de cel puțin 64 de runde, atunci pot fi generate încă 64 de stări în paralel când numărul de elemente logice crește la 5504. De asemenea, sunt posibile variații de performanță diferite în funcție de numărul de elemente. folosit.

Interpretarea software a acestui algoritm este, de asemenea, destul de eficientă. Implementarea C a Trivium pe AthlonXP 1600+ oferă o criptare de peste 2,4 Mbps

Securitate

Spre deosebire de primele cifruri de flux, cum ar fi RC4 , algoritmul Trivium, pe lângă cheia privată ( K ), are și un vector de inițializare ( IV ), care este cheia publică. Utilizarea IV permite mai multe sesiuni independente de criptare/decriptare folosind doar 1 cheie și vectori de inițializare multipli (câte unul pentru fiecare sesiune). De asemenea, este posibil să folosiți mai mulți vectori de inițializare pentru aceeași sesiune, folosind un nou IV pentru fiecare mesaj nou.

În prezent, nu se cunosc metode de atac asupra acestui algoritm care ar fi mai eficiente decât enumerarea secvențială . Complexitatea acestui atac depinde de lungimea mesajului și este de ordinul . $2^{120}$

Există studii despre metodele de atac (de exemplu, atacul cubic [5] ), care sunt apropiate ca eficiență de enumerare. În plus, există o metodă de atac care vă permite să recuperați K din IV și keystream. Complexitatea acestui atac este egală și scade ușor odată cu creșterea numărului de vectori de inițializare utilizați cu o singură cheie. De asemenea, atacurile sunt posibile prin studiul secvenței pseudo-aleatoare a fluxului cheie pentru a găsi modele și a prezice biții ulterioare ai fluxului, dar aceste atacuri necesită soluția unor ecuații neliniare complexe. Cea mai mică complexitate rezultată a unui astfel de atac este [6] [7] $2^{135}$ $2^{164}$

Metode de cercetare

Aproape toate realizările de hacking ale Trivium sunt încercări de a folosi atacuri efectuate cu succes pe versiuni trunchiate ale algoritmului [1] . Adesea, ca cea studiată este folosită o versiune a algoritmului Bivium, care folosește doar 2 registre de deplasare cu o lungime totală de 192 de biți [1] .

Note

↑ 1 2 3 4 Copie arhivată . Consultat la 23 decembrie 2009. Arhivat din original la 25 septembrie 2018. (nedefinit)
↑ Copie arhivată . Consultat la 23 decembrie 2009. Arhivat din original la 20 octombrie 2016. (nedefinit)
↑ Două atacuri banale asupra Trivium | SpringerLink . Preluat la 27 iulie 2018. Arhivat din original la 27 iulie 2018. (nedefinit)
↑ Copie arhivată . Preluat la 10 martie 2017. Arhivat din original la 12 martie 2017. (nedefinit)
↑ Copie arhivată . Consultat la 23 decembrie 2009. Arhivat din original la 17 mai 2017. (nedefinit)
↑ Copie arhivată . Consultat la 23 decembrie 2009. Arhivat din original la 26 august 2016. (nedefinit)
↑ Copie arhivată . Consultat la 23 decembrie 2009. Arhivat din original la 30 iulie 2016. (nedefinit)

Link -uri

Trivium pe pagina proiectului eSTREAM Arhivat 23 septembrie 2015 la Wayback Machine
Descrierea algoritmului pe pagina proiectului eSTREAM Arhivat 20 septembrie 2015 la Wayback Machine
Principii de construcție a cifrurilor flux

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher