2022ByteCTF

CardShark

#!/usr/bin/env python3.9
# -*- coding: utf-8 -*-
import string
import random
import socketserver
import signal
from os import urandom
from hashlib import sha256
from flag import FLAG

BANNER = rb"""
.--------.--------.--------.--------.     .--------.--------.--------.--------.--------.
| C.--.  | A.--.  | R.--.  | D.--.  |.-.  | S.--.  | H.--.  | A.--.  | R.--.  | K.--.  |
|  :/\:  |  (\/)  |  :():  |  :/\:  (( )) |  :/\:  |  :/\:  |  (\/)  |  :():  |  :/\:  |
|  :\/:  |  :\/:  |  ()()  |  (__)  |'-.-.|  :\/:  |  (__)  |  :\/:  |  ()()  |  :\/:  |
|  '--'C |  '--'A |  '--'R |  '--'D | (( ))  '--'S |  '--'H |  '--'A |  '--'R |  '--'K |
`--------`--------`--------`--------'  '-'`--------`--------`--------`--------`--------'
"""


class Card:
    def __init__(self):
        random.seed(urandom(32))
        self.cards = []
        for t in ('Hearts', 'Spades', 'Diamonds', 'Clubs'):
            for p in ('J', 'Q', 'K', 'A'):
                self.cards.append(f'{p} {t}')

    def deal(self):
        n = random.getrandbits(4)
        return self.cards[n]


class Task(socketserver.BaseRequestHandler):
    def _recv_all(self):
        BUFF_SIZE = 1024
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        if isinstance(msg, str):
            msg = msg.encode()
        if newline:
            msg += b'\n'
        self.request.sendall(msg)

    def recv(self, prompt='> '):
        self.send(prompt, newline=False)
        return self._recv_all()

    def proof_of_work(self):
        random.seed(urandom(32))
        alphabet = string.ascii_letters + string.digits
        proof = ''.join(random.choices(alphabet, k=32))
        hash_value = sha256(proof.encode()).hexdigest()
        self.send(f'sha256(XXXX+{proof[4:]}) == {hash_value}')
        nonce = self.recv(prompt='Give me XXXX > ')
        if len(nonce) != 4 or sha256(nonce + proof[4:].encode()).hexdigest() != hash_value:
            return False
        return True

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

    def handle(self):
        try:
            self.send(BANNER)

            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(60)

            if not self.proof_of_work():
                self.send('Wrong!')
                return

            card = Card()
            coin = 5200
            count = 0

            self.send('Greetings! I will give you my secret, if you can guess my card 200 times in a row. '
                      'One coin, one chance.')

            signal.alarm(3600)

            while coin > 0:
                coin -= 1
                c = card.deal()
                r = self.recv(prompt='Your guess > ').decode('l1')
                if r == c:
                    count += 1
                    self.send(f'Correct! Your progress: {count}/200.')
                    if count >= 200:
                        self.send('You are the Card Shark! Flag is yours:')
                        self.send(FLAG)
                        break
                else:
                    count = 0
                    self.send(f'Sorry! My card is {c}.')

            if coin == 0:
                self.send('You have no money! See you another day.')

            self.send('Bye!')

        except TimeoutError:
            self.send('Timeout!')
        except:
            pass
        finally:
            self.request.close()


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


if __name__ == '__main__':
    HOST, PORT = '0.0.0.0', 10000
    print(HOST, PORT)
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

审计代码，容易看出先是四位哈希爆破，然后是随机数预测问题。但起初以为可以用RandCrack来解决这个随机数预测问题，看来是想简单了。

随即预测工具：JuliaPoo/MT19937-Symbolic-Execution-and-Solver: Python implementation of a symbolic execution of MT19937 and a solver for GF(2) matrices (github.com)

相似题目：浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)

from pwn import *
from Crypto.Util.number import *
from hashlib import sha256
import string
from randcrack import RandCrack
from tqdm import tqdm
from MT19937 import MT19937, MT19937_symbolic

alphabet = string.ascii_letters + string.digits

def proof(hash, part):
    for a in alphabet:
        for b in alphabet:
            for c in alphabet:
                for d in alphabet:
                    s = (a+b+c+d).encode() + part
                    if sha256(s).hexdigest() == hash.decode():
                        print(f'Found XXXX: {a+b+c+d}')
                        return a+b+c+d


ID = 'dcb894124cb27c186d8a996bdbb43602'
s = remote(ID + '.2022.capturetheflag.fun', 1337, ssl=True)
s.recvuntil(b'XXX+')
part = s.recvuntil(b')')[:-1]
s.recvuntil(b'== ')
hash = s.recvline()[:-1]

s.send(proof(hash, part).encode())

cards = []
for t in ('Hearts', 'Spades', 'Diamonds', 'Clubs'):
     for p in ('J', 'Q', 'K', 'A'):
           cards.append(f'{p} {t}')

known = []
for i in tqdm(range(4992)):
    s.send('J'.encode())
    s.recvuntil(b'is ')
    key = s.recvline()[:-2].decode()
    pos = cards.index(key)
    known.append(pos)

'''
#预测
rc = RandCrack()
for i in known:
    rc.submit(i)

cnt = 0
for i in tqdm(range(205)):
    pos = rc.predict_getrandbits(4)
    s.send(cards[pos].encode())
    res = s.recvline().decode()
    print(res)
    if 'Correct' in res:
        cnt += 1
        if cnt >= 200:
            s.interactive()
'''
#预测
rc = MT19937(state_from_data=(known, 4))

#好像一开始是初始态，得先过4992个
for i in known:
    assert i == rc() >> (32-4)
print("[*] Cloning successful!")

cnt = 0
for i in range(205):
    pos = rc() >> (32-4)
    # s.sendlineafter(b'Your guess > ', cards[pos].encode())
    s.send(cards[pos].encode())
    res = s.recvline().decode()
    print(res)
    if 'Correct' in res:
        cnt += 1
        if cnt >= 200:
            s.interactive()

Compare

from Crypto.Util.number import getPrime, getRandomNBitInteger, inverse
from fractions import Fraction
from gmpy2 import lcm
import re

N = 512
safe_expr = re.compile(r'^([-+*/0-9.~%^&()=|<>]|and|or|not|MSG)+$')


def encode(m, n, g):
    r = getRandomNBitInteger(N)
    c = pow(g, m, n*n) * pow(r, n, n*n) % (n*n)
    return c


def decode(c, n, l, u):
    return int(Fraction(pow(c, l, n * n) - 1, n) * u % n)


def round(expr):
    p = getPrime(N)
    q = getPrime(N)

    n = p * q
    g = getRandomNBitInteger(N)
    print('n =', n)
    print('g =', g)

    a = getRandomNBitInteger(N)
    b = getRandomNBitInteger(N)

    print('a =', encode(a, n, g))
    print('b =', encode(b, n, g))

    msg = int(input("msg = "))

    l = int(lcm(p - 1, q - 1))
    u = inverse(Fraction(pow(g, l, n * n) - 1, n), n)

    return (a > b) is bool(eval(expr, None, {'MSG': decode(msg, n, l, u)}))


def main():
    expr = input('Hello, Give me your expr: ')
    expr = re.sub(r'\s', '', expr)


    if safe_expr.match(expr) is None:
        raise Exception('Hacker?')

    for i in range(100):
        print('Round:', i)
        try:
            assert round(expr)
        except:
            print('You lost.')
            break
    else:
        print('Congratulations!')
        print(open('/flag').read())


if __name__ == '__main__':
    main()

Paillier同态加密，由于其满足加法同态，即
$$
\begin{cases}
E(a) = g^a*r_1^n\quad mod\ n^2\\
E(b) = g^b*r_2^n\quad mod\ n^2\\
\end{cases}
$$

$$
==> E(a+b) = E(a)*E(b) = g^{a+b}*(r_1*r_2)^n\quad mod\ n^2
$$

那么解密就会得到
$$
D(E(a)*E(b))=a+b
$$
我们只要稍微改变一下就可以得到$a-b$，过程如下

对$E(b)$取逆得
$$
E(b)^{-1} = g^{-b}*(r_2^{-1})^n\quad mod\ n^2
$$
$E(a)*E(b)^{-1}$得
$$
E(a)*E(b)^{-1} = g^{a-b}*(r_1*r_2^{-1})^n\quad mod\ n^2
$$
因此解密就得到
$$
D(E(a)*E(b)^{-1})=a-b
$$
如何构造expr？如果$a-b>0$，则$(a-b)\%2^{1024}<=2^{512}$，但如果$a-b<0$，则$(a-b)\%n>2^{512}$左右，因此可以构造expr为$MSG\%2^{1024}<=2^{512}$。当然也可以根据正负数对整除符号的运算结果的差异性构造$MSG//2^{512}==0$。

代码如下

from pwn import *
from gmpy2 import invert

ID = 'dcb894124cb27c186d8a996bdbb43602'
s = remote(ID + '.2022.capturetheflag.fun', 1337, ssl=True)

MSG = b'MSG//2**512==0'
s.recvuntil(b'expr: ')
s.send(MSG)

for i in range(100):
    s.recvuntil(b'n =')
    n = int(s.recvline()[:-1].decode())
    s.recvuntil(b'g =')
    g = int(s.recvline()[:-1].decode())
    s.recvuntil(b'a =')
    a = int(s.recvline()[:-1].decode())
    s.recvuntil(b'b =')
    b = int(s.recvline()[:-1].decode())
    inv_b = int(invert(b, n**2))
    msg = a*inv_b % (n**2)
    s.recvuntil(b'msg = ')
    s.send(str(msg).encode())
    # r.sendlineafter(b'msg = ', f'{x}'.encode())
s.interactive()

Choose_U_Flag

给出两个代码，其中task.py如下

import ast
import random
import signal
import string
import os

import numpy as np
from sympy import ZZ, Poly
from sympy.abc import x

from ntru import NTRUCipher


def exitHandler(signum, frame):
    print("timeout")
    exit()


signal.signal(signal.SIGALRM, exitHandler)
signal.alarm(30)

flag = os.environ.get("CTF_CHALLENGE_FLAG")

N = 107
p = 3
q = 64

cipher = NTRUCipher(N, p, q)
cipher.generate()
print(f"[+]h_poly: {cipher.h_poly.all_coeffs()}")

random_key = ''.join(random.sample(string.printable, 12))
key_arr = np.unpackbits(np.frombuffer(random_key.encode(), dtype=np.uint8))
key_enc = cipher.encrypt(Poly(key_arr, x).set_domain(ZZ))
key_coeffs = key_enc.all_coeffs()
print(f"[+]key coeffs: {key_coeffs}")

dec_data = input("decrypt data > ")
dec_arr = ast.literal_eval(dec_data)
if dec_arr == key_coeffs:
    exit(-1)
dec = cipher.decrypt(Poly(dec_arr, x).set_domain(ZZ))
dec_coeffs = dec.all_coeffs()
print(f"[+]decrypt coeffs: {dec_coeffs}")

while N > 0:
    try:
        u_key = input("u key > ")
        if u_key == random_key:
            print(flag)
            exit(-1)
        else:
            print("key err")
    except:
        print("input err")
    N = N - 1

给出了$N,p,q,h,c$，允许我们提供$c’(!=c)$，求出$key$。其实只要给$c$加个模数就能绕过这个限制条件，从而得到的解密内容即为$key$。

根据NTRU的解密过程，有
$$
a = f*c\mod (q)
$$
因为模数是$q$，所以添加$q$仍然可以得到正确的$a$
$$
a = f*(c+q)=f*c\mod (q)
$$

不管NTRU是建立在多项式上还是整数上，其加解密原理是不变的。

代码如下（没环境了，只能贴一下别人的代码）

from Crypto.Util.number import *
from pwn import *

CHALLENGE_ID = 'bb3fcb3fc9708bfdcdf710895615ba6e'
sh = remote(CHALLENGE_ID + '.2022.capturetheflag.fun', 1337, ssl=True)

sh.recvuntil("[+]key coeffs: ")
cipher = eval(sh.recvline(False))
cipher[-1] += 64

sh.recvuntil("> ")
sh.sendline(str(cipher).encode())

sh.recvuntil("coeffs: ")
key = eval(sh.recvline(False))

tmp = ''
for i in key:
    tmp += str(i)
res = long_to_bytes(int(tmp, 2))
sh.recvuntil("> ")
sh.sendline(res)
flag = sh.recvline(False)
print(flag)

# sh.interactive()
sh.close()

---

要是不知道这些函数的功能，就挨个试一下。

random.sample(string.printable, 12)#随机产生12个可打印字符
np.frombuffer(random_key.encode(), dtype=np.uint8)#转成数组，数据好像是字符ord()
np.unpackbits()#转成二进制数组，即数据二进制化
Poly(key_arr, x).set_domain(ZZ)#以key_arr的数据为系数，x为变量，在整数域上的多项式
np.zeros(len)#全0数组,长度为len
np.ones(len)#全1数组
np.concatenate((x,y,z))#连接x,y,z，组成一个数组
np.random.permutation()#随机排列
(rand_poly * self.h_poly).trunc(self.q)
h_poly.all_coeffs()#多项式转换成系数数组

---

参考：

其他加密算法 | Lazzaro (lazzzaro.github.io)

ByteCTF 2022 By W&M - W&M Team (wm-team.cn)

ByteCTF WriteUp By Nu1L.pdf