https://github.com/rkm0959/rkm0959_presents/blob/main/PLONKBasic.pdf

 

GitHub - rkm0959/rkm0959_presents: Presentations by rkm0959

Presentations by rkm0959. Contribute to rkm0959/rkm0959_presents development by creating an account on GitHub.

github.com

 

For Open Source Contributon, Ethereum PSE, Advanced Track

https://github.com/rkm0959/Cryptography_Writeups/blob/main/2022/WAConQual/rsa-secret-sharing-chal.py

https://github.com/rkm0959/Cryptography_Writeups/blob/main/2022/WAConQual/rsa-secret-sharing-exploit.py

 

RSA Secret Sharing: by rkm0959 (2 solves in General, 1 solve in Junior)

ON 2-out-of-3 SECRET SHARING BASED ON RSA - MemeCrypt 2022

 

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
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import string, signal, random, hashlib 
signal.alarm(1500)
 
def gen_pow():
    print("Solve PoW plz")
    s = ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(16))
    print(s)
    answer = input()
    hash = bytes_to_long(hashlib.sha256((s + answer).encode()).digest())
    if hash != (hash >> 26<< 26:
        exit() 
 
gen_pow()
= getPrime(342)
print("q = {}".format(q))
 
class LCG:
    def __init__(self, a, x, b):
        self.a = a
        self.x = x 
        self.b = b 
    def fetch(self):
        ret = self.x
        self.x = (self.a * self.x + self.b) % q 
        return ret 
    
print("Hello! You are the owner of one Share Generator! Please insert your parameters :)")
= int(input()) % q
= int(input()) % q
= int(input()) % q
 
assert 1 <= a < q and 1 <= x < q and 1 <= b < q 
 
LCG1 = LCG(a, x, b)
LCG2 = LCG(random.randint(1, q-1), random.randint(1, q-1), random.randint(1, q-1))
LCG3 = LCG(random.randint(1, q-1), random.randint(1, q-1), random.randint(1, q-1))
 
# in Junior Division, LCG2.a was given additionally
 
def roll():
    return LCG3.fetch() * q * q + LCG2.fetch() * q + LCG1.fetch()
 
def checkFactor(n):
    u = int(input())
    v = int(input())
    assert 1 < u < n and 1 < v < n and u * v == n
 
pr = []
 
while len(pr) < 8:
    p = roll()
    if isPrime(p):
        pr.append(p)
 
n1 = pr[0* pr[1]
n2 = pr[2* pr[3]
n3 = pr[4* pr[5]
n4 = pr[6* pr[7]
 
print(n1)
print(n2)
print(n3)
print(n4)
 
checkFactor(n1)
checkFactor(n2)
checkFactor(n3)
checkFactor(n4)
 
flag = open("flag""r").read()
print(flag)
cs

 

Solution

Denote $a_i, x_i, b_i$ to be the initial LCG parameters of $LCG_i$. Denote $LCG_{i, j}$ to be the $j$th value that $i$th LCG generated. 

Note that we control $a_1, x_1, b_1$. We see that with $a_i \not\equiv 1 \pmod{q}$, $$LCG_{i, j} \equiv a_i^j x_i + \frac{a_i^j - 1}{a_i - 1} b_i \equiv a_i^j \left(x_i + \frac{b_i}{a_i - 1} \right) - \frac{b_i}{a_i-1} \pmod{q}$$

We are generating roughly $1024$ bit primes, so with heuristics on prime gap we may assume that we will get our 8 primes generated in our first 6000 tries. Our first goal is to find out which of those 6000 tries were the ones that we actually generated a prime successfully.

 

To do so, we send random $a = a_1, x = x_1, b = b_1$ to the server. This generates random enough values for the LCG we control, and these LCG values will be the value of our primes modulo $q$. For each $n$, there will be two indices $u, v$ such that $$n \equiv LCG_{1, u} \cdot LCG_{1, v} \pmod{q}$$ and we may find these $u, v$ via simple brute force. 

 

Now we move on to finding the parameters for LCG2, the second LCG. If two indices $u, v$ generated $n$, we see $$n \equiv (LCG_{2, u} q + LCG_{1, u})(LCG_{2, v}q + LCG_{1, v}) \pmod{q^2}$$ and with the knowledge of $u, v, LCG_{1, u}, LCG_{1, v}$, we can write $$LCG_{1, v} LCG_{2, u} + LCG_{1, u} LCG_{2, v} \equiv \frac{n - LCG_{1, u}LCG_{1,v}}{q} \pmod{q}$$ Denote $$C \equiv x_2 + \frac{b_2}{a_2 - 1} \pmod{q}, \quad D \equiv - \frac{b_2}{a_2 - 1} \pmod{q}$$ and we can now write, with $LCG_{2, u} \equiv a_2^u C + D \pmod{q}$ and $LCG_{2, v} \equiv a_2^v C + D \pmod{q}$, that $$\left( LCG_{1, v}  a_2^u + LCG_{1, u} a_2^v \right) C + \left( LCG_{1, u} +LCG_{1, v} \right) D  \equiv \frac{n - LCG_{1, u}LCG_{1,v}}{q} \pmod{q}$$

 

Note that we have four $n$, so four such equations - and we note that $(C, D, -1)$ is orthogonal to $$\left( LCG_{1, v} a_2^u + LCG_{1, u} a_2^v, LCG_{1, u} + LCG_{1, v}, \frac{n - LCG_{1, u} LCG_{1, v}}{q} \right)$$ when considered as vectors in $\mathbb{F}_q^3$. Therefore, given three such vectors, they will be linearly dependent. This can be expressed algebraically by taking three such vectors, making a matrix with them, and then claiming its determinant is zero. 

 

This determinant will be a polynomial of $a_2$ over $\mathbb{F}_q$. There are now two ways to finish.

The first one is to directly factor this polynomial to find its roots. This is efficient enough to solve the challenge.

The second one is to get two such polynomials, using the fact that we are given not three, but four such equations. Then we can simply take the GCD of two polynomials to get a polynomial of much smaller degree. This can be solved to get $a_2$.

 

With $a_2$ calculated, we can solve the linear system to get $C, D$, and then we can solve for $x_2, b_2$ by $$x_2 \equiv C+D \pmod{q}, \quad b_2 \equiv -D(a_2-1) \pmod{q}$$ We can even check for validity of $a_2$ by checking if all four $n \pmod{q^2}$ can be recalculated accordingly. 

 

We now have full knowledge of the second LCG. There are now two ways to finish. 

The first one is to use Coppersmith's Attack - since we know 2/3 of each primes we can definitely factor each $n$. 

The second one is to apply this same logic to the third LCG - the details are practically the same. 

 

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
from sage.all import *
from pwn import * 
from tqdm import tqdm 
import random as rand
from Crypto.Util.number import inverse
 
conn = remote("175.123.252.200"6666)
 
conn.recvline()
= conn.recvline().rstrip().decode()
assert len(s) == 16
 
for i in tqdm(range(1 << 28)):
    t = str(i)
    hash = hashlib.sha256((s + t).encode()).hexdigest()
    if hash[-6:] == "000000" and hash[-7in "048c"
        conn.sendline(t.encode())
        break
 
= int(conn.recvline().split()[-1])
conn.recvline()
 
a_mine = rand.randint(1, q - 1)
x_mine = rand.randint(1, q - 1)
b_mine = rand.randint(1, q - 1)
 
conn.sendline(str(a_mine).encode())
conn.sendline(str(x_mine).encode())
conn.sendline(str(b_mine).encode())
 
n1 = int(conn.recvline())
n2 = int(conn.recvline())
n3 = int(conn.recvline())
n4 = int(conn.recvline())
 
n1q = n1 % q 
n2q = n2 % q
n3q = n3 % q 
n4q = n4 % q 
 
n1qq = n1 % (q * q)
n2qq = n2 % (q * q)
n3qq = n3 % (q * q)
n4qq = n4 % (q * q)
 
targets = [n1, n2, n3, n4]
targetsq = [n1q, n2q, n3q, n4q]
targetsqq = [n1qq, n2qq, n3qq, n4qq]
 
dat = [x_mine]
for i in range(010000):
    dat.append((a_mine * dat[-1+ b_mine) % q)
 
dic = {}
for i in range(10000):
    dic[dat[i]] = i
 
idx = [(-1-1)] * 4
for i in range(10000):
    for j in range(4):
        target = (targetsq[j] * inverse(dat[i], q)) % q
        if target in dic.keys():
            other = dic[target]
            if other < i:
                idx[j] = (other, i)
            else:
                idx[j] = (i, other)
 
print(idx)
 
st = time.time()
POL = PolynomialRing(GF(q), 'a')
= POL.gen()
 
f1 = dat[idx[0][1]] * a ** idx[0][0+ dat[idx[0][0]] * a ** idx[0][1]
f2 = dat[idx[1][1]] * a ** idx[1][0+ dat[idx[1][0]] * a ** idx[1][1]
f3 = dat[idx[2][1]] * a ** idx[2][0+ dat[idx[2][0]] * a ** idx[2][1]
 
c1 = dat[idx[0][1]] + dat[idx[0][0]]
c2 = dat[idx[1][1]] + dat[idx[1][0]]
c3 = dat[idx[2][1]] + dat[idx[2][0]]
 
v1 = ((n1 % (q * q) - dat[idx[0][1]] * dat[idx[0][0]]) // q) % q
v2 = ((n2 % (q * q) - dat[idx[1][1]] * dat[idx[1][0]]) // q) % q
v3 = ((n3 % (q * q) - dat[idx[2][1]] * dat[idx[2][0]]) // q) % q
 
det = f1 * c2 * v3 + f2 * c3 * v1 + f3 * c1 * v2 - f1 * c3 * v2 - f2 * c1 * v3 - f3 * c2 * v1 
det = det // (a ** idx[0][0])
 
while det(1== GF(q)(0):
    det = det // (a - 1)
print("degree : ", det.degree())
a_cand = det.roots()
print(a_cand)
en = time.time()
 
print("took {} seconds".format(en - st))
 
for root, mult in a_cand:
    a_final = root 
    F1 = int(f1(a_final))
    F2 = int(f2(a_final))
    F3 = int(f3(a_final))
 
    C = ((v1 * c2 - v2 * c1) * inverse(F1 * c2 - F2 * c1, q)) % q
    D = ((v1 - F1 * C) * inverse(c1, q)) % q 
    assert (F1 * C + c1 * D - v1) % q == 0
    assert (F2 * C + c2 * D - v2) % q == 0
 
    x_final = (C + D) % q 
    b_final = (-* (int(a_final) - 1)) % q 
 
    dat_final = [x_final]
    for i in range(10000):
        dat_final.append((int(a_final) * dat_final[-1+ b_final) % q)
    
    ok = True 
    for i in range(4):
        pr1q2 = dat_final[idx[i][0]] * q + dat[idx[i][0]]
        pr2q2 = dat_final[idx[i][1]] * q + dat[idx[i][1]]
        if (pr1q2 * pr2q2) % (q * q) != targetsqq[i]:
            ok = False 
    
    if ok:
        for i in range(4):
            pr1q2 = dat_final[idx[i][0]] * q + dat[idx[i][0]]
            pr2q2 = dat_final[idx[i][1]] * q + dat[idx[i][1]]
            
            POL = PolynomialRing(Zmod(targets[i]), 'x')
            x = POL.gen()
            f = x * q * q + pr1q2
            f = f.monic()
            share3 = f.small_roots(X = q, beta = 0.49, epsilon = 0.05)[0]
            
            p = int(share3) * q * q + pr1q2
            conn.sendline(str(p).encode())
            conn.sendline(str(targets[i] // p).encode())
        
        print(conn.recvline())
cs

 

Comments

To solve the PoW efficiently, instead of doing the entire bytes_to_long you should just check the last 4 bytes of SHA256.

 

Sending random $a_1, x_1, b_1$ rather than $1, 1, 1$ is a bit better because with $1, 1, 1$, you can't really distinguish $3 \cdot 10 = 5 \cdot 6$ and stuff like that. With random values, it's should be possible to show that such collisions occur with a very low probability, with for example Schwartz-Zippel lemma. Proving this in mathematically precise fashion is left as an exercise for the reader. 

 

Before computing GCD or factorizing polynomials, it's helpful to reduce the degrees by dividing out some obvious parts.

 

By giving $a_2$ to the participants of Junior Division, we allow them to go straight into Coppersmith's Attack without setting up for the determinant or doing polynomial stuff. However, the only solver from Junior Division solved this challenge without Coppersmith's Attack. 

 

We note that to solve the problem, we do not need the first and third RNGs to be an LCG. Also, there's no need to let the participants select their values of $a_1, x_1, b_1$. However, letting the participants choose their $a_1, x_1, b_1$ opens up the possibility for other ideas that end up not working. The intended trap was to select $a_1, x_1, b_1$ so that the first LCG always output the same value. This does not help to solve the challenge to the best of author's knowledge. Letting the third RNG to not be an LCG forces the participant to know Coppersmith's Attack - but I did not really want to test this, since finding the $a_2$ part is already hard enough for WACon 2022 Quals. However, for Junior Division, I decided to award the knowledge of Coppersmith's Attack by giving them $a_2$. I think this was reasonable. 

 

It's also possible to solve LCG3 easier than the two methods described in the solution - this is due to the solvers in the Junior Division.

Since we have $$n = (LCG_{3, u} q^2 + LCG_{2, u} q + LCG_{1, u})(LCG_{3, v} q^2 + LCG_{2, v} q+ LCG_{1, v})$$ we can rewrite this as $$n' = \frac{n-(LCG_{2,u}q+LCG_{1,u})(LCG_{2,v}q+LCG_{1,v})}{q^2}$$ $$= LCG_{3,u}LCG_{3,v} q^2 +(LCG_{3,u}LCG_{2,v}+LCG_{3,v}LCG_{2,u})q + (LCG_{3,u}LCG_{1,v} + LCG_{3,v}LCG_{1,u}) $$ and now since this value can be calculated as we know $LCG_{1,u},LCG_{1,v},LCG_{2,u},LCG_{2,v},q$. 

 

Let $$\alpha = \left\lfloor \frac{LCG_{3,u}LCG_{1,v} + LCG_{3,v}LCG_{1,u}}{q} \right\rfloor$$ This is usually on the order of $q$, but by selecting $a_1 = x_1 = b_1 = 1$ we can force this value to be small, usually less than $10^4$.

 

We now have $$LCG_{3,u}LCG_{1,v} + LCG_{3,v} LCG_{1,u} \equiv n' \pmod{q}$$ and $$LCG_{3,u}LCG_{2,v} + LCG_{3,v}LCG_{2,u} \equiv \lfloor n' / q \rfloor - \alpha \pmod{q}$$ Therefore, if we know $\alpha$, we can solve this using a linear system easily. Since $\alpha$ is in a brute forcable range, we are done. 

 

This is a beautiful solution that I have overlooked, congratulations to the team! It's very cool that this solution uses the exact setup $a_1 = x_1 = b_1 = 1$ that I advised not to do in my second comment above. Of course, this means that they had to deal with a multiple possibilities for the index, i.e. the reason I advised not to use $a_1=x_1=b_1=1$. To see how they did it, consult their writeup in Korean. 

 

I gave participants four $n$ instead of three $n$ to make the knowledge of fast polynomial factorization or SageMath not required.

 

The description "2-out-of-3 secret sharing" comes from Coppersmith's Attack - note that if two share generators collaborate, they can find 2/3 of the primes and therefore can factorize $n$ using Coppersmith's Attack. I thought about making a challenge to check their understanding of why this challenge is about 2-out-of-3 secret sharing, but decided not to do it. Of course, only having one share generator does not allow you to factorize $n$, so this scheme fits the definition of "2-out-of-3 secret sharing". 

 

The flag was 

WACon{we_should_probably_use_a_better_RNG_than_LCG!!!_(and_hopefully_remove_the_trusted_third_party_:wink:)}

which notes that a trusted third party or TEE is required to check the primality of generated values and compute $n$. 

 

One of the solvers from General Division practically never studied cryptography in their life, but they are quite strong players in the Korean competitive programming scene. They actually solved all three cryptography challenges, which is a fascinating feat.

Of course, note that we didn't set challenges that require huge amount of prior knowledge in cryptography. 

'CTF' 카테고리의 다른 글

0CTF 2022 ezRSA+++  (0) 2022.09.19
0CTF 2022 TCTF NFT Market  (0) 2022.09.19
CODEGATE 2022 Preliminary : Prime-Generator  (0) 2022.02.28
CODEGATE 2022 Preliminary : Dark Arts  (0) 2022.02.28
SECCON CTF 2021 Writeups  (0) 2021.12.14

https://www.secmem.org/blog/2022/06/13/Caulk/

StarkWare 쪽 논문이라 일단 Cryptography. PS를 깊게 한 분들이라면 재밌게 읽을만 합니다.

https://www.math.toronto.edu/swastik/ECFFT1.pdf

 

논문 설명을 여기가 아니라 다른 커뮤니티에서 했는데, 캡쳐해서 가져왔습니다.

예시 구현체는 (제가 작성한 것이 아닙니다) https://solvable.group/posts/ecfft/ 에 있습니다.

 

https://www.secmem.org/blog/2022/05/15/KZG-ASVC/

1. 4월 7일 ~ 4월 28일에 훈련소를 다녀왔습니다. 많이 편하게 다녀온 것 같아서 다행입니다.

2. 이직을 했습니다. 해치랩스에서 Security Engineer로 근무하게 되었습니다. 공부 열심히 하려구요.

3. Ernest K. Ryu 교수님의 랩실에서 2저자로 함께 참가한 논문이 ICML에 Long Presentation으로 어셉되었습니다.

4. 5월 말에 친구들과 함께 MSI 보러 부산여행을 가기로 했습니다. 기대가 됩니다. 

 

5/31 추가

5. T1 5세트 밴픽 진짜 뭔지 모르겠어요. 아쉽습니다.
6. DiceGuesser 팀으로 데프콘 본선에 진출하기는 했는데 제가 한 건 없습니다. 변명하자면 MSI 여행과 예선이 아예 겹쳤고 MSI 결승 끝나고 오니까 제가 할 수 있는 부분이 다 끝나있더라구요 ㅠㅠ 그래도 이번에는 온사이트 가려고 하지 않을까 싶습니다. 경험은 해봐야죠..

7. UST 홀더였다가 0.996에 던졌는데 이번에 루나 에어드랍 달달하게 받아서 기분이 그나마 좋습니다 ㅋㅅㅋㅅㅋ 상장되자마자 던졌어야 했는데 ㄲㅂ

'미래 계획 및 근황' 카테고리의 다른 글

2022: Quick Retrospective  (6) 2022.12.28
Recent Updates  (4) 2022.08.12
6월 및 7월 초 정리  (4) 2021.07.15
4-5월 정리  (1) 2021.05.31
3월 정리  (0) 2021.04.02

https://www.secmem.org/blog/2022/02/17/RecentAttacksBlockchain/

https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf