ZKHack challenge 1 “Let’s hash it out”.md

ZKHack challenge 1 "Let's hash it out"

BLS signatures

Creating a BLS signature comprises of two steps. For a particular user, given the secret key $x$ and a binary-represented message $M ∈ {0, 1}^∗$, and $G_1$ the subgroup of an elliptic curve with additional properties (see [1]):

1. compute $h ← H(M)$, where $h ∈ G_1$, and
2. $σ ← h^x$. The signature is $σ ∈ G_1$.

The computation of $h$ is called hashing to the curve.

The verification of the signature uses two other parameters of the signature scheme:

• $g_2$, a generator of another subgroup $G_2$
• $e$, a bilinear mapping $G_1 \times G_2 \mapsto G_\mathbb{T}$ and the public key of the signer, $u = g_2^x$ and checks that :

$$ e(H(m), u) = e(σ, g_2) $$

The bilinear map $e$ has the following property (see [3] §15.4):

$$ \text{for all } α, β ∈ \mathbb{Z}_q \text{ we have } e(g^α_0, g^β_2) = e(g_0, g_2)^{α·β} = e(g^β_0, g^α_2) $$

So the verification passes for a valid signature, since $e(H(m), u) = e(H(m), g_2^x) = e(H(m)^x, g_2) = e(σ, g_2)$

Aggregates seen through a bilinear pairing

Let's say we have 256 signatures $\sigma_1,\ldots,\sigma_{256}$ on messages $M_1,\ldots,M_{256}$, by the same signer with public key $u$. What can we say about a linear combination of the messages and signatures?

To define that combination, we fix $c_1,\ldots, c_{256} \in \mathbb{Z}_q$ scalars. Then letting $i$ range from 1 to 256:

$$ e(\prod_i H(M_i)^{c_i}, u) = e(\prod_i (H(M_i)^x)^{c_i}, g_2) = e(\prod_i \sigma_i^{c_i}, g_2) $$

In other words, any linear combination of the initial 256 signatures will produce a valid signature for a particular message: the exact same linear combination of hashes of the original 256 messages $\prod_i H(M_i)^{c_i}$.

What does this mean for us?

We're required to produce a signature on our user name $M_u$. One way to forge a signature is to create a hash collision in the first step of the signature process, using another hash for which we already have a signature.

In our case, if we can create a collision between our Github username's hash and any linear combination of the hashes we have for $M_1,\ldots, M_{256}$, we now know how to exhibit a valid signature for it.

Windowed Pedersen collisions

The hash function used in the challenge uses a windowed Pedersen hash (see [4] for the scheme, [5] for general Pedersen commitemnts). What's interesting in this case is that it uses a window of size 1.

In concrete terms, our message $M\in {0, 1}^*$ is:

• first hashed to a 256-bit binary string $s$ using BLAKE2, a secure hash function,
• the overall hash function has a fixed 256 distinct points $P_1,\ldots P_{256}$ in $G_1$, and adds $P_i$ to the final hash if the corresponding bit of $s$ is set to $1$.

In other words if $\text{BLAKE2s}(M) = s_1| \ldots| s_{256}$, with $s_k \in {0, 1}$, then $H(M) = \prod_{j=1}^{256}P_j^{s_j}$.

While we have little hope of finding a BLAKE2 collision, there may be a way of finding a collision between the hash of $s_u$ -the BLAKE2 hash of our username— and a linear combination of the hashes used in the other signatures. More formally, if:

• our username is $M_{u}$ and $\text{BLAKE2}(M_{u}) = s_{u,1}| \ldots | s_{u,256}$, and
• similarly for $M_1, \ldots M_{256}$, we have $\text{BLAKE2}(M_i) = s_{i, 1} | \ldots |s_{i, 256}$

We are looking for linear coefficients $c_1, \ldots, c_{256}$ such that:

$$ \prod_i c_i \prod_{j=1}^{256} P_j^{s_{i, j}} = \prod_{j=1}^{256} P_j^{s_{u, j}} $$

If we let S be the matrix which $i$-th column vector is

$$ s_i = \begin{bmatrix} s_{i,1} \\ \vdots \\ s_{i, 256} \end{bmatrix} $$

and if we set

$$ s_u = \begin{bmatrix} s_{u,1} \\ \vdots \\ s_{u, 256} \end{bmatrix} $$

then we are looking for a solution to the linear system:

$$ S \begin{bmatrix} c_{1} \\ \vdots \\ c_{256} \end{bmatrix} = s_u $$

Gaussian elimination

The algorithm for finding a solution to this linear system is precisely Gaussian elimination in the field $\mathbb{Z}_q$ of scalars for the BLS 12-381 curve. We will replace the "usual" division by a chosen pivot coefficient (when operating on real numbers) by a multiplication by the equivalent field inverse.

Once we solve for $c_1, \ldots, c_{256}$, we can perform a sanity-check and make the collision we have found precise, by verifying that the following equation holds:

$$ \prod c_i H(M_i) = H(M_u) $$

Finally, we compute and submit the signature $\prod c_i \sigma_i$, which is a valid signature for the message $M_u$ under public key $u$.