매우 늦게 올린다. 결과는 6등으로, 예상보다는 매우 높았으나 여전히 만족스러운 결과는 아니었다. J를 풀지 못한것이 아쉬움.

작년의 팀과 멤버는 동일하다. rkm0959, junie, bjwj5505다. 내가 1년간 공부를 많이 한 건 맞지만, 정작 최근에는 CTF 참가 등으로 PS, CP에 집중하지 못해서 팀의 전체적인 실력이 강화된건지 퇴화된건지 좀 애매한 것 같다. 다른 팀원도 비슷하다. 일단 지금까지는 나쁘지 않게 하고 있는듯.

 

타임라인과 함께 간략한 설명을 붙이도록 하겠다. 모든 사람을 3인칭으로 명명하겠다.

  • 시작하자마자 문제 12개 모두 출력
  • 스코어보드 보니까 I가 0분컷으로 풀렸네? 진짜 쉽네?
  • rkm0959가 바로 컴퓨터 잡고 AC (5분)
  • 이때쯤 E도 퍼솔이 나왔고, 바로 rkm0959가 이어서 AC (8분)
  • bjwj5505는 이때 L을 읽고 있었고, junie는 앞쪽 문제를 읽는 중.
  • bjwj5505가 L을 구현했지만 WA 후 코드 프린트
  • rkm0959는 G를 보면서 수학 문제라고 생각을 했으나 매우 어려워보여서 대기중
  • 대신 K가 쉽다는 것을 확인하고, 풀이를 bjwj5505와 확인
  • rkm0959가 H의 풀이를 찾고, 정당성을 bjwj5505와 확인 
  • 그러다가 F가 쉬워보여서 rkm0959, junie가 해결 시도
  • bjwj5505가 L을 디버깅하고 있으며, rkm0959가 K를 짜기 시작
  • bjwj5505가 L을 고치고 AC (39분), rkm0959도 곧 K AC (46분)
  • bjwj5505, junie가 F의 풀이를 찾는동안 rkm0959 H 구현
  • F의 풀이를 찾고 AC (51분), H도 곧 AC (58분) - 1시간 6솔브 도달
  • 정확하게 기억은 안나지만 junie가 느린 J 풀이를 찾았음 (로그 2개)
  • 그러나 정확하게 풀이를 이해하고 있는 사람은 junie 혼자
  • bjwj5505, junie는 A의 해결에 집중. rkm0959는 B가 DP임을 확인
  • rkm0959가 D가 세그먼트 트리로 해결될 수 있는 문제임을 확인
  • A, B, D의 동시다발적 구현 + WA + 디버깅 파티 후 전부 AC (115, 133, 149분)
  • J를 고치려고 했고, "맞는" 풀이를 1분 전에 찾았으나 TLE. 똑떨....


'PS > 대회 후기' 카테고리의 다른 글

ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22
APIO 2020 Open Contest  (0) 2020.08.22
ACM-ICPC Seoul Regional 2019  (0) 2019.11.11
나는 코더다 2018 송년대회  (4) 2018.12.22

I participated in N1CTF as a member of Super Guesser. 

We solved all crypto problems, and it was a great collaboration of me and rbtree. 

The explanation will be very brief, because I don't have a lot of free time on my hands :( :(


VSS


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
#!/usr/bin/python3
import qrcode  # https://github.com/lincolnloop/python-qrcode
import random
import os
from PIL import Image
from flag import FLAG
 
 
def vss22_gen(img):
    m, n = img.size
    share1, share2 = Image.new("L", (2*m, 2*n)), Image.new("L", (2*m, 2*n))
    image_data = img.getdata()
    flipped_coins = [int(bit) for bit in bin(random.getrandbits(m*n))[2:].zfill(m*n)]
    for idx, pixel in enumerate(image_data):
        i, j = idx//n, idx % n
        color0 = 0 if flipped_coins[idx] else 255
        color1 = 255 if flipped_coins[idx] else 0
        if pixel:
            share1.putpixel((2*j, 2*i), color0)
            share1.putpixel((2*j, 2*i+1), color0)
            share1.putpixel((2*j+12*i), color1)
            share1.putpixel((2*j+12*i+1), color1)
 
            share2.putpixel((2*j, 2*i), color0)
            share2.putpixel((2*j, 2*i+1), color0)
            share2.putpixel((2*j+12*i), color1)
            share2.putpixel((2*j+12*i+1), color1)
        else:
            share1.putpixel((2*j, 2*i), color0)
            share1.putpixel((2*j, 2*i+1), color0)
            share1.putpixel((2*j+12*i), color1)
            share1.putpixel((2*j+12*i+1), color1)
 
            share2.putpixel((2*j, 2*i), color1)
            share2.putpixel((2*j, 2*i+1), color1)
            share2.putpixel((2*j+12*i), color0)
            share2.putpixel((2*j+12*i+1), color0)
    share1.save('share1.png')
    share2.save('share2.png')
 
 
def vss22_superposition():
    share1 = Image.open('share1.png')
    share2 = Image.open('share2.png')
    res = Image.new("L", share1.size, 255)
    share1_data = share1.getdata()
    share2_data = share2.getdata()
    res.putdata([p1 & p2 for p1, p2 in zip(share1_data, share2_data)])
    res.save('result.png')
 
 
def main():
    qr = qrcode.QRCode(
        version=1,
        error_correction=qrcode.constants.ERROR_CORRECT_L,
        box_size=12,
        border=4,
    )
    qr.add_data(FLAG)
    qr.make(fit=True)
    img = qr.make_image(fill_color="black", back_color="white")
    vss22_gen(img._img)
    img.save('res.png')
    vss22_superposition()
 
 
if __name__ == '__main__':
    main()
 
cs


The vulnerability lies in the use of "getrandbits" - it's implemented using MT19937. This PRNG is known to be predictable after 624 output values are known. Also, if you try to generate a QR code with a sample flag, we can see that the first few rows of the generated output are all white. With this fact, we can retrieve the first few thousand bits generated, and we can predict the following bits generated by MT19937. Therefore, we can recover the original QR code. This solution (and code itself) is due to rbtree. 


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
from mt import untemper
import random
from PIL import Image
 
img = Image.open('share2.png')
value = 0
for i in range(444):
    for j in range(444):
        value <<= 1
        value ^= 1 if 255 == img.getpixel((2 * j + 12 * i)) else 0
 
tmp = value
values = []
for i in range(444 * 444 // 32):
    values.append(tmp & 0xffffffff)
    tmp >>= 32
 
mt_state = tuple(list(map(untemper, values[:624])) + [0])
random.setstate((3, mt_state, None))
 
# for i in range(444 * 444 // 32):
#     assert values[i] == random.getrandbits(32)
 
random.setstate((3, mt_state, None))
 
real_value = 0
for i in range(444 * 444 // 32):
    real_value ^= random.getrandbits(32<< (32 * i)
 
value ^= real_value
arr = [int(bit) for bit in bin(value)[2:].zfill(444 * 444)]
 
res = Image.new("L", (444444))
 
for i in range(444):
    for j in range(444):
        res.putpixel((j, i), 0 if arr[i * 444 + j] else 255)
    
res.save("res.png")
cs


FlagBot


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
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
import base64
from secret import flag
 
RECEIVER_NUM = 7
 
def generate_safecurve():
    while True:
        p = random_prime(2 ^ 256-1False2 ^ 255)
        a = randint(-p, p)
        b = randint(-p, p)
 
        if 4*a^3 + 27*b^2 == 0:
            continue
 
        E = EllipticCurve(GF(p), [a, b])
 
        fac = list(factor(E.order()))
 
        # Prevent rho method
        if fac[-1][0< 1 << 80:
            continue
 
        # Prevent transfer
        for k in range(120):
            if (p ^ k - 1) % fac[-1][0== 0:
                break
        else:
            return E
 
class Sender:
    def __init__(self, curves, receivers):
        self.secret = randint(1 << 2541 << 255)
        self.curves = curves
        self.receivers = receivers
        self.shared_secrets = [None for _ in range(len(receivers))]
 
    def setup_connections(self):
        for idx, receiver in enumerate(self.receivers):
            curve = self.curves[idx]
            print(f"curves[{idx}] : {curve}")
            g = self.curves[idx].gens()[0]
            print(f"g[{idx}] = {g.xy()}")
            receiver.set_curve(curve, g)
            public = self.secret * g
            print(f"S_pub[{idx}] = {public.xy()}")
            yours = receiver.key_exchange(public)
            print(f"R_pub[{idx}] = {yours.xy()}")
            self.shared_secrets[idx] = yours * self.secret
 
    def send_secret(self):
        msg = b'Hi, here is your flag: ' + flag
        for idx, receiver in enumerate(self.receivers):
            px = self.shared_secrets[idx].xy()[0]
            _hash = sha256(long_to_bytes(px)).digest()
            key = _hash[:16]
            iv = _hash[16:]
            encrypted_msg = base64.b64encode(AES.new(key, AES.MODE_CBC, iv).encrypt(pad(msg, 16)))
            print(f"encrypted_msg[{idx}] = {encrypted_msg}")
            receiver.receive(encrypted_msg)
 
 
class Receiver:
    def __init__(self):
        self.secret = randint(1 << 2541 << 255)
        self.curve = None
        self.g = None
        self.shared_secret = None
 
    def set_curve(self, curve, g):
        self.curve = curve
        self.g = g
 
    def key_exchange(self, yours):
        self.shared_secret = yours * self.secret
        return self.g * self.secret
 
    def receive(self, encrypted_msg):
        px = self.shared_secret.xy()[0]
        _hash = sha256(long_to_bytes(px)).digest()
        key = _hash[:16]
        iv = _hash[16:]
        msg = AES.new(key, AES.MODE_CBC, iv).decrypt(base64.b64decode(encrypted_msg))
        msg = unpad(msg, 16)
        assert msg.startswith(b'Hi, here is your flag: ')
 
 
receivers = [Receiver() for _ in range(RECEIVER_NUM)]
curves = [generate_safecurve() for _ in range(RECEIVER_NUM)]
 
= Sender(curves, receivers)
A.setup_connections()
A.send_secret()
 
cs


This problem was solved by me, so I can give you a brief look inside my brain.

  • You can't really do anything with AES-CBC in this challenge
  • You can't really do anything with SHA256 anywhere
  • That means that we have to break the DH style shared secret generation
  • The secret key is reused every time, so that's the vulnerability
  • The curve generation only checks the existence of large primes, so small primes can exist

At this point, the solution was straightforward. For each small prime $p$ that divides the order of the elliptic curve used, we can find the value of the secret key $\pmod{p}$ by using Pohlig-Hellman approach. Combining these with CRT, we can recover $d$ since it is at most $2^{255}$. 

Since we do need to deal with primes of size around $10^{12}$, Baby-Step-Giant-Step is required. Just use Sage.


The below code finds all the shared secrets. The remaining parts of the problem are straightforward.


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
cur_mod = 1
cur_val = 0
 
for i in range(07):
    a = S[i][0]
    b = S[i][1]
    p = S[i][2]
    E = EllipticCurve(GF(p), [a, b])
    Ord = E.order()
    L = list(factor(Ord))
    GG = E(g[i])
    SS = E(S_pub[i])
    for pp, dd in L:
        if pp <= 10 ** 12 and dd == 1:
            Gp = (Ord // pp) * GG
            Sp = (Ord // pp) * SS
            tt = discrete_log(Sp, Gp, operation='+')
            cur_val = crt(cur_val, tt, cur_mod, pp)
            cur_mod = (cur_mod * pp) // gcd(pp, cur_mod)
    print("Done ", i)
    
print("[+] Secret: ", cur_val)
 
for i in range(07):
    a = S[i][0]
    b = S[i][1]
    p = S[i][2]
    E = EllipticCurve(GF(p), [a, b])
    RR = E(R_pub[i])
    RES = RR * cur_val
    print(RES.xy()[0])
cs


curve


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
#!/usr/bin/env sage
 
import signal, hashlib, string, random, os 
 
os.chdir(os.path.dirname(os.path.abspath(__file__)))
FLAG = open("./flag.txt"'r').read()
ROUNDS = 30
 
def PoW():
  s = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
  h = hashlib.sha256(s.encode()).hexdigest()
  prefix = s[:16]
  print("sha256(%s+XXXX) == %s" % (prefix, h))
  c = input("Give me XXXX: ")
  if hashlib.sha256((prefix + c).encode()).hexdigest() == h:
    return True 
  return False
 
def chall():
  p = ZZ(input("P: "))  # of course we are using sage >= 9
  a = ZZ(input("A: "))
  b = ZZ(input("B: "))
 
  if not is_prime(p) or p.nbits() < 512:
    print("No bad parameters.")
    return
 
  E = EllipticCurve(GF(p), [a, b])
  if E.is_supersingular():
    print("No this is not good enough.")
    return
 
  q = E.order()
  x1 = ZZ(input("X1: "))
  y1 = ZZ(input("Y1: "))
  x2 = ZZ(input("X2: "))
  y2 = ZZ(input("Y2: "))
  G1 = E((x1, y1))
  G2 = E((x2, y2))
 
  for _ in range(ROUNDS):
    a0 = randint(1, q - 1)
    a1 = randint(1, q - 1)
 
    c = -1
    while c == -1 or c == a0 * a1:
      c = randint(1, q - 1)
 
    g0, g1 = G1 * a0, G2 * a1 
    c0, c1 = G1 * (a0 * a1), G1 * c
    b = randint(01)
 
    if b == 0:
      print(g0, g1, c0)
    else:
      print(g0, g1, c1)
 
    choice = ZZ(input("Choice: "))
    if choice != b:
      print("Wrong choice.")
      return
 
  print(f"Thank you! Here's your reward: {FLAG}")
  return 
 
if __name__ == '__main__':
  if not PoW():
    print("Invalid PoW.")
    exit()
  signal.alarm(90)
 
  try:
    chall()
  except:
    print("oof...")
    exit()
 
 
cs


We struggled greatly on this challenge, despite finding the solution quite immediately. Here's the process.

  • $E$ is a large elliptic curve over a prime field, not supersingular
  • We select two points $G_1, G_2$ on the curve, and play a sort of Decisional Diffie-Hellman game.
  • Let's just fix $G = G_1 = G_2$ and see what we can do!
  • If the order of $G$ is small, say $t$ - we can recover $a_0, a_1 \pmod{t}$ easily. 
  • Therefore, we can directly calculate $a_0a_1G$ as well!
  • Check if this is equal to the third point given. If so, check $b=0$ and otherwise check $b=1$.
Now we do some analysis. 
  • If $b=0$ was chosen, this will give the correct answer with probability 1
  • If $b=1$ was chosen, we fail if $c \equiv a_0 a_1 \pmod{t}$, so we succeed with probability $1-1/t$
  • We do $30$ rounds, so $t$ shouldn't be too small (we want, say, $t> 50$)
  • Obviously we do need to solve the discrete logarithm on a group of order $t$, so we want small $t$

This leads to the following goal.

  • Find an elliptic curve that satisfies the server's desired conditions, with the order of the curve having a prime between $50$ and $400$

I think I took about 5 minutes until here, but the journey towards the flag for several reasons.

  • First, my initial code used random $p, a, b$, generate the curve, find the order, then check for small primes.
  • Seems good right? However, I tried to find $G$ using E.gens()[0] * (Order // small_prime)
  • This obviously takes infinite time, and my computer was on the verge of dying because of it
  • I realized the problem and replaced it by generating any point with Tonelli-Shanks and multiplying it by Order // small_prime

So I thought I was done here. After sending the parameters, I realized that I was not done here. Why?

  • The server calculates the order of the elliptic curve as well
  • While order calculation is done in polynomial time, it's still slow with 512 bit curve parameters
  • Therefore, the server times out, and I can't solve the problem

So I thought I was done here, in a different meaning. After solving the remaining challs, I tried the following.

  • Simply try the curves of the form $y^2 = x^3 + b$.

This worked, as the order calculation was done much faster. The challenge was solved.

The parameter finding and solution finding was done by me, and the programming was done by rbtree.


I learned a lot from solving this problem :) I'm still inexperienced, lots of studying to do... 


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
pr = []
for x in range(50200):
    if x in Primes():
        pr.append(x)
while True:
    p = random_prime(2 ** 512False2 ** 511)
    if p % 3 == 2## in this case, y^2 = x^3 + b is guaranteed to be supersingular
        continue
    d = randint(1, p-1)
    E = EllipticCurve(GF(p), [0, d])
    if E.is_supersingular() == True:
        continue
    print(p)
    L = E.order()
    for cc in pr:
        if L % cc == 0:
            print(p, d, cc, L)
            break
 
## find any point on the elliptic curve
for u in range(1100):
    goal = (u ** 3 + a * u + b) % p
    if pow(goal, (p-1// 2, p) == 1:
        v = tonelli(goal, p) ## sqrt, so you can directly use sage
        G = E(u, v)
        break
 
## hope that G is nonzero
= G * (Ord // pr)
G1 = G
G2 = G
 
## this ends parameter generation
cs


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
## by rbtree
 
from pwn import *
import string
import itertools
 
conn = remote('47.242.140.57'9998)
conn.settimeout(None)
 
# PoW
 
challenge = conn.recvline().strip()
print(challenge)
prefix = challenge[7:7+16]
= challenge.split()[-1]
charset = (string.ascii_letters + string.digits).encode()
for suffix in itertools.product(charset, repeat=4):
    if hashlib.sha256(prefix+bytes(suffix)).hexdigest() == h.decode():
        conn.sendlineafter(b'Give me XXXX: ', bytes(suffix))
        break
print("PoW Done")
 
= 11572562087281212077294341316763410822093276559896892655806738743748493229131824454041157658617469079306138012813995393545636120267619633658087398895787057 
= 0
= 587626359248673832094266933340735482471140319598254235432650868938827936103013631493279303809976008538035914917596142929543705518144408460458007005924570
pr = 97
order = 11572562087281212077294341316763410822093276559896892655806738743748493229131918957581964494921602014693617723606720177358361724985583223555103419211299648
 
Gs = [] ## bunch of points (G, 2G, ... 97G)
print(len(Gs))
 
def get_points():
    points_s = conn.recvline().decode().strip()[1:-1].split(') (')
    points = []
    for point_s in points_s:
        point = tuple(int(v.strip()) for v in point_s.split(':')[:2])
        points.append(point)
    return points
 
conn.sendlineafter(b'P: 'str(p))
conn.sendlineafter(b'A: 'str(a))
conn.sendlineafter(b'B: 'str(b))
conn.sendlineafter(b'X1: 'str(Gs[0][0]))
conn.sendlineafter(b'Y1: 'str(Gs[0][1]))
conn.sendlineafter(b'X2: 'str(Gs[0][0]))
conn.sendlineafter(b'Y2: 'str(Gs[0][1]))
 
print("Parameter Sent")
 
for _ in range(30):
    points = get_points()
 
    for i in range(96):
        if points[0== Gs[i]:
            a = i + 1
            break
 
    for i in range(96):
        if points[1== Gs[i]:
            b = i + 1
            break
 
    to_send = 0 if Gs[(a * b % 97- 1== points[2else 1
    conn.sendlineafter(b'Choice: 'str(to_send))
 
conn.interactive()
cs


BabyProof


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
from hashlib import sha256
 
from Crypto.Util.number import getRandomRange
from Crypto.PublicKey import DSA
 
from secret import proof_of_work, flag
 
 
= int.from_bytes(flag, 'big')
assert x.bit_length() == 247
 
 
def baby_proof():
    key = DSA.generate(3072)  # It takes time to generate, plz be patient...
    p, q, g = key.domain()
    y = pow(g, x, p)
 
    v = getRandomRange(1, x)
    t = pow(g, v, p)
 
    gyt = b"".join(
        map(
            lambda x: int.to_bytes(len(str(x)), 4'big'+ str(x).encode(),
            (g, y, t)
        ))
    c = int.from_bytes(sha256(gyt).digest(), 'big')
    r = (v - c*x) % q
 
    print("I want to prove to you that I am in the knowledge of the discrete "
          "logarithm x that satisfies g^x = y modulo p, with the order of g "
          "modulo p being q.")
    print("However, I don't want to leak any information about x.")
    print("So, I use a non-interactive zero-knowledge proof for my purpose.")
    print("=================================================================")
    print("Here is my proof: ")
    print("Firstly, I choose a random (secret) v and compute t = g^v in Zq.")
    print("Secondly, I compute c = SHA256(g, y, t).")
    print("Then, I compute r = v - cx modulo q.")
    print("Finally, I will send you my proof (t, r).")
    print("You can check it by determining whether t == g^r * y^c or not.")
    print("Since there's negligible probability that I could forge the value "
          "r, you should believe that I really have knowledge of x.")
    print(g, y, p, q, t, r, sep="\n")
 
 
if __name__ == "__main__":
    if proof_of_work():
        baby_proof()
cs


The key here is that $x$ is quite small compared to $2^{256}$, and $v$ is selected in $[1, x]$. 

Given the printed parameters, we can directly obtain the value of $c$ as well. We see that $$ cx \equiv v - r \pmod{q}, \quad 1 \le v \le x $$ Since $x$'s bit length is $247$, we get $1 \le v \le 2^{247}$ and can write something like $$ cx \pmod{q} \approx -r + 2^{246} \pmod{q} $$ This is an instance of Hidden Number Problem, so just gather a lot of these information and solve it.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
= 60 ## get 60 instances
= Matrix(ZZ, d+1, d+1)
for i in range(0, d):
    M[0, i] = cs[i]
M[0, d] = 1
for i in range(0, d):
    M[i+1, i] = qs[i]
 
Target = [0* (d+1)
for i in range(0, d):
    Target[i] = (2 ** 246- rs[i]
Target[d] = (2 ** 246)
 
= M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
= TT[d]
print(x)
print(bytes.fromhex(hex(x)[2:]))
cs


easyRSA?


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
from Crypto.Util.number import *
import numpy as np
 
mark = 3**66
 
def get_random_prime():
    total = 0
    for i in range(5):
        total += mark*** getRandomNBitInteger(32)
    fac = str(factor(total)).split(" * ")
    return int(fac[-1])
 
def get_B(size):
    x = np.random.normal(016, size)
    return np.rint(x)
 
= get_random_prime()
= get_random_prime()
= p * q
= 127
 
flag = b"N1CTF{************************************}"
secret = np.array(list(flag))
 
upper = 152989197224467
= np.random.randint(281474976710655, size=(e, 43))
= get_B(size=e).astype(np.int64)
linear = (A.dot(secret) + B) % upper
 
result = []
for l in linear:
    result.append(pow(l, e, N))
 
print(result)
print(N)
np.save("A.npy", A)
 
cs


Looking at the problem, we see that we need to do the following

  • Factorize $N$ using the vulnerable random prime generator, and recover the array "linear"
  • Solve the instance of LWE by using the fact that secret vector (the flag) is small as well

We first focus on the first part. I actually thought about coppersmith method, but I couldn't get it to work.

I already have an experience in wasting time with coppersmith approach, (sharsable) so I stopped attempting.


rbtree noted that there is a polynomial $f$ with small coefficients, degree 8, and $f(3^{66}) \equiv 0 \pmod{N}$.

This is because for each $p, q$, there's a degree 4 polynomial with small coefficients that vanishes at $3^{66}$ modulo that prime.

If we multiply the two degree 4 polynomials, we arrive at the described polynomial of degree 8.

He then suggested using a lattice to find this polynomial. This was an excellent idea!


Since we want a small-coefficient-linear-combination of $3^{66 \cdot 0}, 3^{66 \cdot 1}, \cdots , 3^{66 \cdot 8}$ that vanishes to zero, we must use scaling, as I did in sharsable. Check the code for technical details. As I do usually, I used Babai's closest vector algorithm. We can expect $f$ to be factorized into two polynomials of degree 4. By calculating each polynomial at $3^{66}$ and taking GCDs, we can retrieve $p, q$. This completes Part 1. 


For Part 2, we need to solve the LWE problem. This is hard in general, but we know that the secret vector is small as well. 

Of course, LWE problem can be modeled as CVP problem, and we use the "secret vector is small" fact here as well.


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
## Step 1 : Factorization of N
rat = 2 ** 1000 
## scaling : super large to force zero in the first column
 
for i in range(09):
    M[i, 0= (3 ** (66 * i)) * rat
M[90= n * rat
for i in range(09):
    M[i, i+1= 1
 
Target = [0* 10
for i in range(110):
    Target[i] = (2 ** 64)
 
= M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
P.<x> = PolynomialRing(ZZ)
= 0
for i in range(110):
    f = f + TT[i] * x^(i-1)
print(f.factor())
## (2187594805*x^4 + 2330453070*x^3 + 2454571743*x^2 + 2172951063*x + 3997404950) 
## (3053645990*x^4 + 3025986779*x^3 + 2956649421*x^2 + 3181401791*x + 4085160459)
 
cc = 0
cc += 2187594805 * (3 ** (66 * 4))
cc += 2330453070 * (3 ** (66 * 3))
cc += 2454571743 * (3 ** (66 * 2))
cc += 2172951063 * (3 ** (66 * 1))
cc += 3997404950 * (3 ** (66 * 0))
 
= gcd(cc, n)
print(p)
print(n // p)
print(n % p)
 
## Step 2 : housekeeping stuff
## res in res.txt, A in A.npy
= 122286683590821384708927559261006610931573935494533014267913695701452160518376584698853935842772049170451497
= 268599801432887942388349567231788231269064717981088022136662922349190872076740737541006100017108181256486533
= 127
= p * q
phi = (p-1* (q-1)
= inverse(e, phi)
 
cv = []
for x in res:
    cv.append(pow(x, d, n))
 
print(cv)
 
np.set_printoptions(threshold=sys.maxsize)
= np.load("A.npy")
= np.ndarray.tolist(A)
print(A)
 
## Step 3 : LWE with CVP
mod = 152989197224467
 
sel = 15 ## sel can be large as 127, but that's too slow
= Matrix(ZZ, sel + 43, sel + 43)
for i in range(043):
    for j in range(0, sel):
        M[i, j] = A[j][i]
    M[i, sel + i] = 1
for i in range(4343+sel):
    M[i, i-43= mod
Target = [0* (sel + 43)
for i in range(0, sel):
    Target[i] = cv[i] - 8
for i in range(sel, sel + 43):
    Target[i] = 80 ## printable
 
Target = vector(Target)
= M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
print(TT)
 
res = ""
for i in range(sel, sel+43):
    res += chr(TT[i])
 
print(res)
 
cs


'수학 > 암호론 및 CTF' 카테고리의 다른 글

N1CTF 2020 Crypto Write-Ups  (0) 2020.10.18
Leftover Hash Lemma and its Applications  (0) 2020.10.18
SECCON 2020 OnlineCTF Crypto Write-Ups  (0) 2020.10.11
CryptoHack All Solve  (3) 2020.09.30
TokyoWesternCTF 2020 Crypto Write-Ups  (0) 2020.09.20
DownUnderCTF Crypto Write-Ups  (2) 2020.09.19

main.pdf


'수학 > 암호론 및 CTF' 카테고리의 다른 글

N1CTF 2020 Crypto Write-Ups  (0) 2020.10.18
Leftover Hash Lemma and its Applications  (0) 2020.10.18
SECCON 2020 OnlineCTF Crypto Write-Ups  (0) 2020.10.11
CryptoHack All Solve  (3) 2020.09.30
TokyoWesternCTF 2020 Crypto Write-Ups  (0) 2020.09.20
DownUnderCTF Crypto Write-Ups  (2) 2020.09.19

I participated in SECCON 2020 Online CTF as a member of HangulSarang. We got 1st place :)

Hangul Day is also my birthday, so that's something I guess :D


The competition collided with ACM-ICPC quals, so I had to start solving at like 7PM. (4 hours late)


During that 4 hours, my teammate solved "This is RSA", which is solved using that each byte can be only 0x30 to 0x39. After that, we can compute solutions in $\pmod{2^k}$ and move upwards using recursion. It was the easiest crypto problem in this CTF, (and the solver wasn't me) so I think I don't need to explain further. The other four crypto problems were quite good, challenging, and very enjoyable, so I will describe my thought process as well. Huge thanks to the problem authors for creating these challenges. :D


koharu


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
while True:
    p = random_prime(1<<64)
    if is_prime((p+1// 2):
        break
 
with open("flag.txt""rb"as f:
    flag = f.read()
flag = int.from_bytes(flag, "big")
 
 
PR.<x> = PolynomialRing(GF(p))
while True:
    P = PR.random_element(degree=64)
    if P.is_irreducible():
        break
 
while True:
    Q = PR.random_element(degree=64)
    if Q.is_irreducible():
        break
 
NP = p**P.degree()
NQ = p**Q.degree()
 
while True:
    R = PR.random_element(degree=64)
    if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
        break
 
PQ = P*Q
= []
while flag:
    S = PR.random_element(degree=64)
    if flag & 1:
        c.append((S * S) % PQ)
    else:
        c.append((S * S * R) % PQ)
    flag = flag >> 1
 
print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)
 
 
cs


The code screams "quadratic residue", and it's similar to bitcrypto in InterKosenCTF. (write-up in this blog)

The only difference is that we are not using large primes, but polynomials in $GF(p)[x]$. This is already weak. 

The reason is that we can easily factorize polynomials in $GF(p)$. We can ask Sage to do it for us :)

Now we can determine whether a given polynomial is a quadratic residue or not. Combine this to get the flag.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
= 4832823609987476353
F.<x> = PolynomialRing(GF(p))
PQ = 2475361839038406994*x^128 + 1816580044636445865*x^127 + 771106714052997910*x^126 + 2532248969060743840*x^125 + 157159147928168793*x^124 + 1165294508775017303*x^123 + 54498477947855453*x^122 + 564670281176250610*x^121 + 4686383084102262935*x^120 + 4798143559496813901*x^119 + 2373759188753852032*x^118 + 3458843219210551923*x^117 + 3389173528515223367*x^116 + 3175114023644661971*x^115 + 2668820643276713526*x^114 + 1644657084961816584*x^113 + 1949973045428555331*x^112 + 2314884799372359978*x^111 + 1614909032209480656*x^110 + 3706101120120959039*x^109 + 1443476119293487220*x^108 + 507539962924420368*x^107 + 2851578707595377440*x^106 + 2660707099322090529*x^105 + 2275120831055073492*x^104 + 4642644673121099806*x^103 + 780741129747777966*x^102 + 3824963851609159359*x^101 + 1445016816241934269*x^100 + 4706494165496469049*x^99 + 91460120231848540*x^98 + 2033361932245472629*x^97 + 4657205830657809352*x^96 + 627579987075662316*x^95 + 2638155163726745709*x^94 + 773248040814209977*x^93 + 4426134463977473378*x^92 + 1748835523159978170*x^91 + 2545886874835388035*x^90 + 4318027045196127783*x^89 + 529092995613843935*x^88 + 37621695756851259*x^87 + 724317479549357114*x^86 + 235872728824864204*x^85 + 1409136599403563059*x^84 + 984842291673572708*x^83 + 1000642979551429427*x^82 + 2599952022893048437*x^81 + 33489199855748196*x^80 + 2138571356326295553*x^79 + 357904099457660261*x^78 + 1388605866466399741*x^77 + 2123614714168365349*x^76 + 1296407111118101425*x^75 + 3175149128196009486*x^74 + 4407671566428651830*x^73 + 3653949472018283742*x^72 + 2150666969917189331*x^71 + 2425834809198809729*x^70 + 202017664024051124*x^69 + 4656859267960293209*x^68 + 95544718007904685*x^67 + 551963924883187932*x^66 + 1220133766833256737*x^65 + 418789913385574936*x^64 + 3140425594489130574*x^63 + 653426727346469624*x^62 + 2168508737790275670*x^61 + 1350675684196344669*x^60 + 86970043713584944*x^59 + 3125122442296761190*x^58 + 1691082709013935740*x^57 + 14954357710735056*x^56 + 1951640599446313225*x^55 + 3057759244385615044*x^54 + 2842299299534580663*x^53 + 60118912044101305*x^52 + 3791459205438092561*x^51 + 3961025931327708139*x^50 + 3352223936735193809*x^49 + 458087980170556413*x^48 + 303065746752057039*x^47 + 270269323703788403*x^46 + 3435561048914221019*x^45 + 244980776425782882*x^44 + 1756735569264346021*x^43 + 1049402079460555244*x^42 + 1181023304135761892*x^41 + 2480814159047994100*x^40 + 3359295278584507081*x^39 + 1031815312165038169*x^38 + 2284789340145013050*x^37 + 2507227047920435897*x^36 + 4212274843760760739*x^35 + 1874163516348469998*x^34 + 4184876619139253979*x^33 + 2454055493008310058*x^32 + 4810631595605704078*x^31 + 2705618732956794205*x^30 + 4588422028499215564*x^29 + 1362947071518584749*x^28 + 200625668549982104*x^27 + 4162225127389871946*x^26 + 3671964574429446847*x^25 + 497776717675475749*x^24 + 3171362364421276926*x^23 + 4040585504650270495*x^22 + 55143980688943936*x^21 + 1680279432641096886*x^20 + 1141249890787830167*x^19 + 1632171956841566025*x^18 + 4489792289887403690*x^17 + 72863318133800422*x^16 + 3512973315964270180*x^15 + 1880837549990432714*x^14 + 629108155937185931*x^13 + 605563550674482475*x^12 + 3125052390516629852*x^11 + 3434353753938817079*x^10 + 2199180089161294937*x^9 + 4128993677150612079*x^8 + 875038461592559534*x^7 + 1344699457303227348*x^6 + 3605318452000064928*x^5 + 1825112182884559504*x^4 + 4214849563830404245*x^3 + 3018789469914511583*x^2 + 4256870332540451928*+ 3478109193918270445
= 10529800129354981*x^64 + 4658846300069202283*x^63 + 1343603688498785880*x^62 + 77535778799313918*x^61 + 3909004297055292936*x^60 + 1574062357470841720*x^59 + 2255026177942473610*x^58 + 2913895405335010190*x^57 + 910153010204378491*x^56 + 4823161627331431259*x^55 + 4314926186108070132*x^54 + 3776194104903441585*x^53 + 4218241384907734159*x^52 + 2928099962473177675*x^51 + 3620663369166129209*x^50 + 4671199329340054093*x^49 + 2953252709684913819*x^48 + 1470028746745533363*x^47 + 393509208258687360*x^46 + 2631641671658679748*x^45 + 4823463900549231672*x^44 + 22025139085889956*x^43 + 3905072220448754367*x^42 + 3525611426409694274*x^41 + 1087703571442464513*x^40 + 983613039355879671*x^39 + 2292836760450398296*x^38 + 2429042383184252432*x^37 + 4241866215562144008*x^36 + 3567456235250802214*x^35 + 289826756486726727*x^34 + 3070079221437908111*x^33 + 3164478508626375897*x^32 + 4028195041942471423*x^31 + 1611744044712776226*x^30 + 682031605725048858*x^29 + 2334009162012075842*x^28 + 1056698946696323305*x^27 + 1193918408929283326*x^26 + 1546583097398597126*x^25 + 632624061599387394*x^24 + 3924194912006864689*x^23 + 836241738980292724*x^22 + 2019639656826418643*x^21 + 646182266409329495*x^20 + 3568811299250961381*x^19 + 4024124722170180214*x^18 + 2765626713849083593*x^17 + 830125243533734584*x^16 + 3773807917205041413*x^15 + 4579071273569219071*x^14 + 4169012455774239610*x^13 + 2779202281389813792*x^12 + 1668767138196611027*x^11 + 3668902156196312613*x^10 + 2118966174503976203*x^9 + 2876683474352545557*x^8 + 4749450906737437136*x^7 + 2048549559963146669*x^6 + 2337906091414592304*x^5 + 3234395871197583532*x^4 + 624006023034932764*x^3 + 1020142386943254010*x^2 + 4346889740151908150*+ 2337193413394346074
= []
= (x^64 + 2705838326093066801*x^63 + 1861763125820805142*x^62 + 1919270169024731361*x^61 + 728192979251886197*x^60 + 3703504742135431297*x^59 + 608310330267197202*x^58 + 677522369546315305*x^57 + 45111914222503868*x^56 + 3231090245423531905*x^55 + 4439626063971680541*x^54 + 264779255326565930*x^53 + 943573327092647824*x^52 + 3642035360519473519*x^51 + 4624797912514728904*x^50 + 815168423497123035*x^49 + 2058290770523809000*x^48 + 4368972367338353614*x^47 + 1102710837251449034*x^46 + 1838631000574578462*x^45 + 1550208773716319692*x^44 + 4479635398032603580*x^43 + 2547505501081696879*x^42 + 4733577241261296757*x^41 + 1459044726889718801*x^40 + 4736670792998507780*x^39 + 3481084975759672453*x^38 + 4491590348438475003*x^37 + 4286960290474469508*x^36 + 2519824328645383346*x^35 + 722570560813334776*x^34 + 3203376079187925593*x^33 + 2137713042365333594*x^32 + 2529680584881125743*x^31 + 881878615185959251*x^30 + 2648895700342509353*x^29 + 3093613170934869890*x^28 + 1839149659686122740*x^27 + 901352037355979824*x^26 + 3079388294575162468*x^25 + 4316897640303347156*x^24 + 3768144827267250554*x^23 + 1585476600468626452*x^22 + 2408180731465025131*x^21 + 2754322334879778466*x^20 + 1965864600205111832*x^19 + 3016989393277154199*x^18 + 993850365653028982*x^17 + 1661221355151932055*x^16 + 2141520480611688809*x^15 + 636670112723307258*x^14 + 1200822100799196786*x^13 + 2223563845526420680*x^12 + 3134534498746508642*x^11 + 1820327632682349699*x^10 + 4628418849122802568*x^9 + 3731553570235638636*x^8 + 1636534607043587796*x^7 + 1007966122754856335*x^6 + 3571611463638839115*x^5 + 4733247188903796455*x^4 + 3512981852602786831*x^3 + 1560667366459827025*x^2 + 1113839338158290233*+ 4011393002849553527)
= (x^64 + 2776622066009961678*x^63 + 1020248994272362724*x^62 + 1812889731002797017*x^61 + 3946133096396475132*x^60 + 1064362775780462120*x^59 + 4267166204741846229*x^58 + 4461168980925876722*x^57 + 3701193932757315736*x^56 + 4004259984657770019*x^55 + 2566923830139634808*x^54 + 2958380329303059106*x^53 + 4642913814072279374*x^52 + 713990683265973444*x^51 + 2282781718594249732*x^50 + 1691679008052617295*x^49 + 4723620313305465430*x^48 + 4052669689859242595*x^47 + 4607757741831461143*x^46 + 3048879536065529044*x^45 + 2012013680568798151*x^44 + 2125237235418450484*x^43 + 2622384625077739224*x^42 + 710661875195936255*x^41 + 375897308743404378*x^40 + 3253268532586707019*x^39 + 3759767504239334681*x^38 + 2945194932005180334*x^37 + 1316716161821289054*x^36 + 2210075866459201344*x^35 + 3421886933443572088*x^34 + 2124192011313760002*x^33 + 3183242335232871177*x^32 + 4722704310996441203*x^31 + 1640862527872462873*x^30 + 292078618156889354*x^29 + 3970255331239899451*x^28 + 290424178543927660*x^27 + 3979382049081683506*x^26 + 3341058157535181184*x^25 + 1891458780676141416*x^24 + 4585931142037966308*x^23 + 2621586816910493860*x^22 + 4526407296014662985*x^21 + 3345825075365423903*x^20 + 433595205227433076*x^19 + 3510443356995660854*x^18 + 1469161865274264871*x^17 + 1968552305256496645*x^16 + 1902262417167822976*x^15 + 3211385257470450715*x^14 + 259183745852362935*x^13 + 1368548986536267534*x^12 + 3726482530039832086*x^11 + 1196244075361051439*x^10 + 3346319329141804238*x^9 + 2362535635162047034*x^8 + 2131037938034625812*x^7 + 3970887869581347678*x^6 + 4428522899784697485*x^5 + 2482987898184812388*x^4 + 3180131420672415636*x^3 + 4690602932003451909*x^2 + 2572790493146370264*+ 802891458181310745)
cv = (p ** 64 - 1// 2
fin = 0
add = 1
for ply in c:
    Pv = power_mod(ply, cv, P)
    Qv = power_mod(ply, cv, Q)
    if Pv == 1 and Qv == 1:
        fin += add
    add = add * 2
print(fin) ## long to bytes here
cs


urara


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
from flag import flag
 
= random_prime(1 << 1024)
= random_prime(1 << 1024)
= p * q
 
print("n =", n)
 
# ---
 
= int.from_bytes(flag, "big")
= randint(0, n-1)
 
= randint(0, n-1)
= (y^2 - (x^3 + a*x)) % n
 
EC = EllipticCurve(Zmod(n), [a, b])
 
= EC((x, y))
= 2 * P
 
print("a, b =", [a, b])
print("Q =", Q.xy())
 
# ---
 
= int.from_bytes(flag, "big")
= randint(0, n-1)
 
= power_mod(m + t, 65537, n)
print("t =", t)
print("c =", c)
 
cs


Very concise problem. We are given $t, e, n$ and $(m+t)^e \pmod{n}$, and a point is double the point with [$x$-coordinate equal to $m$] [which lies on the elliptic curve $y^2 = x^3 + ax + b$]. I broke that sentence up into pieces because it's pretty long and confusing. So anyways, doing actually elliptic curve stuff seems nearly impossible with the lack of hints we have, and we have a huge hint in $(m+t)^e \pmod{n}$. If we have another polynomial equation about $m$ in $\mathbb{Z}_n[x]$, we can solve this problem using polynomial GCD. (Franklin-Reiter related message attack, like padrsa in InterKosen CTF) Of course, we do have another polynomial equation! Directly using the doubling formula, we have $$ (3m^2 + a)^2 - (2m + Q_x)(4(m^3 + am+b)) \equiv 0 \pmod{n}$$ which is the type of equation we want. Write polynomial GCD, and we can easily find $m$. Again, note that if we encounter a problem while performing standard Euclidean Algorithm, it's because the leading coefficient has a non-trivial GCD with $n$. In this case, we can just factorize $n$ to solve the problem. I was stuck in sharsable for so long before solving this one, so I got some energy from it :D 


For the implementation of polynomial GCD, refer to the write-up of the problem padrsa


1
2
3
4
5
6
= Zmod(n)
P.<x> = PolynomialRing(K, implementation='NTL')
= (3 * x^2 + a)^2 - (2*+ Qx) *(4*(x^3 + a*x+b))
= power_mod(x + t, 65537, f) - c
print(GCD(f, g, n))
## the remaining details are trivial
cs


sharsable


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
from Crypto.Util.number import getPrime, GCD
from flag import FLAG
import random
 
def egcd(a, b):
    r0, r1 = a, b
    s0, s1 = 10
    t0, t1 = 01
    while r1 > 0:
        q = r0 // r1
        r0, r1 = r1, r0 % r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1
    return s0, t0
 
def generateKey():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p-1)*(q-1)
 
    while True:
        d1 = getPrime(int(n.bit_length()*0.16))
        e1 = random.randint(1, phi)
        ed1 = e1 * d1 % phi
 
        d2 = getPrime(int(n.bit_length()*0.16))
        e2, k = egcd(d2, phi)
        e2 = e2 * (phi + 1 - ed1) % phi
        ed2 = e2 * d2 % phi
 
        if GCD(e1, e2) > 10:
            break
 
    assert((ed1 + ed2) % phi == 1)
 
    return (n, (e1, d1), (e2, d2))
 
n, A, B = generateKey()
= int.from_bytes(FLAG, 'big')
C1 = pow(M, A[0], n)
C2 = pow(M, B[0], n)
assert(pow(C1, A[1], n) * pow(C2, B[1], n) % n == M)
 
import json
print(json.dumps({
    "n": n,
    "A": (A[0], C1),
    "B": (B[0], C2),
    #"d": (A[1], B[1]), # for debug
    }))
 
cs


The code looks convoluted, but it can be compressed (without information loss) into the following results:

  • $d_1, d_2$ are quite small, around $n^{0.16}$. 
  • $e_1d_1 + e_2d_2 \equiv 1 \pmod{\phi(n)}$.
  • We know $e_1, e_2, n$, but we can't use common modulus attack due to $\text{gcd}(e_1, e_2) = 11$.

I didn't even realize we could use common modulus attack here, but that was okay since it doesn't give us useful information anyway. The key clearly lies in the small $d_1, d_2$. At first, my thought was headed to the Wiener's Attack, which I think is justifiable because that attack works with small $d$ as well. Of course, it's hard (if not impossible) to use the continued fraction idea directly. After reading up on some generalizations of Wiener's Attacks, I thought this problem was related to the coppersmith attack. I tried weird stuff like 3-variable coppersmith but it all failed pretty badly. That led to me solving this problem the last out of the four I solved. The idea of the last problem helped me :)


We begin by writing (note that this kind of manipulation is done in Wiener's Attack as well) $$e_1 d_1 + e_2 d_2 = k \phi(n) + 1 = k(n-p-q+1) + 1 \equiv -k(p+q-1) + 1 \pmod{n}$$ We may now note that $k$ is probably around $n^{0.16}$ as well, so the RHS is around $-n^{0.66}$ multiplied by some constant. 


Okay, so we want $d_1, d_2$ to be around $n^{0.16}$, and $e_1d_1 + e_2d_2 \pmod{n}$ to be around $-n^{0.66} \cdot c$ for some "reasonable" constant $c$. Let's first decide the range of $c$ we will look for. We can expect $k$ to be $0.4 \cdot n^{0.16}$ to $2 \cdot n^{0.16}$. We can expect $p+q$ to be $2 \cdot n^{0.5}$ to $3/\sqrt{2} \cdot n^{0.5}$. Combining, we can get something like $c \in [0.8, 4]$. Note that I'm using a lot of handwaving. Now we will fix $c$. 


The result? We have goal values for $d_1, d_2, e_1d_1 + e_2d_2 \pmod{n}$. Sounds like CVP to me now. 

Indeed, we can work this as a CVP with the lattice generated by $$ [e_1, 1, 0], \quad [e_2, 0, 1], \quad [n, 0, 0] $$ and making the result vector as close as possible to $$ [-c \cdot n^{0.66}, n^{0.16}, n^{0.16} ] $$ Here's a problem. The scale between the first column and the next two columns are off by $n^{0.5}$. If we run CVP now, it'll probably ignore the $n^{0.16}$ condition in order to get similar values for the first column. At least, that's what I thought :D 


Therefore, we rescale. We will work with the lattice generated by $$  [e_1, n^{0.5}, 0], \quad [e_2, 0, n^{0.5}], \quad [n, 0, 0] $$ and making our result vector as close as possible to $$ [-c \cdot n^{0.66}, n^{0.66}, n^{0.66} ] $$ which sounds more reasonable. If we run the CVP algorithm, (Babai's) we will have our candidate values for $d_1, d_2$. 

If correct, we will have that $e_1d_1 + e_2d_2 - 1$ is a product of $\phi(n)$, so we can finish easily. So, how do we find the right $c$ to use?


Simple. Just try a whole bunch of them. Refer to the code below for details.  


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
def Babai_closest_vector(M, G, target):
        small = target
        for _ in range(1):
            for i in reversed(range(M.nrows())):
                c = ((small * G[i]) / (G[i] * G[i])).round()
                small -=  M[i] * c
        return target - small 
    
n  = 142793817321992828777925840162504083304079023834001118099549928854335392622287928254035247188624975743042449746066633491912316354241339908190889792327014012472372654378644158878787350693992259970146885854641856991605625756536504266728483088687985429310233421251081614258665472164668993082471923690196082829593
e1 = 82815162880874815458042429141267540989513396527359063805652845923737062346339641683097075730151688566721221542188377672708478777831586255213972947470222613130635483227797717393291856129771004300757155687587305350059401683671715424063527610425941387424425367153041852997937972925839362190900175155479532582934
C1 = 108072697038795075732704334514926058617161875495016327352871122917196026504758904760148391499245235850616838765611460630089577948665981247735905622903872682862860306107704253287284051312867625831877418240290183661755993649928399992531008191618616452091127799880839665225093055618092869662205901927957599941568
e2 = 84856171747859965508406237198459622554468224770252249975158471902036102010991476445962577679301719179079633469099994226630172251817358960347828156301869905575867853640850107406452911333646573296923235424617864473580743418995994067645338437540627399276292679100115018844287273293945121023787594592185295794983
C2 = 101960082023987498941061751761131381167414505957511290567652602520714324823481487410890478130601013005035303795327512367595187718926017321227779179404306882163521882309833982882201152721855538832465833869251505131262098978117904455226014402089126682222497271578420753565370375178303927777655414023662528363360
 
rat = int(n ** 0.5)
= Matrix(ZZ, 33)
M[00= e1
M[10= e2
M[20= n
M[01= rat
M[12= rat
 
= []
for i in range(8002450):
    Target = vector([-int(n ** 0.66 * i / 1000) , int(n ** 0.16* rat, int(n ** 0.16* rat])
    M = M.LLL()
    GG = M.gram_schmidt()[0]
    TT = Babai_closest_vector(M, GG, Target)
    d1 = TT[1// rat
    d2 = TT[2// rat
    L.append(e1 * d1 + e2 * d2 - 1)
print(list(set(L))) ## this is c
 
for phi in c:
    d1 = inverse(e1, phi)
    print(long_to_bytes(pow(C1, d1, n)))
    d2 = inverse(e2, phi)
    print(long_to_bytes(pow(C2, d2, n)))
cs

  

crypto01


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
from sage.all import *
from flag import flag
from functools import reduce
 
def encrypt(m, e, n):
    n = int(n)
    size = n.bit_length() // 2
    m_low = m & ((1 << size) - 1)
    m_high = (m >> size)
 
    b = (m_low**2 - m_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
 
    return (EC((m_high, m_low)) * e).xy()
 
def decrypt(c, d, n):
    n = int(n)
    size = n.bit_length() // 2
 
    c_high, c_low = c
    b = (c_low**2 - c_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
    m_high, m_low = (EC((c_high, c_low)) * d).xy()
    m_high, m_low = int(m_high), int(m_low)
 
    return (m_high << size) | m_low
 
def gen_prime(size):
    p = random_prime(1 << size)
    while p % 3 != 2:
        p = random_prime(1 << size)
 
    q = random_prime(1 << size)
    while q % 3 != 2:
        q = random_prime(1 << size)
 
    if q > p:
        p, q = q, p
 
    return int(p), int(q)
 
 
 
SIZE = 512
HINTSIZE = 96
= 3
 
flag = int.from_bytes(flag, "big")
assert flag < (1 << SIZE)
 
masks = [randint(1 << (SIZE-1), 1 << SIZE) for _ in range(N)]
masked_flag = reduce(lambda a, b: a ^ b, masks, flag)
 
 
count = 0
ciphertexts = []
while count < N:
    try:
        p, q = gen_prime(SIZE)
        n = p * q
 
        x = random_prime(int(n ** 0.40))
        y = random_prime(int(sqrt(2 * n // (144 * x*x))))
        zbound = -1 * int(round(((p-q) * (n ** 0.25* y) / (3 * (p + q))))
 
        z_ = zbound + ((p + 1)*(q + 1)*- zbound) % x
        e = ((p + 1* (q + 1* y - z_) // x
        d = inverse_mod(e, (p + 1)*(q + 1))
 
        assert (x*y*x*< (2 * n // 144))
        assert (gcd(x, y) == 1)
 
        d = inverse_mod(e, (p+1)*(q+1))
        c = encrypt(masks[count], e, n)
        assert decrypt(c, d, n) == masks[count]
 
        ciphertexts.append({
            "n": n,
            "e": e,
            "c": c,
            "hint": p & ((1<<HINTSIZE)-1)
        })
        count += 1
    except KeyboardInterrupt:
        break
    except (ZeroDivisionError, OverflowError):
        pass
 
 
print("masked_flag = " ,masked_flag)
print("ciphertexts = ", ciphertexts)
 
cs


@diff (pcw) noted that the order of the elliptic curve must be $(p+1)(q+1)$ since $p \equiv q \equiv 2 \pmod{3}$.

This is a cool fact that I didn't know, but it could be easily guessed by the definition of $d$ in the script. 


So, first things first : is this really a elliptic curve challenge? The answer : probably not?

I thought this for a few reasons - I thought the generation of $e$ was quite convoluted so there should be a weakness.

The elliptic curve part looked too clean to have a vulnerability, and it's not even over a field. Hard to do anything, really. 


Therefore, I decided to take a look at how the parameter generation behaves.

First, I look at the sizes of the values. It 's clear that $y$ is small, so $zbound$ and $z$ are also quite small compared to $x$.

This leads to the following suspicion, is $e = \lfloor (p+1)(q+1)y / x \rfloor$? Generating parameters on our own, we see that this is true with a very high probability. This means that we can ignore $zbound$ and $z$ completely now! This is a good progress indeed :) 


This simplifies a lot of things, and we have a good, clean equation to work with. Start with $$ xe  = (p+1)(q+1)y - r \equiv (p+q+1)y - r\pmod{n}$$ with $r < x \approx n^{0.4}$. With $y \approx n^{0.1}$, we see that $(p+q+1)y - r \approx n^{0.6}$. So $x \approx n^{0.4}$ satisfies $xe \pmod{n} < \approx n^{0.6}$. 

Heuristically speaking, there should be a fairly small number of $x$ that satisfy that condition! Can we find them though?


Turns out the answer is yes. I guess you can do this with lattices, but here's a method I learned from competitive programming. 

In fact, given $L, R, M, A$, we can find the minimum nonnegative integer $x$ such that $L \le Ax \pmod{M} \le R$. 

The method is not long, but I don't want to type it all out, so here's a link (scroll down to the end of the editorial)

Also, a problem using this algorithm appeared in NWRRC, (problem G) set by tourist. 


Since we know $e, n$, we can select some $CUT \approx n^{0.6}$ and find the minimum $x$ such that $1 \le ex \pmod{n} \le CUT$. Of course, we have to be cautious with constants when selecting $CUT$. It's not too hard, since we can always verify our value of $x$ by checking its primality and size. This concludes the recovery of $x$, which is a huge progress again! Now we try to recover $y$. 


To recover $y$, we use basic inequalities. Note the following two inequalities $$ y = \frac{xe+r}{(p+1)(q+1)} \ge \frac{xe}{n + 3 \sqrt{n/2} + 1}$$ $$ y = \frac{xe+r}{(p+1)(q+1)} \le \frac{xe + x-1}{n + 2\sqrt{n} + 1}$$ which gives us decent lower/upper bounds. Turns out that this is also perfect, as the two bounds are actually equal! This recovers $y$. 


With this information, we can now bound $p+q$. Simply use $$ p+q = \frac{xe+r}{y} - 1 \ge \frac{xe}{y} - 1 $$ $$ p+q  = \frac{xe+r}{y} -1 \le \frac{xe+x-1}{y} - 1$$ which gives us a good bound for $p+q$. Now we proceed as we did in l33tcrypt in DownUnderCTF and use quadratic formula to get a good bound for $p$. Note that $p > q$. If we analyze the two bounds, we see that this gives us about 200 MSBs of $p$. Now we are practically done. 


We already know 96 LSBs of $p$ via the hint. This adds up to 296 bits of information, so we only need to determine 216 bits of $p$. This can be easily done with coppersmith method, i.e. Sage's small_roots. This part is very straightforward. Now we calculate $p, q, d$ and eventually the masks. The conversion of masks to the actual flag was done by @ironore15. This concludes the problem :D


Also, maybe you can recover $x, y$ with continued fractions on $e/n$? Maybe. I didn't try it :P

UPD : Okay I tried it and it works easily. Why didn't I think about this lmao... This is a much easier way to solve. :)

Basically, from $e = \lfloor (p+1)(q+1)y / x \rfloor$, we can guess that $$ \frac{e}{n} \approx \frac{e}{(p+1)(q+1)} \approx \frac{y}{x}$$ so $y/x$ is a good approximation of $e/n$. Find all convergents of $e/n$, and find those that have primes as its numerator and denominator. 

This gives us $x, y$, so we can proceed with the coppersmith attack as above. Much easier :)


UPD : The continued fraction solution is indeed the intended sol. I guess it could be proved using the given bounds :)

UPD : So apparently this thing had a name, KMOV cryptosystem. didn't know that :P



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
def kthp(n, k):
    if n == 0:
        return 0
    lef = 1
    rig = 2
    while rig ** k < n:
        rig = rig << 1
    while lef <= rig:
        mid = (lef + rig) // 2
        if mid ** k <= n:
            best = mid
            lef = mid + 1
        else:
            rig = mid - 1
    return best
 
def ceil(n, m):
    return (n + m - 1// m
 
def optf(A, M, L, R):
    if L == 0:
        return 0
    if 2 * A > M:
        L, R = R, L
        A = M - A
        L = M - L
        R = M - R
    cc_1 = ceil(L, A)
    if A * cc_1 <= R:
        return cc_1
    cc_2 = optf(A - M % A, A, L % A, R % A)
    return ceil(L + M * cc_2, A)
 
def decrypt(c, d, n):
    n = int(n)
    size = n.bit_length() // 2
 
    c_high, c_low = c
    b = (c_low**2 - c_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
    m_high, m_low = (EC((c_high, c_low)) * d).xy()
    m_high, m_low = int(m_high), int(m_low)
 
    return (m_high << size) | m_low
 
ciphertexts =  []
for C in ciphertexts:
    n = C['n']
    e = C['e']
    c = C['c']
    hint = C['hint']
    CUT = kthp( (int)(n ** 0.2// 722* kthp(n, 2* 8
    x = optf(e, n, 1, CUT)
    R = ((e * x + x - 1// (n + 2 * kthp(n, 2+ 1))
    L = ((e * x) // (n + 3 * kthp(n//22+ 1))
    y = (L + R) // 2
    assert L == R and x in Primes() and y in Primes()
    sum_L = (x * e) // y - 1 - n
    sum_R = (x * e + x - 1// y - 1 - n
    lr = (sum_R + kthp(sum_R * sum_R - 4 * n, 2)) // 2
    sm = (sum_L + kthp(sum_L * sum_L - 4 * n, 2)) // 2
    assert sm <= lr
    assert (sm >> 312== (lr >> 312)
    p_hint = hint
    K = Zmod(n)
    P.<t> = PolynomialRing(K, implementation='NTL')
    f = (p_hint * inverse_mod(2 ** 96, n)) % n + t + (2 ** (312-96)) * (lr >> 312)
    x0 = f.small_roots(X = (2 ** 220), beta = 0.5, epsilon = 0.03)
    ## print(x0)
    p = p_hint + x0[0* (2 ** 96+ (2 ** 312* (lr >> 312)
    p = (int)(p)
    q = n // p
    d = inverse_mod(e, (p+1* (q+1))
    print(decrypt(c, d, n))
 
## thanks, ironore!
def recover_flag(masks, masked_flag):
    flag = reduce(lambda a, b: a ^ b, masks, masked_flag)
    return flag.to_bytes(512 // 8'big')
cs


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
def get_red(e, n):
    cur_num, cur_den = e, n
    num_1, den_1 = 01
    num_2, den_2 = 10
    while True:
        val = cur_num // cur_den
        nxt_num = cur_den
        nxt_den = cur_num - val * cur_den
        # calculate new convergent
        num_3 = val * num_2 + num_1
        den_3 = val * den_2 + den_1
        if isPrime(num_3) and isPrime(den_3):
            return num_3, den_3
        if den_3 > int(n ** 0.4):
            return -1
        # update convergents
        num_1, den_1 = num_2, den_2
        num_2, den_2 = num_3, den_3
        # update continued fractions
        cur_num, cur_den = nxt_num, nxt_den
 
ciphertexts =  []
for C in ciphertexts:
    n = C['n']
    e = C['e']
    c = C['c']
    hint = C['hint']
    y, x = get_red(e, n)
    R = ((e * x + x - 1// (n + 2 * kthp(n, 2+ 1))
    L = ((e * x) // (n + 3 * kthp(n//22+ 1))
    assert y == (L + R) // 2
    assert L == R and isPrime(x) and isPrime(y)
    ## continue as the initial solution
cs


'수학 > 암호론 및 CTF' 카테고리의 다른 글

N1CTF 2020 Crypto Write-Ups  (0) 2020.10.18
Leftover Hash Lemma and its Applications  (0) 2020.10.18
SECCON 2020 OnlineCTF Crypto Write-Ups  (0) 2020.10.11
CryptoHack All Solve  (3) 2020.09.30
TokyoWesternCTF 2020 Crypto Write-Ups  (0) 2020.09.20
DownUnderCTF Crypto Write-Ups  (2) 2020.09.19


오늘 남았던 2문제를 해결하여 올솔브를 했습니다. 2문제 다 쫄아서 못 건드리고 있었는데 펜 굴리니까 생각보다 무난하게 풀리네요 :) 

여기서 접근한 새로운 정보들이 많으니 공부 좀 해야겠습니다. 그래도 올솔하니까 후련하네요 ㅋㅋ 

  1. rkm 그는 갓인가.. rkm 그는 갓인가..rkm 그는 갓인가..rkm 그는 갓인가..rkm 그는 갓인가..

    • 사용자 rkm0959 2020.10.07 18:56 신고

      바킹독 그는 킹인가.. 바킹독 그는 킹인가.. 바킹독 그는 킹인가.. 바킹독 그는 킹인가.. 바킹독 그는 킹인가..

  2. mathboy7 2020.10.08 07:04

    당신의 팬을 멈출 수 없습니다!!

I participated in TWCTF 2020 as a member of the team D0G$. We got 1st place!


easy hash

I tried to do something but then @yoshiking sensei solved it. :D


sqrt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import bytes_to_long, isPrime
from secret import flag, p
 
 
def encrypt(m, k, p):
    return pow(m, 1 << k, p)
 
 
assert flag.startswith("TWCTF{")
assert len(flag) == 42
assert isPrime(p)
 
= 64
pt = bytes_to_long(flag.encode())
ct = encrypt(pt, k, p)
 
with open("output.txt""w"as f:
    f.write(str(ct) + "\n")
    f.write(str(p) + "\n")
 
# 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
# 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
cs

So we are given $m^{2^{64}} \pmod{p}$ and $p$. We need to find $m$. The first thing we note is that $\nu_2 (p-1) = 30$. Therefore, we have $\text{gcd}(2^{64}, p-1) = 2^{30}$ possibilities for $m$, if we disregard the length and "TWCTF{" condition. This is a large number of solutions, but it's not impossible to brute force. We first find any solution of $m^{2^{64}} \equiv enc \pmod{p}$ by repeated usage of Tonelli-Shanks. Now, we may write all solutions as $m \cdot g^{(p-1)/2^{30} \cdot k}$, where $g$ is some generator easily found by Sage. We go over each solution, check if it's small enough to be a candidate first (optimization), then convert it to bytes and see if it meets the desired conditions. 

It was estimated to run in ~1.5 hours in my computer, so I asked for some computational help. 
@theoldmoon0602 and @ironore15 were kind enough to help me in this brute force.

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
## Step 1 : Find any solution
def gogo(r, d, m):
    if d == 0:
        print(r)
        exit()
        return
    u = tonelli(m, r)
    if u == -1:
        return
    gogo(u, d-1, m)
    gogo((m-u)%m, d-1, m)
 
 
## Step 2 : Start Brute Force
res = 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
= 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
ex = 1948865039294009691576181380771672389220382961994854292305692557649261763833149884145614983319207887860531232498119502026176334583810204964826290882842308810728384018930976243008464049012096415817825074466275128141940107121005470692979995184344972514864128534992403176506223940852066206954491827309484962494271
assert pow(ex, 1 << 64 , p) == res
 
def is_ascii(s):
    return all(c < 128 for c in s)
 
gen = 3
jp = pow(3, (p-1// (2 ** 30), p)
 
for i in tqdm(range(02**30)):
    ex = (ex * jp) % p
    if ex.bit_length() <= 400:
        u = long_to_bytes(ex)
        if is_ascii(u) and b"TWCTF{" in u:
            print(u)
            exit()
cs
 
twin-d
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
require 'json'
require 'openssl'
 
= OpenSSL::BN::generate_prime(1024).to_i
= OpenSSL::BN::generate_prime(1024).to_i
 
while true
    d = OpenSSL::BN::generate_prime(1024).to_i
    break if ((p - 1* (q - 1)).gcd(d) == 1 && ((p - 1* (q - 1)).gcd(d + 2== 1
end
 
e1 = OpenSSL::BN.new(d).mod_inverse(OpenSSL::BN.new((p - 1* (q - 1))).to_i
e2 = OpenSSL::BN.new(d + 2).mod_inverse(OpenSSL::BN.new((p - 1* (q - 1))).to_i
 
flag = File.read('flag.txt')
msg = OpenSSL::BN.new(flag.unpack1("H*").to_i(16))
= OpenSSL::BN.new(p * q)
enc = msg.mod_exp(OpenSSL::BN.new(e1), n)
 
puts ({ n: (p*q).to_s, e1: e1.to_s, e2: e2.to_s, enc: enc.to_s }).to_json
cs

So we have $e_1, e_2$ corresponding to $d_1, d_2$, which have a difference of $2$.
Basically what this says is that $e_2^{-1} - e_1^{-1} \equiv 2 \pmod{\phi(n)}$. Therefore, we can simply write $e_1-e_2 \equiv 2e_1e_2 \pmod{n}$. 
This implies that $2e_1e_2 + e_2 - e_1$ is a multiple of $\phi(n)$. It is very well-known fact that given $n$ and a multiple of $\phi(n)$, we can factorize $n$. So apply that method to factorize $n$. The rest is basic RSA. Happy to get first solve :)

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
= 26524843197458127443771133945229625523754949369487014791599807627467226519111599787153382777120140612738257288082433176299499326592447109018282964262146097640978728687735075346441171264146957020277385391199481846763287915008056667746576399729177879290302450987806685085618443327429255304452228199990620148364422757098951306559334815707120477401429317136913170569164607984049390008219435634838332608692894777468452421086790570305857094650986635845598625452629832435775350210325954240744747531362581445612743502972321327204242178398155653455971801057422863549217930378414742792722104721392516098829240589964116113253433
e1 = 3288342258818750594497789899280507988608009422632301901890863784763217616490701057613228052043090509927547686042501854377982072935093691324981837282735741669355268200192971934847782966333731663681875702538275775308496023428187962287009210326890218776373213535570853144732649365499644400757341574136352057674421661851071361132160580465606353235714126225246121979148071634839325793257419779891687075215244608092289326285092057290933330050466351755345025419017436852718353794641136454223794422184912845557812856838827270018279670751739019476000437382608054677808858153944204833144150494295177481906551158333784518167127
e2 = 20586777123945902753490294897129768995688830255152547498458791228840609956344138109339907853963357359541404633422300744201016345576195555604505930482179414108021094847896856094422857747050686108352530347664803839802347635174893144994932647157839626260092064101372096750666679214484068961156588820385019879979501182685765627312099064118600537936317964839371569513285434610671748047822599856396277714859626710571781608350664514470335146001120348208741966215074474578729244549563565178792603028804198318917007000826819363089407804185394528341886863297204719881851691620496202698379571497376834290321022681400643083508905
enc = 18719581313246346528221007858250620803088488607301313701590826442983941607809029805859628525891876064099979252513624998960822412974893002313208591462294684272954861105670518560956910898293761859372361017063600846481279095019009757152999533708737044666388054242961589273716178835651726686400826461459109341300219348927332096859088013848939302909121485953178179602997183289130409653008932258951903333059085283520324025705948839786487207249399025027249604682539137261225462015608695527914414053262360726764369412756336163681981689249905722741130346915738453436534240104046172205962351316149136700091558138836774987886046
 
cc = 2 * e1 * e2 + e2 - e1
 
tt = 0
cv = cc
while cv % 2 == 0:
    cv //= 2
    tt += 1
 
for i in range(3100):
    t = pow(i, cv, n)
    for j in range(0, tt):
        g = GCD(t-1, n)
        if g != 1 and g != n:
            print(g) ## this is p
            exit()
        t = (t * t) % n
 
= 177276401739167429751099686272064967069179029118915820763787396008698833618702905602522557760805466539182350759150950532254737829482867347218636052172454990031666206911810532732619372311183056810552780771197878348351916381506465238562588760944922289622011858546760490648690942678177540128777265354408766804279
= n // p
 
phi = (p-1* (q-1)
= inverse(e1, phi)
print(long_to_bytes(pow(enc, d, n)))
cs

The Melancholy of Alice
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
from Crypto.Util.number import getStrongPrime, getRandomRange
 
= 1024
 
def generateKey():
    p = getStrongPrime(N)
    q = (p - 1// 2
    x = getRandomRange(2, q)
    g = 2
    h = pow(g, x, p)
    pk = (p, q, g, h)
    sk = x
    return (pk, sk)
 
def encrypt(m, pk):
    (p, q, g, h) = pk
    r = getRandomRange(2, q)
    c1 = pow(g, r, p)
    c2 = m * pow(h, r, p) % p
    return (c1, c2)
 
def main():
    with open("flag.txt"as f:
        flag = f.read().strip()
 
    pk, sk = generateKey()
    with open("publickey.txt""w"as f:
        f.write(f"p = {pk[0]}\n")
        f.write(f"q = {pk[1]}\n")
        f.write(f"g = {pk[2]}\n")
        f.write(f"h = {pk[3]}\n")
 
    with open("ciphertext.txt""w"as f:
        for m in flag:
            c = encrypt(ord(m), pk)
            f.write(f"{c}\n")
 
 
if __name__ == "__main__":
    main()
 
cs

I had good fun solving this problem, so I'll write my thought process as well. 

This honestly looks like a perfect code, but the key line that left a question mark for me was line 35. 

$ord(m)$ is incredibly small, so maybe we can bypass the entire discrete logarithm?


To think further in this direction, we need some knowledge on $p-1$. I first checked if $q$ was prime - it was not.

Then I checked the factors of $q$ - I could brute force small primes, but I just went to FactorDB. Why not?

I found out that $3, 5, 19$ were factors of $q$, which was quite surprising to me.

I thought StrongPrimes generated a prime of a form $2 \cdot q + 1$ where $q$ is a prime. Oops?


Anyways, since $3 \cdot 5 \cdot 19$ was pretty large, so it seems this should be fine.

Discrete Logarithm calculation is hard, but calculation modulo a small prime is easy by Pohlig-Hellman style thinking.

Can we abuse this? Well, given the signature data we can calculate the logarithm of the $ord(m)$ modulo $3 \cdot 5 \cdot 19$.

So if we precompute all logarithms of 0 to 255 modulo $3 \cdot 5 \cdot 19$, we can find the "candidates" for each letter.


I did this, but found there are multiple solutions. I tried to fix this by working with $5710354319$, which is another prime divisor.

I thought this should also work using sage's BSGS and stuff, but it was way too slow.


I posted my partial result (candidates) on discord and asked for guesswork/recovery, then @yoshiking found the solution.


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
def crt(a, b):
    u, v = 01
    for i in range(len(a)):
        u, v = CRT(u, v, a[i], b[i])
    return u
 
def get_DL(x, pr):
    gg = pow(x, (p-1// pr, p)
    for i in range(0, pr):
        gt = pow(g, i * (p-1// pr, p)
        if gt == gg:
            return i
 
def get_DLs(x):
    p_1 = get_DL(x, 3)
    p_2 = get_DL(x, 5)
    p_3 = get_DL(x, 19)
    return crt([p_1, p_2, p_3], [3519])
 
cc = [-1]
for i in range(1255):
    cc.append(get_DLs(i))
 
xx = get_DLs(h)
 
res = []
fin = []
fom = ""
for x, y in res:
    s = ""
    u = get_DLs(x)
    v = get_DLs(y)
    ## v = xx * u + get_DLs(desire)
    res = (v - xx * u) % (3 * 5 * 19)
    for j in range(0255):
        if cc[j] == res and j <= 128:
            s += chr(j)
    print(s)
 
cs


XOR and shift encryptor

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
#!/usr/bin/python3
 
= []
= 0
 
def init():
  global s,p
  s = [i for i in range(0,64)]
  p = 0
  return
 
def randgen():
  global s,p
  a = 3
  b = 13
  c = 37
  s0 = s[p]
  p = (p + 1& 63
  s1 = s[p]
  res = (s0 + s1) & ((1<<64)-1)
  s1 ^= (s1 << a) & ((1<<64)-1)
  s[p] = (s1 ^ s0 ^ (s1 >> b) ^ (s0 >> c))  & ((1<<64)-1)
  return res
 
def jump(to):
 
  # Deleted...
 
  return
 
def check_jump():
  init()
  jump(10000)
  assert randgen() == 7239098760540678124
 
  init()
  jump(100000)
  assert randgen() == 17366362210940280642
 
  init()
  jump(1000000)
  assert randgen() == 13353821705405689004
 
  init()
  jump(10000000)
  assert randgen() == 1441702120537313559
 
  init()
  for a in range(31337):randgen()
  for a in range(1234567):randgen()
  buf = randgen()
  for a in range(7890123):randgen()
  buf2 = randgen()
  init()
  jump(31337+1234567)
  print (buf == randgen())  
  jump(7890123)
  print (buf2 == randgen())
 
check_jump()
 
init()
for a in range(31337):randgen()
 
flag = open("flag.txt").read()
assert len(flag) == 256
 
enc = b""
 
for x in range(len(flag)):
  buf = randgen()
  sh = x//2
  if sh > 64:sh = 64
  mask = (1 << sh) - 1
  buf &= mask
  jump(buf)
  enc += bytes([ ord(flag[x]) ^ (randgen() & 0xff) ])
  print ("%r" % enc)
 
open("enc.dat","wb").write(bytearray(enc))
 
 
cs


So basically what we have to do is efficiently "advance" the RNG large amount of times. 

The given RNG state transition can be regarded as a linear transformation over the $64^2$ bits in the state.

Therefore, we can model this by matrix multiplication, where the size of the matrix is $64^2$. 

Using binary exponentiation, we can get our random numbers relatively quickly.


I had thought of this but believed this would be way too slow, but @theoldmoon0602 wrote a beautiful code in sage and managed to find the flag. The code took about 30 minutes ~ 1 hour to run, according to the solver. 


The below code, by @theoldmoon0602, derives the key sequence. 

Also, for the write-up written by the actual solver @theoldmoon0602, check here.


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
= 64
= GF(2)
 
def L(n):
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N - n):
    m[i + n][i] = 1
 
  return matrix(F, m)
 
def R(n):
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N - n):
    m[i][i + n] = 1
 
  return matrix(F, m)
 
 
def I():
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N):
    m[i][i] = 1
 
  return matrix(F, m)
 
def O():
  m = [[0 for x in range(N)] for y in range(N)]
  return matrix(F, m)
 
def genM():
  a = 3
  b = 13
  c = 37
 
  o = O()
  i = I()
  la = L(a)
  rb = R(b)
  rc = R(c)
 
  blocks = [
    [i + rc, i + la + rb + la*rb] + [o for _ in range(62)]
  ]
  for j in range(1, N):
    row = [o for _ in range(N)]
    row[(j+1) % N] = i
    blocks.append(row)
 
  M = block_matrix(F, [*zip(*blocks)])
 
  return M
 
def initial_state():
  s = "".join(["{:064b}".format(i) for i in range(N)])
  vec = []
  for c in s:
    vec.append(F(int(c)))
  return Matrix(F, vec)
 
def getvalue(row, index):
  v = 0
  for i in range(N):
    v = v*2 + int(row[0][index*+ i])
  return v
 
def dumpstate(a):
  xs = []
  for i in range(N):
    xs.append(getvalue(a, i))
  print(xs)
 
= initial_state()
= genM()
 
def init():
  global s, M
  s = initial_state()
  M = genM()
 
def randgen():
  global s, M
  res = (getvalue(s, 0+ getvalue(s, 1)) % ((1<<64)-1)
  s = s * M
  return res
 
def jump(n):
  global s,M
  s = s * (M^n)
 
init()
jump(31337)
for x in range(256):
  buf = randgen()
  sh = x//2
  if sh > 64:sh = 64
  mask = (1 << sh) - 1
  buf &= mask
  jump(buf)
  print(randgen() & 0xff
 
cs


circular

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
## keygen
 
require "openssl"
require "json"
 
= OpenSSL::BN.generate_prime(1024)
= OpenSSL::BN.generate_prime(1024)
= OpenSSL::BN.generate_prime(2048false)
= p * q
File.write("pubkey.txt", { n: n.to_s, k: k.to_s }.to_json)
 
## interaction
 
require "functions_framework"
require "digest/sha2"
 
fail unless ENV["FLAG"]
 
key = JSON.parse(File.read("pubkey.txt"))
= key["n"].to_i
= key["k"].to_i
 
EXPECTED_MESSAGE = 'SUNSHINE RHYTHM'
 
FunctionsFramework.http("index"do |request|
  if request.request_method != "POST"
    return "Bad Request"
  end
 
  data = JSON.parse(request.body.read)
  cmd = data["cmd"]
  if cmd == "pubkey"
    return { pubkey: { n: n.to_s, k: k.to_s } }
  elsif cmd == "verify"
    x = data["x"].to_i
    y = data["y"].to_i
    msg = data["msg"].to_s
    hash = ""
    4.times do |i|
      hash += Digest::SHA512.hexdigest(msg + i.to_s)
    end
    hash = hash.to_i(16) % n
    signature = (x ** 2 + k * y ** 2) % n
 
    if signature == hash
      if msg == EXPECTED_MESSAGE
        return { result: ENV["FLAG"] }
      end
      return { result: "verify success" }
    else
      return { result: "verify failed" }
    end
  else
    return "invalid command"
  end
end
 
cs


Basically, we have to find $x, y$ such that $x^2 + ky^2 \equiv HASH \pmod{n}$. 

We know $k, HASH, n$, but not the factorization of $n$. This seemed to be very difficult. 


First few ideas of mine included the Brahmagupta's Identity and Pell's Equation. 

I tried to work on Pell's Equation + continued fractions, but it failed as well.


After a while, @ironore15 notified us that this scheme has a name - OSS signature.

I was quite surprised because I didn't think this would be an actual scheme in the literature.

Anyways, after a bit of googling I was able to find a paper that describes the attack.

The rest was relatively straightforward implementation. I was glad to see one of my ideas used in the attack.


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
def comb(x1, y1, x2, y2, k, n):
    return (x1 * x2 + k * y1 * y2) % n, (x1 * y2 - x2 * y1) % n
 
def solve(k, m, n): ## solve x^2 + ky^2 == m mod n
    print("solve", k, m, n)
    fu = kthp(m, 2)
    if fu * fu == m:
        return (fu, 0)
    if k < 0:
        se = kthp(-k, 2)
        if se * se == -k:
            retx = (m+1* inverse(2, n) % n 
            rety = (m-1* inverse(2 * se, n) % n
            return retx, rety
    if m == 1:
        return (10)
    if m == k % n:
        return (01)
    while True:
        u = random.getrandbits(1024)
        v = random.getrandbits(1024)
        m_0 = (m * (u * u + k * v * v)) % n
        if isPrime(m_0):
            if GCD(m_0, n) != 1:
                print("LOL", m_0)
                exit()
            x_0 = tonelli(m_0, (-k) % m_0)
            if (x_0 * x_0 + k) % m_0 == 0:
                break
    ms = [m_0]
    xs = [x_0]
    sz = 1
    while True:
        new_m = (xs[sz-1* xs[sz-1+ k) // ms[sz-1]
        ms.append(new_m)
        if k > 0 and xs[sz-1<= ms[sz] <= ms[sz-1]:
            sz = sz + 1
            break
        if k < 0 and abs(ms[sz]) <= kthp(abs(k), 2):
            sz = sz + 1
            break
        xs.append(min(xs[sz-1] % ms[sz], ms[sz] - (xs[sz-1] % ms[sz])))
        sz = sz + 1
    assert sz == len(ms)
    assert sz - 1 == len(xs)
    uu, vv = xs[0], 1
    dv = 1
    for i in range(1, sz-1):
        assert (xs[i] ** 2 + k) % n == (ms[i] * ms[i+1]) % n
        uu, vv = comb(uu, vv, xs[i], 1, k, n)
        dv = (dv * ms[i]) % n
    dv = (dv * ms[sz-1]) % n
    uu = (uu * inverse(dv, n)) % n 
    vv = (vv * inverse(dv, n)) % n
    X, Y = solve(-ms[sz-1], (-k) % n, n)
    soly = inverse(Y, n)
    solx = (X * soly) % n
    finx, finy = comb(solx, soly, uu, vv, k, n)
    godx = ((finx * u - k * finy * v) * inverse(u * u + k * v * v, n)) % n
    gody = ((finx * v + finy * u) * inverse(u * u + k * v * v, n)) % n
    return godx, gody
 
msg = 'SUNSHINE RHYTHM'
hsh = ''
 
for i in range(04):
    cc = msg + chr(ord('0'+ i)
    hsh += hashlib.sha512(cc.encode()).hexdigest()
 
request = {
    'cmd''pubkey'
}
= web_request('POST''https://crypto02.chal.ctf.westerns.tokyo', request, False)
 
 
= 25299128324054183472341067223932160732879350179758036557232544635970111090474692853470743347443422497121006796606102551210094872253782062717537548880909979729182337501587763866901367212812697076494080678616385493076865655574412317879297160790121009524506015912113098690685202868184636344610142590510988192306870694667596904330867479578103616304053889409982447653859514868824002960431331342963562137691362725961627846051021103954795862501700267818317148154520620016172888281127685503677751830350686839873220480306266506898497203511851305686566444690384065880667273398255172752236076702247451872387522388546088290187449
= 31019613858513746556266176233462864650379070310554671955689986199007361221356361736128815989480106678809272137963430923820800280374078610631771089089882153619351592434728588050285853284795554255483472955286848474793299446184220594124878818081534965835159741218233013815338595300394855159744354636541274026478456851924371621879725248093305782590590080796638483359868136648681381332610536250576568502512250581068814961097404403694071264894656697723213779631364079010490113719021172301802643377777927176399460547584115127172190000090756708138720022664973312744713394243720961199400948876916817452969615149776530401604593 % n
goal = int(hsh, 16) % n 
 
x, y = solve(k, goal, n)
print((x * x + k * y *- goal) % n)
 
request = {
    'cmd''verify',
    'x'str(x),
    'y'str(y),
    'msg': msg
}
 
= web_request('POST''https://crypto02.chal.ctf.westerns.tokyo', request, False)
print(X)
cs


'수학 > 암호론 및 CTF' 카테고리의 다른 글

SECCON 2020 OnlineCTF Crypto Write-Ups  (0) 2020.10.11
CryptoHack All Solve  (3) 2020.09.30
TokyoWesternCTF 2020 Crypto Write-Ups  (0) 2020.09.20
DownUnderCTF Crypto Write-Ups  (2) 2020.09.19
InterKosenCTF 2020 Crypto 분야 Write-Ups (?)  (0) 2020.09.06
Crypto CTF 2020  (2) 2020.08.16

I played DownUnderCTF as a member of Defenit, and solved all cryptography problems. 


rot-i

1
2
Ypw'zj zwufpp hwu txadjkcq dtbtyu kqkwxrbvu! Mbz cjzg kv IAJBO{ndldie_al_aqk_jjrnsxee}. Xzi utj gnn olkd qgq ftk ykaqe uei mbz ocrt qi ynlu, etrm mff'n wij bf wlny mjcj :).
 
cs


The problem seems to imply a variant of rotation cipher. Now, it's reasonable to guess that "Mbz cjzg kv IAJBO" is actually "The flag is DUCTF". We subtract the alphabet order of each text to find that the "amount of rotation" changes by 1 each time. 

I changed all letters into lowercase, cleaned up some parts of the string, and wrote the following code.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
= 'ypw zj zwufpp hwu txadjkcq dtbtyu kqkwxrbvu! mbz cjzg kv iajbo{ndldie_al_aqk_jjrnsxee}. xzi utj gnn olkd qgq ftk ykaqe uei mbz ocrt qi ynlu, etrm mffn wij bf wlny mjcj :'
= 'the flag is ductf'
= 'mbz cjzg kv iajbo'
 
for i in range(026):
    s = ""
    st = i
    for j in range(len(t)):
        if ord('a'<= ord(t[j]) <= ord('z'):
            cc = chr(ord('a'+ (ord(t[j]) - ord('a'+ st) % 26)
            s += cc
        else:
            s += t[j]
        st = st - 1
    print(s)
cs


babyrsa

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import bytes_to_long, getPrime
 
flag = open('flag.txt''rb').read().strip()
p, q = getPrime(1024), getPrime(1024)
= p*q
= 0x10001
= pow(557*- 127*q, n - p - q, n)
= pow(bytes_to_long(flag), e, n)
print(f'n = {n}')
print(f's = {s}')
print(f'c = {c}')
cs


The extra information we have here is $s$. Since $n-p-q = \phi(n) - 1$, we see that $s$ is the modular inverse of $557p - 127q$ $\pmod{n}$. Therefore, we may recover $557p-127q \equiv s^{-1} \pmod{n}$ with Extended Euclidean algorithm. Since $557p - 127q$ is between $0$ and $n$, we can just recover $557p-127q$. Since we already know $n = pq$, we can just solve a quadratic equation. I did it with a binary search.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
= 19574201286059123715221634877085223155972629451020572575626246458715199192950082143183900970133840359007922584516900405154928253156404028820410452946729670930374022025730036806358075325420793866358986719444785030579682635785758091517397518826225327945861556948820837789390500920096562699893770094581497500786817915616026940285194220703907757879335069896978124429681515117633335502362832425521219599726902327020044791308869970455616185847823063474157292399830070541968662959133724209945293515201291844650765335146840662879479678554559446535460674863857818111377905454946004143554616401168150446865964806314366426743287
= 3737620488571314497417090205346622993399153545806108327860889306394326129600175543006901543011761797780057015381834670602598536525041405700999041351402341132165944655025231947620944792759658373970849932332556577226700342906965939940429619291540238435218958655907376220308160747457826709661045146370045811481759205791264522144828795638865497066922857401596416747229446467493237762035398880278951440472613839314827303657990772981353235597563642315346949041540358444800649606802434227470946957679458305736479634459353072326033223392515898946323827442647800803732869832414039987483103532294736136051838693397106408367097
= 7000985606009752754441861235720582603834733127613290649448336518379922443691108836896703766316713029530466877153379023499681743990770084864966350162010821232666205770785101148479008355351759336287346355856788865821108805833681682634789677829987433936120195058542722765744907964994170091794684838166789470509159170062184723590372521926736663314174035152108646055156814533872908850156061945944033275433799625360972646646526892622394837096683592886825828549172814967424419459087181683325453243145295797505798955661717556202215878246001989162198550055315405304235478244266317677075034414773911739900576226293775140327580
= 65537 
 
tt = inverse(s, n)
lef = 2 ** 1023
rig = 2 ** 1025
while lef <= rig:
    mid = (lef + rig) // 2
    p = mid 
    q = (557 * p - tt) // 127
    if p * q >= n:
        best = mid
        rig = mid - 1
    else:
        lef = mid + 1
= best 
= (557 * best - tt) // 127
phi = (p-1* (q-1)
= inverse(e, phi)
print(long_to_bytes(pow(c, d, n)))
cs


Extra Cool Block Chaining

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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.strxor import strxor
from os import urandom
 
flag = open('./flag.txt''rb').read().strip()
KEY = urandom(16)
IV = urandom(16)
 
def encrypt(msg, key, iv):
    msg = pad(msg, 16)
    blocks = [msg[i:i+16for i in range(0len(msg), 16)]
    out = b''
    for i, block in enumerate(blocks):
        cipher = AES.new(key, AES.MODE_ECB)
        enc = cipher.encrypt(block)
        if i > 0:
            enc = strxor(enc, out[-16:])
        out += enc
    return strxor(out, iv*(i+1))
 
def decrypt(ct, key, iv):
    blocks = [ct[i:i+16for i in range(0len(ct), 16)]
    out = b''
    for i, block in enumerate(blocks):
        dec = strxor(block, iv)
        if i > 0:
            dec = strxor(dec, ct[(i-1)*16:i*16])
        cipher = AES.new(key, AES.MODE_ECB)
        dec = cipher.decrypt(dec)
        out += dec
    return out
 
flag_enc = encrypt(flag, KEY, IV).hex()
 
print('Welcome! You get 1 block of encryption and 1 block of decryption.')
print('Here is the ciphertext for some message you might like to read:', flag_enc)
 
try:
    pt = bytes.fromhex(input('Enter plaintext to encrypt (hex): '))
    pt = pt[:16# only allow one block of encryption
    enc = encrypt(pt, KEY, IV)
    print(enc.hex())
except:
    print('Invalid plaintext! :(')
    exit()
 
try:
    ct = bytes.fromhex(input('Enter ciphertext to decrypt (hex): '))
    ct = ct[:16# only allow one block of decryption
    dec = decrypt(ct, KEY, IV)
    print(dec.hex())
except:
    print('Invalid ciphertext! :(')
    exit()
 
print('Goodbye! :)')
cs


Let's first consider what the encryption function is actually doing. Given a plaintext $P_1 P_2 \cdots P_n$, we are basically doing $C_i = E_K(P_i) \oplus C_{i-1}$ for each $i$, then XORing the $IV$ to all ciphertexts before returning. In other words, we are just sending $IV \oplus E_K(P_1), IV \oplus E_K(P_1) \oplus E_K(P_2)$, $\cdots , IV \oplus E_K(P_1) \oplus \cdots \oplus E_K(P_n)$. 


Now what we can do is ask for an encryption of a single block, and a decryption of a single block. 

Say we want to find $P_k$. To do so, we need to ask for a decryption of $IV \oplus E_K(P_k)$. How do we find that? 

Note that this is trivial for $k=1$. Assume $k \ge 2$. Now, by XORing the two consecutive results of the output, we can easily get $E_K(P_k)$. Therefore, we need to find a way to get $IV$. This looks like a time for encryption oracle. 


Note that if $P_1 = P_2$, our second output will be $IV \oplus E_K(P_1) \oplus E_K(P_2) = IV$. 

We want to use this to our benefit, but we can only ask for one block! It's okay, because we can abuse the padding. 

By asking for the encryption of b'\x10' * 16, we can make our padded plaintext of the form $P_1 P_1$. 

This enables us to get $IV$, and we can decrypt each block as we want. I did this manually, so code below is not perfect.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cc = 'Here is the ciphertext for some message you might like to read: '
print(conn.recvline())
= conn.recvline()
print(T)
hxval = T[len(cc):-1]
hxval = hxval.decode()
print(len(hxval))
conn.send((b'\x10' * 16).hex() + "\n")
= conn.recvline()
cc = "Enter plaintext to encrypt (hex): "
print(T)
IV = T[len(cc):-1]
print(IV)
IV = IV.decode()
IV = bytes.fromhex(IV)
IV = IV[-16:]
## change indexes to find different blocks (below)
conn.send((strxor(bytes.fromhex(hxval[160:192]), strxor(bytes.fromhex(hxval[128:160]), IV))).hex() + "\n"
print(conn.recvline()) ## change hex -> bytes here
cs


ceebc

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
#!/usr/bin/env python3
from os import urandom
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives import constant_time
from cryptography.hazmat.backends import default_backend
 
backend = default_backend()
key = urandom(32)
solution_message = b'flagflagflagflag'
 
def CBC_MAC(key, message, iv):
    if len(message) != 16 or len(iv) != 16:
        raise ValueError('Only messages/IVs of size 16 are allowed!')
    cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=backend)
    enc = cipher.encryptor()
    return enc.update(message) + enc.finalize()
 
def sign(message, iv):
    return CBC_MAC(key, message, iv) + iv
 
def verify(message, signature):
    iv = signature[16:]
    computed_sig = sign(message, iv)
    return constant_time.bytes_eq(signature, computed_sig)
 
sample = b'cashcashcashcash'
print('Hey there, have a message {} and its signature {}!'.format(
      sample.decode('utf-8'), sign(sample, urandom(16)).hex()
      ))
 
received_message = input('Now give me your message: ').encode('utf-8')
try:
    received_signature = bytes.fromhex(input('Now the signature (in hex): '))
except ValueError:
    print('Signature was not in hex!')
    exit()
 
try:
    valid = verify(received_message, received_signature)
except ValueError as e:
    print(e)
    exit()
 
if valid:
    print('Signature valid!')
 
    if received_message == solution_message:
        print(open('flag.txt').read())
    else:
        print('Phew! Good thing the message isn\'t {}!'
              .format(solution_message.decode('utf-8')))
else:
    print('Invalid signature!')
 
cs


We are given a signature of an known example message, and we have to forge a signature of a desired message.

The signature is given by $E_{K, IV}^{CBC} (P) || IV$ which is just $E_{K}^{ECB} (P \oplus IV) || IV$.

So we have $IV$, $E_{K}^{ECB}(P_{ex} \oplus IV)$, and $P_{ex}$. We want to forge a signature of $P_{flag}$. 

To do so, calculate $IV'$ such that $P_{ex} \oplus IV = P_{flag} \oplus IV'$. This can be easily done.

Then simply send $P_{K}^{ECB} (P_{ex} \oplus IV) || IV'$ as a signature. It's clear that this works. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
= conn.recvline()
cc = 'Hey there, have a message cashcashcashcash and its signature '
SIG = T[len(cc) : -2]
SIG = bytes.fromhex(SIG.decode())
INC = SIG[0:16]
IV = SIG[16:32]
ms = b'cashcashcashcash'
goal = "flagflagflagflag"
conn.send(goal + "\n")
TT = INC + bytexor(ms, bytexor(IV, goal.encode()))
conn.send(TT.hex() + "\n")
print(conn.recvline())
conn.send(TT.hex() + "\n")
print(bytes.fromhex(TT.hex()))
print(conn.recvline())
print(conn.recvline())
cs


Hex Shift Cipher

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
from random import shuffle
from secret import secret_msg
 
ALPHABET = '0123456789abcdef'
 
class Cipher:
    def __init__(self, key):
        self.key = key
        self.n = len(self.key)
        self.s = 7
 
    def add(self, num1, num2):
        res = 0
        for i in range(4):
            res += (((num1 & 1+ (num2 & 1)) % 2<< i
            num1 >>= 1
            num2 >>= 1
        return res
 
    def encrypt(self, msg):
        key = self.key
        s = self.s
        ciphertext = ''
        for m_i in msg:
            c_i = key[self.add(key.index(m_i), s)]
            ciphertext += c_i
            s = key.index(m_i)
        return ciphertext
 
plaintext = b'The secret message is:'.hex() + secret_msg.hex()
 
key = list(ALPHABET)
shuffle(key)
 
cipher = Cipher(key)
ciphertext = cipher.encrypt(plaintext)
print(ciphertext)
 
# output:
# 85677bc8302bb20f3be728f99be0002ee88bc8fdc045b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a
 
cs


It's simple to see that the 'add' function is just XOR. We will brute force the key by backtracking. 

Basically, with the known parts of the plaintext, we have pieces of information like $key(key^{-1}(m_i) \oplus s) = c_i$. 

If $key^{-1}(m_i)$ are known, then we can figure out $key^{-1}(c_i)$ and vice-versa.

If this information is contradictory to the previous assumption of our key, we can stop the backtracking.

If we have no idea on $key^{-1}(m_i)$ and $key^{-1}(c_i)$, we can brute force what their value will be. 

If we have the complete key, it's straightforward to decrypt the given output. Select those that can be cleanly decrypted.


Also, now we can obviously see what the "linear algebra solution" is. Seems like a lot of work to be honest...

My code seems to have a few buggy pieces, but it got the job done so I didn't bother to fix it.


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
def fr(x):
    if 0 <= x and x <= 9:
        return chr(ord('0'+ x)
    return chr(ord('a'+ x - 10)
 
def cv(x):
    if ord('0'<= ord(x) <= ord('9'):
        return ord(x) - ord('0')
    else:
        return ord(x) - ord('a'+ 10
 
def finisher(key, s):
    ct = 'b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a'
    pt = ""
    for i in range(len(ct)):
        ot = cv(ct[i])
        myidx = key.index(ot) ^ s
        m_i = key[myidx]
        pt += fr(m_i)
        s = myidx
    print(bytes.fromhex(pt))
 
def solve(key, s, res, cts, idx):
    if idx == len(res):
        # print("found", key, s)
        finisher(key, s)
        return
    p = cv(res[idx])
    q = cv(cts[idx])
    ## key[index(p) ^ s] == q
    if p in key:
        if key[key.index(p) ^ s] != -1 and key[key.index(p) ^ s] != q:
            return
        it = key.index(p) ^ s
        key[it] = q 
        solve(key, key.index(p), res, cts, idx+1)
        key[it] = -1
    if q in key:
        it = key.index(q) ^ s
        if key[it] != -1 and key[it] != p:
            return
        key[it] = p
        solve(key, key.index(p), res, cts, idx+1)
        key[it] = -1
    for i in range(016):
        if key[i] == -1 and key[i ^ s] == -1:
            key[i] = p
            key[i ^ s] = q
            solve(key, key.index(p), res, cts, idx+1)
            key[i] = -1
            key[i ^ s] = -1
 
res = '54686520736563726574206d6573736167652069733a'
cts = '85677bc8302bb20f3be728f99be0002ee88bc8fdc045'
 
key = [-1* 16
= 7
solve(key, s, res, cts, 0)
cs


Cosmic Rays

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
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
from os import urandom
 
flag = open('flag.txt''rb').read().strip()
flag = flag.lstrip(b'DUCTF{').rstrip(b'}')
assert len(flag) == 32
 
KEY = urandom(16)
 
def encrypt(msg, key, p0, c0):
    msg = pad(msg, 16)
    blocks = [msg[i:i+16for i in range(0len(msg), 16)]
 
    out = b''
 
    for p in blocks:
        c = strxor(p, c0)
        c = AES.new(key, AES.MODE_ECB).encrypt(c)
 
        out += strxor(p0, c)
 
        c0 = c
        p0 = p
 
    return out
 
msg = 'If Bruce Schneier multiplies two primes, the product is prime. On a completely unrelated note, the key used to encrypt this message is ' + KEY.hex()
ciphertext = encrypt(msg.encode(), KEY, flag[16:], flag[:16])
 
print('key = ' + KEY.hex())
print('ciphertext = ' + ciphertext.hex())

## ke▒ = 0▒9d0fe1920ca▒85e3851b162b8cc9▒5 ## ci▒her▒ext = ed5dd65ef5ac36e886830cf006359b300▒1▒▒7▒▒▒▒▒▒c▒▒▒▒▒a▒▒▒▒▒8▒▒▒▒▒▒▒d6▒▒▒▒▒7▒▒▒▒b▒▒▒▒2▒▒▒▒▒▒▒▒▒f▒d▒0▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒6▒▒▒▒▒▒▒▒▒▒▒▒▒f▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒d▒▒b▒▒▒a▒▒▒▒▒e▒▒c▒▒▒▒▒2▒▒▒▒▒▒▒▒▒▒0▒▒3▒0c▒▒f▒▒▒▒▒▒▒▒▒▒▒▒1▒▒7▒▒▒▒▒▒▒▒▒▒▒▒▒1e▒▒0▒0▒▒▒▒▒9▒▒c▒▒e▒▒2▒▒4▒▒▒▒7▒▒▒▒▒0▒▒▒▒▒4▒▒▒▒▒▒▒▒f▒▒▒7▒▒▒▒▒e▒b▒▒9▒▒▒▒4▒f▒▒1▒c▒▒6▒0a▒3a0e6▒d7▒975d▒1cde66e41791b▒780988c9b8329

 
cs


Let's analyze the encryption process first. Given the padded message $P_1 P_2 \cdots P_n$, we see that $C_i = E_K(P_i \oplus C_{i-1})$, and the $i$th output block is $O_i = C_i \oplus P_{i-1}$. Since the key bytes and the latter parts of the output are quite known, we will start by figuring them all out. There are five unknowns in the hex data of the key and the final block (32 hex digits) of the output. We brute-force all $2^{20}$ combinations. How do we verify correctness? Since $C_n = O_n \oplus P_{n-1} = E_K(P_n \oplus C_{n-1})$, we see that $O_{n-1} = C_{n-1} \oplus P_{n-2} = D_K(O_n \oplus P_{n-1}) \oplus P_n \oplus P_{n-2}$. We know partial outputs of $O_{n-1}$, so we compare the known values of $O_{n-1}$ and $D_K(O_n \oplus P_{n-1}) \oplus P_n \oplus P_{n-2}$. Turns out that this is enough to uniquely determine all five unknowns. 


Now that we know all plaintext data, key, and the final block of output, we can use the above formula to completely decide the output value. Now we can work on finding $P_0$ and $C_0$. We may find $C_2 = O_2 \oplus P_1$. Then $C_1 = D_K(C_2) \oplus P_2$, $C_0 = D_K(C_1) \oplus P_1$. Now to find $P_0$, we use $P_0 = O_1 \oplus C_1$. This solves the problem. Unfortunately, my code is a bit dirty. You can still see all the key ideas.


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
## part 1 : brute force to find the key and final 32 bytes of output
def solve(KEY):
    msg = 'If Bruce Schneier multiplies two primes, the product is prime. On a completely unrelated note, the key used to encrypt this message is ' + KEY
    msg = msg.encode()
    msg = pad(msg, 16)
    CV = ctxt[-32:]
    for i in range(016):
        for j in range(016):
            CVV = CV[0:4+ cc[i] + CV[5:18+ cc[j] + CV[19:]
            c_n = bytes.fromhex(CVV)
            c_n_1 = AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(strxor(c_n, msg[-32:-16]))
            c_n_1 = strxor(c_n_1, msg[-16:])
            c_n_1 = strxor(c_n_1, msg[-48:-32])
            found_c = False
            tt = c_n_1.hex()
            for k in range(032):
                if ctxt[-64+k] != '▒' and ctxt[-64+k] != tt[k]:
                    found_c = True
                    break
            if found_c == False:
                print("found!", KEY, i, j)
 
for i in range(016):
    for j in range(016):
        for k in range(016):
            KEY = key0 + cc[i] + key1 + cc[j] + key2 + cc[k] + key3
            solve(KEY)
 
## part 2 : recover entire output
KEY = '0b9d0fe1920ca685e3851b162b8cc9e5'
## change the final 32 hex data of 'ciphertext' accordingly 
 
for i in range(110):
    if i == 1:
        CVV = ctxt[-32*i : ]
    else:
        CVV = ctxt[-32*i : -32*(i-1)]
    c_n = bytes.fromhex(CVV)
    print(len(c_n))
    print(len(msg[-16*(i+1):-16*i]))
    c_n_1 = AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(strxor(c_n, msg[-16*(i+1):-16*i]))
    if i == 1:
        c_n_1 = strxor(c_n_1, msg[-16*i:])
    else:
        c_n_1 = strxor(c_n_1, msg[-16*i:-16*(i-1)])
    c_n_1 = strxor(c_n_1, msg[-16*(i+2):-16*(i+1)])
    ctxt = ctxt[0:-32*(i+1)] + c_n_1.hex() + ctxt[-32*i:]
 
## part 3 : recover answer
ctxt = 'ed5dd65ef5ac36e886830cf006359b300112c744b0aac58207aea28e804ec6abd6e5c397d1d4bd6f42539db06aff5de0a45d08c7dee9da217412bb6edcdab75f3096f135f702fdda23b764c1bfde3b103a1fe35ed6c0b03d2e1a8badb6c04e330c0dff963317506a110a742feea43cf2ed1e8e0f0f5e33993c8ee28200461ad755fca0ebd654e6962862f31270f414eab7c9076140feb15c1e690a83a0e60d75975d21cde66e41791b8780988c9b8329'
c_2 = strxor(bytes.fromhex(ctxt[32:64]), msg[0:16])
c_1 = strxor(AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(c_2), msg[16:32])
c_0 = strxor(AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(c_1), msg[0:16])
p_0 = strxor(bytes.fromhex(ctxt[0:32]), c_1)
print(c_0 + p_0)
cs

 

impECCable

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
#!/usr/bin/env python3.8
 
import ecdsa
import random
import hashlib
 
Curve = ecdsa.NIST384p
= Curve.generator
= Curve.order
 
flag = open('flag.txt''r').read().strip()
auth_msg = b'I know alll of your secrets!'
 
def inv(z, n=n):
    return pow(z, -1, n)
 
def gen_keypair():
    d = random.randint(1, n-1)
    Q = d*G
    return d, Q
 
def sign(msg, d):
    x = int(hashlib.sha1(int.to_bytes(d, 48, byteorder='big')).hexdigest(), 16) % 2**25
    while True:
        k1 = (random.getrandbits(340<< 25+ x
        k2 = (random.getrandbits(340<< 25+ x
        r1 = (k1*G).x()
        r2 = (k2*G).y()
        if r1 != 0 or r2 != 0:
            break
    h = int(hashlib.sha384(msg).hexdigest(), 16)
    s = inv(k1)*(h*r1 - r2*d) % n
    return (r1, r2, s)
 
def verify(msg, Q, sig):
    if any(x < 1 or x >= n for x in sig):
        return False
    r1, r2, s = sig
    h = int(hashlib.sha384(msg).hexdigest(), 16)
    v1 = h*r1*inv(s)
    v2 = r2*inv(s)
    x1 = (v1*+ (-v2 % n)*Q).x()
    return (x1 - r1) % n == 0
 
def menu():
    m = '''Here are your options:
    [S]ign a message
    [V]erify a signature
    [P]ublic Key
    [Q]uit'''
    print(m)
    choice = input()[0].lower()
    if choice == 's':
        print('Enter your message (hex):')
        msg = bytes.fromhex(input())
        if len(msg) >= 8:            
            print('Message too long!')
            exit()
        sig = sign(msg, d)
        print(' '.join(map(str, sig)))
    elif choice == 'v':
        print('Enter your message (hex):')
        msg = bytes.fromhex(input())
        print('Enter your signature:')
        sig = [int(x) for x in input().split()]
        if verify(msg, Q, sig):
            if msg == auth_msg:
                print('Hello there authenticated user! Here is your flag:', flag)
                exit()
            else:
                print('Verified!')
        else:
            print('Invalid Signature!')
    elif choice == 'p':
        print(Q.x(), Q.y())
    else:
        print('Oh ok then... Bye!')
        exit()
 
d, Q = gen_keypair()
 
print('Welcome to my impECCable signing service.')
for _ in range(11):
    menu()
 
cs


So we have to forge a signature. Let's try that by finding the private key $d$. 

Let's take a look at the signature scheme. $x$, while unknown, is always fixed for each signature.

$h$ is a hash of the message, so we know this value too. We are also given $r_1, r_2, s$ as a result of the signature.

So let's take a look at the last equation $s \equiv k_1^{-1} \cdot (hr_1 - dr_2) \pmod{n}$. 

We already know $r_1, r_2, s, h$, so the unknowns are $k_1$ and $d$. Note that $d$ is also always fixed.


Also, note that $k_1 = small \cdot 2^{25} + x$, where $small$ is around $2^{340}$, far less than $n$.

Taking this into account, we can rewrite our equation as follows: $$ k_1 s \equiv hr_1 - dr_2 \pmod{n}$$ $$ (small \cdot 2^{25} + x) s \equiv hr_1 - dr_2 \pmod{n}$$ $$ - 2^{-25}s^{-1} r_2 d + 2^{-25}s^{-1} hr_1 \equiv small + x \cdot 2^{-25} \pmod{n}$$ This starts to look like a hidden number problem! But the $x$ variable seems like a problem. 


It doesn't matter, since there are 10 such equations, and we can subtract two of them to get 9 (or more?) equations without $x$. 

Now it resolves into solving $A_i x + B_i \equiv small \pmod{n}$ for some known $A_i, B_i$. I'm sure there are many ways to solve this, but the method I enjoy is to use LLL + Babai's Closest Vector Algorithm. Check the implementation below. For details, ask in comments :)


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
def rhexc():
    t = random.randrange(016)
    if t <= 9:
        return chr(ord('0'+ t)
    if t >= 10:
        return chr(ord('a'+ t - 10)
 
conn.recvline()
msgs = []
= []
r1 = []
r2 = []
= []
for i in range(010):
    conn.recvline()
    conn.recvline()
    conn.recvline()
    conn.recvline()
    conn.recvline()
    conn.send("S\n")
    conn.recvline()
    msg = rhexc() + rhexc() + rhexc() + rhexc()
    msgs.append(bytes.fromhex(msg))
    hh = int(hashlib.sha384(bytes.fromhex(msg)).hexdigest(), 16)
    h.append(hh)
    conn.send(msg + "\n")
    T = conn.recvline().split()
    r1.append(int(T[0].decode()))
    r2.append(int(T[1].decode()))
    s.append(int(T[2].decode()))
 
= open("data.txt""w")
 
def goprint(t, s):
    f.write(s + " = [")
    for i in range(len(t)):
        f.write(str(t[i]))
        if i != len(t) - 1:
            f.write(", ")
    f.write("]")
 
goprint(h, "h")
f.write("\n")
goprint(r1, "r1")
f.write("\n")
goprint(r2, "r2")
f.write("\n")
goprint(s, "s")
f.write("\n")
f.close()
print("DONE")
 
= int(input())
= int(input())
= int(input())
 
conn.recvline()
conn.recvline()
conn.recvline()
conn.recvline()
conn.recvline()
cs


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
import hashlib
import random
 
def Babai_closest_vector(M, G, target):
        small = target
        for _ in range(1):
            for i in reversed(range(M.nrows())):
                c = ((small * G[i]) / (G[i] * G[i])).round()
                small -=  M[i] * c
        return target - small  
 
def sign(msg, d):
    x = int(hashlib.sha1(int.to_bytes((int)(d), 48, byteorder='big')).hexdigest(), 16) % 2**25
    while True:
        k1 = (random.getrandbits(340<< 25+ x
        k2 = (random.getrandbits(340<< 25+ x
        r1 = (k1*G).xy()[0]
        r1 = (int)(r1)
        r2 = (k2*G).xy()[1]
        r2 = (int)(r2)
        if r1 != 0 or r2 != 0:
            break
    r1 = (int)(r1)
    r2 = (int)(r2)
    d = (int)(d)
    h = int(hashlib.sha384(msg).hexdigest(), 16)
    s = ((int)(inverse_mod(k1, n)*(h*r1 - r2*d))) % n
    return (r1, r2, s)
 
= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF
= EllipticCurve(GF(p), [-30xB3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF])
= 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
= E(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab70x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f)
 
= Matrix(ZZ, 1010)
 
= [23373110631075193719266457389414979915652067802760928444766935944879643632295509247045983611079293484112015812298424811003402020297682803985280385324059294547276381651936828219428316450314628727089306406877936309521585868406250470175316885109379804821688072632290173800758739631603772082754507195286366672698956794660328935945376515222833227166743604799661784305629457905658453013644199233256000811172566174284088964733098321266328817522944101159806550053672465111272134849660563344197668625651398585469230739650422640053316031881717853156318362750855003467577550566014131759397129217522833947829971970831549610408465678755851766156002824392132712585346344907951634422061454339288046940644971842355048565966108823133336040004731331511816813546177398663640071161623005240948090128405051134442180445829093516536128496735302713412781192449440072502796901684384799422985608472930590031587697602766375490458840116389733463012282962827788632952803218754973100280759480653668967733390339433130095532033058453861213887392525350002069192823299958647615008843981182040291480007346492436282071178418873478338505839724866567471088415321631607204728733513138973751666571]
r1 = [125792098081893129153271320012769944462551723285005006959449898897110628589831637412713099922720775501248695056553817513277357285561480579177542964843200136945674434297199648445568840598439313878617162347254052095342876235191554585371112946404190387697534646035651694165960225187891433236446686273017304702714837212569297073575677253044266881569331352105137929972597744016411888049220372925675806096677491319577734959841100142754252499792455324441192018313181788861780723987416598640431710927060042829654174074330726326454191648747289766855935722741692751443902685950187836527761407228814320863611585879580881526756177120011066949498954824121650008685326439038329973891388684478285112725357277297239579671831365646495939802272274337333539026578608949371807361019158565975131738819215458209990534022768120947364956988030862701298496872632133592704536625686657579967644830046483396779789062671782387408609718000755429523017378123303513703344050232181913631490791674903898631849071077766234175757327699143730753085218136678616919597070926672624169019517838564518311384425555195298893854856387163253094963173848316296091845329567038393753791750586302201087]
r2 = [3362705797849617878647365660985990566049333116696565173083098561696239463413527201559140422082923583525045722549763141450603545235890592161947671375787238986673424728720893211406121188302943965521929149121089641707209293057354158732989615888199480368584527145692972209296417979002891123443603039793642553264887018294420846216950155955789642333100828295713529327846754165290558634286334350103809603649440117629677663367232344783261643275422157945835517134018581552983232074211022157684373593413491443701555835520155282447333430511575840945023689199790120796429677083420888294071248636436860822091936553328528390089880429533444443531710524149018078316986247996206863971158222206750312356490848712172376087957939144239533590664428657297700738539681962241559027660276255529486815550264413927604748955534219627695392709789759941452590018545869438658483068512455482025841857198895843042152803170787159084628080664335181269308125493421502567998605288977656406462044757435916248144031525271978912293359297469713007462661888882462608763155490069178131458354800313627611820028529141092961133175220661883156536844963568120403379640053999048076879854251402929920752081]
= [1792511144039689273903318752137759745462143141098725137682093678306382426947223215585139337546865928300998266784866921853582586273412881491430100511011448648027948649700911052731210656190304335253416414001734385549707694334614279337191062203044109887767816880312389937164819418360232444378873250244702401402032266378069632021381398013152392371690741750780140406543650726899558630187881571728484688257236195175292572653350501942804007412488781203027946839496288064549008191186974448720552805518713886102427259103015212058052428442526766077687194058156203185631325913298446956209002848029443869407894949511190324333919423549809323005416077239725402202176445509601055803223037148237908166958921603025703610354773191595397225912857234424274497331129500961893925842562869928957637655440191485239263057624366236967535250892306702204257161647804357938419519035520998074047145026561330719294866708077896328061665323777575601890535226293858114869057076473182768127774574760476876569030100124465903751052999236746448650991848633734951138686868470982950133302053638667654050592244700225839457979855163938098516151926858754963517053234739223403629384061080926568390283532]
 
iv = inverse_mod(2 ** 25, n)
 
for i in range(09):
    M[0, i] = (((inverse_mod(s[i+1], n) * r2[i+1- inverse_mod(s[0], n) * r2[0]) * iv) % n) * n
    M[i+1, i] = n * n
M[09= 1
 
Target = [0* 10
for i in range(09):
    Target[i] = (((inverse_mod(s[i+1], n) * r1[i+1* h[i+1- inverse_mod(s[0], n) * r1[0* h[0]) * iv) % n) * n
Target[9= 2 ** 383
 
= M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
print(TT[9]) ## d
 
sec = b'I know alll of your secrets!'
= sign(sec, TT[9])
print(X[0])
print(X[1])
print(X[2])
cs


LSB || MSB Calculation Game

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
#!/usr/bin/env python3
from os import urandom
from random import randint
 
print('Welcome! As you may know, guessing is one of the most important skills in CTFs and in life in general. This game is designed to train your guessing skills so that you\'ll be able to solve any CTF challenge after enough practice. Good luck!\n')
 
class LCG:
    M = 937954372991277727569919570466170502903005281412586514689603
    a = randint(2, M-1)
    c = randint(2, M-1)
    print(f'M = {M}')
    print(f'a = {a}')
    trunc = 20
 
    def __init__(self, x0):
        self.x = x0
 
    def next(self):
        self.x = (self.a * self.x + self.c) % self.M
        return ((self.x % 2**self.trunc) << self.trunc) + (self.x >> (self.M.bit_length() - self.trunc))
 
NUM_GUESSES = 5 # higher chances of winning!!
rng = LCG(int(urandom(25).hex(), 16))
wins = 0
 
for r in range(124):
    try:
        num = rng.next()
        print('Round ' + str(r) + '. What\'s the lucky number? ')
        guesses = [int(guess) for guess in input().split(' ')[:NUM_GUESSES]]
        if any(guess == num for guess in guesses):
            print('Nice guess! The number was', num)
            wins += 1
        else:
            print('Unlucky! The number was', num)
    except ValueError:
        print('Please enter your three numbers separated by spaces next time! e.g. 123 1337 999')
        exit()
 
if wins > 10:
    print('YOU WIN! Your guessing skills are superb. Here\'s the flag:'open('flag.txt''r').read().strip())
else:
    print('Better luck next time :(')
 
cs


This is yet another LCG breaking with lattices :) Basically we are given 20 LSB and 20 MSB of each number.

We can such number as $2^{180} \cdot a_i + 2^{20} \cdot small + b_i$, where $a_i, b_i$ are known and $small$ is around $2^{160}$. 

We know $a$, but we do not know $c$. Denote the 0th number as $x$. Then our next numbers will be $ax+c$, $a^2x+(a+1)c$, $\cdots$ $, a^n x + (a^{n-1} + \cdots + 1)c$. Therefore, our goal here is to solve the set of equations $$ a^k x + (a^{k-1} + \cdots + 1) c \equiv 2^{180} a_k + 2^{20} \cdot small + b_k \pmod{m} $$ $$ 2^{-20} a^k x + 2^{-20}(a^{k-1} + \cdots + 1) c - 2^{-20}(2^{180} a_k + b_k) \equiv small \pmod{m}$$ for each $k$. This is yet another hidden number problem, so we can set up a similar procedure as the above problem. However, the bounds are kinda tight, so we have to optimize a little bit. Refer to the following code, and leave comments if there are parts you don't understand. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
print(conn.recvline())
print(conn.recvline())
print(conn.recvline())
print(conn.recvline())
 
num = []
for i in range(124):
    if i <= 12:
        conn.recvline()
        conn.send("0\n")
        T = conn.recvline()
        cc = 'Unlucky! The number was '
        T = T[len(cc):-1]
        T = T.decode()
        num.append(int(T))
    if i == 12:
        print(num)
    if i >= 13:
        conn.recvline()
        x = int(input())
        conn.send(str(x) + " " + str(x) + "\n")
        conn.recvline()
print(conn.recvline())
cs


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
def Babai_closest_vector(M, G, target):
        small = target
        for _ in range(1):
            for i in reversed(range(M.nrows())):
                c = ((small * G[i]) / (G[i] * G[i])).round()
                small -=  M[i] * c
        return target - small  
 
= 937954372991277727569919570466170502903005281412586514689603
= 340191373049582240414926177838297382326391494482892283959227
num = [766060457621362859134107548649301417190636173195700955483003856434851034009926669141095280053170105685083393701621243850981672150015408709955639]
 
low = []
upp = []
for x in num:
    low.append(x >> 20)
    upp.append(x % (2 ** 20))
 
mult_1 = [a]
mult_2 = [1]
 
for i in range(112):
    mult_1.append((a * mult_1[i-1]) % n)
    mult_2.append((a * mult_2[i-1+ 1) % n)
 
= Matrix(ZZ, 1414)
iv = inverse_mod(2 ** 20, n)
 
for i in range(012):
    M[0, i] = ((int)(mult_1[i] * iv % n)) * n
M[012= 1
 
for i in range(012):
    M[1, i] = ((int)(mult_2[i] * iv % n)) * n
M[113= 1
 
for i in range(012):
    M[i+2, i] = n * n
 
Target = [0* 14
for i in range(012):
    Target[i] = (((2 ** 160* upp[i] + iv * low[i]) % n + (2 ** 159)) * n
Target[12= n // 2
Target[13= n // 2
               
= M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
= TT[12]
= TT[13]
 
for i in range(124):
    x = (a * x + c) % n
    if i <= 12:
        print(x % (2 **  20== low[i-1])
        print((x >> 180== upp[i-1])
    if i >= 13:
        print( ((x % (2 ** 20)) << 20+ (x >> 180)) 
cs


l337crypt

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
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
 
flag = open('flag.txt''rb').read().strip()
 
p, q = getPrime(1337), getPrime(1337)
= p*q
 
= (1*3*3*7)^(1+3+3+7)
hint = int(D*sqrt(p) + D*sqrt(q))
 
= randint(1337, n)
while 1337:
    lp = legendre_symbol(x, p)
    lq = legendre_symbol(x, q)
    if lp * lq > 0 and lp + lq < 0:
        break
    x = randint(1337, n)
 
= map(int, bin(bytes_to_long(flag))[2:])
= []
for b in m:
    while 1337:
        r = randint(1337, n)
        if gcd(r, n) == 1:
            break
    c.append((pow(x, 1337 + b, n) * pow(r, 1337+1337, n)) % n)
 
print(f'hint = {hint}', f'D = {D}', f'n = {n}', f'c = {c}', sep='\n')
 
cs


We assume that $p<q$ in the following analysis. It's easy to see that it doesn't matter.


First, the obvious part. Since $x$ is a quadratic non-residue modulo $p$ and $q$, we easily see that the appended value in the ciphertext is a quadratic residue modulo $n$ if and only if $b=1$. This can be determined with legendre symbols if we know the factorization of $n$.


The only hint here is the bounds on $D(\sqrt{p} + \sqrt{q})$. With this bound, we can easily manipulate the inequalities to get a bound on $p+q$, so eventually a bound on $q$ using quadratic equations and the knowledge of $n$.


Now this is a good time to use coppersmith's attack. Assume that we derived $L \le q \le R$. 

Set $f(x) = x + L$, set a bound $X = R - L$, then perform sage's small_roots() algorithm.

However, like rbtree wrote in the coppersmith attack tutorial (Korean, check the blog) we need to carefully select $\beta$ and $\epsilon$. 

We are working with $q$, so $\beta = 0.5$ is fine. Doing some calculations, we see that $n$ is around 2674 bits and $R-L$ is around 600 bits. 

We do some math and find $\epsilon = 0.02$ to be sufficient. This provides a slow, yet guaranteed solution in sage. Full code is below. 


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
## kth root of n, (integer rounded) using binary search
def kthp(n, k):
    lef = 1
    rig = 2
    while rig ** k < n:
        rig = rig << 1
    while lef <= rig:
        mid = (lef + rig) // 2
        if mid ** k >= n:
            best = mid
            rig = mid - 1
        else:
            lef = mid + 1
    return best        
 
hint = 49380072119923666878249192613131592074839617141388577115293351423167399196342955381916004805107462372075198711094652660372962743330048982663144511583693085794844754920667876917018671057410534100394910738732436580386544489904637
= 15515568475732467854453889
= 6337195756161323755030821007055513472030952196189528055855325889406457327105118920711415415264657259037549360570438684177448730672113983949019501534456306880443480045757556693491657382839313528872206247714019569057234809244745178637139314783799705976807860096251357543835678457306901513720623505353691449216464755029227364954566851544050983088509816181294050114090489118245225264446360947782705558298586215673137402419393055466097552149369002210996708260599901728735979196557443301850639382966378922196935480476418239903494619475397129088135961432456212959427154766737697387874383258702208776154403167756944619240167487825357079536617150547060929824469887270443261440975473300946304087345552321787097829023298865763114083681766490064879774973163395320826072815425507105417077348332650202626344592023021273
 
## hint / D <= sqrt(p) + sqrt(q) <= (hint + 1) / D
= (hint * hint) // (D * D) - 2 * kthp(n, 2)
= (hint * hint + 2 * hint + 1// (D * D) - 2 * kthp(n, 2)
= int(X)
= int(Y)
## small p + q = Y
lr = (X + kthp(X * X - 4 * n, 2)) // 2
sm = (Y + kthp(Y * Y - 4 * n, 2)) // 2
 
sm = int(sm)
lr = int(lr)
df = sm-lr
assert df >= 0
print((int)(df).bit_length())
 
= Zmod(n)
P.<x> = PolynomialRing(K, implementation='NTL')
= x + lr
 
= f.small_roots(X = 2**600, beta=0.5, epsilon = 0.02)
print(T) ## T[0] + lr is a factor of n
 
for x in c:
    if pow(x, (p-1// 2, p) == 1 and pow(x, (q-1// 2, q) == 1:
        s += '1'
    else:
        s += '0'
 
= int(s, 2)
print(long_to_bytes(s))
cs


  1. mathboy7 2020.10.08 09:20

    ECDSA 문제에서 Lattice를 만들 때 왜 모든 식에 n이 곱해져 있는 건가요?

    • 사용자 rkm0959 2020.10.08 10:37 신고

      이론적인 근거는 사실 저도 잘 모르고, 실험적으로 저렇게 하니까 잘 되는 것 같더라구요 ㅋㅋ 제 직관은 격자의 각 벡터의 마지막 entry가 d를 편하게 복구하려고 있는 거지 사실 원하는 CVP 문제의 일부라고 보기는 어려워서 (원하는거는 첫 9개의 entry가 target에 가깝도록 하는 것이니까) 그냥 첫 9개의 entry에 대한 행렬 원소 및 target vector에다가 scale을 오지게 크게 주면 잘 되겠다~ 정도인 것 같아요

      쓰고 보니까 설명 참 못쓰네여


참가팀들 중 2번째로 올솔브를 찍어서 해피엔딩으로 끝냈다. 나는 Crypto 문제를 맡았고 결과적으로 5문제를 풀었다.


Ciphertexts


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
from Crypto.Util.number import *
import gmpy2
from flag import flag
 
= getPrime(512)
= getPrime(512)
= getPrime(512)
n1 = p * q
n2 = p * q * r
 
e1 = getPrime(20)
e2 = int(gmpy2.next_prime(e1))
 
= bytes_to_long(flag)
c1 = pow(m, e1, n1)
c2 = pow(m, e2, n2)
 
print("n1 = {}".format(n1))
print("n2 = {}".format(n2))
print("e1 = {}".format(e1))
print("e2 = {}".format(e2))
print()
print("c1 = {}".format(c1))
print("c2 = {}".format(c2))
 
'''
n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223
n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749
e1 = 745699
e2 = 745709
c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818
c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546
'''
cs


$n_1, n_2$를 알고 있으니 $r$을 얻을 수 있다. $m^{e_2} \pmod{r}$도 알고 있으니 여기서 $m \pmod{r}$을 알 수 있다.

또한, $m^{e_1} \pmod{n_1}$과 $m^{e_2} \pmod{n_1}$을 알고 있으니, $e_1d_1 + e_2d_2 = 1$인 $d_1, d_2$를 찾아서 $m \pmod{n_1}$도 구할 수 있다. 

이제 중국인의 나머지 정리로 두 정보를 합치면 flag를 얻는다. 수식 잘 가지고 노는 문제 :)

 

1
2
3
4
5
6
7
8
= n2 // n1
= inverse(e2, r - 1)
mr = pow(c2, d, r)
d1 = inverse(e1, e2)
d2 = (e1 * d1 - 1// e2
mn1 = pow(c1, d1, n1) * inverse(pow(c2, d2, n1), n1) % n1
u, v = CRT(mn1, n1, mr, r)
print(long_to_bytes(u))
cs


No Pressure


1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Cipher import ARC4
from hashlib import sha256
from base64 import b64encode
import zlib
import os
 
flag = open("./flag.txt""rb").read()
 
nonce = os.urandom(32)
while True:
    m = input("message: ")
    arc4 = ARC4.new(sha256(nonce + m.encode()).digest())
    c = arc4.encrypt(zlib.compress(flag + m.encode()))
    print("encrypted! :", b64encode(c).decode())
cs


사실 거의 비슷한 문제가 CryptoHack에 있어서 풀이를 쓰기가 조금 애매하긴 하다 ㅋㅋ

문제 이름에서도 나오듯이 compression이 적용되었다는 것을 활용하는 문제이다. 

대충 직관적으로 넣어준 메시지와 flag의 공통 prefix가 크다면 압축이 더 많이 되어 ciphertext의 길이가 작다는 것이다.

flag가 'KosenCTF{' 으로 시작된다는 것은 알고 있으니, 여기에 문자를 하나씩 추가해보며 작은 ciphertext를 찾는 것을 반복하면 된다.


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
HOST = "misc.kosenctf.com"
PORT = 10002
 
conn = pwnlib.tubes.remote.remote(HOST, PORT)
 
solution = "KosenCTF{"
chars = [chr(x) for x in range(32128)]
dumb = ';'
 
while True:
    p = (solution + dumb) * 5
    r = conn.send(str.encode(p + "\n"))
    res = conn.recvline()
    res = res[22:-1]
    res = base64.b64decode(res)
    res = len(res)
    ## print(res)
    for c in chars:
        ntry = (solution + c) * 5
        r = conn.send(str.encode(ntry + "\n"))
        r = conn.recvline()
        r = r[22:-1]
        r = base64.b64decode(r)
        r = len(r)
        ## print(r)
        if r < res:
            res = r
            solution += c
            print(solution)
            if c == "}":
                print(solution)
                exit()
            break
cs


BitCrypto


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
from Crypto.Util.number import *
from secret import flag
 
def legendre_symbol(x, p):
    a = pow(x, (p-1// 2, p)
    if a == 0:
        return 0
    elif a == 1:
        return 1
    else:
        return -1
 
def key_gen(bits):
    p = getPrime(bits)
    q = getPrime(bits)
    n = p * q
 
    while True:
        z = getRandomRange(2, n)
        a, b = legendre_symbol(z, p), legendre_symbol(z, q)
        if a == -1 and b == -1:
            break
 
    return (n, z), (p, q)
 
def enc(pubkey, m):
    n, z = pubkey
    bits = [int(b) for b in "{:b}".format(m)]
 
    c = []
    for b in bits:
        while True:
            x = getRandomRange(2, n)
            if GCD(x, n) == 1:
                break
        c.append( ((z**b) * (x**2)) % n )
    return c
 
def dec(privkey, c):
    p, q = privkey
    m = ""
    for b in c:
        if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1:
            m += "0"
        else:
            m += "1"
    return int(m, 2)
 
def main():
    pubkey, privkey = key_gen(256)
 
    keyword = "yoshiking, give me ur flag"
    m = input("your query: ")
    if any([c in keyword for c in m]):
        print("yoshiking: forbidden!")
        exit()
 
    if len(m) > 8:
        print("yoshiking: too long!")
        exit()
 
    c = enc(pubkey, bytes_to_long(m.encode()))
    print("token to order yoshiking: ", c)
 
    c = [int(x) for x in input("your token: ")[1:-1].split(",")]
    if len(c) != len(set(c)):
        print("yoshiking: invalid!")
        exit()
 
    if any([x < 0 for x in c]):
        print("yoshiking: wow good unintended-solution!")
        exit()
 
    m = long_to_bytes(dec(privkey, c))
    if m == keyword.encode():
        print("yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~")
        print(flag)
    else:
        print(m)
        print("yoshiking: ...?")
 
 
if __name__ == '__main__':
    main()
 
cs


뭔가 길게 생겼는데 코드부터 대충 해석해보자.

  • KeyGen: 소수 $p, q$를 고르고 $n = pq$라 한자. $z$는 $p, q$ 모두에 대해 이차비잉여이다.
  • 이 과정에서 public key는 $n, z$이며, private key는 $p, q$이다.
  • Encryption: 메시지를 이진법으로 쓰고 $0$을 위해서는 이차잉여, $1$을 위해서는 이차비잉여를 추가한다.
  • Decryption: 르장드르 기호를 직접 계산하여 주어진 값에서 $0$, $1$을 복원한다.
  • 목표: 플래그 내놓으라는 저 문장이 복호화 결과가 되도록하는 암호문을 만들라는 것이다.
  • 단, 암호문의 각 정수는 모두 서로 달라야 하며, 음수면 안된다.
  • 쿼리를 날릴 수도 있는데 문제를 날로 먹을 수는 없고 쿼리의 길이에도 제한이 있다.

이러면 문제가 풀렸다. 사실 encryption을 못하는 이유는 그냥 우리가 $n$도 모르고 $z$도 몰라서다.

그런데 애초에 $n, z$을 몰라도 $\pmod{n}$에 대한 이차잉여/비이차잉여를 만드는 것은 쉽다. 

  • 이차잉여: 그냥 제곱수를 하나 보내주면 된다.
  • 비이차잉여: 정수 하나를 잡고 비이차잉여라고 기도하자. 이 값에 제곱수를 곱하면 된다.
  • 비이차잉여를 뽑을 확률은 든든하게 높으니까 별로 기도하지 않아도 된다.
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
HOST = "crypto.kosenctf.com"
PORT = 13003
 
conn = pwnlib.tubes.remote.remote(HOST, PORT)
conn.send("@\n")
print(conn.recvline())
print(bytes_to_long("yoshiking, give me ur flag".encode()))
 
= 195139091440424100361889710829481093024970143303085039083610471
= bin(z)[2:]
= str(c)
 
= 2
res = ""
for t in c:
    if t == '0':
        q += 1
        res += str(q*q) + ","
    if t == '1':
        q += 1
        res += str(2*q*q) + ","
 
res = res[:-1]
print(res)
conn.send(res + "\n")
 
print(conn.recvline())
print(conn.recvline())
cs


PadRSA


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
import os
import signal
from binascii import unhexlify, hexlify
from Crypto.Util.number import *
from flag import flag
 
= os.urandom(8)
nonce = 1
 
= getPrime(256)
= getPrime(256)
= p * q
es = set()
 
def pad(x: bytes) -> bytes:
    global r, nonce
    y = long_to_bytes(r[0| nonce) + x + r
 
    nonce += 1
    r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
    return y
 
def encrypt(m: bytes, e: int-> bytes:
    m_ = bytes_to_long(pad(m))
    return long_to_bytes(pow(m_, e, n))
 
MENU = """
1. Encrypt the flag
2. Encrypt your message
3. EXIT
"""
 
signal.alarm(30)
print("n: {}".format(n))
 
while True:
    print(MENU)
    choice = input("> ")
    if choice not in ["1""2"]:
        break
 
    e = int(input("e: "))
    if not(3 <= e <= 65537):
        print("[-] invalid e")
        break
 
    if e in es:
        print("[-] e already used")
        break
 
    if choice == "1":
        m = flag
    if choice == "2":
        m = unhexlify(input("m: "))
 
    c = encrypt(m, e)
    print("c: {}".format(hexlify(c).decode()))
 
    es.add(e)
cs


뭔가 패딩이 있고 정신이 나갈 것 같다. 우선 주어진 코드부터 분석해보자.

  • $e$를 고른 뒤, flag의 ciphertext를 얻거나 임의의 메시지에 대한 ciphertext를 얻을 수 있다.
  • 하지만 한 번 사용한 $e$의 값은 다시 사용할 수가 없다.
  • 랜덤한 패딩처럼 생긴 뭔가를 쓰는데 사실 nonce의 값을 대놓고 알려줬다.
  • nonce 값을 안다는 것은 $r$을 구하기만 하면 그 뒤의 $r$ 값을 싹 다 구할 수 있다는 것이다.
  • $r$이 8 바이트인데 8 비트라고 생각해서 브루트포스하면 되는 줄 알았다 ㅋㅋ

$r$을 구해보자. 사실 $r$이 64 비트라는 점은 꽤 치명적인데, $r^3 < n$을 강제하기 때문이다.

그러니까 사실 빈 메시지와 $e=3$을 보내고 암호화 하라고 부탁하면 얘가 알아서 $r$을 갖다 바친다.


이제 $r$을 알았으니 문제를 풀 수 있다. $e=4, 5, 6, 7$에 대해서 flag의 암호문을 달라고 하자.

우리는 각 암호화 과정에서 사용된 $r, nonce$의 값을 전부 알고 있다. 그러니 우리가 얻은 정보는 사실상 $$ ( (r[0]|nonce) \cdot 2^{l(x) + 64} + 2^{64} \cdot x + r)^e \equiv c \pmod{n}$$ 형태로 쓸 수 있다. 여기서 $l(x)$는 flag의 길이이며, $x$는 flag 자체이다. 이는 결국 $x$가 여러 차수 낮은 $\mathbb{Z}_n$ 위의 다항식의 공통근임을 의미한다.

그러니 저 다항식들의 GCD를 구하면 된다. $l(x)$의 값을 모르지만 이 정도는 brute-force가 가능하다.

Sage에서 $\mathbb{Z}_n$ 위 다항식의 GCD를 지원하지 않는 것 같은데, 그냥 직접 구현하면 된다.

예전에 쓴 RSA 논문리딩에서 언급했듯이, 유클리드 호제법 과정이 망한다면 그때 $n$의 약수를 하나 얻을 수 있고, 이 경우에는 문제가 바로 풀린다.


첫 부분은 Python으로, 두 번째 부분은 Sage로 작성하였다.

pwntools를 살면서 처음 써봐서 통신 부분 코드가 지나치게 더럽고, 그래서 여기서는 생략했다.


Part 1 : $r$ 값 복원하고 $e=4,5,6,7$에 대한 flag의 ciphertext 얻기

아래 코드에서 kthp는 그냥 이분탐색으로 $k$th root를 구하는 코드이다.


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
= 13213917004013074941883923518155352500136040759518468945870343732851737037017858345555718553480688185605981252067134741952110065084206701357744511961587797
rg = 0x0ae26226b16dfc3ca101a1b750f38d0f131fff3c93f04a1222586f
= kthp(rg, 3)
= long_to_bytes(r)
= r[1:]
nonce = 1
 
print("For c4")
nonce += 1
= long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
 
print(r[0| nonce)
print(bytes_to_long(r))
 
print("For c5")
nonce += 1
= long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
 
print(r[0| nonce)
print(bytes_to_long(r))
 
print("For c6")
nonce += 1
= long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
 
print(r[0| nonce)
print(bytes_to_long(r))
 
print("For c7")
nonce += 1
= long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
 
print(r[0| nonce)
print(bytes_to_long(r))
 
c4 = 0x8043b337fd500f49ff23589ac40d6208d1ba5e8b6af341da6c63d4dc4af8944930cd5812076686450967c0b36a52b66e25a632d9b1780ca0195be15f81c7efe7
c5 = 0x13d464f1f4d139c78e8bbf20eaf9b7693a931e65649db09f259ffc9a17674d72187fb10b10ad3db629c0dcb7048cf9b836972320b0018edae6c0604bf9911a59
c6 = 0x0a7c1297094b925b4dcb42b001c2cfa9b0524939b4bb13048fb8e3778238e28b93c59b010ee2e45c7d7d25da69824a729141caf8c613e6dae1a8c08e153e5ae9
c7 = 0x5ee21f49be33499cce3a157a1ad55d3df5bce4ad99e90f8f91929c2a7a1a8f56a99bf69789137276eaac3294fd4b91fc1ee857eeb3544cd0c4f95be49ab3abd7
cs


Part 2: 다항식 GCD를 통해서 공통근 도출 (혹시 싶어서 $2^{64} \cdot x$를 변수로 잡았다)

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
def GCD(f, g, n):
    g = g % f
    if g == 0:
        return f
    t = g.lc()
    if gcd(t, n) != 1:
        print(t)
        exit()
    tt = inverse_mod(Integer(t), n)
    g = g * tt
    return GCD(g, f, n)
 
= 13213917004013074941883923518155352500136040759518468945870343732851737037017858345555718553480688185605981252067134741952110065084206701357744511961587797
= Zmod(n)
P.<x> = PolynomialRing(K, implementation='NTL')
t4 = 179
b4 = 12905559065630283676
t5 = 103
b5 = 7364374057551015739
t6 = 204
b6 = 14728748115102031474
t7 = 157
b7 = 11010752156494511329
 
c4 = 0x8043b337fd500f49ff23589ac40d6208d1ba5e8b6af341da6c63d4dc4af8944930cd5812076686450967c0b36a52b66e25a632d9b1780ca0195be15f81c7efe7
c5 = 0x13d464f1f4d139c78e8bbf20eaf9b7693a931e65649db09f259ffc9a17674d72187fb10b10ad3db629c0dcb7048cf9b836972320b0018edae6c0604bf9911a59
c6 = 0x0a7c1297094b925b4dcb42b001c2cfa9b0524939b4bb13048fb8e3778238e28b93c59b010ee2e45c7d7d25da69824a729141caf8c613e6dae1a8c08e153e5ae9
c7 = 0x5ee21f49be33499cce3a157a1ad55d3df5bce4ad99e90f8f91929c2a7a1a8f56a99bf69789137276eaac3294fd4b91fc1ee857eeb3544cd0c4f95be49ab3abd7
 
for i in range(2200):
    f4 = (b4 + x + 2^(8*i) * t4)^4 - c4
    f5 = (b5 + x + 2^(8*i) * t5)^5 - c5
    f6 = (b6 + x + 2^(8*i) * t6)^6 - c6
    f7 = (b7 + x + 2^(8*i) * t7)^7 - c7
    f5 = GCD(f4, f5, n)
    f6 = GCD(f5, f6, n)
    f7 = GCD(f6, f7, n)
    if f7.degree() >= 1:
        print(f7)
    
## x + 13213917004013074941883923518155157707200933836201561801562186284370121597148945566062799149031981069879277394219016188339927598569756720133104910406574165
  
cs


Part 3: 마무리 및 flag 도출

1
2
3
res = n - 13213917004013074941883923518155157707200933836201561801562186284370121597148945566062799149031981069879277394219016188339927598569756720133104910406574165
tt = (res * inverse(2 ** 64, n)) % n
print(long_to_bytes(tt))
cs


Ochazuke


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
from Crypto.Util.number import bytes_to_long
from binascii import unhexlify
from hashlib import sha1
import re
 
EC = EllipticCurve(
    GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff),
    [-30x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b]
)
= 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 # EC.order()
Zn = Zmod(n)
= EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
        0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
 
def sign(private_key, message):
    z = Zn(bytes_to_long(message))
    k = Zn(ZZ(sha1(message).hexdigest(), 16)) * private_key
    assert k != 0
    K = ZZ(k) * G
    r = Zn(K[0])
    assert r != 0
    s = (z + r * private_key) / k
    assert s != 0
    return (r, s)
 
def verify(public_key, message, signature):
    r, s = signature[0], signature[1]
    if r == 0 or s == 0:
        return False
    z = Zn(bytes_to_long(message))
    u1, u2 = z / s, r / s
    K = ZZ(u1) * G + ZZ(u2) * public_key
    if K == 0:
        return False
    return Zn(K[0]) == r
 
if __name__=="__main__":
    from secret import flag, d
    public_key = ZZ(d) * G
    print("public key:", public_key)
    
    your_msg = unhexlify(input("your message(hex): "))
    if len(your_msg) < 10 or b"ochazuke" in your_msg:
        print("byebye")
        exit()
    your_sig = sign(d, your_msg)
    print("your signature:", your_sig)
 
    sig = input("please give me ochazuke's signature: ")
    r, s = map(Zn, re.compile("\((\d+), (\d+)\)").findall(sig)[0])
    if verify(public_key, b"ochazuke", (r, s)):
        print("thx!", flag)
    else:
        print("it's not ochazuke :(")
 
cs


일단 생긴 것으로 보아 ECDSA 문제인 것 같고, 요구하는 것은 주어진 메시지에 대한 서명이다.

곡선 자체가 이상한 것 같지도 않고 $G$도 제대로 된 generator 임을 확인할 수 있었다.

그러니 우선 저 ECDSA처럼 생긴 서명 및 verify 과정을 한 번 살펴보자고 생각했다.


일단 sign 과정에서 랜덤성이 정확히 0mg 추가되었고 verify 과정에서 해싱 과정이 하나도 없으니 뭔가 벌써 망했다.

적당한 조건을 만족하는 메시지를 서명 받을 수 있으니, 메시지와 서명의 쌍 하나를 가지고 생각해보자.


sign 알고리즘을 보고, 우리가 여기서 $m, r, s$를 안다고 가정하자. 

$z$는 단순히 bytes_to_long을 때린 결과이므로 계산할 수 있다.

$k$는 계산할 수는 없으나, 계산할 수 있는 값 $kt$가 있어 $k = kt \cdot pvk$로 쓸 수 있다. ($pvk$는 비밀키)

이제 $s = (z + r \cdot pvk) / k$라는 식을 보면, 이는 $pvk$에 대한 일차방정식이다. 


그러니 $pvk$를 도출할 수 있고, 이제 서명을 알아서 잘 하면 된다.


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
HOST = "crypto.kosenctf.com"
PORT = 13005
 
conn = pwnlib.tubes.remote.remote(HOST, PORT)
print(conn.recvline())
conn.send("ffffffffffffffffffff\n")
print(conn.recvline())
 
## (98664527284046924431103876265370791373438293020179316375883642857046660842422 : 51449822108608164116773906593599196539335313713052966364410874461652593273305 : 1)
 
msg = binascii.unhexlify("ffffffffffffffffffff")
= 98909165505886332260977490746820914928283581853841477470132641900339514121815
= 86962637426480431206806090924202825437488410614468755585865520420765819501712
 
= bytes_to_long(msg)
kt = int(sha1(msg).hexdigest(), 16)
= 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
 
## s = (z + r * pvk) / (kt * pvk)
## s * kt * pvk == z + r * pvk
 
pvk = z * inverse(s * kt - r, n) % n
 
print(pvk)
print(bytes_to_long(b'ochazuke'))
 
fr = 98165594340872803797719590291390519389514915039788511532783877037454671871717
fs = 115665584943357876566217145953115265124053121527908701836053048195862894185539
 
mys = "(" + str(fr)  + ", " + str(fs) + ")"
conn.send(mys + "\n")
print(conn.recvline())
cs


sage에서 서명하는 부분은 자명하므로 따로 첨부하지 않았다.