Hashes y colisiones

En su momento hablé de las contraseñas de Windows (I y II) éstas se guardan utilizando un algoritmo que genera un hash.

Si recuerdo lo que comenté en alguno de esos dos posts, en la universidad te enseñan que al realizar un algoritmo para introducir un dato en una tabla hash se utiliza ese hash como "posición" para localizar ese dato. Y que a veces, y sólo a veces, (cómo me gustaba la serie de El cuervo aunque a muchos no les acabara de gustar), se producía una colisión. ¿Y qué es una colisión? Describiéndolo de una manera resumida es cuando dos paquetes coinciden en un instante determinado en la misma red... Vaya, no quería poner esto. Ese tipo de colisión es la definición aplicadas a las redes. Yo quería definirlo aplicado a los hashes. Y ésta es la circustancia en la que dado un algoritmo determinado, y un dos elementos del que se quiere saber sus hashes, ambos hashes coinciden. En la universidad, para solventar esto, a la hora de realizar la búsqueda, lo que se hacía era que si el elemento a buscar no estaba en la posición del hash obtenido, se buscaba secuencialmente en una tabla auxiliar. Pero estamos hablando de contraseñas. Y aquí no debería de haber cabida para las colisiones. Cuanto más complicado sea que se produzcan, mejor.

Pongamos un ejemplo. En un abecedario, de la A la Z, sin distinguir mayúsculas y minúsculas:

A	B	C	D	E	F	G	H	I	J	K	L	M	N	Ñ	O	P	Q	R	S	T	U	V	W	X	Y	Z
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27

¿Qué ejemplo de algoritmo puede producir colisiones? Un ejemplo podría ser la suma del valor de las letras que tiene la palabra de la queremos sacar el hash. Si queremos codificar:

• osos: 16 + 20 + 16 + 20 = 72
• soso: 20 + 16 + 20 + 16 = 72

En efecto, si utilizásemos la segunda palabra como contraseña en un sistema que utilizase este algoritmo, tendríamos la posibilidad de pasar con la primera palabra. A parte de que no es el mejor ejemplo porque ambas palabras existen, y seguro que se encuentra en un diccionario de datos. Si no es así, dad por seguro que ahora sí que estará.

Ahora. Hace unas dos semanas, en el curso / master de seguridad que estoy haciendo con Informática64 nos enseñaron que un sitio determinado tenía una zona de acceso restringido. Y, ese sitio tenía varias cosas que deberían de arreglar:

1. La seguridad estaba en el lado del cliente. ¿Qué significa esto? Que el control de si la autenticación es válida o no se hace desde el navegador. No se solicita comprobación en el servidor. 
2. Los usuarios están incluidos en un combo. No se pueden introducir nombres de usuario. Pero con tal de tener ese combo con los usuarios válidos ya es un paso para poder entrar en el sitio. 
3. Las contraseñas están codificadas en la propia página web. ¿Qué implica esto? Que si tenemos el usuario y tenemos la contraseña (codificada), estamos a un paso para poder entrar en el sitio. 
4. Tenemos el algoritmo que genera ese hash, que ya tenemos. 

Con estas 4 cosas, ya podríamos entrar en el sitio. Pero eso no es lo que quiero enseñar. Primero, porque entrar en un sitio sin autorización, por muy fácil que sea la contraseña, no es legal. Y segundo, porque quiero enseñar un poquito un pseudocódigo de como es el algortimo que han utilizado (si acaso, modifico cosas para que no sea tan fácil averiguar de dónde sale:

funcion dameHash(palabra, modificador){

  palabra_auxiliar = palabra;

  elHash = 0;

  desde i =0;i

    elHash = elHash *(modificador^modificador) + valor_letra_en_posicion(i,palabra_auxiliar) + 1;

  }

  devolver elHash;

}

Existe algún que otro problema. Uno de ellos, el que comentaba antes. Puede haber un montón de combinaciones posibles que den el mismo hash. ¿Qué pasa si hacemos la invera? Buscar la (¿no serán las?) palabra(¿s?) que nos permitan llegar a ese hash.

Para eso hay que despejar en la ecuación anterior. Pero nos podemos encontrar con problemas con los nombres. Por eso hay que pensar en un hash_auxiliar y el hash_actual.

La ecuación quedaría algo así:

hash_auxiliar = (hash_actual -1 - posicionPosibleDeLaLetra);

Esto está muy resumido, pero, se explica de una menera muy sencilla. Hay que hacer todas las pruebas posibles de esta ecuación, hasta que hash_auxiliar sea 0. Lo que significa que:

1. La ecuación se repetirá tantas veces como longitud_siempre_fija tenga como valor.
2. Después de realizar la operación, hash_actual cogerá le valor de hash_auxiliar. 
3. posicionPosibleDeLaLetra será una variable que irá cogiendo todos los posibles valores que permitan que su combinación con las selecciones anteriores lleguen al objetivo deseado, es decir, que el hash_auxiliar sea 0. Siempre se puede elegir obtener el primer resultado ó que nos devuelva todos. Y esto es lo que quería enseñar.
   

Se que no está muy, muy resumido, pero no puedo dar muchos más datos. El tema está en que una función de estas características puede producir casi 1019 colisiones. Si alguien quiere más detalles, que me de un toque.