track the that que made discarded commits are and git hash-collision

the - ¿Cómo manejaría Git una colisión SHA-1 en un blob?



git revision (6)

Creo que los criptógrafos 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, que requieren menos de 2 ^ 69 operaciones. (Una búsqueda de fuerza bruta requeriría 2 ^ 80 operaciones).

Probablemente esto nunca haya sucedido en el mundo real todavía, y puede que nunca suceda, pero consideremos esto: digamos que tienes un repositorio de git, haz un commit, y te pones muy desafortunado: uno de los blobs termina teniendo el mismo SHA-1 como otro que ya está en tu repositorio. La pregunta es, ¿cómo manejaría esto Git? Simplemente fallar? ¿Encuentre una manera de vincular los dos blobs y verifique cuál se necesita según el contexto?

Más un problema mental que un problema real, pero me pareció interesante.

Hay varios modelos de ataque diferentes para hashes como SHA-1, pero el que normalmente se discute es la búsqueda de colisiones, incluida la herramienta HashClash Marc Stevens.

"A partir de 2012, Marc Stevens [34] considera que el ataque más eficiente contra SHA-1 es el que tiene un costo estimado de $ 2.77M para romper un solo valor de hash al alquilar el poder de la CPU de los servidores en la nube".

Como lo señaló la gente, podría forzar una colisión de hash con git, pero al 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 es 100% seguro.

Dicho esto, si hackeas un repositorio remoto, podrías hacer que tu objeto falso sea el más antiguo allí , posiblemente incrustando código hackeado en un proyecto de código abierto en github o similar. Si tuvieras cuidado, tal vez podrías introducir una versión pirateada que los nuevos usuarios descargaron.

Sin embargo, sospecho que muchas cosas que podrían hacer los desarrolladores del proyecto podrían exponer o destruir accidentalmente su truco multimillonario. En particular, eso es un montón de dinero en el desagüe si algún desarrollador, a quien no hackeaste, alguna vez ejecute el git push --no-thin mencionado anteriormente - no git push --no-thin después de modificar los archivos afectados, a veces incluso sin la dependencia - no --no-thin .

Hice un experimento para descubrir 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, solo reduje el tamaño de hash de 160 bits a 4 bits aplicando el siguiente diff 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); }

Entonces hice algunas confirmaciones y noté lo siguiente.

  1. Si ya existe un blob con el mismo hash, no recibirá ninguna advertencia. Todo parece estar bien, pero cuando empuja, alguien clona o revierte, perderá 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 repo está corrupto.
  3. Si ya existe un objeto de confirmación y hace un blob con el mismo hash: igual que # 2 - corrupto
  4. Si ya existe un blob y crea un objeto de confirmación con el mismo hash, fallará cuando se actualice la "referencia".
  5. Si ya existe un blob y creas un objeto de árbol con el mismo hash. Fallará al crear el commit.
  6. Si ya existe un objeto de árbol y crea un objeto de confirmación con el mismo hash, fallará cuando se actualice la "referencia".
  7. Si ya existe un objeto de árbol y crea un objeto de árbol con el mismo hash, todo parecerá correcto. Pero cuando te comprometes, 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 antigua.
  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.

Para el # 2, normalmente obtendrás un error como este cuando ejecutas "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 elimina el archivo y luego ejecuta "git checkout file.txt".

Para # 4 y # 6, normalmente obtendrás un error como este:

error: Trying to write non-commit object f000000000000000000000000000000000000000 to branch refs/heads/master fatal: cannot update HEAD ref

cuando se ejecuta "git commit". En este caso, normalmente puede volver a escribir "git commit" ya que esto creará un nuevo hash (debido a la marca de tiempo cambiada)

Para # 5 y # 9, normalmente obtendrá un error como este:

fatal: 1000000000000000000000000000000000000000 is not a valid ''tree'' object

cuando se ejecuta "git commit"

Si alguien intenta clonar tu repositorio corrupto, típicamente verán 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 advertencias, y en 3 casos (1,7,8), todo parece estar bien, pero el contenido del repositorio es diferente al que usted espera. ser. La clonación o extracción de personas tendrá un contenido diferente al que tienes. 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.

Para agregar a mi respuesta anterior de 2012 , ahora hay (febrero de 2017, cinco años después), un ejemplo de colisión SHA-1 real con shattered.io n donde puede crear dos archivos PDF en colisión: es obtener un SHA- 1 firma digital en el primer archivo PDF que también puede ser abusada como una firma válida en el segundo archivo PDF.
Consulte también " En la puerta 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 plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL :

(1) En primer lugar, el cielo no se está cayendo. 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 bastante sencilla a otro hash que no romperá el mundo, o incluso los antiguos repositorios de git.

Con respecto a esa transición, consulte el Q1 2018 Git 2.16 y agregue una estructura que represente el algoritmo hash. La implementación de esa transición ha comenzado.

Respuesta original (25 de febrero) Pero:

  • Esto permite forjar 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 git? "; un blob SHA1 se calcula en función del contenido y el tamaño .
    Aunque tiene algunos problemas para git-svn . O más bien con svn en sí , como se ve aquí .
  • Como mencioné en mi respuesta original , el costo de tal intento sigue siendo prohibitivo por ahora (6.500 CPU años y 100 GPU). Ver también Valerie Anita Aurora en "La vida de las funciones criptográficas de hash ".
  • Como se comentó anteriormente, esto no se trata de seguridad o confianza, sino de integridad de datos (deduplicación y detección de errores) que puede ser fácilmente detectada por un git fsck , como lo menciona Linus Torvalds hoy. git fsck advertiría sobre un mensaje de confirmación con datos opacos ocultos después de un NUL (aunque NUL no siempre está presente en un archivo fraudulento ).
    No todos activan transfer.fsck , pero GitHub lo hace: cualquier impulso sería abortado en el caso de un objeto mal formado o un enlace roto. Aunque ... hay una razón por la que esto no está activado por defecto .
  • un archivo pdf puede tener datos binarios arbitrarios que puede cambiar para generar un SHA-1 en colisión, en oposición al código fuente forjado.
    El problema real en la creación de dos repositorios Git con el mismo hash de confirmación de cabecera y contenidos diferentes. E incluso entonces, el ataque sigue enrevesado .
  • Linus añade :

    El punto central de un SCM es que no se trata de un evento único, sino de un historial continuo. Eso también significa, fundamentalmente, que un 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 detectará la próxima semana, en realidad no hizo nada útil. Sólo 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 la adición de datos idénticos a estos archivos en conflicto genera otras colisiones, la preparación de los datos no lo hace.

Entonces el principal vector de ataque (forjar un commit) sería :

  • Generar un objeto de confirmación regular;
  • usar todo el objeto de confirmación + NUL como el prefijo elegido, y
  • use el ataque de colisión con el prefijo idéntico para generar los objetos buenos / malos en colisión.
  • ... ¡y esto es inútil porque los objetos de compromiso bueno y malo apuntan al mismo árbol!

Además, ya puede detectar ataques de colisión analítica contra SHA-1 presentes en cada archivo con cr-marcstevens/sha1collisiondetection

Agregar un cheque similar en Git en sí tendría algún costo de cálculo .

Al cambiar el hash, Linux comenta :

El tamaño del hash y la elección del algoritmo de hash son problemas independientes.
Lo que probablemente harías es cambiar a un hash de 256 bits, usarlo internamente y en la base de datos nativa de git, y luego, de forma predeterminada, solo muestra el hash como una cadena hexadecimal de 40 caracteres (algo así como la forma en que abreviamos las cosas en muchas situaciones).
De esa manera, las herramientas alrededor de git ni siquiera ven el cambio a menos que se pasen en algún argumento especial " --full-hash " (o " --abbrev=64 " o lo que sea, el valor predeterminado es que --abbrev=64 a 40).

Aún así, un plan de transición (de SHA1 a otra función hash) aún sería complejo , pero se estudiaría activamente.
Una campaña de convert-to-object_id está en progreso :

Actualización del 20 de marzo: GitHub detalla un posible ataque y su protección :

A los nombres de SHA-1 se les puede asignar confianza 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 reales del archivo utilizando 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 una mitad de la colisión, y la víctima ve la otra mitad.

Proteccion:

El ataque reciente utiliza técnicas especiales para explotar las debilidades en el algoritmo SHA-1 que encuentran una colisión en mucho menos tiempo. Estas técnicas dejan un patrón en los bytes que pueden detectarse al calcular el SHA-1 de cualquiera de las dos partes de un par en colisión.

GitHub.com ahora realiza esta detección para cada SHA-1 que calcula, y aborta 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, así como evitar que alojen a la mitad maliciosa.

Ver " cr-marcstevens/sha1collisiondetection " por 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.

Respuesta original (2012) (ver colisión SHA1 shattered.io 2017 a continuación)

Esa vieja respuesta (2006) de Linus aún podría ser relevante:

No 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 un repositorio en particular siempre terminará anulando. Pero tenga en cuenta que "anterior" es obviamente por repositorio, en el sentido de que la red de objetos git genera un DAG que no está completamente ordenado, por lo que mientras que diferentes repositorios estarán de acuerdo sobre lo que es "anterior" en el caso de ascendencia directa, si el el objeto vino a través de ramas separadas y no directamente relacionadas, obviamente, dos repos diferentes pueden haber obtenido los dos objetos en orden diferente.

Sin embargo, la "anulación de la voluntad anterior" es mucho lo que quiere desde un punto de vista de seguridad: recuerde que el modelo git es que debe confiar principalmente en su propio repositorio.
Por lo tanto, si realiza un " git pull ", los nuevos objetos entrantes son, por definición, menos confiables que los objetos que ya tiene, y como tal, sería incorrecto permitir que un nuevo objeto reemplace uno antiguo.

Así que tienes dos casos de colisión:

  • el tipo inadvertido , donde de alguna manera usted es muy desafortunado, y dos archivos terminan teniendo el mismo SHA1.
    En ese momento, lo que sucede es que cuando confirma ese archivo (o realiza un " git-update-index " para moverlo al índice, pero aún no se ha confirmado), se calculará el SHA1 de los nuevos contenidos, pero dado que coincide con un objeto antiguo, no se creará un nuevo objeto y el cometer-o-índice termina apuntando al objeto antiguo .
    No lo notará de inmediato (ya que el índice coincidirá con el objeto anterior SHA1, y eso significa que algo como " git diff " usará la copia desprotegida), pero si alguna vez hace una diferencia a nivel de árbol (o si lo hace) un clon o un pull, o forzar un checkout) de repente notará que el archivo ha cambiado a algo completamente diferente de lo que esperaba.
    Por lo tanto, generalmente notarán este tipo de colisión con bastante rapidez.
    En noticias relacionadas, la pregunta es qué hacer con la colisión involuntaria.
    En primer lugar, permítame recordarle a la gente que el tipo involuntario de colisión es realmente muy improbable, por lo que es muy probable que nunca lo veamos en la historia completa del universo.
    Pero si sucede, no es el fin del mundo: lo más probable es que deba cambiar el archivo que colisionó ligeramente y forzar una nueva confirmación con el contenido modificado (agregue un comentario que diga " /* This line added to avoid collision */ ") y luego enseñar a Git sobre la magia SHA1 que se ha demostrado que es peligrosa.
    Entonces, durante un par de millones de años, tal vez tengamos que agregar uno o dos valores de SHA1 "envenenados" a git. Es muy poco probable que sea un problema de mantenimiento;)

  • El atacante es una especie de colisión porque alguien rompió (o por fuerza bruta) 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 maneras mucho más fáciles de arruinarte.
    Entonces, en este caso, la colisión no es un problema : obtendrás un repositorio "malo" que es diferente de lo que pretendía el atacante, pero como en realidad nunca usarás su objeto en colisión, literalmente no es diferente del el atacante simplemente no encontró una colisión en absoluto , sino que simplemente usó el objeto que ya tenía (es decir, es 100% equivalente a la colisión "trivial" del archivo idéntico que genera el mismo SHA1).

La cuestión de usar SHA-256 se menciona regularmente, pero no actúa de momento.

Nota (Humor): puede forzar un compromiso con un prefijo SHA1 en particular, con el proyecto gitbrute de Brad Fitzpatrick ( bradfitz ) .

gitbrute brute forza un par de sellos de tiempo de autor + comitador, de modo que el git commit resultante tenga el prefijo deseado.

Ejemplo: https://github.com/bradfitz/deadbeef

Daniel Dinnyes señala en los comentarios a 7.1 Git Tools - Revision Selection , 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 forjar una colisión SHA1:
(ver mucho más en mi respuesta por separado , 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 SHA1. Esto tomó la potencia de procesamiento equivalente como 6.500 años de cálculos de una sola CPU y 110 años de cálculos de una sola GPU.
  • b / forjaría un archivo (con el mismo SHA1), pero con la restricción adicional, su contenido y tamaño producirían el SHA1 idéntico (una colisión en el contenido solo no es suficiente): consulte " ¿Cómo se calcula el hash git? ") : un blob SHA1 se calcula en función del contenido y el tamaño .

Consulte " Duración de las funciones hash criptográficas " de Valerie Anita Aurora para obtener más información.
En esa página, ella nota:

Google invirtió 6500 años de CPU y 110 años de GPU para convencer a todos que debemos dejar de usar SHA-1 para aplicaciones de seguridad críticas.
También porque era genial.

Ver más en mi respuesta por separado a continuación .

Según Pro Git :

Si sucede que confirma un objeto que contiene hash con el mismo valor SHA-1 que un objeto anterior en su repositorio, Git verá el objeto anterior ya en su base de datos de Git y asumirá que ya fue escrito. Si intenta revisar ese objeto nuevamente en algún momento, siempre obtendrá los datos del primer objeto.

Así que no fallaría, pero tampoco guardaría tu nuevo objeto.
No sé cómo se vería eso en la línea de comando, pero ciertamente sería confuso.

Un poco más abajo, esa misma referencia intenta ilustrar la probabilidad de tal colisión:

Aquí hay un ejemplo para darle una idea de lo que se necesitaría para obtener una colisión SHA-1. Si todos los 6.500 millones de seres humanos en la Tierra estuvieran programando, y cada segundo, cada uno producía un código que era el equivalente de toda la historia del kernel de Linux (1 millón de objetos Git) y lo insertaba en un enorme repositorio de Git, llevaría 5 años ese repositorio contenía suficientes objetos para tener una probabilidad del 50% de una única 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.