Un bug de alias en Circom (o en cualquier lenguaje de circuitos ZK) ocurre cuando un arreglo binario de señales codifica un número mayor al que puede almacenar el elemento del campo. En este artículo, nos referiremos a las señales y a los elementos del campo indistintamente. Nos referimos a la característica del campo como p. En términos generales, p es el valor en el que la señal se “desborda”. Es el valor del módulo implícito en todas las operaciones aritméticas.

Por defecto, Circom establece que p sea 21888242871839275222246405745257275088548364400416034343698204186575808495617, el cual requiere 254 bits para almacenarse. Sin embargo, $2^{254} - 1 (\sim2.89\times10^{76})$ es mayor que el valor predeterminado de p ($\sim2.18\times10^{76}$). Es decir, 254 bits pueden codificar números más grandes de los que las señales de Circom pueden almacenar.

A continuación, graficamos la recta numérica mostrando estos valores, aproximadamente a escala:

De 0 a $p - 1$ (el segmento de línea verde) es el intervalo que un elemento del campo de Circom puede almacenar, y de p a $2^{254} - 1$ (el segmento rojo) son los valores que un valor binario de 254 bits puede almacenar, pero un elemento del campo no.

La “zona de peligro” son los valores binarios de 254 bits mayores que p - 1. Estos son los números en el intervalo $[p, 2^{254} − 1]$. En el caso (predeterminado) de Circom, el rango $[p, 2^{254} − 1]$ es

[21888242871839275222246405745257275088548364400416034343698204186575808495617, 28948022309329048855892746252171976963317496166410141009864396001978282409983]

Para tener una idea de la escala, si dividimos $p / 2^{254}$ obtenemos 0.7561, lo que significa que p puede almacenar aproximadamente 3/4 partes de los números representables por un número de 254 bits.

Las restricciones de la representación binaria fallan silenciosamente cuando se desbordan

Para restringir que un número binario $b₀, b₁, ..., bₙ$ sea igual a un elemento del campo v, escribimos el siguiente circuito aritmético:

y también restringimos que cada $bᵢ$ sea $0$ o $1$.

Sin embargo, el cálculo $v = b_0 + 2 * b_1 + … + n * b_n$ se realiza módulo p. Por lo tanto, si el cálculo $b_0 + 2b_1 + … + nb_n$ desborda p, entonces podríamos presentar un número binario $b_0, b_1, ..., b_n$ cuyo valor no es v y crear una prueba falsa. Por ejemplo, si nuestro módulo es 11, entonces 2 y 13 son “iguales” entre sí porque 13 mod 11 es 2.

Pequeño ejemplo

Supongamos que $p = 11$ y estamos utilizando cuatro bits para representar un elemento del campo. Los bits pueden codificar números de hasta 15. Si codificamos 12 en binario como (1100), esto se evaluará como 12 módulo 11 = 1. Por lo que podemos afirmar que 1100 es la representación binaria de 1.

Específicamente:

$8(1) + 4(1) + 2(0) + (0) == 1 (\mod 11 )$

Demostración en Python

Para ver los valores que está usando el atacante, a continuación recreamos en Python la restricción utilizada por Bits2Num y Num2Bits de Circomlib para que los valores puedan imprimirse fácilmente:

Copy
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

# replicates the constraints Num2Bits and Bits2Num use
def constrain_modulo_p(bits, num, p):
    multiplier = 1
    acc = 0
    for i in range(len(bits)):
        assert bits[i] == 0 or bits[i] == 1
        acc = (acc + multiplier * bits[i]) % p
        multiplier = (multiplier * 2) % p

    # binary conversion must be correct
    assert num == acc

# this cannot be done in Circom because `value` needs to be higher than p
# but less than 2^254 - 1
def malicious_witness_generator(nbits, value):
    bits = []
    for i in range(nbits):
        bit = value >> i & 1

        bits.append(bit)

    return bits

# "normal" case -- constraints pass
constrain_modulo_p([1,1], 3, p)

# adversary case -- constraints pass, but the binary number is not 3
adversary_bits = malicious_witness_generator(254, 3 + p)
print(adversary_bits)

# no asserts are triggered although adversary_bits ≠ 3
constrain_modulo_p(adversary_bits, 3, p)

Lo importante aquí es que constrain_modulo_p acepta dos representaciones binarias para 3: la representación binaria “correcta” para 3 (11), y su alias $3 + p$, el cual es codificable como un número de 254 bits.

Prevención de bugs con AliasCheck, Num2Bits_strict y Bits2Num_strict

Las versiones “estrictas” de las plantillas de conversión de bits en la biblioteca bitify de Circomlib evitan el bug de alias pasando el arreglo binario a la plantilla AliasCheck.

La plantilla AliasCheck toma un arreglo binario y verifica que el valor codificado sea menor que el valor máximo que puede almacenar el elemento del campo.

Copy
pragma circom 2.0.0;

include "compconstant.circom";

template AliasCheck() {

    signal input in[254];

    component compConstant = CompConstant(-1);

    for (var i=0; i<254; i++) in[i] ==> compConstant.in[i];
    // compConstant returns 1 if the binary
    // input is greater than the supplied constant
    compConstant.out === 0;
}

AliasCheck utiliza -1 para referirse a p - 1. compConstant toma una entrada binaria (que podría codificar un valor mayor al que puede almacenar el elemento del campo) y devuelve 0 si es menor o igual a cierto umbral, y 1 si el valor binario es mayor que el umbral.

Al restringir que la salida de compConstant sea 0, y estableciendo la constante de comparación en -1, AliasCheck rechaza los números binarios que son mayores a p.

Si el arreglo binario contiene menos bits de los que el campo puede codificar, no hay peligro de bugs de alias

Aplicar Num2Bits a un elemento del campo también aplica una comprobación de rango en ese número para que sea menor que $2^n$, donde n es el número de bits. Por ejemplo, si n = 4 y p es el valor predeterminado, y configuramos la señal de entrada para que sea 17, el resultado no se desbordará silenciosamente hacia el binario 1 (0001): el circuito no se satisfará.

Es por esto que Num2Bits_strict y Bits2Num_strict en Circomlib tienen el número de bits codificado de forma fija a 254; este es el valor en el que pueden aparecer los alias.

Esta es también la razón por la que la plantilla LessThan no permite al desarrollador construir un comparador con más de 252 bits. Esto evita un riesgo innecesario (footgun) con el bug de alias.

Copy
template LessThan(n) {
    assert(n <= 252);
    signal input in[2];
    signal output out;

    component n2b = Num2Bits(n+1);

    n2b.in <== in[0] + (1<<n) - in[1];

    out <== 1-n2b.out[n];
}

Si cambias el p predeterminado en el compilador de Circom (la opción -p), asegúrate de verificar que Num2Bits_strict, Bits2Num_strict, AliasCheck, y CompConstant todavía te protejan de los bugs de alias porque están programados para usar 254 bits.

Reto: Encuentra el bug

Aquí hay un CTF que publicamos en X (anteriormente Twitter) que contiene el bug descrito en este artículo:

Copy
pragma circom 2.1.8;

include ".node_modules/circomlib/circuits/comparators.circom";
include ".node_modules/circomlib/circuits/poseidon.circom";

template UnsafePoseidon(n) {
    signal input in;
    signal output out;

    component n2b = Num2Bits(n);
    component b2n = Bits2Num(n);
    component phash = Poseidon(1);

    n2b.in <== in;
    for (var i = 0; i < n; i++) {
        b2n.in[i] <== n2b.out[i];
    }

    phash.inputs[0] <== b2n.out;
    phash.out ==> out;
}

component main = UnsafePoseidon(254);

El problema con el código anterior es que hay múltiples testigos (witnesses) que conducen al mismo hash, debido a que permitir 254 bits lleva a un desbordamiento.

Recuerda, la entrada a un circuito aritmético no son solo las señales etiquetadas como input, sino cada señal en el circuito. Circom nos proporciona un lenguaje de programación similar a C muy útil para “completar” algunas de las señales basándose en los valores proporcionados en las señales de input, pero el código no forma parte del sistema final de restricciones.

En el código anterior, el arreglo binario de 254 bits se mantiene en las señales de salida de Num2Bits y en las señales de entrada de Bits2Num.

Para inyectar los valores incorrectos en las señales utilizadas para codificar el arreglo binario, necesitamos usar la técnica descrita en nuestro tutorial sobre cómo hackear circuitos Circom sub-restringidos (underconstrained). Para generar una prueba de concepto para el código anterior, seguimos estos pasos:

1. Generar un hash usando un número u que sea lo suficientemente pequeño como para tener un alias en el rango, es decir, $[p, 2^{254} − 1]$.
2. Generar un testigo malicioso usando el mismo número aplicado a la señal input in pero reasignando el arreglo binario para que contenga el valor u + p.
3. El hash generado por ambas asignaciones de señales será el mismo, pero el testigo es diferente.

En resumen, el código del reto es vulnerable a un ataque de segunda preimagen a través de un bug de alias.

Publicado originalmente el 13 de julio