usar tag remote how hacer drop delete create como git hash sha1 hash-collision

remote - how to delete tag git



Colisión hash en git (9)

¿Qué pasaría realmente si tuviera una colisión hash al usar git?

Por ejemplo, me las arreglé para enviar dos archivos con la misma suma de comprobación sha1, ¿lo notaría o dañaría alguno de los archivos?

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

(Por favor, no desvíe esta pregunta al hablar de lo poco probable que es - Gracias)

¿Podría mejorarse 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 evita el problema, solo hace que sea menos probable que suceda. Entonces debes elegir una muy buena función hash (SHA-1 ya lo es, pero pediste que no te lo dijeran :)

¡Una colisión hash es tan poco probable que es pura alucinación! Los científicos de todo el mundo se esfuerzan por lograrlo, pero aún no lo lograron. Para ciertos algoritmos, como MD5, tuvieron éxito, sin embargo.

¿Cuáles son las probabilidades?

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

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 probabilidad de ganar la lotería es de aproximadamente 1: 14 Mio. ¡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 universe tiene aproximadamente 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 mínimas. Sin embargo, los matemáticos lograron crear una colisión:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89 55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0 e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

tiene el mismo MD5 que

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89 55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0 e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

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

Conclusión

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

Bueno, supongo que ahora sabemos lo que sucedería, debería esperar que su repositorio se corrompiera ( source ).

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 está comprometida.

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

No es posible responder a 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 sobre 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 probable será. Ahora, la gran mayoría de las colisiones serán un galimatías, haciendo que sea mucho más probable que sucedan realmente (nunca verificaría en galimatías ... incluso una imagen binaria está algo estructurada). Al final, las posibilidades son remotas. Para responder a su pregunta, sí, git los tratará como si fueran iguales, cambiar el algoritmo de hash no ayudaría, tomaría un "segundo control" de algún tipo, pero en última instancia, necesitaría tantos datos de "verificación adicional" como la longitud de los datos es 100% segura ... tenga en cuenta que sería 99.99999 ... a una cantidad realmente larga de dígitos ... seguro con un simple control como el que describe. SHA-x son hashes criptográficamente fuertes, lo que significa que generalmente no es difícil crear intencionalmente dos conjuntos de datos fuente que sean MUY SIMILARES entre sí y que tengan el mismo hash. Un pequeño cambio en los datos debería crear más de un (preferiblemente tantos como sea posible) bits de cambio en la salida hash, lo que también significa que es muy difícil (pero no imposible) trabajar desde el hash al conjunto completo de colisiones y, por lo tanto, extraer el mensaje original de ese conjunto de colisiones; todas excepto algunas serán un galimatías, y de las que no lo son aún hay un gran número para examinar si la longitud del mensaje es significativa. La desventaja de un hash criptográfico es que son lentos de calcular ... en general.

Entonces, ¿qué significa todo eso para Git? No mucho. Los hashes se hacen 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 muy bajas, no es una posibilidad real de ocurrir y no se pueden detectar inmediatamente (es decir, su código probablemente dejará de funcionar repentinamente), lo que permite al usuario solucionar el problema (hacer una copia de seguridad de una revisión, y haz el cambio de nuevo, y casi seguro obtendrás 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 ti si estás almacenando binarios arbitrarios en git, que no es realmente lo que es el modelo de uso primario. Si desea hacer eso ... probablemente sea mejor que use una base de datos tradicional.

No está mal pensar en esto; es una buena pregunta que mucha gente simplemente hace pasar por "tan poco probable que no valga la pena pensar", pero en realidad es un poco más complicado que eso. Si Ocurre, debe ser fácilmente detectable, no será una corrupción silenciosa en un flujo de trabajo normal.

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

Dado que ahora es posible una colisión SHA1 (como menciono 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) .

Consulte 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 de marzo de 2017)

Makefile : hace que DC_SHA1 el predeterminado

Solíamos usar la implementación SHA1 de la biblioteca OpenSSL de forma predeterminada.
Como estamos tratando de tener cuidado contra los ataques de colisión después del reciente anuncio "roto", cambie el valor predeterminado para animar 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 mediante OPENSSL_SHA1=YesPlease cuando ejecuten " make ".

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

¿Se podría mejorar 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 apoyar un SHA alternativo está en marcha: ver " .com/a/47838703/6309 ".

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

Git 2.18 (Q2 2018) documentos que procesan.

Ver commit 5988eb6 , commit 45fa195 (26 de marzo de 2018) por Ævar Arnfjörð Bjarmason ( avar ) .
(Fusionado por Junio ​​C Hamano - gitster - en commit d877975 , 11 de abril de 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 hacía mención alguna a que Git ya tenía una mitigación para este ataque específico, que los investigadores de SHAttered afirman detectarán los ataques de colisión criptoanalítica.

Puede que haya obtenido algunos de los matices incorrectos, pero hasta donde sé, 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 (producen exactamente las mismas salidas 99.99999999999 ...% de las veces).

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

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

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

Entonces la nueva documentación ahora dice:

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

Así, Git ya ha migrado a un nuevo hash que no es SHA-1 y no comparte sus vulnerabilidades, su nueva función hash simplemente produce exactamente el mismo resultado para todas las entradas conocidas, excepto dos PDF publicados por SHAttered. Los investigadores y la nueva implementación (escrita por esos investigadores) afirman detectar futuros ataques de colisión criptoanalítica.

De todos modos, se considera prudente pasar cualquier variante de SHA-1 a un nuevo hash. No hay garantía de que los ataques futuros a 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 se podría considerar criptográficamente segura. Esto impactaría en la comunicación de los valores de hash porque no podríamos confiar en que un valor de hash dado representara la buena versión conocida del contenido que pretendía el hablante.

Recientemente encontré una publicación del 2013-04-29 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 hash una vez, usando git rebase.

Lamentablemente, no proporciona ninguna prueba para 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 probabilidad de una colisión 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 de Git combinados.

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

Si un desarrollador se basa mucho en la rebase, cada vez que se ejecuta una rebase para una rama, todas las confirmaciones en todas las versiones de esa rama (o parte redistribuida de la rama) obtienen nuevos valores hash. Lo mismo es cierto para cada archivo que se modifique con "git filter-branch". Por lo tanto, "rebase" y "filter-branch" podrían ser grandes multiplicadores para el número de hashes generados a lo largo del tiempo, aunque no todos se mantienen: con frecuencia, después de rebase (especialmente con el propósito de "limpiar" una rama ), la rama original es desechada.

Pero si la colisión ocurre durante la rebase o la rama de 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 ejecutarían git y mantendrían sus cosas versionadas en 100 repositorios de git por persona. Supongamos además que el repositorio promedio tiene 100 commits y 10 archivos, y solo uno de esos archivos cambia por commit.

Para cada revisión, tenemos al menos un hash para el objeto de árbol y el objeto de compromiso 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 billones de personas, esto da pow (2, 47) que aún 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 las posibilidades de una colisión considerablemente. Especialmente si los repositorios muy grandes que tienen un historial de compromiso largo (como el kernel de Linux) son actualizados por muchas personas para pequeños cambios, que sin embargo crean hashes diferentes para todas las confirmaciones afectadas.

Un hash SHA-1 es una cadena de 40 caracteres hexadecimales ... eso es 4 bits por personaje multiplicado por 40 ... 160 bits. Ahora sabemos que 10 bits es 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 hash SHA-1 diferentes ... 10 48 .

¿De qué es este equivalente? Bueno, la Luna está compuesta de alrededor de 10 47 átomos. Entonces, si tenemos 10 Lunas ... y escoges aleatoriamente un átomo en una de estas lunas ... y luego sigues adelante y tomas un átomo aleatorio sobre ellas nuevamente ... entonces la probabilidad de que elijas el mismo átomo dos veces , es la probabilidad de que dos commit de git tengan el mismo hash SHA-1.

Ampliando esto podemos hacer la pregunta:

¿Cuántas confirmaciones necesitas en un repositorio antes de que debas preocuparte por las colisiones?

Esto se relaciona con los llamados "Ataques de cumpleaños", que a su vez se refieren a la "Paradoja de cumpleaños" o "Problema de cumpleaños", que establece que cuando se elige al azar de un conjunto determinado, se necesitan sorprendentemente pocas selecciones antes de que sea más probable que haber elegido algo dos veces Pero "sorprendentemente pocos" es un término muy relativo aquí.

Wikipedia tiene una tabla sobre la probabilidad de colisiones Birthday Paradox . No hay entrada para un hash de 40 caracteres. Pero una interpolación de las entradas para 32 y 48 caracteres nos lleva al rango de 5 * 10 22 commit de git para una probabilidad del 0.1% de una colisión. Eso es cincuenta mil millones de millones de compromisos diferentes, o cincuenta compromisos de Zetta , antes de haber alcanzado una probabilidad del 0.1% de que tenga una colisión.

La suma de bytes de los valores hash 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 generar códigos más rápido que YouTube. Buena suerte con eso. :RE

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

Pero que si...?

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

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

  1. Si ya existe un blob con el mismo hash, no recibirás ninguna advertencia. Todo parece estar bien, pero cuando presionas, 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 haces un blob con el mismo hash: todo parecerá normal, hasta que intentes empujar o alguien clone tu repositorio. Entonces verás que el repositorio está corrupto.
  3. Si ya existe un objeto commit y crea un blob con el mismo hash: igual que el # 2 - corrupto
  4. Si ya existe un blob y crea un objeto commit con el mismo hash, fallará al actualizar el "ref".
  5. Si ya existe un blob y haces un objeto de árbol con el mismo hash. Fallará al crear la confirmación.
  6. Si un objeto de árbol ya existe y crea un objeto de confirmación con el mismo hash, fallará al actualizar el "ref".
  7. Si un objeto de árbol ya existe y crea un objeto de árbol con el mismo hash, todo parecerá correcto. Pero cuando se compromete, todo el repositorio hará referencia al árbol equivocado.
  8. Si ya existe un objeto commit y usted crea un objeto commit con el mismo hash, todo parecerá correcto. Pero cuando se compromete, la confirmación nunca se creará, y el puntero HEAD se moverá a una confirmación anterior.
  9. Si ya existe un objeto commit y usted crea un objeto tree con el mismo hash, fallará al crear el commit.

Como puede parecer, algunos casos no son buenos. Especialmente los casos # 2 y # 3 arruinan su repositorio. Sin embargo, parece que la falla permanece dentro de ese repositorio, y la improbabilidad ataque / extraño no se propaga a otras repositorias.

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