DEAL – 128 cifra de bit de bloques prefabricados

 

Lars R. Knudsen

El 21 de febrero 1998

 

La traducción con inglés: Kochetkov N.N.

El octubre 1998

 

La anotación

 

Proponemos una nueva cifra de bloques prefabricados, DEAL, fundado en DES (DEA). La dimensión del bloque DEAL – 128 palas, la dimensión de la llave puede ser 128 192 o 256 palas. La cifra, propuesta por nosotros, tiene algunas ventajas ante otros esquemas: agradeciendo большему a la dimensión de los bloques, el problema «los ataques según la cifra-texto recogida» se hace menos esencial, а la velocidad de la cifración corresponde a la velocidad triple DES. Suponemos que más realista (o menos irrealizable) el ataque a cualquier versión DEAL’а es una búsqueda completa de las llaves. Hemos invitado ANSI (el instituto) a incluir DEAL en el estándar ANSI X9.52. Además proponemos DEAL, como el candidato al estándar NIST AES.

 

1 Introducción

DES (o DEA) [15] – la cifra de bloques prefabricados con la dimensión del bloque 64 pala y 64 llave de bit, en que son eficaces 56 palas. Es iterativo 16 цикловой la cifra, en ello la cifra-texto es calculada por medio de la aplicación iterativa цикловой las funciones al texto abierto. DES tiene Fejstelevu así llamado la estructura: en cada ciclo la mitad del bloque es dejada pasar a través de la función no lineal, su salida XOR’ится con otra mitad, después de que las dos mitades se cambian por lugares.

Para las aplicaciones modernas la dimensión de la llave DES se hacía demasiado pequeña. Винер [20] ha mostrado que construir el mecanismo especializado, capaz de hacer la búsqueda completa de la llave DES por término medio todo en 3.5 horas, costará alrededor de 1 millón US $. Además, recientemente era mostrado, así como de los ataques de programa la llave de la dimensión de 56 palas no concede la defensa considerable – la llave DES era encontrada por medio de la búsqueda completa por los medios difundido por Internet’у.

La verdad es que al problema de la dimensión insuficiente de la llave indicaban ya casi justamente después de la publicación DES [6]. Por eso, a menudo DES se usa por el esquema triple de la cifración llamada triple DES’ом (Triple-DES), donde el texto abierto es cifrado tres veces sobre tres llaves independientes. En otra variante llamada dosclave triple DES’ом, el texto abierto es cifrado al principio por la llave К1, luego es descifrado por la llave К2 y, al fin, es cifrado de nuevo por la llave К1 [18]. Sin embargo, la dimensión del bloque en 64 pala hace estos esquemas vulnerable al ataque según la cifra-texto recogida, que es fundada en aquel hecho que para большего 2³³ bloques son posibles esperar el número de los regímenes del trabajo con DES [16] después de зашифрования los bloques iguales de la cifra-texto, esto da la filtración de información sobre el texto abierto [5, 9, 13]. ¿Además, triple DES con tres llaves independientes es vulnerable al ataque por la llave [7] dependiente (?), que tiempo de la ejecución alrededor de mismo, como el tiempo de la búsqueda completa de la llave en simple DES.

La comisión X9.F.1 del Instituto Nacional Americano de los Estándares (ANSI) trabaja sobre la aceptación del juego de los regímenes de la cifración DES triple [21]. Un de estos regímenes – con la realimentación según la cifra-texto (Triple DES Cipher Block Chaining – TCBC), donde el bloque para la realimentación es el bloque de la cifra-texto después de 3 зашифрований, – se llama también exterior (outer-) CBC en el régimen. Sin embargo, este régimen es vulnerable al ataque según la cifra-texto recogida. Por eso, es invitado a usar triple DES en el régimen con la realimentación según la cifra-texto con la interacción, se llama también interior (inner-) CBC en el régimen, donde la realimentación se realiza después de cada uno зашифрования único DES’ом. Aunque este régimen es menos vulnerable al ataque según la cifra-texto recogida, el ataque eficaz por la apertura de la llave puede ser pasado en tiempo mucho menor, que se podría esperar para el esquema con la cifración triple [1].

Coupersmith, Jonson y Matyas [5, 4] proponen para triple DES’а el régimen CBC con OFB Masking (CBCM). Wagner [5] ha pasado криптоанализ de la proposición que precedía la elaboración dada, donde cada uno dos cantidades iniciales puede aceptar solamente 2²⁰ significados. El régimen CBCM no es vulnerable al ataque según la cifra-texto recogida, y el nivel de la seguridad se supone 2⁸⁰. La incomodidad del esquema propuesto que para зашифрования del bloque del texto abierto de la dimensión 64 pala se usa 4 зашифрования DES sobre tres llaves distintas. Antes Biham y Knudsen han mostrado que DES en el régimen CBCM es vulnerable al ataque según la cifra-texto escogida, en que se usan 2⁶⁵ bloques de la cifra-texto escogida y que complicación por el tiempo – 2⁵⁸ [2].

Proponemos r-tsiklovoj Fejstelev la cifra que usa DES en la cualidad цикловой las funciones. Resulta en resultado la cifra con la dimensión del bloque de 128 palas y r · por 64 palas цикловых de las llaves recibidas por el algoritmo del horario de las llaves. El horario de las llaves es elaborado así que la dimensión de la llave puede aceptar un de tres significados distintos: 128 192 o 256 palas. Recomendamos poner a primero dos dimensiones de la llave r = 6, а a la dimensión de la llave de 256 palas r = 8. Más abajo explicaremos, por qué recomendamos r ≥ 6. Si las palas de la comprobación четности cada uno байта de la llave no se usan a la cifración, como esto pasa en DES, las dimensiones activas de las llaves se disminuyen hasta 112, 168 y 224 palas respectivamente. La búsqueda completa de la llave es completamente imposible todavía (cm., por ejemplo, la discusión de las dimensiones de las llaves en [3]). Además, el ataque exitoso según la cifra-texto recogida tiene que introducir aproximadamente 2⁶⁴ bloques de la cifra-texto. La velocidad de la cifra, propuesta por nosotros, mismo, como a triple DES’а, si usar 6 зашифрований para el cierre de dos bloques del texto abierto por 64 pala, además, se puede aplicarlo con el uso de los medios DES existentes.

El Instituto nacional de los Estándares y la Tecnología (NIST) recientemente ha declarado la intención de estandartizar un nuevo algoritmo de la cifración, Advanced Encryption Standart, como la sustitución DES [14]. La declaración NIST de lo que antes de que AES será preparado, pasará algunos años y que tienen intención de reconocer «el DES-algoritmo Triple, la vez él es aceptada por el estándar ANSI» [14], hace la iniciativa ANSI hasta más importante.

 

2 DEAL

DEAL (Data Encryption Algorithm with Larger blocks – el Algoritmo de la Cifración de los Datos con los bloques Engrandecidos) es 128 cifra de bit de bloques prefabricados con las dimensiones de la llave 128, 192 y 256 palas que más se dejará ver aquí DEAL-128, DEAL-192 y DEAL-256 respectivamente. Todas las versiones pueden usarse en cualquier de cuatro regímenes DES’a estandartizados [16]. Comenzaremos de la descripción del trabajo DEAL en el régimen ECB. Que con = EVA () significa cifrado DES el significado 64 de bit А sobre la llave En, y que Y = ЕA_Z (X) significa зашифрование DEAL 128 de bit X sobre la llave Z. El texto Р abierto se divide en los bloques P_i por 128 palas cada uno, P = P₁, P₂, …, P_n. El horario de las llaves acepta la llave A y devuelve r de las llaves DES RK_i, donde i = 1, …, r, como es descrito más abajo. Designaremos X^L y X^R izquierdo y derecho se precipita Х respectivamente. La Cifra-texto es calculada del modo siguiente. Pondremos, y calcularemos para j = 1, …, r

	(1)
.	(2)

Pondremos. En fig. 1 es mostrado un ciclo DEAL. Para DEAL-128 y DEAL-192 invitamos a usar 6 ciclos, e.d. r = 6. Sin embargo, como veremos más abajo, de esto puede ser insuficientemente para DEAL-256, es invitado a usar aquí 8 ciclos, r = 8. Parece que la versión con la dimensión de la llave de 256 palas se usa solamente cuando es necesario especialmente fuerte зашифрование.

Notaremos que el último ciclo DEAL de la mitad del bloque se cambian en algunas partes. La causa en lo siguiente: la parte derecha de la cifra-texto С_i no es cifrada en el último ciclo i зашифрования, y solamente la parte izquierda de la entrada i + 1 зашифрования (que es igual) es cifrada sobre el último ciclo. Т la isla la parte C_i derecha se quedaría no recifrado dos ciclos. Esto puede dar la esfera de actividad a los malhechores, además, que la cifra consiste de todo de 6 o 8 ciclos. Notaremos que la propiedad análoga es y a DES en el régimen CBC. Sería propio La verdad es que esto más difícil usar, ya que a DES 16 ciclos. Se permitiremos notar que el cambio para lugares de las partes derechas e izquierdas sobre el último ciclo no influye sobre la firmeza de la cifra de bloques prefabricados en el régimen ECB.

El trabajo del régimen CBC es descrito más detalladamente en [16]. Así, designaremos los bloques del texto abierto por 128 palas P₁, P₂, …, P_n y С₁, С₂, …, С_n – los bloques, correspondientes a ellos, de la cifra-texto. Entonces:

,

Donde С₀ – el significado inicial.

En DES el traslado IP inicial primero se aplica al texto abierto, y análogamente ante la salida la cifra-texto es dejada pasar a través de vuelta a ella IP^-1. Es posible aumentar la velocidad DEAL, si arreglar de usado DES estos los traslados iniciales y finales. Es fácil mostrar que para la recepción de la realización DEAL’а IP correcta debe ser aplicada a las dos partes del texto abierto ante зашифрованием, а IP^-1 – a las dos partes de la cifra-texto.

A la entrada del horario de las llaves se aparta s de las llaves DES, К₁, …, K_s, para s = 2, 3, 4, cada uno por 64 palas (incluyendo 8 palas de comprobación mayores de las palas cada байта), a la salida resulta r de las llaves DES, RК_i. Usamos el método general, приложимый a todas tres dimensiones de la llave. Extendemos En primer lugar s de las llaves hasta r de las llaves, por medio de la repetición y XOR’ения con una nueva constante para cada nueva repetición. Ciframos la lista extendida de las llaves DES’ом en el régimen CBC con la llave fijada y el significado de cero inicial. De los bloques recibidos de la cifra-texto se forman conecta RK_i. Más llevamos las definiciones exactas cada uno los horarios de las llaves, aquí A = 0х1234 5678 90ab cdef_x (el número hexadecimal) – la llave DES fijada.

En DEAL-128 conecta son generados del modo siguiente:

,

,

,

,

,

,

Donde – 64 número de bit entero, en que i – las 1 palas (la indexación va con 0) es establecido, а otro son limpiados. Por ejemplo, puede ser presentado como hexadecimal “0х8000 0000 0000 0000_х”.

 

En DEAL-192 conecta son generados del modo siguiente:

,

,

,

,

,

.

Estas versiones del horario de las llaves exigen 6 horarios de las llaves DES y 6 зашифрований DES sobre la llave fijada. Conecta es necesario generar sólo una vez, si de ellos posteriormente conservar.

 

En DEAL-256 conecta son generados del modo siguiente:

,

,

,

,

,

,

,

.

Esta versión del horario de las llaves exige 8 horarios de las llaves DES y 8 зашифрований DES sobre la llave fijada. Conecta es necesario generar sólo una vez, si de ellos posteriormente conservar.

 

Notaremos que para todas las versiones del horario de las llaves de 64 cantidades RK_i de bit se usan como las llaves DES, por eso las palas de la comprobación четности RK_i no se usan en el i ciclo. Sin embargo, todo 64 pala RK_i, como la salida de la cifración sobre la llave A, se usan a la generación de lo siguiente подключа.

¿Los principios de la elaboración del horario de las llaves consisten, en primer lugar, que conecte dependían del número más grande битов de la llave básica, pero no exigían además muchos trabajos, en segundo lugar, a la introducción s de las llaves básicas de la dimensión por 64 palas, cualesquiera s consecutivo подключей deben tener энтропию s ∙ 56 palas, y no deben ser, al fin, las llaves dependientes y débiles y no debe quedarse la propiedad de la complementariedad (?). Notaremos que los últimos dos problemas asisten y en DES, y – todo tres – en triple DES. Hemos notado que si las llaves básicas de la dimensión por 64 pala cada uno, puede encontrarse un par de las llaves que generan las multitudes iguales подключей. Sin embargo, el número de tales llaves es tanto pequeño al parecer que no presenta la amenaza DEAL’у, aplicado para la cifración.

Los desplazamientos son introducidos para la prevención de la aparición de las llaves débiles. Si no eran, había unas llaves, para que todo conecta eran iguales. Por ejemplo, para DEAL-128 las llaves K₁ = K₂ = D_K (0) generarían 6 подключей con el significado 0. Los desplazamientos y la cifración sobre la llave fijada previenen la aparición de las llaves débiles y dependientes y la propiedad de la complementariedad.

Notaremos que si las palas de la comprobación четности se usa en cada uno байте de la llave básica, las dimensiones activas de las llaves propuestas componen 112 168 y 224 palas, respectivamente.

La estructura DEAL arriba descrita podría ser y otro – es algunas variantes posibles. En vez de Fejstelevoj de la estructura es posible usar la estructura MISTY por primera vez descrita en [12], ella permite en gran medida распараллелить los cálculos (en la realización dura). Sin embargo, esta estructura es elaborada mucho más tarde y todavía no es analizada tan profundamente. Otra variante – usar DEAL en el régimen «DES-X» [8], en que la llave XOR’ится adicional con el texto abierto y con la cifra-texto. O, en vez del uso DES, como цикловой las funciones, es posible usar DES-X. La falta de últimas dos proposiciones de lo que será necesario generar большее el número подключей, y, por consiguiente, el horario de las llaves DEAL se hace más difícil.

 

2.1 Firmeza DEAL’а

¿Que es posible decir en la firmeza DEAL’а en total? Ante todo, notaremos que para DEAL el ataque simple meet-in-the-middle (encontrar por el medio), análogo a tal ataque en doble DES [6, 19], encontrará las llaves durante el orden 2¹⁶⁸ зашифрований para seis y 2²²⁴ зашифрований para ocho ciclos DEAL respectivamente, independientemente del horario de las llaves. Precisamente por eso, es invitado a hacer por lo menos 8 ciclos зашифрования. Para DEAL-128 la búsqueda completa de la llave ocupará el tiempo aproximadamente 2¹¹² зашифрований.

Patarin en [17] ha mostrado que para distinguir 5 o 6 цикловой Fejstelev n-de bit la cifra con casual цикловой por la función del traslado en realidad casual 2n-de bit, es necesario saber por lo menos 2^{2n / de 3} textos abiertos y las cifras-textos, correspondientes a ellos. Más él supone que es necesario 2^{n el} vapor. Si contar que DES modela el traslado [1] casual, esto, por la suposición Patarin’а, es necesario aproximadamente 2⁶⁴ зашифрований para distinguir DEAL del traslado casual; es tal la complicación del ataque según la cifra-texto recogida. Más rápido de los ataques conocidos por la posición de la llave en DEAL (con seis ciclos), que reconocemos, – el ataque general en 6 цикловые Fejstelevy las cifras [10], en la aplicación a DEAL, exige aproximadamente 2¹²¹ зашифрований DES, usando aproximadamente 2⁷⁰ textos escogidos abiertos, para cualquier horario de las llaves. Determinaremos en lo sucesivo la diferencia entre dos consecuencias de las palas, como побитное XOR.

La afirmación 1: Hay un ataque en шестицикловый DEAL con independientes цикловыми por las llaves, que exige aproximadamente 2¹²¹ зашифрований DES, usando aproximadamente 2⁷⁰ textos escogidos abiertos.

La prueba: Examinaremos 5 цикловую la versión y un par de los textos abiertos con la diferencia α ≠ 0 en las partes derechas y las partes iguales izquierdas. Supondremos que las cifras-textos después de 5 ciclos tienen la diferencia α en las partes izquierdas y las partes iguales derechas. Esto significa que en los dos зашифрованиях a las entradas DES (en цикловой las funciones DEAL) eran los significados iguales en primero y sobre los quintos ciclos. Más, la diferencia a las entradas DES en segundo y sobre los cuartos ciclos era α. Pero debe de aquí que las salidas DES en el tercer ciclo son iguales, así que, y las entradas DES sobre el tercer ciclo son iguales también. Esto conduce a la contradicción, porque. Esto significa que las salidas DES en segundo y sobre los cuartos ciclos son iguales que es imposible, porque. Hemos supuesto que no son igual. Así la suposición que la diferencia entre las cifras-textos después de 5 ciclos es igual α en izquierdo y 0 en las partes derechas, no justo. Con otras palabras, hemos determinado 5 цикловой el diferencial con la probabilidad de cero. Esto puede ser usado para el ataque en DEAL.

El ataque pasa del modo siguiente. Escogeremos 2⁶⁴ textos abiertos con las partes fijadas izquierdas y distintas derechas, los designaremos _a i = 1, …, 2⁶⁴. Designaremos las cifras-textos, correspondientes a ellos. Calcularemos y encontraremos las coincidencias a i  ≠ j. Se Puede esperar aproximadamente tales 2⁶³ coincidencias:. Pondremos. Para todos tales pares que coinciden y para todos los significados de la llave en el sexto ciclo descifraremos un ciclo de las cifras-textos. Si las diferencias después de 5 ciclos son iguales α y 0, el significado supuesto de la llave no justo. Notaremos que al significado correcto de la llave tales diferencias después de 5 ciclos no pueden aparecer, pero a incorrecto aparecerán con la probabilidad 2^-64 para cada pareja analizada. Así con 2⁶³ vapores aproximadamente la mitad de las llaves serán arrojados. Con la repetición del ataque de 56 veces habrá posible solamente pocos significados de la llave en el sexto ciclo. En general, el ataque exige 56 ∙ 2⁶⁴ ≈ 2⁷⁰ textos escogidos abiertos, (2⁵⁶ + 2⁵⁵ + 2⁵⁴ + … + 2 + 1) ∙ 2⁶⁴ ≈ 2⁵⁷ ∙ 2⁶⁴ = 2¹²¹ зашифрований DES y 2⁶⁴ palabras ярь =Ю.бббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббббб □

El ataque arriba descrito aplicado a DEAL-192 es más rápido, que la búsqueda completa de la llave, aunque las premisas muy irrealizable. Si que ataca consigue encontrar 2⁶⁴ o más vapores abierto y las cifras-textos, puede entrar en el juego el ataque según la cifra-texto recogida, y en cualquier caso será necesaria la cifra con la dimensión grande del bloque. El ataque más estudiado en DEAL-128 – la búsqueda completa de la llave – exige el tiempo aproximadamente 2¹¹² зашифрований. No hemos encontrado el ataque en DEAL con восемью por los ciclos mejor, que la búsqueda arriba descrita completa de la llave «meet-in-the-middle». Hay Puede ser, unos ataques más rápidos, por ejemplo, la generalización acertada del ataque antes citado a 6 ciclos, pero tal plan del ataque exigirán la cantidad irreal de los textos escogidos abiertos y la capacidad de almacenaje irreal.

El ataque a 6 ciclos explica nuestras recomendaciones – usar para DEAL r ≥ 6. A r ≤ 5 es posible indicar los diferenciales con la probabilidad de cero. Esto significa que para algunos las diferencias en los vapores del texto abierto, algunas otras diferencias son imposibles en los vapores correspondientes de la cifra-texto. Ante todo, tal propiedad no existe cerca de algunas cifras modernas de bloques prefabricados, después, tales diferenciales pueden ser usados en los ataques por la apertura de la llave con la complicación aproximadamente 2⁸⁸ para DEAL solamente con 5-ю por los ciclos [10]. (Notaremos que tal ataque – solamente el límite superior del nivel de la seguridad).

A finales de esta sección sacaremos el total a los rasgos DEAL.

·         DEAL tiene la dimensión del bloque de 128 palas y la dimensión de la llave 128, 192 o 256 palas (la dimensión activa, respectivamente, – 112 168 o 224 pala,).

· el         Ataque según la cifra-texto recogida exige aproximadamente 2⁶⁴ bloques de la cifra-texto.

·         no Hay ataques conocidos, probables.

·         DEAL con seis ciclos tiene la velocidad análoga a la velocidad triple DES.

·         DEAL puede usarse en los regímenes estandartizados del trabajo.

·         DEAL puede ser realizado en que hay duro y de programa el mantenimiento DES.

·         no Hay llaves débiles y es eliminada la propiedad de la complementariedad.

Al fin, se permitiremos notar que en vista del horario bastante difícil de las llaves, DEAL usar no prácticamente en las funciones casuales.

 

3 Conclusión

Hemos descrito la cifra de bloques prefabricados, DEAL, con la dimensión del bloque de 128 palas y la dimensión de la llave 128, 192 o 256 palas, como la alternativa a los regímenes existentes triples de la cifración. DEAL puede usarse en todo de cuatro, elaborado para DES, los regímenes estandartizados de la cifración. Para primero dos dimensiones de la llave el esquema cifra dos bloques por 64 pala, usando seis зашифрований DES, así su productividad es igual a la productividad triple DES. La productividad DEAL con восемью por los ciclos (y la dimensión de la llave de 256 palas) es igual DES en el régimen CBCM. Gracias a las dimensiones grandes del bloque y la llave, la búsqueda completa de la llave y el ataque según la cifra-texto recogida son irrealizables. Además, son evitados los puntos flacos DES y triple DES. No hay llaves débiles, no se quedó las propiedades de la complementariedad, y el éxito de los ataques por la llave dependiente es muy poco probable. Recomendábamos ANSI aceptar DEAL, como la parte [21]. Además, proponemos DEAL, como el candidato posible en Advanced Encryption Standard [14].

 

4 Agradecimientos

El autor es agradecido Don Coupersmith’y, Bart Preneel’y, Vincent Rijmen’y y Matthew Robshaw’y por la multitud de comentarios considerables.

 

Las referencias

Véase el original del artículo en inglés, la sección References.