Seguridad de SHA256 y Bitcoins

10

La red de Bitcoin usa SHA256 como un componente central para su diseño. No soy un experto en criptografía, pero me parece que generalmente es solo una cuestión de tiempo antes de que se descubran las vulnerabilidades de seguridad (MD5 por ejemplo, así como muchos otros).

¿Cuáles son las posibilidades de que se descubran vulnerabilidades similares en SHA256 en algún momento, y qué tan dañino sería para la red de Bitcoin?

    
pregunta Gilles 09.06.2011 - 11:06
fuente

6 respuestas

12

La única forma conocida de determinar la seguridad de un algoritmo criptográfico es dejarlo bajo el escrutinio de cientos de criptógrafos durante varios años, y ver qué sale. Así que la perspectiva correcta aquí es histórica.

MD5 fue publicado en 1992 ; En realidad fue diseñado el año anterior (1991). En 1993, se detectaron las primeras debilidades y luego las mayores en 1996 (colisiones en la función de compresión, encontradas por Dobbertin). Wang tardó 8 años para que estas debilidades se convirtieran en colisiones reales en 2004. Siete años más tarde, en 2011, podemos crear colisiones MD5 a voluntad (y mucho más eficientemente que con el método original de Wang), pero antes y después Las resistencias de preimagen de MD5 siguen siendo tan buenas como siempre.

De esto podemos inferir que cuando se encuentran debilidades en la función hash, no aparecen de la noche a la mañana: tenemos bastante tiempo para reaccionar. Además, las primeras debilidades del MD5 se descubrieron solo un año después de su publicación, y eso fue a principios de la década de 1990 cuando la investigación pública en criptografía involucró a muchas menos personas que en la actualidad.

Veamos lo que esto da para SHA-256: publicado por primera vez en 2001; Diez años después (2011), todavía no tenemos ninguna pista sobre el más mínimo indicio de debilidad. Esto sugeriría que SHA-256 es realmente robusto, y las colisiones para SHA-256 no están a la vuelta de la esquina. Además, no he examinado en detalle el protocolo de Bitcoin, pero parece que las colisiones no son un peligro real para Bitcoin, sino que se basa en la resistencia de preimagen, para la cual no solo SHA-256 es sólida, sino que incluso MD5 Sigue siendo confiable.

Sin embargo , es peligroso hacer estadísticas en una sola medida. En 2007, se estimó que existía un riesgo relativamente alto de que los ataques en MD5 se pudieran transportar a SHA-1 y luego a SHA-256/512; esto llevó a NIST a organizar el Competencia SHA-3 . Resultó que los ataques en SHA-1 de alguna manera han dejado de progresar, y no hay ningún ataque en SHA-2. No se sabe si esto es porque SHA-2 es realmente robusto, o porque todos los criptógrafos están ocupados intentando romper a los candidatos de SHA-3, pero mi opinión es la primera: SHA-2 es un algoritmo hash seguro. p>     

respondido por el Thomas Pornin 29.09.2011 - 22:47
fuente
7

Las vulnerabilidades pueden ocurrir en diferentes niveles aquí.

1) Se puede descubrir un ataque teórico que reduce la complejidad necesaria para un ataque exitoso, pero no lo suficientemente bajo como para ser práctico. Es decir. desde un punto de vista técnico, el algoritmo se considera roto, pero sigue siendo seguro para cualquier uso práctico.

2) Se descubre un ataque que reduce la complejidad a un nivel que puede ser practicado prácticamente por un gran ataque distribuido dentro del tiempo factible. El algoritmo aún puede ser útil para fines específicos (por ejemplo, MD5 para identificar errores de descarga de un archivo), pero es un No Go para cualquier cosa que requiera seguridad a largo plazo, como firmas digitales.

3) El algoritmo está completamente roto, cualquiera puede hacerlo en su PC doméstica. Olvídalo y todo lo que lo use como componente central. La verificación de descarga aún puede estar bien, pero no mucho más allá de eso.

Hay algunas leyes fundamentales que deben ser consideradas aquí. En primer lugar, no puede probar que un algoritmo es seguro, solo puede probar que no es seguro realmente rompiéndolo. En segundo lugar, los ataques siempre mejoran, nunca empeoran. Es decir. el conocimiento investigado de ataques anteriores no será olvidado.

Para las posibilidades, un descubrimiento se puede hacer mañana. O en dos años. O en veinte años. SHA-1 está roto (http://en.wikipedia.org/wiki/SHA-1) y en algún lugar entre 1 y 2, y SHA256 usa una estructura básica similar. Pero aún no se conocen ataques contra SHA256, AFAIK.

    
respondido por el Secure 09.06.2011 - 12:10
fuente
7

Parece que el funcionamiento interno de Bitcoin es que firma, usando el algoritmo ECDSA, el doble aplicado (el primer hash es hash otra vez) hash SHA256 de la transacción.

Siempre es solo cuestión de tiempo antes de que se encuentren las vulnerabilidades de seguridad. Pero tiende a haber más vulnerabilidades de seguridad de una implementación deficiente del mejor algoritmo que de una buena implementación de un algoritmo aceptable.

O, lo peor de ambos mundos, una implementación deficiente de un algoritmo deficiente. Se usó un ataque de inyección SQL para obtener detalles de la cuenta en el monte. Gox Bitcoin Exchange, donde almacenaban hashes de contraseñas MD5 en su base de datos, incluidos los de los administradores de Exchange.

Lo que no tiene absolutamente nada que ver con la seguridad criptográfica de SHA256, pero fue algo perjudicial para la red de Bitcoin.

    
respondido por el tsundoku 21.08.2011 - 15:38
fuente
4

Hay un par de cosas que entender.

Lo primero es entender la fuerza de un algoritmo de hash. Para replicar un hash, el nivel de dificultad es el tamaño completo de la clave de hash. Por lo tanto, si ya tiene un hash MD5 y desea encontrar un patrón que coincida, lo difícil es un total de 128 bits. Pero debido a los problemas descubiertos, podríamos hacerlo con solo 100 bits de dificultad. Pero, lo máximo que podemos hacer es 60 bits de dificultad. Por lo tanto, descifrar el MD5 de la manera sigue siendo imposible con el conocimiento / hardware actual.

Pero hay una segunda preocupación por los algoritmos de hash: el de crear dos cosas que tienen un valor nuevo. Es una especie de ataque en el medio. Es la mitad del número de bits de dificultad, por lo que para un algoritmo de 128 bits, solo tiene 64 bits de dificultad. Con los errores conocidos en MD5, esa dificultad se vuelve más como 50 bits, dentro de la capacidad de las computadoras modernas.

Este problema de encuentro en el medio significa que el SHA-256 tiene solo 128 bits de dificultad. Lo que eso significa para Bitcoins es crear dos transacciones que tengan el mismo valor.

Como MD5, no lo romperemos todo de una vez. En su lugar, las personas se afeitarán unos pocos bits de dificultad a la vez, tal como lo hicieron recientemente con 2 bits de dificultad para AES. Por lo tanto, pasará de 128 bits de dificultad, a 125, a 120, a 115, y así sucesivamente.

Con la Ley de Moore agregando un poco de poder de craqueo (60 bits hoy, 61 bits el próximo año, 62 bits el año siguiente) y SHA-256 perdiendo un poco de resistencia en el medio cada año. , eso significa que nos quedan unos 30 años antes de que sea práctico forjar transacciones de Bitcoin.

Bitcoin hace algunas cosas para hacer que esto sea más difícil, pero probablemente en los próximos 30 años, alguien descubra una forma de solucionar esos problemas. Por lo tanto, supongo que los Bitcoins tienen una vida útil de 30 años.

Eso es más que la moneda para muchos países mal administrados.

    
respondido por el Robert David Graham 24.08.2011 - 08:04
fuente
3

Tal vez se pueda adivinar el tiempo en función de cuánto tiempo sobrevivieron otros algoritmos ampliamente utilizados antes de encontrarlos defectuosos, pero eso, por supuesto, no significa que puedas hacer predicciones útiles.

Una solución inteligente que un amigo mío explicó para un proyecto grande fue simplemente usar dos algoritmos de hash en paralelo (es decir, cada archivo tenía dos hashes asociados), luego intercambiar uno si es roto. La posibilidad de que dos se rompan alrededor del mismo tiempo, y que la combinación de los dos también sea quebradiza, es probablemente 10 ^ mucho ^ mucho más pequeña que la posibilidad de que cualquier solo algorithm alguna vez se romperá, y como beneficio adicional, tendrá tiempo para encargarse de la transición a un nuevo hash cuando se rompa uno de ellos.

    
respondido por el l0b0 09.06.2011 - 14:50
fuente
0

MD5 es un valor hash de 128 bits, mientras que SHA256 es 256 bits. Por lo tanto, la posibilidad de una llamada colisión es mucho menor para SHA256 en comparación con MD5.

También MD5 es un viejo veterano que había estado alrededor de los 90, supongo, mientras que el SHA256 tiene aproximadamente una década y necesitaría una gran cantidad de computación para colisionar. Pero en caso de que suceda, entonces sería gradual y creo que habría algún tiempo ( SHA-3 estaría fuera para entonces ) y ellos (BitCoin) podrían migrar, pero eso es todo. una tarea gigantesca en sí misma y hay otras personas con la experiencia para analizar esa parte (no encajo en absoluto)

Todavía mucho tiempo para un compromiso de este tipo en SHA256, creo.

    
respondido por el V4Vendetta 09.06.2011 - 12:07
fuente

Lea otras preguntas en las etiquetas