Blowfish es un codificador de bloques simétricos, diseñado por Bruce Schneier en 1993 e incluido en un gran número de conjuntos de codificadores y productos de cifrado. No se han encontrado técnicas de criptoanálisis efectivas contra el blowfish. Sin embargo, se ha dado más atención de la decodificación de bloques con bloques más grandes, como AES y Twofish .- ............................:http://es.wikipedia.org/w/index.php?title=Especial:Libro&bookcmd=download&collection_id=9fdf28a6cd056a4496b2cb9acf7d3c4cd9cf0356&writer=rdf2latex&return_to=Blowfish
BLOWFISH
Blowfish es un bloque de cifrado de clave simétrica desarrollado por Bruce Schneier, autor del famoso libro Applied Cryptography. Este algoritmo utiliza diversas técnicas que incluyen la red de Feistel, las funciones S-box-dependiente teclas F y no reversibles, por lo que es tal vez el algoritmo más seguro actualmente disponibles. Las claves utilizadas varían en tamaño hasta un máx. de 448 bits y los bloques se utilizan para el cifrado de 64 bits. Usted no sabe en el momento de técnicas de ataque le sea aplicable. E 'considerado uno de los algoritmos de cifrado de bloque más rápido (que es más rápido que DES e IDEA) . Blowfish no está patentado y es de dominio público.
El procedimiento consta de dos fases: una fase de expansión de la llave y una etapa de cifrado de los datos.
La clave de expansión convierte una clave de a lo sumo 448 bits en una matriz de subclaves para un total de 4168 bytes.
El cifrado de datos se realiza a través de 16 rondas. Cada Raund consiste en una permutación dependiente de la clave y un empleado de la sustitución de claves a partir de datos obtenidos mediante Blowfish mismo.
Se usan las únicas operaciones XOR, las cantidades de palabras de 32 bits y cuatro lecturas por ronda en arrays indexados datos.
A partir de la clave simétrica se derivan P-Array con 18 subclaves de 32 bits (P1, P2, ..., P18) y 4 cajas-S cada uno formado por 256 subclaves de 32 bits.
Las subclaves se calculan utilizando el siguiente procedimiento:
1. Inicialice primero el P-array y, a partir de entonces, las cuatro cajas-S con una cadena fija.
2. Pregunta al XOR entre P1 y los primeros 32 bits de la clave, entonces el XOR entre P2 y los siguientes 32 bits de la clave, y así sucesivamente para todos los bits de la clave (posiblemente hasta P14 como la clave simétrica es largo en la mayoría 448 = 14 * 32 bits).Repetir el ciclo hasta que haya ejecutado el XOR de la totalidad de P-array con los bits de la clave.
3. codifican una cadena de todos 0 con el algoritmo Blowfish, utilizando la P-array obtenido en el paso 2) y el inzializzate S-Box en el paso 1).
4. Reemplazar P1 y P2 con la salida de la etapa 3) (64-bit de salida = 2 * 32-bit).
5. Codificar salida del paso 3) utilizando el algoritmo Blowfish con las subclaves modificados.
6. Reemplazar P3 y P4 con la salida de la etapa 5).
7. Continuar el proceso mediante la sustitución de todos los ingresos de la P-array y, posteriormente, la totalidad de los ingresos de las cuatro cajas-S.
Desde cada iteración genera dos subclaves, se requieren 521 iteraciones para generar todas las subclaves (18/2 iteraciones para generar la matriz-P y 256/2 iteraciones para cada uno de los cuatro S-box).
Blowfish es una red de Feistel que consta de 16 rondas (ver Figura 1).
La entrada es un bloque de 64 bits denotado por x.
X dividido en dos bloques de 32 bits cada uno (XL y XR)
Para i = 1 a 15
xL = xL xor P i
xR = F (XL) xR xor
Intercambiar xL y xR
xL = xL xor P 16
xR = F (XL) xR xor
xR = xR xor P 17
xL = xL xor P 18
Bloquear traducido = (XL xR)
Función F (ver figura 2):
· Divida xL en cuatro bloques de 8 bits: a, b, cyd
· F (XL) = ((S1 (a) + S2 (b)) xor S3 (c)) + S4 (d) (donde + es la adición de módulo 2 32 )
La función de decodificación de la misma manera con la excepción de la orden de codificación en el que se usan las subclaves P1, P2, ..., P18, que se invierte.
Aunque hay una fase de inicialización muy complejo (la construcción de la P-matriz y las cajas-S que todavía pueden ser precomputata), las fases de codificación y decodificación de datos están muy rápido como se muestra en el siguiente esquema que compara el Blowfish con algunos de los sistemas de cifrado de clave simétrica mejor conocidos y utilizados.
Como se ha dicho, el Blowfish es un algoritmo de cifrado simétrico con una longitud variable clave (max 448 bits). Consideremos, por ejemplo, una clave de 64 bits que implica 2 64 1844674407 * 10 = 19 combinaciones posibles. Supongamos que tenemos un equipo capaz de procesar 1.000.000 combinaciones por segundo, tardaría 300.000 años para probar todas las combinaciones posibles. La posibilidad de utilizar también las teclas de mayor longitud, hace que el Blowfish muy seguro hacia ataques de "fuerza bruta", incluso si son realizadas por diferentes equipos al mismo tiempo.
The Blowfish fue presentada por primera vez por B. Schneier en las páginas de la famosa revista del Dr. Dobb en 1994. La misma revista también patrocinó un concurso de criptoanálisis ($ 1,000 premio para el ganador) completado en abril de 1995. En este contexto Jon Kelsey ha desarrollado un ataque que puede romper una versión de Blowfish que funciona con sólo tres rondas, pero no logró extender este ataque para completar Blowfish. Vikramijit Singh Chhabra ha creado una máquina que puede hacer eficiente la búsqueda a través de un ataque de tipo llave "fuerza bruta", pero sin resaltar los riesgos reales para el algoritmo. Los resultados más interesantes se han obtenido por Serge Vaundenay que, además de definir los ataques a versiones modificadas del Blowfish, se ha demostrado la presencia de claves débiles en el algoritmo.
En esta sección, se supone que el atacante conoce la parte de la clave privada que se describe la función F, es decir, vamos a suponer que el atacante conoce todos los ingresos de la S-Box, pero no las teclas P 1 , P 2 , ..., P 18.
A "débil" (clave débil) es una tecla a la que al menos uno de los cuatro S-Box generado, por ejemplo, S 1 , tiene al menos una colisión. Esto significa que para S 1 hay dos bytes diferentes, A y A ', tal que S 1 (a) = S 1 (a '). Son P 1 , P 2 , ..., P 18 subclaves generadas por una clave débil y tanto δ el XOR de la colisión para S 1 que es, tanto δ = un xor a '. Para un S-box en cualquiera de la probabilidad de que no hay colisiones es:
Por lo tanto, la probabilidad de que hay al menos una colisión para al menos uno de los 4 cajas S es 2 -15 . Esto significa que, en promedio, hay una clave débil cada 2 15 llaves. Tenga en cuenta la siguiente figura, que prevé una colisión a S 1 :
( δ es un valor de 8 bits y [ δ000 ] es un valor A32-bit)
Suponiendo una sola colisión para S 1 , con la diferencia de δ , la probabilidad de ocurrencia de este resultado es 2 -7 . Considere entonces la figura siguiente (en el que el proceso anterior se repite tres veces conseguir Blowfish ocho rondas):
([ xyzt ] representa un valor indeterminado])
Siempre suponiendo una sola colisión para S 1 , con la diferencia de δ , la probabilidad de ocurrencia de este resultado es 2 -21 ( 2 -7 * 2 -7 * 2 -7). Así, tratando 2 21 pares elegidos PLAINTEX con xor [ 0000δ000 ], es fácil encontrar un par de texto cifrado (C, C ') con xor [ δ000xyzt ].
Sea C = (L, R). Tenemos: F (L xor P 10 ) xor F (L xor P 10 xor [ δ000 ]) = [ xyzt ].
Tratar todos los 2 32 combinaciones posibles que puede calcular el valor de P 10 que verifica la ecuación anterior. Es fácil demostrar que el Blowfish con t subclave redonda y P t + 2 es equivalente a la Blowfish conocido con t-1 ronda. En la práctica, por lo tanto, este ataque permite al atacante para reducir el número de rondas de 8 a 7. Más en general, para la Blowfish con t ronda que utiliza una clave débil, es posible calcular Pt + 2 tratando 2 7 * es T-2/2 ù pares elegido PLAINTEX.
Un par de texto cifrado aleatoria tiene xor = [ δ000xyzt ] con probabilidad 2 -32 . Para estar seguro de que el resultado sea válido, es conveniente consultar con varios pares de texto cifrado con el xor. E 'posible para demostrar que con t menos de 11 un solo par es suficiente para garantizar, con una buena probabilidad de que el resultado es correcto. Por el contrario, con t mayor que o igual a 11, se puede encontrar sobre 2 7 * es t-2.22 3 - ù pares de texto cifrado con xor = [ δ000xyzt ] que conduzcan a un resultado incorrecto para P t + 2 . Por esta razón, cuando t es mayor que o igual a 11 necesario para encontrar al menos tres pares de texto cifrado que dan el mismo resultado, lo que implica que se debe a tientas en promedio con 3 * 2 7 * está t-2/2 ù pares de PLAINTEX elegido con xor = [ 0000δ000 ].
Después de descubrir la subclave P t + 2 pueden atacar la tecla P t + 1 con el mismo método en el Blowfish con t-1 ronda. El uso de este método de forma iterativa podemos volver a todos los t + 2 subclaves. Porque, si t es par, la complejidad del ataque a t ronda es el mismo que t-1 ronda, en busca de todas las subclaves requiere 3 * 2 * 2 + 7 se t-2/2 ù pares elegido PLAINTEX . Para t = 16, este valor es 3 * 2 51 . Para t = 8, desde el 8 de <11 ataque="" de="" el="" elegido="" es="" este="" mero="" n="" nbsp="" para="" plaintex="" requerido="" span="">2 23 .
En este caso, la clave privada es una clave para cualquiera y no necesariamente una "clave débil". La función de (a, b) en S 1 (a) + S 2 (b) es una expansión de 16 a 32 bits que pueden conducir a una colisión S 1 (a) + S 2 (b) = S 1 (en ') + S 2 (b ') con probabilidad relativamente alta. Tanto δ = a xor a ', μ = b xor b 'y consideran, como antes, la siguiente figura:
( δ y μ son valores de 8 bits y [ δ μ 00 ] es un valor A32-bit)
Suponiendo una sola colisión para S 1 + S 2 , con la diferencia μ δ , la probabilidad de ocurrencia de este resultado es 2 -15 . Considere entonces la figura siguiente (en el que el proceso anterior se repite tres veces conseguir Blowfish ocho rondas):
([ xyzt ] representa un valor indeterminado])
Siempre suponiendo una sola colisión para S 1 + S 2 , la probabilidad de ocurrencia de este resultado es 2 -45 ( 2 -15 * 2 -15 * 2 -15 ). Así que el número de PLAINTEX elegido requerida para atacar P 10 es 2 46 (queremos dos pares de texto cifrado con xor = [ δ000xyzt ] para que pueda comprobar los resultados obtenidos con la primera pareja) y dos de 48 pares para todas las subclaves. Para Blowfish con más de ocho rondas de este ataque es imposible porque le obliga a probar demasiados PLAINTEX elegido.
Sin asumir que las cajas-S se conocen, sólo se puede averiguar si la clave utilizada es una clave débil o no (no se puede volver a la serie P, la caja de S o la propia llave). Vamos a ver cómo se puede distinguir una clave débil usando un ataque PLAINTEX elegido. Consideremos, por ejemplo, una colisión de S 1 utilizando la segunda figura de la sección 1.A.
Elegir al azar los bytes B 1 , B 2 , B 3 , B 4 , B 6 , B 7 y B 8 (no B 5 a continuación), en la matriz M B de todos los 2 8 combinaciones posibles de [ B 1, B 2 , B 3 , B 4 , B 5 , B 6 , B 7 , B 8 ], tenemos dos 7 pares con buena xor (es decir, 2 7 parejas con xor igual a [ 0000δ000 ] donde δ es el valor de cualquier colisión S 1 ). Sea M C la matriz del texto cifrado correspondiente [ C 1 , C 2 , C 3 , C 4 , C 5 , C 6 , C 7 , C 8 ].
Spreader es demostrar que en cada þ valor buna par = [ (B 5 xor C 5 ), C 6 , C 7 , C 8 ] es el mismo para ambos mensajes de torque en el que, para una buena par significa el par ( B i , B j ) tal que B i O exclusiva B j = [ 0000δ000 ] y el texto cifrado correspondiente tienen igual xor = [δ000xyzt ].
Así que para encontrar un buen par, acabamos de ver si estamos en la matriz de los pares para los que existe una colisión de la þ valor. Si no hay buenos pares, es decir, si no hay colisiones para cualquiera de las cuatro cajas S, la probabilidad de tener una colisión para þ es muy bajo (aproximadamente 2 -17 ).
Con 2 14 matrices hay una alta probabilidad de encontrar un buen par, siempre que haya al menos una colisión para al menos uno de la caja S.Así que con 2 22 elegido PLAINTEX ( 2 14 matrices con 2 8 elegido PLAINTEX cada uno) podemos, con toda probabilidad, para averiguar si hay colisiones de la caja S, es decir, para saber si la clave utilizada es una clave débil. El mismo ataque, sin embargo, no es factible, ya que requeriría el Blowfish completar un gran número de PLAINTEX elegido.
Hemos demostrado que es posible aplicar el análisis a la Blowfish diferencial en un número limitado de rondas, o asumiendo el conocimiento de la clave privada que describe la función F. Hemos estudiado los S-cajas que tienen colisión destacando la presencia de claves débiles en 'algoritmo que disminuir la complejidad de los ataques (de 2 48 a 2 23 a 8 rondas F cuando se conoce). También hemos demostrado un sistema para detectar una clave débil con 2 22 PLAINTEX elegido (en Blowfish con 8 rondas).
No hay comentarios:
Publicar un comentario