KASUMI

KASUMI

Розробники	SAGE
Уперше оприлюднений	1999 р.
Раундів	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\leq i\leq 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\leq 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 мережах.