KASUMI

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},R{K}_i)$

де $f_i$ - раундова функція. $R{K}_i$ - раундовий 128-бітний ключ

$R{K}_i=K{L}_i||K{O}_i||K{I}_i$

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

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

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

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

$F_i(I,R{K}_i)=FO(FL(I,K{L}_i),K{O}_i,K{I}_i)$

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

$F_i(I,R{K}_i)=FL(FO(I,K{O}_i,K{I}_i),K{L}_i)$

Функція FL

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

$K{L}_i=K{L}_{i,1}||K{L}_{i,2}$.

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

$I=L||R$.

Визначимо:

$R^{\prime }=R\oplus ROL(L\cap K{L}_{i,1})$

$L^{\prime }=L\oplus ROL(R^{\prime }\vee K{L}_{i,2})$

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

На виході $(L^{\prime }||R^{\prime })$.

Функція FO

На вхід функції подається 32-бітний блок даних і два ключі по 48 біт: $K{O}_i,K{I}_i$.

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

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

$K{O}_i=K{O}_{i,1}||K{O}_{i,2}||K{O}_{i,3}$ і $K{I}_i=K{I}_{i,1}||K{I}_{i,2}||K{I}_{i,3}$.

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

$R_j=FI(L_{j-1}\oplus K{O}_{i,j},K{I}_{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} :

$K{I}_{i,j}=K{I}_{i,j,1}||K{I}_{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 K{I}_{i,j,2}{R}_2=S7[L_1]\oplus TR(R_1)\oplus K{I}_{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^{\prime }}=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
$K{L}_{i,1}$	K1<<<1	K2<<<1	K3<<<1	K4<<<1	K5<<<1	K6<<<1	K7<<<1	K8<<<1
$K{L}_{i,2}$	K3'	K4'	K5'	K6'	K7'	K8'	K1'	K2'
$K{O}_{i,1}$	K2<<<5	K3<<<5	K4<<<5	K5<<<5	K6<<<5	K7<<<5	K8<<<5	K1<<<5
$K{O}_{i,2}$	K6<<<8	K7<<<8	K8<<<8	K1<<<8	K2<<<8	K3<<<8	K4<<<8	K5<<<8
$K{O}_{i,3}$	K7<<<13	K8<<<13	K1<<<13	K2<<<13	K3<<<13	K4<<<13	K5<<<13	K6<<<13
$K{I}_{i,1}$	K5'	K6'	K7'	K8'	K1'	K2'	K3'	K4'
$K{I}_{i,2}$	K4'	K5'	K6'	K7'	K8'	K1'	K2'	K3'
$K{I}_{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 мережах.