Complejidad de los ataques de certificados web

El MD5 ha quedado en desuso debido a la facilidad con la que puedes encontrar una colisión: hace unos años escribí un artículo que mostraba cómo generar una colisión MD5 en menos de un minuto. Esto ha sido refinado a solo unos segundos.

La generación de dos documentos postscript diferentes con la misma suma MD5 aprovecha el hecho de que postscript es un lenguaje informático y los espectadores postcript evalúan este lenguaje. Es un buen truco. Funciona así: el archivo 1 tiene un bloque binario Q, luego un código, luego el documento A y luego el documento B. Cuando se muestra el archivo 1, se ejecuta el código que examina Q y luego aparece A.

Ahora hacemos una copia de File1 llamada File2. Modificamos solo Q a Q ', que tiene la misma suma MD5 que Q. Esto significa que File2 tiene la misma suma MD5 que File1 ya que nada más cambia. Pero ahora, cuando mostramos el Archivo 2, se ejecuta el mismo código, ve Q 'y genera el documento B. ¡Lindo!

Pero aquí estamos usando el hecho de que colisiones son fáciles de encontrar en MD5. Nadie (por lo que sé) puede invertir compendios MD5 arbitrarios, ni nadie puede encontrar una segunda entrada para que coincida con la suma MD5 de un archivo dado (esto se denomina "segunda resistencia de preimagen").

Así que lo que sugieres anteriormente es todavía inviable. El cálculo que solicitó: MD5 genera 128 bits, por lo que la probabilidad de que un resumen aleatorio coincida con uno dado es de $ 1/2 ^ {128} $ y, por lo tanto, tomará los $ 2 ^ {128} $ intentos para reproducir los digerir.

Los ataques existentes se refieren a colisiones : el atacante construye dos certificados que contienen hash para el mismo MD5, pero con contenidos distintos. Uno de ellos es "benigno" (contiene el nombre del atacante) y este es el que el atacante envía a la CA para una firma. La CA lo firma porque es una solicitud de certificado perfectamente válida (proviene del atacante y realmente contiene el nombre del atacante). Gracias a la colisión de MD5, la firma es también verificable cuando se enchufa en el otro certificado. Así que el atacante obtuvo una firma de CA en un certificado en el que eligió los contenidos fuera de control de la CA. Los detalles son un poco complejos porque el atacante debe encontrar una colisión de tal manera que los dos certificados resultantes sean "estructuralmente válidos".

Lo que pides es algo muy diferente : estás preguntando por un atacante que intenta generar un certificado con un hash que coincida con el de un certificado existente , uno que El atacante no se generó en primer lugar. Esto se denomina segundo ataque de preimagen y generalmente es más difícil que encontrar colisiones. En particular, actualmente no hay debilidad conocida en MD5 con respecto a las segundas preimágenes.

Hay 2 ¹²⁸ salidas MD5 posibles (eso es 16 ³² , no 32 ¹⁶ ). En general, si tiene N mensajes de entrada m₁ , m ₂ , ... m_N , y desea crear un nuevo mensaje m distinto de todos los m _i pero tal que el MD5 de m es igual al MD5 de uno de los m_i (cualquier testamento do), entonces el mejor método de ataque conocido es simplemente intentar mensajes aleatorios m hasta que uno coincida. El costo promedio de esa operación será 2 ¹²⁸ / N .

Probablemente hay mucho menos que 2 ³² certificados SSL, así que esto significa que el costo del ataque será de al menos 2 ⁹⁶ , lo cual es totalmente inviable con los existentes. tecnología. Así que este ataque no funcionará. Romper una clave pública de CA será mucho más fácil (tampoco es factible, pero aún más fácil, alrededor de 1 millón si la clave de CA atacada es una clave RSA de 1024 bits).

En realidad, para los certificados, el ataque es más caro que eso, porque un certificado contiene el nombre de la CA emisora. Tener una firma coincidente de la CA (por ejemplo, mediante el uso del mismo MD5) no es suficiente para que el certificado resultante sea de alguna utilidad: también debe "encadenarse" adecuadamente con la CA, lo que implica que contiene el nombre de la CA como "nombre del emisor" . Por lo tanto, la N en la fórmula anterior no es el número total de certificados existentes en la naturaleza, sino el número total de certificados emitidos por una CA dada a los que debe dirigirse específicamente . Eso es más bajo, lo que produce un costo de ataque aún mayor.