KASUMI

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é 27. ledna 2015; kontroly vyžadují 13 úprav .

KASUMI
Tvůrce	ETSI
Vytvořeno	1999
zveřejněno	1999
Velikost klíče	128 bit
Velikost bloku	64 bit
Počet kol	osm
Typ	Úprava sítě Feistel

KASUMI (z japonštiny 霞 (hiragana かすみ, romaji kasumi) - mlha, mlha) je bloková šifra používaná v celulárních sítích. V UMTS se používá v kryptografických funkcích f8 a f9 , v GSM se používá v algoritmu A5/3 a v GPRS se používá v algoritmu GEA/3 , poslední dva používají šifru KASUMI s délkou klíče 64 bitů.

KASUMI je vyvinut skupinou expertů SAGE (Security Algorithms Group of Experts), která je součástí Evropského institutu pro telekomunikační standardy ( ETSI ) [1] . Stávající algoritmus MISTY1 byl vzat jako základ a optimalizován pro použití v mobilní komunikaci.

Jak kryptanalytici ukázali v roce 2010, v procesu změn byla spolehlivost algoritmu MISTY1 snížena: KASUMI má zranitelnosti pro některé typy útoků, zatímco MISTY1 je vůči nim odolný. [2]

Popis

KASUMI používá 64bitovou velikost bloku a 128bitový klíč v 8kolovém schématu Feistel. Každé kolo používá 128bitový zaokrouhlovací klíč sestávající z osmi 16bitových podklíčů získaných z původního klíče pomocí pevné procedury generování podklíče.

Schéma šifrování

Základní algoritmus

KASUMI se rozkládá na sadu funkcí (FL, FO, FI), které se používají spolu s jejich přidruženými klávesami (KL, KO, KI)

Vstupní datový blok I je rozdělen na dvě stejné části:

I=L_{0}||R_{0}

Pak pro každý : $1\leq i\leq 8$

R_{i}=L_{i-1}

L_{i}=R_{i-1}\oplus f_{i}(L_{i-1},RK_{i})

kde je kruhová funkce. - kulatý 128bitový klíč $f_{i}$ ${\displaystyle RK_{i))$

RK_{i}=KL_{i}||KO_{i}||KI_{i}

U východu $(L_{8}||R_{8})$

Kulatá funkce

Vypočteno takto:

Pro kola 1,3,5,7:

f_{i}(I,RK_{i})=FO(FL(I,KL_{i}),KO_{i},KI_{i})

Pro kola 2,4,6,8:

f_{i}(I,RK_{i})=FL(FO(I,KO_{i},KI_{i}),KL_{i})

Funkce FL

Vstupem funkce je 32bitový datový blok I a 32bitový klíč KL i , který je rozdělen na dva 16bitové podklíče:

KL_{i}=KL_{i,1}||KL_{i,2}

Vstupní řetězec I je rozdělen na dvě části po 16 bitech:

I=L||R

Pojďme definovat:

R'=R\oplus ROL(L\cap KL_{i,1})

L'=L\oplus ROL(R'\vee KL_{i,2})

Kde je cyklický posun doleva o 1 bit. $ROL(x)$

U východu . $(L'||R')$

Funkce FO

Funkčním vstupem je 32bitový datový blok a dva klíče po 48 bitech: . $KO_{i},KI_{i}$

Vstupní řetězec I je rozdělen na dvě části po 16 bitech: . $I=L_{0}||R_{0}$

48bitové klíče jsou rozděleny do tří částí:

KO_{i}=KO_{i,1}||KO_{i,2}||KO_{i,3}

a .

KI_{i}=KI_{i,1}||KI_{i,2}||KI_{i,3}

Potom definujeme: $1\leq j\leq 3$

{\displaystyle R_{j}=FI(L_{j-1}\oplus KO_{i,j},KI_{i,j})\oplus R_{j-1))

L_{j}=R_{j-1}

U východu . $(L_{3}||R_{3})$

Funkce FI

Funkčním vstupem je 16bitový datový blok I a 16bitový klíč KIi ,j .

Vstup I je rozdělen na dvě nestejné složky: 9bitovou levou stranu L 0 a 7bitovou pravou stranu R 0 :

I=L_{0}||R_{0}

Podobně je klíč KI i, j rozdělen na 7bitovou složku KI i, j,1 a 9bitovou složku KI i, j,2 :

KI_{i,j}=KI_{i,j,1}||KI_{i,j,2}

Funkce využívá dva S-boxy: S7, který mapuje 7bitový vstup na 7bitový výstup, a S9, který mapuje 9bitový vstup na 9bitový výstup.

Existují také dvě další funkce:

ZE(x)

Převede 7bitovou hodnotu x na 9bitovou hodnotu přidáním dvou nul k nejvýznamnějším bitům.

TR(x)

Převede 9bitovou hodnotu x na 7bitovou hodnotu odstraněním dvou nejvýznamnějších bitů z ní.

Funkce je implementována následující sadou operací:

L_{1}=R_{0}~~~~~~~~~~~~~~~~~~~~~~~~R_{1}=S9[L_{0}]\ plus ZE(R_{0})

L_{2}=R_{1}\oplus KI_{i,j,2}~~~~~~~~~~~~~R_{2}=S7[L_{1}]\oplus TR (R_{1})\oplus KI_{i,j,1}

L_{3}=R_{2}~~~~~~~~~~~~~~~~~~~~~~~~R_{3}=S9[L_{2}]\ plus ZE(R_{2})

{\displaystyle L_{4}=S7[L_{3}]\oplus TR(R_{3})~~~~~~R_{4}=R_{3))

Funkce vrací hodnotu . $(L_{4}||R_{4})$

S-bloky

S-boxy převádějí 7 nebo 9bitový vstupní blok na 7 nebo 9bitový výstupní blok pomocí vyhledávacích tabulek

Například: S7[30] = 124

Desetinná substituční tabulka pro blok S7:

S7[0-15]	54	padesáti	62	56	22	34	94	96	38	6	63	93	2	osmnáct	123	33
S7[16-31]	55	113	39	114	21	67	65	12	47	73	46	27	25	111	124	81
S7[32-47]	53	9	121	79	52	60	58	48	101	127	40	120	104	70	71	43
S7[48-63]	dvacet	122	72	61	23	109	13	100	77	jeden	16	7	82	deset	105	98
S7[64-79]	117	116	76	jedenáct	89	106	0	125	118	99	86	69	třicet	57	126	87
S7[80-95]	112	51	17	5	95	čtrnáct	90	84	91	osm	35	103	32	97	28	66
S7[96-111]	102	31	26	45	75	čtyři	85	92	37	74	80	49	68	29	115	44
S7[112-127]	64	107	108	24	110	83	36	78	42	19	patnáct	41	88	119	59	3

Desetinná substituční tabulka pro blok S9:

S9[0-15]	167	239	161	379	391	334	9	338	38	226	48	358	452	385	90	397
S9[16-31]	183	253	147	331	415	340	51	362	306	500	262	82	216	159	356	177
S9[32-47]	175	241	489	37	206	17	0	333	44	254	378	58	143	220	81	400
S9[48-63]	95	3	315	245	54	235	218	405	472	264	172	494	371	290	399	76
S9[64-79]	165	197	395	121	257	480	423	212	240	28	462	176	406	507	288	223
S9[80-95]	501	407	249	265	89	186	221	428	164	74	440	196	458	421	350	163
S9[96-111]	232	158	134	354	13	250	491	142	191	69	193	425	152	227	366	135
S9[112-127]	344	300	276	242	437	320	113	278	jedenáct	243	87	317	36	93	496	27
S9[128-143]	487	446	482	41	68	156	457	131	326	403	339	dvacet	39	115	442	124
S9[144-159]	475	384	508	53	112	170	479	151	126	169	73	268	279	321	168	364
S9[160-175]	363	292	46	499	393	327	324	24	456	267	157	460	488	426	309	229
S9[176-191]	439	506	208	271	349	401	434	236	16	209	359	52	56	120	199	277
S9[192-207]	465	416	252	287	246	6	83	305	420	345	153	502	65	61	244	282
S9[208-223]	173	222	418	67	386	368	261	101	476	291	195	430	49	79	166	330
S9[224-239]	280	383	373	128	382	408	155	495	367	388	274	107	459	417	62	454
S9[240-255]	132	225	203	316	234	čtrnáct	301	91	503	286	424	211	347	307	140	374
S9[256-271]	35	103	125	427	19	214	453	146	498	314	444	230	256	329	198	285
S9[272-287]	padesáti	116	78	410	deset	205	510	171	231	45	139	467	29	86	505	32
S9[288-303]	72	26	342	150	313	490	431	238	411	325	149	473	40	119	174	355
S9[304-319]	185	233	389	71	448	273	372	55	110	178	322	12	469	392	369	190
S9[320-335]	jeden	109	375	137	181	88	75	308	260	484	98	272	370	275	412	111
S9[336-351]	336	318	čtyři	504	492	259	304	77	337	435	21	357	303	332	483	osmnáct
S9[352-367]	47	85	25	497	474	289	100	269	296	478	270	106	31	104	433	84
S9[368-383]	414	486	394	96	99	154	511	148	413	361	409	255	162	215	302	201
S9[384-399]	266	351	343	144	441	365	108	298	251	34	182	509	138	210	335	133
S9[400-415]	311	352	328	141	396	346	123	319	450	281	429	228	443	481	92	404
S9[416-431]	485	422	248	297	23	213	130	466	22	217	283	70	294	360	419	127
S9[432-447]	312	377	7	468	194	2	117	295	463	258	224	447	247	187	80	398
S9[448-463]	284	353	105	390	299	471	470	184	57	200	348	63	204	188	33	451
S9[464-479]	97	třicet	310	219	94	160	129	493	64	179	263	102	189	207	114	402
S9[480-495]	438	477	387	122	192	42	381	5	145	118	180	449	293	323	136	380
S9[496-511]	43	66	60	455	341	445	202	432	osm	237	patnáct	376	436	464	59	461

Získání kulatých klíčů

Každé kolo získává KASUMI klíče z veřejného klíče K takto:

128bitový klíč K je dělen 8:

{\displaystyle K=K_{1}||K_{2}||K_{3}||\dots ||K_{8))

Druhé pole Kj se vypočítá :

{\displaystyle K_{j'}=K_{j}\oplus C_{j))

kde C j jsou určeny podle tabulky:

C1	0x0123
C2	0x4567
C3	0x89AB
C4	0xCDEF
C5	0xFEDC
C6	0xBA98
C7	0x7654
C8	0x3210

Klíče pro každé kolo se vypočítávají podle následující tabulky:

Klíč	jeden	2	3	čtyři	5	6	7	osm
$KL_{i,1}$	K1<<1	K2<<1	K3<<1	K4<<1	K5<<1	K6<<1	K7<<1	K8<<1
$KL_{i,2}$	K3'	K4'	K5'	K6'	K7'	K8'	K1'	K2'
$KO_{i,1}$	K2<<5	K3<<5	K4<<5	K5<<5	K6<<5	K7<<5	K8<<5	K1<<5
$KO_{i,2}$	K6<<8	K7<<8	K8<<8	K1<<8	K2<<8	K3<<8	K4<<8	K5<<8
$KO_{i,3}$	K7<<<13	K8<<13	K1<<<13	K2<<13	K3 <<<13	K4<<13	K5<<13	K6<<<13
$KI_{i,1}$	K5'	K6'	K7'	K8'	K1'	K2'	K3'	K4'
$KI_{i,2}$	K4'	K5'	K6'	K7'	K8'	K1'	K2'	K3'
$KI_{i,3}$	K8'	K1'	K2'	K3'	K4'	K5'	K6'	K7'

kde X<<<n je cyklický levý posun o n bitů.

Kryptoanalýza

V roce 2001 byl zaveden nemožný diferenciální útok. Autor - Ulrich Köhn (2001). [3]

V roce 2003 Elad Barkan, Eli Biham a Nathan Keller předvedli útok typu man-in-the-middle na GSM protokol, který obchází šifru A5/3 a porušuje tak protokol. Tento přístup však přímo neprolomí šifru A5/3. [4] Plná verze byla zveřejněna později v roce 2006. [5]

V roce 2005 Eli Biham, Orr Dunkelman a Nathan Keller publikovali bumerangový útok na KASUMI, který prolomil šifru rychleji než hrubá síla . [3] Útok vyžaduje vybrané otevřené texty, každý zašifrovaný jedním ze 4 přidružených klíčů, a má časovou složitost ekvivalentní šifrám KASUMI. Tento útok ukazuje nezabezpečenost šifrování KASUMI v sítích 3G. $2^{54,6}$ $2^{76,1}$

V lednu 2010 Orr Dunkelman, Nathan Keller a Adi Shamir publikovali článek ukazující zranitelnost Kasumi vůči útoku souvisejícím klíčem . Útočník může obnovit kompletní klíč A5/3 pomocí malého množství výpočetních zdrojů (autoři je odhadují na 2 26 v datech, 2 30 v paměti a 2 32 v čase a dokázali to implementovat za 2 hodiny moderního osobního počítač). Autoři také poznamenali, že útok nemusí být použitelný na způsob, jakým se KASUMI používá v sítích 3G. Útok, který vyvinuli, se také nevztahuje na původní MISTY a zpochybňují tvrzení 3GPP, že bezpečnost algoritmu nebyla při vytvoření KASUMI ohrožena. [2]

Poznámky

↑ (eng) Univerzální mobilní telekomunikační systém (UMTS); Specifikace algoritmů důvěrnosti a integrity 3GPP; Dokument 2: Specifikace Kasumi . ETSI (2007). Archivováno z originálu 11. dubna 2012. (neurčitý)
↑ 1 2
* Orr Dunkelman, Nathan Keller, Adi Shamir. Praktický útok na kryptosystém A5/3 používaný v GSM telefonii třetí generace // International Association for Cryptologic Research Archiv Eprint: journal. - 2010. - 10. ledna. Archivováno z originálu 3. února 2013.
- Praktický klíčový útok na kryptosystém KASUMI používaný v GSM a 3G telefonii // CRYPTO 2010, Poznámky k přednáškám z informatiky, svazek 6223, 2010, str. 393-410 doi:10.1007/94238-173- 21
↑ 1 2 Eli Biham , Orr Dunkelman, Nathan Keller. Obdélníkový útok souvisejícího klíče na celé KASUMI . ASIACRYPT 2005.pp. 443–461. Archivováno z originálu (ps) dne 2013-10-11 . Získáno 27. 11. 2009 . Archivováno 11. října 2013 na Wayback Machine
↑ Elad Barkan, Eli Biham , Nathan Keller. Okamžitá kryptoanalýza pouze šifrované komunikace GSM (PDF) . CRYPTO 2003.pp. 600–616. Archivováno z originálu (PDF) dne 2005-12-16. Použitý zastaralý parametr |deadlink=( help );Parametry |deadurl=a |deadlink=duplikovat se navzájem ( help ); Nesprávná hodnota |dead-url=404( help ) Archivováno 16. prosince 2005 na Wayback Machine
↑ Elad Barkan, Eli Biham , Nathan Keller. Okamžitá kryptoanalýza šifrované komunikace GSM pouze pomocí šifrovaného textu od Barkan a Biham of Technion (plná verze) . Archivováno z originálu 11. dubna 2012. (neurčitý)

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