SHA1 demo de colisión/ejemplo

Question

Esta pregunta es similar a this, pero esa solo hace referencia a demos de colisión MD5.

¿Hay pares de colisiones SHA1 reales de mensajes arbitrarios conocidos hasta ahora?

Me gustaría usar estos para probar cómo varios productos de software (el mío y el tercero) se ocupan de ello.

Al hacer algunas búsquedas en Google solo aparecieron las oh-tan prominentes colisiones MD5/SHA0 y algunos consejos sobre cómo abordar las colisiones SHA1, pero no pude encontrar ningún ejemplo.

Answer 1

La primera colisión conocida ahora ha sido publicado en https://shattered.it/

Answer 2

Hay un ejemplo en el documento Collision Search Attacks on SHA1 de Wang, Yin y Yu, de 2005, pero solo para la versión debilitada de 58 rondas de SHA-1. (El completo y oficial SHA-1 realiza 80 rondas.)

3 A collision example for 58-step SHA1 

     h₁ = compress(h₀,M₀) = compress(h₀,M'₀) 
_____________________________________________________ 
    h₀: 67452301 efcdab89 98badcfe 10325476 c3d2e1f0 
_____________________________________________________ 
    M₀: 132b5ab6 a115775f 5bfddd6b 4dc470eb 
     0637938a 6cceb733 0c86a386 68080139 
     534047a4 a42fc29a 06085121 a3131f73 
     ad5da5cf 13375402 40bdc7c2 d5a839e2 
_____________________________________________________ 
    M'₀: 332b5ab6 c115776d 3bfddd28 6dc470ab 
     e63793c8 0cceb731 8c86a387 68080119 
     534047a7 e42fc2c8 46085161 43131f21 
     0d5da5cf 93375442 60bdc7c3 f5a83982 
_____________________________________________________ 
    h₁: 9768e739 b662af82 a0137d3e 918747cf c8ceb7d4 
_____________________________________________________ 

Table 2: A collision of SHA1 reduced to 58 steps. The two 
messages that collide are M₀ and M'₀. Note that padding 
rules were not applied to the messages. 

Answer 3

Como del 23 de febrero de 2017 esta respuesta ya no es exacto.

For more than six years, the SHA1 cryptographic hash function underpinning Internet security has been at death's door. Now it's officially dead, thanks to the submission of the first known instance of a fatal exploit known as a "collision."

No hay colisión conocido para SHA-1 todavía. Ahora mismo:

• Hay algunas colisiones en reducidos versiones de SHA-1, con menos de las 80 rondas de la norma SHA-1.
• Un algoritmo ha sido describir, que debe obtener una colisión SHA-1 con un esfuerzo de cálculo más o menos equivalente a 2 invocaciones de SHA-1 en los mensajes pequeños; eso es mucho mejor que los algoritmos genéricos (que requieren 2 invocaciones en promedio) pero eso todavía es bastante grande y ese algoritmo no se ha ejecutado aún.

Hubo un esfuerzo por obtener una colisión SHA-1 mediante el aprovechamiento de la energía de la persona que realizó algunos ciclos de reloj de la CPU de repuesto para donar, con el marco BOINC para organizar todo el asunto, pero no había suficientes voluntarios y el esfuerzo fue abandonado el año pasado. Por lo tanto, todavía no hay una colisión SHA-1 real.

Los ataques teóricos se basan en algunas suposiciones que pueden ser ligeramente falsas; por ejemplo, el ataque a MD5 es en realidad un poco más rápido de lo esperado (en algún momento hay una propiedad que debe cumplirse, con una probabilidad teórica de 2 ^-28, pero en la práctica es más como 2 ^-27.7 , es decir, el ataque es un 20% más rápido de lo previsto). Todavía se considera que el ataque teórico es correcto y la complejidad "bastante precisa".

Answer 4

Blog Seguridad de Google describe la primera pública, intencional SHA-1 Collision aquí: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

enlaces directos a los 2 archivos PDF con el mismo SHA-1 (de la site dedicated to this finding):

• https://shattered.it/static/shattered-1.pdf
• https://shattered.it/static/shattered-2.pdf

Una vez más, Marc Stevens estuvo involucrado junto con CWI Amsterdam y algunos empleados de Google, pero esta vez para la ronda completa de SHA-1 en dos archivos PDF construidos.

Stevens also notes que, debido a SHA-1 Merkle-Damgård construction, ambos 2 PDF se pueden ampliar (adjuntar) con los mismos datos arbitrarios para producir versiones más largas hash para el mismo compendio.

Aparentemente, Google publicará el código fuente que lo acompaña en 90 días a partir de ahora (23 de febrero de 2017), brindando a los proveedores de sistemas afectados algún tiempo para actualizar sus cosas.

Todavía está por verse cómo un software como git y proveedores de servicios como GitHub lidiarán con esto, especialmente en términos de compatibilidad con versiones anteriores.

Linus Torvalds tiene issued a statement regarding git, teniendo en cuenta que migrarán a hashes más nuevos de forma compatible, pero que llevará tiempo.

Por cierto, el "roto" demostración de colisión no afecta a Git (sin modificaciones), ya que utiliza SHA-1 como esto:

sha1("blob " + <size in octets as text> + "\0" + <contents>) 

, usted puede obtener el hash git utilizando git hash-object <file path>, incluso si el archivo no está en git.

En related news, Subversion seems to be the first real victim de esta prueba, causando daños en el repositorio, haciendo que los archivos mencionados sean exploits prácticos.

- ANTERIORMENTE ... -

Un 76-round collision fue encontrado por Marc Stevens.

criptógrafo Jean-Philippe Aumasson, co-creador de BLAKE y SipHash e iniciador de la Password Hashing Competition (PHC), adivina una colisión SHA-1 en las 80 rondas completas will have been found by 2020.

Según ongoing research by Marc Stevens et al. published in October 2015,

... calculamos la colisión SHA-1 cuesta hoy (es decir, Fall 2015) entre 75K $ 120K y $ alquiler de Amazon EC2 computación en la nube a través de una pocos meses. Por el contrario, el experto en seguridad Bruce Schneier previamente proyectado el costo de colisión SHA-1 para ser ~ $ 173K por 2018.

También describen un ataque de colisión para la función de compresión de SHA-1.

Answer 5

No exactamente SHA1 colisión, pero hay colisiones de PBKDF2-HMAC-SHA1 mensaje de código de autenticación de mensaje.

Por ejemplo, PBKDF2 (SHA1, contraseña, sal, iteraciones, dkLen) de las dos contraseñas plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd y eBkXQTfuBqp\'cTcar&g*, sal hunter2, 4 iteraciones, proporcionar el mismo valor (35d1c8f259129dc800ec8e073bb68f995424619c para dkLen 20).

De hecho, es trivial encontrar tales colisiones para cadenas de más de 64 bytes.

Otro ejemplo de colisión (python3):

>>> import hashlib, binascii 
>>> def pbkdf2sha1hex(x, salt, iters): 
...  h = hashlib.pbkdf2_hmac('sha1', x, salt, iters) 
...  return binascii.hexlify(h) 
>>> pbkdf2sha1hex(b'http://stackoverflow.com/questions/3475648/sha1-collision-demo-example/31136714', b'NaCl', 1000000) 
b'20177527e04e05d5e7b448c1ab2b872f86831d0b' 
>>> pbkdf2sha1hex(b'\x8c\xbf8\x94\xbc\xf4\xbe\x90xT,r\xbc\x03\xd1\xed\xd9\xea\xfb\x9f', b'NaCl', 1000000) 
b'20177527e04e05d5e7b448c1ab2b872f86831d0b' 

Tenga en cuenta que el mismo "problema" se aplica a PBKDF2-HMAC-SHA256 así:

>>> h1 = pbkdf2_hmac('sha256', b'http://stackoverflow.com/questions/3475648/sha1-collision-demo-example/31136714', b'NaCl', 1000000) 
b"\xcf\xc5\xee\x15=\r\x0b\x0e\x89r\x9b\xe1\xb7'+\xa4'o\x98kn++u\x12\xec\xd9\xec\xea\xebL\xb7" 
>>> h2 = pbkdf2_hmac('sha256', b'.\x83\xb0D\x93D\x9f\x162\xf3\xd4x\xb6\x1a\x9f-\x1f\xdb\xdc\xa4\x8f\xb3\x95Y5\xea\x99*\x97\x00V\x81', b'NaCl', 1000000) 
>>> h1 == h2 
True 

Todo sucede, porque de la definición PBKDF2, para cadenas largas, contiene:
PBKDF2(hashalgo, s, ...) == PBKDF2(hashalgo, hashalgo(s), ...).

Más información, p. aquí: https://mathiasbynens.be/notes/pbkdf2-hmac