KASUMI

Cifrado de bloque

KASUMI es un cifrador de bloques utilizado en los sistemas de comunicaciones móviles UMTS , GSM y GPRS . En UMTS, KASUMI se utiliza en los algoritmos de confidencialidad ( f8 ) e integridad ( f9 ) con los nombres UEA1 y UIA1, respectivamente. ^[1] En GSM, KASUMI se utiliza en el generador de flujo de claves A5/3 y en GPRS en el generador de flujo de claves GEA3 .

KASUMI fue diseñado para 3GPP para ser utilizado en el sistema de seguridad UMTS por el Grupo de Expertos en Algoritmos de Seguridad (SAGE), una parte del organismo de normalización europeo ETSI . ^[2] Debido a las presiones de calendario en la estandarización de 3GPP, en lugar de desarrollar un nuevo cifrado, SAGE acordó con el grupo de especificaciones técnicas (TSG) de 3GPP para aspectos del sistema de seguridad 3G (SA3) basar el desarrollo en un algoritmo existente que ya había sido sometido a alguna evaluación. ^[2] Eligieron el algoritmo de cifrado MISTY1 desarrollado ^[3] y patentado ^[4] por Mitsubishi Electric Corporation . El algoritmo original fue ligeramente modificado para una implementación de hardware más sencilla y para cumplir con otros requisitos establecidos para la seguridad de las comunicaciones móviles 3G.

KASUMI lleva el nombre del algoritmo original MISTY1 — 霞み (hiragana かすみ, romaji kasumi ) es la palabra japonesa para "niebla".

En enero de 2010, Orr Dunkelman , Nathan Keller y Adi Shamir publicaron un artículo que demostraba que podían romper Kasumi con un ataque de clave relacionada y recursos computacionales muy modestos; este ataque es ineficaz contra MISTY1 . ^[5]

Descripción

El algoritmo KASUMI se especifica en una especificación técnica 3GPP. ^[6] KASUMI es un cifrado de bloques con una clave de 128 bits y una entrada y salida de 64 bits. El núcleo de KASUMI es una red Feistel de ocho rondas . Las funciones de ronda en la red Feistel principal son transformaciones de red irreversibles similares a Feistel. En cada ronda, la función de ronda utiliza una clave de ronda que consta de ocho subclaves de 16 bits derivadas de la clave original de 128 bits utilizando un programa de claves fijo.

Calendario clave

La clave de 128 bits K se divide en ocho subclaves de 16 bits K _i :

${\displaystyle K=K_{1}\|K_{2}\|K_{3}\|K_{4}\|K_{5}\|K_{6}\|K_{7}\|K_{8}\,}$

Además , se utiliza una clave modificada K' , dividida de forma similar en subclaves de 16 bits K' _i . La clave modificada se deriva de la clave original mediante la operación XOR con 0x123456789ABCDEFFEDCBA9876543210 (elegida como un número "no tengo nada bajo la manga" ).

Las claves redondas se derivan de las subclaves mediante una rotación bit a bit hacia la izquierda en una cantidad determinada y de las subclaves modificadas (sin cambios).

Las claves redondas son las siguientes:

${\displaystyle {\begin{array}{lcl}KL_{i,1}&=&{\rm {ROL}}(K_{i},1)\\KL_{i,2}&=&K'_{i+2}\\KO_{i,1}&=&{\rm {ROL}}(K_{i+1},5)\\KO_{i,2}&=&{\rm {ROL}}(K_{i+5},8)\\KO_{i,3}&=&{\rm {ROL}}(K_{i+6},13)\\KI_{i,1}&=&K'_{i+4}\\KI_{i,2}&=&K'_{i+3}\\KI_{i,3}&=&K'_{i+7}\end{array}}}$

Las adiciones de subíndices de clave son cíclicas, de modo que si i+j es mayor que 8, se debe restar 8 del resultado para obtener el subíndice de clave real.

El algoritmo

El algoritmo KASUMI procesa la palabra de 64 bits en dos mitades de 32 bits, izquierda ( ) y derecha ( ). La palabra de entrada es la concatenación de las mitades izquierda y derecha de la primera ronda: ${\displaystyle L_{i}}$ ${\displaystyle R_{i}}$

${\displaystyle {\rm {input}}=R_{0}\|L_{0}\,}$.

En cada ronda, la mitad derecha se combina con la salida de la función de ronda, después de lo cual se intercambian las mitades:

${\displaystyle {\begin{array}{rcl}L_{i}&=&F_{i}(KL_{i},KO_{i},KI_{i},L_{i-1})\oplus R_{i-1}\\R_{i}&=&L_{i-1}\end{array}}}$

donde KL _i , KO _i , KI _i son claves redondas para la i ^ésima ronda.

Las funciones de redondeo para los números pares e impares son ligeramente diferentes. En cada caso, la función de redondeo es una composición de dos funciones FL _i y FO _i . Para un número impar

${\displaystyle F_{i}(K_{i},L_{i-1})=FO(KO_{i},KI_{i},FL(KL_{i},L_{i-1}))\,}$

y para una ronda pareja

${\displaystyle F_{i}(K_{i},L_{i-1})=FL(KL_{i},FO(KO_{i},KI_{i},L_{i-1}))\,}$.

La salida es la concatenación de las salidas de la última ronda.

${\displaystyle {\rm {output}}=R_{8}\|L_{8}\,}$.

Tanto la función FL como la función FO dividen los datos de entrada de 32 bits en dos mitades de 16 bits. La función FL es una manipulación de bits irreversible, mientras que la función FO es una red irreversible de tres rondas similar a la de Feistel.

Función FL

La entrada de 32 bits x de se divide en dos mitades de 16 bits . Primero, la mitad izquierda de la entrada se combina con AND bit a bit con una clave circular y se gira a la izquierda un bit. El resultado de esto se combina con XOR en la mitad derecha de la entrada para obtener la mitad derecha de la salida . ${\displaystyle FL(KL_{i},x)}$ ${\displaystyle x=l\|r}$ ${\displaystyle l}$ ${\displaystyle KL_{i,1}}$ ${\displaystyle r}$ ${\displaystyle r'}$

${\displaystyle r'={\rm {ROL}}(l\wedge KL_{i,1},1)\oplus r}$

Luego, la mitad derecha de la salida se combina con la operación OR bit a bit con la clave circular y se gira a la izquierda un bit. El resultado de esto se combina con la operación XOR en la mitad izquierda de la entrada para obtener la mitad izquierda de la salida . ${\displaystyle r'}$ ${\displaystyle KL_{i,2}}$ ${\displaystyle l}$ ${\displaystyle l'}$

${\displaystyle l'={\rm {ROL}}(r'\vee KL_{i,2},1)\oplus l}$

La salida de la función es la concatenación de las mitades izquierda y derecha . ${\displaystyle x'=l'\|r'}$

Función FO

La entrada de 32 bits x de se divide en dos mitades de 16 bits y pasa a través de tres rondas de una red Feistel. ${\displaystyle FO(KO_{i},KI_{i},x)}$ ${\displaystyle x=l_{0}\|r_{0}}$

En cada una de las tres rondas (indexadas por j que toma los valores 1, 2 y 3) la mitad izquierda se modifica para obtener la nueva mitad derecha y la mitad derecha se convierte en la mitad izquierda de la siguiente ronda.

${\displaystyle {\begin{array}{lcl}r_{j}&=&FI(KI_{i,j},l_{j-1}\oplus KO_{i,j})\oplus r_{j-1}\\l_{j}&=&r_{j-1}\end{array}}}$

La salida de la función es . ${\displaystyle x'=l_{3}\|r_{3}}$

Función FI

La función FI es una red irregular tipo Feistel.

La entrada de 16 bits de la función se divide en dos mitades , una de las cuales tiene 9 bits de ancho y otra de 7 bits de ancho. ${\displaystyle x}$ ${\displaystyle FI(Ki,x)}$ ${\displaystyle x=l_{0}\|r_{0}}$ ${\displaystyle l_{0}}$ ${\displaystyle r_{0}}$

Los bits de la mitad izquierda se mezclan primero mediante la caja de sustitución de 9 bits (caja S) S9 y el resultado se combina con la mitad derecha extendida a cero para obtener la nueva mitad derecha de 9 bits . ${\displaystyle l_{0}}$ ${\displaystyle r_{0}}$ ${\displaystyle r_{1}}$

${\displaystyle r_{1}=S9(l_{0})\oplus (00\|r_{0})\,}$

Los bits de la mitad derecha se mezclan mediante la caja S7 de 7 bits y el resultado se combina con los siete bits menos significativos ( LS7 ) de la nueva mitad derecha para obtener la nueva mitad izquierda de 7 bits . ${\displaystyle r_{0}}$ ${\displaystyle r_{1}}$ ${\displaystyle l_{1}}$

${\displaystyle l_{1}=S7(r_{0})\oplus LS7(r_{1})\,}$

La palabra intermedia se combina con la clave redonda KI para obtener KI, que tiene 7 bits de ancho y KI, que tiene 9 bits de ancho. ${\displaystyle x_{1}=l_{1}\|r_{1}}$ ${\displaystyle x_{2}=l_{2}\|r_{2}}$ ${\displaystyle l_{2}}$ ${\displaystyle r_{2}}$

${\displaystyle x_{2}=KI\oplus x_{1}}$

Luego, los bits de la mitad derecha se mezclan mediante la caja S9 de 9 bits y el resultado se combina con la mitad izquierda extendida a cero para obtener la nueva mitad derecha de 9 bits de la salida . ${\displaystyle r_{2}}$ ${\displaystyle l_{2}}$ ${\displaystyle r_{3}}$

${\displaystyle r_{3}=S9(r_{2})\oplus (00\|l_{2})\,}$

Finalmente, los bits de la mitad izquierda se mezclan mediante la S-box S7 de 7 bits y el resultado se combina con los siete bits menos significativos ( LS7 ) de la mitad derecha de la salida para obtener la mitad izquierda de 7 bits de la salida. ${\displaystyle l_{2}}$ ${\displaystyle r_{3}}$ ${\displaystyle l_{3}}$

${\displaystyle l_{3}=S7(l_{2})\oplus LS7(r_{3})\,}$

La salida es la concatenación de las mitades izquierda y derecha finales . ${\displaystyle x'=l_{3}\|r_{3}}$

Cajas de sustitución

Las cajas de sustitución (S-boxes) S7 y S9 se definen tanto mediante expresiones AND-XOR bit a bit como mediante tablas de consulta en la especificación. Las expresiones bit a bit están pensadas para la implementación en hardware, pero actualmente es habitual utilizar las tablas de consulta incluso en el diseño de hardware.

S7 se define mediante la siguiente matriz:

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

S9 se define mediante la siguiente matriz:

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

Criptoanálisis

En 2001, Kühn (2001) presentó un ataque diferencial imposible en seis rondas de KASUMI. ^[7]

En 2003, Elad Barkan, Eli Biham y Nathan Keller demostraron ataques de intermediario contra el protocolo GSM que evitaban el cifrado A5/3 y, por lo tanto, rompían el protocolo. Sin embargo, este enfoque no ataca el cifrado A5/3. ^[8] La versión completa de su artículo se publicó más tarde en 2006. ^[9]

En 2005, los investigadores israelíes Eli Biham , Orr Dunkelman y Nathan Keller publicaron un ataque de rectángulo de clave relacionada (boomerang) contra KASUMI que puede romper las 8 rondas más rápido que una búsqueda exhaustiva. ^[10] El ataque requiere 2 ^54,6 textos simples elegidos, cada uno de los cuales ha sido cifrado con una de las cuatro claves relacionadas, y tiene una complejidad temporal equivalente a 2 ^76,1 cifrados de KASUMI. Si bien esto obviamente no es un ataque práctico, invalida algunas pruebas sobre la seguridad de los protocolos 3GPP que se habían basado en la presunta fortaleza de KASUMI.

En 2010, Dunkelman, Keller y Shamir publicaron un nuevo ataque que permite a un adversario recuperar una clave A5/3 completa mediante un ataque de clave relacionada . ^[5] Las complejidades de tiempo y espacio del ataque son lo suficientemente bajas como para que los autores lo llevaran a cabo en dos horas en una computadora de escritorio Intel Core 2 Duo incluso utilizando la implementación de referencia KASUMI no optimizada. Los autores señalan que este ataque puede no ser aplicable a la forma en que se utiliza A5/3 en los sistemas 3G; su principal propósito era desacreditar las garantías de 3GPP de que sus cambios a MISTY no afectarían significativamente la seguridad del algoritmo.

Véase también

• A5/1 y A5/2
• NIEVE

Referencias

1. "Informe preliminar de SA3 #38" (PDF) . 3GPP. 2005.
2. "Informe general sobre el diseño, especificación y evaluación de los algoritmos de confidencialidad e integridad del estándar 3GPP" (PDF) . 3GPP. 2009.
3. Matsui, Mitsuru; Tokita, Toshio (diciembre de 2000). "Desarrollo de algoritmos de cifrado MISTY, KASUMI y Camellia" (PDF) . Mitsubishi Electric Advance . 100 . Mitsubishi Electric corp.: 2–8. ISSN  1345-3041. Archivado desde el original (PDF) el 24 de julio de 2008 . Consultado el 6 de enero de 2010 .
4. US 7096369, Matsui, Mitsuru y Tokita, Toshio, "Aparato de transformación de datos y método de transformación de datos", publicado el 19 de septiembre de 2002, emitido el 22 de agosto de 2006 
5. Orr Dunkelman; Nathan Keller; Adi Shamir (10 de enero de 2010). "Un ataque en tiempo real al criptosistema A5/3 utilizado en la telefonía GSM de tercera generación". {{cite journal}}: Requiere citar revista |journal=( ayuda )
6. "3GPP TS 35.202: Especificación de los algoritmos de confidencialidad e integridad 3GPP; Documento 2: Especificación Kasumi". 3GPP. 2009.
7. Kühn, Ulrich. Criptoanálisis de MISTY de forma redonda reducida . EUROCRYPT 2001. CiteSeerX 10.1.1.59.7609 . 
8. Elad Barkan, Eli Biham , Nathan Keller. Criptoanálisis instantáneo de texto cifrado únicamente de comunicaciones GSM encriptadas (PDF) . CRYPTO 2003. págs. 600–616. Archivado desde el original (PDF) el 25 de enero de 2020. Consultado el 15 de septiembre de 2019 .{{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace )
9. Elad Barkan, Eli Biham , Nathan Keller. "Criptoanálisis instantáneo de texto cifrado de comunicaciones GSM por Barkan y Biham de Technion (versión completa)" (PDF) . Archivado desde el original (PDF) el 25 de enero de 2020. Consultado el 15 de septiembre de 2019 .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )
10. Eli Biham , Orr Dunkelman , Nathan Keller. Un ataque de rectángulo de clave relacionada en el KASUMI completo. ASIACRYPT 2005. págs. 443–461. Archivado desde el original (ps) el 11 de octubre de 2013.{{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace )

Enlaces externos

• Página de inicio de Nathan Keller