HITCON CTF 2022 Crypto Writeups

2022-11-29

字数统计: 2.6k字 | 阅读时长≈ 13分

Hitcon 2022 Crypto 方向题解，这次纯crypto方向六道题，剩一道chimera没有解出来。和去年一样，Hitcon又出了NTRU格密码相关的攻击，去年是选择密文攻击，这次是广播攻击。该题解不包含两道NTRU题的题解，之后有空会单独写一篇NTRU相关攻击的博客。以下是BabySSS，Secret，Superprime的题解。

BabySSS

源代码

I implemented a toy Shamir’s Secret Sharing for fun. Can you help me check is there any issues with this?

from random import SystemRandom
from Crypto.Cipher import AES
from hashlib import sha256
from secret import flag

rand = SystemRandom()


def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])


DEGREE = 128
SHARES_FOR_YOU = 8  # I am really stingy :)

poly = [rand.getrandbits(64) for _ in range(DEGREE + 1)]
shares = []
for _ in range(SHARES_FOR_YOU):
    x = rand.getrandbits(16)
    y = polyeval(poly, x)
    shares.append((x, y))
print(shares)

secret = polyeval(poly, 0x48763)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR)
print(cipher.encrypt(flag))
print(cipher.nonce)

分析

SSS密钥共享算法，用于构建密钥分享的多项式是 $f(x) = \sum\limits_0^{128} a_i *x^i$ ，其中 $a_i$ 都是64比特的随机数，个人持有的子密钥 $x_i$ 是 16 比特。我们有8个子密钥即 $(x_1, f(x_1)),...,(x_8,f(x_8))$ ，借此恢复整个多项式。下面介绍两种算法，一种基于格的算法；一个基于中国剩余定理的恢复算法。

格基规约-最短向量

相比较于 $x_i^{128}$ （2048比特）， $a_i$ 的长度64比特就很小，因此可以考虑基于多项式的等式构建下面的基本格：

$M = \begin{bmatrix} 1 & 1 &...& 1 & 1 & & \\ x_1 & x_2 & ... & x_8 & & 1 \\ ... & ... & ... & ... & & & ... \\ x_1^{128} & x_2^{128} & ... & x_8^{128} & & & &1\\ - y_1 & - y_2 & ... & - y_8 & & & & & 1 \\ \end{bmatrix} \tag{1}$

由于 $\vec V = (a_0,...,a_{128},1)*M = (0,...,0,a_0,a_1,...,a_{128},1)$ 是上述矩阵M行空间的上的短向量，因此可以应用LLL算法，大概率就能得到上面得到目标向量，但是仅仅靠上面的格解不出来目标解，因为目标解模长在各维度上分布不均匀，所以我们修改上面矩阵 (1) ，使得目标解各个维度的模长都约等于1即可。

$M' = \begin{bmatrix} 1 & 1 &...& 1 & 2^{-63} & & \\ x_1 & x_2 & ... & x_8 & & 2^{-63} \\ ... & ... & ... & ... & & & ... \\ x_1^{128} & x_2^{128} & ... & x_8^{128} & & & & 2^{-63}\\ - y_1 & - y_2 & ... & - y_8 & & & & & 1 \\ \end{bmatrix} \tag{1}$

此时目标向量为 $\vec V' = (a_0,...,a_{128},1)*M' = (0,...,0,\frac{a_0}{2^{63}},\frac{a_1}{2^{63}},...\frac{a_{128}}{2^{63}},1)$ ，各个维度都为1比特左右。对上述矩阵LLL之后，即可得到 $\vec V'$ ，从而恢复出参数 $a_i$ 。

CRT解法

注意到 $y_i \mod x_i = \sum\limits_0^{128} a_j *x_i^j = a_0 \mod x_i$ ，我们有8组 $(x_i,y_i)$ ，得到8组 $a_0 \mod x_i$ ，从而恢复出 $a_0$ 。更一般的，推导任意 $a_i$ , 在恢复出 $a_0,..,a_{i-1}$ 后， $s = y- \sum_0^{i-1} a_k*x^k = \sum_i^{128} a_k*x^k$ ，则 $\frac{s}{x^i}$ 也就和 $a_0$ 的情况一样，同理恢复出 $a_i$ 。

EXP

格方法：

from ast import literal_eval

lines = open("./output.txt","r").readlines()

shares = literal_eval(lines[0].strip())
enc = literal_eval(lines[1].strip())
nonce = literal_eval(lines[2].strip())

from random import SystemRandom
from Crypto.Cipher import AES
from hashlib import sha256
def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])

vector_list = []
for x,y in shares:
    vector_list.append(vector(ZZ, [x^i for i in range(129)] + [-y]))

A = matrix(ZZ,vector_list)
A = A.transpose()
B = matrix.identity(ZZ, 130)
B[-1,-1] = 2**63
B = B/2**63
M = block_matrix(QQ, [A,B], ncols = 2)

L = M.LLL()
L = L*2**63
L = L.change_ring(ZZ)
for i in range(8):
    for j in range(138):
        print(L[i,j].nbits(),end = " ")
    print()

poly = L[1][8:8+129]
secret = polyeval(poly, 0x48763)
for x,y in shares:
    assert y == polyeval(poly,x)
    
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce = nonce)
print(cipher.decrypt(enc))

CRT 解法

from ast import literal_eval
from hashlib import sha256
from Crypto.Cipher import AES
def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])

lines = open("./output.txt","r").readlines()
shares = literal_eval(lines[0].strip())
enc = literal_eval(lines[1].strip())
nonce = literal_eval(lines[2].strip())

a_list = []
for i in range(129):
    mods = []
    consts = []
    for x,y in shares:
        s = y - sum([a*(x^j) for j,a in enumerate(a_list)])
        assert s % x^i == 0
        r = s//(x^i)
        mods.append(x)
        consts.append(r)
    a_list.append(crt(consts,mods))

poly = a_list[:]
secret = polyeval(poly, 0x48763)
for x,y in shares:
    assert y == polyeval(poly,x)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce = nonce)
print(cipher.decrypt(enc))

Secret

源代码

import random, os
from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(1024)
q = getPrime(1024)
n = p * q

flag = open('flag','rb').read()
pad_length = 256 - len(flag)
m = bytes_to_long(os.urandom(pad_length) + flag)
assert(m < n)
es = [random.randint(1, 2**512) for _ in range(64)]
cs = [pow(m, p + e, n) for e in es]
print(es)
print(cs)

分析

已知64组 $(e_i,m^{p+e_i} \mod n)$ ，我们需要恢复m。这题有些类似之前n1ctf的一道题，详情参考我之前的博客ezdlp。难点在于恢复n，这题的不同点在于我们不知道基底m，因此这里我们需要找很小的 $k_i,\ i= 1,2,...,64$ 使得：

$\sum k_i = 0 \xrightarrow{s.t.} \sum k_i* p = 0 \\ \sum e_i*k_i = 0$

解空间，即上面两个方程的核空间，是一个线性空间。因此我们可以取一组核空间的基构成的矩阵，在这个矩阵上进行LLL算法即可得到符合条件的小系数 $k_i$ 。因为我们不能求逆，把正负号分两边进行计算，即可得到n的整数倍 $K*n$ , 利用多组这样的倍数求一个最大公倍数即可恢复n。

得到n之后，利用求逆，消去未知参数p的影响： $c' = m^{(p+e_i-p - e_j)} = m^{e_i-e_j} = m^{e'}$ ，在新的集合 $\{c_i', e_i'\}$ 里，根据指数计算扩展欧几里得算法得到一组： $x*e_i'+y*e_j' = 1$ ，即可恢复得到 $(c_i’)^x*(c_j')^y = m^{x*e_i'+y*e_j'} = m$ 。

EXP

# sage
from ast import literal_eval
lines = open("./output.txt","r").readlines()
es = literal_eval(lines[0].strip())
cs = literal_eval(lines[1].strip())
NUM = len(cs)
B = matrix(ZZ,NUM,2) 
for i,e in enumerate(es):
    B[i,0] = e
    B[i,1] = 1
    
M = B.transpose().right_kernel_matrix()
for l in M:
    assert list(l*B) == [0,0]
L = M.LLL()

    
def compute_kn(coff):
    res_right = 1
    res_left = 1
    for i ,cof in enumerate(coff):
        if cof > 0:
            res_right = res_right * cs[i]**cof
        else:
            res_left = res_left * cs[i]**(-cof)
    return res_left - res_right

n = compute_kn(L[0])
for l in L[1:]:
    assert list(l*B) == [0,0]
    n = gcd(compute_kn(l),n)
    n = factor(n,limit = 2**20)[-1][0]
    if n.nbits() <= 2048:
        break
print(n)

from Crypto.Util.number import *
mpe1_inv = inverse(cs[0],n)
_es = [e-es[0] for e in es[1:]]
_cs = [c*mpe1_inv%n for c in cs[1:]]

# find gcd(_ei,_ej) = 1
find = False
for i in range(len(_es)):
    for j in range(len(_es)):
        if gcd(_es[i],_es[j]) == 1:
            find = True
            break
    if find:
        break
print(i,j)

e1,e2 = _es[i] , _es[j]
c1,c2 = _cs[i] , _cs[j]
g, x1, x2 = xgcd(e1,e2)
m = pow(c1,x1,n)*pow(c2,x2,n) % n
print(long_to_bytes(int(m)))

Superprime

源代码

from Crypto.Util.number import getPrime, isPrime, bytes_to_long


def getSuperPrime(nbits):
    while True:
        p = getPrime(nbits)
        pp = bytes_to_long(str(p).encode())
        if isPrime(pp):
            return p, pp


p1, q1 = getSuperPrime(512)
p2, q2 = getSuperPrime(512)
p3, q3 = getSuperPrime(512)
p4, q4 = getSuperPrime(512)
p5, q5 = getSuperPrime(512)

n1 = p1 * q1
n2 = p2 * p3
n3 = q2 * q3
n4 = p4 * q5
n5 = p5 * q4

e = 65537
c = bytes_to_long(open("flag.txt", "rb").read().strip())
for n in sorted([n1, n2, n3, n4, n5]):
    c = pow(c, e, n)

print(f"{n1 = }")
print(f"{n2 = }")
print(f"{n3 = }")
print(f"{n4 = }")
print(f"{n5 = }")
print(f"{e = }")
print(f"{c = }")

分析

可以拆分为三个小问题，题目中SuperPrime得到的两个素数的形式如下：

$p = a_ta_{t-1}...a_1a_0 = \sum\limits_0^t a_i*10^i \tag{1}$ $q = \sum\limits_0^t (a_i+48)*256^i \tag{2}$

下面分布讨论题目中的三种情况，我们把bytes_to_long(str(p).encode())定义为： $f(p)$ ，显然 $f(p)$ 是单调递增函数。

情况一： $n_1 = p_1*q_1$ ，即 $n = p_1*f(p_1)$ ，显然右边是一个单调递增函数，因此可以通过二分搜索，快速分解n。
情况二： $n_2 = p_2*p_3 , n_3 = q_2*q_3 = f(p_2)*f(p_3)$ ，这种情况下我们注意到：由式（1）（2）给出的关系，我们可以通过 $n_2$ 模10的结果和 $n_3$ 模256的结果，去推导出 $p_2,q_2$ 的低位，以此类推，从低位到高位搜索，每次可以得到若干可能的结果，剪枝掉不符合条件的值，进行深度优先搜索即可。
情况三： $n_4 = p_4*q_5 , n_5 = p_5*q_4$ ，这里写一下官方题解里的思想，考虑到 $n_4 = p_4* f(\frac{n_5}{f(q_4)})$ ，在 $q_4$ 的长度保持不变的情况下，上述函数也是单调递增的，因此也可以使用二分搜索分解 $n_4,n_5$ 。比赛时候巨神写的从高位开始的搜索算法，类似二维的二分搜索。官方的脚本可以参考这里solve.py。

EXP

from Crypto.Util.number import *
n1 = 132240475872174910020944408159013384770525986234801028624784519134365862704105251340824787510945183963356820885920367304711310957365047441178683686926111455575911962257698539064559510444855775549001648292058855493337857073693460061212792795075263084221929517773754699732129582794061997056827998985829666251060653380798686353779510948629280009197715644814616657550158740378670095210797455828266323922570838468050733341304227070902756780052159113811360169205531739117518635829837403006788948761106892086004133969899267757339921
n2 = 95063555614573541810575593850289506856925979977609991181205616159125089261546784721154599484613262518469706157215924537125160406418217535531993036958388330505871763176297570429533467696205928686731756713059807727405313286020007347211892135226632724359291407913539632339885950358476265995466145680878334722001
n3 = 59077122528757446350604269162079270359932342538938986760275099248290981958441838384256597839386787448447136083450980256330743221155636885358548541847176342745397373638152767362253944731433134474562146358334422503033973244936835557423934491676324297243326613498319086748647812745223753746779568080090592100960499863677438403657325762852705171109382084916335379889394829715777901290096314487661584614712488781379507151355301063123233880909931925363322846957197537676660047824476129446066149857051131731840540157488590899311381370266592295206055792990886734933291304077440476730373491475852882163732120626849448728573574411786320772125534383707413572678316508826450778346723441956945169297689138799298561759843280317867927205551400065163199599457
n4 = 24589423756497058585126900932611669798817346035509889383925628660158156567930038333401661451846451875869437263666365776498658699865323180836374906288949824205543130261556051807217164348291174483234810669420041361857307271050079366739157441129916338485838528114129985080841445467007786565727910355311119650431197742495274527401569906785121880408809802492383216836691265423297722021017515667257863302820657924121913047547741420413553737917632809270380269758313556777803344394624408862183672919570479289614998783678080936272369083
n5 = 185885020243714550225131939334004568560534422416697599024696590344782893162219788079305752632863387855011040772104676488940707663157284194641170875157382507202789029285286466326803699701161968587945867047101502048926016515139728368809523009828247173096909917611001113266938209226483162533302629909322412013492978440863258135181226831155024690292336026753678424906151360739424148666951389956182136072508650529271179749569637083537783283360860102371562796635391549934474381821125255176073752645643893294533330184238070085333427
e = 65537
c = 44836759088389215801662306050375432910426695023654894661152471598197009644316944364461563733708795401026569460109604554622161444073404474265330567406370705019579756826106816505952084633979876247266812002057927154389274998399825703196810049647324831928277737068842860115202258059693760003397831075633707611377854322143735834890385706873765241863615950449707047454133596389612468366465634011925228326638487664313491916754929381088396403448356901628825906815317934440495749705736715790281606858736722493438754469493049523175471903946974639097168758949520143915621139415847104585816466890751841858540120267543411140490236193353524030168152197407408753865346510476692347085048554088639428645948051171829012753631844379643600528027854258899402371612
    
f = lambda x : bytes_to_long(str(x).encode())
def binary_search1(N,lb,ub):
    while lb!= ub:
        middle = (lb+ub)//2
        v = middle*f(middle)
        if v < N:
            lb = middle + 1
        elif v >= N:
            ub = middle - 1
    return lb

def prune_search2(N2,N3):
    def comnpute_table(p1,p2,cnt):
        table =  []
        for i in range(10):
            pp1 = p1 + i*10**cnt
            for j in range(10):
                pp2 = p2 + j*10**cnt
                if test(pp1,pp2,cnt+1):
                    table.append((pp1,pp2))
        return table
    
    fn = lambda x,cnt : bytes_to_long(str(x).zfill(cnt).encode())
    def test(p1,p2,cnt):
        q1,q2 = fn(p1,cnt),fn(p2,cnt)
        return N2%(10**cnt) == (p1*p2)%(10**cnt) and (q1*q2)%(256**cnt) == N3%(256**cnt)
    
    def search(p1,p2, cnt):
        if p1>1 and N2%p1 == 0:
            return (True,(p1,N2//p1))
        if p2>1 and N2%p2 == 0:
            return (True,(p2,N2//p2))
        for pp1,pp2 in comnpute_table(p1,p2,cnt):
            res = search(pp1,pp2,cnt+1)
            if res[0] == True:
                return res
        return (False,None)
    return search(0,0,0)[1]

def get_ndecbits(x, k=512):
    for i in range(k*2):
        if x<(2**k*0x30*(256**i)):
            return i+1

def wrap(x):
    return bytes_to_long(str(x).encode())

def get_bound(x, l, k=512):
    nbits = get_ndecbits(x, k)
    lbs = ''.join('{:d}'.format(i) for i in l)
    lbsa = lbs
    if lbs == '':
        lbsa = '1'
    lb = int(lbsa.ljust(nbits, '0'))
    ub = int(lbs.ljust(nbits, '9'))
    
    return (x//wrap(ub), x//wrap(lb))

def common_prefix(o):
    s1 = str(o[0])
    s2 = str(o[1])
    assert len(s1)==len(s2)
    for i in range(1, len(s1)):
        if s1[:i]!=s2[:i]:
            return [int(j) for j in s1[:i-1]]
    return [int(j) for j in s1]
    
def solve3(o):
    n4, n5 = o
    pref = [ [], [] ]
    pref1 = []
    while 1:
        # print('pref1',pref1)
        bnd = get_bound(n4, pref1)
        # print('bnd', bnd)
        pref2 = common_prefix(bnd)
        # print('pref2',pref2)
        bnd = get_bound(n5, pref2)
        # print('bnd', bnd)
        pref1 = common_prefix(bnd)
        # print('pref1',pref1)
        if bnd[0] == bnd[1]:
            break
    bnd2 = get_bound(n4, pref1)
    assert n5%bnd[0]==0
    assert n4%bnd2[0]==0
    return bnd2[0], bnd[0]

# n1 = p1 * q1
# n2 = p2 * p3
# n3 = q2 * q3
# n4 = p4 * q5
# n5 = p5 * q4

p1 = binary_search1(n1,0,2**512)
q1 = n1//p1
p2, p3 = prune_search2(n2,n3)
q2, q3 = f(p2),f(p3)
p4 , p5 = solve3((n4, n5))
q4 , q5 = f(p4), f(p5)

assert n1 == p1 * q1
assert n2 == p2 * p3
assert n3 == q2 * q3
assert n4 == p4 * q5
assert n5 == p5 * q4
T = [[n1, (p1 , q1)],[n2, (p2 , p3)],[n3, (q2 , q3)],[n4, (p4 , q5)],[n5, (p5 , q4)]]
for n,fcators in sorted(T, reverse = True , key = lambda x : x[0]):
    phi = (fcators[0]-1)* (fcators[1]-1)
    d = inverse(e,(phi))
    c = pow(c, d, n)
print(long_to_bytes(c))