题目：
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')
|
可以发现，用time.time()作为AES的key，对flag进行加密。
查看一下time.time()这个函数的功能：
1
2
3
4
|
In [1]: import time
In [2]: time.time()
Out[2]: 1585451787.9715672
|
time.time()返回当前的Unix timestamp (时间戳)，所以只要知道加密的时候的timestamp就能解密。
查看文件的修改日期：
最后一次修改日期是今年的三月25号。
去在线网站
上分别算出三月24号和三月26号的timestamp，然后在这个范围内进行穷举，必有一个key是可以解密的。
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}
|
有一个类似的题目：https://id0-rsa.pub/problem/30/
简单的审计后，可以发现这是一个Elgamal Encryption Scheme。
服务器每一轮都会根据findQNR和findQR这两个函数分别生成2个明文。
1
2
3
|
plaintexts = dict()
plaintexts[0] = findQNR(key.p)
plaintexts[1] = findQR(key.p)
|
跟进findQNR和findQR函数，可以发现findQNR会随机生成一个在$\mathbb{F}_p^*$下的一个二次非剩余（quadratic nonresidue），findQR则会随机生成一个二次剩余（quadratic residue）
随后，服务器会随机选取其中一个明文，对其进行加密，再将密文发送给我们。
我们需要回复0或1来猜测服务器选中的是哪一个明文。
0表示我们猜测服务器选取的是二次非剩余，1表示我们猜的是二次剩余。
如果我们在1000轮内全都猜中的话，服务器就会将flag发送给我们。
关于二次剩余，有如下的乘法规则：
另外，我们可以用Legendre Symbol来表示某个数是二次剩余（QR）还是二次非剩余（NR）：
$$
\left(\frac{a}{p}\right) =
{\begin{cases}
1&{\text{if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\newline
-1&{\text{if }}a{\text{ is a non-quadratic residue modulo }}p,\newline
0&{\text{if }}a\equiv 0{\pmod {p}}.
\end{cases}}
$$
Legendre Symbol的计算，可以利用Euler’s Criterion：
$$
\left(\frac{a}{p}\right) = a^{(p-1)/2} \pmod{p}
$$
我们可以考察Elgamal Encryption Scheme中一些参数的Legendre Symbol。
密钥生成部分：
$$
y = g^x \pmod{p}
$$
其中$g$为$\mathbb{F}_p^*$下的一个生成元，$x$即为私钥，而$y$和$p$则是服务器一开始就会发送给我们的公钥。
虽然$g$也是公钥的一部分，但服务器并没有发送给我们。
我们可以利用Euler’s Criterion来算出$y$的Legendre Symbol。
加密部分：
$$
\begin{cases}
c_1 \equiv g^r \pmod{p} \newline
c_2 \equiv m \cdot y^r \pmod{p}
\end{cases}
$$
$r$是随机选取的临时密钥，无关紧要。
主要观察$c_2 \equiv m \cdot y^r \pmod{p}$这一步。由于QR乘自己很多次是不会改变Legendre Symbol，而NR乘自己很多次则是有可能会改变Legendre Symbol的，所以，如果$y$的Legendre Symbol是1的话，$y^r$的Legendre Symbol肯定还是1。
但如果$y$的Legendre Symbol是-1的话，$y^r$的Legendre Symbol就会取决于$r$的奇偶性，但$r$我们是不太可能会知道的。
$$
\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)
$$
这样$m$的Legendre Symbol就跟$c_2$的Legendre Symbol一样了，因此可以根据$c_2$是否为二次剩余来判断出$m$是否为二次剩余。
根据这个思路可以写出exp：
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}
|
给了我们一个client.py和一个pcap流量包文件。
对client.py进行简单的审计后，可以发现这是一个ECDH（Elliptic 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))
|
结合client.py和pcap流量包中的内容，可以画出如下时序图：
现在我们可以获得到的信息为：
-
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流量包中解析出来。
我们需要仅凭这些“离线”信息，算出key，解密出flag。
这是一个Diffie-Hellman Problem。
Given an element g and the values of $g^x$ and $g^y$, what is the value of $g^{xy}$?
一个显然的解法就是，解出$a * G = A$或者$b * G = B$中的$a, b$。
$b * G = B$这一步是服务器暗地里操作的，我们无从得知。
不过$a * G = A$这一步则在client.py中有给出具体实现：
1
2
3
4
5
6
7
8
|
# ...
BITS = 56
# ...
# ...
secureNumber = random.getrandbits(BITS)
sendPointToServer(sock, P * secureNumber)
# ...
|
可以发现client这边的私钥$a$是一个56-bit的数。
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
|
而$G, A, B$的阶数均为1732447508855707297839490248756403（一个111-bit的数）。
显然client的私钥选取地过于小了，这或许是为了减少$A = a*G$这一步的运算？
此外，从这道题的名字Keygreed（greedy key，贪婪的密钥）也能看出来，似乎这道题的考点就是这个私钥的位数太小了。
根据这个暗示，我们需要去解出$a * G = A$这个DLP。
目前已知的ECDLP解法
有如下几种：
- Baby-step giant-step algorithm：DLP的通用解法，用空间换时间，复杂度为$O(\sqrt{n})$。
- Pohlig-Hellman algorithm：针对阶数较为光滑的情况，复杂度取决于阶数中最大的那个素因子。
- Index calculus algorithm：针对某些特殊的椭圆曲线
- …
由于这个私钥$a$挺“小”的，平方根一下，也就大概$2^{28}$的运算量，可以尝试一下Baby-step giant-step algorithm。
$1732447508855707297839490248756403 = 280438073097979 \times 6177647313424620457$，这个阶数的因数分解是两个$2^{50}$左右的素数，因此没有考虑Pohlig-Hellman algorithm。
wiki上关于Baby-step giant-step algorithm的流程如下：
注意到这边，我们已经掌握到了关于私钥$a$的部分信息：$a$是一个56-bit左右的数，因此我们可以轻松地给出$a$的一个上界：$2^{56}$，只需要在区间$(0, 2^{56})$内去寻找这个$a$就可以了。
这种以空间换时间的查找算法，在我之前的一篇An Interesting Factorization Method on Close-prime
中有提到一些相关的内容。
- 先预先存好一段长为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$。
有了这张图后，Baby-step giant-step这个算法的名字想要表达的意思就很明显了。
由于这是一个空间换时间的算法，所以需要考虑到内存是否能够存的下那段长度为m的空间。
经过测试，发现$2^{22}$大小的空间需要大概500MB的内存，因此可以选择$m = 2^{26}$，这样大概需要8GB的空间，在我16GB内存的笔记本上完全是可行的。
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
|
由于我们在baby-step的时候将预先存储的空间大小调小了（从$2^{56 / 2}=2^{28}$减少到$2^{26}$），因此在giant-step的时候，我们需要相应地增加步数（从$2^{28}$增加到$2^{30}$），这样才能保证会落到预先存储的那段区间中，否则就有可能触碰不到这个范围。可见，我们这边又是相应地用时间换取了一些空间。
SageMath的discrete_log也是用Baby-step giant-step algorithm和Pohlig-Hellman algorithm，不过SageMath的实现并没有像我这样考虑到内存的因素，算到8GB+，电脑的内存就已经满了，算不下去了。因此才萌生了自己实现一下Baby-step giant-step algorithm的想法。
感觉用C实现应该更快，不过没怎么试过用C处理大整数，所以就用Python实现了。
跑了大概3个多小时，得到了私钥$a = 71144474526556922$。
接下来，只需要利用$a$和$B = b \cdot G$算出key，再解密即可。
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}
|
嘶～，照这个flag的意思，这个方法好像这不是预期解？？
去网上搜了下，的确有一个Singular Curve Point Decompression Attack。
不过Singular Curve Point Decompression Attack需要动态交互的环境。后来经某位师傅提醒，这一题实际上需要用到MOV Attack
，可以直接秒解。