Try   HackMD

ZK-Hack Puzzle #2 Writeup

Intro

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).

Group Dynamics

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.

Prime Order Subgroups and the Pohlig-Hellman Algorithm

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)

G and
xG
where the order of
G
is
nN
s.t.
n=i=1rpi
where
pi
are the prime factors of
n
. We wish to compute
x
(solving the Discrete Log Problem[1]).
Note that
xZn
.

We know, by the Chinese Remainder Theorem, that if we can find

xi=x mod pi for all
i
, then we can efficiently compute
x mod n
, which is
x
since
xZn
.

Now, we can compute

p¯i:=npi.
Then,
p¯iG
generates a subgroup of order
pi
.[2]
Assuming
pi
is small enough, we can iterate over
αZpi
and find
α
s.t.
α(p¯iG)=p¯i(xG)
.
Note that
α=x mod pi=xi
.
However in reality, this is done using the baby-step giant-step algorithm, taking only
O(pi)
time.

Now we use the Chinese Remainder Theorem to compute

x.

Overall, the time complexity of solving the Discrete Log Problem becomes:

O(p) where
p
is that largest prime factor of
n
.
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 Curve Cofactors

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:

E is defined by :
y2=x3+4
over
Fq
.
E2
is defined by:
y2=x3+4(1+u)
over
Fq2
.

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

r).
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:

factor(E.order()) > 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513 # pick r = the large prime, so: cofactor = 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 hex(cofactor) > 0x396c8c005555e1568c00aaab0000aaab

And this is indeed the cofactor used for

E.
The subgroup of order
r
is normally denoted as
G1
. (note the
G1
in the challenge is different)
A similar process has been done to compute the cofactor for
E2
to work in the group
G2
of order
r
also.

Some Intuition for the Challenge Ahead

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.

The Challenge

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

siG1 and
siG2
here.
Note that
G1
is a point on the BLS12_381 Curve we denoted
E
above.
And
G2
is a point on the BLS12_381 Curve we denoted
E2
.

To solve the challenge, all we have to do is find

s , or more specifically find
s
such that
sG1=sG1sG2=sG2
.
This means that we essentially want to compute the discrete log of either
sG1
or
sG2
.

The Solution

Note that for

i=0 we have
G1
and
G2
directly.
And for
i=1
we have
sG1
and
sG2
.

Keeping in mind our intuition for this challenge, it seems we must be able to utilize the Pholig-Hellman algorithm here in some way.

Investigation

In order to use the Pohlig-Hellman algorithm we must first know the prime factorizations of the orders of both

E and
E2
, and the subgroups generated by
G1
and
G2
(of
E
and
E2
, respectively).
We start with computing these for
G1
and
E
.
Using sage (and defining the curves
E
and
E2
using this gist), we compute these to be:

factor(E.order()) > 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513 G1 = E(/*coordinates of ts1_0 in rust code*/) factor(G1.order()) > 3 * 11 * 10177 * 859267 * 52437899 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

Now we can see that the order of the subgroup generated by the point

G1 indeed has small prime factors of sizes
3,11,10177,859267,52437899
.
Also, note that given the closure of groups,
sG1
is also in the same subgroup.

Partially Finding
s

We can now almost use the Pohlig-Hellman algorithm, the only problem is that

G1 and
sG1
are in a group where the big prime
524358...
(denote as
r
) 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

G1 by
r
, the order of the subgroup generated by
rG1
is exactly
n1:=3111017785926752437899
.
Because of the closure of groups then
s(rG1)
is also in the same subgroup, and
s(rG1)=r(sG1)
.

This means we can run the Pohlig-Hellman algorithm to find

s1:=s mod n1.
Luckily, sage has a built-in implementation of Pohlig-Hellman that's as simple to use as:

s_times_g1 = E(/*coordinates of ts1_1 in rust code*/) discrete_log(s_times_g1,G1,operation='+') > 2335387132884273659

However,

log2(s1)61 and we know that
s
is about 128-bits long.
This means we are missing some information (roughly 67-bits of it), about
s
.

Partially Finding More of
s

We now come back to

E2 and
G2
and find their relevant subgroup orders.
However, since the order of
E2
is roughly the square of the order of
E
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

E2 is:
0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5
(taken from here)
We also know that the order of the "safe" subgroup of
E2
is
r
(must be the same as in
E
for the pairing to work).
Therefore the order of
E2
is precisely
rcofactor
by definition of the cofactor.
Let's take a look at the factors of
cofactor
:

factor(E2_cofactor) > 13^2 * 23^2 * 2713 * 11953 * 262069 * 402096035359507321594726366720466575392706800671181159425656785868777272553337714697862511267018014931937703598282857976535744623203249

We see it's just

n2:=132232271311953262069 multiplied by some big prime (denote as
bp
)

If we use the same projection trick as before and compute

bprG2 and
bpr(sG2)
, these should both be in a subgroup of order
n2
.

However, it is not certain that

bprG2 generates a subgroup of order
n2
(it could generate a smaller subgroup).
So we need to find the order of
bprG2
.
We want to find the smallest number
n2
such that
n2bprG2=O
,
O
being the point at infinity.
By omitting prime factors of
n2
one at a time and multiplying by
bprG2
we can find this easily to be
271311953262069
.
We therefore define our base point to be
base:=132232bprG2
.
And the exponent point to be
exp:=132232bpr(sG2)
.
To compute
s2:=s mod n2
:

discrete_log(exp, base, 2713 * 11953 * 262069, operation='+') > 6942769366567

Note that

log2(s2)43 so can't use this alone to construct our 128-bit integer
s
.

Putting It All Together

We now have

s1=s mod n1 and
s2=s mod n2
.
We should also note that
gcd(n1,n2)=1
.
This means that we can apply the Chinese Remainder Theorem to compute
s=s mod (n1n2)
:

crt([s_mod_n1, s_mod_nt2], [n1, nt2]) > 62308043734996521086909071585406

Yet again, note that

log2(s)105.
This means that
ss
, at least if the challenge description is correct.
We can also run the assertions in the challenge code with our
s
to verify and see that indeed they do not pass.
We're still missing something!

Well, if you think about it, knowing that

s=s mod (n1n2) just means that for some
kN
,
s=k(n1n2)+s
.
And since
log2(n1n2)106
, and the fact that we know
s
is only about 128-bits long,
k
can only be about as large as
222
.
This means we can brute force
k
and find
s
!
With a little Rust this time:

let (_ts1, _ts2) = puzzle_data(); let n1_times_nt2 = Fr::from_str("128602524809671824928355010578973").unwrap(); let s_tag = Fr::from_str("62308043734996521086909071585406").unwrap(); for k in 0..4000000 { let s = n1_times_nt2*Fr::from(k) + s_tag; if _ts1[0].mul(s) == _ts1[1] && _ts2[0].mul(s) == _ts2[1] { println!("{}", s); return; } }

After 893,754 iterations, this prints out:
0x56787654567876541234321012343210
In decimal: 114939083266787167213538091034071020048
We run:

let s = Fr::from_str("114939083266787167213538091034071020048").unwrap(); assert_eq!(_ts1[0].mul(s), _ts1[1]); assert_eq!(_ts2[0].mul(s), _ts2[1]);

The asserts pass!
We did it!

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →


  1. Given a cyclic group

    G,
    g
    a generator, and
    gx
    , find
    x
    . ↩︎ ↩︎

  2. By Lagrange's theorem. ↩︎