CTF-Training-Record-1

Preface

CTF-Training-Record系列仅用于作部分CTF刷题记录，不定期更新

De1CTF2019 - Babylfsr

[题目考点]

BM algorithm

[题目文件]

[题解分析]

assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
assert(FLAG[7:11]=='1224')

LENGTH = 256

assert(KEY.bit_length()==LENGTH)
assert(MASK.bit_length()==LENGTH)

...

if __name__=="__main__":
    l = lfsr(KEY,MASK,LENGTH)
    r = ''
    for i in range(63):
        b = 0
        for j in range(8):
            b = (b<<1)+l.next()
        r += pad(bin(b)[2:])
    with open('output','w') as f:
        f.write(r)

BM算法的前提是要有$2\cdot LENGTH$个连续比特，而密文仅给出$2\cdot LENGTH-8$个连续比特

因此通过爆破末尾8个比特校验FLAG[7:11]=='1224'

本题类似https://0xdktb.top/2020/03/12/Summary-of-Crypto-in-CTF-stream/#lfsr—-known-plain-attack

原理可参照WIKI

[exp]

# In[88]:
cipher = open('output', 'r').read()

# In[89]:
cipher = [int(i) for i in cipher]

# In[90]:
F2 = GF(2)
X = []
S = []
LENGTH = 256
for i in range(len(cipher) - LENGTH):
    X.append(cipher[i : i + LENGTH])
    S.append(cipher[i + LENGTH])
X = Matrix(F2, X)
S = Matrix(F2, S)

# In[91]:
X, S
# Out[91]:
(248 x 256 dense matrix over Finite Field of size 2,
 1 x 248 dense matrix over Finite Field of size 2)

# In[92]:
import itertools

# In[93]:
suffix = list(itertools.product(range(2), repeat=8))

# In[94]:
MASK = []
for suf in suffix:
    X_n = X
    c = cipher + list(suf)
    for i in range(len(cipher) - LENGTH, len(cipher) - LENGTH + 8):
        v = vector(F2, c[i : i + LENGTH])
        X_n = X_n.stack(v)
    S_n = Matrix(F2, list(S[0]) + c[-8:]).T
    try:
        msk = X_n.solve_right(S_n)
        MASK.append(msk.T)
    except:
        pass

# In[95]:
def decrypt(cipher, feedback):
    assert(len(cipher) == LENGTH)
    cur = cipher
    key = ''
    for i in range(LENGTH):
        right = [cur[j] for j in feedback[1:]]
        left = right.count(1) % 2
        key = str(left) + key
        cur = [left] + cur[:-1]
    key = int(key, 2)
    return key

# In[96]:
KEY = []
for msk in MASK:
    feedback = []
    fb = list(msk[0])
    for i in range(LENGTH):
        if fb[i] == 1:
            feedback.append(i)
    feedback.append(LENGTH)
    delta = feedback[0] + 1
    feedback = [_ - delta for _ in feedback]
    KEY.append(decrypt(cipher[:LENGTH], feedback))

# In[97]:
import hashlib

# In[98]:
for k in KEY:
    flag = hashlib.sha256(hex(k)[2:].encode()).hexdigest()
    if flag[:4] == "1224":
        print("de1ctf{" + flag + "}")
        break
        
# de1ctf{1224473d5e349dbf2946353444d727d8fa91da3275ed3ac0dedeb7e6a9ad8619}

网鼎杯2020朱雀组 - guess_game

[题目考点]

LCG - unknown (a, b, m)
BM algorithm

[题目文件]

并不是朱雀组der- -赛中V👴分享了下，虽然都是已知考点，但过程还是有点繁琐

于是自己写dockerfile做了下复现

Click Here to Download

[题解分析]

configure选取Game Level时，其对应的level code是由LCG生成的，所有参数均未知，但回显给出连续六个数据，采用之前提到的trick即可，https://0xdktb.top/2020/03/27/Summary-of-Crypto-in-CTF-PRNG/#lcg—-unknown-a-b-m

LCG crack成功以后，拿到的level对应coin为10，因此在LFSR predict时可以用9个coin去换连续9个LFSR输出，即得到连续72bits.

知n=39，BM algorithm(末尾6bits采用爆破)即可…但仅余1个coin，所以从BM的多组解中随机选择发送，失败即重新remote.

[exp]

#!/usr/bin/env sage
import re, itertools
from pwn import *
from sys import argv
from functools import reduce
from Crypto.Util.number import *

#context.log_level = 'debug'

io = remote(argv[1], argv[2])


def crack_LCG():
    io.sendlineafter("Your choice:\n", "2")
    data = []
    for i in range(6):
        io.recvuntil(":")
        data.append(int(io.recvline().strip()))
    delta = [d1 - d0 for (d0, d1) in zip(data, data[1:])]
    m_mul = [d0 * d2 - d1 * d1 for (d0, d1, d2) in zip(delta, delta[1:], delta[2:])]
    m = reduce(GCD, m_mul)
    factors = factor(m)
    if len(factors) > 1:
        for (prime, degree) in factors:
            if size(prime) == 64:
                m = prime
                break
            m //= (prime**degree)
    s0, s1, s2 = data[0], data[1], data[2]
    A = Matrix([
        [s0  ,s1  ,1/m ,0   ,0   ],
        [1   ,1   ,0   ,1/m ,0   ],
        [-s1 ,-s2 ,0   ,0   ,1   ],
        [m   ,0   ,0   ,0   ,0   ],
        [0   ,m   ,0   ,0   ,0   ]
    ])
    A = A.LLL()
    a, b = None, None
    for l in A:
        if l[0] == 0 and l[1] == 0:
            if l[-1] == 1:
                a, b = l[2] * m, l[3] * m
            elif l[-1] == -1:
                a, b = -l[2] * m, -l[3] * m
            else:
                continue
    if not a or not b:
        print("[!] crack_LCG failed.")
        return False
    a %= m
    b %= m
    res = (a * data[-1] + b) % m
    io.sendlineafter("Input the level code:\n", str(res))
    return True


def get_LFSR():
    io.sendlineafter("Your choice:\n", "1")
    cipher = ""
    for i in range(9):
        io.sendlineafter("Input your answer:\n", "2333")
        ct = int(re.findall(r"\d+", io.recvline().decode("utf-8"))[0])
        cipher += bin(ct)[2:].rjust(8, "0")
    cipher = [int(i) for i in cipher]
    assert(len(cipher) == 72)
    return cipher


def crack_LFSR(cipher):
    F2 = GF(2)
    X, S = [], []
    LENGTH = 39
    for i in range(len(cipher) - LENGTH):
        X.append(cipher[i : i + LENGTH])
        S.append(cipher[i + LENGTH])
    X, S = Matrix(F2, X), Matrix(F2, S)
    suffix = list(itertools.product(range(2), repeat=6))
    MASK = []
    for suf in suffix:
        X_n = X
        c = cipher + list(suf)
        for i in range(len(cipher) - LENGTH, len(cipher) - LENGTH + 6):
            v = vector(F2, c[i : i + LENGTH])
            X_n = X_n.stack(v)
        S_n = Matrix(F2, list(S[0]) + c[-6:]).T
        try:
            msk = X_n.solve_right(S_n)
            MASK.append(msk.T)
        except:
            pass
    return MASK


def predict_LFSR(ct, msk):
    F2 = GF(2)
    nxt = 0
    for i in range(8):
        x = F2(0)
        for j in range(39):
            x += ct[j] * msk[j]
        ct = ct[1:] + [int(x)]
        nxt += (int(x) << (7 - i))
    io.sendlineafter("Input your answer:\n", str(nxt))
    if "Right!" in io.recvline().decode("utf-8"):
        return ct
    else:
        print("[!] predict_LFSR failed.")
        return None


def main():
    if crack_LCG():
        print("[+] crack_LCG success.")
    else:
        return False
    cipher = get_LFSR()
    MASK = crack_LFSR(cipher)
    if len(MASK):
        print("[+] {} masks have been found.".format(len(MASK)))
    else:
        print("[!] crack_LFSR failed.")
        return False
    ct = cipher[-39:]
    msk = list(MASK[randrange(0, len(MASK))][0])
    #msk = list(MASK[0][0])
    ct = predict_LFSR(ct, msk)
    if not ct:
        return False
    else:
        for i in range(498):
            ct = predict_LFSR(ct, msk)
    return True


if __name__ == "__main__":
    cnt = 0
    while main() == False:
        cnt += 1
        print(cnt)
        io.close()
        io = remote(argv[1], argv[2])
    io.interactive()

[More]

重连大概二三十次拿到flag…u1s1网鼎出题人没一个正常的

GKCTF2020 - Backdoor

[题目考点]

ROCA (RSALib - CVE)
PH
Coppersmith

[题解分析]

这题其实还是有一定难度的- -只是这个CVE披露出来以后github早有完整的轮子（paper题被秒emmm

在此借鉴paper及github上的脚本进行适当分析：

RSALib生成大素数的规则如下：

$N=(km+(65537^{a})\%M)(lm+(65537^{b})\%M)\equiv 65537^{a+b}(mod\ M).$

且M是前n个素数的乘积（n是有关size(N)的定值）：

由于M足够光滑，所以PH求解DLP得到c=a+b，再在$(\frac{c}{2},\frac{c+ord}{2})$上爆破a，进行Coppersmith求解k即可.

但对于现有的M，$ord_{M}(65537)$过大，而Coppersmith partial p的界还很宽裕，因此我们考虑取得M的因子M’，使得$ord_{M’}(65537)$在满足$size(M’)\geq size(N^{\frac{1}{4}})$的情况下尽可能的小.（此界的估计参考https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/#RSA-Partial-p）

Get M’ smaller than M (prepared for Coppersmith)

n = 15518961041625074876182404585394098781487141059285455927024321276783831122168745076359780343078011216480587575072479784829258678691739
M = 0x924cba6ae99dfa084537facc54948df0c23da044d8cabe0edd75bc6


def prime_power_factor(n):
    div = []
    for (p, r) in factor(n):
        if r == 1:
            div.append(p)
        else:
            div = div + [p**i for i in range(1, r + 1)]
    return div[::-1]

# divided by divisor(p) such that ord_p(65537)\nmid order
def sub_Gen_M_smaller(M, order):
    M_factor = [_[0] for _ in M.factor()]
    for p in M_factor:
        p_order = Zmod(p)(65537).multiplicative_order()
        if order % p_order != 0:
            M //= p
    return M, Zmod(M)(65537).multiplicative_order()

# Get M' smaller than M
def Gen_M_smaller(M, bound):
    candidates = [(M, Zmod(M)(65537).multiplicative_order())]
    while True:
        M_smaller, order = candidates[-1][0], candidates[-1][1]
        order_factor = prime_power_factor(order)
        candidates = []
        for p in order_factor:
            new_M, new_order = sub_Gen_M_smaller(M_smaller, order // p)
            param = (log(order, 2) - log(new_order, 2)) / (log(M_smaller, 2) - log(new_M, 2)) # 衡量阶下降速度的参数
            candidates.append((new_M, new_order, param))
        candidates = sorted(candidates, key=lambda x:x[2])
        if size(candidates[-1][0]) < bound:
            break
    return M_smaller, order

# size(n)//4 -> Coppersmith bound
M_smaller, order = Gen_M_smaller(M, size(n) // 4)
# (1134636716748630821225010071671110, 21840)

获得M’后，我们仍可以将p表示作$k’M’+(65537^{a’})\%M’$，且$k’<N^{\frac{1}{4}}$.

for a in range(c//2, (c + ord) // 2)上Coppersmith求解$f=k*M+pow(65537,a,M)$即可.

但Coppersmith构造的系数矩阵相关参数mm, tt及解的上界X在默认情况下，于本题效果极差- -

回到paper发现有对参数构造的方案：

这里的$(mm,tt)$在paper中并未给出具体证明，应该是实验性得到的数据- -

值得注意的是，paper中给出的(5, 6)是针对Gen_M_smaller(M, 512 // 4)给出的，至于能让阶更小的Gen_M_smaller(M, size(n) // 4)对应的参数可能又不相同…这里暂未实验

from tqdm import tqdm


def coppersmith_univariate(f, n, beta, mm, tt, XX):
    assert(f.is_monic() and 0 < beta <= 1)
    #epsilon = beta / 7
    dd = f.degree() # degree of polynomial
    #mm = ceil(beta**2 / (dd * epsilon)) # optimized param
    #tt = floor(dd * mm * (1 / beta - 1)) # optimized param
    #XX = ceil(n**(beta**2 / dd - epsilon)) # |x| < XX
    nn = mm * dd + tt
    # change ring of f and x to ZZ
    fZ = f.change_ring(ZZ)
    x = fZ.parent().gen()
    # instruct matrix
    A_list = []
    for i in range(mm):
        for j in range(dd):
            A_list.append((XX * x)**j * n**(mm - i) * fZ(XX * x)**i)
    A_list += [(XX * x)**i * fZ(XX * x)**mm for i in range(tt)]
    A = Matrix(ZZ, nn)
    for i in range(nn):
        for j in range(i + 1):
            A[i, j] = A_list[i][j]
    # LLL to solve SVP
    AL = A.LLL(early_red=True, use_siegel=True)
    f_smaller = 0
    for i in range(nn):
        f_smaller += (AL[0, i] * x**i) / (XX**i)
    candidates = f_smaller.roots()
    roots = []
    for root, _ in candidates:
        if root.is_integer():
            res = fZ(ZZ(root))
            if gcd(res, n) >= n**beta: # module's size satisfies
                roots.append(ZZ(root))
    return roots

M_smaller, order = Gen_M_smaller(M, 512 // 4)
c = discrete_log(Mod(n, M_smaller), Mod(65537, M_smaller))

PR.<k> = PolynomialRing(Zmod(n), implementation='NTL')
beta = 0.48
mm = 5
tt = 6
XX = int((2 * n**beta) / M_smaller)
#XX = ceil(n**(beta**2 - beta/7))
for a in tqdm(range(c // 2, (c + order) // 2)):
    f = k * M_smaller + Integer(pow(65537, a, M_smaller))
    roots = coppersmith_univariate(f.monic(), n, beta, mm, tt, XX)
    if len(roots):
        print(roots[0])
        print(gcd(roots[0] * M_smaller + Integer(pow(65537, a, M_smaller)), n))
        break
'''
  0%|          | 5/600600 [00:00<17:58:28,  9.28it/s]
1426982562847111986146541
3386619977051114637303328519173627165817832179845212640767197001941
'''

coppersmith分解n成功，后续略

[More]

coppersmith求解的参数$(mm,tt)$在不同情况也要不用调参，后续我以一个有更小order的M’(17304344567133368654502628603056098610)进行了参数估计（利用已知满足coppersmith条件的f进行测试）

基于复杂度考虑，选取$(mm,tt)=(10,11)$.

但是可以看到这里在阶减小的同时，mm,tt也增大，意味着LLL的矩阵扩大，求解时间并没有太大的变化- -

这题的数据应该是出题人generate的一组较易求解的p，q（因为我们发现在爆破a的时候，其最差时间约18h，但a能在很小的时候即符合）

coppersmith这东西…调参就很玄（刚刚提到的$(mm,tt)=(10,11)$求解成功的f，在直接small_roots时即求解失败- -其实可以用来出题埋一手坑(x)）

Unknown-name Crypto Challenge(2020/08/10)

[题目考点]

化简能力- -||

[题解分析]

Encryption

key = "KEYIS{xxxxxxxxxxxxxxxx}"

def lfsr(R,mask):
    output = (R << 1) & 0xffffffff
    i=(R&mask)&0xffffffff
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)

mask = int(os.urandom(4).encode('hex'), 16)
R = int(os.urandom(4).encode('hex'), 16)
iv = int(os.urandom(4).encode('hex'), 16)

enc = ''
for i in key:
    R,m = lfsr(R,mask)
    x = R ^ iv
    x ^= x >> 16
    x ^= x >> 8
    x = x & 255
    enc += chr(ord(i)^x)

由于iv是fixed的，所以可以简化为8bits的new_iv，在最后异或即可
R, _ = lfsr(R, mask)，因此也可简化为8bits的new_R, _ = new_lfsr(new_R)

注：这里的new_lfsr实际上已非lfsr，但仍保持如下性质

即经new_LFSR后，new_R = ((new_R << 1) & 0xff) | random_bit

因此可将上述化简为：

1
2
3

new_R = new_lfsr(new_R)
x = new_R ^ new_iv
enc += chr(ord(i) ^ x)

故对密钥流有以下递推关系：

prev = R ^ new_iv
curr = (((R << 1) & 0xff) | random_bit) ^ new_iv
(prev & 0x7f) = (R & 0x7f) ^ (new_iv & 0x7f)
(curr >> 1) = (R & 0x7f) ^ (new_iv >> 1)
(prev & 0x7f) ^ (curr >> 1) = (new_iv & 0x7f) ^ (new_iv >> 1) # new_iv -> constant

但curr的最低比特未知，flag内芯为小写md5，因此递归作判断即可

[exp]

from binascii import unhexlify

flag_charset = b"0123456789abcdef"
cipher = unhexlify(b"3bcd21d009a7e0ad9fa6718cd6310ed06a13bd589e0963")
prefix = b"S{"
suffix = b"}"
constant = ((prefix[0] ^ cipher[4]) & 0x7f) ^ ((prefix[1] ^ cipher[5]) >> 1)
pre = prefix[1] ^ cipher[5]
flag = "KEYIS{"
cipher = cipher[6:]

def getflag(flag, pre, constant, i):
    # print(i)
    cur = ((pre & 0x7f) ^ constant) << 1
    if i == 16 and chr((cur + 1) ^ cipher[i]) == '}' or chr(cur ^ cipher[i]) == '}':
        print(flag + '}')
    else:
        if (cur ^ cipher[i]) in flag_charset:
            getflag(flag + chr(cur ^ cipher[i]), cur, constant, i + 1)
        if ((cur + 1) ^ cipher[i]) in flag_charset:
            getflag(flag + chr((cur + 1) ^ cipher[i]), cur + 1, constant, i + 1)
    return
    
getflag(flag, pre, constant, 0)

# KEYIS{1fa32bc3ccee9872}

[More]

并不知道是什么赛事的题目- -好多师傅都在问，出题思路和X-MAS CTF基本相同，主要考察点即为化简

https://github.com/pberba/ctf-solutions/blob/8eb87af5bb2fbf7af683c7fd79d7979f032b7ae9/20181223_xmasctf/crypto-460-probably_really_nice_goodies/README.md

CISCN2018 - sm

[题目文件]

Click Here to Download

[题解分析]

Encryption

def gen512num():
    order = shuffle(list(range(1, 513)))
    ps = []
    for i in range(512):
        p = getPrime(512 - order[i] + 10)
        pre = bin(p)[2:][0:(512-order[i])] + "1"
        ps.append(int(pre + "0" * (512 - len(pre)), 2))
    return ps

可以看到gen512num返回的ps数组中，均为512bits的随机数，但存在下列关系：

for $p\in ps$，bin(p)[2:]的suffix均满足’1’+i*’0’ $(i\in [0,511])$，且i互不重复

choose为长度512的01向量，按如下规则leak出信息r

r = 0
for i in range(512):
    if bchoose[i]=='1':
        r = r ^ ps[i]

且题目给出ps，又有上述ps特性，即可从r末位比特向前恢复出choose

[exp]

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

r = 6753785483255906709117615805253027649453460653974415214642466102672301763943358839905575042938258141827000621474498066533397472809407687579125519939754658
ps = []
with open("ps", "r") as f:
    for line in f:
        ps.append(int(line[:-1]))
ps_dict = dict() # ps_dict[i]'s suffix satisfies '1' + i * '0'
for p in ps:
    for i in range(512):
        if ((2**i) & p) != 0:
            ps_dict[i] = p
            break

choose = [0] * 512
for i in range(512):
    if ((2**i) & r) != 0:
        r ^= ps_dict[i]
        choose[ps.index(ps_dict[i])] = 1
choose = int(''.join(str(_) for _ in choose), 2)

key = long_to_bytes(int(md5(long_to_bytes(choose)).hexdigest(), 16))
aes_obj = AES.new(key, AES.MODE_ECB)
cipher = b64decode(b"5eFo3ANg2fu9LRrFktWCJmVvx6RgBFzd0R8GXQ8JD78=")
flag = aes_obj.decrypt(cipher)
print(flag)

# b'flag{shemir_alotof_in_wctf_fun!}'

[More]

临近2020国赛了 :(

赛前找了些往年的cry题看了看- -难度上几乎比不上其他国际赛，但是有些风格奇奇怪怪

Training系列的博文就以一篇5题为规范吧，希望国赛人没事

END