# Writeup for Crypto Problems in VolgaCTF 2020

## Noname 100pt

 1 2 3 4 5  key = md5(str(int(time.time()))).digest() padding = 16 - len(flag) % 16 aes = AES.new(key, AES.MODE_ECB) outData = aes.encrypt(flag + padding * hex(padding)[2:].decode('hex')) print outData.encode('base64') 

 1 2 3 4  In [1]: import time In [2]: time.time() Out[2]: 1585451787.9715672 

time.time()返回当前的Unix timestamp (时间戳)，所以只要知道加密的时候的timestamp就能解密。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  from hashlib import md5 from base64 import b64decode from Crypto.Cipher import AES from tqdm import tqdm cipher = b64decode(open("encrypted", "rb").read()) print(len(cipher)) for k in tqdm(range(1585008000, 1585353600)): key = md5(str(k).encode()).digest() aes = AES.new(key, AES.MODE_ECB) msg = aes.decrypt(cipher) if b"Volga" in msg: print(k, msg) # 1585242915 # VolgaCTF{5om3tim3s_8rutf0rc3_i5_th3_345iest_w4y} 

## Guess 200pt

 1 2 3  plaintexts = dict() plaintexts[0] = findQNR(key.p) plaintexts[1] = findQR(key.p) 

0表示我们猜测服务器选取的是二次非剩余1表示我们猜的是二次剩余

$$\left( \frac{c_2}{p} \right) = \left( \frac{m y^r}{p} \right) = \left( \frac{m}{p} \right) \left( \frac{y^r}{p} \right) = \left( \frac{m}{p} \right)$$

  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  # nc guess.q.2020.volgactf.ru 7777 from pwn import * from tqdm import tqdm import re def legendre(a, p): return pow(a, (p-1)//2, p) r = remote("guess.q.2020.volgactf.ru", 7777) # context.log_level = "debug" y_p = r.recvline().decode() y = int(re.findall(r"$$([0-9].*?),", y_p)[0]) p = int(re.findall(r", ([0-9].*?)$$", y_p)[0]) print(f"y: {y}\np: {p}") if legendre(y, p) != 1: exit() for i in tqdm(range(1000)): c1c2 = r.recvline().decode() c2 = int(re.findall(r", ([0-9].*?)L\)", c1c2)[0]) leg_symbol = legendre(c2, p) if leg_symbol == 1: r.sendline(b"1") else: r.sendline(b"0") r.interactive() # VolgaCTF{B3_c4r3ful_with_4lg0rithm5_impl3m3nt4ti0n5} 

## Keygreed 300pt

client.py进行简单的审计后，可以发现这是一个ECDHElliptic Curve Diffie-Hellman）。

  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  # region Params BITS = 56 INPUTSIZE = 1024 a = 1 b = 0 p = 3009944491747103173592552029257669572283120430367 order = 3009944491747103173592552029257669572283120430368 gx = 2900641855339024752663919275085178630626065454884 gy = 1803317565451817334919844936679231131166218238368 curve = Curve("Super Secure Elliptic Curve", p, a, b, order, gx, gy) P = Point(gx, gy, curve) # endregion Params # ... # Some util functions # ... if __name__ == "__main__": HOST, PORT = sys.argv[1], int(sys.argv[2]) with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as sock: sock.connect((HOST,PORT)) secureNumber = random.getrandbits(BITS) sendPointToServer(sock, P * secureNumber) point = getPointFromServer() securePoint = secureNumber * point encrytpedFlag = getMessageFromServer() flag = decrypt(encrytpedFlag,securePoint.x) print('Your flag: {0}'.format(flag)) 

• Elliptic Curve $y^2 = x^3 + x \quad \text{over}\ \mathbb{F}_p^*$

• Point G (

​ 2900641855339024752663919275085178630626065454884,

​ 1803317565451817334919844936679231131166218238368

)

• Point A (

​ 0x83c02e919804d3aa0aa98a3162a393884bb3f203,

​ 0x11d46c5db96703a64609ddf2526b79bef026ceb7a

)

• Point B (

​ 0x1ddc663e98edb9e848b66dd961bb555396fa680,

​ 0xdedc439c092188a093b2b887dcbee2abe302934c

)

• cipher: PiRh20C/A0GWTxDQnyBiiTEzYPTf33fNQWFNcirzJsTg/lqFDor0jW22fv8DDUaiRar1aEf3OPudbIwakEp1tQ==

Point A, Point B, cipher需要从pacp流量包中解析出来。

Given an element g and the values of $g^x$ and $g^y$, what is the value of $g^{xy}$?

$b * G = B$这一步是服务器暗地里操作的，我们无从得知。

 1 2 3 4 5 6 7 8  # ... BITS = 56 # ... # ... secureNumber = random.getrandbits(BITS) sendPointToServer(sock, P * secureNumber) # ... 

  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  # SageMath 8.9 a = 1 b = 0 p = 3009944491747103173592552029257669572283120430367 order = 3009944491747103173592552029257669572283120430368 gx = 2900641855339024752663919275085178630626065454884 gy = 1803317565451817334919844936679231131166218238368 ecc = EllipticCurve(GF(p), [a,b]) G = ecc(gx,gy) print ecc.order(), G.order() A_x = 0x83c02e919804d3aa0aa98a3162a393884bb3f203 A_y = 0x11d46c5db96703a64609ddf2526b79bef026ceb7a A = ecc(A_x, A_y) B_x = 0x1ddc663e98edb9e848b66dd961bb555396fa680 B_y = 0xdedc439c092188a093b2b887dcbee2abe302934c B = ecc(B_x, B_y) print A.order(), B.order() # 3009944491747103173592552029257669572283120430368 1732447508855707297839490248756403 # 1732447508855707297839490248756403 1732447508855707297839490248756403 

• Baby-step giant-step algorithm：DLP的通用解法，用空间换时间，复杂度为$O(\sqrt{n})$。
• Pohlig-Hellman algorithm：针对阶数较为光滑的情况，复杂度取决于阶数中最大的那个素因子。
• Index calculus algorithm：针对某些特殊的椭圆曲线

$1732447508855707297839490248756403 = 280438073097979 \times 6177647313424620457$，这个阶数的因数分解是两个$2^{50}$左右的素数，因此没有考虑Pohlig-Hellman algorithm。

wiki上关于Baby-step giant-step algorithm的流程如下：

• 先预先存好一段长为m的空间，即上图中红色大括号内的部分。
• 然后从$\gamma = \beta = A = a \cdot G$出发，不断地减去长度为m的内容$\gamma = \gamma + (-m \cdot G)$，直到某一次掉入一开始存好的那个范围内。
• 此时，有等式$j \cdot G = a \cdot G - im \cdot G$，从中可以算出$a = j + i \cdot m$。

  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 tqdm import tqdm from fastecdsa.curve import Curve from fastecdsa.point import Point a = 1 b = 0 p = 3009944491747103173592552029257669572283120430367 order = 3009944491747103173592552029257669572283120430368 gx = 2900641855339024752663919275085178630626065454884 gy = 1803317565451817334919844936679231131166218238368 curve = Curve("Super Secure Elliptic Curve", p, a, b, order, gx, gy) P = Point(gx, gy, curve) inf = P.IDENTITY_ELEMENT # identity element X = 0x83c02e919804d3aa0aa98a3162a393884bb3f203 Y = 0x11d46c5db96703a64609ddf2526b79bef026ceb7a A = Point(X, Y, curve) ##################################### # baby-step & giant-step algorithm # ##################################### m = 2**26 # baby step precomputed = {} # 16min + 8GB RAM r = inf for i in tqdm(range(m)): precomputed[r.x] = i r = r + P # giant step mP = P * (1732447508855707297839490248756403-2**26) # -mP Y = A for i in tqdm(range(2**30)): if Y.x in precomputed: print(i*m + precomputed[Y.x]) break Y = Y + mP 

SageMath的discrete_log也是用Baby-step giant-step algorithmPohlig-Hellman algorithm，不过SageMath的实现并没有像我这样考虑到内存的因素，算到8GB+，电脑的内存就已经满了，算不下去了。因此才萌生了自己实现一下Baby-step giant-step algorithm的想法。

  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  import base64 import hashlib from tqdm import tqdm from fastecdsa.curve import Curve from fastecdsa.point import Point from Crypto.Cipher import AES a = 1 b = 0 p = 3009944491747103173592552029257669572283120430367 order = 3009944491747103173592552029257669572283120430368 gx = 2900641855339024752663919275085178630626065454884 gy = 1803317565451817334919844936679231131166218238368 curve = Curve("Super Secure Elliptic Curve", p, a, b, order, gx, gy) P = Point(gx, gy, curve) Bx = 0x1ddc663e98edb9e848b66dd961bb555396fa680 By = 0xdedc439c092188a093b2b887dcbee2abe302934c B = Point(Bx, By, curve) def decrypt(enc, password): unpad = lambda s: s[:-ord(s[len(s) - 1:])] private_key = hashlib.sha256(str(password).encode("utf-8")).digest() enc = base64.b64decode(enc) iv = enc[:16] cipher = AES.new(private_key, AES.MODE_CBC, iv) return bytes.decode(unpad(cipher.decrypt(enc[16:]))) encrytpedFlag = b"PiRh20C/A0GWTxDQnyBiiTEzYPTf33fNQWFNcirzJsTg/lqFDor0jW22fv8DDUaiRar1aEf3OPudbIwakEp1tQ==" secureNumber = 71144474526556922 securePoint = secureNumber * B flag = decrypt(encrytpedFlag,securePoint.x) print('Your flag: {0}'.format(flag)) # Your flag: VolgaCTF{s0m3_curv35_4r3_sup3r_bu7_s1ngul4r}