Red Hat Cup 2021(红帽杯) Writeup

2021-05-11

字数统计: 1.8k字 | 阅读时长≈ 9分

这应该是暑假前打的最后一场CTF了，后面准备保研直接摊开了。

EBCDIC

MISC 签到题，直接送分的。提示EBCDIC编码，拿python或者编辑器改一下编码就行。

data = "86 93 81 87 C0 A6 85 F1 83 F0 94 85 6D A3 F0 6D 99 85 84 88 81 A3 F2 F0 F2 F1 D0"
data = bytes.fromhex(data)
print(data)
dt = ''.join(data.decode('cp500'))
print(dt)

1	flag{we1c0me_t0_redhat2021}

Colorful code

MISC的题大都是脑洞题。这个题只提示了colorful code，一开始我以为只是说的是RGB的颜色代码如#FFFFC0等，但是思路也基本正确。给了data1和data2两个文件。观察两个文件如下。

第一个文件全是数字与空格，拿python统计一下数字范围在0~19内，再看第二个文件，后面都是三个相同的字母连起来，其十六进制值从0x14到0xFF，这些信息都是没用的，那么大概率只有前面的60字节是有用的信息，每三个一组作为颜色代码的RGB值，刚好20个和data1的数字范围对应。那么data作为像素值代入进行图像的矩阵构建，应该就是正确的思路了。

还有一个问题是我们不知道图像的宽和高。对data1内像素的数量进行简单计算：

data = open("data1", "r").read().split(" ")
data = list(filter(None, data))
print(len(data))
# 7076=37*191

那么图像的宽高应该是37*191或者反过来。

转换图像的代码如下：

from PIL import Image
color = [(0x00,0x00,0x00),(0x00,0x00,0xc0),(0x00,0xff,0xff),(0x00,0xff,0x00),(0xff,0xc0,0xff),(0xff,0xc0,0xc0),(0xc0,0xc0,0xff),(0xc0,0xc0,0x00),(0xff,0x00,0xff),(0xff,0x00,0x00),(0xc0,0x00,0x00),(0xc0,0x00,0xc0),(0xff,0xff,0xff),(0xff,0xff,0x00),(0xff,0xff,0xc0),(0x00,0xc0,0x00),(0x00,0xc0,0xc0),(0xc0,0xff,0xff),(0xc0,0xff,0xc0),(0x00,0x00,0xff)]
data=open('data1',"r").read().split(" ")[:-1]
img = Image.new("RGB",(37,191))
for i in range(37):
    for j in range(191):
        img.putpixel((i,j),color[int(data[i*191+j])])        
img.save('flag.png')

from PIL import Image
im = Image.new("RGB", (37,191))
# im = Image.new("RGB", (191,37))

infile = open('data1', 'r')
hide = "00 00 00 00 00 C0 00 FF FF 00 FF 00 FF C0 FF FF C0 C0 C0 C0 FF C0 C0 00 FF 00 FF FF 00 00 C0 00 00 C0 00 C0 FF FF FF FF FF 00 FF FF C0 00 C0 00 00 C0 C0 C0 FF FF C0 FF C0 00 00 FF".split(
    " ")
data = infile.read().strip('\n').split(" ")
data = list(filter(None, data))

key_set = []
for i in range(20):
    print(data.count(str(i)))
for i in range(len(hide)//3):
    key = hide[3*i]+hide[3*i+1]+hide[3*i+2]
    key_set.append(key)
print(key_set)

rgblist = []

for x in data:
  v = key_set[int(x)]
  rgb = (int(v[:2],16),int(v[2:4],16),int(v[4:],16))
  rgblist.append(rgb)
im.putdata(rgblist)
im.save("flag.png")

这里给了两个脚本，想说明一下这两个脚本解出来的图像是不一样的，因为python的putdata或者用reshape来自动化重构像素矩阵，它默认的像素序列的填充方式是先横轴再纵轴，而这个题像素重构的正确方向是先纵轴再横轴，所以后一个脚本得到的图像拿不到正确的flag。

后面就是真正的colorful code所代表的的编程语言PIET，然后这里mark一下一些脑洞大开的编程语言，可能有一些奇奇怪怪的隐写题会用到。

最后把得到的图像放到在线编译网站即可得到flag。（或者可以去github下载python对应的编译包）

primegame

这次的crypto题目简直离谱，虽然有难度，但是都是前面比赛出现过的原题的一丢丢魔改就拿来出题。所以基本上你会Google基本就能AK。

这个的原题writeup链接：Pokajeon / Kapojeon 2020

server 源代码

#!/usr/bin/env python3

from decimal import *
import math
import random
import struct
# from flag import flag

flag=b"123456"*6
assert (len(flag) == 48)
msg1 = flag[:24]
msg2 = flag[24:]
primes = [2]
for i in range(3, 90):
    f = True
    for j in primes:
        if i * i < j:
            break
        if i % j == 0:
            f = False
            break
    if f:
        primes.append(i)

print(primes)

getcontext().prec = 100
keys = []
for i in range(len(msg1)):
    keys.append(Decimal(primes[i]).ln())

print(keys)

sum_ = Decimal(0.0)
for i, c in enumerate(msg1):
    # print(i,c)
    sum_ += c * Decimal(keys[i])

ct = math.floor(sum_ * 2 ** 256)
print(ct)

sum_ = Decimal(0.0)
for i, c in enumerate(msg2):
    sum_ += c * Decimal(keys[i])

ct = math.floor(sum_ * 2 ** 256)
print(ct)

类似0/1背包问题，将[3,89]的素数的自然对数值作为密钥，然后和flag的每个byte乘后累加，最后再乘以2²⁵⁶。

恢复方法是低密度攻击。然后不管这些，其实魔改writeup的代码即可

# sagemath
import math
from decimal import *
import random
import struct

getcontext().prec = int(100)

primes = [2]
for i in range(3, 90):
    f = True
    for j in primes:
        if i * i < j:
            break
        if i % j == 0:
            f = False
            break
    if f:
        primes.append(i)

keys = []
for i in range(len(primes)):
    keys.append(Decimal(int(primes[i])).ln())

arr = []
for v in keys:
    arr.append(int(v * int(16) ** int(64)))

ct = 425985475047781336789963300910446852783032712598571885345660550546372063410589918
# ct = 597952043660446249020184773232983974017780255881942379044454676980646417087515453
def encrypt(res):
    h = Decimal(int(0))
    for i in range(len(keys)):
        h += res[i] * keys[i]

    ct = int(h * int(16)**int(64))
    return ct

def f(N):
    ln = len(arr)
    A = Matrix(ZZ, ln + 1, ln + 1)
    for i in range(ln):
        A[i, i] = 1
        A[i, ln] = arr[i] // N
        A[ln, i] = 64

    A[ln, ln] = ct // N

    res = A.LLL()

    for i in range(ln + 1):
        flag = True
        for j in range(ln):
            if -64 <= res[i][j] < 64:
                continue
            flag = False
            break
        if flag:
            vec = [int(v + 64) for v in res[i][:-1]]
            ret = encrypt(vec)
            if ret == ct:
                print(N, bytes(vec))
            else:
                print("NO", ret, bytes(vec))

for i in range(2, 10000):
    print(i)
    f(i)
# b'flag{715c39c3-1b46-4c23-8006-27b43eba2446}\x00\x00\x00\x00\x00\x00\x00'

hpcurve

然后这个题也是一次CTF的原题： hxpCTF 2020。

基本就改了加密的时候异或的密钥长度比明文长度长，所以取余即可。

server:

#!/usr/bin/env sage
import struct
from random import SystemRandom

p = 10000000000000001119
R.<x> = GF(p)[]
y=x
f = y + y^7
C = HyperellipticCurve(f, 0)
J = C.jacobian()

es = [SystemRandom().randrange(p**3) for _ in range(3)]
Ds = [J(C(x, min(f(x).sqrt(0,1)))) for x in (11,22,33)]
q = []

def clk():
	global Ds,es
	Ds = [e*D for e,D in zip(es, Ds)]
	return Ds

def generate():
    
    u,v = sum(clk())
    rs = [u[i] for i in range(3)] + [v[i] for i in range(3)]
    assert 0 not in rs and 1 not in rs
    q = struct.pack('<'+'Q'*len(rs), *rs)
    return q


flag = "flag{xxxxxxx}"
text = 'a'*20+flag
t = ''
keys = generate()
leng = len(keys)
i = 0
for x in text:
    t += chr(ord(keys[i%leng])^^ord(x))
    i+=1
print t.encode('hex')
#for x,y in zip(RNG(),flag):

solve:

from itertools import product
import struct
p = 10000000000000001119

K = GF(p)
R.<x> = K[]; y=x
f = y + prod(map(eval, 'yyyyyyy'))
C = HyperellipticCurve(f, 0)
J = C.jacobian()

def get_u_from_out(output, known_input):
    res = []
    for i in range(24):
        res.append(output[i]^^known_input[i])
    res = bytes(res)
    u0, u1, u2 = struct.unpack("<QQQ", res)
    u = x^3+x^2*u2+x*u1+u0
    return u

def get_v_from_u(u):
    Kbar = GF(p^6)
    Rbar.<t> = Kbar["t"]
    u2 = u.change_ring(Rbar)
    roots = [x[0] for x in u2.roots()]
    ys = []
    for root in roots:
        ys.append(f(root).sqrt(0,1))
    res = []
    for perm in product(range(2), repeat=3):
        poly = Rbar.lagrange_polynomial([(roots[i], ys[i][perm[i]]) for i in range(3)])
        if poly[0] in K:
            res.append(R(poly))
    return res

def try_decode(output, u, v):
    rs = [u[0], u[1], u[2], v[0], v[1], v[2]]
    otp = struct.pack("<QQQQQQ", *rs)
    l=len(otp)
    plain = []
    for i in range(len(output)):
        plain.append(output[i]^^otp[i%l])
    return bytes(plain)


output = bytes.fromhex("66def695b20eeae3141ea80240e9bc7138c8fc5aef20532282944ebbbad76a6e17446e92de5512091fe81255eb34a0e22a86a090e25dbbe3141aff0542f5")
known_input = b"a"*20+b"flag"
u = get_u_from_out(output, known_input)
vs = get_v_from_u(u)
for v in vs:
    print(try_decode(output,u,v))
# flag{1b82f60a-43ab-4f18-8ccc-97d120aae6fc}