Crypto Book (Work in Progress)

Gathering the Pieces

Recall that the BLS signature of message $m$ is the point on ${\mathbb{G}}_1$ defined as $S=xH(m),$ where $x\in {\mathbb{Z}}_r$ is the secret key. We also established in the previous section that $H(m)$ is given by $$H(m):=\sum _{j=0}^{255}{h}_j{B}_j$$ where the $h_j$'s are the bits of $blakes2s(m).$ Hence, the signature of $m$ can be expressed as $$S=xH(m)=\sum _{j=0}^{255}{h}_j(x{B}_j).$$ In other words, $S$ is a formal linear combination (with known coefficients) of secret points $(x{B}_0,\dots ,x{B}_{255}).$ As we are given 256 signatures, we should be able to forge a new signature with some linear algebra.

In the following, we let $m^{\ast }$ be the message for which we want to forge a signature, and ${\mathbf{h}}^{\ast }=(h_0^{\ast },\dots ,h_{255}^{\ast }):=blakes2s(m^{\ast })$ denote the output of the BLAKE2s hash function applied to $m^{\ast },$ seen as a vector of bits. Hence, the signature $S^{\ast }$ that we want to forge is $$S^{\ast }=xH(m^{\ast })=\sum _{j=0}^{255}{h}_j^{\ast }(x{B}_j).$$ Similarly, let $m_0,\dots ,m_{255}$ denote the 256 messages whose signature is given in the puzzle data and let ${\mathbf{h}}_i=(h_{i,j}{)}_{0\le j\le 255}:=blake2s(m_i)$ denote the hash of $m_i$ with BLAKE2s. Then the signature $S_i$ of message $m_i$ is $$S_i=\sum _{j=0}^{255}{h}_{i,j}(x{B}_j).$$

Assume that we can write ${\mathbf{h}}^{\ast }$ as a linear combination of vectors ${\mathbf{h}}_0,\dots ,{\mathbf{h}}_{255},$ i.e., we can find a vector $\mathbf{c}=(c_0,\dots ,c_{255})\in ({\mathbb{Z}}_r{)}^{256}$ such that $${\mathbf{h}}^{\ast }=\sum _{i=0}^{255}{c}_i{\mathbf{h}}_i.\text{\hspace{1em}(25.4.1)}$$ Then we can compute $S^{\ast }$ as $$\begin{array}{rl}\sum _{i=0}^{255}{c}_i{S}_i& =\sum _{i=0}^{255}\sum _{j=0}^{255}{c}_i{h}_{i,j}(x{B}_j)\\ & =\sum _{j=0}^{255}\underset{h_j^{\ast }}{\underbrace{\left(\sum _{i=0}^{255}{c}_i{h}_{i,j}\right)}}(x{B}_j)\\ & =S^{\ast }.\end{array}$$ How do we compute $\mathbf{c}$? Letting $\mathbf{M}$ denote the $256\times 256$ matrix whose rows are ${\mathbf{h}}_0,\dots ,{\mathbf{h}}_{255},$ then Eq. (25.4.1) is equivalent to $${\mathbf{h}}^{\ast }=\mathbf{c}\cdot \mathbf{M}.$$ Hence, we need to solve a linear system.

Implementing the Attack

To perform the linear algebra and compute $\mathbf{c},$ we will use Sage. For this, we first write $\mathbf{M}$ and ${\mathbf{h}}^{\ast }$ as arrays in a file sage/data.sage that we will load in Sage later on. Note that we must write the individual bits of the outputs of BLAKE2s. For this, we use the bytes_to_bits function from the pedersen module which returns a vector of booleans. Trying to write this vector yields an array of true and false strings which is not what we want, so we first need to convert these booleans into bytes.

use bls_pedersen::bls::verify;
use bls_pedersen::data::puzzle_data;
use bls_pedersen::PUZZLE_DESCRIPTION;
use prompt::{puzzle, welcome};

// additional items brought into scope for puzzle solving
use bls_pedersen::hash::hash_to_curve;
use ark_crypto_primitives::crh::pedersen::bytes_to_bits;
use ark_ff::{PrimeField, Zero};
use ark_ec::{AffineCurve, ProjectiveCurve, msm::VariableBaseMSM};
use ark_bls12_381::{Fr, G1Affine, G1Projective};
use std::fs;
use std::fs::File;
use std::io::Write;

fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);
    let (pk, ms, sigs) = puzzle_data();
    for (m, sig) in ms.iter().zip(sigs.iter()) {
        verify(pk, m, *sig);
    }

    // --snip--

    let m = b"your_username";

    let mut data_file = File::create("sage/data.sage").unwrap();

    // write matrix M to be passed to SAGE
    data_file.write_all("M = [".as_bytes()).unwrap();
    for m in ms {
        let (hash, _) = hash_to_curve(&m);
        let bits = bytes_to_bits(&hash);
        let bits: Vec<u8> = bits.into_iter().map(|x| x as u8).collect();
        let line = format!("{:?}, ", bits);
        data_file.write_all(line.as_bytes()).unwrap();
    }
    data_file.write_all("]\n".as_bytes()).unwrap();

    // write vector h to be passed to SAGE
    data_file.write_all("h = ".as_bytes()).unwrap();
    let (hash, _) = hash_to_curve(m);
    let bits = bytes_to_bits(&hash);
    let bits: Vec<u8> = bits.into_iter().map(|x| x as u8).collect();
    let line = format!("{:?}", bits);
    data_file.write_all(line.as_bytes()).unwrap();

    // --snip--

    // read solution in coeffs.txt and cast these strings (one per line) into scalar field Fr elements
    let mut coeffs = Vec::new();
    for line in fs::read_to_string("sage/coeffs.txt").unwrap().lines() {
        // let c = Fr::from_le_bytes_mod_order(line.as_bytes()); // doesn't work
        let c: Fr = line.parse().unwrap();
        coeffs.push(c);
    }

    // --snip--

    // compute forgery using affine coordinates
    let mut aff_forge = G1Affine::zero();
    for (c, sig) in coeffs.iter().zip(sigs.iter()) {
        aff_forge = aff_forge + sig.mul(*c).into();
    }

    // compute forgery using projective coordinates
    let mut proj_forge = G1Projective::zero();
    for (c, sig) in coeffs.iter().zip(sigs.iter()) {
        proj_forge += sig.mul(*c);
    }

    // compute forgery using multi-scalar multiplication
    let coeffs: Vec<<Fr as PrimeField>::BigInt> = coeffs.iter().map(|c| (*c).into_repr()).collect();
    let msm_forge = VariableBaseMSM::multi_scalar_mul(&sigs, &coeffs);

    /* Your solution here! */

    verify(pk, m, aff_forge);
    verify(pk, m, proj_forge.into_affine());
    verify(pk, m, msm_forge.into_affine());
    println!("Puzzle solved!");
}

Then we move to Sage. We write a script sage/lin_algebra.sage that reads matrix $\mathbf{M}$ and vector ${\mathbf{h}}^{\ast }$ from file sage/data.sage and then we use the solve_left method to solve the linear system. Note that we must work over the scalar field ${\mathbb{F}}_r$ of BLS12-381 and explicitly declare that $\mathbf{M}$ and ${\mathbf{h}}^{\ast }$ are defined over ${\mathbb{F}}_r.$ After that, we write coefficients of solution $\mathbf{c}$ returned by Sage in file sage/coeffs.txt, one coefficient per line. Note that $\mathbf{M}$ is invertible and the system has a unique solution (which was not a given). Here is the content of the sage/lin_algebra.sage file (the size $r$ of the scalar field of BLS12-381 can be found for example here):

r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
Fr = FiniteField(r)
load('sage/data.sage')
M = Matrix(Fr, M)
h = vector(Fr, h)
c = M.solve_left(h)
file = open('sage/coeffs.txt', 'w')
for coeff in c:
    file.write(str(coeff) + '\n')
file.close()

We simply run it with

$ sage ./sage/lin_algebra.sage

It remains to import the coefficients in our Rust function and compute $S^{\ast }=\sum c_i{S}_i.$ For this, we read file sage/coeffs.txt line by line, obtaining strings that we must convert into elements of the scalar field. Hence, we bring BLS12-381 scalar field into scope with use ark_bls12_381::Fr and look for how to do the conversion. Initially, I tried to use functions from_be_bytes_mod_order and from_le_bytes_mod_order of the PrimeField trait (after converting strings into slices of bytes using as_bytes): the code compiles but the forgery does not verify... A simpler solution uses the fact that the PrimeField trait has supertrait FromStr, meaning one can directly convert strings into the Fr type using the parse method.

use bls_pedersen::bls::verify;
use bls_pedersen::data::puzzle_data;
use bls_pedersen::PUZZLE_DESCRIPTION;
use prompt::{puzzle, welcome};

// additional items brought into scope for puzzle solving
use bls_pedersen::hash::hash_to_curve;
use ark_crypto_primitives::crh::pedersen::bytes_to_bits;
use ark_ff::{PrimeField, Zero};
use ark_ec::{AffineCurve, ProjectiveCurve, msm::VariableBaseMSM};
use ark_bls12_381::{Fr, G1Affine, G1Projective};
use std::fs;
use std::fs::File;
use std::io::Write;

fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);
    let (pk, ms, sigs) = puzzle_data();
    for (m, sig) in ms.iter().zip(sigs.iter()) {
        verify(pk, m, *sig);
    }

    // --snip--

    let m = b"your_username";

    let mut data_file = File::create("sage/data.sage").unwrap();

    // write matrix M to be passed to SAGE
    data_file.write_all("M = [".as_bytes()).unwrap();
    for m in ms {
        let (hash, _) = hash_to_curve(&m);
        let bits = bytes_to_bits(&hash);
        let bits: Vec<u8> = bits.into_iter().map(|x| x as u8).collect();
        let line = format!("{:?}, ", bits);
        data_file.write_all(line.as_bytes()).unwrap();
    }
    data_file.write_all("]\n".as_bytes()).unwrap();

    // write vector h to be passed to SAGE
    data_file.write_all("h = ".as_bytes()).unwrap();
    let (hash, _) = hash_to_curve(m);
    let bits = bytes_to_bits(&hash);
    let bits: Vec<u8> = bits.into_iter().map(|x| x as u8).collect();
    let line = format!("{:?}", bits);
    data_file.write_all(line.as_bytes()).unwrap();

    // --snip--

    // read solution in coeffs.txt and cast these strings (one per line) into scalar field Fr elements
    let mut coeffs = Vec::new();
    for line in fs::read_to_string("sage/coeffs.txt").unwrap().lines() {
        // let c = Fr::from_le_bytes_mod_order(line.as_bytes()); // doesn't work
        let c: Fr = line.parse().unwrap();
        coeffs.push(c);
    }

    // --snip--

    // compute forgery using affine coordinates
    let mut aff_forge = G1Affine::zero();
    for (c, sig) in coeffs.iter().zip(sigs.iter()) {
        aff_forge = aff_forge + sig.mul(*c).into();
    }

    // compute forgery using projective coordinates
    let mut proj_forge = G1Projective::zero();
    for (c, sig) in coeffs.iter().zip(sigs.iter()) {
        proj_forge += sig.mul(*c);
    }

    // compute forgery using multi-scalar multiplication
    let coeffs: Vec<<Fr as PrimeField>::BigInt> = coeffs.iter().map(|c| (*c).into_repr()).collect();
    let msm_forge = VariableBaseMSM::multi_scalar_mul(&sigs, &coeffs);

    /* Your solution here! */

    verify(pk, m, aff_forge);
    verify(pk, m, proj_forge.into_affine());
    verify(pk, m, msm_forge.into_affine());
    println!("Puzzle solved!");
}

We are now ready to compute the forgery. Scalar multiplication is performed using the mul method. One can choose to work with affine or projective coordinates. One thing to note is that mul applied to a point in affine coordinates returns a point in projective coordinates. In order to add it to an affine point afterwards, it must be converted back into affine form using method into. There is also the option to use the multi_scalar_mul function (replaced by msm in version 0.4.0 of the library) implementing multi-scalar multiplication directly. However, the scalars in vector coeffs must first be cast into their "big integer" representation using the into_repr method. The code below uses the three possibilities. Note that the += operator does not work for affine representation.

use bls_pedersen::bls::verify;
use bls_pedersen::data::puzzle_data;
use bls_pedersen::PUZZLE_DESCRIPTION;
use prompt::{puzzle, welcome};

// additional items brought into scope for puzzle solving
use bls_pedersen::hash::hash_to_curve;
use ark_crypto_primitives::crh::pedersen::bytes_to_bits;
use ark_ff::{PrimeField, Zero};
use ark_ec::{AffineCurve, ProjectiveCurve, msm::VariableBaseMSM};
use ark_bls12_381::{Fr, G1Affine, G1Projective};
use std::fs;
use std::fs::File;
use std::io::Write;

fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);
    let (pk, ms, sigs) = puzzle_data();
    for (m, sig) in ms.iter().zip(sigs.iter()) {
        verify(pk, m, *sig);
    }

    // --snip--

    let m = b"your_username";

    let mut data_file = File::create("sage/data.sage").unwrap();

    // write matrix M to be passed to SAGE
    data_file.write_all("M = [".as_bytes()).unwrap();
    for m in ms {
        let (hash, _) = hash_to_curve(&m);
        let bits = bytes_to_bits(&hash);
        let bits: Vec<u8> = bits.into_iter().map(|x| x as u8).collect();
        let line = format!("{:?}, ", bits);
        data_file.write_all(line.as_bytes()).unwrap();
    }
    data_file.write_all("]\n".as_bytes()).unwrap();

    // write vector h to be passed to SAGE
    data_file.write_all("h = ".as_bytes()).unwrap();
    let (hash, _) = hash_to_curve(m);
    let bits = bytes_to_bits(&hash);
    let bits: Vec<u8> = bits.into_iter().map(|x| x as u8).collect();
    let line = format!("{:?}", bits);
    data_file.write_all(line.as_bytes()).unwrap();

    // --snip--

    // read solution in coeffs.txt and cast these strings (one per line) into scalar field Fr elements
    let mut coeffs = Vec::new();
    for line in fs::read_to_string("sage/coeffs.txt").unwrap().lines() {
        // let c = Fr::from_le_bytes_mod_order(line.as_bytes()); // doesn't work
        let c: Fr = line.parse().unwrap();
        coeffs.push(c);
    }

    // --snip--

    // compute forgery using affine coordinates
    let mut aff_forge = G1Affine::zero();
    for (c, sig) in coeffs.iter().zip(sigs.iter()) {
        aff_forge = aff_forge + sig.mul(*c).into();
    }

    // compute forgery using projective coordinates
    let mut proj_forge = G1Projective::zero();
    for (c, sig) in coeffs.iter().zip(sigs.iter()) {
        proj_forge += sig.mul(*c);
    }

    // compute forgery using multi-scalar multiplication
    let coeffs: Vec<<Fr as PrimeField>::BigInt> = coeffs.iter().map(|c| (*c).into_repr()).collect();
    let msm_forge = VariableBaseMSM::multi_scalar_mul(&sigs, &coeffs);

    /* Your solution here! */

    verify(pk, m, aff_forge);
    verify(pk, m, proj_forge.into_affine());
    verify(pk, m, msm_forge.into_affine());
    println!("Puzzle solved!");
}

The attack requires to run the Rust binary to write the file sage/data.sage, then the Sage script, and then the Rust binary again to read sage/coeffs.txt. Not great, but I have no idea how to call the Sage script from the Rust main function. Feel free to improve this, for example with a bash script.

Conclusion

The key takeaway of this puzzle is that Pedersen hashing does not behave as a random oracle. Although it is provably collision-resistant assuming the discrete logarithm problem is hard, it has a rich algebraic structure which makes it unsuitable for cases where a hash function behaving as a random oracle is required, such as BLS signatures.

Which hash-to-curve function should be used to make BLS secure then? The easy solution is to hash the message together with a counter into the base field of the elliptic curve until the result is the x-coordinate of a point on the curve.¹ The drawback is that it is not possible to implement it in constant time and that security of this construction is not known to hold in the strong sense of being indifferentiable from a random oracle [BCI+10]. For the specific case of BLS12-381, an efficient solution based on isogenies was recently proposed by Wahby and Boneh [WB19]. See also RFC 9380 specifying various hash-to-curve constructions.

---

1: Note that hashing into the scalar field to get $h(m)\in {\mathbb{F}}_r$ and letting $H(m)=h(m)G_1$ is completely insecure: one single signature $S=xH(m)=x(h(m)G_1)$ on some message $m$ reveals $x{G}_1=h(m{)}^{-1}S,$ which allows to forge a signature on any other message $m^{\prime }$ by computing $S^{\prime }=h(m^{\prime })(x{G}_1)=xH(m^{\prime }).$