¿Por qué usar MD4 para el almacenamiento en caché?

5

ccache es una herramienta popular para acelerar la recompilación con GCC y otros compiladores. Funciona almacenando en caché las compilaciones anteriores y detectando cuándo se vuelve a realizar la misma compilación. La detección se realiza mediante hashes MD4.

Tengo curiosidad por saber (a) por qué una herramienta de almacenamiento en caché de este tipo usaría cualquier función hash criptográfica , y (b) de todas las funciones de hash criptográficas disponibles, por qué se usaría MD4 en particular.

Con respecto a (a), ¿cuál es el beneficio de usar una función criptográfica de hash, en lugar de alguna función de hash no diseñada teniendo en cuenta la criptografía? Por ejemplo, funciones hash integradas de Java no parecen corresponder a los conocidos utilizados (o anteriormente utilizados) en la criptografía. ¿Por qué no usar una de estas funciones hash no criptográficas en su lugar? Dadas las debilidades conocidas de MD4, no puedo imaginar que sea elegido por un deseo de mayor seguridad.

Con respecto a (b), suponiendo que haya alguna base para usar un hash criptográfico, ¿por qué MD4 en particular? Entiendo que no tendría sentido utilizar una función criptográfica moderna de hash, ya que generalmente son computacionalmente intensivas, lo que anula el propósito de una herramienta de almacenamiento en caché de acelerar los tiempos de acceso. Por lo tanto, MD4 debe usarse al menos en parte para la velocidad. Pero, ¿es absolutamente la función criptográfica hash más rápida , o hay otras que son más rápidas? Si no es el más rápido, ¿qué otras ventajas tendría MD4 (sobre, por ejemplo, MD5) para usar en el almacenamiento en caché?

    
pregunta Psychonaut 26.02.2016 - 11:45
fuente

2 respuestas

3

Los hashes no criptográficos habituales como CRC-32 son estadísticamente buenos, pero aquí lo que el caché quiere evitar es falsos positivos : recompilaciones que se declaran idénticas a las anteriores, pero no lo son. . Un hash no criptográfico habitual que produce solo 32 bits tiene un riesgo demasiado alto de falsos positivos, simplemente por su tamaño de salida y sin importar sus cualidades estadísticas. Un hash criptográfico tiene un resultado mucho mayor, lo que hace que los riesgos de falsos positivos sean insignificantes.

Esta no es una pregunta de seguridad : todas las entradas son del usuario, por lo que si el usuario realiza una colisión a propósito, solo está luchando contra sí mismo. Por lo tanto, se puede utilizar una función hash criptográfica rota.

Ahora, para la elección específica de MD4 sobre una función más común (como MD5 o SHA-1), solo se puede especular, pero supongo que se trata del rendimiento; después de todo, ccache se trata de hacer las compilaciones más rápido. MD4 es increíblemente rápido (incluso más rápido que el CRC-32 en algunas plataformas). Por supuesto, el hash es más rápido que cualquier proceso de compilación o incluso simplemente leyendo , por lo que es probable que el uso de MD5 en lugar de MD4 no haga una diferencia significativa en el rendimiento general de ccache. Muchas de las decisiones relacionadas con el desempeño se toman en la práctica en una corazonada, sin molestarse en tomar medidas reales para ver si hay un problema de desempeño que deba resolverse.

Desde el trabajo en esta biblioteca , hay muy pocas funciones de hash criptográficas que son al menos tan rápidas como MD4. BLAKE2 , un derivado reciente del candidato de BLAKE SHA-3, puede ser su mejor apuesta para una función hash criptográfica segura que se acerca a los niveles de rendimiento de MD4. Pero, como escribí anteriormente, es muy probable que el rendimiento no sea un problema real en el caso de ccache.

    
respondido por el Tom Leek 26.02.2016 - 21:25
fuente
9

Las funciones hash criptográficas generalmente tienen la propiedad de que las entradas ligeramente diferentes generan salidas muy diferentes. Cualquier colisión debería generalmente tiene una entrada muy diferente.

Esta propiedad no se aplica a la mayoría de las sumas de comprobación no criptográficas. Los cambios pequeños pueden dar como resultado sumas de comprobación similares, y en algunos casos de esquina, algunos cambios pequeños pueden cancelarse mutuamente de manera que se genere la misma suma de comprobación.

Los cambios en el código fuente a menudo son bastante pequeños, por lo que en el contexto de la verificación de los cambios en el código fuente, el riesgo de colisiones es bastante alto con sumas de comprobación no criptográficas. La herramienta de control de versiones git, por ejemplo, utiliza hashes SHA-1 como identificador único para las revisiones de código.

¿Por qué MD4 en particular? Bueno, tienes que preguntarle a los desarrolladores de ccache acerca de esto. Es una herramienta bastante antigua, y el MD5 no se estandarizó hasta 1992. Es posible que el MD4 fuera simplemente la opción más obvia que estaba disponible en el momento en que se desarrolló esta característica, y más adelante nadie sintió la necesidad de reemplazar el algoritmo. , porque hizo lo que se suponía que debía hacer.

    
respondido por el Philipp 26.02.2016 - 13:32
fuente

Lea otras preguntas en las etiquetas