¿Cómo Git manejar un SHA-1 de la colisión en un blob?
https://stackoverflow.com/questions/9392365
-
29-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Probablemente esto nunca había sucedido en el mundo real, sin embargo, y puede que nunca suceda, pero consideremos esto:dicen que usted tiene un repositorio de git, hacer un commit, y obtener una muy muy mala suerte:uno de los blobs termina teniendo el mismo SHA-1 como otro que ya está en su repositorio.La pregunta es, ¿cómo Git manejar esto?Simplemente no?Encontrar una manera de vincular las dos notas y comprobar que es necesaria según el contexto?
Más de un cerebro teaser de un problema real, pero me he encontrado con el problema interesante.
Solución
Hice un experimento para averiguar exactamente cómo se comportaría Git en este caso. Esto es con la versión 2.7.9 ~ rc0 + next.20151210 (versión Debian). Básicamente, reduje el tamaño de hash de 160 bits a 4 bits aplicando la siguiente diferencia y reconstruyendo git:
--- git-2.7.0~rc0+next.20151210.orig/block-sha1/sha1.c
+++ git-2.7.0~rc0+next.20151210/block-sha1/sha1.c
@@ -246,6 +246,8 @@ void blk_SHA1_Final(unsigned char hashou
blk_SHA1_Update(ctx, padlen, 8);
/* Output hash */
- for (i = 0; i < 5; i++)
- put_be32(hashout + i * 4, ctx->H[i]);
+ for (i = 0; i < 1; i++)
+ put_be32(hashout + i * 4, (ctx->H[i] & 0xf000000));
+ for (i = 1; i < 5; i++)
+ put_be32(hashout + i * 4, 0);
}
Luego hice algunas confirmaciones y noté lo siguiente.
- Si ya existe un blob con el mismo hash, no recibirá ninguna advertencia. Todo parece estar bien, pero cuando presiona, alguien clona o revierte, perderá la última versión (de acuerdo con lo explicado anteriormente).
- Si ya existe un objeto de árbol y crea un blob con el mismo hash: Todo parecerá normal, hasta que intente presionar o alguien clone su repositorio. Entonces verá que el repositorio está dañado.
- Si ya existe un objeto de confirmación y crea un blob con el mismo hash: igual que el n. ° 2: corrupto
- Si ya existe un blob y crea un objeto de confirmación con el mismo hash, fallará al actualizar la "ref".
- Si ya existe un blob y crea un objeto de árbol con el mismo hash. Fallará al crear la confirmación.
- Si ya existe un objeto de árbol y crea un objeto de confirmación con el mismo hash, fallará al actualizar la "ref".
- Si ya existe un objeto de árbol y crea un objeto de árbol con el mismo hash, todo parecerá correcto. Pero cuando confirme, todo el repositorio hará referencia al árbol incorrecto.
- Si ya existe un objeto de confirmación y crea un objeto de confirmación con el mismo hash, todo parecerá correcto. Pero cuando realiza una confirmación, la confirmación nunca se creará y el puntero HEAD se moverá a una confirmación anterior.
- Si ya existe un objeto de confirmación y crea un objeto de árbol con el mismo hash, fallará al crear la confirmación.
Para el n. ° 2, normalmente obtendrá un error como este cuando ejecute "git push":
error: object 0400000000000000000000000000000000000000 is a tree, not a blob
fatal: bad blob object
error: failed to push some refs to origin
o:
error: unable to read sha1 file of file.txt (0400000000000000000000000000000000000000)
si borra el archivo y luego ejecuta "git checkout file.txt".
Para los números 4 y 6, normalmente obtendrá un error como este:
error: Trying to write non-commit object
f000000000000000000000000000000000000000 to branch refs/heads/master
fatal: cannot update HEAD ref
al ejecutar "git commit". En este caso, normalmente puede escribir "git commit" nuevamente, ya que esto creará un nuevo hash (debido a la marca de tiempo modificada)
Para los números 5 y 9, normalmente obtendrá un error como este:
fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object
al ejecutar "git commit"
Si alguien intenta clonar su repositorio dañado, normalmente verá algo como:
git clone (one repo with collided blob,
d000000000000000000000000000000000000000 is commit,
f000000000000000000000000000000000000000 is tree)
Cloning into 'clonedversion'...
done.
error: unable to read sha1 file of s (d000000000000000000000000000000000000000)
error: unable to read sha1 file of tullebukk
(f000000000000000000000000000000000000000)
fatal: unable to checkout working tree
warning: Clone succeeded, but checkout failed.
You can inspect what was checked out with 'git status'
and retry the checkout with 'git checkout -f HEAD'
Lo que me "preocupa" es que en dos casos (2,3) el repositorio se corrompe sin ninguna advertencia, y en 3 casos (1,7,8), todo parece estar bien, pero el contenido del repositorio es diferente al esperas que sea. Las personas que clonan o tiran tendrán un contenido diferente al tuyo. Los casos 4, 5, 6 y 9 están bien, ya que se detendrá con un error. Supongo que sería mejor si fallara con un error al menos en todos los casos.
Otros consejos
Respuesta original (2012) (consulte la colisión shattered.io 2017 SHA1 a continuación)
Esa respuesta anterior (2006) de Linus podría seguir siendo relevante:
colisión del archivo idéntico que genera el mismo SHA1).Nop. Si tiene el mismo SHA1, significa que cuando recibamos el objeto desde el otro extremo, no sobrescribiremos el objeto que ya tenemos.
Entonces, lo que sucede es que si alguna vez vemos una colisión, el objeto "anterior" en cualquier repositorio en particular siempre terminará anulando. Pero tenga en cuenta que "anterior" es obviamente por repositorio, en el sentido de que el objeto git La red genera un DAG que no está completamente ordenado, por lo que si bien los diferentes repositorios estarán de acuerdo sobre lo que es "anterior" en el caso de la ascendencia directa, si el objeto pasó por ramas separadas y no directamente relacionadas, dos repositorios diferentes obviamente pueden haber obtenido los dos objetos en diferente orden.
Sin embargo, "lo anterior se anulará" es mucho lo que desea desde el punto de vista de la seguridad: recuerde que el modelo de git es que debe confiar principalmente solo en su propio repositorio.
Entonces, si haces un "git pull", los nuevos objetos entrantes son, por definición, menos confiables que los objetos que ya tienes, y como tal sería incorrecto permitir que un nuevo objeto reemplace uno antiguo.Entonces tiene dos casos de colisión:
del tipo inadvertido , en el que de alguna manera tienes mucha muy mala suerte y dos archivos terminan teniendo el mismo SHA1.
En ese punto, lo que sucede es que cuando confirmas ese archivo (o haces un "git-update-index" para moverlo al índice, pero aún no confirmado), se calculará el SHA1 del nuevo contenido, pero ya que coincide un objeto antiguo, no se creará un objeto nuevo y la confirmación o índice termina apuntando al objeto antiguo .
No lo notará inmediatamente (ya que el índice coincidirá con el objeto antiguo SHA1, y eso significa que algo como "git diff" usará la copia extraída), pero si alguna vez hace una diferencia a nivel de árbol (o hace una clonar o extraer, o forzar un pago) de repente notará que ese archivo ha cambiado a algo completamente diferente de lo que esperaba.
Por lo general, notaría este tipo de colisión con bastante rapidez.
En noticias relacionadas, la pregunta es qué hacer con la colisión accidental.
En primer lugar, permítanme recordarles a las personas que el tipo de colisión inadvertida es realmente realmente muy improbable, por lo que es muy probable que nunca la veamos en la historia completa del universo.
Pero si sucede, no es el fin del mundo: lo más probable es que tengas que hacer simplemente cambiar el archivo que chocó ligeramente y forzar una nueva confirmación con el cambio contenido (agregue un comentario que diga "/* This line added to avoid collision */") y luego enséñele a git sobre la magia SHA1 que se ha demostrado que es peligrosa.
Entonces, en un par de millones de años, tal vez tengamos que agregar uno o dos valores SHA1 "envenenados" a git. Es muy poco probable que se trate de un problema de mantenimiento;)El tipo de colisión del atacante porque alguien rompió (o forzó) SHA1.
Este es claramente mucho más probable que el tipo inadvertido, pero por definición siempre es un repositorio "remoto". Si el atacante tuviera acceso al repositorio local, tendría formas mucho más fáciles de arruinarlo.
Entonces, en este caso, la colisión no es un problema en absoluto : obtendrá un repositorio "malo" que es diferente de lo que pretendía el atacante, pero ya que nunca usará su objeto que colisiona, es literalmente no diferente del atacante que simplemente no ha encontrado una colisión en absoluto , sino que simplemente usa el objeto que ya tenía (es decir, es 100% equivalente al "trivial"
La pregunta sobre el uso de SHA-256 se menciona con regularidad, pero no se actúa sobre ello por ahora (2012).
Nota: a partir de 2018 y Git 2.19 , el código se está refactorizando para usar SHA-256.
Nota (Humor): puede forzar un compromiso con un prefijo SHA1 en particular, con el proyecto gitbrute de Brad Fitzpatrick (bradfitz) .
gitbrute fuerza bruta un par de marcas de tiempo de autor + confirmador de modo que la confirmación de git resultante tenga el prefijo deseado.
Ejemplo: https://github.com/bradfitz/deadbeef
Daniel Dinnyes señala en los comentarios a 7.1 Git Tools - Selección de revisión , que incluye:
Existe una mayor probabilidad de que todos los miembros de su equipo de programación sean atacados y asesinados por lobos en incidentes no relacionados en la misma noche.
Incluso el más reciente (febrero de 2017) shattered.io demostró la posibilidad de falsificar un Colisión SHA1:
(ver mucho más en mi respuesta separada , incluida la publicación de Linus Torvalds en Google+)
- a / todavía requiere más de 9,223,372,036,854,775,808 cálculos de SHA1. Esto tomó la potencia de procesamiento equivalente a 6.500 años de cálculos con una sola CPU y 110 años de cálculos con una sola GPU.
- b / falsificaría un archivo (con el mismo SHA1), pero con la restricción adicional, su contenido y tamaño produciría el mismo SHA1 (una colisión en el contenido solo no es suficiente): consulte " ¿Cómo se calcula el hash de git? "): a blob SHA1 se calcula en función del contenido y tamaño .
Consulte " Duración de las funciones de hash criptográficas " en Valerie Anita Aurora para obtener más información.
En esa página, nota:
Google pasó 6500 años de CPU y 110 años de GPU para convencer a todos de que debemos dejar de usar SHA-1 para aplicaciones críticas de seguridad.
También porque fue genial
Vea más en mi respuesta separada a continuación .
Según Pro Git :
Si compromete un objeto que tiene el mismo valor SHA-1 que un objeto anterior en su repositorio, Git verá el objeto anterior ya en su base de datos Git y asumirá que ya fue escrito. Si intenta verificar ese objeto nuevamente en algún momento, siempre obtendrá los datos del primer objeto.
Por lo tanto, no fallaría, pero tampoco guardaría su nuevo objeto.
No sé cómo se vería eso en la línea de comandos, pero ciertamente sería confuso.
Un poco más abajo, esa misma referencia intenta ilustrar la probabilidad de tal colisión:
Aquí tienes un ejemplo para darte una idea de lo que se necesitaría para provocar una colisión SHA-1. Si los 6.500 millones de seres humanos en la Tierra estuvieran programando, y cada segundo, cada uno estuviera produciendo un código que fuera el equivalente a la historia completa del kernel de Linux (1 millón de objetos Git) y colocándolo en un enorme repositorio Git, tomaría 5 años hasta ese repositorio contenía suficientes objetos para tener una probabilidad del 50% de una sola colisión de objetos SHA-1. Existe una mayor probabilidad de que todos los miembros de su equipo de programación sean atacados y asesinados por lobos en incidentes no relacionados en la misma noche.
Para agregar a mi respuesta anterior de 2012 , ahora hay (febrero de 2017, cinco años después), una ejemplo de colisión SHA-1 real con shattered.io , donde puedes crear dos colisiones Archivos PDF: es decir, obtener una firma digital SHA-1 en el primer archivo PDF que también se puede utilizar como firma válida en el segundo archivo PDF.
Consulte también " En las puertas de la muerte durante años, la función SHA1 ampliamente utilizada ahora está muerta ", y esta ilustración .
Actualización 26 de febrero: Linus confirmó los siguientes puntos en una publicación de Google+ :
(1) Primero, el cielo no se cae. Hay una gran diferencia entre usar un hash criptográfico para cosas como la firma de seguridad y usar uno para generar un "identificador de contenido" para un sistema de contenido direccionable como git.
(2) En segundo lugar, la naturaleza de este ataque SHA1 en particular significa que en realidad es bastante fácil de mitigar, y ya se han publicado dos conjuntos de parches para esa mitigación.
(3) Y finalmente, hay una transición razonablemente sencilla a algún otro hash que no romperá el mundo, ni siquiera a los viejos repositorios de git.
Con respecto a esa transición, consulte Git 2.16 del primer trimestre de 2018 que agrega una estructura que representa el algoritmo hash. La implementación de esa transición ha comenzado.
A partir de Git 2.19 (tercer trimestre de 2018) , Git eligió SHA-256 como NewHash , y está en proceso de integrarlo al código (lo que significa que SHA1 sigue siendo el predeterminado (Q2 2019, Git 2.21), pero SHA2 será el sucesor)
Respuesta original (25 de febrero) Pero:
- Esto permite falsificar un blob, sin embargo, el SHA-1 del árbol aún cambiaría ya que el tamaño del blob forjado podría no ser el mismo que el original: consulte " ¿Cómo se calcula el hash de git? "; un blob SHA1 se calcula según el contenido y el tamaño .
Sin embargo, tiene algún problema congit-svn. O mejor dicho con el propio svn , como visto aquí . - Como mencioné en mi respuesta original , el costo de tal intento sigue siendo prohibitivo por ahora (6500 años de CPU y 100 años de GPU) Consulte también Valerie Anita Aurora en " Duración de las funciones hash criptográficas ".
- Como se comentó antes, este no es sobre seguridad o confianza, pero la integridad de los datos (deduplicación y detección de errores) que puede ser fácilmente detectado por un
git fsck, como mencionado por Linus Torvalds hoy .git fsckadvertiría sobre un mensaje de confirmación con da opaco
NUL (aunque NUL no siempre está presente en un archivo fraudulento ). No todo el mundo activa
transfer.fsck , pero GitHub lo hace: cualquier push se cancelará en el caso de un objeto con formato incorrecto o un enlace roto. Aunque ... hay un motivo por el que esto no está activado de forma predeterminada .
El problema real al crear dos repositorios de Git con el mismo hash de confirmación principal y diferentes contenidos. E incluso entonces, el ataque sigue siendo complicado .
El punto de un SCM es que no se trata de un evento único, sino sobre la historia continua. Eso también significa fundamentalmente que un El ataque exitoso debe funcionar con el tiempo y no ser detectable.
Si puede engañar a un SCM una vez, inserte su código y se detectado la próxima semana, en realidad no hizo nada útil. Solo te quemaste.
Joey Hess prueba esos PDF en un repositorio de Git y encontró :
Eso incluye dos archivos con el mismo SHA y tamaño, que obtienen diferentes blobs gracias a la forma en que git antepone el encabezado al contenido.
joey@darkstar:~/tmp/supercollider>sha1sum bad.pdf good.pdf
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a bad.pdf
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a good.pdf
joey@darkstar:~/tmp/supercollider>git ls-tree HEAD
100644 blob ca44e9913faf08d625346205e228e2265dd12b65 bad.pdf
100644 blob 5f90b67523865ad5b1391cb4a1c010d541c816c1 good.pdf
Si bien agregar datos idénticos a estos archivos en colisión genera otras colisiones, anteponer datos no.
Entonces, el vector principal de ataque (forjar un compromiso) sería :
- Genere un objeto de confirmación regular;
- use todo el objeto de confirmación + NUL como prefijo elegido, y
- utilice el ataque de colisión de prefijo idéntico para generar la colisión de objetos buenos / malos.
- ... ¡y esto es inútil porque los objetos de confirmación buenos y malos todavía apuntan al mismo árbol!
Además, ya puede detectar y detectar ataques de colisión criptoanalíticos contra SHA-1 presentes en cada archivo con cr-marcstevens/sha1collisiondetection
Agregar una verificación similar en el propio Git tendría algún costo de cálculo .
Sobre el cambio de hash, comentarios de Linux :
El tamaño del hash y la elección del algoritmo hash son cuestiones independientes.
Lo que probablemente harías es cambiar a un hash de 256 bits, usa eso internamente y en la base de datos nativa de git, y luego solo por defecto mostrar el hash como una cadena hexadecimal de 40 caracteres (algo así como ya abreviar cosas en muchas situaciones).
De esa manera, las herramientas de git ni siquiera ven el cambio a menos que se pasen algún argumento especial "--full-hash" (o "--abbrev=64" o lo que sea - siendo por defecto que abreviamos a 40).
Aún así, un
eferrer "> plan de transición (de SHA1 a otra función hash) aún sería complejo , pero estudiado activamente.Una campaña
convert-to-object_id es en curso :
Actualización 20 de marzo: detalle de GitHub posible ataque y su protección :
Se puede asignar confianza a los nombres SHA-1 a través de varios mecanismos. Por ejemplo, Git le permite firmar criptográficamente una confirmación o etiqueta. Al hacerlo, firma solo el objeto de confirmación o etiqueta en sí, que a su vez apunta a otros objetos que contienen los datos del archivo real mediante el uso de sus nombres SHA-1. Una colisión en esos objetos podría producir una firma que parece válida, pero que apunta a datos diferentes a los que pretendía el firmante. En tal ataque, el firmante solo ve la mitad de la colisión y la víctima ve la otra mitad.
Protección:
El ataque reciente utiliza técnicas especiales para explotar las debilidades del algoritmo SHA-1 que encuentran una colisión en mucho menos tiempo. Estas técnicas dejan un patrón en los bytes que se puede detectar al calcular el SHA-1 de cualquier mitad de un par en colisión.
GitHub.com ahora realiza esta detección para cada SHA-1 que calcula y cancela la operación si hay evidencia de que el objeto es la mitad de un par en colisión. Eso evita que los atacantes utilicen GitHub para convencer a un proyecto de que acepte la mitad "inocente" de su colisión, además de evitar que alojen la mitad maliciosa.
Consulte " sha1collisiondetection " de Marc Stevens
Nuevamente, con Q1 2018 Git 2.16 agregando una estructura que representa el algoritmo hash, la implementación de una transición a un nuevo hash ha comenzado.
Como se mencionó anteriormente, el nuevo Hash admitido será SHA-256 .
Creo que los criptógrafos lo celebrarían.
Cita del artículo de Wikipedia sobre SHA-1 :
En febrero de 2005, se anunció un ataque de Xiaoyun Wang, Yiqun Lisa Yin y Hongbo Yu. Los ataques pueden encontrar colisiones en la versión completa de SHA-1, requiriendo menos de 2 ^ 69 operaciones.(Una búsqueda de fuerza bruta requeriría 2 ^ 80 operaciones).
Hay varias ataque de los modelos para los hash como SHA-1, pero la que suelen ser discutido es el de la colisión de búsqueda, incluyendo Marc Stevens HashClash de la herramienta.
A medida que las personas se señaló, podría forzar una colisión de hash con git, pero hacerlo no sobrescribir los objetos existentes en otro repositorio.Me imagino que incluso git push -f --no-thin no sobrescribir los objetos existentes, pero no 100% seguro.
Dicho esto, si usted hack en un repositorio remoto, entonces usted podría hacer su falsa objeto el de mayor edad allí, posiblemente hackeado la incrustación de código en un proyecto de código abierto en github o similar.Si tuviera el cuidado entonces tal vez usted podría introducir una versión hackeada de que los nuevos usuarios a descargar.
Sospecho sin embargo que muchas de las cosas a los desarrolladores del proyecto puede hacer cualquiera de los dos podría exponer o destruir accidentalmente su dólar del multi-million hack.En particular, eso es un montón de dinero por el desagüe, si algún desarrollador, que no hack, nunca se ejecuta el mencionado git push --no-thin después de modificar el efectuado en los archivos, a veces incluso sin el --no-thin en función.
