¿Qué pasaría realmente si tuviera una colisión de hash mientras usaba git?

Por ejemplo, me las arreglo para comprometer dos archivos con la misma suma de comprobación sha1, ¿lo notaría o corrompería uno de los archivos?

¿Podría mejorarse git para vivir con eso, o tendría que cambiar a un nuevo algoritmo hash?

(Por favor, no desvíe esta pregunta discutiendo lo poco probable que sea eso - Gracias)

Recogiendo átomos en 10 lunas

Un hash SHA-1 es una cadena de 40 caracteres hexadecimales ... eso es 4 bits por carácter multiplicado por 40 ... 160 bits. Ahora sabemos que 10 bits son aproximadamente 1000 (1024 para ser exactos), lo que significa que hay 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 diferentes hashes SHA-1 ... 10 ⁴⁸ .

¿De qué es este equivalente? Bueno, la Luna está formada por unos 10 ⁴⁷ átomos. Entonces, si tenemos 10 Lunas ... y seleccionas aleatoriamente un átomo en una de estas lunas ... y luego continúas y seleccionas un átomo aleatorio en ellas nuevamente ... entonces la probabilidad de que elijas el mismo átomo dos veces , es la probabilidad de que dos commits git dados tengan el mismo hash SHA-1.

Ampliando esto, podemos hacer la pregunta ...

¿Cuántas confirmaciones necesita en un repositorio antes de comenzar a preocuparse por las colisiones?

Esto se relaciona con los llamados "ataques de cumpleaños", que a su vez se refiere a la "paradoja del cumpleaños" o "problema de cumpleaños", que establece que cuando elige al azar de un conjunto dado, sorprendentemente necesita pocas selecciones antes de que sea más probable que no. haber escogido algo dos veces. Pero "sorprendentemente pocos" es un término muy relativo aquí.

Wikipedia tiene una tabla sobre la probabilidad de colisiones de Birthday Paradox . No hay entrada para un hash de 40 caracteres. Pero una interpolación de las entradas para 32 y 48 caracteres nos ubica en el rango de 5 * 10 ²² git commits para una probabilidad de colisión del 0.1%. Es decir, cincuenta mil millones de billones de confirmaciones diferentes, o cincuenta Zettacommits , antes de que haya alcanzado incluso un 0.1% de posibilidades de que tenga una colisión.

La suma de bytes de los hashes solo para estas confirmaciones sería más datos que todos los datos generados en la Tierra durante un año, lo que significa que necesitaría producir código más rápido que YouTube transmite video. Buena suerte con eso. :RE

El punto de esto es que, a menos que alguien esté causando una colisión deliberadamente, la probabilidad de que ocurra al azar es tan asombrosamente pequeña que puede ignorar este problema

"Pero cuando una colisión no se produce, entonces lo que realmente sucede?"

Ok, supongamos que sucede lo improbable, o supongamos que alguien logró adaptar una colisión deliberada de hash SHA-1 . ¿Qué pasa entonces?

En ese caso, hay una excelente respuesta donde alguien experimentó con ella . Citaré de esa respuesta:

1. Si ya existe un blob con el mismo hash, no recibirá ninguna advertencia en absoluto. Todo parece estar bien, pero cuando empujas, alguien clona o reviertes, perderás la última versión (en línea con lo explicado anteriormente).
2. Si ya existe un objeto de árbol y crea un blob con el mismo hash: todo parecerá normal, hasta que intente empujar o alguien clone su repositorio. Entonces verás que el repositorio está corrupto.
3. Si ya existe un objeto de confirmación y crea un blob con el mismo hash: igual que # 2 - corrupto
4. Si ya existe un blob y realiza un objeto de confirmación con el mismo hash, fallará al actualizar el "ref".
5. Si ya existe un blob y crea un objeto de árbol con el mismo hash. Fallará al crear el commit.
6. Si ya existe un objeto de árbol y realiza un objeto de confirmación con el mismo hash, fallará al actualizar la "ref".
7. Si ya existe un objeto de árbol y usted hace un objeto de árbol con el mismo hash, todo parecerá correcto. Pero cuando se compromete, todo el repositorio hará referencia al árbol incorrecto.
8. Si ya existe un objeto de confirmación y crea un objeto de confirmación con el mismo hash, todo parecerá correcto. Pero cuando confirma, la confirmación nunca se creará y el puntero HEAD se moverá a una confirmación anterior.
9. Si ya existe un objeto de confirmación y crea un objeto de árbol con el mismo hash, fallará al crear la confirmación.

Como puede parecer, algunos casos no son buenos. Especialmente los casos n. ° 2 y n. ° 3 estropean su repositorio. Sin embargo, parece que la falla permanece dentro de ese repositorio, y la improbabilidad de ataque / extraña no se propaga a otros repositorios.

También parece que el problema de las colisiones deliberadas se reconoce como una amenaza real, por lo que GitHub está tomando medidas para evitarlo .

Si dos archivos tienen la misma suma de hash en git, trataría esos archivos como idénticos. En el caso absolutamente improbable de que esto ocurra, siempre podría retroceder una confirmación y cambiar algo en el archivo para que ya no colisionen ...

Ver la publicación de Linus Torvalds en el hilo "¿Comienza a pensar en sha-256?" en la lista de correo de git .

No es realmente posible responder esta pregunta con el "pero" correcto sin explicar también por qué no es un problema. No es posible hacer eso sin tener realmente un buen control de lo que realmente es un hash. Es más complicado que los casos simples a los que podría haber estado expuesto en un programa de CS.

Aquí hay un malentendido básico de la teoría de la información. Si reduce una gran cantidad de información en una cantidad menor descartando cierta cantidad (es decir, un hash), habrá una posibilidad de colisión directamente relacionada con la longitud de los datos. Cuanto más cortos sean los datos, MENOS es probable que sean. Ahora, la gran mayoría de las colisiones serán galimatías, por lo que es mucho más probable que sucedan realmente (nunca verificaría galimatías ... incluso una imagen binaria está algo estructurada). Al final, las posibilidades son remotas. Para responder a su pregunta, sí, git los tratará de la misma manera, cambiar el algoritmo hash no ayudará, tomará una "segunda verificación" de algún tipo, pero en última instancia, necesitaría la mayor cantidad de datos de "verificación adicional" como la longitud de los datos para estar 100% seguro ... tenga en cuenta que sería 99.99999 ... a un número realmente largo de dígitos ... seguro con una simple verificación como la que usted describe. SHA-x son hashes criptográficamente fuertes, lo que significa que generalmente no es difícil crear intencionalmente dos conjuntos de datos de origen que son MUY SIMILARES entre sí y tienen el mismo hash. Un bit de cambio en los datos debería crear más de uno (preferiblemente el mayor número posible) de cambio en la salida del hash, lo que también significa que es muy difícil (pero no del todo imposible) volver desde el hash al conjunto completo de colisiones y, por lo tanto, extraer el mensaje original de ese conjunto de colisiones: todas menos algunas serán galimatías, y de las que no lo son, todavía hay un gran número para examinar si la longitud del mensaje es de una longitud significativa. La desventaja de un cifrado hash es que son lentos para calcular ... en general.

Entonces, ¿qué significa todo para Git? No mucho. Los hashes se realizan tan raramente (en relación con todo lo demás) que su penalización computacional es baja en general para las operaciones. Las posibilidades de golpear un par de colisiones son tan bajas que no es una posibilidad realista de ocurrir y no ser detectado de inmediato (es decir, su código probablemente dejaría de construirse repentinamente), lo que le permite al usuario solucionar el problema (respaldar una revisión, y haga el cambio nuevamente, y seguramente obtendrá un hash diferente debido al cambio de tiempo, que también alimenta el hash en git). Es más probable que sea un problema real para usted si está almacenando archivos binarios arbitrarios en git, que no es realmente el modelo de uso principal. Si quieres hacer eso ... probablemente estés mejor usando una base de datos tradicional.

No está mal pensar en esto, es una buena pregunta que muchas personas simplemente pasan por "tan poco probable que no valga la pena pensar", pero en realidad es un poco más complicado que eso. Si sucede, debería ser fácilmente detectable, no será una corrupción silenciosa en un flujo de trabajo normal.

¿Podría mejorarse git para vivir con eso, o tendría que cambiar a un nuevo algoritmo hash?

Las colisiones son posibles para cualquier algoritmo hash, por lo que cambiar la función hash no excluye el problema, solo hace que sea menos probable que ocurra. Por lo tanto, debe elegir una función hash realmente buena (SHA-1 ya lo es, pero pidió que no se lo dijeran :)

Puedes ver un buen estudio en " ¿Cómo manejaría Git una colisión SHA-1 en una gota? ".

Dado que ahora es posible una colisión SHA1 (como hago referencia en esta respuesta con shattered.io ), sepa que Git 2.13 (Q2 2017) mejorará / mitigará la situación actual con una variante "detectar intento de crear colisiones" de la implementación SHA-1 por Marc Stevens (CWI) y Dan Shumow (Microsoft) .

Ver commit f5f5e7f , commit 8325e43 , commit c0c2006 , commit 45a574e , commit 28dc98e (16 de marzo de 2017) por Jeff King ( peff) .
^{(Fusionada por Junio ​​C Hamano - gitster- en commit 48b3693 , 24 mar 2017)}

Makefile: establece DC_SHA1el valor predeterminado

Solíamos usar la implementación SHA1 de la biblioteca OpenSSL por defecto.
Como estamos tratando de tener cuidado contra los ataques de colisión después del reciente anuncio "destrozado", cambie el valor predeterminado para alentar a las personas a usar la implementación DC_SHA1 en su lugar.
Aquellos que quieran usar la implementación de OpenSSL pueden solicitarla explícitamente OPENSSL_SHA1=YesPleaseal ejecutar " make".

En realidad, no tenemos una colisión de objetos Git, por lo que lo mejor que podemos hacer es ejecutar uno de los PDF destrozados a través de test-sha1. Esto debería desencadenar la verificación de colisión y morir.

¿Podría mejorarse Git para vivir con eso, o tendría que cambiar a un nuevo algoritmo hash?

Actualización de diciembre de 2017 con Git 2.16 (Q1 2018): este esfuerzo para admitir un SHA alternativo está en marcha: consulte " ¿Por qué Git no usa SHA más moderno? ".

Podrá usar otro algoritmo hash: SHA1 ya no es el único para Git.

Git 2.18 (Q2 2018) documenta ese proceso.

Ver commit 5988eb6 , commit 45fa195 (26 de marzo de 2018) por Ævar Arnfjörð Bjarmason ( avar) .
^{(Fusionada por Junio ​​C Hamano - gitster- en commit d877975 , 11 abr 2018)}

doc hash-function-transition: aclarar qué significa SHAttered

Intenta aclarar qué significa el ataque SHAttered en la práctica para Git.
La versión anterior del texto no mencionaba que Git ya tuviera una mitigación para este ataque específico, que según los investigadores de SHAttered detectará ataques de colisión criptoanalítica.

Puede que haya entendido mal algunos de los matices, pero que yo sepa, este nuevo texto resume con precisión la situación actual con SHA-1 en git. Es decir, git ya no usa SHA-1, usa Hardened-SHA-1 (de hecho, producen las mismas salidas el 99.99999999999 ...% del tiempo).

Por lo tanto, el texto anterior era incorrecto al afirmar que:

[...] Como resultado [de SHAttered], SHA-1 ya no puede considerarse criptográficamente seguro [...]

Ese no es el caso. Tenemos una mitigación contra SHAttered, sin embargo , consideramos prudente avanzar para trabajar en NewHashcaso de que surjan vulnerabilidades futuras en SHA-1 o Hardened-SHA-1.

Entonces la nueva documentación ahora dice:

Git v2.13.0 y posteriormente se trasladó a una implementación SHA-1 reforzada de forma predeterminada, que no es vulnerable al ataque SHAttered.

Por lo tanto, Git ya ha migrado a un nuevo hash que no es SHA-1 y no comparte sus vulnerabilidades, su nueva función hash solo produce exactamente la misma salida para todas las entradas conocidas, excepto dos PDF publicados por SHAttered investigadores, y la nueva implementación (escrita por esos investigadores) pretende detectar futuros ataques de colisión criptoanalítica.

En cualquier caso, se considera prudente pasar cualquier variante de SHA-1 a un nuevo hash. No hay garantía de que futuros ataques contra SHA-1 no se publiquen en el futuro, y esos ataques pueden no tener mitigaciones viables.

Si SHA-1 y sus variantes se rompieran realmente, la función hash de Git ya no podría considerarse criptográficamente segura. Esto afectaría la comunicación de valores hash porque no podíamos confiar en que un valor hash dado representara la buena versión conocida del contenido que pretendía el hablante.

Nota: ese mismo documento ahora (Q3 2018, Git 2.19) hace referencia explícita al "nuevo hash" como SHA-256 : vea " ¿Por qué Git no usa SHA más moderno? ".

Google ahora afirma que la colisión SHA-1 es posible bajo ciertas condiciones previas: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Dado que git usa SHA-1 para verificar la integridad del archivo, esto significa que la integridad del archivo en git se ve comprometida.

En mi opinión, git definitivamente debería usar un mejor algoritmo de hash ya que ahora es posible una colisión deliberada.

Una colisión de hash es tan poco probable que es alucinante. Los científicos de todo el mundo están tratando de lograr uno, pero aún no lo lograron. Sin embargo, para ciertos algoritmos como MD5 tuvieron éxito.

¿Cuáles son las probabilidades?

SHA-256 tiene 2 ^ 256 posibles hashes. Eso es alrededor de 10 ^ 78 . O para ser más gráfico, las posibilidades de una colisión son aproximadamente

1: 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

La posibilidad de ganar la lotería es de aproximadamente 1: 14 millones . ¡La posibilidad de una colisión con SHA-256 es como ganar la lotería en 11 días consecutivos !

Explicación matemática: 14 000 000 ^ 11 ~ 2 ^ 256

Además, el universo tiene alrededor de 10 ^ 80 átomos. Eso es solo 100 veces más que las combinaciones SHA-256.

Exitosa colisión MD5

Incluso para MD5 las posibilidades son pequeñas. Sin embargo, los matemáticos lograron crear una colisión:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 a 80d1e c69821bcb6a88393 96f965 2 b6ff72a70

tiene el mismo MD5 que

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 a b6ff72a70

Esto no significa que MD5 sea menos seguro ahora que su algoritmo está descifrado. Puede crear colisiones MD5 a propósito, pero la posibilidad de una colisión MD5 accidental sigue siendo 2 ^ 128, lo que sigue siendo mucho.

Conclusión

No tiene que preocuparse por las colisiones. Los algoritmos de hash son la segunda forma más segura de verificar la uniformidad del archivo. La única forma más segura es una comparación binaria.

Bueno, supongo que ahora sabemos lo que sucedería: debe esperar que su repositorio se corrompa ( fuente ).

Recientemente encontré una publicación del 29/04/2013 en un grupo de discusión de BSD en

http://openbsd-archive.7691.n7.nabble.com/Why-does-OpenBSD-use-CVS-td226952.html

donde el cartel dice:

Me encontré con una colisión de hash una vez, usando git rebase.

Lamentablemente, no proporciona pruebas de su reclamo. Pero tal vez le gustaría tratar de contactarlo y preguntarle sobre este supuesto incidente.

Pero en un nivel más general, debido al ataque de cumpleaños, la posibilidad de una colisión de hash SHA-1 es 1 en pow (2, 80).

Esto suena mucho y ciertamente es mucho más que el número total de versiones de archivos individuales presentes en todos los repositorios Git del mundo combinados.

Sin embargo, esto solo se aplica a las versiones que realmente permanecen en el historial de versiones.

Si un desarrollador confía mucho en el rebase, cada vez que se ejecuta un rebase para una rama, todos los commits en todas las versiones de esa rama (o parte de la rama) obtienen nuevos hashes. Lo mismo es cierto para cada archivo modificado con "git filter-branch". Por lo tanto, "rebase" y "filter-branch" pueden ser grandes multiplicadores para la cantidad de hashes generados a lo largo del tiempo, aunque no todos se guarden realmente: Frecuentemente, después de rebase (especialmente con el propósito de "limpiar" una rama ), la rama original se descarta.

Pero si la colisión ocurre durante el rebase o la ramificación del filtro, aún puede tener efectos adversos.

Otra cosa sería estimar el número total de entidades hash en repositorios git y ver qué tan lejos están de pow (2, 80).

Digamos que tenemos alrededor de 8 mil millones de personas, y todas ellas estarían ejecutando git y mantendrían sus cosas versionadas en 100 repositorios git por persona. Supongamos además que el repositorio promedio tiene 100 confirmaciones y 10 archivos, y solo uno de esos archivos cambia por confirmación.

Para cada revisión tenemos al menos un hash para el objeto del árbol y el objeto de confirmación en sí. Junto con el archivo modificado, tenemos 3 hashes por revisión y, por lo tanto, 300 hashes por repositorio.

Para 100 repositorios de 8 mil millones de personas, esto proporciona pow (2, 47) que todavía está lejos de pow (2, 80).

Sin embargo, esto no incluye el supuesto efecto de multiplicación mencionado anteriormente, porque no estoy seguro de cómo incluirlo en esta estimación. Tal vez podría aumentar considerablemente las posibilidades de una colisión. Especialmente si los repositorios muy grandes que tienen un largo historial de confirmaciones (como el Kernel de Linux) son modificados por muchas personas para pequeños cambios, que sin embargo crean diferentes hashes para todas las confirmaciones afectadas.