Btrfs y colisiones de hash

A estas alturas habrán leído titulares en muchos sitios de Internet sobre un fallo de seguridad/ataque de denegación en Btrfs, provocando colisiones de hash desvelado por este blog. Como suele ocurrir con las cosas técnicas, la información ha oscilado entre la ausencia y la confusión, de ahí esta entrada.

La mayor confusión es que al mencionar la palabra "hash" junto con "btrfs", mucha gente ha asociado esto con la capacidad de Btrfs o ZFS de hacer checksums de todos los datos del disco, pero no tiene nada que ver. De lo que trata el ataque es del hash de los nombres de los archivos. Organizar el contenido de los directorios con un hash puede sorprender, pero es un método estándar utilizado por todos los sistemas de archivo modernos: Ext3/4, XFS, Reiserfs v3, JFS, ZFS, etc. Los checksums para asegurar la integridad del sistema de archivos son otro asunto.

Para calcular el hash de los nombres de archivo, Btrfs utiliza el algoritmo crc-32c. Como ha demostrado el artículo del blog citado anteriormente, se trata de un algoritmo débil frente a ataques de colisiones; es decir, es relativamente fácil generar a propósito un nombre de archivo cuyo hash crc32c sea idéntico al de otro con un nombre diferente. No pueden existir dos nombres con el mismo hash, por lo tanto se puede imposibilitar la creación de un archivo determinado creando otro que tenga el mismo hash.

El principal problema de Btrfs es que no se gestionan correctamente esas colisiones de hash. Una colisión por si misma no es ningún problema: se detecta fácilmente, se prohíbe la creación del archivo con hash duplicado, se devuelve error, y punto. No poder crear el archivo por la colisión es una molestia pero que se puede gestionar sin problemas, sin embargo, Btrfs parece entrar en un loop infinito para el proceso que encuentra la colisión, y eso es un fallo. Sobre su solución, hace poco que Btrfs ha añadido verdadera gestión de errores (Linux 3.4), y parece que había algunos parches en SuSE relacionados con ello que solucionan el problema de la colisión que aun no están en mainline - o quizás algunos fallos que hacen que el sistema de archivos se remonte en modo de solo lectura (el asunto no está del todo claro aun). En breve se enviarán los parches para 3.8 y para -stable, y Btrfs gestionará el problema normalmente, sin entrar en loops infinitos ni sufrir errores extraños. Hasta aquí el problema en la gestión de colisiones.

El otro asunto es la discusión sobre si el algoritmo de hash utilizado por Btrfs es demasiado débil. Este asunto es un poco más sutil. Lo cierto es que, aunque es cierto que el algoritmo es débil frente a colisiones, no es nada nuevo. El autor de Btrfs ya ha dicho que nunca esperó que crc-32c fuese capaz de resistir ataques colisiones. Seguramente tampoco resistan los de reiserfs, ni Ext4, ni XFS, si se intenta. Incluso ZFS usa CRC-64, que es más fuerte, pero no inquebrantable.

Lo cierto es que los algoritmos de hash utilizados habitualmente para ordenar directorios no se escogen pensando en resistir ataques extremos - de ser así, de entrada no usarían algoritmos como CRC. Esos algoritmos no se escogen pensando en resistir pruebas extremas de seguridad sino más bien en evitar coincidencias casuales y asegurar la integridad de datos (por ejemplo, en archivos comprimidos). Al fin y al cabo, se asume que si alguien permite a cualquier persona crear archivos en un directorio de su propiedad, es su problema (podrían hacerse otra clase de ataques DoS, como simplemente crear el máximo número de archivos posible que permita el sistema de archivos en un directorio).

Además, en los sistemas de archivo se tiene muy en cuenta que el algoritmo sea de cálculo sencillo, para afectar lo menos posible al rendimiento. Una de las razones por las que Btrfs utiliza crc-32c es que las CPUs Intel modernas con soporte SSE4.2 tienen una instrucción crc32c que permite usar ese algoritmo prácticamente "gratis". No parece que el autor de Btrfs tenga intención de cambiar el algoritmo por defecto (aunque quizás acepte otros alternativos para quienes quieran usarlos), simplemente solucionará el problema de gestión correcta de colisiones. Aun así, Btrfs un tiene espacio de 64 bits para almacenar el hash de los elementos de un directorio, por lo que añadir soporte para otro (u otros cuantos) algoritmos no sería especialmente difícil.