Find $ secreta en $ a == MD5 (. $ B $ secreta)

Question

Una función es:

$a == md5($b . $secret); 

• Se puede elegir $ ay $ b
• No sabes $ secreta
• Obtiene el valor de la función para $ a y $ b que elija como verdadera o falsa.

¿Hay algún ataque mejor que la fuerza bruta para encontrar $ secret en general? ¿Hay algún ataque mejor que la fuerza bruta para encontrar $ secret usando PHP's md5 function?

Según lo que he encontrado en la web, creo que no, aunque md5 está en desuso en algunos casos de uso. Así que para estar seguro ...

Saludos cordiales

Answer 1

Si MD5 se comporta como un oráculo aleatorio (que es un gran "si", véase más adelante), entonces la búsqueda exhaustiva en $secret es el mejor ataque es posible - y, más importante, cada "adivinar" en el valor de $secret MUST use una consulta para la función (ya que usa PHP, supongo que la función se implementa en un servidor web, y cada "consulta" requiere hablar con ese servidor). Esto último está implícito en la falta de información enviada al atacante: el atacante no obtiene nada excepto un solo bit (el resultado "True" o "False"). En particular, él no obtiene la salida MD5 en sí. El atacante obtendrá una larga secuencia de resultados poco informativos "False" a menos que golpea la salida MD5 correcta, ya sea por pura casualidad (probabilidad 2 ^-128, que es realmente Darn pequeño), o porque supuso correctamente el valor de $secret antemano. Vale la pena notar que esto evita que el atacante use muchas técnicas de costo compartido, incluidas las tablas precalculadas, en particular el sobrediminicado rainbow tables.

Un random oracle es un objeto mítico que puede ser visto como un cuadro negro determinista: sabes nada en la salida que se obtiene de una entrada dada, excepto que la caja siempre devolverá el mismo resultado para una entrada dada . Un modelo es el siguiente: la caja contiene un gnomo, algunos dados y un gran libro. El gnomo usa los dados para elegir aleatoriamente la salida. También usa el libro para realizar un seguimiento de las respuestas que ya envió, a fin de ser coherente, es decir, si la entrada es idéntica a una entrada presentada anteriormente, el gnomo devolverá el mismo resultado que anteriormente en lugar de tirar los dados.

MD5, sin embargo, es no un oráculo al azar. Por ejemplo, podemos construir colisiones para MD5 mucho más rápido que la resistencia teórica de 2 para una función con una salida de 128 bits. Además, tenga en cuenta que ser una buena función hash (resistente a las colisiones, etc.) no requiere absolutamente "oráculo aleatorio". Por ejemplo, SHA-256 se considera una función hash segura, aunque todavía sufre el llamado "ataque de extensión de longitud" (dado SHA256($a), se puede calcular SHA256($a) sin conocer $a, para valores casi arbitrarios de $b). Por lo tanto, las garantías de un oráculo aleatorio no se cumplen con MD5 (o, para el caso, SHA-256). ¡Esto no significa que se conocen ataques más rápidos! Solo que estás solo aquí.

También se puede señalar que md5($b . $secret) es una especie de "hash con clave", es decir, un MAC (Código de autenticación de mensajes). Construir un MAC a partir de una función hash no es fácil, precisamente debido a cosas como el ataque de extensión de longitud (md5($secret . $b), por ejemplo, sería un MAC muy pobre). Se diseñó una forma robusta de construir un MAC a partir de una función hash; se llama HMAC e implica dos invocaciones de la función hash subyacente (pero una de ellas es en una entrada corta, por lo que es eficiente, no obstante). La seguridad de HMAC, más precisamente cómo se puede considerar que HMAC se comporta como un oráculo aleatorio, puede "probarse", es decir, reducirse a algunas propiedades internas de la función hash que se creen verdaderas en el caso de SHA-256 (ver New Proofs for NMAC and HMAC: Security without Collision-Resistance de Mihir Bellare para los detalles sangrientos). Al usar HMAC/SHA-256 sobre $b, con $secret como clave, se beneficiaría de estos resultados de seguridad, y su construcción sería más convincentemente robusta. Por otra parte, no pretendo que haya un ataque conocido en md5($b . $secret), solo que tanto el uso de MD5 como la construcción de MAC hecha en casa levantan banderas rojas, que degradan el nivel de confianza que se puede impartir a dicho sistema.

Answer 2

descarga una tabla de arco iris/hash de la contraseña de la famosa contraseña! :)

Answer 3

Esta es una pregunta interesante, porque en los escenarios típicos de TI-Seguridad no puede elegir $a y $b como atacante. Si puede obtener una contraseña hash, por ejemplo, $a y $b ya están definidos y tiene que trabajar con eso. En ese caso, solo puede usar fuerza bruta o una tabla arcoiris si está disponible una con la sal $b.

En su ejemplo, por otro lado, puede elegir ambos valores. Puedes tomar un secreto arbitrario, p. test y elija los valores para $a y $b en consecuencia. Elijo $ b para que sea empty string y calcule $a con $a = md5($secret), lo que da como resultado 098f6bcd4621d373cade4e832627b4f6.

Elijo $a = "098f6bcd4621d373cade4e832627b4f6" y $b= "" y le pregunto si $secret == "test". Dices cierto y digo problema resuelto.

Esto finalmente nos lleva a la respuesta real. Las dos condiciones dadas

• Se puede elegir $ ay $ b
• No sabes $ secreta

no funcionan juntos. En mi ejemplo, definí $secret. Violé la segunda condición. Por otro lado, no puedo elegir $a y $b de forma arbitraria sin derivarlos de $secret, porque es posible que no tengan una solución.

Si suponemos que hay al menos una solución para todos los pares posibles de $a y $b (tal vez haya pruebas para eso, no sé), y los selecciona de una manera que realmente no sabe $secret, siempre me gustaría definir $b = "", para hacer que el ataque sea lo más fácil posible. Las tablas Rainbow son tus amigos en ese caso.