KASUMI es un cifrado de bloques utilizado en 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 .
General | |
---|---|
Diseñadores | Mitsubishi Electric |
Derivado de | MISTY1 |
Detalle de cifrado | |
Tamaños de clave | 128 bits |
Tamaños de bloque | 64 bits |
Estructura | Red Feistel |
Rondas | 8 |
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 europeo de estándares ETSI . [2] Debido a las presiones de programación 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 los aspectos del sistema de seguridad 3G (SA3) para basar el desarrollo en un algoritmo existente que ya se había sometido a algunos evaluación. [2] Eligieron el algoritmo de cifrado MISTY1 desarrollado [3] y patentado [4] por Mitsubishi Electric Corporation . El algoritmo original se modificó ligeramente para facilitar la implementación del hardware y 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 mostraba 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 en bloque con clave de 128 bits y entrada y salida de 64 bits. El núcleo de KASUMI es una red Feistel de ocho rondas . Las funciones redondas en la red principal de Feistel son transformaciones de red irreversibles similares a las de Feistel. En cada ronda, la función de ronda utiliza una clave redonda que consta de ocho subclaves de 16 bits derivadas de la clave original de 128 bits utilizando un programa de clave fijo.
Horario clave
La clave K de 128 bits se divide en ocho subclaves K i de 16 bits :
Además , se utiliza una clave K ' modificada , igualmente dividida en subclaves K' i de 16 bits . La clave modificada se deriva de la clave original mediante XORing con 0x123456789ABCDEFFEDCBA9876543210 (elegido como un número de "nada bajo mi manga" ).
Las claves redondas se derivan de las subclaves mediante una rotación bit a la izquierda en una cantidad determinada y de las subclaves modificadas (sin cambios).
Las claves redondas son las siguientes:
Las adiciones de índice de subclave son cíclicas, de modo que si i + j es mayor que 8, uno tiene que restar 8 del 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 () y derecha (). La palabra de entrada es la concatenación de las mitades izquierda y derecha de la primera ronda:
.
En cada ronda, la mitad derecha se XOR'ed con la salida de la función de ronda, después de lo cual se intercambian las mitades:
donde KL i , KO i , KI i son teclas redondas para la i ésima ronda.
Las funciones de ronda para rondas 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 . Por una ronda extraña
y por una ronda uniforme
.
La salida es la concatenación de las salidas de la última ronda.
.
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 de tres vueltas tipo Feistel irreversible.
Función FL
La entrada x de 32 bits de se divide en dos mitades de 16 bits . Primero la mitad izquierda de la entrada es AND bit a bit con clave redonda y girado a la izquierda un bit. El resultado de eso es XOR'ed a la mitad derecha de la entrada para obtener la mitad correcta de la salida .
Entonces la mitad derecha de la salida se hace OR bit a bit con la tecla redonda y girado a la izquierda un bit. El resultado de eso es XOR'ed a la mitad izquierda de la entrada para obtener la mitad izquierda de la salida .
La salida de la función es la concatenación de las mitades izquierda y derecha .
Función FO
La entrada x de 32 bits de se divide en dos mitades de 16 bits , 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.
La salida de la función es .
Función FI
La función FI es una red irregular similar a Feistel.
La entrada de 16 bits de la función se divide en dos mitades de los cuales tiene 9 bits de ancho y tiene 7 bits de ancho.
Bits en la mitad izquierda se barajan primero por el cuadro de sustitución de 9 bits ( cuadro S) S9 y el resultado se XOR'ed con la mitad derecha extendida por cero para obtener la nueva mitad derecha de 9 bits .
Pedazos de la mitad derecha se barajan por S-box S7 de 7 bits y el resultado es XOR'ed con los siete bits menos significativos ( LS7 ) de la nueva mitad derecha para obtener la nueva mitad izquierda de 7 bits .
La palabra intermedia se XOR con la tecla redonda KI para obtener de los cuales tiene 7 bits de ancho y tiene 9 bits de ancho.
Bits en la mitad derecha luego se barajan por S-box de 9 bits S9 y el resultado se XOR'ed con la mitad izquierda extendida por cero para obtener la nueva mitad derecha de 9 bits de la salida .
Finalmente los pedacitos de la mitad izquierda se barajan por S-box S7 de 7 bits y el resultado se XOR'ed 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.
La salida es la concatenación de las mitades izquierda y derecha finales .
Cajas de sustitución
Los cuadros de sustitución ( cuadros S) S7 y S9 se definen mediante expresiones AND-XOR bit a bit y tablas de consulta en la especificación. Las expresiones bit a bit están destinadas a la implementación de hardware, pero hoy en día es habitual utilizar las tablas de búsqueda incluso en el diseño de HW.
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 está definido por 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 man-in-the-middle 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ó a finales de 2006. [9]
En 2005, los investigadores israelíes Eli Biham , Orr Dunkelman y Nathan Keller publicaron un ataque de rectángulo de clave relacionada (bumerán) en KASUMI que puede romper las 8 rondas más rápido que una búsqueda exhaustiva. [10] El ataque requiere 2 54,6 textos sin formato elegidos, cada uno de los cuales ha sido cifrado bajo una de las cuatro claves relacionadas, y tiene una complejidad de tiempo 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 fuerza 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 temporales y espaciales del ataque son tan bajas que los autores llevaron a cabo el ataque en dos horas en una computadora de escritorio Intel Core 2 Duo incluso utilizando la implementación de referencia no optimizada de KASUMI. Los autores señalan que este ataque puede no ser aplicable a la forma en que se usa A5 / 3 en 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.
Ver también
- A5 / 1 y A5 / 2
- MISTY1
- NIEVE
Referencias
- ^ "Informe preliminar de SA3 # 38" (PDF) . 3GPP. 2005.
- ^ a b "Informe general sobre el diseño, especificación y evaluación de los algoritmos de integridad y confidencialidad del estándar 3GPP" (PDF) . 3GPP. 2009.
- ^ Matsui, Mitsuru; Tokita, Toshio (diciembre de 2000). "Desarrollo de algoritmos de cifrado MISTY, KASUMI y Camellia" (PDF) . Mitsubishi Electric Advance . Mitsubishi Electric corp. 100 : 2–8. ISSN 1345-3041 . Archivado desde el original (PDF) el 24 de julio de 2008 . Consultado el 6 de enero de 2010 .
- ^ US 7096369 , Matsui, Mitsuru & Toshio Tokita, "Aparato de transformación de datos y método de transformación de datos", publicado el 19 de septiembre de 2002, publicado el 22 de agosto de 2006
- ^ a b Orr Dunkelman; Nathan Keller; Adi Shamir (10 de enero de 2010). "Un ataque en tiempo práctico al criptosistema A5 / 3 utilizado en telefonía GSM de tercera generación" . Cite journal requiere
|journal=
( ayuda ) - ^ "3GPP TS 35.202: Especificación de los algoritmos de confidencialidad e integridad 3GPP; Documento 2: Especificación de Kasumi" . 3GPP. 2009.
- ^ Kühn, Ulrich. Criptoanálisis de MISTY redondo reducido . EUROCRYPT 2001. CiteSeerX 10.1.1.59.7609 .
- ^ Elad Barkan, Eli Biham , Nathan Keller. Criptoanálisis instantáneo de solo texto cifrado de comunicación cifrada GSM (PDF) . CRYPTO 2003. págs. 600–616.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Elad Barkan, Eli Biham , Nathan Keller. "Criptoanálisis instantáneo de sólo texto cifrado de comunicación cifrada GSM por Barkan y Biham of Technion (versión completa)" (PDF) .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ 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.CS1 maint: varios nombres: lista de autores ( enlace )
enlaces externos
- Página de inicio de Nathan Keller