ByteCTF2022 Crypto wp

周末撞上MTCTF决赛了，ByteCTF没仔细研究。把做出的两道随便写写，等官方wp出来再学习学习吧~

Choose_U_Flag

题目源码：

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

NTRU加密，但是有一次decrypt的机会！题目只限制了dec_arr和key_coeffs不相等，由于加密过程, 其中m是二进制的且没有乘任何系数，那么我们偷偷在key_coeffs最后一位减一，解密得到的会是什么呢，嘿嘿。

这题应该是非预期了。听说预期解使用NTRU的选择密文攻击来做，参考论文。

解题脚本（可能会报错，多试几遍）：

from Crypto.Util.number import *
from Crypto.Hash import SHA3_256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from pwn import *

CHALLENGE_ID = 'e644151c5bb33cebf605f12f0dd86a2e'
sh = process(['./wscat', '--endpoint', 'wss://telnet.2022.capturetheflag.fun/ws/' + CHALLENGE_ID])

sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud  = lambda a     :sh.recvuntil(str(a),drop=True)


rud('[+]h_poly: ')
h = eval(rl().strip())
rud('[+]key coeffs: ')
key_enc=eval(rl().strip())
print(h)
print(key_enc)
my_enc=key_enc[:len(key_enc)-1]+[key_enc[-1]+1]
sla('decrypt data > ',str(my_enc))
rud('[+]decrypt coeffs: ')
my_dec=eval(rl().strip())
my_dec=''.join(map(str,my_dec))
key_tmp=long_to_bytes(int(my_dec,2))
key_tmp=list(key_tmp)
key_tmp[-1]-=1
key=bytes(key_tmp).decode('utf-8')
sla('u key > ',key)
sh.interactive()
#ByteCTF{9e8876cc-9eae-4178-b2b4-9a4c7ae0941f}

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同态加密，考察的是同态函数中对加密数据的大小比较。在题目中，先给出公钥相关信息和待比较数据a和b的加密值，然后有一次任意解密的机会，解密出的值存放在MSG变量中，但不会输出。我们需要在每轮中使用同一个表达式来确定a和b的大小关系。题目对eval中的表达式进行了过滤，我们只能使用MSG和常量之间的运算式。

假设同态加密函数为, 首先我们构造： 这里这样构造的原因是，当b<a时，x为N位；当b>a时，x为N+1位。

然后我们加上一个固定常量r，其比特长度略大于x即可，我这里取。

接下来计算： 然后把这个值算出来丢给题中解密，也即是令。

接着计算两个值： 当b<a时，有，此时c和d的值是相同的；当b>a时，有，此时d的值会比c刚好大1。至此，我们可以根据c和d的关系来判断a和b的大小。

解题脚本：

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

CHALLENGE_ID = 'bf3735ea56c9efa904820ce1dc898f80'
sh = process(['./wscat', '--endpoint', 'wss://telnet.2022.capturetheflag.fun/ws/' + CHALLENGE_ID])
context.log_level='debug'
sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud  = lambda a     :sh.recvuntil(str(a),drop=True)

N=512

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

def solve_round():
	rud('n =')
	n=int(rl().strip())
	rud('g =')
	g=int(rl().strip())
	rud('a =')
	enca=int(rl().strip())
	rud('b =')
	encb=int(rl().strip())
	encx=encb*encode(2**N,n,g)*inverse(enca,n**2)%n**2
	r=2**(N+10)
	encz=encx*encode(r,n,g)%n**2
	sla('msg = ',str(encz))

expr='2**10==MSG//(2**512)'
sla('expr: ',expr)
for _ in range(100):
	solve_round()
sh.interactive()
#ByteCTF{ed4dad6f-45a4-41bf-a538-fd5d0754b3df}