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')

可以发现,用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就能解密。

查看文件的修改日期:

Screen Shot 2020-03-29 at 11.20.03 AM

最后一次修改日期是今年的三月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/

Guess 200pt

简单的审计后,可以发现这是一个Elgamal Encryption Scheme

ElGamal cryptosystem pseudocode | Download Scientific Diagram

服务器每一轮都会根据findQNRfindQR这两个函数分别生成2个明文。

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

跟进findQNRfindQR函数,可以发现findQNR会随机生成一个在$\mathbb{F}_p^*$下的一个二次非剩余(quadratic nonresidue),findQR则会随机生成一个二次剩余(quadratic residue)

随后,服务器会随机选取其中一个明文,对其进行加密,再将密文发送给我们。

我们需要回复01来猜测服务器选中的是哪一个明文。

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

如果我们在1000轮内全都猜中的话,服务器就会将flag发送给我们。


关于二次剩余,有如下的乘法规则

Screen Shot 2020-03-29 at 11.47.59 AM

另外,我们可以用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 Symbol1的话,$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}

Keygreed 300pt

给了我们一个client.py和一个pcap流量包文件。

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))

结合client.pypcap流量包中的内容,可以画出如下时序图:

Screen Shot 2020-03-29 at 5.58.24 PM

现在我们可以获得到的信息为:

  • 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的流程如下:

Screen Shot 2020-03-29 at 2.48.36 PM

注意到这边,我们已经掌握到了关于私钥$a$的部分信息:$a$是一个56-bit左右的数,因此我们可以轻松地给出$a$的一个上界:$2^{56}$,只需要在区间$(0, 2^{56})$内去寻找这个$a$就可以了。

这种以空间换时间的查找算法,在我之前的一篇An Interesting Factorization Method on Close-prime中有提到一些相关的内容。

Screen Shot 2020-03-29 at 2.59.46 PM

  • 先预先存好一段长为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 algorithmPohlig-Hellman algorithm,不过SageMath的实现并没有像我这样考虑到内存的因素,算到8GB+,电脑的内存就已经满了,算不下去了。因此才萌生了自己实现一下Baby-step giant-step algorithm的想法。

感觉用C实现应该更快,不过没怎么试过用C处理大整数,所以就用Python实现了。

result

跑了大概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,可以直接秒解。

Load Comments?