This is the solution of the challenge “0KPR00F” given during the Real World CTF 2023. It consists in building a proof of knowledge of a polynomial with precomputed values to solve the challenge.
Description
Sh0w me the pr00f that y0u understand 0kpr00f. If its 0k, i’ll give y0u what y0u want!
attachment
Details
Points: 253
Category: Cryptography
Difficulty: Normal
Solution
When I connected to the server I got the following:
1
2
3
4
5
6
|
$ nc 47.254.47.63 13337
===========================
=WELCOME TO 0KPR00F SYSTEM=
===========================
([(1, 2), (10379311896927965078222180496288933615490530636358549278722177941964432884774, 7714509547569547798808229734646562867723556482384579010071769197480504336820), (3430616551040693219375135771877718810100593689378571508540000319060009831995, 3077500218059954920753338177739977288976705006364594908607537631943798594197), (3787691576821593685680503839478172408486614683487196728593343273819100804201, 3831639355435016445715662230078328463558932472680696826196616869902797206), (19841881606621412536970038986561135035745622707645602001317223990002053108489, 13782469556412737599850638460219394311778093611654835271770857279466058205201), (8585676052234124669074804040520033333948752714453755567676786003836082067069, 19345430380238515974788622182247013681195550523399059839595229686348642094430), (1806043790060102361742450341261907972984590831344220493030906722464215393940, 19513764956890163748821731866424821217672746065877392905085472966266456881944)], [(20338496883582943734783303139016724304685194792912539663763670207865827698840, 21738697805318546675108038901434406624781566118002771204019863879986265605795), (9163192313188025029553714036120159948417877779051855182790084709262690910111, 20773011463725144184929526375468675360502603170804090094623241314977081605973), (15874028040075451397445928238377587396935441716544903997498753947336094108161, 17850586069908753922648021421026823802415535421969843674025874423241988916781), (8697307488080822487974907094816751870067072923078076669691800467892130521704, 1928364690689212967787539073995654394707271699311847496446680838279653513147), (6547568923769866388119163296638527904001918215439747770996134438432404081139, 13130835415334760694600346759333420446489084404155467863362807204995735119970), (9919002048901036744630570357777078338852247040262166854767672104625284300923, 18721625954024341662869229681932280168815894838106996547587010561721318159029), (6037679886357130414201147978531458973794179605469218759532046933054234721499, 10511828560746147010211833433274330964611672405487254060689407540847263774420)])
now give me your proof
|
The challenge is related to zk-SNARK. All computations are done on bn128 curve now more often called bn254. The challenge was build with the library py_ecc from Ethereum.
The goal is to send the server a proof that the verifier knows a polynomial:
$$Z(x) = (x-1)(x-2)(x-3)(x-4) = x^4 - 10x^3 + 35x^2 - 50x + 24$$
The sever samples random values $t$ and $a$ and gently gives us the values:
$$t\cdot G_1, t^2\cdot G_1, …, t^7\cdot G_1$$
$$at\cdot G_1, at^2\cdot G_1, …, at^7\cdot G_1$$
$G_1$ is a generator on the curve bn128. To have the flag I had to give the server a proof $\pi = (\mathrm{PiC}, \mathrm{PiCa}, \mathrm{PiH})$ such that:
$$e(a\cdot G_2, \mathrm{PiC}) = e(G_2, \mathrm{PiCa})$$
and
$$e(G_2, \mathrm{PiC}) = e(Z(t) \cdot G_2, \mathrm{PiH})$$
With $e$ being the Tate pairing and $G_2$ a generator of the twisted curve. To satisfy the second equation I built:
$$\mathrm{PiC} = t^4 \cdot G_1 - 10 t^3 \cdot G_1 + 35 t^2 \cdot G_1 - 50 t \cdot G_1 + 24 \cdot G_1 = Z(t) \cdot G_1$$
From the values previously sent by the server and I set $\mathrm{PiH} = G_1$. From the bilinearity of the paring we have:
$$e(G_2, \mathrm{PiC}) = e(G_2, Z(t) \cdot G_1) = Z(t) e(G_2, G_1) = e(Z(t) \cdot G_2, \mathrm{PiH})$$
Then I built:
$$\mathrm{PiCa} = at^4 \cdot G_1 - 10 a t^3 \cdot G_1 + 35 at^2 \cdot G_1 - 50 a t \cdot G_1 + 24 \cdot G_1 = a Z(t) \cdot G_1$$
Similarly it satisfies the first equation. It was difficult to build the solution with the py_ecc library since it does not handle all the computations properly:
1
2
3
4
5
6
|
>>> from py_ecc import bn128
>>> G1 = bn128.G1
>>> curve_order = bn128.curve_order
>>> multiply = bn128.multiply
>>> multiply(G1, -1)
zsh: segmentation fault (core dumped) python
|
Even though it is possible to write the solution with this library, I decided to write it with Sage and import the curve parameters:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#!/usr/bin/env sage
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
E = EllipticCurve(GF(p),[0, 3])
G1 = E(1,2)
q = 21888242871839275222246405745257275088548364400416034343698204186575808495617
PK = ([(1, 2), (10379311896927965078222180496288933615490530636358549278722177941964432884774, 7714509547569547798808229734646562867723556482384579010071769197480504336820), (3430616551040693219375135771877718810100593689378571508540000319060009831995, 3077500218059954920753338177739977288976705006364594908607537631943798594197), (3787691576821593685680503839478172408486614683487196728593343273819100804201, 3831639355435016445715662230078328463558932472680696826196616869902797206), (19841881606621412536970038986561135035745622707645602001317223990002053108489, 13782469556412737599850638460219394311778093611654835271770857279466058205201), (8585676052234124669074804040520033333948752714453755567676786003836082067069, 19345430380238515974788622182247013681195550523399059839595229686348642094430), (1806043790060102361742450341261907972984590831344220493030906722464215393940, 19513764956890163748821731866424821217672746065877392905085472966266456881944)], [(20338496883582943734783303139016724304685194792912539663763670207865827698840, 21738697805318546675108038901434406624781566118002771204019863879986265605795), (9163192313188025029553714036120159948417877779051855182790084709262690910111, 20773011463725144184929526375468675360502603170804090094623241314977081605973), (15874028040075451397445928238377587396935441716544903997498753947336094108161, 17850586069908753922648021421026823802415535421969843674025874423241988916781), (8697307488080822487974907094816751870067072923078076669691800467892130521704, 1928364690689212967787539073995654394707271699311847496446680838279653513147), (6547568923769866388119163296638527904001918215439747770996134438432404081139, 13130835415334760694600346759333420446489084404155467863362807204995735119970), (9919002048901036744630570357777078338852247040262166854767672104625284300923, 18721625954024341662869229681932280168815894838106996547587010561721318159029), (6037679886357130414201147978531458973794179605469218759532046933054234721499, 10511828560746147010211833433274330964611672405487254060689407540847263774420)])
PKC, PKCa = PK
PiH = G1
# Z(t) = t^4 - 10*t^3 + 35*t^2 - 50*t + 24
PiC = E(PKC[4]) - 10 * E(PKC[3]) + 35 * E(PKC[2]) - 50 * E(PKC[1]) + 24 * E(PKC[0])
PiCa = E(PKCa[4]) - 10 * E(PKCa[3]) + 35 * E(PKCa[2]) - 50 * E(PKCa[1]) + 24 * E(PKCa[0])
print(PiC.xy(), PiCa.xy(), PiH.xy())
|
It allows to obtain the flag from the server:
1
2
|
(2105886096797248523222062850839400458170631766334910029391499655838049053351, 3690941523003270670836628198512120063249475341563577253939417831703171246051) (4984358660174439749773860317292255334342235967511003212599022834726397541537, 19958075134712263985569553337063769716562512118155733260774621571539778635985) (1, 2)
Congratulations,Here is flag:rwctf{How_do_you_feel_about_zero_knowledge_proof?}
|