Hispanopedia Wiki
Articulo de referencia

KASUMI

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 ) ...

Hispanopedia WikiContenido en espanolLectura gratuita

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 ), denominados 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), parte del organismo de estándares europeo ETSI . [ 2 ] Debido a las presiones de tiempo en la estandarización de 3GPP, en lugar de desarrollar un nuevo cifrado, SAGE acordó con el grupo de especificación técnica (TSG) de 3GPP para aspectos del sistema de seguridad 3G (SA3) basar el desarrollo en un algoritmo existente que ya había sido evaluado. [ 2 ] Eligieron el algoritmo de cifrado MISTY1 desarrollado [ 3 ] y patentado [ 4 ] por Mitsubishi Electric Corporation . El algoritmo original fue ligeramente modificado para facilitar la implementación de hardware 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 de 3GPP. [ 6 ] KASUMI es un cifrador 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 tipo 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 mediante una programación de clave fija.

Horario clave

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

K=K1‖K2‖K3‖K4‖K5‖K6‖K7‖K8{\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 manera similar en subclaves de 16 bits K' i . La clave modificada se deriva de la clave original mediante una operación XOR con 0x123456789ABCDEFFEDCBA9876543210 (elegido como un número de "nada oculto" ).

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

Las teclas redondas son las siguientes:

KLi,1=ROL(Ki,1)KLi,2=Ki+2′KOi,1=ROL(Ki+1,5)KOi,2=ROL(Ki+5,8)KOi,3=ROL(Ki+6,13)KIi,1=Ki+4′KIi,2=Ki+3′KIi,3=Ki+7′{\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 índices de subclaves son cíclicas, de modo que si i+j es mayor que 8, hay que restar 8 al resultado para obtener el índice de subclave real.

El algoritmo

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

inortepagtút=R0‖L0{\displaystyle {\rm {entrada}}=R_{0}\|L_{0}\,}.

En cada ronda, la mitad derecha se combina mediante XOR con el resultado de la función de ronda, tras lo cual se intercambian las mitades:

Li=Fi(KLi,KOi,KIi,Li−1)⊕Ri−1Ri=Li−1{\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 las claves de ronda para la i- ésima ronda.

Las funciones de ronda para rondas pares e impares son ligeramente diferentes. En cada caso, la función de ronda es una composición de dos funciones FL i y FO i . Para una ronda impar

Fi(Ki,Li−1)=FO(KOi,KIi,FL(KLi,Li−1)){\displaystyle F_{i}(K_{i},L_{i-1})=FO(KO_{i},KI_{i},FL(KL_{i},L_{i-1}))\,}

y para una ronda igualada

Fi(Ki,Li−1)=FL(KLi,FO(KOi,KIi,Li−1)){\displaystyle F_{i}(K_{i},L_{i-1})=FL(KL_{i},FO(KO_{i},KI_{i},L_{i-1}))\,}.

El resultado es la concatenación de los resultados de la ronda anterior.

otútpagtút=R8‖L8{\displaystyle {\rm {salida}}=R_{8}\|L_{8}\,}.

Las funciones FL y 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 deFL(KLi,incógnita){\displaystyle FL(KL_{i},x)}está dividido en dos mitades de 16 bitsincógnita=l‖r{\displaystyle x=l\|r}. Primero la mitad izquierda de la entradal{\displaystyle l}se combina mediante AND bit a bit con clave redondaKLi,1{\displaystyle KL_{i,1}}y se rota un bit a la izquierda. El resultado se combina mediante XOR con la mitad derecha de la entrada.r{\displaystyle r}para obtener la mitad correcta de la salidar′{\displaystyle r'}.

r′=ROL(l∧KLi,1,1)⊕r{\displaystyle r'={\rm {ROL}}(l\wedge KL_{i,1},1)\oplus r}

Luego, la mitad derecha de la salidar′{\displaystyle r'}se combina mediante OR bit a bit con la clave redondaKLi,2{\displaystyle KL_{i,2}}y se rota un bit a la izquierda. El resultado se combina mediante XOR con la mitad izquierda de la entrada.l{\displaystyle l}para obtener la mitad izquierda de la salidal′{\displaystyle l'}.

l′=ROL(r′∨KLi,2,1)⊕l{\displaystyle l'={\rm {ROL}}(r'\vee KL_{i,2},1)\oplus l}

El resultado de la función es la concatenación de las mitades izquierda y derecha.incógnita′=l′‖r′{\displaystyle x'=l'\|r'}.

Función FO

La entrada de 32 bits x deFO(KOi,KIi,incógnita){\displaystyle FO(KO_{i},KI_{i},x)}está dividido en dos mitades de 16 bitsincógnita=l0‖r0{\displaystyle x=l_{0}\|r_{0}}y pasó por tres rondas de una red Feistel.

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.

rj=FI(KIi,j,lj−1⊕KOi,j)⊕rj−1lj=rj−1{\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 esincógnita′=l3‖r3{\displaystyle x'=l_{3}\|r_{3}}.

Función FI

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

La entrada de 16 bitsincógnita{\displaystyle x}de la funciónFI(Ki,incógnita){\displaystyle FI(Ki,x)}está dividido en dos mitadesincógnita=l0‖r0{\displaystyle x=l_{0}\|r_{0}} de cuáll0{\displaystyle l_{0}}tiene 9 bits de ancho yr0{\displaystyle r_{0}}tiene 7 bits de ancho.

Fragmentos en la mitad izquierdal0{\displaystyle l_{0}}Primero se barajan mediante una caja de sustitución de 9 bits (caja S) S9 y el resultado se combina mediante XOR con la mitad derecha extendida a cero.r0{\displaystyle r_{0}}para obtener la nueva mitad derecha de 9 bitsr1{\displaystyle r_{1}}.

r1=S9(l0)⊕(00‖r0){\displaystyle r_{1}=S9(l_{0})\oplus (00\|r_{0})\,}

Fragmentos de la mitad derechar0{\displaystyle r_{0}}son barajados por la caja S de 7 bits S7 y el resultado se combina mediante XOR con los siete bits menos significativos ( LS7 ) de la nueva mitad derecha.r1{\displaystyle r_{1}}para obtener la nueva mitad izquierda de 7 bitsl1{\displaystyle l_{1}}.

l1=S7(r0)⊕LS7(r1){\displaystyle l_{1}=S7(r_{0})\oplus LS7(r_{1})\,}

La palabra intermediaincógnita1=l1‖r1{\displaystyle x_{1}=l_{1}\|r_{1}}se combina mediante XOR con la clave redonda KI para obtenerincógnita2=l2‖r2{\displaystyle x_{2}=l_{2}\|r_{2}} de cuáll2{\displaystyle l_{2}}tiene 7 bits de ancho yr2{\displaystyle r_{2}}tiene 9 bits de ancho.

incógnita2=KI⊕incógnita1{\displaystyle x_{2}=KI\oplus x_{1}}

Fragmentos en la mitad derechar2{\displaystyle r_{2}}Luego, se barajan mediante la caja S de 9 bits S9 y el resultado se combina mediante XOR con la mitad izquierda extendida a cero.l2{\displaystyle l_{2}}para obtener la nueva mitad derecha de 9 bits de la salidar3{\displaystyle r_{3}}.

r3=S9(r2)⊕(00‖l2){\displaystyle r_{3}=S9(r_{2})\oplus (00\|l_{2})\,}

Finalmente, las partes de la mitad izquierdal2{\displaystyle l_{2}}son mezclados por la caja S de 7 bits S7 y el resultado se combina mediante XOR con los siete bits menos significativos ( LS7 ) de la mitad derecha de la salida.r3{\displaystyle r_{3}}para obtener la mitad izquierda de 7 bitsl3{\displaystyle l_{3}}de la salida.

l3=S7(l2)⊕LS7(r3){\displaystyle l_{3}=S7(l_{2})\oplus LS7(r_{3})\,}

El resultado es la concatenación de las mitades izquierda y derecha finales.incógnita′=l3‖r3{\displaystyle x'=l_{3}\|r_{3}}.

Cajas de sustitución

Las cajas de sustitución (cajas S) S7 y S9 se definen en la especificación mediante expresiones AND-XOR bit a bit y tablas de búsqueda. Las expresiones bit a bit están pensadas para la implementación en hardware, pero actualmente es habitual utilizar las tablas de búsqueda 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 , 89 , 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 , 290 , 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 , 478 , 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 , 297 , 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 eludían el cifrado A5/3 y, por lo tanto, rompían el protocolo. Sin embargo, este método no ataca el cifrado A5/3. [ 8 ] La versión completa de su artículo se publicó posteriormente 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 planos elegidos, cada uno de los cuales ha sido cifrado con una de cuatro claves relacionadas, y tiene una complejidad temporal equivalente a 2 76,1 cifrados 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 supuesta 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 ] La complejidad temporal y espacial del ataque es lo suficientemente baja como para que los autores lo llevaran a cabo en dos horas en un ordenador de sobremesa 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 objetivo era desacreditar las garantías de 3GPP de que sus cambios en MISTY no afectarían significativamente la seguridad del algoritmo.

Véase también

Referencias

  1. ↑ "Borrador del informe de SA3 #38" (PDF) . 3GPP. 2005.
  2. 1 2 "Informe general sobre el diseño, especificación y evaluación de los algoritmos estándar de confidencialidad e integridad de 3GPP" (PDF) . 3GPP. 2009.
  3. ↑ Matsui, Mitsuru; Tokita, Toshio (dic. 2000). "MISTY, KASUMI y desarrollo del algoritmo de cifrado Camellia" (PDF) . Mitsubishi Electric Advance . 100. Mitsubishi Electric corp.: 2–8 . ISSN 1345-3041 . Archivado del original (PDF) el 24 de julio de 2008. Consultado el 6 de enero de 2010 . 
  4. ↑ US 7096369 , Matsui, Mitsuru y Tokita, Toshio, "Aparato y método de transformación de datos", publicado el 19 de septiembre de 2002, emitido el 22 de agosto de 2006 
  5. 1 2 Orr Dunkelman; Nathan Keller; Adi Shamir (10 de enero de 2010). "Un ataque práctico en tiempo real contra el criptosistema A5/3 utilizado en la telefonía GSM de tercera generación" .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  6. ↑ "3GPP TS 35.202: Especificación de los algoritmos de confidencialidad e integridad de 3GPP; Documento 2: Especificación de Kasumi" . 3GPP. 2009.
  7. ↑ Kühn, Ulrich. Criptoanálisis de MISTY Reducido Redondo . EUROCRYPT 2001. CiteSeerX 10.1.1.59.7609 . 
  8. ↑ Elad Barkan, Eli Biham , Nathan Keller. Criptoanálisis instantáneo solo con texto cifrado de comunicaciones encriptadas GSM (PDF) . CRYPTO 2003. págs. 600–616 . Archivado del 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 solo con texto cifrado de comunicaciones encriptadas GSM por Barkan y Biham del Technion (versión completa)" (PDF) . Archivado del 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 con clave relacionada contra el KASUMI completo . ASIACRYPT 2005. págs. 443–461 . Archivado del original (ps) el 11 de octubre de 2013. {{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Página principal de Nathan Keller