MD2

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de diciembre de 2016; las comprobaciones requieren 10 ediciones .

MD2
Creado	1989 _
publicado	abril de 1992 _
Sucesor	MD4
tamaño de hash	128 bits
Número de rondas	Dieciocho
Tipo de	función hash

MD2 (The MD2 Message Digest Algorithm) es una función hash criptográfica desarrollada por Ronald Rivest (RSA Laboratories) en 1989 y descrita en RFC 1319 . El mensaje de entrada tiene una longitud arbitraria. El tamaño del hash es de 128 bits. Por el momento, el algoritmo MD2 se considera obsoleto, y el RFC 1319 correspondiente se ha trasladado a estado histórico.

Historia

Ronald Rivest desarrolló una serie de algoritmos hash llamados MDx, donde x es el número del algoritmo hash.

MD1 es un algoritmo propietario cuya especificación no ha sido publicada.

MD2 se desarrolló en 1989 para su uso como uno de los algoritmos criptográficos incluidos en el estándar de correo electrónico seguro PEM (Privacy-Enhanced Mail) ; [1] su implementación en C se dio en RFC 1115 [2] . Y en 1990, se propuso MD2 como reemplazo de BMAC (MAC bidireccional) [3] . Posteriormente, la especificación y la implementación actualizada de MD2 se publicaron en RFC 1319 [4] .

MD3 nunca ha sido publicado. Parece que se ha abandonado el desarrollo de MD3 [1] . Después de MD2, MD4 , MD5 y MD6 se desarrollaron en 1990, 1991 y 2008 respectivamente.

En 2011, MD2 fue dado de baja oficialmente debido a numerosos criptoataques exitosos. El uso de MD2 ahora se recomienda solo por compatibilidad con programas más antiguos que aún dependen de él [5] .

Algoritmo MD2

Se supone que la entrada es un mensaje que consta de bytes, cuyo hash tenemos que calcular. Aquí hay un número entero no negativo arbitrario ; puede ser cero o arbitrariamente grande. Escribimos el mensaje byte a byte, de la forma: $b$ $b$

m_0 m_1 \ldots m_{b-1}

Los siguientes son los 5 pasos utilizados para calcular el hash de un mensaje.

Paso 1. Agregar bits faltantes.

El mensaje se expande para que su longitud en bytes módulo 16 sea 0. Así, como resultado de la expansión, la longitud del mensaje se convierte en un múltiplo de 16 bytes. La expansión siempre se realiza, incluso si el mensaje originalmente tiene la longitud correcta.

La expansión se realiza de la siguiente manera: se agregan al mensaje i bytes iguales a i para que su longitud en bytes sea 0 módulo 16. Como resultado, se agrega al mensaje un mínimo de 1 byte y un máximo de 16.

Por ejemplo, si el mensaje tiene una longitud de 28 bytes, se rellena a 32 bytes con cuatro adicionales, cada uno de los cuales es igual a cuatro.

En esta etapa (después de agregar los bytes), el mensaje tiene una longitud de exactamente un múltiplo de 16 bytes. Denotemos los bytes del mensaje resultante (N es un múltiplo de 16). $M[0 \ldots N-1]$

Paso 2. Agregar una suma de verificación.

Se agrega una suma de verificación de mensaje de 16 bytes al resultado del paso anterior.

La suma de verificación se calcula de la siguiente manera: para cada bloque de mensaje de 16 bytes, se realizan los siguientes pasos 16 veces:

$c=M[i*16+j]$ ,

$C[j]=S[c \oplus L] \oplus C[j]$ ,

$L=C[j]$

, donde i es el número de un bloque de datos de 16 bytes;

j es el número del paso de ciclo actual;

$M[x]$ — x-ésimo byte del mensaje, es decir, — este es el j-ésimo byte del bloque de datos actual; $M[i * 16 + j]$

c y L son variables temporales, L contiene inicialmente el valor 0;

$C[j]$ — j-ésimo byte de la matriz de suma de comprobación; antes de calcular la suma de comprobación, la matriz contiene cero bytes;

$Si]$ - i-ésimo elemento de la matriz de 256 bytes de dígitos reorganizados "aleatoriamente" de pi :

41	46	67	201	162	216	124	una	61	54	84	161	236	240	6	19
98	167	5	243	192	199	115	140	152	147	43	217	188	76	130	202
treinta	155	87	60	253	212	224	22	103	66	111	24	138	23	229	Dieciocho
190	78	196	214	218	158	222	73	160	251	245	142	187	47	238	122
169	104	121	145	21	178	7	63	148	194	dieciséis	137	once	34	95	33
128	127	93	154	90	144	cincuenta	39	53	62	204	231	191	247	151	3
255	25	48	179	72	165	181	209	215	94	146	42	172	86	170	198
79	184	56	210	150	164	125	182	118	252	107	226	156	116	cuatro	241
69	157	112	89	100	113	135	32	134	91	207	101	230	45	168	2
27	96	37	173	174	176	185	246	28	70	97	105	52	64	126	quince
85	71	163	35	221	81	175	58	195	92	249	206	186	197	234	38
44	83	13	110	133	40	132	9	211	223	205	244	sesenta y cinco	129	77	82
106	220	55	200	108	193	171	250	36	225	123	ocho	12	189	177	74
120	136	149	139	227	99	232	109	233	203	213	254	59	0	29	57
242	239	183	catorce	102	88	208	228	166	119	114	248	235	117	75	diez
49	68	80	180	143	237	31	26	219	153	141	51	159	17	131	veinte

Esta tabla también se utiliza en la función de compresión del algoritmo MD2 en el cuarto paso.

Implementación software del 2do paso en pseudocódigo:

/* Borrar suma de control. */ Para i = 0 a 15 hacer : Establezca C [ i ] en 0. final /* del bucle en i */ Establezca L en 0. /* Procesar cada bloque de 16 palabras. */ Para i = 0 a N / 16-1 hacer /* Bloque de suma de comprobación i. */ Para j = 0 a 15 hacer Establezca c en M [ i * 16 + j ]. Ajuste C [ j ] a C [ j ] x o S [ c x o L ]. Establezca L en C [ j ]. final /* del bucle en j */ final /* del bucle en i */

Se agrega una suma de comprobación de 16 bytes al mensaje. Ahora el mensaje se puede escribir como , donde . $C[0 \ldots 15]$ $M[0 \ldots N_1-1]$ $N_1 = N + 16$

Paso 3. Inicialice el búfer MD.

El búfer X de 48 bytes se utiliza para calcular el hash. Se inicializa con ceros.

Paso 4. Procesamiento del mensaje en bloques de 16 bytes.

Este paso utiliza la misma matriz de permutación S de 256 bytes que en el paso 2.

Cada bloque de mensaje con relleno i-ésimo de 16 bytes, incluido el bloque de suma de comprobación, se superpone en el búfer X de la siguiente manera:

El bloque de datos se copia en el búfer de la siguiente manera:

$X[16 + j] = M[i * 16 + j]$ , j = 0…15,
$X[32 + j] = (X[16 + j] \o más X[j])$ , j = 0…15.

Por lo tanto, si representamos el búfer X como 3 fragmentos de 16 bytes, luego de copiar el bloque de datos, el segundo de los fragmentos del búfer contiene el bloque de datos que se está procesando, y el tercero es el resultado de aplicar la operación XOR bit a bit al bloque actual. contenido del primer fragmento y bloque de datos.
Se realiza el procesamiento del búfer, que consta de 18 rondas de conversiones, cada una de las cuales actualiza cada byte del búfer de la siguiente manera:
$X[k] = (X[k] \o más S[t])$ . . $t = X[k]$
donde k = 0…47,
t es una variable temporal que inicialmente tiene valor cero, y después de cada j-ésima ronda (j = 0…17) t se modifica de acuerdo con la regla:
$t = t + j \ mod 256$ .

Implementación del 4º paso en pseudocódigo:

/* Procesar cada bloque de 16 palabras. */ Para i = 0 a N1 / 16-1 hacer /* Copia el bloque i en X. */ Para j = 0 a 15 hacer Establezca X [ 16 + j ] en M [ i * 16 + j ]. Establezca X [ 32 + j ] en ( X [ 16 + j ] x o X [ j ]). final /* del bucle en j */ Establezca t en 0. /* Haz 18 rondas. */ Para j = 0 a 17 hacer /* Ronda j. */ Para k = 0 a 47 hacer Establezca t y X [ k ] en ( X [ k ] xor S [ t ]). final /* del bucle en k */ Establezca t en ( t + j ) módulo 256. final /* del bucle en j */ final /* del bucle en i */

Paso 5. Formación de un hash.

El hash se calcula como el resultado de ; byte va al principio y . $X[0 \ldots 15]$ $X[0]$ $X[15]$

Esto concluye la descripción del algoritmo MD2. RFC 1319 proporciona una implementación del algoritmo en C.

Ejemplo

MD2("123456789012345678901234567890123456789012345678901234567890123456 78901234567890") = 05dbba941443332475b8e3f572f5d148

Rendimiento

MD2 es un algoritmo hash relativamente lento en comparación con otros algoritmos conocidos. La siguiente tabla muestra la velocidad de cálculo de la suma hash de mensajes de diferentes algoritmos hash en IBM PS/2 (16 MHz 80386) [1] .

Algoritmo	Velocidad, kbps	Año
MD2	78	1989
FFT hash I	212	1991
N-hachís	266	1990
Snefru-8	270	1990
Snefru-6	358	1990
Snefru-4	520	1990
SHA	710	1995
Snefru-2	970	1990
RIPEMD	1334	1996
MD5	1849	1995
MD4	2669	1990

La tabla muestra que MD2 es inferior en velocidad a otros algoritmos ampliamente utilizados, al menos en un orden de magnitud.

Seguridad

El autor de MD2, Ronald Rivest , sugirió que:

la complejidad del problema de encontrar una preimagen mediante una suma hash conocida es del orden de 2.128 operaciones
la complejidad de la tarea de búsqueda de colisiones (dos mensajes con la misma suma hash ) es del orden de 2 64 operaciones [6]

En 1994, Bruce Schneier escribió sobre el algoritmo MD2 que, aunque más lento que otros algoritmos hash, era criptográficamente seguro en ese momento [7] .

Desde entonces, los criptoanalistas han logrado avances significativos en el análisis de MD2; ahora el algoritmo se considera pirateado [5] .

Historia del criptoanálisis MD2

En 1993, Bart Prenel en su trabajo [1] señaló que dado que los últimos 32 bytes del búfer del algoritmo no se utilizan en el valor hash de salida, es posible omitir la actualización de estos bytes en la última iteración del búfer para el último bloque de entrada. datos. En el mismo documento, se observa que el número de rondas del algoritmo (18) es solo una ronda más que el mínimo posible para que el valor de salida del algoritmo pueda alcanzar todas las opciones posibles de 2128 . Por tanto, podemos concluir que el margen de seguridad criptográfica del algoritmo es mínimo y que es imposible aumentar la tasa de hashing reduciendo el número de rondas sin pérdida de seguridad. Bart Prenel también propuso una técnica para atacar MD2 de ronda completa usando criptoanálisis diferencial , pero no describió ataques específicos al algoritmo.

En 1995, se propuso un método para encontrar colisiones, pero no tuvo éxito debido a la suma de comprobación añadida al final del mensaje [8] . En algunos trabajos [9] , se observó que debido al diseño original del algoritmo MD2, los resultados conocidos del criptoanálisis de funciones hash con estructura clásica no son aplicables a este algoritmo. Sin embargo, allá por 1996, RSA recomendaba no utilizar el algoritmo MD2 en los casos en los que se requería la ausencia de colisiones. Pero por lo demás, MD2 permaneció seguro [10] .

Roget y Chavot publicaron un ejemplo de colisiones para MD2 en 1997, aunque no pudieron proporcionar un algoritmo para encontrar otras colisiones.

El primer ataque a MD2 en su totalidad fue propuesto en 2004 por Frederick Müller, lo que permite encontrar una preimagen con una laboriosidad de 2104 operaciones, que es significativamente menor que la laboriosidad teórica de buscar una preimagen para MD2, que es 2128 operaciones. Muller declaró: "MD2 ya no puede considerarse un algoritmo hash seguro" [9] . Aunque la complejidad del ataque aún era demasiado grande para la posibilidad de implementar este ataque en la práctica.

En 2005, Lars Knudsen y John Mathiassen mejoraron significativamente los resultados de Muller al proponer ataques que no solo reducían la complejidad de los ataques, sino que también permitían encontrar los mensajes deseados de longitud variable, mientras que los ataques de Muller permitían encontrar solo preimágenes de 128 bloques de 16 bytes de largo [11] .

El siguiente gran paso en el criptoanálisis MD2 lo dio Soren Thomsen en 2008. Logró reducir la complejidad de la tarea de búsqueda de preimagen a 2 73 operaciones [12] , lo que acercó este ataque al estado de implementación en la práctica.

Un año más tarde, uniendo fuerzas, los autores de trabajos anteriores (Lars Knudsen, John Mathiassen, Frederic Müller, Soren Thomsen) mejoraron los resultados del ataque de búsqueda de colisión, alcanzando una complejidad de 263,3 operaciones, ligeramente inferior a la teórica. uno (2 64 ) [13] .

Aplicación

Debido a su robustez y facilidad de implementación, MD2 se ha utilizado en muchos protocolos de red , entre ellos:

PEM (Privacy-Enhanced Mail) [7] protocolo de correo electrónico seguro , en versiones posteriores de PEM se usó MD2 junto con el más seguro MD5 [14]
Infraestructura de clave pública PKI (Infraestructura de claves públicas) , sin embargo, ya en la especificación de 1999 se recomienda usar SHA-1 o MD5 [15]
El estándar de operaciones criptográficas asimétricas PKCS # 1 (Public Key Cryptography Standard) permitió el uso de seis algoritmos hash: MD2, MD5, SHA-1, SHA-256, SHA-384 y SHA-512, y los dos primeros fueron recomendados para usarse solo por compatibilidad con las aplicaciones antiguas [16] .

Véase también

Notas

↑ 1 2 3 4 Preneel B. Análisis y diseño de funciones hash criptográficas - febrero de 2003
↑ J. Linn. Mejora de la privacidad para el correo electrónico de Internet: Parte III: algoritmos, modos e identificadores (inglés) (enlace no disponible) . IETF (agosto de 1989). Archivado desde el original el 2 de diciembre de 2012.
↑ J. Linn. Mejora de la privacidad para el correo electrónico de Internet: Parte I: Procedimientos de autenticación y cifrado de mensajes (inglés) (enlace inactivo) . IETF (enero de 1988). Archivado desde el original el 2 de diciembre de 2012.
↑ B. Kaliski. El MD2 Message-Digest Algorithm (inglés) (enlace no disponible) . Laboratorios RSA (abril de 1992). Archivado desde el original el 2 de diciembre de 2012.
↑ 1 2 S. Turner, L. Chen. MD2 a estado histórico (inglés) (enlace no disponible) . IETF (marzo de 2011). Archivado desde el original el 2 de diciembre de 2012.
↑ S. Bakhtiari, R. Safavi-naini, J. Pieprzyk, Funciones hash criptográficas: una encuesta (1995)
↑ 1 2 Bruce Schneier, Criptografía aplicada: protocolos, algoritmos y código fuente en C (1995)
↑ Rogier N. , Chauvaud P. Md2 no es seguro sin el byte de suma de comprobación // Des . Codigos Cryptogr. - Springer EE . UU ., Springer Science + Business Media , 1997. - vol. 12, edición. 3.- Pág. 245-251. — ISSN 0925-1022 ; 1573-7586 - doi:10.1023/A:1008220711840
↑ 1 2 Muller F. The MD2 Hash Function Is Not One-Way // Advances in Cryptology - ASIACRYPT 2004 : 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, 5 al 9 de diciembre de 2004, Actas / P. J. Lee - Berlín , Heidelberg , Nueva York, NY , Londres [etc.] : Springer Science + Business Media , 2004. - P. 214-229. — 548 págs. - ( Lecture Notes in Computer Science ; Vol. 3329) - ISBN 978-3-540-23975-8 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-540-30539-2_16
↑ Robshaw MJB sobre los resultados recientes de MD2, MD4 y MD5 (inglés) (1996).
↑ Knudsen L. R. , Mathiassen J. E. Preimage and Collision Attacks on MD2 // Fast Software Encryption : 12th International Workshop , FSE 2005, París, Francia, 21-23 de febrero de 2005, Documentos seleccionados revisados / H. Gilbert , H. Handschuh - Berlín , Heidelberg , Nueva York, NY , Londres [etc.] : Springer Science + Business Media , 2005. - P. 255-267. — 443 pág. - ( Lecture Notes in Computer Science ; Vol. 3557) - ISBN 978-3-540-26541-2 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/11502760_17
↑ Thomsen SS, Un ataque de preimagen mejorado en MD2 (2008)
↑ Knudsen L. R. , Mathiassen J. E. , Muller F. , Thomsen S. S. Cryptanalysis of MD2 (inglés) // Journal of Cryptology / I. Damgård - Springer Science + Business Media , Asociación Internacional para la Investigación Criptológica , 2010. - Vol. 23, edición. 1. - Pág. 72–90. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/S00145-009-9054-1
↑ D. Balenson. Mejora de la privacidad para el correo electrónico de Internet: Parte III: algoritmos, modos e identificadores (inglés) (enlace no disponible) (febrero de 1993). Archivado desde el original el 2 de diciembre de 2012.
↑ R. Housley, W. Ford, W. Polk, D. Solo. Infraestructura de clave pública X.509 de Internet. Certificado y perfil de CRL (inglés) (enlace no disponible) (enero de 1999). Archivado desde el original el 2 de diciembre de 2012.
↑ J. Jonsson, B. Kaliski. Estándares de criptografía de clave pública (PKCS) n.º 1: Criptografía RSA (inglés) (enlace no disponible) (febrero de 2003). Archivado desde el original el 2 de diciembre de 2012.

Enlaces

RFC 1319

Funciones hash
propósito general	Adler-32 CDN Suma de comprobación de Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Árbol de hachís picadillo de jenkins suma de hash
Criptográfico	Stribog GOST R 34.11-94 Cinturón BLAKE BMW CubeHash ECO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H Kupyna Hachís de LM luffa MD2 MD4 MD5 MD6 N-hachís RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD RÁPIDO Piel Snefru Tigre Torbellino
Funciones de generación de claves	cripta PBKDF2 cripta Argón2 Lyra2
Número de cheque ( comparación )	Suma de verificación Algoritmo de Verhouff Algoritmo lunar Maldito algoritmo Código de barras cuentas bancarias tarjetas bancarias ES EN SNILES OKPO ESTAÑO OKATO ISBN OGRN y OGRNIP VIN
Hachís	Comparación de números de cheque Protocolos de autenticación Comparación de códigos de barras Criptografía Enlace magnético firma Merkle ed2k URNA