CryptoCTF 2023 hard分类团队解题writeup 之二

这次 hard 分类也有 5 题，虽然思维方面肯定比 medium 要难些，但也还中规中矩。

Vinefruit

题目描述

题目定义了一个函数 $f$：输入一个消息 $m$，记该消息的每个字节的内容分别为 $m_1, m_2, \ldots, m_l$。$v_0$ 已知，然后满足一个递推关系：

$v_i = (p \cdot (v_{i-1} + m_i)) \bmod 2^{128}$

其中 $p$ 已知。根据这个迭代式一直计算，返回 $f(m) = v_l$。

给定 $l$，需要给出 $m, m’$ 使得 $f(m) = f(m’)$，且 $f(m)$ 在之后的关卡中不能和之前已经用过的 $f(m)$ 相等。

我的解答

可以把那个迭代式展开，得：

$v_l \equiv p^l v_0 + \sum_{i=1}^{l}p^{l-i+1}m_i \pmod{2^{128}}$

把 $m’$ 的各项也代入到上式，两式相减，并记 $d_i = m_i - m_i’$，我们便有：

$\sum_{i=1}^{l}p^{l-i}d_i \equiv 0 \pmod{2^{128}}$

且有 $d_i \in \{-255, -254, \ldots, 255\}$。

那么由于 $d_i$ 较小，这就是经典的格基规约问题了，可构造如下格（把同余式写成等式→把系数非 1 的项都往等号右边丢→写成线性组合）：

$\begin{bmatrix} d_1 & d_2 & \ldots & d_{l-1} & k \end{bmatrix}\begin{bmatrix} 1 & 0 & \ldots & 0 & p^{l-1} \\ 0 & 1 & \ldots & 0 & p^{l-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & 1 & p \\ 0 & 0 & \ldots & 0 & 2^{128} \end{bmatrix} = \begin{bmatrix} d_1 & d_2 & \ldots & d_{l-1} & -d_l \end{bmatrix}$

上面这个公式好像手机 app 端会渲染出问题，用 PC 的 web 端能正常显示，检查了几遍都没发现有语法问题，奇怪奇怪真奇怪

我已经没耐心去调这公式的写法以迎合 app 端的 markdown 解析逻辑了，大家自行前往 web 端看吧

然后规约即可。然后再设 $m_i$ 和 $m_i’$ 的值：

当 $d_i < 0$ 时，设 $m_i = 0, m_i’ = -d_i$
当 $d_i \ge 0$ 时，设 $m_i = d_i, m_i’ = 0$

然后其实，如果能对于最小的 $l$ 有解 $(m, m’)$ 的话，可以直接把更长的解构造为 $(m || 0, m’ || 0)$，这样就能完成剩下的构造，不过注意每一组 $p$ 和 $v_0$ 会在某几组里面挑

规约出结果的代码如下：

def my_solve(v0, p):
    l = 18
    M = [[0 for j in range(l)] for i in range(l)]
    for i in range(l-1):
        M[i][i] = 1
        M[i][l-1] = p^(l-i-1)
    M[l-1][l-1] = 2^128

    M = Matrix(ZZ, M)
    v = M.LLL()[0]
    vlist = v.list()
    vlist[-1] = -vlist[-1]
    print(vlist)

P = [16777619, 1099511628211, 309485009821345068724781371]
O = [2166136261, 14695981039346656037, 144066263297769815596495629667062367629]

for v0, p in zip(O, P):
    my_solve(v0, p)

提交答案的代码如下：

from pwn import *

context.log_level = 'debug'

class Gao:
    def __init__(self):
        # self.conn = process(['python3', 'another.py'])
        self.conn = remote('04.cr.yp.toc.tf', 31777)
        self.ans = [
            [40, -13, 23, 37, -8, -10, -81, -14, 17, 8, 44, -39, -23, 2, 3, -28, 85, -11],
            [-20, 18, 31, -36, -35, -53, 19, 6, -37, -56, 14, 79, -29, 17, 0, -2, -69, 29],
            [-2, -6, 31, 20, 24, -8, -49, 36, 50, 2, 120, -22, -18, -11, -17, 17, 57, 40]
        ]
    
    def gao_one(self, l):
        self.conn.recvuntil('| Submit two different string such that ')
        s = self.conn.recvline().decode()[14]
        problem_id = int(s)
        m1, m2 = [0] * l, [0] * l
        print(f'{problem_id = }')
        for i, di in enumerate(self.ans[problem_id]):
            if (di < 0):
                m1[i], m2[i] = 0, -di
            else:
                m1[i], m2[i] = di, 0
        self.conn.sendline(bytes(m1).hex())
        self.conn.sendline(bytes(m2).hex())
    
    def gao(self):
        self.conn.sendline('S')
        for level in range(18):
            self.gao_one(35 - level)
        self.conn.interactive()

if __name__ == '__main__':
    g = Gao()
    g.gao()

得到 flag 为：

1	CCTF{fINd1n9_cOlL!s10n_f0r___FNV2___!}

Shevid

题目描述

题目基于 SIDH，其中椭圆曲线为 $E_0: y^2 = x^3 + 6x^2 + x$，SIDH 素数为 $p=2^a 3^b - 1$。

并且知道 $E_0[2^a]$ 中的生成元 $P_0, Q_0$、$E_0[3^b]$ 中的生成元 $R_0, S_0$、isogeny $\varphi$ 的 codomain $E/\mathbb{F}_{p^2}$、生成元 $P=\varphi(P_0), Q=\varphi(Q_0)$

试破解 Bob 的私钥。

我的解答

众所周知，去年 Castryck 和 Decru 弄出了个大新闻，把 SIDH 给破解了。

因为我对 SIDH 相关一窍不通，所以直接找到对应的仓库地址并进行一个 git clone：

https://github.com/GiacomoPope/Castryck-Decru-SageMath

开源真是好文明，赞美开源

在这期间其实先找了另一个 repo：

https://github.com/Breaking-SIDH/direct-attack

这个攻击好像是今年发表的，但是实际上并跑不起来，会报个错：

  File "/xxx/yyy/zzz/direct-attack/xonly.py", line 106, in <listcomp>
    return ntl.ZZ_pEX([ntl.ZZ_pE(c.list(), self.ctx) for c in poly])
  File "sage/structure/element.pyx", line 494, in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4831)
  File "sage/structure/element.pyx", line 507, in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4943)
  File "sage/cpython/getattr.pyx", line 361, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2702)
AttributeError: 'sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt' object has no attribute 'list'

不是很懂……

然后就是把题目的数据给接上就行了。因为他那个 attack 函数实际上会有一些全局变量的传入，譬如 $P_3, Q_3, a, b$ 等，所以最好不要去动他 repo 里面的一些命名：

Local imports
import public_values_aux
from public_values_aux import *

# Load Sage files
load('castryck_decru_shortcut.sage')

# Set the prime, finite fields and starting curve
# with known endomorphism
p = 4651852759096127491733667803074539573102288457512521355046899661762757394431

a = 142
b = 69

Fp2.<x> = GF(p^2, modulus=x^2+1)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2) # Speeds things up in Sage

# Generation of the endomorphism 2i
two_i = generate_distortion_map(E_start)

P = (3799366067639160994711391413511701264777392349807255916259320256251336249666*x + 633884628131689177031068067897867565283026098415356709331881575255526844055, 3967348484864888240941807454988077684669074109524399477973520952727771366997*x + 2712354532382043232096058211997452093712477916671679907467703464009558475387)
Q = (560486392227142181240528415381730657098132581407794833013161975335122628946*x + 3215971074127995409351672272900519761566156375365764079386358523254177565572, 2231746347912007096335360835242707156884468521076802738444724241125548841199*x + 1147378568798166954853288670809304301194478550602719730593160186622788033023)
R = (2656280316115888204975052029900945854050191685154131031859911335618240136443*x + 1127449111197960889758916770042950976852995868310602942974825430779982061546, 3477289737920472771668877366806058236254602770820629911886593813749930497839*x + 4646016633241840360901490323351236375375727836768954121794139000985805816564)
S = (2403139149412141532587482679318245468078604585804423116505024414375742701912*x + 2772488504607240668919423445309052101443116827322741849326656561794480962717, 3356599382898540527962106232860239304405841217130774924490318752448476310798*x + 2818004736373436361527915593539097434287090434842750370886675729711731978922)

P, Q, R, S = map(E_start, (P, Q, R, S))

_phi_dom = EllipticCurve(Fp2, [
    0,
    6,
    0,
    (2070374075904221348548347954672740119972290047985052548426161483408084160515*x+896749506444795652787374405713981306103783874504413776724865996633074195878),
    (2497300913991521538985990865799426081199023429830552981773916386651958830387*x+4243320791854592301388975795466391442631117041175807728844738724691845270777)
])
_phi_dom.set_order((p+1)**2, num_checks=0)
_phi_P = (76437828586489590038329193939006186966443918785230388533883401536928551274*x + 1854701339851606878866613257086348330205980107370562791121360193846610915298, 3614996124089236146025194675467338095830005859290616536023140003816221458491*x + 1308394538776387115295908857102539180825411698539070801598965381200026966383)
_phi_Q = (2350346337927935568113772636838467488287314266120334638991371449749383548230*x + 3389994457403704259291228848441313337916860864318549296438418403582347527289, 3514523396038039657181009561828298688334341559779027220238590888980836781356*x + 1132784636339236588815425424619354807485262558088269015122405460656452137103)

_phi_P, _phi_Q = map(_phi_dom, (_phi_P, _phi_Q))

P2, Q2, P3, Q3 = P, Q, R, S
EB, PB, QB = _phi_dom, _phi_P, _phi_Q

# ==== ==== ==== ==== ==== ==== ==== ==== ===
# ==== =  ATTACK  ==== ==== ==== ==== ====
# ==== ==== ==== ==== ==== ==== ==== ==== ===

def RunAttack(num_cores):
    return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)

if __name__ == '__main__' and '__file__' in globals():
    if '--parallel' in sys.argv:
        # Set number of cores for parallel computation
        num_cores = os.cpu_count()
        print(f"Performing the attack in parallel using {num_cores} cores")
    else:
        num_cores = 1
    recovered_key = RunAttack(num_cores)

就这样就可以弄出 Bob 的私钥。然后就是朴实无华的解密：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5

skey = 35588822058809282635150734794357

enc = '50d8ed352ccf3ce6d64b25e50ed67b832dcbcd94dcb7dc8293e813e0c83ace541abb61618d5f971ff5d24fab8a2e'
enc = bytes.fromhex(enc)


key = md5(long_to_bytes(skey)).digest()
iv = md5(str(skey).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
msg = cipher.decrypt(enc)
print(msg)

得到 flag 为：

1	CCTF{3FfiC!En7_k3Y_R3c0vErY_4tTacK_ON_SIDH!!!}

找到了个 MSR 出品的介绍 SIDH 怎么玩的文章：

https://eprint.iacr.org/2019/1321.pdf

有空去补一下