KASUMI

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

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

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

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

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

${\displaystyle ~I=L_{0}||R_{0}}$

Потім для кожного ${\displaystyle ~1\leq i\leq 8}$:

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

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

де ${\displaystyle ~f_{i}}$ - раундова функція. ${\displaystyle ~RK_{i}}$ - раундовий 128-бітний ключ

${\displaystyle ~RK_{i}=KL_{i}||KO_{i}||KI_{i}}$

На виході ${\displaystyle ~(L_{8}||R_{8})}$

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

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

${\displaystyle ~F_{i}(I,RK_{i})=FO(FL(I,KL_{i}),KO_{i},KI_{i})}$

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

${\displaystyle ~F_{i}(I,RK_{i})=FL(FO(I,KO_{i},KI_{i}),KL_{i})}$

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

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

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

${\displaystyle ~I=L||R}$.

Визначимо:

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

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

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

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

На вхід функції подається 32-бітний блок даних і два ключі по 48 біт: ${\displaystyle ~KO_{i},KI_{i}}$.

Вхідний рядок I розділяється на дві частини по 16 біт: ${\displaystyle ~I=L_{0}||R_{0}}$.

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

${\displaystyle ~KO_{i}=KO_{i,1}||KO_{i,2}||KO_{i,3}}$ і ${\displaystyle ~KI_{i}=KI_{i,1}||KI_{i,2}||KI_{i,3}}$.

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

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

${\displaystyle ~L_{j}=R_{j-1}}$

На виході ${\displaystyle ~(L_{3}||R_{3})}$.

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

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

${\displaystyle ~I=L_{0}||R_{0}}$.

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

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

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

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

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

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

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

${\displaystyle ~L_{1}=R_{0}~~~~~~~~~~~~~~~~~~~~~~~~~R_{1}=S9[L_{0}]\oplus ZE(R_{0})}$

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

${\displaystyle ~L_{3}=R_{2}~~~~~~~~~~~~~~~~~~~~~~~~~R_{3}=S9[L_{2}]\oplus ZE(R_{2})}$

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

Функція повертає значення ${\displaystyle ~(L_{4}||R_{4})}$.

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

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

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

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

${\displaystyle ~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
${\displaystyle ~KL_{i,1}}$	K1<<<1	K2<<<1	K3<<<1	K4<<<1	K5<<<1	K6<<<1	K7<<<1	K8<<<1
${\displaystyle ~KL_{i,2}}$	K3'	K4'	K5'	K6'	K7'	K8'	K1'	K2'
${\displaystyle ~KO_{i,1}}$	K2<<<5	K3<<<5	K4<<<5	K5<<<5	K6<<<5	K7<<<5	K8<<<5	K1<<<5
${\displaystyle ~KO_{i,2}}$	K6<<<8	K7<<<8	K8<<<8	K1<<<8	K2<<<8	K3<<<8	K4<<<8	K5<<<8
${\displaystyle ~KO_{i,3}}$	K7<<<13	K8<<<13	K1<<<13	K2<<<13	K3<<<13	K4<<<13	K5<<<13	K6<<<13
${\displaystyle ~KI_{i,1}}$	K5'	K6'	K7'	K8'	K1'	K2'	K3'	K4'
${\displaystyle ~KI_{i,2}}$	K4'	K5'	K6'	K7'	K8'	K1'	K2'	K3'
${\displaystyle ~KI_{i,3}}$	K8'	K1'	K2'	K3'	K4'	K5'	K6'	K7'

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

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

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

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