¿Por qué Git utiliza una función hash criptográfica?

139

¿Por qué Git usa SHA-1 , una función hash criptográfica, en lugar de una función hash no criptográfica más rápida?

Pregunta relacionada:

Pregunta de desbordamiento de pila ¿Por qué Git usa SHA-1 como números de versión? pregunta por qué Git usa SHA-1 en lugar de números secuenciales para confirmaciones.

Praxeolítico
fuente
Personalmente, creo que incluso usar SHA-1 roto sobre SHA-2 fue una optimización prematura.
CodesInChaos
77
@CodesInChaos: y además, incluir cualquier algoritmo en particular en el código fue una horrible violación de los principios de DI. Debería estar en un archivo de configuración XML en algún lugar ;-)
Steve Jessop
Actualización de diciembre de 2017 con Git 2.16 (Q1 2018): se está realizando un esfuerzo para admitir un SHA alternativo: consulte " ¿Por qué Git no usa SHA más moderno? ".
VonC
No hay buenos hashes no criptográficos de 160 bits o más. La mayoría son funciones altamente optimizadas de 32 bits, 64 bits o 128 bits. 128 bits está bien, pero tengo la sensación de que 128 bits es un poco bajo para un gran proyecto como git. Si saliera un hash rápido de 224/256 bits de alta calidad, probablemente sería ideal.
bryc

Respuestas:

197

TLDR;


Puede comprobarlo del propio Linus Torvalds, cuando presentó Git a Google en 2007 :
(énfasis mío)

Verificamos sumas de verificación que se consideran criptográficamente seguras. Nadie ha podido romper SHA-1, pero el punto es que SHA-1 en lo que respecta a git, ni siquiera es una característica de seguridad. Es puramente una verificación de consistencia .
Las partes de seguridad están en otra parte. Mucha gente asume que dado que git usa SHA-1 y SHA-1 se usa para cosas criptográficamente seguras, piensan que es una gran característica de seguridad. No tiene nada que ver con la seguridad, es el mejor hash que puedes obtener.

Tener un buen hash es bueno para poder confiar en sus datos , también tiene algunas otras características buenas, lo que significa que cuando usamos objetos, sabemos que el hash está bien distribuido y no tenemos que preocuparnos por ciertos problemas de distribución .

Internamente significa que, desde el punto de vista de la implementación, podemos confiar en que el hash es tan bueno que podemos usar algoritmos de hash y saber que no hay casos negativos.

Por lo tanto, hay algunas razones por las que también le gusta el lado criptográfico, pero en realidad se trata de la capacidad de confiar en sus datos.
Le garantizo que si pone sus datos en git, puede confiar en el hecho de que cinco años después, después de convertirlos de su disco duro a DVD a cualquier tecnología nueva y copiarlos, cinco años después puede verificar los datos que volver a salir es exactamente la misma información que ingresó. Y eso es algo que realmente debe buscar en un sistema de administración de código fuente .


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? ".


Mencioné en " ¿Cómo manejaría git una colisión SHA-1 en un blob? " Que podría diseñar un commit con un prefijo SHA1 en particular (aún un esfuerzo extremadamente costoso).
Pero el punto permanece, como Eric Sink menciona en el libro " Git: Cryptographic Hashes " ( Version Control by Example (2011) :

Es bastante importante que el DVCS nunca encuentre dos datos diferentes que tengan el mismo resumen. Afortunadamente, las buenas funciones criptográficas de hash están diseñadas para hacer que tales colisiones sean extremadamente improbables.

Es más difícil encontrar un buen hash no criptográfico con baja tasa de colisión, a menos que considere una investigación como "Cómo encontrar hashes no criptográficos de vanguardia con programación genética ".

También puede leer " Considere el uso del algoritmo de hash no criptográfico para acelerar el hash ", que menciona, por ejemplo, " xxhash ", un algoritmo de hash no criptográfico extremadamente rápido, que funciona a velocidades cercanas a los límites de RAM.


Las discusiones sobre cambiar el hash en Git no son nuevas:

(Linus Torvalds)

Realmente no queda nada del código de Mozilla, pero bueno, comencé desde allí. En retrospectiva, probablemente debería haber comenzado desde el código asm de PPC que ya hizo el bloqueo sensatamente, pero eso es un tipo de "retrospectiva 20/20".

Además, hey, el código de Mozilla es un montón de basura horrible, por eso estaba tan convencido de que podía mejorar las cosas. Por lo tanto, es una especie de fuente, incluso si se trata más del lado motivacional que de cualquier código restante real;)

Y debe tener cuidado sobre cómo medir la ganancia de optimización real

(Linus Torvalds)

Prácticamente puedo garantizarle que mejora las cosas solo porque hace que gcc genere un código basura, que luego oculta algunos de los problemas de P4.

(John Tapsell - johnflux)

El costo de ingeniería para actualizar git de SHA-1 a un nuevo algoritmo es mucho mayor . No estoy seguro de cómo se puede hacer bien.

En primer lugar, probablemente necesitemos implementar una versión de git (llamémosla versión 2 para esta conversación) que permita que haya un espacio para un nuevo valor hash aunque no lea ni use ese espacio, solo usa el valor hash SHA-1 que está en la otra ranura.

De esa manera, una vez que finalmente implementemos una versión más nueva de git, llamémosla versión 3, que produce hash SHA-3 además de hash SHA-1, las personas que usen git versión 2 podrán continuar interactuando.
(Aunque, según esta discusión, pueden ser vulnerables y las personas que dependen de sus parches solo SHA-1 pueden ser vulnerables).

En resumen, cambiar a cualquier hash no es fácil.


Actualización de febrero de 2017: sí, en teoría es posible calcular un SHA1 en colisión: shattered.io

¿Cómo se ve afectado el GIT?

GIT se basa fuertemente en SHA-1 para la identificación y verificación de integridad de todos los objetos de archivo y confirmaciones.
Es esencialmente posible crear dos repositorios GIT con el mismo hash head commit y diferentes contenidos, digamos un código fuente benigno y uno backdoo.
Un atacante podría potencialmente servir selectivamente cualquiera de los repositorios a usuarios específicos. Esto requerirá que los atacantes calculen su propia colisión.

Pero:

Este ataque requirió más de 9,223,372,036,854,775,808 cálculos SHA1. Esto tomó la potencia de procesamiento equivalente a 6.500 años de cálculos de CPU única y 110 años de cálculos de GPU única.

Así que no entremos en pánico todavía.
Ver más en " ¿Cómo manejaría Git una colisión SHA-1 en una gota? ".

VonC
fuente
8
Parece que la reciente cosecha de funciones hash no criptográficas de alta calidad, como xxhash, salió demasiado tarde, justo después de git.
Praxeolítico
3
@Praxeolitic de hecho. Se ha debatido sobre la sustitución de SHA1 con otro hash, pero simplemente requeriría bastante trabajo, por algo que, por ahora, funciona bien.
VonC
"sabemos que el hash está bien distribuido y no tenemos que preocuparnos por ciertos problemas de distribución", ¿por qué es un problema para scm?
Roded
@roded la tasa de colisión es lo suficientemente baja como para ser adecuada para un SCM donde los datos generalmente no son aleatorios sino archivos de prueba.
VonC
1
En realidad, hay una razón de seguridad para usar un hash criptográfico. Cuando un autor (por ejemplo, Linus) quiere cortar una versión (por ejemplo, Linux), la gente quiere saber que el código fuente que descargan coincide con lo que el autor pretendía incluir en la versión. Para este fin, se etiqueta el último hash de confirmación en la versión y se firma la etiqueta. Si la cadena de hash de confirmación que termina en la etiqueta no fuera criptográficamente segura, entonces la fuente podría ser manchada a algo diferente a lo que pretendía el autor.
Christopher King