ZK hack week 1 problem notes

let msg = r#"
______ _   __  _   _            _
|___  /| | / / | | | |          | |
   / / | |/ /  | |_| | __ _  ___| | __
  / /  |    \  |  _  |/ _` |/ __| |/ /
./ /___| |\  \ | | | | (_| | (__|   <
\_____/\_| \_/ \_| |_/\__,_|\___|_|\_\
"#;

Hello and welcome to my problem journal. The knowledge I’m operating on is a bachelor’s in Applied Mathematics with one course in cryptography, about two years working experience with Rust, and most importantly, significant enthusiasm. Note that this write-up is currently incomplete, as I have not yet solved the problem.

I’m writing this problem journal in attempt to:

1. Debug my intuition about cryptography, and thought processes to try when I get stuck
2. Share with others, so that we can learn together
3. Document my process so that I can go back, review what I didn’t know or understand, and improve.

Cryptography can be pretty dense, so I’m hoping that writing this problem journal will help me avoid getting stuck on particular details, or generally feel overwhelmed. Go team.

Note that the meat of the solution doesn’t really start until the section titled Figuring out where I’m stuck; til then I’m mostly stumbling around, getting oriented and set up.

Stumbling around cryptography

Starting in lib.rs, I look at this cryptographic problem and think, I recognize some of these words. Verify. hash, but not hash_to_curve. product_of_pairings, I think I remember what an eliptic curve pairing vaguely is, but I woudln’t be able to explain it. I don’t recognize G1Affine or G2Affine, but I would guess it means something about an affine group. Wikipedia affords me this unintelligible answer.

In mathematics, the affine group or general affine group of any affine space over a field K is the group of all invertible affine transformations from the space into itself.

It is a Lie group if K is the real or complex field or quaternions.

what?…kay, what about affine space.

An affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related to parallelism and ratio of lengths for parallel line segments.

Still wat? The picture makes things somewhat clearer, but only barely. How does this relate to our Affine group, and in what way is the group Affine? Still don’t know.

But I might interpret that we have two projections of some “affine” space of our eliptic curve–=BLS12381=–and somehow taking the ChaCha20rng seed of all ones (this seems sketchy), and the CRH over something called the G1Projective and the ZKHackPedersenWindow. Don’t recognize most of these terms, defering a call to my process heap to look these up.

But first, it seems safe to assume that whatever is breakable is in the repo, and not broken in Arkworks, or any of the dependencies. That seed of all ones looked sus. We want to compute a signature such that the product of these pairings is one:

(sig /*manipulate this*/, -prime_subgroup_generator), (hash_to_curve(msg) /* manipulate this */, pk)

It also looks sus that we’re handed a function puzzle_data that generates pk, ms, and sigs. That seems like a plausible attack surface.

Okay, so puzzle_data returns (public_key, messages, signatures). I get 256 signatures. I guess I also get the messages attached to these signatures.

Notable here though, I see a type, Cursor, that I don’t recognize, that might be worth looking up. The docs say:

// usage:
let pk = G2Affine::deserialize(&mut Cursor::new(pk_bytes)).unwrap();
// From docs:
/// A `Cursor` wraps an in-memory buffer and provides it with a
/// [`Seek`] implementation.
///
/// `Cursor`s are used with in-memory buffers, anything implementing
/// [`AsRef`]`<[u8]>`, to allow them to implement [`Read`] and/or [`Write`],
/// allowing these buffers to be used anywhere you might use a reader or writer
/// that does actual I/O.
///
/// The standard library implements some I/O traits on various types which
/// are commonly used as a buffer, like `Cursor<`[`Vec`]`<u8>>` and
/// `Cursor<`[`&[u8]`][bytes]`>`.

So I suppose there’s a reason I would want to be careful about how that data gets stored, and Cursor’s are maybe a way to store the key in RAM which probably gets wiped after dropping the buffer, or something like that. We also use Cursor’s on the signatures, but not on the messages. Wonder why. It doesn’t seem like signature strings should be sensitive.

But looking at puzzle data does give a hint how to pass type-checks. This now passes type checks, and we’re on the road to figuring out what to shove into sig.

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);
    }
    // new:
    use ark_bls12_381::G1Affine;
    use ark_serialize::CanonicalDeserialize;
    use std::io::Cursor;
    let sig = "abcd"; // figure out what to put here
    let sig = G1Affine::deserialize(&mut Cursor::new(hex::decode(sig).unwrap())).unwrap();
    let m = "thor314";
    let ms = hex::decode(m).unwrap();// note-to-self that we use hex::decode, not `as_bytes`.
    verify(pk, &ms, sig);
}

One more question: We’re now using hex::decode to encode our strings. I wonder what the difference between using that and just calling as_bytes is. But we’re at least passing type checks now.

To recap

so far, we’ve:

• Looked at lib.rs, main.rs, and bls.rs, and looked into some of the terms but not all
• Set up type checks in main, borrowing the the approach from data.rs
• Identified that we need to use some of the public key, messages, and signatures from data.rs to generate a new message and signature
• looked at hash.rs, and wondered if seeding rng_pedersen with all ones was sketchy

What next? Options are to look up the terms, try random stuff in the signature box

I guess we could actually, you know, run the code. Who knows, maybe Kobi is a troll king, all the apparent cryptography is just window dressing, and it’ll turn out that I just need to plug some random value in and I’ll be good to go.

It looks like verifying all the given signatures actually takes kindof a long time, about half a second for each sig, or about 128 seconds total. Might turn that off.

Get a runtime error

We have arrived. Our first runtime error.

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: IoError(Error { kind: UnexpectedEof, message: "failed to fill whole buffer" })', src/bin/verify-bls-pedersen.rs:22:82

Yay, we panicked! So my username message is going to need to be longer.

let m = "f2faa8b1bb0f06c6142e788ad836d1f7d1abf95458a08a55593c594056ac224d";

And now, a new error!

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: IoError(Error { kind: UnexpectedEof, message: "failed to fill whole buffer" })', src/bin/verify-bls-pedersen.rs:21:82

Which means the signature probably needs to be longer too.

let sig = "067ffcb122c43181eb4c525d2a7b56714262aae808ae24b62aa5ec6e1035a9f6ce6473f19dc470957afa98b437c68814";

And we are rewarded with our prize! No, not a solution, but an incrementally different error. Thanks be to the error oracle.

thread 'main' panicked at 'assertion failed: Bls12_381::product_of_pairings(&[(sig.into(),\n                                  G2Affine::prime_subgroup_generator().neg().into()),\n                                 (h.into(), pk.into())]).is_one()', src/bls.rs:10:5

Who knows, cryptography could have just been broken, allowing a win for dumb trying. Onto the next thing.

So back to actually trying to solve the problem.

Figuring out where I’m stuck

Uh. Right, so here’s the part where we’re kinda stuck, the real problem-solving part. The things I know I don’t know are:

• A bunch of the terms and types from up above: affine, BLS12381, ChaCha20rng, CRHScheme, G1Projective, ZKHackPedersenWindow, G1Affine, rng_pedersen, pedersenWindow, blake2s_simd, blake2s
• How to generate a new signature from a given string: I think I would need the private key to do this, so I suspect that somehow I should be able to take the 256 data points and attack the private key, or else, generate a new message-signature pair from some combination of other messages. That sounds linear algebra-y.

In any case, I’m going to have to go figure out how elliptic curve pairings work, and how this whole signature game is played.

a mere several days of reading and generally twiddling about later

BLS signatures and bilinear pairings

It turns out signatures are actually pretty straight-forward to construct. The math behind elliptic curves pairings and optimizations is e n t r e n c h e d (whisperings of sextic twists brush softly over the meager remants of my mathematical sophistication), but the actual algorithm to sign is really easy, grounded in the bilinear property of pairings, which just means, given bilinear pairing function e(a, b), the following is true (gosh darn no easy latex support in README):

e(a^x,b)=e(a,b)^x=e(a,b^x)

In this case x is our secret key, a is the hash of our message (a=h(m)), a^x is our signature, b is our group generator, and b^x is our public key.

So given messages m_1 and m_2, signatures s_1, s_2 (or possibly some larger set of messages and messages), we’d love it if something like the following were true, which would allow us to create a new message-signature pair:

h(f(m_1,m_2))^x = g(s_1,s_2)

where f,g are functions we want to know how to compute. That way we don’t have to determine the secret key. So now our task is to dive into the implementation deets of the Pedersen hash, and look for those functions.

Pedersen Hash

Defined in the Aleo pedersen hash example, the pedersen hash is pretty straightforward (the ark-crypto-primitives implementation is a bit more complex but looks similar):

circuit PedersenHash {
  parameters: [group; 256],

  // Instantiates a Pedersen hash circuit
  function new(parameters: [group; 256]) -> Self {
      return Self { parameters: parameters };
  }

  function hash(self, bits: [bool; 256]) -> group {
      let digest: group = 0group;
      for i in 0..256 {
          if bits[i] {
              digest += self.parameters[i];
          }
      }
      return digest;
  }

We want to find some combination of messages m_1+...+m_k=m_n, or signatures s_1+...+s_k=s_n. Let the parameter array of 256 elements be denoted p_i. After trying a couple things on paper, the following stands out: We can produce a new signature as a product of two other signatures,

s_1*s_2=(sum m_1i*p_i)^x*(sum m_2i*p_i)^x

= [(sum m_1i*p_i)*(sum m_2i*p_i)]^x

In which we have reduced the problem to finding the pre-image of (sum m_1i*p_i)*(sum m_2i*p_i), by exploiting the Pedersen hash.

We have our parameters:

let rng_pedersen = &mut ChaCha20Rng::from_seed([
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1,
  ]);
let parameters = CRH::<G1Projective, ZkHackPedersenWindow>::setup(rng_pedersen).unwrap();

So