2024-京麒CTF-wp-crypto

三道后量子题目，记录一下目前能够理解的两道。

*BabyOracle1

题目：

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import random
import os
FLAG = os.environ.get("FLAG", "jdctf{XXX_FAKE_FLAG_XXX}")

class Oracle:
    def __init__(self, k, n):
        F = GF(2^10)
        R.<x> = F[]
        self.g = x^50 + x^3 + 1
        self.L = [a for a in F.list() if self.g(a) != 0]
        self.Gp = self.Gen(k, n)
        self.t = 160
        self.key = os.urandom(16)

    def Gen(self, k, n):
        seed = random.randrange(0, 2**64)
        print("🌱", seed)
        set_random_seed(seed)
        G = codes.GoppaCode(self.g, self.L).generator_matrix()
        P = Permutations(n).random_element().to_matrix()
        S = random_matrix(GF(2), k, k)
        return S*G*P

    def encode(self, msg):
        e = [random.randrange(0, 2) for _ in range(self.t)]+[0]*(1024-self.t)
        random.shuffle(e)
        return vector(GF(2), msg)*self.Gp+vector(GF(2), e)

    def ENC(self, msg):
        return AES.new(self.key, AES.MODE_ECB).encrypt(msg).hex()

sys = Oracle(524, 1024)
time = 3
print("""[A]ES\n[E]ncode""")
while time:
    time -= 1
    op = input("> ")
    if op == 'A':
        mode = input("encrypt msg? y/n ")
        if mode == 'y':
            msg = bytes.fromhex(input("msg:"))
            print(sys.ENC(pad(msg, 16)))
        elif mode == 'n':
            print(sys.ENC(pad(FLAG.encode(), 16)))
    elif op == 'E':
        mode = input("encrypt msg? y/n ")
        if mode == 'y':
            msg = Integer(input("msg:"), 16)
            word = msg.bits()[::-1]
            print(sys.encode([0]*(524-len(word))+word))
        elif mode == 'n':
            msg = Integer(sys.key.hex(), 16)
            word = msg.bits()[::-1]
            print(sys.encode([0]*(524-len(word))+word))
    else:
        print("Under construction ...")
        break

题目基于用Goppa codes的McEliece System的实现，会先生成如下数据：

• 私钥矩阵G、P、S
• 公钥矩阵Gp = SGP
• 随机AES密钥key

提供三次交互机会，可以做以下事情：

• A,y：可以输入一条msg，拿到他的AES加密密文
• A,n：拿到flag的AES加密密文
• E,y：可以输入一条msg，拿到他的encode结果
• E,n：拿到AES的key的encode结果

由于只有三次交互机会，四个选项肯定不会全用。而稍微思考下就知道Ay选项显然是零帮助，所以主要是要想剩下几个怎么用。

而题目给出了一个seed值，在给定seed的情况下，其实作为私钥的S、P矩阵都能够确定，而生成矩阵G本身就是定的，所以说等于整个私钥全知道。因此我赛中的考虑是：

• 第一次机会，输入En，记得到结果为c，就有：

  $$c = key \cdot (SGP) + e$$

  对于McEliece System来说，在知道私钥的情况下解码是这样的：

  $$cP^{-1} = key \cdot SG + eP^{-1}$$

  由于P^(-1)依然仅仅是做了置换，所以error的weight并不会变化，此时就可以对cP^(-1)做decode得到keyS，然后再求逆就得到key了。

• 第二次机会，输入An，然后用key去解密

然后赛中遇到的问题是sage似乎没有内置函数，可以对goppa codes进行有效的解码，所以捣鼓了好一会儿这个。赛后在yolbby的提示下发现，由于g(x)的度仅有50，记为t，而goppa codes的纠错能力如下：

可以算出就是最多纠50个错，因此对于期望为80的weight来说解码可能不太现实，这才是最根本的原因。

赛后请教了hashhash师傅这个问题，解决方法很简单——这个题和goppa codes并没有那么大的关联，由于有三次机会，所以可以输入两次En，就得到：

$$c_1 = key \cdot (SGP) + e_1$$ $$c_2 = key \cdot (SGP) + e_2$$

作差：

$$c_1 - c_2 = e_1 - e_2$$

由于e1、e2都是weight在80左右的error，所以说通过这个差值可以确定较大部分error的位置，仅有小部分可能由于位置相同而正好减掉。然而由于对于任意一次的密文都有：

$$c_1 = key \cdot (SGP) + e_1$$

key仅有524个变量，所以我们选择e1、e2差值里为0的位置，他极大可能也是e1、e2共同为0的位置，所以选择其中524个位置去构造一个满秩矩阵方程就可以得到key了。

如果524还是很容易选到错误位置的话，由于key仅有128bit，前面全部由0在填充，所以其实选128组应该也就可以了。靶机关了，放点测试脚本吧：

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

################################################### preset data
k,n = 524, 1024
F = GF(2^10)
R.<x> = F[]
g = x^50 + x^3 + 1
L = [a for a in F.list() if g(a) != 0]
t = 160
Co = codes.GoppaCode(g, L)

################################################### set data
seed = bytes_to_long(b"seed")
set_random_seed(seed)
G = Co.generator_matrix()
P = Permutations(n).random_element().to_matrix()
S = random_matrix(GF(2), k, k)
Gp = S*G*P


import random
def encode(msg,t=160):
    e = [random.randrange(0, 2) for _ in range(t)]+[0]*(1024-t)
    random.shuffle(e)
    return vector(GF(2), msg)*Gp+vector(GF(2), e)


key = b"1234567812345678"
msg = Integer(key.hex(), 16)
word = msg.bits()[::-1]
e1 = encode(vector(GF(2),[0]*(524-len(word))+word))
e2 = encode(vector(GF(2),[0]*(524-len(word))+word))

sum1 = 0
for i in (e1-e2):
    if(i == 1):
        sum1 += 1
print(sum1)

BabyOracle2

题目：

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import md5
import os
FLAG = os.environ.get("FLAG", "jdctf{XXX_FAKE_FLAG_XXX}")

a, b = 216, 137
p = 2^a*3^b-1
F.<i> = GF(p^2, modulus=x^2+1)
E0 = EllipticCurve(F, [0,6,0,1,0])
Iso = lambda E,P: E.isogeny(P, algorithm="factored")

class Oracle:
    def __init__(self):
        self.P1, self.P2 = E0.torsion_basis(2^a)
        self.Q1, self.Q2 = E0.torsion_basis(3^b)
        self.Alice, self.Bob, self.aux = self.Gen()
        self.J, self.Eb = self.Set_J()

    def Gen(self):
        ska = randrange(2^a)
        skb = randrange(3^b)
        print("🔑 sk:", skb)
        R = self.P1+ska*self.P2
        S = self.Q1+skb*self.Q2
        phia = Iso(E0, R)
        phib = Iso(E0, S)
        Qa1, Qa2 = phia(self.Q1), phia(self.Q2)
        Pb1, Pb2 = phib(self.P1), phib(self.P2)
        return (R, ska), (S, skb), (Pb1, Pb2, Qa1, Qa2)

    def Set_J(self):
        Alice, Bob = self.Alice, self.Bob
        Ea = Iso(E0, Alice[0]).codomain()
        Ra = self.aux[0]+Alice[1]*self.aux[1]
        Eb = Iso(E0, Bob[0]).codomain()
        Sb = self.aux[2]+Bob[1]*self.aux[3]
        Eba = Iso(Eb, Ra).codomain()
        Eab = Iso(Ea, Sb).codomain()
        assert Eab.j_invariant() == Eba.j_invariant()
        return Eab.j_invariant(), Eb

    def KE(self):
        Pb = input("Bob/Image: ").split(',')
        Pb1, Pb2 = self.Eb(Pb[:2]), self.Eb(Pb[2:])
        Ra = Pb1+self.Alice[1]*Pb2
        return Iso(self.Eb, Ra).codomain().j_invariant() == self.J

    def ENC(self, msg):
        aes = AES.new(md5(str(self.J).encode()).digest(), AES.MODE_ECB)
        return aes.encrypt(pad(msg.encode(), 16)).hex()

sys = Oracle()
print("""[E]nc FLAG 🔐\n[K]ey Exchange ♻️""")
while True:
    op = input("> ")
    if op == 'E':
        print("C:", sys.ENC(FLAG))
    elif op == 'K':
        print("KE:", sys.KE())
    else:
        print("Under construction ...")
        break

题目基于同源，他先是完成了一次完整的SIKE，并且泄露了Bob的私钥skb，然后用共享密钥J的md5作为AES的密钥去加密flag。按顺序整理一下全部知道的值有：

$$P_1,P_2,Q_1,Q_2$$ $$skb,S,\phi_b$$ $$P_{b1},P_{b2},E_b$$

然后对于无限次的oracle来说，选项E肯定是要用一次来拿flag的密文的，主要是看选项K能怎么用。选项K的作用是，我们能发送Eb上的两个点，这里我记为R和S，然后靶机会计算：

$$Ra = R + ska\cdot S$$

并返回如下判断结果：

$$Iso(Eb,Ra) == E_{ba}$$

由于Eba就是共享密钥，所以其实这个返回结果等价于在判断：

$$R + ska\cdot S == P_{b1} + ska\cdot P_{b2}$$

所以核心要围绕着怎么构造这样的R、S。

由于Pb1，Pb2都是2^a-torsion的点且阶都为2^a，也就有：

$$2^aP_{b1} = 2^aP_{b2} = O$$ $$2^{a-1}P_{b1} \neq O$$ $$2^{a-1}P_{b2} \neq O$$

这其实也说明：

$$2^a(xP_{b1} + yP_{b2}) = O$$

所以也就想到一个类似于RSA的LSB-oracle的思路，从最低位开始构造：

$$R = P_{b1} - t2^{a-1} \cdot P_{b2}$$ $$S = (1 + 2^{a-1}) \cdot P_{b2}$$

此时有：

$$Ra = P_{b1} - t2^{a-1} \cdot P_{b2} + ska\cdot (1 + 2^{a-1}) \cdot P_{b2}$$

稍微做下整理是：

$$Ra = (P_{b1} + ska \cdot P_{b2}) + 2^{a-1}(ska- t) \cdot P_{b2}$$

此时就可以看出，如果ska-t模2为0，那么后一项由于Pb2阶为2^a的缘故，靶机会返回True；否则靶机会返回False。这就得到了ska的LSB，之后依次类推即可。

exp：

from Pwn4Sage.pwn import *
from Crypto.Cipher import AES
from hashlib import md5
from tqdm import *

sh = remote("146.56.221.86",1338)

######################################################### get skb
sh.recvuntil(b"sk: ")
skb = int(sh.recvline().strip().decode())

######################################################### gen data
a, b = 216, 137
p = 2^a*3^b-1
F.<i> = GF(p^2, modulus=x^2+1)
E0 = EllipticCurve(F, [0,6,0,1,0])
Iso = lambda E,P: E.isogeny(P, algorithm="factored")
P1, P2 = E0.torsion_basis(2^a)
Q1, Q2 = E0.torsion_basis(3^b)
S = Q1+skb*Q2
phib = Iso(E0, S)
Eb = phib.codomain()
Pb1, Pb2 = phib(P1), phib(P2)


######################################################### get cipher
sh.recvuntil(b"> ")
sh.sendline(b'E')
sh.recvuntil(b"C:")
cipher = sh.recvline().strip().decode()

######################################################### oracle
sa_lsb = 0
for i in trange(216):
    for xx in range(2):
        sh.recvuntil(b"> ")
        sh.sendline(b'K')

        RR = Pb1 - ((sa_lsb+xx*2^i)*2^(a-i-1)) * Pb2
        SS = (1 + 2^(a-i-1)) * Pb2
        msg = str(RR.xy()[0]) + "," + str(RR.xy()[1]) + "," + str(SS.xy()[0]) + "," + str(SS.xy()[1])
        sh.sendline(msg.encode())
        sh.recvuntil(b"KE:")

        res = sh.recvline()
        if(b"True" in res):
            sa_lsb += xx*2^i
            break


ska = sa_lsb
Ra = Pb1 + ska*Pb2
Eba = Iso(Eb, Ra).codomain()
J = Eba.j_invariant()

aes = AES.new(md5(str(J).encode()).digest(), AES.MODE_ECB)
print(aes.decrypt(bytes.fromhex(cipher)))


#jdctf{S1mpl3_GPST_att@ck_on_SIDH}