ZK-Hack is a 7-week long event that is still active right now.
The event includes cool workshops to introduce people to the field of Zero-Knowledge Proofs and their uses in the real world!
It also includes fun puzzles that help to really understand the given material by playing around with the underlying mathematical structures used in some ZK Proof systems (the event is hosted at https://www.zkhack.dev/).
This post is a writeup of the second puzzle that I solved together with Matan and Elichai, and is a follow-up post to the solution of the first puzzle (available here).
If it's small, it should not be here
This is the clue we are given as the challenge begins.
We are also referred to a paper on prime order subgroups.
And as usual the documentation of the arkworks library.
The challenge is hosted on Github here.
First, let's talk about prime order subgroups and elliptic curve cofactors.
The Pohlig-Helman algorithm allows us to compute the discrete log of some element in an abelian group efficiently, given that its order has small prime factors.
For full details read here.
We will describe a simplified version to focus on the key points.
Given two group elements (using additive notation) and where the order of is s.t. where are the prime factors of . We wish to compute (solving the Discrete Log Problem[1]).
Note that .
We know, by the Chinese Remainder Theorem, that if we can find for all , then we can efficiently compute , which is since .
Now, we can compute .
Then, generates a subgroup of order .[2]
Assuming is small enough, we can iterate over and find s.t. .
Note that .
However in reality, this is done using the baby-step giant-step algorithm, taking only time.
Now we use the Chinese Remainder Theorem to compute .
Overall, the time complexity of solving the Discrete Log Problem becomes: where is that largest prime factor of .
This is why it's "bad" to have small prime order subgroups in a group where we wish the Discrete Log Problem [1:1] to be hard.
Elliptic Curves are complex objects with a lot of interesting properties, we will try here to focus specifically on the properties that are relevant to the solution of this challenge. Full details here.
We are working with the BLS12-381 Curve.
However these are actually 2 curves:
is defined by : over .
is defined by: over .
However, the orders of these groups have small prime factors (example below).
And we just learned why this is bad.
So what is usually done, is working in a subgroup on the curve that is of a large prime order (denote as ).
This is done by multiplying every point on the curve by a cofactor.
The cofactor is computed as the product of all small prime factors of the order of the group.
Example:
And this is indeed the cofactor used for .
The subgroup of order is normally denoted as . (note the in the challenge is different)
A similar process has been done to compute the cofactor for to work in the group of order also.
Already we can develop some intuition (based on the clues given), that in the challenge we should be able to find an opportunity to compute the discrete log of some group element in a scenario that allows the Pohlig-Hellman algorithm to be utilized.
Alice has computed a trusted setup for a Groth16 proof scheme.
She decided to use a 128-bit long secret, and she swears that she does not know the secret s needed to get this setup.
The trusted setup is constructed as follows using two additional scalars α and β:
- [s^i] G1 for 0 ⩽ i ⩽ 62,
- [α s^i] G1 for 0 ⩽ i ⩽ 31,
- [β s^i] G1 for 0 ⩽ i ⩽ 31,
- [s^i] G2 for 0 ⩽ i ⩽ 31.
Can you recover the secret anyway?
We then find the corresponding and here.
Note that is a point on the BLS12_381 Curve we denoted above.
And is a point on the BLS12_381 Curve we denoted .
To solve the challenge, all we have to do is find , or more specifically find such that .
This means that we essentially want to compute the discrete log of either or .
Note that for we have and directly.
And for we have and .
Keeping in mind our intuition for this challenge, it seems we must be able to utilize the Pholig-Hellman algorithm here in some way.
In order to use the Pohlig-Hellman algorithm we must first know the prime factorizations of the orders of both and , and the subgroups generated by and (of and , respectively).
We start with computing these for and .
Using sage (and defining the curves and using this gist), we compute these to be:
Now we can see that the order of the subgroup generated by the point indeed has small prime factors of sizes .
Also, note that given the closure of groups, is also in the same subgroup.
We can now almost use the Pohlig-Hellman algorithm, the only problem is that and are in a group where the big prime (denote as ) is also a factor of the order.
However, exactly as cofactors are used on curve points to project them into a "safe" subgroup of a large prime order, we can use the same method to project the points into an "unsafe" subgroup:
If we multiply by , the order of the subgroup generated by is exactly .
Because of the closure of groups then is also in the same subgroup, and .
This means we can run the Pohlig-Hellman algorithm to find .
Luckily, sage has a built-in implementation of Pohlig-Hellman that's as simple to use as:
However, and we know that is about 128-bits long.
This means we are missing some information (roughly 67-bits of it), about .
We now come back to and and find their relevant subgroup orders.
However, since the order of is roughly the square of the order of we will need to use publicly available parameters to compute this. (Running E2.order()
directly won't return a result anytime soon).
We know that the cofactor of is:
0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5
(taken from here)
We also know that the order of the "safe" subgroup of is (must be the same as in for the pairing to work).
Therefore the order of is precisely by definition of the cofactor.
Let's take a look at the factors of :
We see it's just multiplied by some big prime (denote as )
If we use the same projection trick as before and compute and , these should both be in a subgroup of order .
However, it is not certain that generates a subgroup of order (it could generate a smaller subgroup).
So we need to find the order of .
We want to find the smallest number such that , being the point at infinity.
By omitting prime factors of one at a time and multiplying by we can find this easily to be .
We therefore define our base point to be .
And the exponent point to be .
To compute :
Note that so can't use this alone to construct our 128-bit integer .
We now have and .
We should also note that .
This means that we can apply the Chinese Remainder Theorem to compute :
Yet again, note that .
This means that , at least if the challenge description is correct.
We can also run the assertions in the challenge code with our to verify and see that indeed they do not pass.
We're still missing something!
Well, if you think about it, knowing that just means that for some , .
And since , and the fact that we know is only about 128-bits long, can only be about as large as .
This means we can brute force and find !
With a little Rust this time:
After 893,754 iterations, this prints out:
0x56787654567876541234321012343210
In decimal: 114939083266787167213538091034071020048
We run:
The asserts pass!
We did it!
By Lagrange's theorem. ↩︎