¿Qué algoritmo de suma de comprobación debería usar?

Question

Estoy construyendo un sistema que debe ser capaz de encontrar si se han actualizado los blobs de bytes. En lugar de almacenar todo el blob (pueden tener hasta 5MB), creo que debería calcular una suma de comprobación, almacenar esto y calcular la misma suma de comprobación un poco más tarde, para ver si el blog se ha actualizado.

El objetivo es reducir al mínimo la siguiente (en ese orden):

• tamaño de la suma de comprobación
• tiempo para calcular
• verosimilitud de colisiones (2 sumas de comprobación idénticos que suceden incluso si el contenido ha sido modificado).

Es aceptable que nuestro sistema tenga una colisión de no más de 1/1,000,000. La preocupación no es la seguridad, sino simplemente la detección de actualización/error, por lo que las colisiones raras están bien. (Por eso lo puse último en las cosas para minimizar).

Además, no podemos modificar los blobs de texto nosotros mismos.

Por supuesto, me vienen a la mente md5, crc o sha1, y si quisiera una solución rápida, lo conseguiría. Sin embargo, más que una solución rápida, estoy buscando lo que podría ser una comparación de diferentes métodos, así como los pros y los contras.

Answer 1

Le sugiero que eche un vistazo a this SO page, CRC vs MD5/SHA1.
La velocidad y las colisiones se discuten en this other thread.
Y como siempre Wikipedia es tu amigo.

Si tuviera que elegir, hay una pregunta importante para responder: ¿quiere que en cualquier caso no haya colisión? O, al menos, que la probabilidad sea tan baja que esté cerca de la posibilidad de que el La luna colisiona con la Tierra en los próximos 5 minutos?

En caso afirmativo, elija la familia SHA.
En su caso, cambiaría la forma en que se realiza la verificación de actualización .
Por ejemplo, un número incremental podría asociarse con el blob, y enviarse en lugar del hash, la solicitud para la actualización sería necesaria si el número es diferente en el otro lado. La probabilidad de colisión, en este caso va de ~ 10 ~^-18 a 0 (0 + básicamente fallo probabilidad) ...

Editar siguientes comentarios

Encontramos este algoritmo, Alder-32, que es bueno para mensajes largos (MB) con un CRC de 32 bits, es decir, aproximadamente ~ 1/10^9 (MD5 tiene 128 bits de longitud).
Es rápido de calcular.
Adler-32. Hay algunos ejemplos (enlaces) en la parte inferior.

Answer 2

Blake2 es la función hash más rápido se puede utilizar y que se adopta principalmente:

BLAKE2 no sólo es más rápido que las otras funciones buenas de hash, es incluso más rápido que MD5 o SHA-1 Source

El ganador del concurso SHA-3 era el algoritmo de Keccak pero aún no tiene una implementación popular, no se adoptó por defecto en las distribuciones de GNU/Linux. En cambio, Blake2 que fue candidato al concurso SHA-3 es más rápido que Keccak y es parte de GNU coreutils. Entonces en su distribución GNU/Linux puede usar b2sum para usar el algoritmo de hash Blake2.