Colección de citas famosas - Colección de consignas - Problemas con el algoritmo de cifrado

Problemas con el algoritmo de cifrado

El nombre completo de MD5 es Message-Digest Algorithm 5 (Algoritmo de resumen de mensajes) Fue desarrollado a principios de la década de 1990 por Ronald L. Rivest del MIT Laboratory for Computer Science y RSA Data Security Inc. Fue aprobado por MD2 y MD3 Desarrollado a partir de MD4. Su función es permitir que la información de gran capacidad se "comprima" en un formato confidencial (es decir, convertir una cadena de bytes de cualquier longitud en un entero grande de cierta longitud) antes de firmar la clave privada con un software de firma digital. Ya sea MD2, MD4 o MD5, todos necesitan obtener una longitud aleatoria de información y generar un resumen de mensaje de 128 bits. Aunque las estructuras de estos algoritmos son más o menos similares, el diseño de MD2 es completamente diferente al de MD4 y MD5. Esto se debe a que MD2 está diseñado y optimizado para máquinas de 8 bits, mientras que MD4 y MD5 están diseñados para computadoras de 32 bits. Las descripciones y el código fuente en lenguaje C de estos tres algoritmos se describen en detalle en Internet RFC 1321 (http://www.ietf.org/rfc/rfc1321.txt), que es el documento más autorizado escrito por Ronald L. Rivest. al IEFT en agosto de 1992.

Van Oorschot y Wiener habían considerado una función Hash de fuerza bruta que buscara colisiones en hashes, y especularon sobre una máquina diseñada específicamente para buscar colisiones MD5 (esta máquina (El costo de fabricación en 1994 fue de aproximadamente $1 millón) y se encontró un promedio de un conflicto cada 24 días. Pero en los 10 años transcurridos entre 1991 y 2001, no hubo ningún MD6 que reemplazara al algoritmo MD5 o un nuevo algoritmo llamado con otro nombre. Podemos ver que esta falla no afectó demasiado la seguridad de MD5. Todo lo anterior no es suficiente para ser un problema para MD5 en aplicaciones prácticas. Además, dado que el uso del algoritmo MD5 no requiere el pago de ninguna tarifa de derechos de autor, en circunstancias normales (no en campos de aplicación de alto secreto). Pero incluso si se aplica en campos de alto secreto, MD5 puede considerarse como un excelente tecnología intermedia), ¿cómo puede MD5? Debe considerarse muy seguro.

Aplicación del algoritmo

Una aplicación típica de MD5 es generar un resumen de mensaje (Message-Digest) para un fragmento de información (Mensaje) para evitar que sea manipulado. Por ejemplo, al descargar muchos programas en UNIX, todos tienen un archivo con el mismo nombre y una extensión de archivo .md5. Por lo general, solo hay una línea de texto en este archivo y la estructura general es la siguiente:

MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461

Esta es la firma digital del archivo tanajiya.tar.gz. MD5 trata el archivo completo como un mensaje de texto grande y genera este resumen de mensaje MD5 único a través de su algoritmo de transformación de cadenas irreversible. Si en el proceso de distribución de este archivo en el futuro, no importa si el contenido del archivo cambia de alguna manera (incluidas modificaciones humanas o errores de transmisión causados ​​por líneas inestables durante el proceso de descarga, etc.), lo descubrirá como Siempre que vuelva a calcular el MD5 de este archivo, el resumen de información es diferente, por lo que puede estar seguro de que acaba de obtener un archivo incorrecto. Si existe una agencia de certificación de terceros, el uso de MD5 también puede evitar el "repudio" del autor del archivo. Esta es la llamada aplicación de firma digital.

MD5 también se utiliza ampliamente en tecnología de cifrado y descifrado. Por ejemplo, en los sistemas UNIX, las contraseñas de los usuarios se cifran mediante MD5 (u otros algoritmos similares) y se almacenan en el sistema de archivos.

Cuando el usuario inicia sesión, el sistema calcula la contraseña ingresada por el usuario en un valor MD5 y luego la compara con el valor MD5 almacenado en el sistema de archivos para determinar si la contraseña ingresada es correcta. A través de tales pasos, el sistema puede determinar la legitimidad del inicio de sesión del usuario en el sistema sin conocer el código claro de la contraseña del usuario. Esto no sólo evita que los usuarios con derechos de administrador del sistema conozcan la contraseña del usuario, sino que también aumenta en cierta medida la dificultad de descifrar la contraseña.

Es por esta razón que uno de los métodos para descifrar contraseñas más utilizados por los piratas informáticos es un método llamado "ejecución de diccionario". Hay dos formas de obtener un diccionario: una es una colección diaria de tablas de cadenas utilizadas como contraseñas y la otra se genera mediante un método de permutación y combinación. Primero, use el programa MD5 para calcular los valores MD5 de estos elementos del diccionario. y luego use los valores MD5 del objetivo que se buscan en este diccionario. Suponemos que la longitud máxima de la contraseña es 8 bytes, y la contraseña solo puede contener letras y números, ***26 26 10 = 62 caracteres, y el número de elementos en el diccionario formado por permutación es P (62, 1 ) P(62, 2)…. P(62, 8), que ya es un número astronómico. Para almacenar este diccionario se requiere una matriz de discos de nivel TB, y este método también tiene un requisito previo, es decir, puede. sólo es posible si se obtiene el valor MD5 de la contraseña de la cuenta de destino. Esta tecnología de cifrado se usa ampliamente en los sistemas UNIX, lo cual es una razón importante por la cual los sistemas UNIX son más robustos que los sistemas operativos generales.

Descripción del algoritmo

Una breve descripción del algoritmo MD5 puede ser la siguiente: MD5 procesa la información de entrada en grupos de 512 bits y cada grupo se divide en 16 subgrupos de 32 bits. Después de una serie de procesamiento, la salida del algoritmo consta de cuatro grupos de 32 bits. Después de concatenar estos cuatro grupos de 32 bits, se generará un valor hash de 128 bits.

En el algoritmo MD5, primero es necesario rellenar la información para que su longitud de bytes sea igual a 448 después del módulo de 512. Por lo tanto, la longitud de bytes (Bits Longitud) de la información se ampliará a N*512 448, es decir, N*64 56 bytes (Bytes), y N es un entero positivo. El método de llenado es el siguiente: complete un 1 e innumerables ceros detrás de la información y deje de completar la información con ceros hasta que se cumplan las condiciones anteriores. Luego, a este resultado se le añade una representación binaria de 64 bits de la longitud de la información previa al relleno. Después de estos dos pasos de procesamiento, la longitud del byte de información actual =N*512 448 64=(N 1)*512, es decir, la longitud es exactamente un múltiplo entero de 512. La razón de esto es cumplir con los requisitos de longitud de la información en el procesamiento posterior.

Hay cuatro parámetros enteros de 32 bits llamados variables de encadenamiento en MD5. Son: A=0x01234567, B=0x89abcdef, C=0xfedcba98, D=0x76543210.

Después de configurar estas cuatro variables de enlace, comienza la operación de bucle de cuatro rondas del algoritmo. El número de ciclos es el número de paquetes de información de 512 bits en el mensaje.

Copie las cuatro variables de enlace anteriores a otras cuatro variables: A a a, B a b, C a c y D a d.

El bucle principal tiene cuatro rondas (MD4 solo tiene tres rondas) y cada bucle es muy similar. Hay 16 operaciones en la primera ronda. Cada operación realiza una operación de función no lineal en tres de a, b, cyd, y luego suma el resultado a una cuarta variable, un subgrupo del texto y una constante. Luego mueve el resultado hacia la derecha un número indefinido y suma uno de a, b, c o d. Finalmente, reemplace uno de a, b, c o d con este resultado.

Las siguientes son las cuatro funciones no lineales utilizadas en cada operación (una para cada ronda).

F(X,Y,Z) =(Xamp;Y)|((~X)amp;Z)

G(X,Y,Z) =(Xamp; Z)|(Yamp; (~Z))

H(X, Y, Z) =X^Y^Z

I(X, Y, Z)=Y^ (X|(~Z))

(amp; es AND, | es OR, ~ no es, ^ es XOR)

Descripción de estas cuatro funciones: si X, The Los bits correspondientes de Y y Z son independientes y uniformes, por lo que cada bit del resultado también debe ser independiente y uniforme. F es una función que opera bit a bit. Es decir, si X, entonces Y, en caso contrario Z. La función H es un operador de paridad bit a bit.

Supongamos que Mj representa el j-ésimo subgrupo del mensaje (de 0 a 15), lt

FF(a, b, c, d, Mj, s, ti) significa a=b ((a (F(b,c,d) Mj ti)lt;lt; GG(a,b,c,d,Mj,s,ti) significa a=b ((a (G (b ,c,d) Mj ti)lt;lt; HH(a,b,c,d,Mj,s,ti) significa a=b ((a (H(b,c,d) Mj ti)lt ;lt ; II(a, b, c, d, Mj, s, ti) significa a=b ((a (I(b, c, d) Mj ti)lt; lt;

Estos cuatro rondas (64 pasos) es:

Primera ronda

FF(a, b, c, d, M0, 7, 0xd76aa478)

FF(d , a, b, c, M1, 12, 0xe8c7b756)

FF (c, d, a, b, M2, 17, 0x242070db)

FF (b, c, d , a, M3, 22, 0xc1bdceee)

FF (a, b, c, d, M4, 7, 0xf57c0faf)

FF (d, a, b, c, M5 , 12, 0x4787c62a)

FF (c, d, a, b, M6, 17, 0xa8304613)

FF (b, c, d, a, M7, 22, 0xfd469501 )

FF(a, b, c, d, M8, 7, 0x698098d8)

FF (d, a, b, c, M9, 12, 0x8b44f7af)

FF(c,d,a,b,M10,17,0xffff5bb1)

FF(b,c,d,a,M11,22,0x895cd7be)

FF (a, b, c, d, M12, 7, 0x6b901122)

FF (d, a, b, c, M13, 12, 0xfd987193)

FF (c, d , a, b, M14, 17, 0xa679438e)

FF (b, c, d, a, M15, 22, 0x49b40821)

Segunda ronda

GG(a, b, c, d, M1, 5, 0xf61e2562)

GG(d, a, b, c, M6, 9, 0xc040b340)

GG(c ,d,a,b,M11,14,0x265e5a51)

GG(b,c,d,a,M0,20,0xe9b6c7aa)

GG(a,b,c ,d,M5,5,0xd62f105d)

GG(d,a,b,c,M10,9,0x02441453)

GG(c,d,a,b,M15 , 14, 0xd8a1e681)

GG(b, c, d, a, M4, 20, 0xe7d3fbc8)

GG(a, b, c, d, M9, 5, 0x21e1cde6 )

GG(d, a, b, c, M14, 9, 0xc33707d6)

GG(c, d, a, b, M3, 14, 0xf4d50d87)

GG(b, c, d, a, M8, 20, 0x455a14ed)

GG(a, b, c

, d, M13, 5, 0xa9e3e905)

GG (d, a, b, c, M2, 9, 0xfcefa3f8)

GG (c, d, a, b, M7 , 14, 0x676f02d9)

GG(b, c, d, a, M12, 20, 0x8d2a4c8a)

Tercera ronda

HH(a, b , c,d,M5,4,0xfffa3942)

HH(d,a,b,c,M8,11,0x8771f681)

HH(c,d,a,b , M11, 16, 0x6d9d6122)

HH (b, c, d, a, M14, 23, 0xfde5380c)

HH (a, b, c, d, M1, 4, 0xa4beea44)

HH(d,a,b,c,M4,11,0x4bdecfa9)

HH(c,d,a,b,M7,16,0xf6bb4b60)

HH(b,c,d,a,M10,23,0xbebfbc70)

HH(a,b,c,d,M13,4,0x289b7ec6)

HH(d, a, b, c, M0, 11, 0xeaa127fa)

HH(c, d, a, b, M3, 16, 0xd4ef3085)

HH( b , c, d, a, M6, 23, 0x04881d05)

HH (a, b, c, d, M9, 4, 0xd9d4d039)

HH (d, a, b , c, M12, 11, 0xe6db99e5)

HH (c, d, a, b, M15, 16, 0x1fa27cf8)

HH (b, c, d, a, M2 , 23, 0xc4ac5665)

Cuarta ronda

II(a, b, c, d, M0, 6, 0xf4292244)

II(d, a, b, c, M7, 10, 0x432aff97)

II (c, d, a, b, M14, 15, 0xab9423a7)

II (b, c, d, a, M5, 21, 0xfc93a039)

II(a, b, c, d, M12, 6, 0x655b59c3)

II(d, a, b, c, M3, 10, 0x8f0ccc92)

II(c, d, a, b, M10, 15, 0xffeff47d)

II(b, c, d, a, M1, 21, 0x85845dd1)

II(a, b, c, d, M8, 6, 0x6fa87e4f)

II(d, a, b, c, M15, 10, 0xfe2ce6e0)

II(c, d, a, b, M6, 15, 0xa3014314)

II (b, c, d, a, M13, 21, 0x4e0811a1)

II (a , b, c, d, M4, 6, 0xf7537e82)

II (d, a, b, c, M11, 10, 0xbd3af235)

II (c, d , a , b, M2, 15, 0x2ad7d2bb)

II (b, c, d, a, M9, 21, 0xeb86d391)

La constante ti se puede seleccionar de la siguiente manera:

p>

En el paso i, ti es la parte entera de 4294967296*abs(sin(i)), y la unidad de i es radianes. (4294967296 es igual a 2 elevado a la 32ª potencia)

Después de completar todo esto, suma a, b, cyd a A, B, C y D respectivamente. Luego continúe ejecutando el algoritmo con el siguiente grupo de datos y el resultado final será la cascada de A, B, C y D.

Después de implementar el algoritmo MD5 de acuerdo con el método que mencioné anteriormente, puede usar la siguiente información para realizar una prueba simple en el programa que creó para ver si hay algún error en el programa.

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661

MD5 ("abc") = 900150983cd24fb 0d6963f7d28 e17f72

MD5 ("resumen del mensaje") = f96b697d7cb7938d525a2f31aaf161d0

MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b

MD5 ("ABCDEFGHIJKLMNOP QRSTUVWXYZabcdefghijk lmnopqrstuvwxyz0123456789") =

d174ab98d277d9f5a5611c2c9f419d9f< /p >

MD5 ("12345678901234567890123456789012345678901234567890123456789

01234567890") = 57edf4a22be3c955ac49da2e2107b

Secur idad de MD5

Mejoras realizadas por MD5 sobre MD4:

1. Se agregó la cuarta ronda;

2. Cada paso tiene una constante de suma única

3. Para debilitar la simetría de la función G en la segunda; ronda, de ( Xamp;Y)|(Xamp;Z)|(Yamp;Z) se convierte en (Xamp;Z)|(Yamp;(~Z));

4. Se agrega el primer paso al paso anterior Como resultado, esto causará un efecto de avalancha más rápido;

5. Cambió el orden de acceso a los subgrupos de mensajes en la segunda y tercera ronda para hacerlos menos similares;

6. Optimicé aproximadamente el desplazamiento cíclico hacia la izquierda en cada ronda para lograr un efecto de avalancha más rápido. El desplazamiento de cada rueda es diferente entre sí.