¿Se puede cambiar maliciosamente un archivo de manera que mantenga su hash SHA-1 original?

33

Según este artículo, y muchos otros, SHA-1 no es seguro.

En mi caso, no me preocupan las contraseñas o los certificados digitales. Me preocupa la integridad del archivo.

¿Es razonablemente posible que un archivo (por ejemplo, una imagen ISO o un archivo ejecutable) se altere maliciosamente de una manera que:

  • Mantiene el hash SHA-1 del archivo original y
  • Mantiene el contenido general y la operación del archivo (pero, por supuesto, ahora incluye contenido malicioso que originalmente no estaba allí)

A mi modo de ver, alterar un archivo de una manera que produce una colisión SHA-1 haría que el archivo sea totalmente inútil. El ISO estaría totalmente dañado, o el archivo ejecutable estaría tan codificado que ya no sería un archivo ejecutable.

Pero, a mi modo de ver, bien podría estar mal. Hasta ahora no he encontrado nada en las búsquedas de Google con respecto a la idoneidad continua de SHA-1 para la verificación de archivos. Alguna idea?

misha256
fuente
77
La respuesta es, depende". Si el ISO contiene muchos archivos jpegs o películas, junto con el ejecutable de destino, entonces es posible. Puede modificar archivos jpeg de manera bastante dramática sin alterar su tamaño o apariencia visual. En última instancia, cuanto más grande sea el archivo, más tendrá que jugar y mayores serán las posibilidades de una colisión no destructiva.
Paul
77
@cpast exactamente, muchos sitios web enumeran hash SHA-1 para permitirle verificar su descarga. Pensando en ello, parece mucho más probable que un pirata informático comprometa un sitio web al alterar el contenido y el hash publicado. Entonces estás realmente jodido.
misha256
1
Solo para mi información, mi pregunta es sobre SHA-1 específicamente porque es bastante común, especialmente con descargas de Microsoft / MSDN. Por supuesto, algunos sitios web publican hash MD5, otros SHA256, etc.
misha256
2
La pregunta es, ¿por qué se desea utilizar un hash que tiene las vulnerabilidades conocidas, cuando hay alternativas que son igual de rápido, fácil de usar, y ampliamente disponible que no lo hacen (por ejemplo. SHA-256) ? Además, hay una razón por la que los criptógrafos declaran un hash inseguro después de encontrar solo una vulnerabilidad: la historia ha demostrado que cuando se encuentra uno, otros lo siguen rápidamente. La famosa cita de Bruce Schneier es "Los ataques siempre mejoran, nunca empeoran"
BlueRaja - Danny Pflughoeft
3
@ misha256 Esos hash sha1 son para que usted compruebe si hay daños en la descarga, no por seguridad. Si desea seguridad, use archivos firmados con
GPG

Respuestas:

41

Nadie ha logrado esto para SHA-1. Es posible en teoría, pero aún no es práctico. Los informes sobre inseguridad en SHA-1 solo significan que el nivel de seguridad no es tan alto como nos gustaría y eso significa que no tenemos tantos años antes de tener que preocuparnos por esto como pensamos que lo hicimos.

Es más difícil producir un archivo con el mismo hash SHA-1 que un archivo dado que crear dos archivos usted mismo con el mismo hash SHA-1. Y hasta donde sabemos, nadie en ninguna parte del mundo ha logrado incluso esta tarea más fácil. Sin embargo, eso no significa que no pueda suceder mañana.

David Schwartz
fuente
¿Existe incluso un ataque conocido en SHA-1 por colisiones con un archivo determinado? Tenía la impresión de que ese ataque no se había encontrado para MD5 o SHA-1 (solo hay un ataque de colisión, no un segundo ataque de preimagen)
cpast
@cpast el malware Flame usó una colisión MD5 para parecer de Microsoft y secuestrar Windows Update. Es posible que hayan tenido un montón de certificados de Microsoft para elegir, pero no solo estaban tratando de encontrar 2 archivos con el mismo MD5.
Aron Foster
2
@Aron No, ese no fue un ejemplo de una colisión con un archivo determinado. Con Flame, Microsoft tenía un servidor de licencias que firmaría certificados X.509 de acuerdo con una solicitud de firma de certificado, lo que significa que el atacante controla lo que se firma dentro de algunos límites. No había un certificado preexistente con el que encontraron una colisión; Microsoft firmó CSR de los clientes como parte de la activación, que permite el uso de un ataque de colisión (que no es un segundo ataque de preimagen).
cpast
2
@OlivierDulac No, de hecho nunca se ha hecho. No se conocen colisiones SHA-1. El costo estimado es sólo una estimación - no es que alguien lo hizo y esto es lo mucho que creo que cuesta, es que nadie lo ha hecho, pero creemos que se trata de cuánto sería el costo.
cpast
44
@cpast No sabemos con certeza si se ha realizado o no, pero un ataque de $ 3 millones es menos del 0.03% del presupuesto anual de la NSA (de hecho, el ataque debería ser más barato dado que ya poseen el hardware y no tiene que alquilar). Es razonable concluir que, dado que tienen los medios y la motivación para hacerlo, probablemente ya lo hayan hecho. Recuerda Llama .
bain
26

Es teóricamente posible, pero aún no se ha hecho.

Lo que está buscando se llama "colisión de hash": dos archivos con el mismo hash. Los códigos hash criptográficos como SHA-1 generalmente están diseñados para dificultar esto. Debido a que SHA-1 es un código de 160 bits, tomará en promedio 2 ^ 159 intentos de fuerza bruta para encontrar un duplicado. Si se encuentra un algoritmo que funciona mejor que eso contra un hash criptográfico, el hash se considera "roto".

MD-5 es un ejemplo de un hash muy roto. Se suponía que tenía una potencia de 128 bits, lo que requería un promedio de 2 ^ 127 intentos. Como es, abusando de las vulnerabilidades conocidas, el número real de intentos necesarios puede ser tan bajo como 2 ^ 47. Esto es MUCHO menor que 2 ^ 127. De hecho, se ha realizado en menos de un día en un clúster informático moderno.

Doy ese ejemplo porque está más cerca de cómo estás buscando usar SHA-1. Sin embargo, ese no es el enfoque de criptoanálisis más común que se utiliza para asegurarse de que los hash no se rompan. Por lo general, permiten una colisión entre dos archivos, según lo elija el atacante, en lugar de hacer que elija un archivo y que el atacante busque igualarlo. Este tipo de ataque tiene la ventaja de ser más fácil de comparar. Si encuentro que es "difícil" descifrar su archivo, ¿eso significa que otro archivo es igualmente fuerte? Este ataque en el que el atacante puede elegir ambos archivos asegura que atrapemos lo peor de lo peor.

Este tipo de ataque permite un truco interesante conocido como el " ataque de cumpleaños ". En pocas palabras, el uso del ataque de cumpleaños reduce a la mitad la fuerza del algoritmo, por lo que SHA-1 requiere 2 ^ 80 intentos (en promedio) y MD5 requiere 2 ^ 64 intentos (en promedio). Estos son la mitad de 160 y 128 respectivamente.

SHA-1 ha conocido ataques que disminuyen su fuerza de 2 ^ 80 a 2 ^ 69. Esto no te va a importar mucho. 2 ^ 69 intentos es mucho tiempo.

Sin embargo, a partir de la historia, hemos descubierto que los algoritmos hash no se rompen espontáneamente, sino que se rompen con el tiempo. Nadie descifra un algoritmo como MD-5 llevándolo de 2 ^ 64 a 2 ^ 47 durante la noche. Ocurre con el tiempo, ya que muchas personas publican artículos sobre las matemáticas que están usando en su contra. Por lo general, se puede observar que la complejidad de los ataques disminuye lentamente desde el inicio del algoritmo (donde el mejor ataque suele ser el ataque de cumpleaños).

El hecho de que estamos viendo algunos cambios en las colisiones sugiere que SHA-1 está viendo la luz al final del túnel. Todavía es fuerte, pero puede haber un deseo de subir al nuevo SHA-3 que actualmente es mucho más seguro.

Realmente debería tomar tales decisiones desde la perspectiva del modelo de amenaza. Cuánto daño puede hacer un atacante si obtiene una de estas colisiones. ¿Sus atacantes escriben a los niños con acceso a algunas computadoras portátiles, o gobiernos con grupos completos de supercomputación a su disposición? ¿Qué tan grande es el intervalo de tiempo que tiene un atacante para romper el hash antes de que sea inútil? Muchos usos de la criptografía implican un "cambio de guardia", como la rotación de la contraseña Todo esto afectará la seriedad con la que debe considerar las colisiones.

Cort Ammon - Restablece a Monica
fuente
8
Con respecto a su párrafo de ataque de cumpleaños, 2 ^ 80 es la raíz cuadrada de 2 ^ 160, no la mitad (que sería 2 ^ 159).
Andrew Morton
La pregunta es sobre los ataques de segunda preimagen, pero su respuesta es sobre colisiones. Ataques previos a la imagen contra SHA-1 y mdash; e incluso MD5 y mdash; son absurdamente impracticables. (Hay un ataque de preimagen de 2 ^ 123 contra MD5, pero con SHA-1 estás atrapado con una fuerza bruta de 2 ^ 160)
Matt Nordhoff
"Debido a que SHA-1 es un código de 160 bits, tomará en promedio 2 ^ 159 intentos de fuerza bruta para encontrar un duplicado". Pero un código 2 ^ 2 requiere 2 ^ 2 conjeturas. No veo por qué tú -1. "En pocas palabras," ... "" reduce a la mitad la fuerza del algoritmo, por lo que SHA-1 requiere 2 ^ 80 "..." MD5 requiere 2 ^ 64 "..." Son la mitad de 160 y 128 respectivamente ". Aquí deberías haber hecho -1'ed. Los bits se suman a la fuerza de manera exponencial, por lo que reducir a la mitad la fuerza de un hash de 160 bits lo trataría como un hash de 159 bits, no un hash de 80 bits. Cada bit duplica el desafío de un ataque de fuerza bruta.
TOOGAM
@TOOGAM: Dijo 'en promedio'; en múltiples ensayos, solo se debe buscar en promedio el 50% del espacio clave para tener éxito en un ataque de fuerza bruta. En cuanto al comentario a la mitad, el comentario anterior de Andrew Morton explica eso; debería ser la raíz cuadrada, no la mitad, de la complejidad.
Reid
@AndrewMorton buen punto, no estaba claro con mi redacción. Encuentro que la literatura cambia entre el número de estados y el logaritmo de base 2 del número de estados con bastante frecuencia. Mi redacción se refería a reducir a la mitad el número de bits porque la gente tiende a hablar de "fuerza" en número de bits. Estaba tan acostumbrado a cambiar de un lado a otro que lo hice inconscientemente. Lo editaré para eliminar la confusión.
Cort Ammon - Restablece a Mónica
8

Los defectos en SHA-1 discutidos en ese artículo son muy específicos: permiten a los atacantes crear dos cosas que tienen el mismo valor (esto se llama "ataque de colisión"). Sin embargo, un ataque de colisión requiere que el atacante controle ambos archivos involucrados. Si el atacante no controla el archivo original, un ataque de colisión no les permite encontrar otro archivo con el mismo valor hash.

La razón por la que esto es importante para TLS / SSL (y las firmas en general) es que con ellos, un atacante a menudo puede controlar ambos archivos. Un certificado TLS es creado principalmente por la persona que lo solicita (los bits que no controlan a menudo son predecibles), por lo que las colisiones les permiten hacer un certificado legítimo y uno ilegítimo, obtener el legítimo firmado y transferir la firma.

Para los archivos, no siempre se aplica la misma situación. Si le preocupa que la persona que crea el archivo sea el atacante (por ejemplo, verificará una cosa independientemente como buena y luego le enviará la carga maligna con el mismo hash), se aplica el ataque SHA-1, y debe mirar hacia su eliminación gradual (aunque todavía no es crítico, como lo mencionó David Schwartz). Si el archivo original es confiable, entonces un atacante no puede aplicar los ataques SHA-1 conocidos actualmente, aunque aún debería pensar en eliminarlo si puede (si tiene una opción, use un hash sin ataques conocidos como SHA- 2)


En respuesta a "la colisión no será útil": si bien un ataque no requiere que un atacante pueda obtener una colisión útil , generalmente no es tan difícil convertir la "colisión" en "colisión útil". Muchos formatos de archivo tienen bastante espacio en el que puede tener lo que quiera sin afectar la funcionalidad del archivo; un atacante generalmente puede modificar eso para obtener una colisión (si las colisiones son prácticamente encontrables), mientras mantiene la parte funcional como lo que quieran. La brecha entre "ataque académico" y "ataque práctico" puede ser grande; la brecha entre "cualquier colisión" y "colisión útil" es generalmente mucho menor.


El problema más grave, que no está relacionado con la elección del algoritmo, es cómo se obtiene el hash. Todo lo que hace un hash es cambiar el problema de "obtener el archivo real" a "obtener el valor real de hash"; un valor de hash enviado desde el mismo servidor y sobre el mismo tipo de conexión que el archivo no tiene ningún valor contra modificaciones maliciosas (cualquier atacante que pueda alterar el archivo puede alterar el hash). Los hash solo son útiles para esto si puede confiar en el hash más de lo que puede confiar en el archivo; Si bien ese es a veces el caso (torrentes, espejos), a menudo se usan cuando no es el caso. Por lo tanto, debe tener mucho cuidado al usar hash para la verificación de integridad.

cpast
fuente
5

Tienes que diferenciar entre un ataque de colisión y un ataque de preimagen . Encontrar dos mensajes que tengan el mismo valor hash es un ataque de colisión.
Reemplazar un mensaje dado en particular (aquí: un ejecutable) con otro mensaje que tiene el mismo hash es un (segundo) ataque de preimagen.

SHA-1 se rompe en la medida en que se puede realizar un ataque de colisión en 2 52 operaciones de acuerdo con un artículo de Wikipedia que no proporciona una cita para ese número (el mejor ataque que sé que es realmente creíble es el de Marc Stevens , que toma 2 60 operaciones). Pero supongamos el caso pesimista de 2 52 .

Esto es preocupante porque un ataque a esa escala no solo es teóricamente concebible, sino que de hecho es perfectamente factible en menos de un día en un equipo multi-GPU. Eso es, por supuesto, un problema para las aplicaciones donde funcionarán los "dos mensajes". Incluso la cifra 2 60 dada por Stevens (que es 256 veces más trabajo) es perfectamente factible si su atacante está dispuesto a arrojar algo de dinero extra al problema, o está dispuesto a pasar un año de tiempo.
Que es exactamente el tipo de cosas que no evitarán que alguien involucrado en espionaje o delito cibernético falsifique certificados.

Ahora, un ataque de preimagen tiene un exponente que es dos veces mayor, por lo que suponiendo 2 52 para el ataque de colisión, serían 2 104 operaciones, que es un estadio totalmente diferente.

Esto no solo no es práctico (una máquina que es mil millones de veces más rápida que la mencionada en el párrafo anterior aún tomaría alrededor de 6 millones más o menos), sino que dado nuestro medio insignificante de generar energía, esto es completamente imposible.

Hacer un cálculo tan masivo requeriría una fuente de energía que es mucho más grande que cualquier cosa que podamos permitirnos dedicar a una sola operación. No, no es una fuente de energía del tamaño del sol, pero sigue siendo bastante grande .

Realmente puede esperar obtener de 10 a 50 GFLOPS de un vatio. Suponiendo que ocurra algún tipo de milagro y que los procesadores obtengan varios miles de veces más energía eficiente durante la noche, uno podría asumir 1 SHA ≈ 1 FLOP (¡bastante optimista!). Esto significaría que para realizar 2 104 cálculos de hash en 10 años, necesita una planta de energía de 10 12 W. Para ejecutar el ataque dentro de 1 año, necesita una planta de energía de 10 13 W. Eso es aproximadamente 50 veces más de lo que pueden producir juntas las centrales nucleares de Estados Unidos, Francia y Japón, solo para forjar un solo hash.

Esto no va a suceder , hay formas mucho más fáciles de lograr el mismo objetivo (explotar el servidor que almacena el hash original y reemplazarlo, chantajear a alguien, etc.).

Damon
fuente
"... formas mucho más fáciles de lograr lo mismo ..." Como se ilustra en xkcd.com/538
Ralph J
2

El punto general del artículo al que se hace referencia en la pregunta es: SHA1 está en desuso y debe eliminarse gradualmente mientras todavía tenga tiempo para hacerlo sin problemas. En algunas áreas, se está acabando el tiempo desde que Google y Microsoft aplican los plazos.

Regla de oro para tecnología obsoleta :

  • Si hace un nuevo diseño o agrega características, no lo use (SHA1).
  • Si mantiene algo viejo, planifique cuándo reemplazarlo (SHA1).

Resumen de la cita del blog de 2012 de Bruce Schneier: "El punto es que nosotros en la comunidad necesitamos comenzar la migración lejos de SHA-1 y ahora a SHA-2 / SHA-3".

jmn
fuente
2

Para la parte de colisión de hash SHA-1 de su pregunta, esto se ha abordado en algunas de las respuestas.

Sin embargo, una gran parte de esto depende del tipo de archivo con el que estamos trabajando:

Mantiene el contenido general y la operación del archivo (pero, por supuesto, ahora incluye contenido malicioso que originalmente no tenía contenido modificado)

Lo que esto significa varía mucho según lo que detecte las alteraciones:

  • Si se trata de un ejecutable firmado, no es una posibilidad (razonable): de alguna manera, tendría que obtener dos colisiones hash: el SHA-1 del archivo y la firma .exe interna.
  • Si se trata de un ejecutable sin firmar, .com, .dll sin firmar, o similar, se pueden agregar sus tenedores de recursos de manera que no cambien su funcionamiento y, por lo tanto, podría (eventualmente) obtener una colisión de hash que no es detectable por 'normal' operación.
  • Si se trata de un archivo de código fuente o estructura similar (.cs, .c, .h, .cpp, .rb, .yml, .config, .xml, .pl, .bat, .ini), las adiciones, modificaciones o eliminaciones puede limitarse a una sintaxis de comentario válida de modo que el cambio no sea discernible para la mayoría de los usos (compilarlo o ejecutarlo, no abrirlo con un editor de texto).
  • Si es un .iso o .zip u otro formato de contenedor, también es más improbable ya que la mayoría de los cambios aleatorios dañarán el contenedor. Es posible hacer: agregar una entrada de archivo falsa o alterar un contenido dentro del contenedor y volver a verificarlo, pero está agregando una capa de complejidad y agregando tiempo adicional para verificar el resultado, así como tener grados limitados de libertad con respecto a cómo y qué contenido se puede cambiar.
  • Si se trata de un texto o un formato similar al texto, se pueden cambiar casi de la manera que desee sin dejar de ser un archivo "válido", aunque el contenido probablemente sea notable.
  • Con muchos formatos como .rtf, .doc, .html, .xslx y otros formatos de marcado, pueden agregarse o modificarse de manera que los analizadores no puedan detectarlos, de modo que no sea la longitud (o incluso con una longitud limitada , menos libertad) los archivos pueden ser alterados para (eventualmente) tener una colisión hash mientras siguen siendo no solo un archivo válido, sino que no se cambian notablemente de ninguna manera que sea visible para las aplicaciones típicas con las que se usarían.

Entonces, lo que te queda es cómo obtener colisiones en cualquier estructura que no sea corrupta y que, en cierto grado, sea indetectable:

  1. Realice los cambios funcionales que desee (tal vez la inserción de contenido malicioso) y realice cambios adicionales para conservar la validez específica del formato de archivo
  2. Agregue una sección que no será funcional (entre los bloques de comentarios, al final de un archivo de texto con 3k retornos de carro por encima, aísle un bloque de comentarios actual)
  3. Agregue o seleccione un carácter / punto de código / byte para modificar y pruebe todas las combinaciones válidas posibles (por ejemplo, no todas las combinaciones de bytes son válidas para diferentes codificaciones).
  4. Vuelva a calcular el hash, vea si la colisión coincide.
  5. si no es así, pase a 3.

Supongamos que tiene una computadora súper rápida y un archivo más pequeño, de modo que la modificación con una secuencia de bytes válida y volver a calcular el hash toma 1 milisegundo (probablemente requiera un hardware dedicado). Si la distribución de hash es perfectamente aleatoria y se distribuye en todo el rango, obtendrá una colisión con SHA-1 cada 2^160intento (fuerza bruta).

2^160/1000/60/60/24/365.24 
= 4.63x10^37 years 
= 46,300,000,000,000,000,000,000,000,000,000,000,000 years 
= 46 undecillion years.

Pero bueno, intentemos con las versiones 2^60y 2^52, y pretendamos que nos permiten modificar el archivo de la forma que queramos (no lo hacen) y que ellos también se pueden hacer en 1 ms en cada intento:

2^52 yields 142,714 years 
/*humans might still be around to care, but not about these antiquated formats*/
2^60 yields 3.65x10^7 years = 36,500,000 years 
/*machines will probably have taken over anyway*/

Pero oye, podrías tener suerte. Realmente, realmente, más de un milagro que cualquier cosa que la gente llame milagros con suerte.

Ehryk
fuente
0

En realidad no, puede satisfacer una de esas condiciones a la vez, pero no ambas ... es posible obtener el mismo hash para dos archivos diferentes, pero que alguien altere un archivo y luego intente obtener el mismo hash es casi imposible. hasta donde sé

Anthony Guess
fuente
1
Bastante imposible todavía . Con suficiente potencia informática, todo es posible.
-6

Sí, es posible. Piense en cómo funcionan los virus en los EXE. La carga útil del malware se agrega al EXE original, de modo que el programa sigue haciendo lo que hizo originalmente, pero también se propaga como un virus. Ahora, para mantener el mismo hash, necesitaría un relleno adicional específicamente diseñado .

Eso significa que el archivo sería más grande. Pero en el caso de un EXE, tal vez podría eliminar parte del código menos utilizado, para que el programa solo parezca funcionar inicialmente. En el caso de un JPEG, puede comprimir la imagen aún más o usar una imagen completamente diferente. Para un ISO, puede eliminar conjuntos de archivos. Los cálculos necesarios para replicar el hash serían más difíciles y quizás matemáticamente imposibles para casos específicos, pero aún serían posibles en general.

Conocer
fuente
77
-1 todo en esta publicación está completamente inventado. Los ataques de extensión de longitud no "mantienen el mismo hash" (el hash solo cambia de una manera conocida) . Además, no hay ninguna razón por la que un virus tenga que eliminar "el código menos utilizado" (¿cómo podría determinar qué es eso?) . ¿Y qué tienen que ver los jpegs con nada?
BlueRaja - Danny Pflughoeft
2
Esto es totalmente incorrecto, ni siquiera puedo comenzar a sugerir correcciones sin reescribir toda la respuesta
Mark K Cowan
2
-1 No está bien en absoluto. alias "Ni siquiera está mal" (Wolfgang Pauli)
Olivier Dulac
1
Bueno, podríamos comenzar con el hecho de que si algo es posible en general , obviamente es posible en un caso específico . Sin embargo, lo contrario no siempre es cierto: es fácil imaginar un problema que pueda resolverse para un caso específico, pero no de manera general.
un CVn