Google anuncia la primera colisión de SHA1 [ENG]

Funciones criptografícas como SHA-1 son la navaja suiza de un criptógrafo. Las funciones hash se usan en la seguridad del navegador, manejando repositorios de código, o incluso detectando archivos duplicados. Estas funciones comprimen grandes cantidades de información en pequeños mensajes (hash). Como requisito criptográfico para su uso extendido, encontrar dos mensajes que lleven al mismo hash debería ser computacionalmente inviable.[...]10 años desde que SHA1 fue introducido, anunciamos la primera técnica para generar una colisión.

[#2 Desactivado]

Ese titular ...

No se trata de "la primera colisión", sino de la primera técnica factible para generar colisiones.

[#44 Desactivado]

#35 En primer lugar, en criptografía una contraseña y una clave no son exactamente lo mismo. La contraseña (password) es lo que tú escribes, que puede ser más o menos larga y utilizar un conjunto más o menos amplio de caracteres. En cambio una clave (key) es un valor binario de una longitud fija dada por el algoritmo a usar. Por ejemplo, DES utilizaba claves de 56 bits, y AES puede usar claves de 128 ó de 256 bits. El primer paso por tanto es generar una clave a partir de la contraseña utilizando una función de derivación de claves (https://en.wikipedia.org/wiki/Key_derivation_function).

Para romper por fuerza bruta un cifrado simétrico con longitud de clave n, habría que probar 2^n combinaciones. Un computador cuántico permitiría aplicar el algoritmo de Grover (https://es.wikipedia.org/wiki/Algoritmo_de_Grover), que permite reducir un algoritmo de complejidad O(n) a O(√n), por lo que en este caso el número de combinaciones pasarían a ser 2^(n/2). Es decir, que la longitud efectiva de la clave sería de la mitad.

Por tanto, AES-128 tendría una fortaleza efectiva de 64 bits, pero la solución sería tan sencilla como usar AES-256.

[#11 Desactivado]

#8 No. SHA es para sacar un hash ("firma digital", si quieres) de un chorro de datos que le pases, AES en cambio es un sistema para cifrar dichos datos.

[#25 Pitt]

#2 #6 #12 Si no ha habido colisiones hasta ahora, aunque se supiera teóricamente, y ahora hubo la primera colisión práctica... pues hubo la primera colisión y el titular es correcto.

[#1 Desactivado]

Putos coches autónomos.

[#6 Vio]

#2 Primera colisión (que se sepa) y primera técnica para lograrla... el título está bien.

[#80 Desactivado]

#12 #25 a ver, solo de manera aclaratoria. Todas las funciones hash tienen infinitas colisiones de manera matematica dado que la longitud del hash (la salida) es finita (aunque pueda ser inmensamente grande) y se puede aplicar sobre entradas mas grandes que la longitud de salida. En cristiano, si tuviera una funcion hash de longitud dos, el tercer valor que meta va a colisionar con uno de los dos anteriores. Se considera que el sistema no es seguro cuando se pueden generar a voluntad dichas colisiones. Dado que, por ejemplo, una contraseña "love" no se almacena en claro, si un hacker intercepta la comunicacion o roba la base de datos lo que va a ver es el hash de dicho password. Y con ese hash no puede conocer de ninguna forma la contraseña original. Pero si hay metodos de generar otro pass, por ejemplo "ajTq61" que colisiona con ese hash original, no necesita la contraseña, le vale con algo que de la misma colision.

[#33 Desactivado]

#c-25" class="content-link" style="color: rgb(227, 86, 20)" data-toggle="popover" data-popover-type="comment" data-popover-url="/tooltip/comment/2739157/order/25">#25 La cuestión es que el titular no es informativo ni ayuda a que personas con menos conocimientos criptográficos sean conscientes de la gravedad del asunto.

No es lo mismo que se haya encontrado UNA colisión (i.e. "Hola Mundo" y "j983rO#@jro23" tienen el mismo hash) , que que se haya descubierto un método para generar documentos arbitrarios con un hash concreto, cosa que tiene muchas implicaciones de seguridad.

[#12 John_Doe]

#6 No, el título no es correcto.
Es la primera colisión práctica. Se sabía ya (y se ha demostrado) que las colisiones eran posibles y factibles, y obviamente faltaba hacerlo de forma práctica, y cuando se lograse (ahora) se podría demostrar empíricamente, pero teóricamente ya se ha demsotrado que la colisión era una realidad.

[#4 Desactivado]

Miedito los dos pdf con diferente contenido pero el mismo hash. Los he bajado y sí sí, no hay trampa ni cartón.

[#27 Desactivado]

#16
El DNIe 3.0 utiliza SHA1 y SHA256
Tendrán que invalidar el SHA1.
Las tarjetas criptográficas de la FNMT usan SHA1, sólo: http://www.cert.fnmt.es/catalogo-de-servicios/tarjetas-criptograficas

[#118 Desactivado]

#69 No, lo que él ha dicho es correcto, y se llama el principio del palomar o principio del agujero de pichón: https://es.wikipedia.org/wiki/Principio_del_palomar

En álgebra no, a mí me lo enseñaron en la asignatura de cálculo

[#32 apetor]

#11, #8
Hash > resumen o huella digital.
Firma > Hash de lo que se quiere firmar que después se cifra con la clave privada de un par de claves ( clave pública + clave privada, de algoritmo asimétrico ).

Ese hash cifrado se pone a disposición del destinatario de el documento/loquesea junto al mismo documento/loquesea.
Para comprobar la validez del documento/loquesea, el destinatario descifra el hash cifrado usando la clave publica del firmante o emisor del documento/loquesea ( que se obtiene del certificado que el firmante ha facilitado anteriormente ) y después se compara con otro hash obtenido del documento/loquesea en el momento de comprobación de firma; si ambos, el hashe de ese momento de comprobación de firma y el hash descifrado con la clave pública del firmante/emisor coinciden, el documento es válido o la firma coincide.

AES-256 es un algoritmo de cifrado SIMÉTRICO ( misma clave para cifrar que para descifrar ).

[#110 Marx]

#97 Te has hecho la picha un lío.

Teóricamente todos los algoritmos de hash tienen colisión, por pura lógica, no hay que ser un genio para saberlo.

Encontrar "en la práctica" la primera colisión es igual a encontrar la primera colisión, así, a secas. Esta es la primera colisión encontrada, punto y pelota, el titular es correcto, Google anuncia la primera colisión.

Después la teoría dice que SHA1 tiene colisiones (anda, como todos, vaya obviedad) y que además en SHA1 se demostró que se pueden hacer en menor coste que fuerza bruta, muy bien, pero la teoría no encontró ninguna colisión, tan solo te dijo que se puede hacer.

[#46 Vio]

#33 Efectivamente, no es lo mismo, pero en este caso se dan ambas opciones.

#2 #12 Se sabía que era inseguro, y de hecho en el artículo mencionan que Google lleva años pidiendo dejar de usarlo. Pero no entiendo qué problema tenéis con que hayan encontrado la primera colisión. Lo mismo podríais dirigir vuestras preocupaciones a los de Google, y lo mismo ellos os pueden resolver las dudas El titular no me lo he inventado yo (por si alguien no se había fijado).

#25 Gracias por intentar ayudarme

[#58 Desactivado]

#24 Ahora pongamos que después de 1 año / 100 (unos 4 días) corriendo 110*100 GPUs (lo puedes hacer con los servicios cloud), logras una colisión y obtienes dos solicitudes de firma de certificado SSL, una para "midominiosinsentido.com" y otra para "google.com". Ahora le envías la de "midominiosinsentido.com" a Symantec para que te la firme, pagas los $1000 que cuesta un certificado EV... y cuando te lo envíen, copias la firma en el de "google.com" que tenía el mismo hash.

Después, imagina cuánto puede ganar alguien que ofrezca WiFi gratis o se cuele en los routers de quien ofrece WiFi gratis, que tenga acceso a certificados para "bancosantander.es", "facebook.com" o cualquier otra web en la que metas una contraseña, y de la que pueda robar dinero, datos, o lo que sea.

[#39 zarr]

#12 Lo dices como si la demostración teórica fuera necesaria:
- Sea una función que mapea 'muchos bits' a 'pocos bits'.
- Con 'pocos bits' no se puede describir el mismo espacio que con 'muchos bits'.
- Por tanto, al menos hay dos secuencias de 'muchos bits' que generan la misma secuencia de 'pocos bits'.
Queda demostrado.

[#29 Desactivado]

#3 ¿Quieres probarlo de verdad? Empieza con esto: https://hashcat.net/hashcat/

O por ejemplo, para romper contraseñas del RAR prueba con esto: http://www.crark.net

Yo hice la prueba, y mi ordenador daba 12000 contraseñas por segundo, tardó casi 20 minutos en reventar una contraseña de 4 caracteres. ¿Cuánto tardaría en reventar una contraseña de 10 caracteres? 2 millones de años. ¿Una de 16 caracteres? Casi un trillón de años. Aunque pusieras mil millones de máquinas en paralelo, no podrías hacerlo por fuerza bruta.

Y la computación cuántica aplicada a la criptografía simétrica lo más que hace es reducir la longitud de la clave a la mitad, así que con duplicarla volveríamos a estar como antes.

[#59 dagavi]

Es cierto que colisiona el sha1, pero no el md5, así pues acabo de salvar el mundo con mi nuevo algoritmo el sha1+md5:
fileEq(file, sha1Check, md5Check): return sha1(f1) == sha1Check and md5(f1) == md5Check

[#9 JungSpinoza]

#1 Los autónomos de este país estamos muy jodidos

[#3 Desactivado]

Y con SHA256 pasará lo mismo. Cuando la gente dice "para romper X cifrado, se necesitan más años que la edad del universo". Bien, pon sistemas en paralelo con CUDA, veamos cuánto tarda de verdad. Y con la tecnología cuántica, ya olvídate.

[#99 Vio]

#97 Tú me estás hablando de otra cosa y la mezclas con que el titular es erróneo. Si te vas a poner tiquismiquis entonces también decir que en 2005 no se demostró que haya colisiones, porque colisiones por haberlas hailas, lo que pasa es que no se pueden computar. Nos estás hablando con un tono como si fuéramos tontos, pero es que simplemente no nos estás entendiendo, y tú tampoco eres el más riguroso al expresar tus ideas (totalmente comprensible en un foro distendido y no técnico).

En 2005 se probó que había colisiones en menor coste que fuerza bruta, es decir, que se puede romper. Google te está diciendo que lo ha roto, y que ha conseguido la primera colisión y que ha encontrado una fórmula para hacerlo (además en menor coste de lo que se dijo en 2005). Te están diciendo que son los primeros en demostrar que es inseguro? No, además te dicen que llevan años quejándose de su uso. Te estoy diciendo yo que se podría enfocar la noticia de otra manera, o que lo de 2005 es más o menos importante? No. Te estoy diciendo que el titular no es erróneo.

He citado exáctamente lo que tenía que citar, que dices que sí cuando es que no, para confundir a una persona que te está preguntando sinceramente, y lo único que quieres es demostrar lo listo que eres. Pues nada, para ti la perra gorda. Quien quiera entender que entienda.

[#13 Desactivado]

#10 Lo que dices es básicamente así y los sistemas antiguos de hash han ido cayendo poco a poco con el paso del tiempo. Pero SHA1 ha sido muy, muy duro de pelar. 160 bits se han quedado cortos al final, al mismo tiempo que, supongo, habrán encontrado debilidades en el propio algoritmo.

[#82 Desactivado]

#66 Deja las drojas y léete la noticia:

In 2013, Marc Stevens published a paper that outlined a theoretical approach to create a SHA-1 collision.

the SHA-1 shattered attack is still more than 100,000 times faster than a brute force attack which remains impractical.

Lo que hay "años después" son datacenters con millones de GPUs capaces de resolver el problema en un tiempo razonable cuando lo simplificas 100.000 veces. Es algo que lleva pasando durante décadas, y seguirá pasando. No hacen falta ni conspiraciones de la NSA, ni ordenadores cuánticos (que según D-Wave los hay, pero ese es otro tema), ni nada parecido.

[#60 fugaz]

#38 Se me ocurre un ataque en 2 pasos.
En la primera sincronización cambias el fichero por otro cualquiera. En la segunda lo cambias por el que tiene el troyano que tiene el mismo sha1 que el original.

Tu tendrás a partir de entonces un fichero troyano pero aunque te sincronices con otra gente, como el sha1 coincide, ni lo transmites ni te lo sobreescribes. Hasta que se cambie el fichero.

Si a mi se me ocurren formas de explotarlo, no te digo lo que se le ocurrirá a los expertos...

[#119 santiagogf89]

#22 #15 #13 #10 Que pueda pasar en teoría y que pase en la realidad son dos cosas diferentes. Al igual que hay un número finito de resultados de SHA-1 (2^160...una auténtica barbaridad) también hay un número finito de archivos en internet.

La noticia no es que haya pasado por casualidad, es que se ha encontrado un método "fácil" de engañar al hashing y generar la misma huella dactilar para dos archivos.
SHA-1 se considera "hackeado" desde hoy, pero no significa que cualquier friki con su ordenador pueda generar un SHA-1 idéntico para dos archivos. Hace falta mucha potencia de cálculo (110 años de cálculo de GPU son MUCHAS operaciones matemáticas) y muchas condiciones de partida.

En cualquier caso, ya se sabía, no es fácil de hacer en la práctica y ya hay nuevos algoritmos mucho más seguros y complejos y el uso de SHA-1 está desaconsejado desde 2011.

[#10 Wallack]

Pero en teoría esto es esperable no? cualquier hash o resumen es, al final eso, un string con menos longitud que el original y obviamente hay más combinaciones posibles en un documento más grande que en el resumen generado por lo tanto al final debería haber una colisión no? o hay algo que yo no entiendo?

[#15 Wallack]

#13 estaba leyendo un poco ahora mismo sobre las colisiones con md5 que era el que se usaba cuando yo estudiaba básicamente y ya veo. Lo que puedo imaginarme es que ya existiesen colisiones pero que no se conociesen, yo que sé, un password de un foro chino y un hash de un driver de linux por decir algo. A la larga tendría que pasar, lo que pasa es que ha debido de pasar y nadie miró y esto que han descubierto ahora es la forma de forzarlo por lo que veo.

Claro que si obtienes el hash de un password y eres capaz de generar con otra password el mismo hash si que es un problema gordo pero entre que imagino que las posibilidades sean cercanas a "ni de coña" y que la gran mayoría usan un seed no debe afectar mucho, pero me ha resultado muy curioso.

Yo siempre me pregunté eso, como es que si el hash tiene tamaño fijo no haya dos archivos/pass que den el mismo? pues mira, buen artículo para aprender cosas.

[#67 Sofrito]

Pues yo uso md5

[#116 santiagogf89]

#3 No tienes ni idea de criptografía, ¿verdad? Si tuvieses la mínima idea del número de operaciones que hacen falta para "romper" matemáticamente un cifrado AES-256 no afirmarías que si CUDA o si la tecnología cuántica.

Edito para añadir este ilustrador extracto del libro de Schneier Applied Cryptography:

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kTkT, where TT is the absolute temperature of the system and kk is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k=1.38⋅10−16erg/∘Kelvink=1.38⋅10−16erg/∘Kelvin, and that the ambient temperature of the universe is 3.2∘K3.2∘K, an ideal computer running at 3.2∘K3.2∘K would consume 4.4⋅10−164.4⋅10−16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21⋅10411.21⋅1041 ergs. This is enough to power about 2.7⋅10562.7⋅1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all of its energy for 32 years, without any loss, we could power a computer to count up to 21922192. Of course, it wouldn’t have the energy left over to perform any useful calculations with this counter.

But that’s just one star, and a measly one at that. A typical supernova releases something like 10511051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

[#22 Desactivado]

#15 Por casualidad no creo que haya ocurrido nunca porque las probabilidades son realmente ridículas. Pero desde que demostraron que los ataques eran 100% viables que el SHA1 se ha dejado de recomendar por activa y por pasiva. Los navegadores no aceptan los certificados firmados con SHA1 o al menos empiezan a quejarse, etc.

Y sí, las personas de bien usan algún tipo de "sal" para hashear las contraseñas.

[#50 Desactivado]

#41 ¿No crees que haya 76 personas en menéame capaces de entender un artículo técnico sobre informática? Eres nuevo, ¿no?

[#86 Vio]

#77 Lo siento por contestarte otra vez, no es nada personal, pero es que no lo entiendo. Ya nos ha quedado claro que sabías del tema y tal, y que ya sabías que era inseguro. Pero es que tú mismo te estás contradiciendo.

#70 "ha habido alguna otra colisión antes?"
#77 "Sí, había posibilidad de colisiones" -> o sea, no.

Que era posible? sí
Que había ocurrido? no (que se sepa!)

Por qué es tan difícil de admitir... todo por un titular. Que en la misma entradilla dice que se ha encontrado una técnica.

[#16 John_Doe]

#5 Tendrá consecuencias desde ahora si alguien usa SHA-1 para demostrar la validez de algún documento/fichero, aunque en principio eso debería ser desde 2011, momento en el que se dejo de recomendar usar SHA-1...
Usarlo desde esa fecha es un tanto masoca por querer meterse en terrenos pantanosos, no por el hecho de la noticia... era algo en lo que había mucha gente trabajando, simplemente éste grupo lo ha logrado antes que el resto, pero ya se sabía que era posible con una certeza del 100%.

[#21 Desactivado]

Anda que está informado el tio:

"Estas funciones comprimen grandes cantidades de información en pequeños mensajes (hash)."

El hash NO son los datos comprimidos. El hash es una casena de texto creada a partir de una fórmula que se aplica sobre los datos, que en teoría es bastante improbable que colisione con otra cadena aplicando la misma formula a datos diferentes.

[#20 John_Doe]

#10 Dada la computación cuántica... sí es algo que ocurrirá con gran parte de los métodos criptográficos actuales.
Las funciones hash se diseñan de modo que sean seguras, básicamente que no puedas obtener el fichero original a partir del hash del mismo y sobre todo... que no puedas encontrar dos ficheros con el mismo hash con facilidad (colisión). No es imposible encontrar una colisión pero debe ser prácticamente imposible. El cómo se logra esto... es lo que requiere años de trabajo por parte de la gente que propone nuevas funciones hash y la evaluación de las mismas.

[#51 Desactivado]

#8 Un algoritmo de hash (SHA es uno) crea o asigna un código corto a cada documento o archivo digital que se le entregue. El documento o archivo digital puede ser enorme, pero el código es muy corto.

La idea es que si se puede conseguir un algoritmo de creación de códigos hashes que funcione de forma tal que pueda afirmarse que dado un código hash cualquiera (o simplemente un "hash") exista únicamente un documento o archivo digital que podría conducir a ese código hash, entonces los códigos hashes pueden usarse como "representantes sustitutivos en miniatura" de los documentos o archivos digitales que son más grandes.

Por ejemplo, imagina que creo un algoritmo de hashes, que llamo ALG-H, que produce códigos hashes que cumplen esa condición, es decir, dado un código hash cualquiera producido por el algoritmo ALG-H, puede tenerse la seguridad de que sólamente existe un documento o archivo digital que podría conducir a ese código. Imagina que cojo la Enciclopedia Británica entera y se la doy como input al algoritmo ALG-H, y el algoritmo me calcula el código hash F7GM44Z para la Enciclopedia Británica.

Si yo te leo la Enciclopedia Británica entera por teléfono, puedo estar tres años leyéndotela. Pero si simplemente te digo por teléfono: "la información que quiero darte a través de esta llamada telefónica es la que conduce al código hash F7GM44Z a través del algoritmo ALG-H", cosa que solo me lleva tres o cuatro de segundos, entonces también te estoy leyendo la Enciclopedia Británica entera, aunque la llamada solo haya durado tres o cuatro segundos, porque tenemos la seguridad de que el único documento digital que a través del algoritmo ALG-H podría conducir al código hash F7GM44Z es la Enciclopedia Británica.

Lógicamente toda la seguridad del procedimiento recae en la condición de que dado un código hash sólamente pueda existir un documento o archivo digital que pueda conducir a él a través del algoritmo de cálculo dado. Si esta seguridad no existe, entonces el código que yo te dije por teléfono, F7GM44Z, lo mismo puede representar la Enciclopedia Británica que algún otro documento digital distinto (esto se llama "colisión", porque si dos documentos digitales tienen el mismo código hash, es como si "colisionaran" entre ellos), así que ese código ya no me sirve a mí para poder asegurar a otras personas que yo te dije a tí la Enciclopedia Británica por teléfono, con lo cual mi algoritmo ALG-H ya no es un buen algoritmo. Esto es lo que le ha pasado al SHA-1.

En teoría es imposible un algoritmo perfecto que garantice que las colisiones jamás ocurrirán. Entonces ¿por qué se siguen utilizando algoritmos de hash? Porque sí es posible crear un algoritmo de hash con el que, aun siendo en teoría posible encontrar colisiones en él, sin embargo en la práctica sea imposible, porque para conseguirlo haría falta superar barreras técnicas tan colosales que no tendría sentido ni utilidad intentar encontrar una colisión (es decir, encontrar un documento digital que consiga hacerse pasar por otro distinto disfrazándose de un mismo código hash válido para ambos).

[#95 Mister_Lala]

#81 ¿Te imaginas que lo usan contra el emule y el lugar de bajarte la peli de moda del momento, te descargas una porno porque han clonado el sha-1?

[#133 Mister_Lala]

#114 sha512 + salt & pepper, y con eso va que chuta.

[#40 Waskachu]

#2 no me gusta los que van de listillos, negativo.

[#7 Desactivado]

#3 Respecto a la tecnología cuántica, ya se estan estudiando algoritmos para ese futuro. No creas que has sido el primero que ha llegado a la conclusión que con los ordenadores cuánticos los cifrados actuales son una risa.

https://en.wikipedia.org/wiki/Quantum_cryptography

[#49 mefistófeles]

Pobre Julio César si levantara la cabeza

[#85 Desactivado]

#67 Yo prefiero MDMA

[#94 Mister_Lala]

#50 😂 El angelito lleva 10 años registrado y aún no se ha enterado que esto está lleno de informáticos que echan el rato entre compilación y compilación.

[#127 JanSmite]

#126 Anda, lee:

https://konklone.com/post/why-google-is-hurrying-the-web-to-kill-sha-1

Y es un artículo de 2014.

[#87 fayser]

Es curioso bajarlos y comprobar uno mismo que el sha1 de ambos pdf es el mismo.

Aunque también es cierto que dan un md5 distinto, con lo que bastaría combinar ambas huellas para joder el invento, y eso que el md5 también está superado.

[#107 ohtempora]

#16 Probar ante un juez que determinado documento, o disco duro, o firma electrónica no ha sido manipulado y es admisible como prueba, si se ha trabajado con SHA1...

[#125 jorgegv]

#119 Pues no, "cualquier friki con su ordenador" no se lo puede permitir... Pero cualquier interesado con suficiente dinero, y mucho que ganar con la prueba, si que puede. Mis numeros:

* 110 años de GPU son aprox. equivalentes a 1 año de 26 instancias con 4 GPUs cada una. Como las g2.8xlarge de Amazon. Precio por hora: $2,6
* 6500 años de CPU son aprox. equivalentes a 1 año de 181 instancias con 36 cores cada una. Como las c4.8xlarge de Amazon. Precio por hora: $1,6
* 1 hora de todas esas instancias funcionando = $2,6 x 26 + $1,6 x 181 = $357,2
* 1 año = 8.760h
* Coste anual de instancias: 8.760h x 357,2$/h =~ $3.130.000

En resumen: coste de generar un par de ficheros PDF con el mismo SHA1 y siguiendo la tecnica de estos pavos (de la que en 90 días publicarán el codigo fuente): 3.130.000 dolares.

Indudablemente, no cualquier friki se lo puede permitir, pero es un precio a pagar más que razonable, a cambio de no ir a la carcel, o de ser encontrado inocente en vez de culpable... para el que pueda permitirselo.

[#146 Vio]

#100 Gracias por el link, la verdad es que sabía que era inseguro pero que no habían encontrado una colisión todavía.
Yo no votaría la noticia errónea porque la colisión que encontraron fue una "freestart collision" y no una colisión de la función hash. O sea, que el título en mi opinión sigue siendo correcto.

Los que publicaron esa primera freestart collision son los que han publicado, junto con google, la nueva colisión (Marc Stevens y Pierre Karpman). En el abstract del report que enviaron se puede leer:
"Freestart collisions do not directly imply a collision for the full hash function." https://eprint.iacr.org/2015/967

A ver si esto aclara más las cosas

[#147 Desactivado]

#146 gracias por aclararlo igualmente ahora la voto positiva 😁

[#24 Zeioth]

Aún con todo, parece un ataque dificil de aplicar en la práctica. Pongamos que despues de 1 año corriendo 110 gpus, logras una colisión y obtienes un duplicado de la clave segura de alguien. Ahora tienes que ponerte a averiguar a quien pertenece la clave que has conseguido. Y alomejor su información ni te sirve de nada siquiera.

Sigue siendo un ataque a ciegas y extremadamente lento.

[#19 GoDie]

#10 Era esperable si, no inviable como dice la entradilla, lo que era bastante improbable que se diera el caso, pero tarde o temprano se iba a dar.

Más todavía improbable que se detectase, alguna vez posiblemente se dio pero paso despercibida.

La importancia de esta noticia no es lo que indica el titulo de que han detectado una colisión, si no que han descubierto una tecnica para generar las colisiones. O eso parece no me la lei por que no tengo tiempo ahora pero de un vistazo es lo que dice.

[#28 Zeioth]

#18 La noticia dice que sigue siendo inviable en la práctica, pero que ahora es 100,000 mas sencillo que en el articulo que comentas.

[#45 Desactivado]

Y por eso hace 2 años que existe SHA-3... que casi nadie utiliza, pero que todos deberían ir implementando para cuando SHA-256 (realmente SHA-2 256) también acabe cayendo.

[#48 sisko69]

#44 Gracias por la explicación. Todo un mundo esto de la criptografía.

[#61 Vio]

#21 Espero que no lo digas por mi, que me he dedicado a traducir el artículo en la entradilla (aunque he tenido que reducir algunas cosas). Pero el caso es que en este caso compresión se refiere a reducción de datos y no significa que esos datos sean recuperables. La compresión a la que te refieres tú es un caso particular, pero no significa que sea el único uso de la palabra.

[#62 fugaz]

#34 Como cuando comprimen un coche en el desguace

[#102 amchacon]

#98 eso es posible, pero si un tío lo ha descubierto cualquier otro también puede hacerlo

[#105 Pitt]

#46 No hay problema

[#113 Desactivado]

#90 Eso es para la criptografía asimétrica usando el algoritmo de Shor (https://es.wikipedia.org/wiki/Algoritmo_de_Shor), ahí si que tendríamos problemas serios ya que reventaría totalmente algoritmos como RSA o ECC.

[#114 Desactivado]

#93 Ya bueno, pero es que si consideras todo el conjunto de mensajes posibles, la probabilidad de que el mensaje original sea más largo que el hash es de 1.

Por cierto, espero que no utilices sólamente SHA-512, sino una función más robusta como PBKDF2, bcrypt, scrypt, o Argon2

[#143 Desactivado]

#141 Usar una sal impide el uso de tablas arcoiris, pero si simplemente usas un hash mas una sal, se puede lanzar un ataque de diccionario con relativa facilidad. Y como muchos usuarios usan contraseñas débiles, se pueden reventar en poco tiempo. Por eso todas las KDF utilizan cientos o miles de iteraciones y procedimientos adicionales para incrementar significativamente el tiempo de cómputo y el consumo de memoria, para que dificultar los ataques lo más posible.

Usar una pimienta si que complica mucho las cosas a un atacante, pero repito lo dicho: usa una KDF probada y robusta, no te inventes la tuya. Además de que en la mayoría de los lenguajes usar bcrypt o scrypt es tan sencillo como importar una biblioteca y llamar a una función. Probablemente suponga menos trabajo que inventarte tu propia función.

[#157 JanSmite]

#148 ¿Cuanto tiempo decías que iba a tardar en tener consecuencias lo de la colisión de los carísimos PDFs? Y no ha sido ni siquiera un ataque: alguien subió los PDFs para ver cómo reaccionaba un sistema que usa SHA-1 para controlar los cambios de versión al repositorio SVN de, nada más y nada menos, WebKit, el motor de Safari, Opera o Konkeror:

Primera víctima de la colisión de SHA1: El repositorio de WebKit [ENG]

Primera víctima de la colisión de SHA1: El reposit...

Resultado: el sistema no ha sabido lidiar con dos ficheros diferentes pero con el mismo hash, y se ha corrompido todo el sistema. ¿Ves? No ha tenido que ver ni siquiera con un ataque criptográfico, pero ha tumbado un sistema que no contemplaba esa posibilidad. ¿Nos ponemos a probar cuántos sistemas están en esa misma situación?

Ah, y ha bastado un día desde la publicación de la colisión.

[#31 Desactivado]

#30 Si, pero siempre he pensado que es erróneo. Porque es cierto que si usas un hash puedes desestimar el origen, únicamente si NUNCA necesitas recuperarlo (es decir, descomprimir).
Un ejemplo claro son los passwords, se guarda el hash y nunca se recupera el original, sólo se compara el que escribe el usuario, pasado por la función hash, comprobando si da lo mismo.
Pero yo a eso no lo llamaría compresión, mas bien "transformación". Aunque bueno, creo que tengo el resto del mundo en contra, sigo pensado lo mismo.

[#38 Desactivado]

#36 Me baso en lo que su día comentó Linus, no sé si aún estará en vigor o qué. Dijo el pollo:


> if you already have a file A in git with hash X is there any condition where a
> remote file with hash X (but different contents) would overwrite the local
> version?

Nope. If it has the same SHA1, it means that when we receive the object
from the other end, we will not overwrite the object we already have.


https://marc.info/?l=git&m=115678778717621&w=2

O sea que sí, por poder pueden crear un repo maligno e intentar endiñártelo pero se ve que git por defecto no confía en los repos externos sino que da tu copia local como aquella de la que se puede fiar.

Pero vamos, que sigue siendo muy arriesgado seguir con SHA1, eso desde luego.

[#54 Frederic_Bourdin]

Había una porra y un listo se la ha llevado (o directamente alguien de Google, aunque creo que es menos probable).

[#74 Benjamin_Linus]

#65 Hombre, una colisión generada intencionalmente en un tiempo razonable sí que es suficiente para afirmar que SHA1 no es seguro.

[#88 Mister_Lala]

#7 Calla, deja que el genio siga ilustrándonos.

[#18 Dovlado]

Según la wiki ya se había encontrado una vulnerabilidad en 2004, aunque la consideraban "computacionalmente inviable":

https://es.wikipedia.org/wiki/Secure_Hash_Algorithm

"En 2004 se encontró una debilidad matemática en SHA-1, que permitiría encontrar colisiones de hash más rápido. Sin embargo, este hallazgo resulta poco relevante, pues la complejidad de búsqueda de colisiones pasaría de 2⁸⁰ a 2⁶⁹, algo que aún es computacionalmente inviable, requiriendo incluso más trabajo que MD5 (2⁶⁴)."

"La resistencia del algoritmo SHA-1 se ha visto comprometida a lo largo del año 2005. Después de que MD5, entre otros, quedara seriamente comprometido en el 2004 por parte de un equipo de investigadores chinos, el tiempo de vida de SHA-1 quedó visto para sentencia."

Así que el que lo siga usando es un chapuzas.

[#30 Desactivado]

#21 En la literatura técnica a los hashes también se les llama funciones de compresión: https://en.wikipedia.org/wiki/One-way_compression_function

[#34 Desactivado]

#31 Por eso se le llama compresión unidireccional, luego no se pueden descomprimir

[#75 Vio]

#68 Es que yo no he "escrito este titular". Pero vamos, que sólo lo mencionaba por si alguien se había pensado que yo había cambiado el titular por algún motivo.

Sigo sin entender el problema. Lo han logrado romper en la práctica. Han encontrado una colisión. Ese es el titular. But wait, there's more! Entonces sigues leyendo el artículo para terminar el "holy shit" que empezó con la noticia de que encontraron la colisión. No veo cómo las dos cosas son incompatibles. Nadie antes había encontrado una colisión (que se sepa!), por lo tanto esta es la primera.

[#26 Pitt]

#3 #7 Bueno, con ordenadores cuánticos podrá crearse cifrados cuánticos también

[#36 JungSpinoza]

#17 How is GIT affected?

GIT strongly relies on SHA-1 for the identification and integrity checking of all file objects and commits. It is essentially possible to create two GIT repositories with the same head commit hash and different contents, say a benign source code and a backdoored one. An attacker could potentially selectively serve either repository to targeted users. This will require attackers to compute their own collision.

[#53 Vio]

#19 Lo que dice la entradilla es que para que un hash sea un buen cifrado, la colisión debería ser computacionalmente inviable (no que no se pudiera dar con recursos infinitos). Que es exactamente lo que prueban en este artículo que SHA1 no es (y que sí que se veía venir).

Y sí, lo que dicen en este artículo es que han encontrado una técnica para generarlas, pero si simplemente hubiesen encontrado una única colisión, también sería una noticia importante.

Sólo matizo tu comentario

[#76 JanSmite]

#4 Estamos hablando de SHA-1 (160 bits), que está marcado como potencialmente inseguro desde hace algún tiempo. En cuanto aumentas el número de bits (SHA3-224, SHA3-256,…), además de mejorar los algoritmos, la cosa cambia. Que sí, que puede que eventualmente se rompa tambien, con tiempo y potencia de proceso, pero para entonces ya se habrán desarrollado sistemas criptográficos más avanzados y acordes con la potencia de proceso disponible.

[#130 Desactivado]

#128 Los algoritmos de hash se inventaron como un subtipo de algoritmo de compresión (aunque hay otros subtipos de algoritmos de compresión que no son algoritmos de hash). Por ejemplo, se inventaron para poder comprobar que te has descargado un archivo muy grande correctamente y sin fallos de transmisión simplemente descargándote también un pequeño código hash, ahorrándote así tener que descargarte el archivo grande también una segunda vez, en vez del código hash, para comprobar que las dos versiones descargadas del archivo grande sean iguales.

[#134 Desactivado]

#132 - "Los algoritmos hash no se concivieron, ni de lejos, como subtipos de algoritmos de compresión."

Por eso se les llama "funciones de resumen" o "funciones de compresión unidireccionales" (one-way compression functions, https://en.wikipedia.org/wiki/One-way_compression_function#One-way )

Si bien es cierto lo que dices de que a diferencia de otras formas de compresión más comunes, dado el hash no puedes conocer a partir de qué archivo original fue calculado.

[#135 zarr]

#118 No sabía que esto tuviera un nombre. ¡Gracias por el apunte!

Ahora, el principio del palomar se disputa con el teorema de Bolzano el honorable puesto del enunciado matemático con nombre más trivial.

[#78 Zeioth]

#58 Ves? Por respuestas así es que me tomo la molestia de seguir comentando en Meneame 😂

[#91 rafaeska]

#c-33" class="content-link" style="color: rgb(227, 86, 20)" data-toggle="popover" data-popover-type="comment" data-popover-url="/tooltip/comment/2739157/order/33">#33 Me has hecho comprobarlo jodío. Te has inventado la colisión:
[xxxx@xxxx-cave ~]$ echo "Hola Mundo" | sha1sum
38beb661c63932eef289638a2443a7fdb8b7ad2d -
[xxxx@xxxx-cave ~]$ echo "j983rO#@jro23" | sha1sum
e1080bb46aa464b3b08d99e4b476e4d8f653afdd -
[xxxx@xxxx-cave ~]$ echo "j983rO#@jro23" | md5sum
7b52a0a5e6640af4cabef151ff19f99a -
[xxxx@xxxx-cave ~]$ echo "Hola Mundo" | md5sum
b4b9e397fb7e08bfeaa54090d2989e53 -

¿O es que era un ejemplo no md5 ni sha1?

[#93 Mister_Lala]

#34 Pero es que la salida no tiene por qué ser menor que la entrada. Yo uso SHA512 para las contraseñas, y tú puedes poner una contraseña de 8 caracteres (8 bytes), por ejemplo, y el sha512 tiene 64 bytes. No has comprimido nada. Al contrario.

[#96 Mister_Lala]

#67 por el culo te la hinco

[#117 santiagogf89]

#79 #71 #27 #16 ¿Habéis leído la cantidad de esfuerzo necesario para crackear un PDF? ¿Habéis visto que no es aplicable a cualquier archivo? ¿Sabéis que el DNIe 3.0 utiliza AMBOS métodos de hashing precisamente porque SHA-1 fue marcado como inseguro en 2011?
Que atrevida es la ignorancia...

[#122 Zeioth]

#120 Claro, casi siempre te capan en 200 maquinas simultaneas. Y por mucho que tuvieses la informacion bancaría de alguien aún necesitas su la tarjeta de cordenadas y/o telefono movil por la doble validación. Pero la premisa es buena.

[#141 Mister_Lala]

#139 No he inventado nada. Hash + salt es muy utilizado, y hash + salt & pepper mejora al anterior.

[#66 capitan__nemo]

¿Tienen una técnica para crearlas o ha sido casualidad porque tienen hashes de tantos archivos en sus bbdd y han visto que dos ficheros diferentes tienen el mismo sha1?

¿No será una liberación de bug que mantenia la nsa/google y que han decidido que ya es hora?
Trump ayuda a Wall Street y desmantela las protecciones que se crearon tras la Gran Recesión para evitar otra crisis/c156#c-156

Matematicos que trabajaban para la nsa encontraron la vulnerabilidad hace tiempo (encontraron sistemas para crear colisiones al gusto, hackearon el algoritmo) y no la publicaron (esos bugs que se guardan), como cuando se descodificó enigma y lo mantuvieron en secreto toda la guerra y años despues.

Ahora igual algunos matematicos del open source están encontrando la vulnerabilidad y entonces toca desacerse de este sistema.

O alguien está construyendo o tienen construidos ordenadores cuanticos experimentales suficientemente potentes para calcular y craer colisiones mas rapido.

Aunque no se si era sha1 el que ya era vulnerable u otro, las dichosas siglas.

[#81 mcfgdbbn3]

#59: Eso pienso yo: ¿Qué pasa con nuestros programas P2P? ¿Tendremos que añadir el SHA256 a los enlaces eD2K? Hace tiempo añadieron el SHA1 porque se estimó que MD4 era demasiado blando y inseguro, ahora hay esos dos a la vez. ¿Por qué no se inventa un SHA2048 y nos dejamos de historias? O sea, aunque sea lento, pero que sea indestructible en varias décadas.

[#98 capitan__nemo]

#82 Pero piensa
¿Y si hay un monton de tipos como Marc Stevens que investigan, pero no publican sus papers?
Los papers se los quedan y los desarrollan otros que tampoco publican papers.

Entonces igual hay metodos incluso muchisimo mas eficaces de resolver el problema, incluso con poquitas maquinas con gpu.
Entonces algunos ya pueden romper sha1 y otros desde hace tiempo, pero no lo sabemos, porque nunca publicaron papers, se los guardaron para otros propósitos (hegemonia, seguridad nacional, ganar)

Y sabemos que entes como la nsa se suelen dedicar a eso bastante. Si alguien lo ha hecho, ellos son unos de los que lo han hecho.

[#100 Desactivado]

#6 #0 Nop, no es la primera pero no sé si considerar la noticia errónea

https://it.slashdot.org/story/15/10/09/1425207/first-successful-collision-attack-on-the-sha-1-hashing-algorithm

[#106 capitan__nemo]

#102 Sí, puede. Pero seguro que no tendrá los mismos medios y financiación. Igual no es un tio y tienen 1000 haciendo eso. Si uno descubre eso, se sustituirá el algoritmo por otro, y "ellos" ya tendrán resuelta la vulnerabilidad del nuevo algoritmo (igual llevan 30 años ahí dandole caña a la investigación y guardandose papers a toneladas, papers de uso interno, e investigación matematica secreta, si ven que uno se acerca, lo contratan para que trabaje para ellos en papers secretos)

[#121 mcfgdbbn3]

#95: Claro, pero aquí la cuestión es que tienes que clonar dos hash a la vez.

[#149 mcfgdbbn3]

#114: BIP 38, tan avanzado que ni siquiera viene en la Wikipedia.

[#150 mcfgdbbn3]

#126: Pues a mi esto me parece más importante que las nimiedades que mira la policía sin venir a cuento a veces.

Es un tema que puede comprometer la seguridad nacional.

[#153 mcfgdbbn3]

#152: Pues que una opción podría ser meter un BIP 38 por ahí para que sea más difícil hacer estos ataques criptográficos. Consiste en meter muchas operaciones y que tengan que ser muy lentos.

[#14 Black_Diamond]

Entre otras cosas, afecta a git de forma severa...

[#37 Pitt]

#33 De acuerdo que puede ser más o menos informativo, pero incorrecto no Y sinceramente, a las personas con menos conocimientos criptográficos seguramente les dé igual esta noticia.

[#41 FueraSionistasdeMeneame]

Me pregunto cuantos de los 76 meneantes saben de qué cojones está hablando el artículo.

[#43 Varlak_]

#12 pero esta es la primera colisión de SHA1, verdad? y el título es "google anuncia la primera colisión de SHA1", verdad? entonces, qué está mal en el título?

[#70 Varlak_]

#64 no lo entiendo muy bien, ha habido alguna otra colisión antes?