Las sumas de verificación no son hashes: CRC-32, Adler-32 y para qué sirven

Tres trabajos que producen todos un número corto

La confusión empieza con la salida. CRC-32, Adler-32, FNV-1a, MurmurHash3, MD5 y SHA-256 toman bytes cualesquiera y devuelven un número de tamaño fijo, así que en una API parecen intercambiables. No lo son. Se diseñaron contra tres modelos de amenaza completamente distintos, y elegir la familia equivocada produce fallos silenciosos hasta que son catastróficos.

Una suma de verificación responde: ¿cambiaron estos datos por accidente de camino aquí? Su adversario es un rayo cósmico, un cable al límite, una escritura truncada, un sector de disco que flaquea. Ese adversario es aleatorio y no se adapta. CRC-32 y Adler-32 son sumas de verificación. Un hash criptográfico responde a una pregunta más dura: ¿puede alguien, con todo el tiempo y el hardware que pueda comprar, encontrar una segunda entrada con la misma salida? Su adversario es una persona con presupuesto. MD5, SHA-1 y SHA-256 son intentos de esto — con éxito variable, que detalla el artículo compañero sobre la elección de hash.

El tercer trabajo es el que se olvida. Un hash de tabla responde: ¿cómo convierto esta clave en un índice de cubo, rápido y de forma uniforme? Su adversario es nominalmente nadie — hasta que las claves vienen de parámetros de peticiones HTTP, momento en que el adversario es quien las envía. FNV-1a y MurmurHash3 viven aquí. Son excelentes en su trabajo y no ofrecen ninguna protección en los otros dos.

CRC-32 es lineal, y aquí está la colisión

CRC-32 es división polinómica sobre GF(2), y la división es lineal. En concreto, para tres mensajes cualesquiera de igual longitud, crc(a XOR b XOR c) es igual a crc(a) XOR crc(b) XOR crc(c). Probado sobre cinco tripletas aleatorias de 32 bytes, la igualdad fue exacta cada vez — una tripleta dio, por ejemplo, 8975e151 en ambos lados. Ningún hash criptográfico tiene una identidad así, y ese único hecho algebraico es toda la diferencia entre las dos familias.

La linealidad permite resolver una colisión en vez de buscarla. Toma un mensaje que un atacante quiera alterar, dale unos bytes de holgura en cualquier sitio — relleno, un campo de comentario, una cabecera reservada, espacios finales — y el valor de holgura necesario es la solución de un sistema lineal de 32 incógnitas sobre GF(2). La eliminación gaussiana lo resuelve en microsegundos.

Hecho de verdad: el mensaje original era «config: mode=safe, retries=3, pad=......», con CRC-32 78aa94ad. La falsificación debía leerse «config: mode=open, retries=9, pad=» seguido de seis bytes de relleno por determinar. Resolver esos bytes dio «config: mode=open, retries=9, pad=!9[noI» — misma longitud de 40 bytes, 11 bytes distintos, y el CRC-32 idéntico 78aa94ad. Se probaron veinticinco rellenos candidatos antes de obtener uno completamente imprimible; todo el programa corrió en 0,11 segundos. Los resúmenes SHA-256 de ambos mensajes empiezan por d9cddeec y 6b7bdc0c, que es el aspecto de una función sin identidad de linealidad.

Nada de esto exigió criptoanálisis, GPU ni diccionario. Exigió saber que CRC-32 es una aplicación lineal y disponer de seis bytes del mensaje. Por eso un CRC que acompaña a un archivo por un canal no fiable no prueba nada contra la manipulación: un atacante que pueda cambiar el archivo puede cambiar el CRC para que cuadre, y aunque el CRC llegue por separado y sea intocable, todavía puede fabricar otro archivo que lo produzca.

En qué es CRC-32 realmente excelente

Nada de lo anterior hace de CRC-32 una mala función. Lo convierte en una función que hace otro trabajo, y en ese trabajo es casi óptima. Sus garantías no son estadísticas, están demostradas: detecta todo error de un bit, todo error de dos bits dentro de una longitud de mensaje enorme, todo error que afecte a un número impar de bits y todo error de ráfaga de hasta 32 bits — la longitud de la propia suma.

Medido y no afirmado: en un mensaje de 200 bytes, los 1 600 cambios posibles de un bit alteraron el CRC, y los 1 279 200 cambios posibles de dos bits también lo alteraron — no escapó ninguno. En una trama de 1500 bytes de tamaño Ethernet, 200 000 errores de ráfaga aleatorios en cada uno de seis anchos (8, 16, 32, 33, 40 y 64 bits) fueron todos detectados. Las ráfagas de más de 32 bits no están garantizadas, solo son abrumadoramente probables: la probabilidad de escape es de unos 2 elevado a menos 32, una entre 4290 millones, por eso 200 000 pruebas no encontraron nada.

Por eso CRC-32 está en las tramas Ethernet, en los finales de fichero gzip, en los bloques PNG, en las entradas ZIP y en SATA. Todos son canales cuyo modo de fallo es un defecto físico que produce una racha contigua de bits corruptos — justo la clase de errores que los polinomios CRC se construyen para cazar con certeza. Un hash criptográfico también los cazaría, pero a varias veces el coste y sin garantía demostrada, solo probabilística.

Adler-32: más barato de calcular, más débil detectando

Adler-32, definido en la RFC 1950 para el formato zlib, son dos sumas corrientes módulo 65 521: una suma simple de los bytes y una suma de esas sumas parciales. Se diseñó para ser mucho más barato que un CRC detectando la mayoría de los mismos errores — sin tabla, solo sumas. En la práctica el módulo cuesta lo bastante como para que la ventaja prometida se evapore a menudo: medido en el mismo motor JavaScript sobre el mismo búfer de 64 MB, Adler-32 corrió a 174 MB/s frente a los 262 MB/s de CRC-32. Adler-32 fue más lento.

También tiene un punto ciego que se demuestra en vez de estimarse. El módulo 65 521 es el mayor primo por debajo de 65 536. Si aumentas un byte en d y disminuyes otro byte en d, la primera suma no cambia, y la segunda cambia en d por la distancia entre ambos — lo que se anula módulo 65 521 exactamente cuando esa distancia es 65 521. Así que todo mensaje de más de unos 64 kilobytes tiene pares de cambios compensatorios que Adler-32 no puede ver en absoluto.

Demostrado sobre un búfer de 70 000 bytes: subir el byte 100 en 7 y bajar el byte 65 621 en 7 dejó Adler-32 en 3fee717c, idéntico byte a byte al valor limpio, mientras CRC-32 pasaba de abc586b8 a 43c209f4. Adler-32 también es pobre en entradas cortas — 200 000 entradas aleatorias de cuatro bytes produjeron solo 152 364 valores Adler-32 distintos, donde una función de 32 bits ideal habría producido unos 199 995. La propia RFC 1950 señala la debilidad para mensajes cortos, por lo que los flujos zlib lo aplican a flujos enteros y no a registros diminutos.

FNV-1a y MurmurHash3: la tercera categoría

FNV-1a y MurmurHash3 no son ni sumas de verificación ni hashes criptográficos. Son hashes no criptográficos diseñados para tablas hash, filtros de Bloom y particionado, donde el requisito es distribución uniforme al menor coste posible por byte. Cumplen. En el mismo motor y sobre el mismo búfer, MurmurHash3 corrió a 730 MB/s y FNV-1a a 520 MB/s, frente a los 262 MB/s de CRC-32.

Las colisiones son triviales de encontrar y el ejercicio lleva menos de dos segundos. Enumerando cadenas de siete caracteres, FNV-1a 32 colisionó en «7yzlaaa» y «e6apaaa», ambas con hash 15111984, tras 700 997 candidatos y 680 milisegundos. MurmurHash3 con semilla 0 colisionó en «rynbaaa» y «ciaabaa», ambas en e5407f96, tras 1 679 907 candidatos y 1,6 segundos. Es lo esperado — 32 bits significan colisión de cumpleaños hacia los 77 163 elementos — y no es un defecto. Se convierte en defecto cuando alguien elige las claves.

La inundación de hash es el ataque resultante, y es fácil de reproducir. Recolectar 20 000 claves cuyo valor FNV-1a cae en el cubo 0 de una tabla de 4 096 cubos costó una fracción de segundo de división de prueba. Insertarlas colapsó la tabla en una única cadena de 20 000 entradas, donde las claves ordinarias daban una cadena máxima de 12. Veinte mil búsquedas pasaron entonces a tardar 1 397,9 milisegundos en vez de 11,5 — una ralentización de 121 veces, de tiempo constante a lineal. Cada petición que toque esa tabla se convierte en un amplificador: es justo la clase de denegación de servicio que empujó a los motores de lenguaje hacia un SipHash con semilla aleatoria para sus diccionarios integrados.

Elegir, en una pregunta

Pregunta a quién beneficia que dos entradas distintas produzcan el mismo valor. Si la respuesta es a nadie — estás cazando copias truncadas, cables inestables, archivos corruptos, podredumbre de bits en un disco de respaldo — una suma de verificación es lo correcto y CRC-32 es el valor por defecto sensato. Es pequeña, está en todas partes, tiene garantías demostradas contra justo las formas de error que produce el hardware, y las implementaciones nativas son rapidísimas: el CRC-32 de zlib en node alcanzó 2 248 MB/s en el mismo búfer, tres veces los 763 MB/s de SHA-256.

Si la respuesta es alguien — una descarga por una red que no controlas, una firma, un archivo de licencia, una carga de actualización, deduplicación de objetos suministrados por usuarios, una caché indexada por algo que un usuario pueda influir — necesitas un hash criptográfico, y hoy eso significa SHA-256. El coste es real pero pequeño: 763 MB/s sigue siendo más rápido que la mayoría de discos y redes, y es la única familia de esta comparación en la que una segunda entrada con la misma salida no es algo que cualquiera pueda simplemente resolver.

Y si el valor nunca sale de tu proceso — índice de cubo, filtro de Bloom, selector de partición — usa un hash de tabla, pero hazte una pregunta de seguimiento: ¿puede un atacante elegir las claves? Si puede, quieres una función con clave y semilla aleatoria como SipHash, no un FNV-1a de semilla fija. La mayoría de motores de lenguaje modernos ya lo hacen en sus mapas integrados; el peligro es una tabla hecha a mano en el código de aplicación que no lo hace.

Preguntas frecuentes

¿Es CRC-32 una función hash?

En el sentido más laxo sí — lleva una entrada cualquiera a una salida fija de 32 bits — pero llamarla así invita al error que este artículo existe para evitar. CRC-32 es una función lineal, calculada como el resto de una división polinómica sobre GF(2). Esa linealidad le da la identidad crc(a XOR b XOR c) = crc(a) XOR crc(b) XOR crc(c), verificada aquí en tripletas aleatorias, y de esa identidad se sigue una colisión resolviendo un sistema lineal de 32 incógnitas en vez de buscando. Un hash criptográfico se diseña específicamente para que no exista tal atajo algebraico; eso es lo que hace la palabra criptográfico. Así que CRC-32 es una suma de verificación, y el modelo mental útil es un muy buen código detector de errores más que un hash débil. Si una biblioteca, una API o una revisión de código lo llama hash, comprueba de qué propiedad se depende realmente: la unicidad frente a un adversario es la que no puede aportar, y es la que se da por supuesta.

¿Puedo usar un CRC-32 para verificar una descarga?

Depende por completo de contra qué verifiques. Si compruebas que los bytes que llegaron coinciden con los que salieron — que la conexión no se cortó a medias, que el archivo no está truncado, que el disco escribió lo que se le dio — un CRC-32 es exactamente la herramienta adecuada y cazará cualquier fallo de transporte realista. Por eso cada entrada ZIP y cada flujo gzip lleva uno. Si en cambio preguntas si el archivo es el que el editor pretendía, un CRC-32 no responde nada. Un atacante que pueda sustituir el archivo puede sustituir también el CRC, e incluso donde el CRC se publica aparte y es intocable, puede construir otro archivo que encaje — este artículo lo hizo en 0,11 segundos. Para verificar al editor necesitas un resumen criptográfico publicado por un canal que el atacante no controle, e idealmente una firma sobre ese resumen más que el resumen solo.

¿Por qué gzip usa CRC-32 y zlib usa Adler-32?

Ambos formatos envuelven los mismos datos comprimidos DEFLATE y difieren sobre todo en su contenedor. La RFC 1952 especifica un CRC-32 en el cierre de gzip; la RFC 1950 especifica un Adler-32 en el de zlib. El razonamiento de entonces era la velocidad: Adler-32 solo necesita sumas y un módulo, sin tabla de 256 entradas, así que en los procesadores de principios de los noventa era notablemente más barato por byte, y zlib apuntaba a contextos donde el coste de la suma importaba frente a la compresión. Esa ventaja se ha evaporado en gran medida. Las implementaciones modernas de CRC-32 usan tablas slicing-by-8 o instrucciones dedicadas, y en las medidas de aquí el CRC-32 nativo de node alcanzó 2 248 MB/s mientras un Adler-32 directo en el mismo motor JavaScript se quedó en 174 MB/s frente a los 262 MB/s de CRC-32. Los formatos siguen como están porque cambiar de algoritmo rompe a todos los lectores existentes, y ambos bastan para su misión de cazar corrupción accidental en un flujo comprimido.

¿Qué probabilidad hay de una colisión CRC-32 accidental?

Para un solo mensaje corrupto la respuesta es excelente: las ráfagas de hasta 32 bits nunca se pierden, y más allá la probabilidad de escape es de una entre 4 294 967 296. Para una colección de archivos es mucho peor de lo que sugiere la intuición, por el efecto cumpleaños. Dos valores aleatorios de 32 bits colisionan con probabilidad de una entre 4290 millones, pero un conjunto de n valores contiene n(n−1)/2 pares, así que el 50 % llega a los 77 163 elementos. Diez mil archivos ya llevan un 1,16 % de probabilidad de que algún par comparta CRC-32, y cien mil llevan un 68,8 %. Eso importa si usas CRC-32 como clave de deduplicación o identificador direccionado por contenido sobre un corpus grande, donde una colisión descarta en silencio uno de dos archivos distintos. Para una comprobación de integridad archivo a archivo contra daños de transporte el efecto cumpleaños es irrelevante, porque comparas un valor con un valor esperado, no buscas coincidencias en una población.

¿Son seguros FNV-1a y MurmurHash3 con claves suministradas por el usuario?

Sin semilla aleatoria, no. Ambos carecen de clave por defecto, así que su salida es una función pública que cualquiera puede calcular sin conexión. Eso permite a un atacante precalcular claves que caigan en el mismo cubo y enviarlas todas de golpe: eso es la inundación de hash. Reproducida aquí en una tabla de 4 096 cubos: 20 000 claves fabricadas hashearon todas al cubo 0, convirtiendo una cadena máxima de 12 en una única cadena de 20 000 y haciendo que 20 000 búsquedas tardaran 1 397,9 milisegundos en vez de 11,5 — 121 veces más lento, y recolectar esas claves llevó menos de un segundo de esfuerzo. El arreglo no es un hash sin clave más fuerte; es uno con clave y semilla aleatoria por proceso, que hace imposible el precálculo sin conexión. SipHash es la opción estándar y es lo que hoy usan por dentro la mayoría de los motores para sus diccionarios. Si tus claves vienen de la configuración, de tu propia base de datos o de algún sitio que un atacante no pueda influir, FNV-1a y MurmurHash3 sin semilla siguen siendo perfectos y muy rápidos.

¿Qué debo usar para claves de caché y deduplicación?

Decide según quién suministra el contenido y cuánto cuesta una respuesta equivocada. Para una caché en memoria cuyas claves generas tú — una forma de consulta, un nombre de plantilla renderizada, un identificador interno — un hash no criptográfico rápido es lo adecuado, y MurmurHash3 a 730 MB/s es buena elección. Para deduplicación sobre un corpus que controlas, donde una colisión significa quedarse en silencio con uno de dos objetos distintos, 32 bits es demasiado estrecho: el punto cumpleaños del 50 % llega a los 77 163 elementos. Pasa a un hash no criptográfico de 64 o 128 bits, o a un SHA-256 truncado. Para cualquier caso en que el usuario suministre el contenido — archivos subidos, objetos generados por usuarios, un almacén direccionado por contenido, una caché compartida entre varios inquilinos — usa SHA-256 completo. Ahí una colisión no es un accidente sino una capacidad: permite colocar un objeto elegido bajo un identificador ya existente, y solo un hash criptográfico lo hace inviable. El coste es modesto: los 763 MB/s medidos aquí superan a la capa de almacenamiento en la que escribes.