0x01 babyrsa

KEY

题目有三个环节：

第一个环节是PoW，爆破前四位即可

第二个环节是小质数 $n$，直接factordb分解得出 $p$ 和 $q$ 即可

第三个环节给出的 $n$ 非常大，无法使用factordb，但观察源码可以发现 $p$ 和 $q$ 是两个相邻的质数，所以可以在这个基础上使用费马分解进行爆破

题目

#!/usr/bin/env python3

import random
import signal
import socketserver
import string
from hashlib import sha256
from os import urandom
from Crypto.Util.number import *
from gmpy2 import next_prime

flag = 'flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}'

class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def proof_of_work(self):
        random.seed(urandom(8))
        proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(16)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4:], digest) + "\n" + '@ XXXX=')
        x = self.request.recv(10)
        x = (x.strip()).decode('utf-8')
        if len(x) != 4 or sha256((x + proof[4:]).encode()).hexdigest() != digest:
            return False
        return True

    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def error(self):
        self.dosend("sorry!")
        self.request.close()

    def game1(self):
        p = getPrime(20)
        q = getPrime(20)
        e = 0x10001
        m = random.randint(0x10000, 0xfffff)
        c = pow(m, e, p * q)
        self.dosend("Welcome to game1" + "\n" + "The answer submitted should be hexadecimal strings like 0x1a23\n" + "# n=" + hex(p * q) + "\n" + "# e=" + hex(e) + "\n" + "# c=" + hex(
            c) + "\n" + "@ m=")
        rec_m = self.request.recv(1024).strip().decode('utf-8')
        if rec_m != hex(m):
            self.error()

    def game3(self):
        self.dosend("Welcome to game3. In this game should try 30 times and solve them")
        for i in range(30):
            p = getPrime(512)
            q = next_prime(p)
            e = 0x10001
            m = random.randint(0x100000000000, 0xffffffffffff)
            c = pow(m, e, p * q)
            self.dosend(
                "{} try".format(i + 1) + "\n" + "# n=" + hex(p * q) + "\n" + "# e=" + hex(e) + "\n" + "# c=" + hex(
                    c) + "\n" + "@ m=")
            rec_m = self.request.recv(1024).strip().decode()
            if rec_m == hex(m):
                continue
            else:
                self.error()

    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(50)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                self.request.close()
            signal.alarm(300)

            self.game1()
            self.game3()

            self.dosend(flag)

        except TimeoutError:
            self.dosend('Timeout!')
            self.request.close()
        except:
            self.dosend('Wtf?')
            self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

EXP

from factordb.factordb import FactorDB
from pwn import *
import itertools
import gmpy2
import hashlib
import string

context.log_level = 'debug'
conn = remote('xx.xx.xx.xx', xx)
pattern = re.compile(r'[a-zA-Z\d]+')

# PoW
text = conn.recvline(keepends=True).decode('utf-8')
texts = pattern.findall(text)
right = texts[2]
ans = texts[3]
for i in string.ascii_letters + string.digits:
    for j in string.ascii_letters + string.digits:
        for k in string.ascii_letters + string.digits:
            for l in string.ascii_letters + string.digits:
                left = i + j + k + l
                data = left + right
                if hashlib.sha256(data.encode('utf-8')).hexdigest() == ans:
                    conn.sendline(str.encode(left))

# game1
conn.recvline(keepends=True) #
conn.recvline(keepends=True) # Welcome to game1
conn.recvline(keepends=True) # The answer submitted should be hexadecimal strings like 0x1a23
nText1 = conn.recvline(keepends=True).decode('utf-8')
eText1 = conn.recvline(keepends=True).decode('utf-8')
cText1 = conn.recvline(keepends=True).decode('utf-8')
conn.recvline(keepends=True) # m=
# 正则提取
n = int(pattern.findall(nText1)[1], base=16)
e = int(pattern.findall(eText1)[1], base=16)
c = int(pattern.findall(cText1)[1], base=16)
# factordb分解质因数
f = FactorDB(n)
f.connect()
pq = f.get_factor_list()
p = pq[0]
q = pq[1]
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)

conn.sendline(str.encode(hex(m)))

# game3
conn.recvline(keepends=True) # Welcome to game3. In this game should try 30 times and solve them
# 连解三十道题
for _ in range(30):
    conn.recvline(keepends=True) # try
    nText = conn.recvline(keepends=True).decode('utf-8')
    eText = conn.recvline(keepends=True).decode('utf-8')
    cText = conn.recvline(keepends=True).decode('utf-8')
    conn.recvline(keepends=True) # m=

    n = int(pattern.findall(nText)[1], base=16)
    c = int(pattern.findall(cText)[1], base=16)
    # 爆破相邻的p和q
    for q in itertools.count(gmpy2.iroot(n, 2)[0]-1):
        if n % q == 0:
            p = n // q
            break
    d = gmpy2.invert(e,(p-1)*(q-1))
    m = pow(c,d,n)
    conn.sendline(str.encode(hex(m)))

# 打印flag
flag = conn.recvline(keepends=True) 
print(flag) # flag{you_must_know_1nteractive_question}

0x02 babyblock

KEY

题目考察的是对AES-CBC的理解

由源码可知在加密时每16字节分为一块，然后使用随机生成的密钥 $k$ 进行AES加密后与$IV$（Initial Vector）进行异或，但题目使用的$IV$是固定的，这就给了我们获取$IV$的机会

所以我们构造一段密文 $C$，将其分为三块，$P$ 为每一块的输出

$$
\begin{aligned}P_0 = Dec_k(C_0)\oplus IV\\ P_1 = Dec_k(C_1)\oplus C_0\\ P_2 = Dec_k(C_2)\oplus C_1\end{aligned}
$$

将 $P_0$ 和 $P_1$ 异或可得

$$
\begin{equation}P_0\oplus P_1 = (Dec_k(C_0)\oplus IV)\oplus Dec_k(C_1)\oplus C_1\end{equation}
$$

如何构造密文 $C$ 使得我们可以从式 $(1)$ 中得到 $IV$ 呢？

答案就是令 $C=0000000000000000\ 0000000000000000\ 0000000000000000$

（为方便辨识，每16个0加了一个空格）

我们知道，任何数与0异或都是它本身，那么化简可得

$$
\begin{aligned}P_0\oplus P_1 &= (Dec_k(C_0)\oplus IV)\oplus (Dec_k(C_1)\oplus C_0)\\&= (Dec_k(C_0)\oplus IV)\oplus Dec_k(C_1)\\&=IV\oplus Dec_k(C_0)\oplus Dec_k(C_1)\\&=IV\oplus 0000000000000000\\&=IV\end{aligned}
$$

所以，我们只需要将 $0000000000000000\ 0000000000000000\ 0000000000000000$ 作为密文提供给程序解密，得到的明文会包括三块，由于 $C_0$ 和 $C_1$ 相同，所以明文的第二块和第三块相同，我们只需要将第一块和第二块异或即可得到 $IV$

题目

#!/usr/bin/env python3

import random
import signal
import socketserver
import string
from hashlib import sha256
from os import urandom
from Crypto.Cipher import AES

flag = b'flag{xxxxxxxxxxxxxxxxxxxxxxxxxx}'
BLOCK_SIZE = 16

def pad(m):
    if len(m) % BLOCK_SIZE != 0:
        m += b'\x00' * (BLOCK_SIZE - len(m) % BLOCK_SIZE)
    return m

pad(flag)
part_flag = [flag[i:i + BLOCK_SIZE] for i in range(0, len(flag), BLOCK_SIZE)]

class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def proof_of_work(self):
        random.seed(urandom(8))
        proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(16)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4:], digest) + "\n" + '@ XXXX=')
        x = self.request.recv(10)
        x = (x.strip()).decode('utf-8')
        if len(x) != 4 or sha256((x + proof[4:]).encode()).hexdigest() != digest:
            return False
        return True

    def dosend(self, msg, newline=True):
        try:
            string = msg.encode('latin-1')
            if newline:
                string = string + b"\n"
            self.request.sendall(string)
        except:
            pass

    def receive(self, prompt=">> "):
        self.dosend(prompt, newline=False)
        return self.request.recv(2048).strip()

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def error(self):
        self.dosend("sorry!")
        self.request.close()

    def keyGen(self):
        key = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(16)])
        return key.encode()

    def encrypt(self):
        self.dosend("Enter HEXADECIMAL message:")
        m = self.receive().decode().strip()
        m = pad(bytes.fromhex(m))
        cipher = AES.new(self.key, AES.MODE_CBC, iv=self.IV)
        c = cipher.encrypt(m)
        self.dosend("This is your cipher")
        self.dosend(c.hex())

    def decrypt(self):
        self.dosend("Enter HEXADECIMAL cipher:")
        c = self.receive().decode().strip()
        c = pad(bytes.fromhex(c))
        cipher = AES.new(self.key, AES.MODE_CBC, iv=self.IV)
        m = cipher.decrypt(c)
        self.dosend("This is your message")
        self.dosend(m.hex())

    def selectIV(self):
        while True:
            self.dosend("Which part of flag do you want to choose?")
            part = self.receive().decode().strip()
            try:
                part = int(part)
                assert 0 <= part < len(part_flag)
                return part_flag[part]
            except:
                continue

    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(50)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                self.request.close()
            signal.alarm(300)

            self.key = self.keyGen()
            self.IV = self.selectIV()
            while True:
                self.dosend("1: Encrypt")
                self.dosend("2: Decrypt")
                self.dosend("3: ChangeIV")
                self.dosend("4: Give up")
                choice = self.receive().decode()
                if choice == "1":
                    self.encrypt()
                elif choice == "2":
                    self.decrypt()
                elif choice == "3":
                    self.IV = self.selectIV()
                elif choice == "4":
                    self.dosend("88")
                    self.request.close()

        except TimeoutError:
            self.dosend('\nTimeout!')
            self.request.close()
        except:
            self.dosend('Wtf?')
            self.request.close()

class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10002
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

EXP

from pwn import *
import hashlib
import string

context.log_level = 'debug'
conn = remote('xx.xx.xx.xx', xx)
pattern = re.compile(r'[a-zA-Z\d]+')

# PoW
text = conn.recvline(keepends=True).decode('utf-8')
texts = pattern.findall(text)
right = texts[2]
ans = texts[3]
for i in string.ascii_letters + string.digits:
    for j in string.ascii_letters + string.digits:
        for k in string.ascii_letters + string.digits:
            for l in string.ascii_letters + string.digits:
                left = i + j + k + l
                data = left + right
                if hashlib.sha256(data.encode('utf-8')).hexdigest() == ans:
                    conn.sendline(str.encode(left))
conn.recvline(keepends=True) # Which part of flag do you want to choose?
conn.recvline(keepends=True)
conn.sendline('0'.encode('utf-8'))
conn.recvline(keepends=True) # 1: Encrypt
conn.recvline(keepends=True) # 2: Decrypt
conn.recvline(keepends=True) # 3: ChangeIV
conn.recvline(keepends=True) # 4: Give up
conn.sendline('2'.encode('utf-8'))
conn.recvline(keepends=True) # Enter HEXADECIMAL cipher:
conn.sendline('00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000'.encode('utf-8'))
conn.recvline(keepends=True) # This is your message
msg = conn.recvline()
conn.recvline(keepends=True) # 1: Encrypt
conn.recvline(keepends=True) # 2: Decrypt
conn.recvline(keepends=True) # 3: ChangeIV
conn.recvline(keepends=True) # 4: Give up
o1 = msg[0:32]
o2 = msg[32:64]
flag_part1 = ''
for i in range(0,32,2):
    flag_part1 += chr(int(o1[i:i+2],16)^int(o2[i:i+2],16)) # 每个字节进行异或
conn.sendline('3'.encode('utf-8'))
conn.recvline(keepends=True) # Which part of flag do you want to choose?
conn.sendline('1'.encode('utf-8'))
conn.recvline(keepends=True) # 1: Encrypt
conn.recvline(keepends=True) # 2: Decrypt
conn.recvline(keepends=True) # 3: ChangeIV
conn.recvline(keepends=True) # 4: Give up
conn.sendline('2'.encode('utf-8'))
conn.recvline(keepends=True) # Enter HEXADECIMAL cipher:
conn.sendline('00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000'.encode('utf-8'))
conn.recvline(keepends=True) # This is your message
msg = conn.recvline()
conn.recvline(keepends=True) # 1: Encrypt
conn.recvline(keepends=True) # 2: Decrypt
conn.recvline(keepends=True) # 3: ChangeIV
conn.recvline(keepends=True) # 4: Give up
o1 = msg[0:32]
o2 = msg[32:64]
flag_part2 = ''
for i in range(0,32,2):
    flag_part2 += chr(int(o1[i:i+2],16)^int(o2[i:i+2],16))
flag = flag_part1 + flag_part2
print(flag) # flag{finnalyrc4C0irWZWWZLnVdysE}