WriteUp(WMCTF2020) - Crypto

Preface

idiot box ===> hellman拿了一血，祥哥拿了二血，顺利落幕（草草草草草草才知道hellman博士都毕业了dbq

Piece of Cake

[题解分析]

考察Wiener’s Attack & NTRU正常解密 & RSA common private key attack

在本题中，RSA cryptosystem的ph=(p-1)(q+1), ed=1(mod ph), 且d作为NTRU中的f

Encryption(NTRU part)

# case 2(make_cake)
cake = getPrime(256)
q = getPrime(1536)
size(f)\approx 1024
g = getPrime(1536 - size(f) - 1)
size(f^{-1})\approx 1536
h = g * f^{-1}
r = getPrime(512)
c = (r * h + cake) % q # size(c)\approx 1536

Attack

Step 1

$\because fh\equiv g(mod\ q)$

$\therefore fh=kq+g\Rightarrow\frac{h}{q}=\frac{k}{f}+\frac{g}{fq}\Rightarrow|\frac{h}{q}-\frac{k}{f}|=\frac{g}{fq}$

Now prove $\frac{1}{2f^2}>\frac{g}{fq}$ which is equivalent to $q>2fg$.

g = getPrime(q.bit_length() - f.bit_length() - 1), Satisfies!

Step 2

For candidate $(f,g)$

On Zmod(q), $c=rh+cake=rgf^{-1}+cake$

$\therefore cf=rg+f\cdot cake$. (bit_length: r = 512; g ≈ 511; f ≈ 1024; q = 1536)

In case 1(eat_cake), size(cake) = 768, while in case 2(make_cake), size(cake) = 256

Hence we have $rg+f\cdot cake$ equivalent to Zmod(q) and ZZ which means that cake can be recover in case 2.

If we get correct cake, we also have d in RSA cryptosystem.

However, in this challenge, we have $ed-1=k(p-1)(q+1)$, not $ed-1=k(p-1)(q-1)$

$ed-kN=1+k(p-q-1)$

Cuz s = p-q-1 is also $<3N^{1/2}$, LLL will be successful to obtain common e. (like SCTF2020 RSA)

size(e) = 477, $\delta=\frac{477}{1024}$

$\because\delta <\frac{r}{2r+2}-log_{N_{r}}(6)$, $\therefore$ when $r\geq 15$, e must can be easily cracked.

Step 3

After getting e, we use the same method to get d in case 1(eat_cake).

Then $ph=(p-1)(q+1),ed=1(mod\ ph)$, so $p\mid pow(2, ph, n),q\nmid pow(2,ph,n)$.

GCD to factor n, then get $ph’=ed’\equiv 1(mod\ (p-1)(q-1))$, finally getflag!

[exp]

本地测试exp

# In[102]:

from Crypto.Util.number import *

BITS = 512
e = getPrime(477)

def eat_cake():
    p, q = getPrime(BITS), getPrime(BITS)
    ph = (p - 1) * (q + 1)
    N = p * q
    d = inverse(e, ph)
    
    cake = getPrime(BITS >> 1 | BITS)
    q = getPrime(BITS << 1 | BITS)
    f = d
    g = getPrime(size(q) - size(f) - 1)
    f_inv_q = inverse(f, q)
    h = f_inv_q * g % q
    r = getPrime(BITS)
    c1 = (r * h + cake) % q
    c2 = pow(cake, 0x10001, N)
    print(cake)
    return q, h, c1, N, c2

# In[103]:

def make_cake():
    p, q = getPrime(BITS), getPrime(BITS)
    N = p * q
    ph = (p - 1) * (q + 1)
    d = inverse(e, ph)
    
    cake = getPrime(BITS >> 1)
    q = getPrime(BITS << 1 | BITS)
    f = d
    g = getPrime(size(q) - size(f) - 1)
    f_inv_q = inverse(f, q)
    h = f_inv_q * g % q
    r = getPrime(BITS)
    c1 = (r * h + cake) % q
    c2 = pow(cake, d, N)
    return q, h, c1, N, c2

# In[104]:

def rational_to_quotients(x, y):
    a = x // y
    quotients = [a]
    while a * y != x:
        x, y = y, x - a * y
        a = x // y
        quotients.append(a)
    return quotients

def convergents_from_quotients(quotients):
    convergents = [(quotients[0], 1)]
    for i in range(2, len(quotients) + 1):
        quotients_partion = quotients[0:i]
        denom = quotients_partion[-1]  # 分母
        num = 1
        for _ in range(-2, -len(quotients_partion), -1):
            num, denom = denom, quotients_partion[_] * denom + num
        num += denom * quotients_partion[0]
        convergents.append((num, denom))
    return convergents

# In[105]:

from tqdm import tqdm

# In[106]:

def crack_d():
    dAndN = []
    for i in tqdm(range(15)):
        q, h, c1, N, c2 = make_cake()
        quotients = rational_to_quotients(h, q)
        convergents = convergents_from_quotients(quotients)
        for (k, f) in convergents:
            try:
                g = (f * h) % q
                f_inv_g = inverse(f, g)
                cake = (c1 * f % q) * f_inv_g % g
                if pow(cake, f, N) == c2:
                    dAndN.append((f, N))
                    break
            except:
                pass
    return dAndN

# In[107]:

dAndN = crack_d()

# In[108]:

def crack_e(dAndN):
    ds = [_[0] for _ in dAndN]
    Ns = [_[1] for _ in dAndN]
    M = isqrt(max(Ns))
    A = Matrix(ZZ, len(dAndN) + 1, len(dAndN) + 1)
    A[0] = [M] + ds
    for i in range(len(dAndN)):
        A[i + 1, i + 1] = -Ns[i]
    AL = A.LLL()
    e = AL[0, 0] // M
    return abs(e)

# In[109]:

guessed_e = crack_e(dAndN)

# In[113]:

def factor_n(e):
    q, h, c1, N, c2 = eat_cake()
    quotients = rational_to_quotients(h, q)
    convergents = convergents_from_quotients(quotients)
    for (k, f) in convergents:
        p = GCD(int(pow(2, f * e - 1, N) - 1), N)
        if p > 1 and p < N:
            q = N // p
            d = inverse(0x10001, (p - 1) * (q - 1))
            cake = pow(c2, d, N)
            print(cake)
            break

# In[114]:

factor_n(guessed_e)

# Out[114]:

1027157078764690788142214800555547316945408825954295437289921287369230545318955110388392518217927993775664997807441799234649846512106765423582377942936106014367093824346097587115033287595424792363420560894490129540416253724597810397
1027157078764690788142214800555547316945408825954295437289921287369230545318955110388392518217927993775664997807441799234649846512106765423582377942936106014367093824346097587115033287595424792363420560894490129540416253724597810397

[Others]

非预期是因为给出size(e)，所以只需eat_cake即可通过cake%g和g恢复出cake- -

baby_sum & sum

[题解分析]

baby_sum中n=120，k=20 (即120维子集和问题，解向量重量为20)

• BKZ所约化的格基在行序shuffle后得到结果一般不同
• 作forced_zero降维，假设降维至105维，则要forced_zero的20个pos均落在解向量为0的pos上，概率为C(100,15)/C(120,15)
• BKZ的block_size取22或以上

$$\left[ \begin{matrix} Na_{1} & 1 & 0 & ... & 0 & N\\ Na_{2} & 0 & 1 & ... & 0 & N\\ ... & ... & ... & ... & ... & ...\\ Na_{n} & 0 & 0 & ... & 1 & N\\ Nc & 0 & 0 & ... & 0 & Nk\\ \end{matrix} \right],N>\sqrt{n}$$

btw，(2, 1)那个格子在本题也8太彳亍，且格基行序不shuffle，而是把Nc所在行放至首行成功率也莫名高…玄学（x

[exp]

import Crypto.Random.random as random
import multiprocessing as mp
from functools import partial
from json import load


def crack(elements, c, k, r, ID=None):
    assert(len(elements) > r)
    n = len(elements) - r # reduce dim -> n
    forced_zero = list(range(len(elements)))
    indexes = set(range(len(elements)))
    coef = ceil(sqrt(n))
    itr = 1
    while True:
        t0 = cputime()
        random.shuffle(forced_zero)
        zero = set(forced_zero[:r])
        # print(zero)
        reduced_indexes = [elements[i] for i in indexes - zero]
        A_list = [[coef * c] + [0] * n + [coef * k]]
        for i, ele in enumerate(reduced_indexes):
            A_list.append([coef * ele] + [1 * (j == i + 1) for j in range(1, n + 1)] + [coef])
        # random.shuffle(A_list) # row shuffle(extremely useful in most cases)
        A = Matrix(ZZ, A_list)
        AL = A.BKZ(block_size=22)
        print("[{}] {} runs, cost {:.3f} s.".format(ID, itr, cputime(t0)))
        for line in AL:
            if all(line[i] == 0 or line[i] == -1 for i in range(n + 2)) or all(line[i] == 0 or line[i] == 1 for i in range(n + 2)):
                if -1 in line:
                    line = -line
                print("[{}] {} success! {} {}".format(ID, itr, line[1:-1], zero))
                part_sol = line[1:-1]
                sol = ''
                j = 0
                for i in range(len(elements)):
                    if i in zero:
                        sol += '0'
                    else:
                        sol += str(part_sol[j])
                        j += 1
                print("You got it ===> {}".format(sol))
                return True
        itr += 1


def main():
    CPU_CORE_NUM = 8 # 8核
    c, elements = load(open("data", "r"))
    k = 20
    r = 15 # 15-dim lower
    crack_ID = partial(crack, elements, c, k, r) # 高阶偏函数
    with mp.Pool(CPU_CORE_NUM) as pool:
        status = pool.imap_unordered(crack_ID, range(1, 1 + CPU_CORE_NUM))
        for s in status:
            if s:
                pool.terminate()
                break


if __name__ == '__main__':
    main()

顺便复习了一次python的多进程- -

(注：脚本中行序shuffle被注释，因为Nc行放置首行一般出的都很快…不知道why)

[Others]

Sum没跑- -祥哥说测题的时候要300+ cpu hours，震撼我妈

Click Here to Download Soreat_u’s Official WriteUp

Game

[题解分析]

AES-CBC的选择明文攻击，即$mt$可控，返回$ct=E_{k}(mt||salt)$的oracle

该oracle下，如图所示，在任意分组中异或后前15bits可控，即可爆破获得未知LSB

发送b"\x00"*15至服务器，则明文第一个分组为b"\x00"*15+salt[0]，截取cipher=ct[:16], known_iv=iv, iv=ct[-16:]（Crypto.Cipher.AES的CBC模式iv是会随着加密行为更新的- -||，👴开debug后发现加密相同明文得到不同密文…tcl，所以必需在每次encrypt后更新iv=ct[-16:]）

再爆破LSB，即发送xor(b"\x00"*15+lsb, known_iv, iv)至服务器(爆破过程记得更新iv)，当ct[:16]=cipher时，lsb正确

得到salt[0]后，类似发送14bits, 13bits, …至服务器，得到salt[1:16]，但server判断len(mt)≠0，因此在爆破salt[15]时，prefix长度应为16

下图为爆破salt[16]的示意图

和爆破salt[0]时一样，发送b"\x00"*15，但此时cipher对应第二个分组，且known_iv为ct[:16]

利用已知的salt[1:16]即可爆破LSB，获得salt[16]，后续比特操作均类似

[exp]

import re, string
from hashlib import sha256
from sys import argv
# from tqdm import tqdm
from binascii import hexlify, unhexlify
from pwn import *
from pwnlib.util.iters import mbruteforce

# context.log_level = 'debug'
io = remote(argv[1], argv[2])

def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

def proof_of_work():
    io.recvuntil("sha256")
    msg = io.recvline().strip().decode()
    suffix = re.findall(r"XXXX\+([^\)]+)", msg)[0]
    cipher = re.findall(r"== ([^\n]+)", msg)[0]
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
                        cipher, string.ascii_letters + string.digits, length=4, method='fixed')
    io.sendlineafter("Give me XXXX: ", proof)

def crack_lsb(known, cipher, known_iv, iv):
    assert(len(known) == 15)
    for lsb in range(0x100):
        io.sendlineafter("> ", "1")
        mt = known + bytes([lsb])
        new_iv = xor(known_iv, iv)
        mt = hexlify(xor(mt, new_iv))
        io.sendlineafter("(in hex): ", mt)
        ct = unhexlify(io.recvline().strip())
        iv = ct[-16:]
        if ct[:16] == cipher:
            print(hex(lsb)[2:].rjust(2, "0"), end="")
            return bytes([lsb]), iv
    raise ValueError("[!] Not Found!")

def crack_salt():
    io.recvuntil("IV")
    msg = io.recvline().strip().decode()
    iv = unhexlify(re.findall(r"is: ([^\n]+)", msg)[0])
    known = b"\x00" * 15
    salt = b""
    for i in range(3):
        for j in range(15, 0, -1):
            prefix = hexlify(b"\x00" * j)
            io.sendlineafter("> ", "1")
            io.sendlineafter("(in hex): ", prefix)
            resp = unhexlify(io.recvline().strip())
            cipher = resp[i*16:(i+1)*16]
            if i > 0:
                known_iv = resp[(i-1)*16:i*16]
            else:
                known_iv = iv
            iv = resp[-16:]
            lsb, iv = crack_lsb(known, cipher, known_iv, iv)
            known = known[1:] + lsb
            salt += lsb
        prefix = hexlify(b"\x00" * 16)
        io.sendlineafter("> ", "1")
        io.sendlineafter("(in hex): ", prefix)
        resp = unhexlify(io.recvline().strip())
        cipher = resp[(i+1)*16:(i+2)*16]
        known_iv = resp[i*16:(i+1)*16]
        iv = resp[-16:]
        lsb, iv = crack_lsb(known, cipher, known_iv, iv)
        known = known[1:] + lsb
        salt += lsb
    io.sendlineafter("> ", "2")
    io.sendlineafter("(in hex): ", hexlify(salt))

def main():
    proof_of_work()
    crack_salt()
    print("\n" + io.recvline().strip().decode())
    io.close()

if __name__ == '__main__':
    main()

[Others]

48*(256+1)次encrypt，本地测秒出，挂载云服务器大概给出的alram(1200)也绰绰有余

i春秋公益赛赵总出了题挺类似的(NewsWebsite)，也是$ct=E_{k}(mt||salt)$的oracle，但是是ECB_MODE，buuoj.cn上有复现环境，感兴趣可以去van~

idiot box

[题解分析]

Click Here to View the WriteUp

[Others]

SU用的也是二轮迭代差分特征，但似乎更好些（甚至让我觉得普适性的1-R差分攻击是个憨憨…

图1是我所用四条差分路径其中的一条（对应的不是WMCTF上发布的版本，是我之前自己测题的第一版，难度会更大些，图懒得改了- -btw祥哥推荐的draw.io画图真的好用）

而图2是祥哥所用的差分路径（对应的是WMCTF上发布的版本，但是一条就能出最后一轮完整的子密钥）

差异就在于是2-R差分攻击，T_L’已知，但T_R’未知，且在这里T_R’据说可以激活第六轮全部八个S盒，所以能分段8次得到完整子密钥

而1-R攻击给出的差分路径使得l’和r’均固定（相较于2-R差分攻击具备了去噪能力），但相应的，这条路径的r’也只能激活第六轮的Sbox[1]和Sbox[2]，即只能攻击得到第六轮子密钥的前12bit，剩下比特再通过相同方法得到3条差分路径，直至攻击恢复出完整子密钥

有亿点点憨啊1-R攻击这么看起来…wtcl