0xGame 2020 Crypto Problems

本文最后更新于：2022年11月17日 下午

0xGame2020 是第一届 0xGame 比赛，时间持续一个月，面向零基础的新生。题目和exp可以在我的GitHub上找到：https://github.com/Am473ur/My-CTF-Challenge/tree/main/0xGame2020 ，这里记录一下出题人角度的wp。

Week 1

Calendar

题目给了一张图片和一串逗号隔开的坐标信息，没看出来的话不难想到去百度一下“日历加密”，这题只是做了简单的修改。

SAT1,THU1,MON3,MON2,WED3,SUN2,THU1,SUN4,FRI3,THU1,MON4,MON4,FRI4,THU3,SUN4,SUN2,TUE4,THU1,FRI1,MON3,MON2

懒得百度的话，也不难看出前三个字母代表周一到周日，紧跟的数字范围是1～4，所以他们代表两个坐标，列举出来并用a～z替换1～26，即可得到flag。

easyXor

做出这题只需要知道异或的逆运算还是异或，反过来跑一遍就拿到了flag。

exp:

1
2
3
4
5
6
7
8
cipher=[72, 63, 38, 12, 8, 30, 30, 6, 82, 4, 84, 88, 92, 7, 79, 29, 8, 90, 85, 26, 25, 87, 80, 10, 20, 20, 9, 4, 80, 73, 31, 5, 82, 0, 1, 92, 0, 0, 94, 81, 4, 85, 27, 35]
flag=""
cipher+=[ord("^")]
for i in range(len(cipher)-1):
    flag = chr(cipher[len(cipher)-i-2]^cipher[len(cipher)-i-1])+flag
    cipher[len(cipher)-i-2]=ord(flag[0])
print(flag)
# 0xGame{ec15a9eb-08b7-4c39-904d-27eed888f73f}

发现有的学弟跑完脚本手动补0，exp正确的话，是可以得到完整flag的。

supperAffine

这题其实就是普通的仿射加密，看起来是套了三层，但是一旦展开化简，仍然是Ax+BAx+B的一次式。

f(x)=A1(A2(A3⋅x+B3)+B2)+B3=(A1A2A3)⋅x+(A1A2B3+A1B2+B1)=A⋅x+B\begin{aligned} f(x)&=A_1(A_2(A_3\cdot x+B_3)+B_2)+B_3\\ &=(A_1A_2A_3)\cdot x+(A_1A_2B_3+A_1B_2+B_1)\\ &=A\cdot x+B \end{aligned}

其中 A=A1A2A3, B=A1A2B3+A1B2+B1.A = A_1A_2A_3,\ B = A_1A_2B_3+A_1B_2+B_1.

并且过大的A和B都是没有意义的，可以等效为模数以内的数，所以解普通的仿射加密的脚本都可以直接解这一题。

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
from Crypto.Util.number import *
from string import ascii_letters, digits
table = ascii_letters+digits
cipher = "t6b7Tn{2GByBZBB-aan2-JRWn-GnZB-Jyf7a722ffnZ}"
MOD = len(table)


def find_ab():
    for a in range(MOD):
        for b in range(MOD):
            if (a*table.find("0")+b) % MOD == table.find(cipher[0]):
                if (a*table.find("x")+b) % MOD == table.find(cipher[1]):
                    if (a*table.find("G")+b) % MOD == table.find(cipher[2]):
                        if (a*table.find("a")+b) % MOD == table.find(cipher[3]):
                            print("a, b = {}, {}".format(a,b))
                            return (a, b)


flag = ""
A, B = find_ab()
for i in cipher:
    if i not in table:
        flag += i
    else:
        flag += table[inverse(A, MOD)*(table.find(i)-B) % MOD]
print(flag)

0xGame{1b292822-33e1-46fe-be82-49ca3a11cce8}

equationSet

这题是个简单的解方程组，可以发现给出的值有

n=p⋅q⋅r s=p+q+r t=p⋅(q+r)\begin {aligned} n&= p\cdot q\cdot r\\\ s&= p + q + r\\\ t&= p\cdot(q+r) \end {aligned}

我们需要求的是

ϕ(n)=(p−1)⋅(q−1)⋅(r−1)\phi(n)=(p-1)\cdot (q-1)\cdot (r-1)

其中

p=GCD(n,t)p=GCD(n,t)

所以

ϕ(n)=(p−1)⋅(q⋅r−(q+r)+1) =(p−1)⋅((n−t)/p+1)\begin {aligned} \phi(n) &= (p-1)\cdot( q\cdot r-(q+r)+1) \\\ &= (p-1)\cdot( (n-t)/p+1) \end {aligned}

exp:

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *

c = 216719040256186298397028655750064798850...
n = 894056034566447301955142597300391580123...
s = 296550633935119159669335323468002356547...
t = 157435908314881832180551915807491465031...

p = GCD(n, t)
phi = (p-1)*((n-t)//p+1)
d = inverse(65537, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

这题也可以使用sagemath直接解，甚至不需要简单的公式推导：

1
2
var('p q r')
solve([p+q+r == s, p*q*r == n, p*q+p*r == t],[p,q,r])

可以直接求出3个素数的值，然后进行解密。

Fibonacci

这题的考点是斐波那契数列对一个模数n取模，会出现循环节，求出循环周期这题就相当于解决了。

这个周期就是皮萨诺周期（Pisano periods），先对 nn 进行素因数分解，然后求解每个素数幂的周期，最后通过中国剩余定理（Chinese remainder theorem）合并，一个素数幂 pnp^n 的周期等于 pn−1p^{n-1} 乘以 pp 的周期，所以需要求出每个素因数的周期。这里分为两种情况，如果 55 是模 pp 的二次剩余，那么 pp 的周期是 p−1p-1 的一个因数；如果不是，那么周期为 2(p+1)2(p+1) 的一个因数。55 是否为模 pp 的二次剩余，可以通过勒让德（Legrend）符号来判断。

不过这题的 nn 很小，直接爆破就可以很快得到它的周期。。。（而且还挺快的orz）

这里给出通过定理求解的脚本（用C++写矩阵快速幂来实现的话会快很多）。

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
from Crypto.Util.number import *
from gmpy2 import next_prime

def genFibonacci():
    a = [1, 1]
    for i in range(2, 2**16):
        a.append(a[i-1]+a[i-2])
    return a

def Legrend(a, p):
    if a == 1:
        return 1
    if p % a == 0:
        return 0
    if a % 2 == 0:
        return Legrend(a // 2, p) * pow(-1, (pow(p, 2) - 1) // 8)
    return Legrend(p % a, a) * pow(-1, (a - 1)*(p - 1) // 4)


def isPeriod(T, a):
    for t in range(T):
        p = t+T
        while p < len(a):
            if a[p] != a[t]:
                return False
            p += T
    return True


def Factor_n(n):
    a = []
    for i in range(2**3, 2**5):
        if (not isPrime(i)) or (n % i):
            continue
        a.append([i, 0])
        n = n//i
        while n % i == 0:
            n = n//i
            a[-1][1] += 1
    return a


def Factor_x(x):
    a = []
    for i in range(2, x):
        if x % i == 0:
            a.append(i)
    return a


def solve(a):
    per = []
    for i in range(len(a)):
        prime = a[i][0]
        if Legrend(5, prime) == 1:
            fac = Factor_x(prime-1)
            tmp = prime-1
        else:
            fac = Factor_x(2*(prime+1))
            tmp = 2*(prime+1)
        fib_mod = [(k % prime) for k in fib]
        for t in fac:
            if isPeriod(t, fib_mod):
                per.append(t*(prime**a[i][1]))
                break
        else:
            per.append(tmp*(prime**a[i][1]))

    LCM = per[0]
    for i in range(1, len(per)):
        LCM = (per[i]*LCM)//GCD(LCM, per[i])
    return LCM

r = 6799657976717333
n = 34969
c = 18230697428395162035214602694158399484881314...
N = 18856119995376203055253776689360000192482523...

fib = genFibonacci()
a = Factor_n(n)
T = solve(a)

fib_mod = [(k % n) for k in fib]
S = sum(fib_mod[:T])*(r//T)+sum(fib_mod[:r%T])
p = next_prime(S**16)
q = N//p
m=pow(c,inverse(65537,(p-1)*(q-1)),N)
print(long_to_bytes(m))

Week 2

smallModulus

这题很简单，只是过一层 proof of work​ 然后用 CRT 就可以拿到 flag，是想让大家熟悉一下远程的题目，写个自动的脚本，但是这题可以 nc 连上去手动拿 8 组数据出来，然后本地计算出flag…

爆破 pow 可以用 pwntools 的 mbruteforce() 函数来多线程爆，速度相对快很多。

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 pwn import *
import hashlib
import string
from functools import reduce
from Crypto.Util.number import*
from gmpy2 import invert

HOST = "xx.xxx.xxx.xx"
PORT = 10000
r = remote(HOST, PORT)


def proof_of_work():
    rev = r.recvuntil("sha256(XXXX+")
    suffix = r.recv(16).decode()
    rev = r.recvuntil(" == ")
    tar = r.recv(64).decode()

    def f(x):
        hashresult = hashlib.sha256(x.encode()+suffix.encode()).hexdigest()
        return hashresult == tar

    prefix = util.iters.mbruteforce(f, string.digits + string.ascii_letters, 4, 'upto')
    r.recvuntil("Give me XXXX:")
    r.sendline(prefix)


def CRT(a, m):
    Num = len(m)
    M = reduce(lambda x, y: x*y, m)
    Mi = [M//i for i in m]
    t = [invert(Mi[i], m[i]) for i in range(Num)]
    x = 0
    for i in range(Num):
        x += a[i]*t[i]*Mi[i]
    return x % M


def getData():
    line = r.recvuntil(b"> ")
    r.sendline(b"1")
    line = r.recvline().decode().strip()
    mod, res = int(line[9:25], 16), int(line[37:54], 16)
    return (mod, res)


proof_of_work()
m = []
a = []
for i in range(8):
    mod, res = getData()
    m.append(mod)
    a.append(res)
flag = CRT(a, m)
print(long_to_bytes(flag))
r.interactive()
# 0xGame{3a8f45be-a0cf-457e-958e-b896056841d7}

parityOracle

RSA parity oracle 是一个经典的攻击，并且给出了CTF Wiki上相关部分的链接，我把模数改成了4，理解一下就可以自己编写脚本解决这一题了。

这是一个不断更新上下界来缩小范围逼近正确的明文值的过程，对不同余数下的上下界的更新需要分类讨论。

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
from pwn import *
from Crypto.Util.number import *

HOST = "xx.xxx.xxx.xx"
PORT = 10001
r = remote(HOST, PORT)


def proof_of_work():
    rev = r.recvuntil("sha256(XXXX+")
    suffix = r.recv(16).decode()
    rev = r.recvuntil(" == ")
    tar = r.recv(64).decode()

    def f(x):
        hashresult = hashlib.sha256(x.encode()+suffix.encode()).hexdigest()
        return hashresult == tar

    prefix = util.iters.mbruteforce(
        f, string.digits + string.ascii_letters, 4, 'upto')
    r.recvuntil("Give me XXXX:")
    r.sendline(prefix)
    
def getNum(c):
    r.sendline(b"1")
    r.recvuntil(b"Your cipher (in hex): ")
    r.sendline(hex(c)[2:].encode())
    return int(r.recvline().decode().strip())
proof_of_work()
r.recvuntil(b"n = ")
n = int(r.recvline().decode().strip())
r.recvuntil(b"c = ")
c = int(r.recvline().decode().strip())
e = 65537

upper = n
lower = 0
i = 1
while True:
    power = pow(4, i, n)
    new_c = (pow(power, e, n)*c) % n
    rev = getNum(new_c)
    if rev == 0:
        upper = (3*lower+upper)//4
    elif rev == 1:
        temp = upper
        upper = (lower+upper)//2
        lower = (3*lower+temp)//4
    elif rev == 2:
        temp = upper
        upper = (lower+3*upper)//4
        lower = (lower+temp)//2
    else:
        lower = (lower+3*upper)//4
    if (upper-lower) < 2:
        break
    i += 1
for i in range(100):
    if pow(lower+i,e,n)==c:
        print(long_to_bytes(lower+i))
        break
r.interactive()
# 0xGame{a9abdec6-7b84-4443-afb8-ee4dada8bdca}

Week 3

signinRSA

很简单的一题，发送密文，服务器会返回解密后的结果，只是不能发送 flag 的密文。

没想到有两位学弟用 parityOracle 的脚本打。。。

因为 c⋅2e≡me⋅2e≡(2m)e mod nc\cdot 2^e\equiv m^e\cdot 2^e\equiv (2m)^e\ mod\ n 所以可以发送 c⋅pow(2,e,n)c\cdot pow(2,e,n) 收到 2m，除 2 得到 flag。

有位学弟想到发送 -c，得到返回 -m，tql

easyRSA

这题是给了 x=11⋅d+7⋅(p−1)⋅(q−1)x=11\cdot d + 7\cdot (p-1)\cdot (q-1) ，我们知道 e⋅d≡1 mod (p−1)⋅(q−1)e\cdot d\equiv 1\ mod\ (p-1)\cdot (q-1) ，所以存在 rr 使

e⋅d=1 + r⋅(p−1)⋅(q−1)e\cdot d= 1\ +\ r\cdot(p-1)\cdot (q-1)

所以

x⋅e=11⋅e⋅d+7⋅e⋅ϕ(n) x⋅e=11⋅(1+r⋅ϕ(n))+7⋅e⋅ϕ(n) x⋅e−11=(11⋅r+7⋅e)⋅ϕ(n)x\cdot e=11\cdot e\cdot d +7\cdot e\cdot \phi(n)\\\ x\cdot e=11\cdot (1+r\cdot \phi (n)) +7\cdot e\cdot \phi(n)\\\ x\cdot e-11=(11\cdot r+7\cdot e)\cdot \phi (n)

枚举 rr 即可得到 ϕ(n)\phi(n) .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *

n = 15321211041844905603734344178124947...
c = 14896093236493033914781929755936872...
x = 26506090189848554080676908570070818...
e = 65537
kphi = x*e-11
for r in range(e):
    k = 7*e+11*r
    if kphi % k: continue
    phi = kphi//k
    if len(bin(n-phi+1)[2:]) > 1025: continue
    print(long_to_bytes(pow(c, inverse(e, phi), n)))
# 0xGame{cfac8284-3013-439b-8ff3-884decb642bb}

paddingOracle

题目名称直接告诉了是 Padding Oracle Attack，学弟们也都学会并实现了这种攻击，网上资料也非常多，我就不详细写了（其实是因为懒）。

这种攻击针对的是块加密的CBC模式，通过求得正确的中间值（Intermediary Value）并在最终和正确的向量异或得到明文。需要对密文分块从后往前破解，对于每一块，从最后一字节往前破解。

对于一块需要破解的密文，需要先构造一个IV，并枚举IV的最后一字节，直到服务器告诉我们解密后的padding是正确的，将枚举到的这个字节的值和padding的值（\x01）异或即可得到当前位置的中间值。然后更新IV的最后一字节（中间值最后一字节和\x02异或）来保证枚举倒数第二字节的时候，倒数第一字节解密后的值是\x02（这样爆破倒数第二字节的时候，只要服务器解密后倒数第二字节是\x02就会padding正确）。

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from pwn import *


HOST = "49.235.239.97"
PORT = 10003
r = remote(HOST, PORT)


def proof_of_work():
    rev = r.recvuntil("sha256(XXXX+")
    suffix = r.recv(16).decode()
    rev = r.recvuntil(" == ")
    tar = r.recv(64).decode()

    def f(x):
        hashresult = hashlib.sha256(x.encode()+suffix.encode()).hexdigest()
        return hashresult == tar

    prefix = util.iters.mbruteforce(
        f, string.digits + string.ascii_letters, 4, 'upto')
    r.recvuntil("Give me XXXX:")
    r.sendline(prefix)


proof_of_work()
r.recvuntil(b"iv : ")
iv = [long_to_bytes(int(r.recvline().decode().strip(), 16))]
r.recvuntil(b"crypttext : ")
crypttext = long_to_bytes(int(r.recvline().decode().strip(), 16))
blocks = [crypttext[i*16:i*16+16] for i in range(len(crypttext)//16)]
iv += blocks[:-1]
flag = b""
for block in range(len(blocks)):
    mid_value = []
    new_iv = bytearray(b"\x00"*16)
    for i in range(16):
        for j in range(256):
            new_iv[15 - i] = j
            r.recvuntil(b"> ")
            r.sendline(b"1")
            r.recvuntil(b"Your IV (in hex): ")
            r.sendline(new_iv.hex())
            r.recvuntil(b"Your cipher (in hex): ")
            r.sendline(blocks[block].hex().encode())
            data = r.recvline()
            if b"success" in data:
                ans = j ^ (i+1)
                break

        mid_value.append(ans)
        for m in range(15 - i, 16):
            new_iv[m] = (i+2) ^ mid_value[15 - m]
    find = ""
    for i in range(16):
        find += hex(iv[block][i] ^ mid_value[15 - i])[2:].rjust(2, '0')
    flag += long_to_bytes(int(find, 16))
    print(flag)
r.interactive()

Week 4

littleTrick

逐字节构造服务器端的flag，使服务器发送给我们的密文解密后只有一字节是我们未知的，所以我们只需要本地枚举一下这个字节，并在本地加密，本地的密文和服务器返回的密文一致的话，就说明爆破对了。

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from pwn import *


HOST = "xx.xxx.xxx.xx"
PORT = 10004
r = remote(HOST, PORT)


def proof_of_work():
    rev = r.recvuntil("sha256(XXXX+")
    suffix = r.recv(16).decode()
    rev = r.recvuntil(" == ")
    tar = r.recv(64).decode()

    def f(x):
        hashresult = hashlib.sha256(x.encode()+suffix.encode()).hexdigest()
        return hashresult == tar

    prefix = util.iters.mbruteforce(f, string.digits + string.ascii_letters, 4, 'upto')
    r.recvuntil("Give me XXXX:")
    r.sendline(prefix)


proof_of_work()
r.recvuntil(b"n : ")
n = int(r.recvline().decode().strip(), 16)
e = 65537
flag=b""
for i in range(44):
    mask=b"1"*(44-i-1)
    print(mask)
    r.sendlineafter(b"> ", b"1")
    r.sendlineafter(b"Your mask (in hex): ",hex(pow(bytes_to_long(mask),e,n))[2:].encode())
    tar = int(r.recvline().decode().strip(), 16)
    for j in range(32,128):
        guess=flag+long_to_bytes(j)+mask
        if pow(bytes_to_long(guess),e,n)==tar:
            flag+=long_to_bytes(j)
            print(flag)
            break
r.interactive()

ElGamal

这题的考点是判断二次剩余，如果发现了y是二次剩余的话，那么只需要判断c1是否为二次剩余就可以了。

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *

y = 2101136318398982764494355697982735290351867853540128399809061806690701481465143258501856786165972388085070268979718711434744226290744692988395355120277617
g = 8401562798890834492298947403582806359769363301996138198850077614144023393945770711612546197987255078645962298286362268504959833530010137313108031112774451
p = 10946148224653120484646906462803901217745837751637974066354601688874051778651193811412739372059281847771491564589986518154039493312147458591216351424346123

datalist = [c.split(", ") for c in open("data", "r").read().split("\n")[:-1]]
flag = "".join(["0" if pow(int(c[1], 16), (p-1)//2, p) == 1 else "1" for c in datalist])
print(long_to_bytes(int(flag,2)))

如果y不是二次剩余的话，就需要多进行一层判断。

这题改自CVE-2018-6594

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
f = open("data", "r").read().split("\n")[:-1]
datalist = [c.split(", ") for c in f]

y = 2101136318398982764494355697982735290351867853540128399809061806690701481465143258501856786165972388085070268979718711434744226290744692988395355120277617
g = 8401562798890834492298947403582806359769363301996138198850077614144023393945770711612546197987255078645962298286362268504959833530010137313108031112774451
p = 10946148224653120484646906462803901217745837751637974066354601688874051778651193811412739372059281847771491564589986518154039493312147458591216351424346123

flag = ""
for c in datalist:
    output = -1
    if (pow(y, (p-1)//2, p) == 1) or (pow(int(c[0], 16), (p-1)//2, p) == 1):
        if pow(int(c[1], 16), (p-1)//2, p) == 1:
            flag += "0"
        else:
            flag += "1"
    else:
        if pow(int(c[1], 16), (p-1)//2, p) == 1:
            flag += "1"
        else:
            flag += "0"
flag = long_to_bytes(int(flag,2))
print(flag)