Skip to content

Instantly share code, notes, and snippets.

@StarLI-Trapdoor
Created October 31, 2021 14:15
Show Gist options
  • Save StarLI-Trapdoor/7d744018d0b7df6ed6dd3d89cde4625f to your computer and use it in GitHub Desktop.
Save StarLI-Trapdoor/7d744018d0b7df6ed6dd3d89cde4625f to your computer and use it in GitHub Desktop.
The write-up of Puzzle 1 - zkhack-bls-pedersen

From the source code, we can find the authentication system used by Alice is illustrated as:

  • Authentication Algorithm (assume the user's message is $m$)

    $${m_hash} = blake2s(m)$$

    $$m_{g1} = hash_to_curve(m_hash)$$

    $$pk = sk* g2$$

    $$ sig = sk*{m_{g1}}$$

  • Verification Algorithm

$$e(sig, g2) =?\ e(m_{g1}, pk)$$

What's $hash_to_curve$ function?

As defined in ZkHackPedersenWindow,

impl Window for ZkHackPedersenWindow {
    const WINDOW_SIZE: usize = 1;
    const NUM_WINDOWS: usize = 256;
}

One blake2s hash value (256bits) is seperated as 256 windows. That's to say, one window is with one bit. Through random generator, 256 G1 points are randomly selected. The $m_{g1}$ is the sum of those G1 points if the according bit is 1. Assume $g1_{0}, g1_{1}, g1_{2}, ..., g1_{255}$ are randomly selected G1 points, the $hash_to_curve$ can be represented as follows:

​ $$ hash_to_curve = \sum_{i=0}^{255} m_hash[i]*g1_i$$

Let's hash it out

Due to the addition homomorphic of points on elliptic curve, if more than 256 random hashes and according signatures are leaked, the signature of any hash can be "calculated" using the linear combination of leaked signatures. To find the linear combination coefficients ($c_0, c_1 ... c_{255}$), the following equation is used. Assume the leaked 256 hashes is $h_i \ i\in (0, 255)$ and the target hash is $h_t = blake2s(message)$.

$$ \begin{bmatrix} h_{0_0} & h_{1_0} &\cdots & h_{255_{0}} \ h_{0_1} & h_{1_1} &\cdots & h_{{255}{1}} \ \cdots &\cdots &\cdots&\cdots \ h{0_{255}} & h_{1_{255}} &\cdots & h_{{255}{255}}\ \end{bmatrix} \begin{bmatrix} c{0} \ c_{1} \ \vdots \ c_{255} \end{bmatrix} = \begin{bmatrix} h_{t_0} \ h_{t_1}\ \vdots \ h_{t_{255}} \end{bmatrix} $$

Once the coefficients are obtained, the signature of the specified hash can be got:

  • $$h_{g1} = \sum_{i=0}^{255} c_i * m_{g1_i}$$

  • $$h_{sig} = \sum_{i=0}^{255} c_i * sig_{i}$$

The $h_{sig}$ is exactly what we need.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment