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.
|
etiquetas: sha1 , criptografía , seguridad
No se trata de "la primera colisión", sino de la primera técnica factible para generar colisiones.
No se trata de "la primera colisión", sino de la primera técnica factible para generar colisiones.
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.
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.
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%.
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 280 a 269, algo que aún es computacionalmente inviable, requiriendo incluso más trabajo que MD5 (264)."
"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.
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.
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.
"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.
Y sí, las personas de bien usan algún tipo de "sal" para hashear las contraseñas.
Sigue siendo un ataque a ciegas y extremadamente lento.
O por ejemplo, para romper contraseñas del RAR prueba con esto: 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.
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.
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 ).
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.
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.
> 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.
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.
- 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.
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 (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.
#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
#25 Gracias por intentar ayudarme
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).
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
twitter.com/rauchg/status/834770508633694208
it.slashdot.org/story/15/10/09/1425207/first-successful-collision-atta
fileEq(file, sha1Check, md5Check): return sha1(f1) == sha1Check and md5(f1) == md5Check
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...
¿No será una liberación de bug que mantenia la nsa/google y que han decidido que ya es hora?
www.meneame.net/c/21185135
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.
Es obvio que la noticia del blog de Google está orientada al marketing y probablemente los periodistas de medio mundo tomarán el asunto de que SHA-1 no es seguro como algo que es nuevo y de autoría de Google... pero no es así.
En cualquier caso, tampoco es tan traumático porque es cuestión de invalidar como dices el uso de SHA-1 y en los nuevos certificados que usen obviamente... ni mirarlo.
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.
La cuestión está en si necesitas ver un caso práctico (ésta noticia) o la demostración matemática que prueba que hay casos (uno o más...)
#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.
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.
Es decir y para entendernos (totalmente inventado):
Ordenador convencional:
Clave con 1 caracter: 6s
2 caracteres: 6^2=36s
4 caracteres: 6^4=1200s
8 caracteres: 6^8=466 horas
10 caracteres=2 años.
Ordenador cuántico:
1 caracter: 6s.
10 caracteres: 60s
[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?
Si la idea es, cojo un archivo, hago unos cálculos con los bits que lo forman usando el algoritmo que sea, para obtener una cadena de caracteres que siempre tiene una longitud fija sea el archivo que sea, la cosa es bien sencilla: el número de archivos distintos posibles es infinito, mientros que el número de combinaciones de una cadena de X bits es 2^X siendo 2^X<<infinito... Por lo tanto es inevitable que haya colisiones.
El problema gordo debe estar en cuando se encuentra un método para que, cogiendo cualquier archivo que se te ocurra y haciéndole una mínima y rapida modificación, como puede ser añadirle una serie de bits al final del mismo, se consiga dar como resultado siempre el mismo hash para todos ellos o el hash que a ti te interese en ese momento.
Pero hablo desde la más absoluta y profunda de las ignorancias.
La demostración práctica de la inseguridad de SHA-1 que se nos cuenta hoy no es suficiente para afirmar que SHA-1 es inseguro, y ni mucho menos para afirmar que es la primera colisión porque la matemática ya dijo en 2005 que hay colisiones. Otra cosa es que ésta sea la primera colisión en la práctica hasta la fecha.
Prueba del caos y del morbo del asunto, distintos medios ya están poniendo titulares del estilo de éste: "Google just cracked one of the building blocks of web encryption (but don’t worry)" por The Verge (www.theverge.com/2017/2/23/14712118/google-sha1-collision-broken-web-e).
¿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.
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.