# ZKHack - Puzzle 2

Michael Adjedj aka ZeroFearSyndrom

URL: https://www.zkhack.dev/puzzle2.html
GitHub Repo: https://github.com/kobigurk/zkhack-trusted-setup

----------------------

## First run
Running the Rust package with

cargo run --release

gives the following messages:

     ______ _   __  _   _            _
    |___  /| | / / | | | |          | |
       / / | |/ /  | |_| | __ _  ___| | __
      / /  |    \  |  _  |/ _` |/ __| |/ /
    ./ /___| |\  \ | | | | (_| | (__|   <
    \_____/\_| \_/ \_| |_/\__,_|\___|_|\_\
    
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?
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `GroupProjective { x: Fp384(BigInteger384([8505329371266088957, 17002214543764226050, 6865905132761471162, 8632934651105793861, 6631298214892334189, 1582556514881692819])), y: Fp384(BigInteger384([8505329371266088957, 17002214543764226050, 6865905132761471162, 8632934651105793861, 6631298214892334189, 1582556514881692819])), z: Fp384(BigInteger384([0, 0, 0, 0, 0, 0])) }`,
 right: `GroupAffine { x: Fp384(BigInteger384([15762092791530907762, 14353239805090574623, 13809155403070804300, 6989569382920461896, 5836331322348341706, 447374432227641519])), y: Fp384(BigInteger384([2537905508174741674, 7447226891833344413, 16859929101408865527, 8747024270350136743, 18161936183247689636, 1532509781487618909])), infinity: false }`', src/bin/verify-trusted-setup.rs:18:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

OK... So the following assertion failed.

    assert_eq!(_ts1[0].mul(s), _ts1[1]);

But we learn one interesting thing: the goal of this challenge is to **retrieve the master secret key $s$** used by Alice to compute the (un-)trusted setup.

## Code analysis
Let's dive a bit into what the code does. It consists in few files:

├── bin
│   └── verify-trusted-setup.rs <= main function
├── data.rs                     <= contains a lot of constant
└── lib.rs                      <= contains the puzzle description

Now, let's have a look at the main function:

fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);
    let (_ts1, _ts2) = puzzle_data();

    /* Your solution here! (s in decimal)*/
    let s = Fr::from_str("0").unwrap();

    assert_eq!(_ts1[0].mul(s), _ts1[1]);
    assert_eq!(_ts2[0].mul(s), _ts2[1]);
}

The first two calls just print out the ZKHack header and the challenge description, while the following `let (_ts1, _ts2) = puzzle_data();` seems more interesting. The function `puzzle_data()` in located in the `data.rs` file. The prototype of this function is the following:

pub fn puzzle_data() -> ([G1Affine; 2 * 32 - 1 + 32 + 32], [G2Affine; 32]);

So it returns two arrays of Elliptic Curve Points. The first one, of size 127 (`= 2 * 32 - 1 + 32 + 32`), the second one of size 32.
The first array contains points of the $G_1$ group, in affine form, the second one points of the $G_2$ group.

Here are the mathematical description of the involved groups:
- $G_1$ is the subgroup of order $r = 52435875175126190479447740508185965837690552500527637822603658699938581184513$ of the curve BLS12_381
- $G_2$ is the subgroup of order $r$ of the quadratic twist of BLS12_381
- BLS12_381 is the following elliptic curve (sorry for the line split):
- $p = 4002409555221667393417789825735904156556882819939007885332$ //
$058136124031650490837864442687629129015664037894272559787$
- $E(Fp): Y^2 = X^3 + 4$
- $\#E(Fp) = 3\cdot 11^2 \cdot 10177^2 \cdot 859267^2 \cdot 52437899^2 \cdot r$

## Breaking the challenge

### Dry run and setting everything up

To work on this challenge, I used my favorite computer algebra systems ever (probably one of the bests)! PARI-GP (Vive Bordeaux !), available at this address: https://pari.math.u-bordeaux.fr/ which you can install typing `apt install pari-gp`.

So let's import all the parameters first:

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab;
Ell = ellinit([0, 4], p);
cofac = 0x396c8c005555e1568c00aaab0000aaab;
ord = ellcard(Ell);
r = ord / cofac;

Now, let's import the two first points from the `puzzle_data` function:

P1 = [0x0F99F411A5F6C484EC5CAD7B9F9C0F01A3D2BB73759BB95567F1FE4910331D32B95ED87E36681230273C9A6677BE3A69, 0x12978C5E13A226B039CE22A0F4961D329747F0B78350988DAB4C1263455C826418A667CA97AC55576228FC7AA77D33E5];
P2 = [0x16C2385B2093CC3EDBC0F2257E8F23E98E775F8F6628767E5F4FC0E495285B95B1505F487102FE083E65DC8E9E3A9181, 0x0F4B73F63C6FD1F924EAE2982426FC94FBD03FCEE12D9FB01BAF52BE1246A14C53C152D64ED312494A2BC32C4A3E7F9A];

From the puzzle description, we can say the $P_2 = [s]P_1$

First of all, make sure that the import of the two points was correct:

(19:18) gp > ellisoncurve(Ell, P1)
%8 = 1
(19:37) gp > ellisoncurve(Ell, P2)
%9 = 1

Now check that they belong to the proper subgroup. For this, we will simply check that $[r]P_i$ is the point at infinity (represented as $[0]$ in PARI-GP):

(19:38) gp > ellpow(Ell, P1, r) == [0]
%10 = 0
(19:38) gp > ellpow(Ell, P2, r) == [0]
%11 = 0

Wait... What?! I may have done something wrong during the transfer Rust->PARI-GP... Let's check it again... My imports were all correct after all. Let's see what happens here.
Let's compute the order of the points:

(19:41) gp > o = ellorder(Ell, P1); factor(o)
%13 = 
[                                                                            3 1]

[                                                                           11 1]

[                                                                        10177 1]

[                                                                       859267 1]

[                                                                     52437899 1]

[52435875175126190479447740508185965837690552500527637822603658699938581184513 1]

So the order is smooth, and is $3\cdot 11 \cdot 10177 \cdot 859267 \cdot 52437899 \cdot r$. This sounds like a **small subgroup attack**!

### Solving the Discrete Logarithm

Note that $P_1$ and $P_2$ are of same order. Let's denote it $o$. So the points $[r]P_1$ and $[r]P_2 := [rs]P_1$ are of smooth order $\gamma = 3\cdot 11 \cdot 10177 \cdot 859267 \cdot 52437899$. Solving Dlog for those two points becomes very easy, thanks to a powerful combination of the Pollig-Hellman reduction with any of the usual Dlog solving algorithms.
Fortunately PARI-GP already integrates it in the `elllog()` function:

(20:07) gp > rP1 = ellpow(Ell, P1, r);
(20:07) gp > rsP1 = ellpow(Ell, P2, r);
(20:07) gp > alpha = elllog(Ell, rsP1, rP1)

The result is computed in only few milliseconds!
This first step tells us that $s \equiv 2335387132884273659 \mod \gamma$. Differently speaking, we can write $s$ as $s = 2335387132884273659 + k \cdot \gamma$ for an unknown $k$.

Nice! The challenge description states that "[Alice] decided to use a 128-bit long secret", so
- $s < 2^{128}$
- $2335387132884273659 + k \cdot \gamma < 2^{128}$
- $k < (2^{128} - 2335387132884273659) / \gamma < 2^{65}$

We now know that $k$ is at most 65-bits long. We must define the Dlog instance to find this $k$.
It can be achieved by noticing that $P_2 - [2335387132884273659]P_1 = [k\gamma]P_1$.

Solving the Dlog problem with $P_2 - [2335387132884273659]P_1$ and $[\gamma]P_1$ will give us $k$. But this is not easy. The PARI-GP `elllog` function implements the BabyStep-GiantStep algorithm which, to solve this instance, will require $\mathcal{O}\left(\sqrt{2^{65}}\right)$ operations (doable on a regular laptop), but requires $\mathcal{O}\left(\sqrt{2^{65}}\right)$ in storage (less doable...).

My first attempt failed miserably. I got OOM'ed quickly. I found out that Sage (https://www.sagemath.org/) offers additional Dlog solving algorithm. One is of particular interest, since it allows the caller to specify bounds to the discrete log, and would have a storage complexity of $\mathcal{O}\left(log(\sqrt{2^{65}})\right)$ (much lower than previously)

discrete_log_lambda(a, base, bounds, operation='*', hash_function=<built-in function hash>)

I ran it on the previous instance, but got nothing after one hour... But I noticed that only one core was working on my machine, and as far as I remember, the Pollard Lambda method can be parallelized.
I let it run on my machine, and search over the internet whether such parallel implementation existed.

I finally found this very powerful python implementation: https://github.com/Telariust/pollard-kangaroo. It works with both Python 2/Python 3, and supports multi-core computations. The current code solves ECDLP only on the BTC curve. I modified the few lines defining the curve, and the generator, as:

A_short = 0
B_short = 4
modulo  = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
order   = 52435875175126190479447740508185965837690552500527637822603658699938581184513
Gx      = 1691765604700820662413597467510238956833129262837483290676921058937608571052203865521568157973508327061054468773397
Gy      = 707371832587218157314095400180668998405228304396670482228056806517035905608579489520832124138514827069658663257925

The new generator being the point $[\gamma]P_1$. And I called it on command-line, giving it the range for $k$, and the point $P_2 - [2335387132884273659]P_1$ represented as an octet string as defined in the SEC1 standard:

$ python3 kangaroo.py 0000000000000001:1381204ca56cd56b3 040563e99f062db4f574851f6898b7cb7c1525343a870db7422914cb0e4afdea0d1f9fe291edea0aaea0b330e3fa534b4803d3fe17b8c07c1085c2498d6fc3bf331cb6852c36cf8bddb845b325ee8c362bd122f336c6a39ed48da3bb0ec0c47212

While running, this tool gave me live ETA, and I knew from the beginning that it will take no more than 2 hours on my machine. I got the answer I was looking for as

0x6968e64d55896815

One final step was to recover $s$ from all this, and check in the rust implementation that it was correct
$$s = 2335387132884273659 + 0x6968e64d55896815 \cdot \gamma$$ $$ s = 114939083266787167213538091034071020048$$

Inserting it in the Rust file confirmed me I was right! Cheers!