KASUMI (от японск.霞 (hiragana かすみ, romaji kasumi) — туман, mist) — блочный шифр, использующийся в сетях сотовой связи. В UMTS используется в криптографических функциях f8 и f9, в GSM используется в алгоритме A5/3, а в GPRS — в алгоритме GEA/3, причем два последних используют шифр KASUMI с ключом длины 64 бита.
KASUMI разработан группой SAGE (Security Algorithms Group of Experts), которая является частью Европейского Института по Стандартизации в области Телекоммуникаций (ETSI)(англ) . За основу был взят существующий алгоритм MISTY1 и оптимизирован для использования в сотовой связи.
Как показали в 2010 году криптоаналитики, в процессе изменений надежность алгоритма MISTY1 была снижена: KASUMI имеет уязвимости для некоторых типов атак, тогда как MISTY1 является стойким по отношению к ним.
Описание KASUMI использует 64-битный размер блока и 128-битный ключ в 8-раундовой схеме Фейстеля. В каждом раунде используется 128-битный раундовый ключ, состоящий из восьми 16-битных подключей, полученных из исходного ключа по фиксированной процедуре генерации подключей.
Схема шифрования
Основной алгоритм KASUMI разлагается в набор функций (FL, FO, FI), которые используются вместе со связанными с ними ключами (KL, KO, KI)
Входной блок данных I разделяется на две равные части:
Затем для каждого :
где — раундовая функция. — раундовый 128-битный ключ
На выходе
Функция раунда Вычисляется следующим образом:
Для раундов 1,3,5,7:
Для раундов 2,4,6,8:
Функция FL На вход функции подается 32-битный блок данных I и 32-битный ключ KLi, который разделяется на два 16-битных подключа: . Входная строка I разделяется на две части по 16 бит: . Определим:
Где — циклический сдвиг влево на 1 бит.
На выходе .
Функция FO На вход функции подается 32-битный блок данных и два ключа по 48 бит: .
Входная строка I разделяется на две части по 16 бит: .
48-битные ключи разделяются на три части каждый: и . Затем для определим:
На выходе .
Функция FI На вход функции подается 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-блоки S-блоки преобразуют 7 или 9 битный входной блок в соответственно 7 или 9 битный выходной блок, используя таблицы подстановок Например: S7 = 124 Десятичная таблица замены для блока S7: {| class="standard"
|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:
{| class="standard"
|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 определяются по таблице: {| class="standard"
|C1|| 0x0123
|С2|| 0x4567
|С3|| 0x89AB
|С4|| 0xCDEF
|С5|| 0xFEDC
|С6|| 0xBA98
|С7|| 0x7654
|С8|| 0x3210
Ключи для каждого раунда вычисляются по следующей таблице: {| class="standard" !Ключ || 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).
В 2003 году Элад Баркан, Эли Бихам и Натан Келлер продемонстрировали атаку с посредником на протокол GSM, что позволяет обойти шифр A5/3 и таким образом сломать протокол. Однако, этот подход не взламывает шифр A5/3 напрямую.(англ) Полная версия была опубликована позже, в 2006.(англ)
В 2005 году Эли Бихам, Орр Дункельман и Натан Келлер опубликовали атаку на KASUMI методом бумеранга, которая взламывает шифр быстрее, чем полный перебор. Для атаки требуется выбранных открытых текстов, каждый из которых был зашифрован одним из 4 связанных ключей, и имеет сложность по времени, эквивалентную шифрованиям KASUMI. Эта атака показывает небезопасность шифрования KASUMI в 3G сетях.
В январе 2010 Orr Dunkelman, Nathan Keller и Ади Шамир опубликовали работу, в которой показали уязвимость Kasumi для атаки на основе связанных ключей (Related-key attack). Злоумышленник может восстановить полный ключ A5/3 с использованием незначительного количества вычислительных ресурсов (авторы оценивают их в 226 по данным, 230 по памяти и 232 по времени и смогли реализовать её за 2 часа работы современного персонального компьютера). Авторы также отметили, что атака может быть не применима к тому способу, каким KASUMI используется в сетях 3G. Разработанная ими атака также не применима к оригинальному MISTY, и они ставят под сомнение заявления 3GPP о том, что при создании KASUMI не была снижена защищенность алгоритма.* 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
Примечания
Категория:Блочные шифры Категория:Сеть Фейстеля