MUGI

MUGI
zveřejněno	února 2002
Velikost klíče	128 bit
Počet kol	32
Typ	Streamová šifra

MUGI je generátor pseudonáhodných čísel , který byl navržen pro použití jako proudová šifra . Projektem CRYPTREC jej doporučila japonská vláda [1] [2] .

Jak to funguje

Vstupními parametry MUGI jsou 128bitový tajný klíč a 128bitový inicializační vektor. Po přijetí klíče a inicializačního vektoru MUGI generuje 64bitové bloky na základě vnitřního stavu, který se po každém bloku mění. Velikost vnitřního stavu MUGI je 128 bitů. Skládá se ze tří 64bitových stavových registrů ("stavové" registry) a 16 64bitových registrů ("buffer" registrů). [3] MUGI používá nelineární S-boxy původně vzniklé ve standardu Advanced Encryption Standard (AES).

Definice

Vývojáři definovali rodinu šifer podobných Panamě jako Panama-like keystream generator (PKSG) . Uvažujme stavový automat se dvěma vnitřními stavy a, vyrovnávací pamětí b a jejich aktualizačními funkcemi a . Šifra je považována za kód patřící do rodiny PKSG, pokud: $\rho$ $\lambda$

$\rho$ zahrnuje transformaci SPN a jako parametr používá b části vyrovnávací paměti. $a^{(t+1)}=\rho (a^{(t)},b^{(t)})$

$\lambda$ je lineární transformace a používá části a jako parametr $b^{(t+1)}=\lambda (b^{(t)},a^{(t)})$

f vytiskne část stavu (obvykle ne více než 1/2)

Hlavní stav činnosti tohoto pseudonáhodného generátoru se skládá z množiny , kde S je vnitřní stav, F je jeho aktualizační funkce a f je filtr, který izoluje výstupní sekvenci od vnitřního stavu S. V podstatě množina ( S, F) je konečný automat vnitřních stavů šifry. V případě panamské šifry je vnitřní stav rozdělen na dvě části, stav a a vyrovnávací paměť b. Funkce aktualizace je také rozdělena na 2 části. Výstupní filtr f vybere přibližně polovinu stavových bitů a v každém kole. $(S,F,f)$

MUGI je PRNG se 128bitovým tajným klíčem K (tajný parametr) a 128bitovým inicializačním vektorem I (veřejný parametr). Minimální množství dat, které může šifra slova zpracovat, je 64 bitů.

V tomto algoritmu pracují funkce zpracování v konečném Galoisově poli GF(2^8) nad polynomem 0x11b.

Algoritmus

Vstup: Tajný klíč K, inicializační vektor I, počet výstupních slov n (každé 64 bitů) Výstup: Posloupnost náhodných čísel Out[i] (0<=i<n) Inicializace Krok 1: Umístěte tajný klíč K do stavu a. Poté inicializujte vyrovnávací paměť b pomocí funkce Krok 2: Přidejte inicializační vektor I do stavu a a aktualizujte stav a pomocí funkce Krok 3: Spusťte aktualizaci vnitřního stavu spuštěním funkce aktualizace MUGI před dokončením spuštění inicializace Náhodné generování čísel Krok 4: Spusťte N cyklů aktualizace vnitřní stav funkce a výstupní části každé kolo.

\rho

\rho

Výše zmíněná funkce aktualizace je kombinací funkcí a následujících: $\rho$ $\lambda$ $(a^{(t+1)},b^{(t+1)})Aktualizovat(a^{(t)},b^{(t)}=(\rho (a^{( t)},b^{(t)}),(\lambda (a^{(t)},b^{(t)})))$

Funkce F je složením sčítání (z bufferu), S-box nelineární transformace, lineární transformace pomocí MDS matice M a byte shuffling. Transformace S a matice M lze jednoduše implementovat vyhledáváním v tabulce.

Transformace S je bitová substituce - S-box v MUGI je stejný jako v AES šifře. To znamená, že náhrada S-boxu je složením inverze x -> x^-1 v GF(2^8) a afinní transformace.

Aktualizační funkce : $\rho$ ${\displaystyle a_{0}^{(t+1)}=a_{1}^{(t)))$

$a_{1}^{(t+1)}=a_{2}^{(t)}\bigoplus F(a_{1}^{(t)},b_{4}^{(t) })\bigoplus C_{1}$

$a_{2}^{(t+1)}=a_{2}^{(t)}\bigoplus F(a_{0}^{(t)},b_{1}^{(t) }0<<<17)\bigoplus C_{2}$

Algoritmus MUGI používá tři konstanty: C0 pro inicializaci a C1, C2 ve funkci ρ. Mají následující hodnoty:

C0=0x6A09E667F3BCC908

C1 = 0xBB67AE8584CAA73B

C2=0x3C6EF372FE94F82B

Jedná se o hexadecimální hodnoty √2, √3 a √5 vynásobené 264.

Vývoj

Šifra byla navržena tak, aby byla snadno implementovatelná v softwaru i hardwaru. Vývojáři vzali za základ panamskou šifru , kterou lze použít jako hashovací funkci a proudovou šifru.

Vývojáři panamské šifry nepoužili posuvné registry s lineární zpětnou vazbou (LFSR). Místo toho použili principy návrhu proudové šifry na návrh blokové šifry.

Výhody

Šifra MUGI byla navržena tak, aby byla snadno implementovatelná v softwaru i hardwaru. Ve srovnání s šiframi RC4 , E0 , A5 MUGI vykazují lepší výsledky v hardwarové implementaci na FPGA . Maximální rychlost kódování dosahuje 7 Gbps pro frekvenci čipu 110 MHz. [čtyři]

Aplikace

MUGI lze jednoduše použít jako proudovou šifru. K tomu je nutné rozdělit otevřený text do bloků po 64 bitech. Poté XOR každý z těchto bloků pomocí výstupních bloků šifry MUGI v každém kole pomocí tajného klíče a inicializačního vektoru.

Zabezpečení

Úplný výčet klíčů pro tento algoritmus trvá v průměru kroků. $2^{127}$

Bezpečnost PRNG je určena závislostí mezi vstupními a výstupními bitovými toky (nebo závislostí mezi výstupními bity sekvence). Všechny útoky na PRNG, které mohou poskytnout útočníkovi informace v méně než počtu kroků potřebných k vyčerpávajícímu výčtu klíčů nebo vnitřních stavů generátoru, využívají tyto závislosti. Výstupní bitová sekvence PRNG tedy musí být nepředvídatelná. Lze tedy rozlišit 3 třídy zranitelností PRNG:

Porušení náhodnosti . Útočník opraví tajný klíč a inicializační vektor a zpozoruje narušení náhodnosti ve výstupní sekvenci.
Znovu synchronizovat . Útočník opraví tajný klíč a sleduje korelaci mezi inicializačními vektory a výstupními sekvencemi.
Klíčové útoky . Útočník opraví inicializační vektor a sleduje korelaci mezi tajnými klíči a výstupními sekvencemi.

Lineárně aktualizovaná složka (buffer) MUGI byla teoreticky analyzována [5] a bylo zjištěno, že vnitřní odezva bufferu, bez zpětné vazby na nelineárně aktualizované komponenty, sestává z binárních lineárních rekurentních sekvencí s velmi malou periodou 48, které se mohou stát zdrojem zranitelnosti. Je ukázáno, jak lze tuto slabinu v principu využít k obnovení tajného klíče a nalezení lineárních statistických vztahů.

Byla také provedena předběžná analýza nelineární složky MUGI [6] , kde byly nalezeny možné zranitelnosti. Přestože v celkové struktuře šifry nebyly nalezeny žádné významné zranitelnosti, bylo zjištěno, že její jednotlivé části jsou velmi citlivé na malé změny. Zejména je možné obnovit celý 1216bitový stav šifry a 128bitový tajný klíč pomocí pouze 56 slov z kanálu ve 2 14 krocích analýzy této informace. Pokud je z této analýzy vyloučena lineární část MUGI, lze tajný 192bitový stav obnovit pomocí pouhých 3 slov z kanálu ve 232 krocích analýzy.

Od roku 2011 však nejsou známy žádné útoky, které by byly rychlejší než útoky hrubou silou na klíčový prostor nebo vnitřní stavy algoritmu MUGI jako celku .

Odkazy

Domovská stránka MUGI

Poznámky

↑ Oficiální stránky CRYPTREC (anglicky) (nepřístupný odkaz) . Získáno 10. listopadu 2011. Archivováno z originálu 3. září 2012.
↑ Dai Watanabe, Soichi Furuya, Kazuo Takaragi, Bart Preneel , (únor 2002). „Nový generátor klíčového proudu MUGI“ ( PDF ) . 9. mezinárodní seminář o rychlém softwarovém šifrování (FSE 2002) . Leuven : Springer-Verlag . str. 179-194 . Získáno 2007-08-07 . (nedostupný odkaz)
↑ Hitachi Ltd. Specifikace generátoru pseudonáhodných čísel MUGI Ver. 1.2 (anglicky) (nedostupný odkaz) (1. prosince 2001). Získáno 10. listopadu 2011. Archivováno z originálu 3. září 2012.
↑ Paris Kitsos a Athanassios N. Skodras. O hardwarové implementaci generátoru pseudonáhodných čísel MUGI (anglicky) (downlink) . Hellenic Open University (21. března 2007). Získáno 10. listopadu 2011. Archivováno z originálu 3. září 2012.
↑ Jovan DJ. Golic (únor 2004). „Slabost lineární části proudové šifry MUGI“. 11. mezinárodní seminář o rychlém softwarovém šifrování (FSE 2004) . Dillí : Springer-Verlag. str. 178-192.
↑ Alex Biryukov, Adi Shamir (únor 2005). „Analýza nelineární části Mugi“ . 12. mezinárodní seminář o rychlém softwarovém šifrování (FSE 2005) . Paříž : Springer-Verlag. str. 320-329. Archivováno z originálu ( PostScript ) dne 2006-05-15 . Získáno 2007-08-07 . Použitý zastaralý parametr |deadlink=( help );Parametry |deadurl=a |deadlink=vzájemně se duplikují ( nápověda )

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