Перейти до вмісту

KASUMI

Матеріал з Вікіпедії — вільної енциклопедії.
KASUMI
РозробникиSAGE
Уперше оприлюднений1999 р.
Раундів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=L0||R0

Потім для кожного  1≤i≤8:

 Ri=Li−1
 Li=Ri−1⊕fi(Li−1,RKi)

де  fi - раундова функція.  RKi - раундовий 128-бітний ключ

 RKi=KLi||KOi||KIi

На виході  (L8||R8)

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

[ред. | ред. код]

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

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

 Fi(I,RKi)=FO(FL(I,KLi),KOi,KIi)

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

 Fi(I,RKi)=FL(FO(I,KOi,KIi),KLi)

Функція FL

[ред. | ред. код]

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

 KLi=KLi,1||KLi,2.

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

 I=L||R.

Визначимо:

 R′=R⊕ROL(L∩KLi,1)
 L′=L⊕ROL(R′∨KLi,2)

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

На виході  (L′||R′).

Функція FO

[ред. | ред. код]

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

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

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

 KOi=KOi,1||KOi,2||KOi,3 і  KIi=KIi,1||KIi,2||KIi,3.

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

 Rj=FI(Lj−1⊕KOi,j,KIi,j)⊕Rj−1
 Lj=Rj−1

На виході  (L3||R3).

Функція FI

[ред. | ред. код]

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

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

 I=L0||R0.

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

 KIi,j=KIi,j,1||KIi,j,2.

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

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

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

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

 L1=R0                         R1=S9[L0]⊕ZE(R0)
 L2=R1⊕KIi,j,2             R2=S7[L1]⊕TR(R1)⊕KIi,j,1
 L3=R2                         R3=S9[L2]⊕ZE(R2)
 L4=S7[L3]⊕TR(R3)      R4=R3

Функція повертає значення  (L4||R4).

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

[ред. | ред. код]

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

  • 128-бітний ключ K поділяється на 8:
 K=K1||K2||K3||…||K8
  • Обчислюється другий масив 'K j ':
 Kj′=Kj⊕Cj

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

C10x0123
С20x4567
С30x89AB
С40xCDEF
С50xFEDC
С60xBA98
С70x7654
С80x3210
  • Ключі для кожного раунду обчислюються за наступною таблицею:
Ключ12345678
 KLi,1K1<<<1K2<<<1K3<<<1K4<<<1K5<<<1K6<<<1K7<<<1K8<<<1
 KLi,2K3'K4'K5'K6'K7'K8'K1'K2'
 KOi,1K2<<<5K3<<<5K4<<<5K5<<<5K6<<<5K7<<<5K8<<<5K1<<<5
 KOi,2K6<<<8K7<<<8K8<<<8K1<<<8K2<<<8K3<<<8K4<<<8K5<<<8
 KOi,3K7<<<13K8<<<13K1<<<13K2<<<13K3<<<13K4<<<13K5<<<13K6<<<13
 KIi,1K5'K6'K7'K8'K1'K2'K3'K4'
 KIi,2K4'K5'K6'K7'K8'K1'K2'K3'
 KIi,3K8'K1'K2'K3'K4'K5'K6'K7'

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

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

[ред. | ред. код]

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

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

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

Примітки

[ред. | ред. код]
  1. ↑ Архівована копія (PDF). Архів оригіналу (PDF) за 11 квітня 2012. Процитовано 24 червня 2012.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) [Архівовано 2012-05-12 у Wayback Machine.]
  2. ↑ Архівована копія. Архів оригіналу за 11 жовтня 2013. Процитовано 24 червня 2012.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) [Архівовано 2013-10-11 у Wayback Machine.]
  3. ↑ Архівована копія (PDF). Архів (PDF) оригіналу за 16 грудня 2005. Процитовано 16 грудня 2005.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
  4. ↑ Архівована копія (PDF). Архів оригіналу (PDF) за 11 квітня 2012. Процитовано 24 червня 2012.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) [Архівовано 2012-05-13 у Wayback Machine.]