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)[1]. За основу був узятий існуючий алгоритм 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 0 і 7-бітну праву R 0 :

 ~ 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).[2]

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

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

Примітки[ред.ред. код]