KASUMI

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
KASUMI
Создатель ETSI
Создан 1999 год
Опубликован 1999 год
Размер ключа 128 бит
Размер блока 64 бит
Число раундов 8
Тип модификация сети Фейстеля

KASUMI (от японск.霞 (hiragana かすみ, romaji kasumi) — туман, mist) — блочный шифр, использующийся в сетях сотовой связи. В UMTS используется в криптографических функциях f8 и f9, в GSM используется в алгоритме A5/3, а в GPRS — в алгоритме GEA/3, причем два последних используют шифр KASUMI с ключом длины 64 бита.

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 разделяется на две равные части:

Затем для каждого :

где  — раундовая функция.  — раундовый 128-битный ключ

На выходе

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

[править | править код]

Вычисляется следующим образом:

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

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

На вход функции подается 32-битный блок данных I и 32-битный ключ KLi, который разделяется на два 16-битных подключа:

.

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

.

Определим:

Где  — циклический сдвиг влево на 1 бит.

На выходе .

На вход функции подается 32-битный блок данных и два ключа по 48 бит: .

Входная строка I разделяется на две части по 16 бит: .

48-битные ключи разделяются на три части каждый:

и .

Затем для определим:

На выходе .

На вход функции подается 16-битный блок данных I и 16-битный ключ KIi, j.

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

.

Точно так же ключ KIi, j, разделяется на 7-битную компоненту KIi, j,1 и 9-битную компоненту KIi, j,2:

.

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

Также используются еще две функции:

Преобразует 7-битное значение x в 9-битное значение добавлением двух нулей в старшие биты.
Преобразует 9-битное значение x в 7-битное вычеркиванием из него двух старших битов.

Функция реализуется следующим набором операций:

Функция возвращает значение .

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:
  • Вычисляется второй массив Kj:

где 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
K1<<<1 K2<<<1 K3<<<1 K4<<<1 K5<<<1 K6<<<1 K7<<<1 K8<<<1
K3' K4' K5' K6' K7' K8' K1' K2'
K2<<<5 K3<<<5 K4<<<5 K5<<<5 K6<<<5 K7<<<5 K8<<<5 K1<<<5
K6<<<8 K7<<<8 K8<<<8 K1<<<8 K2<<<8 K3<<<8 K4<<<8 K5<<<8
K7<<<13 K8<<<13 K1<<<13 K2<<<13 K3<<<13 K4<<<13 K5<<<13 K6<<<13
K5' K6' K7' K8' K1' K2' K3' K4'
K4' K5' K6' K7' K8' K1' K2' K3'
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] Для атаки требуется выбранных открытых текстов, каждый из которых был зашифрован одним из 4 связанных ключей, и имеет сложность по времени, эквивалентную шифрованиям 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 * Orr Dunkelman, Nathan Keller, Adi Shamir. A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony (англ.) // International Association for Cryptologic Research Eprint archive : journal. — 2010. — 10 January. Архивировано 3 февраля 2013 года.
    • A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony // CRYPTO 2010, Lecture Notes in Computer Science Volume 6223, 2010, pp 393-410 doi:10.1007/978-3-642-14623-7 21
  3. 1 2  (англ.) Eli Biham, Orr Dunkelman, Nathan Keller. A Related-Key Rectangle Attack on the Full KASUMI (ps). ASIACRYPT 2005. pp. 443–461. Архивировано 11 октября 2013. Дата обращения: 27 ноября 2009.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Источник. Дата обращения: 27 ноября 2009. Архивировано из оригинала 11 октября 2013 года.
  4. (англ) Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (PDF). CRYPTO 2003. pp. 600–616. Архивировано из оригинала (PDF) 16 декабря 2005.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Источник. Дата обращения: 27 ноября 2009. Архивировано 16 декабря 2005 года.
  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 года.