1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#!/usr/bin/sage
import hashlib
 
def solve_part1():
    SUB_TABLE = set() # contains (a, b, c) such that a - b == c (mod p)
    MUL_TABLE = set() # contains (a, b, c) such that a * b == c (mod p)
    REGISTERED_EC = set() # contains elliptic curve points in y^2 = x^3 + 7 (mod p)
    REGISTERED_X = set() # contains x-coordinates of a elliptic curve point of REGISTERED_EC
 
    bn254 = 21888242871839275222246405745257275088696311157297823662689037894645226208583
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    
    x_start = int(input()) % p 
    y_start = int(input()) % p
    assert (y_start * y_start) % p == (x_start * x_start * x_start + 7) % p 
 
    # this target value is the target x-coordinate
    target = int.from_bytes(hashlib.sha256(str(x_start).encode() + b"#" + str(y_start).encode()).digest(), "big") % p 
 
    # (x_start, y_start) is known to be a valid elliptic curve point
    REGISTERED_EC.add((x_start, y_start))
    REGISTERED_X.add(x_start)
 
    count = 0
    while True:
        count += 1
        assert count < 20000
        whi = int(input())
        if whi == 1 or whi == 2:
            a = int(input())
            b = int(input())
            quotient = int(input())
            result = int(input())
            assert 0 <= a < (1 << 256)
            assert 0 <= b < (1 << 256)
            assert 0 <= quotient < (1 << 256)
            assert 0 <= result < (1 << 256)
            if whi == 1:
                # add (a, b, result) in SUB_TABLE
                assert (a - b + p - quotient * p - result) % bn254 == 0 
                assert (a - b + p - quotient * p - result) % (1 << 256== 0
                SUB_TABLE.add((a, b, result))
            if whi == 2:
                # add (a, b, result) in MUL_TABLE
                assert (a * b - quotient * p - result) % bn254 == 0 
                assert (a * b - quotient * p - result) % (1 << 256== 0
                MUL_TABLE.add((a, b, result))
        if whi == 3:
            # check two points (x1, y1), (x2, y2) are already registered elliptic curve points
            # check (x3, y3) = (x1, y1) + (x2, y2) via elliptic curve addition
            # valid computation over (mod p) is checked by SUB_TABLE and MUL_TABLE
            x1 = int(input())
            y1 = int(input())
            x2 = int(input())
            y2 = int(input())
            assert (x1, y1) in REGISTERED_EC # check (x1, y1) is a known valid elliptic curve point
            assert (x2, y2) in REGISTERED_EC # check (x2, y2) is a known valid elliptic curve point
            lam = int(input())
            if x1 == x2 and y1 == y2: # point doubling algorithm
                x_sq = int(input())
                x_sq_3 = int(input())
                y_2 = int(input())
                y_2_inv = int(input())
                assert (x1, x1, x_sq) in MUL_TABLE # check x_sq = x1^2
                assert (x_sq, 3, x_sq_3) in MUL_TABLE # check x_sq_3 = 3 * x1^2
                assert (y1, 2, y_2) in MUL_TABLE # check y_2 = 2 * y1
                assert (y_2, y_2_inv, 1in MUL_TABLE # check y_2_inv = 1 / (2 * y1)
                assert (x_sq_3, y_2_inv, lam) in MUL_TABLE # check lam = (3 * x1^2) / (2 * y1)
            else:
                y_diff = int(input())
                x_diff = int(input())
                x_diff_inv = int(input())
                assert (y2, y1, y_diff) in SUB_TABLE # check y_diff = y2 - y1
                assert (x2, x1, x_diff) in SUB_TABLE # check x_diff = x2 - x1
                assert (x_diff, x_diff_inv, 1in MUL_TABLE # check x_diff_inv = 1 / (x2 - x1)
                assert (y_diff, x_diff_inv, lam) in MUL_TABLE # check lam = (y2 - y1) / (x2 - x1)
            lam_sq = int(input())
            lam_sq_minus_x1 = int(input())
            x_final = int(input())
            x1_minus_x_final = int(input())
            lam_mul_x1_minus_x_final = int(input())
            y_final = int(input())
            assert (lam, lam, lam_sq) in MUL_TABLE # check lam_sq = lam^2
            assert (lam_sq, x1, lam_sq_minus_x1) in SUB_TABLE # check lam_sq_minus_x1 = lam^2 - x1
            assert (lam_sq_minus_x1, x2, x_final) in SUB_TABLE # check x_final = lam^2 - x1 - x2
            assert (x1, x_final, x1_minus_x_final) in SUB_TABLE # check x1_minus_x_final = x1 - x_final
            assert (lam, x1_minus_x_final, lam_mul_x1_minus_x_final) in MUL_TABLE  # check lam_mul_x1_minus_x_final = lam * (x1 - x_final)
            assert (lam_mul_x1_minus_x_final, y1, y_final) in SUB_TABLE # check y_final = lam * (x1 - x_final) - y1
            REGISTERED_EC.add((x_final, y_final)) # add (x_final, y_final) to REGISTERED_EC
            REGISTERED_X.add(x_final) # add x_final to REGISTERED_X
        if whi == 4:
            break 
 
    assert target in REGISTERED_X # end with the target x-coordinate in REGISTERED_X
 
def solve_part2():
    ADD_TABLE = set() # contains (a, b, c) such that a + b == c (mod p)
    MUL_TABLE = set() # contains (a, b, c) such that a * b == c (mod p)
    
    # Curve25519
    p = (1 << 255- 19 
    E = EllipticCurve(GF(p), [0486662010])
    G = E(GF(p)(9), GF(p)(43114425171068552920764898935933967039370386198203806730763910166200978582548))
    
    # Commit a set of NUM_POINTS points in Curve25519
    NUM_POINTS = 165
    commit = bytes.fromhex(input().strip())
    assert len(commit) == 32 * NUM_POINTS 
 
    # this is the target point on Curve25519
    target = int.from_bytes(hashlib.sha256(commit).digest(), "big"* G
 
    # Add tuples to ADD_TABLE and MUL_TABLE by submitting proofs
    count = 0
    while True:
        count += 1
        assert count < 20000
        whi = int(input())
        if whi == 1 or whi == 2:
            a = int(input())
            b = int(input())
            quotient = int(input())
            result = int(input())
            assert 0 <= a < (1 << 256)
            assert 0 <= b < (1 << 256)
            assert 0 <= quotient < (1 << 256)
            assert 0 <= result < (1 << 256)
            if whi == 1:
                assert (a + b - (quotient * p + result)) % (1 << 512== 0
                ADD_TABLE.add((a, b, result))
            if whi == 2:
                assert (a * b - (quotient * p + result)) % (1 << 512== 0
                MUL_TABLE.add((a, b, result))
        if whi == 3:
            break
    
    # submit a bitmask corresponding to a subset
    # the subset sum of the points you committed before must equal to the target point
    bmask = int(input())
    assert 0 <= bmask < (1 << NUM_POINTS)
    
    tot = 0 * G
 
    for i in range(NUM_POINTS):
        if ((bmask >> i) & 1== 0# the bitmask doesn't contain the i'th point, so skip
            continue 
        # the bitmask contains the i'th point
        # decompress the 32 bytes, with proof, to obtain a point on Curve25519
        x = int(input())
        y = int(input())
        top_value = int(input()) 
        x_sq = int(input())
        x_cube = int(input())
        x_sq_486662 = int(input())
        sum1 = int(input())
        sum2 = int(input())
        # x_sum is the x-coordinate encoded in the 32 byte compressed format
        x_sum = 0
        for j in range(32):
            x_sum += commit[i * 32 + j] * (256 ** j)
        x_sum &= ((1 << 255- 1)
        # bit is the parity of the y-coordinate encoded in the 32 byte compressed format
        bit = (commit[i * 32 + 31>> 7& 1
        assert x == x_sum # check x matches the encoded x-coordinate
        assert 0 <= top_value < (1 << 255
        assert y == top_value * 2 + bit # check bit matches the parity of y
        assert (x, x, x_sq) in MUL_TABLE # check x_sq = x^2
        assert (x, x_sq, x_cube) in MUL_TABLE # check x_cube = x^3
        assert (x_sq, 486662, x_sq_486662) in MUL_TABLE # check x_sq_486662 = 486662 * x^2
        assert (x_cube, x_sq_486662, sum1) in ADD_TABLE # check sum1 = x^3 + 486662 * x^2
        assert (sum1, x, sum2) in ADD_TABLE # check sum2 = x^3 + 486662 * x^2 + x 
        assert (y, y, sum2) in MUL_TABLE # check y^2 = x^3 + 486662 * x^2 + x, so (x, y) is in Curve25519
        recovered_point = E(GF(p)(x), GF(p)(y)) 
        tot += recovered_point # add the recovered point to the subset sum
    
    assert tot == target # assert the subset sum matches the target point
 
solve_part1()
print("PART 1 SOLVED!")
 
solve_part2()
print("PART 2 SOLVED!")
 
flag = open("flag.txt""r").read()
print(flag)
cs

 

Part 1

You have access to proving subtraction and multiplication over $\mathbb{F}_p$, and using that, you can prove elliptic curve addition over secp256k1. From this, by using the provable elliptic curve addition, your goal is to provide $(x, y)$ inside secp256k1 such that you can provide a provable addition chain to the elliptic curve point with $H(x, y)$ as the x-coordinate. In other words, you need to find the discrete logarithm between $(x, y)$ and the point with $H(x, y)$ as the x-coordinate. Of course, raw discrete logarithm is hard in secp256k1.

 

The idea is in the faulty emulated finite field in the subtraction/multiplication proof.

 

Note that we are checking $a - b + p - q \cdot p - r = 0$ with the equation (here $l$ is the bn254 prime) $$a - b + p - q \cdot p - r \equiv 0 \pmod{l \cdot 2^{256}}$$ This isn't actually sound, as $q \cdot p$ can go as high as $2^{512}$, larger than the modulo of the equation above. Indeed, we can try $$a - b + p - q \cdot p + l \cdot 2^{256} = r$$ so in a way, we can get $r$ to be $l \cdot 2^{256} \pmod{p}$ more than what it's supposed to be. Similar ideas work for multiplication. 

 

This allows us to do weird things with the elliptic curve addition - so we can try an invalid curve attack. As secp256k1 is of the form $y^2 = x^3 + b$, we can try to move to the curve $y^2 = x^3$, where discrete logarithm is easy as a finite field operation as the curve is singular. Now the goal would be to find the starting point on secp256k1 such that after a single attack on subtraction/multiplication, the point lies on $y^2 = x^3$. This can be written as a system of polynomial equations with $x, y$, so the usual tricks with resultants or Groebner basis, or even manual reduction to a single variable equation works. I used manual reduction, and rbtree used Groebner basis. 

 

One of the solvers told me that a bruteforce for a smooth curve order ($p_{max} \approx 10^{15}$) worked, albeit painful. 

 

The idea was taken by this vulnerability report in ZKP systems. See #2. 

 

Part 2

You have to provide 165 points on Curve25519 in compressed form, and the hash of those points is the target point for subset sum. You then have to provide which of the 165 points will be the subset which sums to the target, while also providing the decompression proof that the compressed points decompress to the claimed result. Intuitively, $2^{165} \ll p$, so standard method doesn't work. 

 

The main idea here is that $y$ can be larger than $p$. Therefore, if the $b$ is the bit and $y$ is the square root of $sum2$ that is less than $p$ with $b$ as its LSB, one can actually use $y' = 2p - y$ which also has $b$ as its LSB. However, as $y' \pmod{p} = p - y$, we see that $(x, y')$ and $(x, y)$ are different points. Using this, we can actually make three decisions for each point - not use it, use $y$, or use $y'$. Now $3^{165} \approx 2^{262} \gg p$.

 

Now this challenge is a puzzle: you have to find a set $S$ such that you can easily solve the modified subset sum $$\sum_S c_i s_i = T, \quad c_i \in \{-1,0,1\}$$ as the $3^n$ thing suggests, this can be solved via ternary systems, setting $s_i = 3^i$. See balanced ternary systems.

 

There is a catch - you need to prove that $(2p - y)^2 \equiv sum2 \pmod{p}$. To do so, you need to provide $0 \le q < 2^{256}$ such that $$(2p-y)^2 = q \cdot p + sum2$$ which means that $$2p-y < \sqrt{2^{256} \cdot p} \approx \sqrt{2} p$$ forcing $y > (2 - \sqrt{2})p \approx 0.6p$. Therefore, this technique doesn't work for all $y$. 

 

This can be resolved as follows. Select the $i$th point as $3^i \cdot v_i \cdot G$ where $v_i$ is small positive integer, and not a multiple of $3$.

In this case, solving subset sum to $N$ with values $v_0, 3v_1, 9v_2, \cdots$ can be done recursively as follows

  • if $N \equiv 0 \pmod{3}$, solve $N/3$ with $v_1, 3v_2, 9v_3, \cdots$
  • if $N \equiv v_0 \pmod{3}$, solve $(N-v_0)/3$ with $v_1, 3v_2, 9v_3, \cdots$
  • if $N \equiv -v_0 \pmod{3}$, solve $(N+v_0)/3$ with $v_1, 3v_2, 9v_3, \cdots$

as we can see, the value of $N$ decreases exponentially - so at some point, the value of $N$ will become small regardless - say, within $[-40, 40]$. The unfortunate part is that we don't know if it will become exactly zero. In practice, it turns out that $N$ does become zero.

 

Here, we show a much more intuitively sound way for a finish. Since $3^{163}$ is sufficiently large, what we can do is to do the $3^i \cdot v_i \cdot G$ for $0 \le i < 164$, but set the final 164th point to be a random elliptic curve point. This point will not be used for subset sum, but it will be used to try out various target points, as the target point is the hash of the entire set of 165 points. This way, we can try various target points, and clearly with a sufficient probability we will be able to find a target point in which $N$ does become exactly zero.   

 

An alternate way by Mystiz is to have use $v_0, 3v_0, \cdots 3^{14} v_0, v_1, 3v_1, \cdots, 3^{14} v_1, \cdots v_{10}, \cdots, 3^{14} v_{10}$ and so on - then, one can try to solve for $\sum_{i=0}^{10} c_i v_i = T$ with small coefficients $c_i$ via LLL. Here, the catch is that $3^0 v_i, 3^1 v_i, \cdots, 3^{14} v_i$ must have working set of $y$-coordinates, but since there's only 15 points this actually works with high probability. Note that while we mentioned $y > 0.6p$, we can also handle $y < 0.4p$ using $p+y$ and $p-y$. Therefore, only 20% of the points fail to use this trick, and $0.8^{15}$ is definitely brute-forcable. 

 

The idea was taken by this vulnerability report in ZKP systems. See #9. 

'CTF' 카테고리의 다른 글

Paradigm CTF 2023 2nd Place  (0) 2023.10.31
CODEGATE 2023 Finals - The Leakers (1 solve)  (1) 2023.08.25
ACSC 2023 Writeups  (0) 2023.02.26
HackTM CTF Writeup  (0) 2023.02.22
BlackHat MEA Finals  (0) 2022.11.21

https://hackmd.io/qS36EcIASx6Gt_2uNwlK4A

 

Curta / Plonky2x Audit Report - HackMD

   owned this note    owned this note       Published Linked with GitHub # Curta / Plonky2x Audit Report ![kalos-logo-2](https://hackmd.io/_uploads/rJNoMpIB6.png =250x) Audited by Allen Roh (rkm0959). Report Published by KALOS. # ABOUT US Pione

hackmd.io

 

'Blockchain Security' 카테고리의 다른 글

zkSummit11 @ Athens  (0) 2024.02.24
Paradigm CTF 2023: "Cryptography Challenges"  (1) 2023.10.30
Scroll's Security Measure Seminar  (0) 2023.10.25
Scroll zkEVM Audit Report  (0) 2023.10.17
ZKP Security Seminar @ SpearbitDAO  (1) 2023.07.27

https://www.zksummit.com/

 

zkSummit - Zero Knowledge Summit

Join us for the next upcoming Zero Knowledge Summit. This edition bring together best thinkers and builders in the space to learn about the latest in zero knowledge research, SNARKs, STARKs, cryptographic primitives, privacy and maths.

www.zksummit.com

 

zkSummit11에 Speaker로 참가합니다! 

'Blockchain Security' 카테고리의 다른 글

Curta / Plonky2x Audit Report  (0) 2024.02.27
Paradigm CTF 2023: "Cryptography Challenges"  (1) 2023.10.30
Scroll's Security Measure Seminar  (0) 2023.10.25
Scroll zkEVM Audit Report  (0) 2023.10.17
ZKP Security Seminar @ SpearbitDAO  (1) 2023.07.27

https://hackmd.io/qb-NrfZ7SgWMvPGNF4xPxw

 

1/8-1/10: Fixing the Proof of [DP23] - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/8-1/10: Fixing the Proof of [[DP23]](https://eprint.iacr.org/2023/630.pdf) Continued from https://hackmd.io/c2eTRG3PSLeverwHTMkNDQ A similar approach is now integrated

hackmd.io

https://twitter.com/rkm0959/status/1746723799012442565

 

X의 rkm0959 | KALOS님(@rkm0959)

Here's something I've been working on the past week: finding & assisting in fixing a flaw in the extractability proof in https://t.co/BvfWzoqlJu - now fixed on eprint. discussed with @benediamond on this one, was a very fun experience. we auditing papers n

twitter.com

https://twitter.com/benediamond/status/1746724679706956213

 

X의 Ben Diamond님(@benediamond)

was a pleasure working through Merkle-extraction technicalities with @rkm0959, who is very astute. fixed version now live. the gap in our old proof also affects Brakedown 😅 @SuccinctJT

twitter.com

 

https://hackmd.io/gwQ-RYURT8G1MeE5g-sbPw

 

1/12: MPC Definitions / Problems Collection - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/12: MPC Definitions / Problems Collection - chapter 23 of https://toc.cryptobook.us/book.pdf - the book https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pd

hackmd.io

https://hackmd.io/b__SmbY8TESHKGOM4Hwo5Q

 

1/13: Beaver’s Protocol - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/13: Beaver's Protocol - Chapter 23.2 of https://toc.cryptobook.us/book.pdf ## The Big Idea Consider that we want to deal with $$(y_1, \cdots, y_m) = f(x_1, \cdots, x_n

hackmd.io

https://hackmd.io/1_LFw9IORhOsJsZLjNEkiA

 

1/14: Garbled Circuits - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/14: Garbled Circuits - Chapter 23.3 of https://toc.cryptobook.us/book.pdf - Chapter 3.1 of https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf - https://i

hackmd.io

 

https://hackmd.io/NmxP5CsPTAerr2E-oPFlkQ

 

1/4: Studying FRI Soundness - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/4: Studying FRI Soundness I actually skipped over a lot of parts on this, mostly intuitive understanding only. The reason for this was that the proof techniques were w

hackmd.io

https://hackmd.io/keVLzFSrQdmCcmUVh2l_BQ

 

1/5: Proximity Testing with Logarithmic Randomness - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/5: [[DP23]](https://eprint.iacr.org/2023/630.pdf): Logarithmic Randomness ## Summary Recall the statement from [1/3: Ligero's Proof for $q < d'/3$](https://hackmd.io/k

hackmd.io

https://hackmd.io/c2eTRG3PSLeverwHTMkNDQ

 

1/6: [DP23] Proof of Extractability - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/6: [[DP23]](https://eprint.iacr.org/2023/630.pdf) Proof of Extractability + Efficiency Continued from https://hackmd.io/keVLzFSrQdmCcmUVh2l_BQ ## Part 1: Extractor Def

hackmd.io

 

https://hackmd.io/WzCftDAjQ7u0mYTAEg49Bw

 

1/2: Succinct Proofs and Linear Algebra - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/2: Succinct Proofs and Linear Algebra preparation for studying Binius / more code-related PCS stuff fundamentally note: this write-up is really for my understanding -

hackmd.io

 

https://hackmd.io/k8_1AfQNTfy25N23QTmZ6g

 

1/3: Ligero’s Proof for q < d'/3 - HackMD

   owned this note    owned this note       Published Linked with GitHub # 1/3: [Ligero](https://eprint.iacr.org/2022/1608.pdf)'s Proof for $q < d'/3$ This is also used in Brakedown for its soundness proof. It's for general codes, so... The mai

hackmd.io

 

https://infossm.github.io/blog/2023/12/25/HyperNova/

 

Folding Part 2: HyperNova

이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 HyperNova에 대해서 다룬다. https://eprint.iacr.org/2023/573.pdf Preliminaries Incremental Verifiable Computation Incrementally Veri

infossm.github.io