KASUMI

Алгоритм блочного шифрування
Назва:	KASUMI
Розробник:	SAGE
Створений:	1999 р.
Опублікований:	1999 р.
Розмір ключа:	128 біт
Розмір блоку:	64 біт
Число раундів:	8
Тип:	модифікована мережа Фейстеля

KASUMI (з японської 霞 (хірагана かすみ, romaji kasumi), що означає "туман") - блочний шифр, що використовується в мережах стільникового зв'язку 3GPP. Також позначається A5/3 при використанні в GSM і GEA3 в GPRS.

KASUMI розроблений групою SAGE (Security Algorithms Group of Experts), яка є частиною Європейського Інституту по Стандартизації в області Телекомунікацій (ETSI). За основу був узятий існуючий алгоритм MISTY1 і оптимізований для використання в стільниковому зв'язку.

Опис

KASUMI використовує 64-бітний розмір блоку і 128-бітний ключ у 8-раундовій схемі Фейстеля. У кожному раунді використовується 128-бітний раундовий ключ, що складається з восьми 16-бітових підключів, отриманих з вихідного ключа фіксованою процедурою генерації підключів.

Схема шифрування

Основний алгоритм

KASUMI розкладається в набір функцій (FL, FO, FI), які використовуються разом з пов'язаними з ними ключами (KL, KO, KI)

Вхідний блок даних I поділяється на дві рівні частини:

$~ I = L_0 | | R_0$

Потім для кожного $~ 1 \le i \le 8$:

$~ R_ {i} = L_ {i-1}$

$~ L_i = R_ {i-1} \oplus f_i (L_ {i-1}, RK_i)$

де $~ f_i$ - раундова функція. $~ RK_i$ - раундовий 128-бітний ключ

$~ RK_i = KL_i | | KO_i | | KI_i$

На виході $~ (L_8 | | R_8)$

Функція раунду

Обчислюється таким чином:

Для раундів 1,3,5,7:

$~ F_i (I, RK_i) = FO (FL (I, KL_i), KO_i, KI_i)$

Для раундів 2,4,6,8:

$~ F_i (I, RK_i) = FL (FO (I, KO_i, KI_i), KL_i)$

Функція FL

На вхід функції подається 32-бітний блок даних I і 32-бітний ключ 'KL _i ', який поділяється на два 16-бітових підключа:

$~ KL_i = KL_ {i, 1} | | KL_ {i, 2}$.

Вхідна рядок I поділяється на дві частини по 16 біт:

$~ I = L | | R$.

Визначимо:

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

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

Де $~ ROL (x)$ - циклічний зсув вліво на 1 біт.

На виході $~ (L '| | R')$.

Функція FO

На вхід функції подається 32-бітний блок даних і два ключі по 48 біт: $~ KO_i, KI_i$.

Вхідний рядок I розділяється на дві частини по 16 біт: $~ I = L_0 | | R_0$.

48-бітові ключі поділяються на три частини кожен:

$~ KO_i = KO_ {i, 1} || KO_ {i, 2} || KO_ {i, 3}$ і $~ KI_i = KI_ {i, 1} | | KI_ { i, 2} || KI_ {i, 3}$.

Потім для $~ 1 <j \le 3$ визначимо:

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

$~ L_j = R_ {j-1}$

На виході $~ (L_3 | | R_3)$.

Функція FI

На вхід функції подається 16-бітний блок даних 'I і 16-бітний ключ 'KI _{i, j} .

Вхід I поділяється на дві нерівні складові: 9-бітну ліву частину L ₀ і 7-бітну праву R ₀ :

$~ I = L_0 | | R_0$.

Точно так же ключ KI _{i, j,} поділяється на 7-бітну компоненту KI _{i, j, 1} і 9 - бітну компоненту KI _{i, j, 2} :

$~ KI_ {i, j} = KI_ {i, j, 1} | | KI_ {i, j, 2}$.

Функція використовує два S-блоку: S7 який відображає 7-бітний вхід в 7-бітний вихід, і S9 який відображає 9-бітний вхід в 9-бітний вихід.

Також використовуються ще дві функції:

$~ ZE (x)$ Перетворює 7-бітове значення x в 9-бітове значення додаванням двох нулів в старші біти.

$~ TR (x)$ Перетворює 9-бітове значення x в 7-бітове викреслюванням з нього двох старших бітів.

Функція реалізується наступним набором операцій:

$~ L_1 = R_0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ R_1 = S9 [L_0] \oplus 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] \oplus ZE (R_2)$

$~ L_4 = S7 [L_3] \oplus TR (R_3) ~ ~ ~ ~ ~ ~ R_4 = R_3$

Функція повертає значення $~ (L_4 | | R_4)$.

Отримання раундових ключів

Кожен раунд KASUMI отримує ключі із загального ключа K наступним чином:

• 128-бітний ключ K поділяється на 8:

$~ K = K_1 || K_2 || K_3 || \dots | | K_8$

• Обчислюється другий масив 'K _j ':

$~ K_ {j '} = K_j \oplus C_j$

де 'C _j ' визначаються за таблицею:

C1	0x0123
С2	0x4567
С3	0x89AB
С4	0xCDEF
С5	0xFEDC
С6	0xBA98
С7	0x7654
С8	0x3210

• Ключі для кожного раунду обчислюються за наступною таблицею:

Ключ	1	2	3	4	5	6	7	8
$~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'

де X <<< n - циклічний зсув на n біт вліво.

Криптоаналіз

У 2001 році була представлена атака методом неможливих диференціалів. Автор - Ульріх Кен (2001).

У 2003 році Елад Баркан, Елі Біхамом і Натан Келлер продемонстрували атаку з посередником на протокол GSM, що дозволяє обійти шифр A5/3 і таким чином зламати протокол. Однак, цей підхід не зламує шифр A5/3 безпосередньо. Повна версія була опублікована пізніше, в 2006.

У 2005 році Елі Біхамом, Орр Дункельман і Натан Келлер опублікували атаку на KASUMI методом бумеранга, яка зламує шифр швидше, ніж повний перебір. Для атаки потрібно $2 ^ {54.6}$ обраних відкритих текстів, кожен з яких був зашифрований одним з 4 пов'язаних ключів, і має складність за часом, еквівалентну $2 ^ {76.1}$ шифрування KASUMI. Ця атака показує небезпечність шифрування KASUMI в 3G мережах.