Русская Википедия:KASUMI
Шаблон:Другие значения Шаблон:Карточка блочного шифра 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 разделяется на две равные части:
- <math>I = L_0 || R_0</math>
Затем для каждого <math>1 \le i \le 8</math>:
- <math>R_{i} = L_{i-1}</math>
- <math>L_i = R_{i-1} \oplus f_i(L_{i-1}, RK_i)</math>
где <math>f_i</math> — раундовая функция. <math>RK_i</math> — раундовый 128-битный ключ
- <math>RK_i = KL_i || KO_i || KI_i</math>
На выходе <math>(L_8 || R_8)</math>
Функция раунда
Вычисляется следующим образом:
Для раундов 1,3,5,7:
- <math>f_i(I, RK_i) = FO( FL( I, KL_i), KO_i, KI_i )</math>
Для раундов 2,4,6,8:
- <math>f_i(I, RK_i) = FL( FO( I, KO_i, KI_i ), KL_i )</math>
Функция FL
На вход функции подается 32-битный блок данных I и 32-битный ключ KLi, который разделяется на два 16-битных подключа:
- <math>KL_i = KL_{i,1} || KL_{i,2}</math>.
Входная строка I разделяется на две части по 16 бит:
- <math>I = L || R</math>.
Определим:
- <math>R' = R \oplus ROL ( L \cap KL_{i,1})</math>
- <math>L' = L \oplus ROL ( R' \vee KL_{i,2})</math>
Где <math>ROL(x)</math> — циклический сдвиг влево на 1 бит.
На выходе <math>(L' || R')</math>.
Функция FO
На вход функции подается 32-битный блок данных и два ключа по 48 бит: <math>KO_i, KI_i</math>.
Входная строка I разделяется на две части по 16 бит: <math>I = L_0 || R_0</math>.
48-битные ключи разделяются на три части каждый:
- <math>KO_i = KO_{i,1} || KO_{i,2} || KO_{i,3}</math> и <math>KI_i = KI_{i,1} || KI_{i,2} || KI_{i,3}</math>.
Затем для <math>1 \le j \le 3</math> определим:
- <math>R_j = FI(L_{j-1} \oplus KO_{i,j} , KI_{i,j} ) \oplus R_{j-1}</math>
- <math>L_j = R_{j-1}</math>
На выходе <math>(L_3 || R_3)</math>.
Функция FI
На вход функции подается 16-битный блок данных I и 16-битный ключ KIi, j.
Вход I разделяется на две неравные составляющие: 9-битную левую часть L0 и 7-битную правую R0:
- <math>I = L_0 || R_0</math>.
Точно так же ключ KIi, j, разделяется на 7-битную компоненту KIi, j,1 и 9-битную компоненту KIi, j,2:
- <math>KI_{i,j} = KI_{i,j,1} || KI_{i,j,2}</math>.
Функция использует два S-блока: S7 который отображает 7-битный вход в 7-битный выход, и S9 который отображает 9-битный вход в 9-битный выход.
Также используются еще две функции:
- <math>ZE(x)</math> Преобразует 7-битное значение x в 9-битное значение добавлением двух нулей в старшие биты.
- <math>TR(x)</math> Преобразует 9-битное значение x в 7-битное вычеркиванием из него двух старших битов.
Функция реализуется следующим набором операций:
- <math>L_1 = R_014:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04) R_1 = S9[L_0] \oplus ZE(R_0)</math>
- <math>L_2 = R_1 \oplus KI_{i,j,2} 14:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04)EducationBot (обсуждение)R_2 = S7[L_1] \oplus TR(R_1) \oplus KI_{i,j,1}</math>
- <math>L_3 = R_214:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04)14:14, 15 июля 2023 (+04) R_3 = S9[L_2] \oplus ZE(R_2)</math>
- <math>L_4 = S7[L_3] \oplus TR(R_3) 14:14, 15 июля 2023 (+04)~ R_4 = R_3</math>
Функция возвращает значение <math>(L_4 || R_4)</math>.
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:
- <math>K = K_1 || K_2 || K_3 || \dots || K_8</math>
- Вычисляется второй массив Kj:
- <math>K_{j'} = K_j \oplus C_j</math>
где 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 <math>KL_{i,1}</math> K1<<<1 K2<<<1 K3<<<1 K4<<<1 K5<<<1 K6<<<1 K7<<<1 K8<<<1 <math>KL_{i,2}</math> K3' K4' K5' K6' K7' K8' K1' K2' <math>KO_{i,1}</math> K2<<<5 K3<<<5 K4<<<5 K5<<<5 K6<<<5 K7<<<5 K8<<<5 K1<<<5 <math>KO_{i,2}</math> K6<<<8 K7<<<8 K8<<<8 K1<<<8 K2<<<8 K3<<<8 K4<<<8 K5<<<8 <math>KO_{i,3}</math> K7<<<13 K8<<<13 K1<<<13 K2<<<13 K3<<<13 K4<<<13 K5<<<13 K6<<<13 <math>KI_{i,1}</math> K5' K6' K7' K8' K1' K2' K3' K4' <math>KI_{i,2}</math> K4' K5' K6' K7' K8' K1' K2' K3' <math>KI_{i,3}</math> 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] Для атаки требуется <math>2^{54.6}</math> выбранных открытых текстов, каждый из которых был зашифрован одним из 4 связанных ключей, и имеет сложность по времени, эквивалентную <math>2^{76.1}</math> шифрованиям KASUMI. Эта атака показывает небезопасность шифрования KASUMI в 3G сетях.
В январе 2010 Orr Dunkelman, Nathan Keller и Ади Шамир опубликовали работу, в которой показали уязвимость Kasumi для атаки на основе связанных ключей (Related-key attack). Злоумышленник может восстановить полный ключ A5/3 с использованием незначительного количества вычислительных ресурсов (авторы оценивают их в 226 по данным, 230 по памяти и 232 по времени и смогли реализовать её за 2 часа работы современного персонального компьютера). Авторы также отметили, что атака может быть не применима к тому способу, каким KASUMI используется в сетях 3G. Разработанная ими атака также не применима к оригинальному MISTY, и они ставят под сомнение заявления 3GPP о том, что при создании KASUMI не была снижена защищенность алгоритма.[2]
Примечания
Шаблон:Симметричные криптоалгоритмы
- ↑ (англ) Шаблон:Cite web
- ↑ 2,0 2,1 * Шаблон:Статья
- 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,0 3,1 Шаблон:Ref-en Шаблон:Cite conference Шаблон:Cite web
- ↑ (англ) Шаблон:Cite conference Шаблон:Cite web
- ↑ (англ) Шаблон:Cite web
