KASUMI

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
KASUMI
Создатель:

ETSI

Создан:

1999 год

Опубликован:

1999 год

Размер ключа:

128 бит

Размер блока:

64 бит

Число раундов:

8

Тип:

модификация сети Фейстеля

KASUMI (от японск.霞 (hiragana かすみ, romaji kasumi) — туман, mist) — блочный шифр, использующийся в сетях сотовой связи 3GPP. Также обозначается A5/3 при использовании в GSM и GEA3 в GPRS.

KASUMI разработан группой SAGE (Security Algorithms Group of Experts), которая является частью Европейского Института по Стандартизации в области Телекоммуникаций (ETSI)[1]. За основу был взят существующий алгоритм MISTY1 и оптимизирован для использования в сотовой связи.

Как показали в 2010 году криптоаналитики, в процессе изменений надежность алгоритма MISTY1 была снижена: KASUMI имеет уязвимости к некоторым типам атак, тогда как MISTY1 является стойким по отношению к ним.[2]

Описание[править | править вики-текст]

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-битный ключ KLi, который разделяется на два 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 \le 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-битный ключ KIi, j.

Вход I разделяется на две неравные составляющие: 9-битную левую часть L0 и 7-битную правую R0:

~I = L_0 || R_0.

Точно так же ключ KIi, j, разделяется на 7-битную компоненту KIi, j,1 и 9-битную компоненту KIi, 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).

S-блоки[править | править вики-текст]

S-блоки преобразуют 7 или 9 битный входной блок в соответственно 7 или 9 битный выходной блок, используя таблицы подстановок

Например: S7[30] = 124

Десятичная таблица замены для блока S7:

S7[0-15] 54 50 62 56 22 34 94 96 38 6 63 93 2 18 123 33
S7[16-31] 55 113 39 114 21 67 65 12 47 73 46 27 25 111 124 81
S7[32-47] 53 9 121 79 52 60 58 48 101 127 40 120 104 70 71 43
S7[48-63] 20 122 72 61 23 109 13 100 77 1 16 7 82 10 105 98
S7[64-79] 117 116 76 11 89 106 0 125 118 99 86 69 30 57 126 87
S7[80-95] 112 51 17 5 95 14 90 84 91 8 35 103 32 97 28 66
S7[96-111] 102 31 26 45 75 4 85 92 37 74 80 49 68 29 115 44
S7[112-127] 64 107 108 24 110 83 36 78 42 19 15 41 88 119 59 3

Десятичная таблица замены для блока S9:

S9[0-15] 167 239 161 379 391 334 9 338 38 226 48 358 452 385 90 397
S9[16-31] 183 253 147 331 415 340 51 362 306 500 262 82 216 159 356 177
S9[32-47] 175 241 489 37 206 17 0 333 44 254 378 58 143 220 81 400
S9[48-63] 95 3 315 245 54 235 218 405 472 264 172 494 371 290 399 76
S9[64-79] 165 197 395 121 257 480 423 212 240 28 462 176 406 507 288 223
S9[80-95] 501 407 249 265 89 186 221 428 164 74 440 196 458 421 350 163
S9[96-111] 232 158 134 354 13 250 491 142 191 69 193 425 152 227 366 135
S9[112-127] 344 300 276 242 437 320 113 278 11 243 87 317 36 93 496 27
S9[128-143] 487 446 482 41 68 156 457 131 326 403 339 20 39 115 442 124
S9[144-159] 475 384 508 53 112 170 479 151 126 169 73 268 279 321 168 364
S9[160-175] 363 292 46 499 393 327 324 24 456 267 157 460 488 426 309 229
S9[176-191] 439 506 208 271 349 401 434 236 16 209 359 52 56 120 199 277
S9[192-207] 465 416 252 287 246 6 83 305 420 345 153 502 65 61 244 282
S9[208-223] 173 222 418 67 386 368 261 101 476 291 195 430 49 79 166 330
S9[224-239] 280 383 373 128 382 408 155 495 367 388 274 107 459 417 62 454
S9[240-255] 132 225 203 316 234 14 301 91 503 286 424 211 347 307 140 374
S9[256-271] 35 103 125 427 19 214 453 146 498 314 444 230 256 329 198 285
S9[272-287] 50 116 78 410 10 205 510 171 231 45 139 467 29 86 505 32
S9[288-303] 72 26 342 150 313 490 431 238 411 325 149 473 40 119 174 355
S9[304-319] 185 233 389 71 448 273 372 55 110 178 322 12 469 392 369 190
S9[320-335] 1 109 375 137 181 88 75 308 260 484 98 272 370 275 412 111
S9[336-351] 336 318 4 504 492 259 304 77 337 435 21 357 303 332 483 18
S9[352-367] 47 85 25 497 474 289 100 269 296 478 270 106 31 104 433 84
S9[368-383] 414 486 394 96 99 154 511 148 413 361 409 255 162 215 302 201
S9[384-399] 266 351 343 144 441 365 108 298 251 34 182 509 138 210 335 133
S9[400-415] 311 352 328 141 396 346 123 319 450 281 429 228 443 481 92 404
S9[416-431] 485 422 248 297 23 213 130 466 22 217 283 70 294 360 419 127
S9[432-447] 312 377 7 468 194 2 117 295 463 258 224 447 247 187 80 398
S9[448-463] 284 353 105 390 299 471 470 184 57 200 348 63 204 188 33 451
S9[464-479] 97 30 310 219 94 160 129 493 64 179 263 102 189 207 114 402
S9[480-495] 438 477 387 122 192 42 381 5 145 118 180 449 293 323 136 380
S9[496-511] 43 66 60 455 341 445 202 432 8 237 15 376 436 464 59 461

Получение раундовых ключей[править | править вики-текст]

Каждый раунд KASUMI получает ключи из общего ключа K следующим образом:

  • 128-битный ключ K разделяется на 8:
~K = K_1 || K_2 || K_3 || \dots || K_8
  • Вычисляется второй массив Kj:
~K_{j'} = K_j \oplus C_j

где Cj определяются по таблице:

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

В 2003 году Элад Баркан, Эли Бихам и Натан Келлер продемонстрировали атаку с посредником на протокол GSM, что позволяет обойти шифр A5/3 и таким образом сломать протокол. Однако, этот подход не взламывает шифр A5/3 напрямую.[4] Полная версия была опубликована позже, в 2006.[5]

В 2005 году Эли Бихам, Орр Дункельман и Натан Келлер опубликовали атаку на KASUMI методом бумеранга, которая взламывает шифр быстрее, чем полный перебор.[3] Для атаки требуется 2^{54.6} выбранных открытых текстов, каждый из которых был зашифрован одним из 4 связанных ключей, и имеет сложность по времени, эквивалентную 2^{76.1} шифрованиям KASUMI. Эта атака показывает небезопасность шифрования KASUMI в 3G сетях.

В январе 2010 Orr Dunkelman, Nathan Keller и Ади Шамир опубликовали работу, в которой показали уязвимость Kasumi к атаке Related-key attack (англ.)русск.. Злоумышленник может восстановить полный ключ A5/3 с использованием незначительного количества вычислительных ресурсов (авторы оценивают их в 226 по данным, 230 по памяти и 232 по времени и смогли реализовать ее за 2 часа работы современного персонального компьютера). Авторы также отметили, что атака может быть не применима к тому способу, каким KASUMI используется в сетях 3G. Разработанная ими атака также не применима к оригинальному MISTY, и они ставят под сомнение заявления 3GPP о том, что при создании KASUMI не была снижена защищенность алгоритма.[2]

Примечания[править | править вики-текст]

  1. (англ) Universal Mobile Telecommunications System (UMTS); Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification. ETSI (2007). Архивировано из первоисточника 11 апреля 2012.
  2. 1 2
  3. 1 2  (англ.) Eli Biham, Orr Dunkelman, Nathan Keller. "A Related-Key Rectangle Attack on the Full KASUMI" (ps) in ASIACRYPT 2005.: 443-461. 
  4. (англ) Elad Barkan, Eli Biham, Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication" in CRYPTO 2003.: 600-616. 
  5. (англ) Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version). Архивировано из первоисточника 11 апреля 2012.