Desvelado el bug del trucha

wiibrew escribió:The bug here is that the hash can (and very likely does) contain a NULL byte, (chr)0 that is. To quote from the first google hit for strncmp:
"Compares up to num characters of the C string str1 to those of the C string str2. This function starts comparing the first character of each string. If they are equal to each other, it continues with the following pairs until the characters differ, until a terminating null-character is reached, or until num characters match in both strings, whichever happens first."
This last part means that if it finds a NULL byte, it stops comparing, even if there is more data after the NULL.
This reduces the effective length of the hash to the number of bytes before the NULL byte. This means that the difficulty of finding a hash collision is reduced from 2^(HASHLENGTH*8) to 2^(bytes before the null). That is a big change if the NULL is early in the hash. Assuming the NULL is at the 5th byte, that means that there is a one in 2^(4*8) chance that the hash matches, or one in 4 294 967 296, fairly computable within a reasonable time frame on a current computer that can try a few million hash inputs each sec.

El bug es que el hash puede contener un byte nulo (NULL), 0. La cita de el primer resultado de Google para "strncmp":

"Compara hasta num caracteres de la cadena str1 a estos en la cadena str2. La función empieza a comparar el primer carácter de cada cadena. Si son iguales, continua con los pares de caracteres siguientes, hasta que se llegue a un carácter nulo o hasta que se llega a num caracteres a ambas cadenas, lo que ocurra primero"

Esta ultima parte significa que si encuentra un carácter nulo, para de leer, aunque haya más información detrás del carácter nulo.

Esto reduce la longitud efectiva del hash a el numero de bytes antes del byte nulo. Esto significa que la dificultad de encontrar una colisión de hash se reduce de 2^(LONGITUDDELHASH*8) a 2^(bytes antes del carácter nulo). Esto es un gran cambio si el caracter nulo se encuentra en el hash. Suponiendo que el carácter nulo es el quinto byte, esto significa que hay una posibilidad entre 2^(4*8) de que el hash coincida, o una posibilidad entre 4.294.967.296, bastante computable en un tiempo razonable en un ordenador actual que puede probar unos pocos millones de hash cada segundo.

GameZelda escribió:Supongo que debieron utilizar el método típico del "funciona? pues ya está" y listo

pepone1234 escribió:A ver si lo he entendido bien. Lo que hace este método es comparar dos cadenas para ver si son iguales. Si las dos son iguales, salta y si en la primera hay un byte nulo no continúa la comprobación, con lo que las posibilidades de éxito aumentan a medida que el byte nulo se encuentre más cerca del principio debido a las características de los números exponenciales y un poco de probabilidad ¿no es así?

GameZelda escribió:Exacto (excepto que el byte nulo puede estar en cualquiera de las dos cadenas y no solo en la primera)

(Que no son cadenas, este es el problema, que son datos binarios y usaron funciones para cadenas)

xt5 escribió:edit



no es que pueda estar en cualquiera de las dos, DEBE estar en las dos cadenas y en la misma posicion.