El ataque de segunda preimagen en los árboles de Merkle puede ocurrir cuando un nodo intermedio en un árbol de Merkle se presenta como una hoja.
El nombre de este ataque es bastante engañoso porque implica que los hashes tienen una segunda preimagen. Las funciones hash modernas no tienen múltiples preimágenes (computables).
Un mejor nombre para este ataque sería “ataque de nodo como hoja” o “ataque de prueba acortada”.
Requisitos previos
Asumimos que el lector está familiarizado con los árboles de Merkle y las pruebas de Merkle.
Notación
Nos referimos a h(x) como el hash de x. h(x + y) es el hash de la concatenación de x e y. En este artículo, nos centraremos en keccak256 como nuestra función hash; elegir una función específica ayudará a que parte del razonamiento sea más claro más adelante en el artículo. Sin embargo, ten en cuenta que las ideas de este artículo se aplicarán a cualquier función hash. Nos referimos a las hojas de un árbol de Merkle con ℓ. La i-ésima hoja se denomina ℓᵢ.
Un ejemplo de ataque
Supongamos que deseamos crear una prueba para la hoja 2 (ℓ₂) en el árbol a continuación. La hoja será ℓ₂, y la prueba será \[h(ℓ₁), h(b), h(f)\]. Los valores a, b, c, …, g son la concatenación de los valores hijos. Aceptamos la prueba si h(g) es igual a la raíz de Merkle.
La prueba será \[h(ℓ₁), h(b), h(f)\] que están marcados en verde. La prueba hacia la raíz es
h(a) = h(h(ℓ₁) + h(ℓ₂))
h(e) = h(h(a) + h(b))
h(g) = h(h(e) + h(f))
return root == h(g)
El ataque de segunda preimagen
¿Qué pasa si el atacante proporciona a como una hoja y \[h(b), h(f)\] como la prueba?
El contrato verá a como una hoja, donde a = h(ℓ₁), h(ℓ₂)). Si la prueba es [h(b), h(f)], la prueba de Merkle se aceptará como válida.
Esencialmente, si una prueba de Merkle es válida, entonces una versión acortada de la misma también es válida si pasamos el primer valor en la prueba original como una hoja.
¡Por lo tanto, el atacante habrá proporcionado una “hoja” y una prueba que el contrato acepta, pero la “hoja” dada no es una hoja en el árbol de Merkle original!
Entonces, ¿cómo evitamos que esto ocurra?
La advertencia de OpenZeppelin
En la biblioteca de árboles de Merkle de OpenZeppelin, vemos la advertencia en los comentarios junto con algunas soluciones. Explicamos sus soluciones en las siguientes secciones.
Las siguientes dos secciones explican cómo estas dos soluciones previenen el problema.
El ataque requiere hojas de 64 bytes
Para que este ataque funcione, el atacante debe pasar la preimagen del nodo intermedio, no su valor hash. Esto significa que debe pasar a como la hoja, no hash(a). Dado que Solidity usa hashes de 32 bytes, a = h(ℓ₁) + h(ℓ₂) tendrá 64 bytes de longitud.
Si el contrato no acepta hojas de 64 bytes como entrada, entonces el ataque no funcionará.
Es decir, si la entrada de la hoja tiene una longitud diferente a 64 bytes, es imposible pasar h(ℓ₁) + h(ℓ₂) como un valor de hoja falso.
Usar un hash diferente para la hoja como defensa
Si nuestra aplicación necesita aceptar hojas de 64 bytes por alguna razón, entonces podemos prevenir el ataque usando un hash diferente para las hojas que para la prueba.
Es decir, cuando se aplica el hash a la hoja por primera vez, usamos un hash diferente del que usamos para aplicar el hash hacia la raíz. Esto evitará que el atacante “reconstruya” un nodo intermedio como si fuera una hoja. Utilizando el diagrama anterior, el atacante está usando h(a) para crear la “hoja” falsa. Sin embargo, si las hojas se pasan por h’(a), entonces el valor intermedio no puede ser reconstruido.
OpenZeppelin usa un hash doble como un “hash diferente”
En lugar de utilizar una función hash diferente (como mediante un precompile) lo cual costaría más gas, OpenZeppelin simplemente aplica el hash a la hoja dos veces. Es decir, h’(x) = h(h(x)).
Hemos utilizado subrayados verdes para mostrar dónde se toma el hash dos veces para construir el nodo de la hoja a partir de los datos subyacentes
Ten en cuenta que la biblioteca no te obliga a aplicar el hash dos veces; de hecho, ¡no te obliga a aplicar el hash a la hoja en absoluto! No aplicar un hash a la hoja puede abrir vectores de ataque más allá del ataque de segunda preimagen: consulta el problema de práctica al final.
Conclusión
El ataque de segunda preimagen funciona porque podemos proporcionar una versión acortada de una prueba válida y recrear la raíz de Merkle. Las raíces de Merkle sí tienen una preimagen; sin embargo, la raíz se crea en incrementos, no aplicando un hash a toda la prueba de una sola vez. Al comenzar la prueba en un punto posterior de la secuencia, podemos tener una entrada alternativa que genere la misma raíz.
Es fácil defenderse del ataque: simplemente no permitas que los valores que no son hojas se interpreten como hojas.
Problemas de práctica
El siguiente ejercicio de Capture the Flag usa las pruebas de Merkle de manera incorrecta y, por lo tanto, puede ser hackeado
RareSkills Riddles: Furry Fox Friends
Aprende más con RareSkills
Por favor, consulta nuestro blockchain bootcamp para ver nuestra oferta educativa.
Publicado originalmente el 24 de noviembre de 2023