Como comentaba en la entrada anterior vamos a hablar de MD5.
MD5 es una función de hash más antigua que SHA1, y también más atacada. Tiene agujeros reconocidos, lo que la hace (si se usa sola) una función hash vulnerable y poco recomendada.
Podéis ver el funcionamiento de MD5 aquí.
El output de MD5 es de 32 caracteres hexadecimales, es decir, 8 menos que SHA1.
Siguiendo con la política de "indexar" todo el hash, en esta ocasión lo tendremos "más fácil", puesto que las combinaciones son bastantes menos: concretamente 340282366920938463463374607431768211456.
Si además usamos una base 254 (es decir, todo el ASCII extendido, menos el caracter 255), podríamos hacer la siguiente comparativa:
SHA1
1461501637330902918203684832716283019655932542976 => 16^40 (combinaciones totales)
317327747538939448210764374129986337215282732335104 => 254^21 (se necesitan 21 caracteres de longitud)
30691534383948961282277381487041943412774583402496 => (16^40) * 21 (Tamaño en bytes)
27913787911483233000000000000000000000 => Tamaño en tb necesario
MD5
340282366920938463463374607431768211456 => 16^32 (combinaciones totales)
76238296299110445689222455991796294877184 => 254^17 (se necesitan 17 caracteres de longitud)
5784800237655953878877368326340059594752 => (16^32) * 17 (Tamaño en bytes)
5261245166962866000000000000 => Tamaño en tb necesario
Como veis sigue siendo un tamaño astronómico, pero como comentaba, en ambos casos hay vulnerabilidades basadas en colisiones.
¿Colisión de partículas?
Casi. En la entrada anterior se definió de manera vaga el concepto de colisión. Veamos ahora un poco más en profundidad de qué se trata.
Así que vamos a desempolvar los conceptos matemáticos (aquí tenéis un poco de teoría) y nos ponemos con ello (nos centramos en SHA1):
Podemos representar un hash como una función f(x): N+ -> N+, es decir, con un dominio acotado (y tan acotado) en los números naturales positivos, y con un recorrido también en el mismo cuerpo.
Para transoformar un texto en un número natural positivo no tenemos más que usar, por ejemplo, la base 254 (ASCII extendido), y ahí lo tenemos.
¿Qué más sabemos de esta función?
Bien, sabemos que es un conjunto cerrado, es decir, tiene un valor máximo que nunca será pasado. Este máximal es 16^40.
Ahora puede que haya una pequeña confusión... ¿no estábamos en base 254? Sí, en el recorrido (valores que puede tomar la función); pero el dominio puede ser escrito en base 16. Esto se hace para evitar vacíon en los valores que pueda tomar el dominio. Usando base 16, podemos definir el dominio como D={x|x<=16^40, x
N+}.Otro motivo para usar base16 es que pasar a numérico es computacionalmente muy sencillo (muchos lenguajes de programación tienen funciones para pasar hexadecimal a otras bases y de estas mismas a hexadecimal).
Obviamente esta función no es continua, ya que está definida solamente en N+ (no imaginamos un texto que al pasar a numérico de decimales...).
Podríamos apilar los 100 primeros valores numéricos y generar un gráfico como éste:
Temas aparte... ¿Os habéis fijado que independientemente de la base que usemos (dec o hex), con un par de suposiciones podríamos definir un endomorfismo?
¿endoqué?
Entiendo que no todos mis lectores (los que pueda llegar a tener... jeje) tienen porqué saber demasiadas matemáticas. Así que explicaré un poco por encima qué es un endomorfismo.
Se conoce como endomorfismo una función cuyo conjunto inicial y conjunto imagen son el mismo.
Es decir, imaginaos lo siguiente: tenemos un conjunto de los números de una cifra (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) y una función definida "a mano" tal que:
f(0) = 1
f(1) = 5
f(2) = 4
f(3) = 9
f(4) = 0
f(5) = 2
f(6) = 7
f(7) = 3
f(8) = 6
f(9) = 8
de esta manera, f(x) siempre estará dentro del conjunto de los números de una cifra, que es el conjunto inicial.
Esto nos permite hacer afirmaciones como que "podemos componer infinitamente un endomorfismo sobre si mismo", o lo que es lo mismo, podemos hacer f(f(x)), f(f(f(x))), f(f(f(f(x)))), ... y como el resultado siempre estará dentro del conjunto de valores válidos, la función siempre tendrá un valor existente.
Ahora que ya sabemos qué es un endomorfismo, seamos un poco optimistas, y supongamos lo siguiente:
cualquier numérico positivo (0 inclusive) menor o igual que 16^40 tiene un hash diferente y único (principio de máxima distributividad).
Esto significaría que el conjunto imagen (SHA1(x)) sería siempre un elemento del conjunto inicial.
Pero, ¿si introducimos un valor que esté fuera del conjunto?
Entonces se rompe nuestro endomorfismo... pero ahora entra una nueva información en juego: el resultado de SHA1(x) siempre estará dentro del conjunto que habíamos definido antes. De esta manera, es igualmente válido componer indefinidamente y sobre si mismo la función SHA1(x).
Bueno, esto está un poco "ido de vueltas"... el tema de introducir SHA1 (o cualquier hash) como un endomorfismo es para demostrar que cualquier elemento que esté fuera del conjunto de valores iniciales puede producir una colisión.
Y estamos en el meollo. Colisión. Para hacer una explicación gráfica... la función f(x) = 2x no tiene colisiones, es decir, para cada "x" existe un único f(x) que lo define, de manera que dado un f(x) podemos obtener el "x" original.
Por otra parte f(x) = sin(x) es una función sensible a colisiones, puesto que varios "x" pueden dar el mismo valor, lo que imposibilita obtener el "x" original, y nos veremos forzados a expresarlo como "kx".
Pues un hash se parece más a sin(x) (no gráficamente, sino en el sentido de las colisiones), puesto que varios "x" pueden teóricamente dar el mismo f(x).
Y ahí es donde surgen los ataques, en el método óptimo para encontrar dos "x" con igual f(x).
Desde luego estoy (poco a poco) investigando estos temas. Podría copiaros párrafos y párrafos de wikipedia y foros con respecto a estos ataques, pero no podría explicarlos; de manera que no los copiaré (podéis buscar por Google, la información es bien accesible :D).
Y hasta aquí la "breve" reflexión de los hashes.
La próxima entrada irá en el filo de los hash, y cómo "comprimir" los enormes diccionarios que os comentaba (o parte de ellos).
Saludos y ¡Hasta la próxima!
No hay comentarios:
Publicar un comentario