摸鱼Writeup-1

本系列博客大概写一些较大比赛解数量较少的writeup,主要提供思路,具体流程可能不会过于细节

ByteCTF 2020 crypto2

crypto1和crypto3都没啥好说的,这里就放下crypto2的writeup~

分析可以构造

$$ B=(H(m)+1)G \Rightarrow encK = H(kcG) = H(A-H(m)G) $$

故做签名的sk为$flag \otimes Cprime$,使$Cprime = cipher = flag \otimes private_key$

则对s,e 有$s \equiv r - e private_key \mod (n)$,即有$rG =sG + epk$,又$rG.x = e$,故可做verify判断,这里考虑可以诸位爆破,从低位对$Cprime$ 诸位取反,则最终得到的sk为private_key某一位取反后的值,即$sk = private_key \pm 2^i$,通过verify即可判断为加还是减,即可判断private_key那一位为0/1,256次后得到private_key,再与cipher异或即得到flag,exp如下:

from winpwn import *
from Crypto_tools import *
from gmssl import sm3, func
from binascii import a2b_hex, b2a_hex

sm2p256v1_ecc_table = {
    'n': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',
    'p': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',
    'g': '32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7' + 'bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',
    'a': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',
    'b': '28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',
}

class APAKE(object):
    def __init__(self, hashed_pwd, pubkey):
        self.ecc_table = sm2p256v1_ecc_table
        self.para_len = len(self.ecc_table['n'])
        self.ecc_a3 = (int(self.ecc_table['a'], base=16) + 3) % int(self.ecc_table['p'], base=16)
        self.hashed_pwd = hashed_pwd
        self.K = None
        self.public_key = pubkey

    def sm3_hash_str(self, msg):
        return sm3.sm3_hash(func.bytes_to_list(msg.encode()))

    def send_client(self, kc_str):
        kc = int(kc_str, 16)
        hpi = int(self.hashed_pwd, 16)
        a = (kc + hpi) % int(self.ecc_table['n'], base=16)
        A = self._kg(a, self.ecc_table['g'])
        return A

    def prove_client(self, password, kc_str, A, B, c_prime):
        kc = int(kc_str, 16)
        hpi = int(self.hashed_pwd, 16)
        n_sub_hpi = (int(self.ecc_table['n'], base=16) - hpi) % int(self.ecc_table['n'], base=16)
        n_sub_hpi_G = self._kg(n_sub_hpi, self.ecc_table['g'])
        print('N_H(M) ->', n_sub_hpi_G)
        B_sub_hpi_G = self._add_point(B, n_sub_hpi_G)
        B_sub_hpi_G = self._convert_jacb_to_nor(B_sub_hpi_G)
        print('B_H(M) ->', B_sub_hpi_G)
        self.K = self._kg(kc, B_sub_hpi_G)
        enc_K = self.sm3_hash_str(self.K)
        print('K ->', enc_K)
        sk = '%064x' % (int(c_prime, 16) ^ int(password, 16) ^ int(enc_K, 16))
        transcript = A + B + c_prime
        signature = self._sign(transcript, sk)
        return signature

    def _sign(self, data, sk):
        k_str = func.random_hex(len(self.ecc_table['n']))
        k = int(k_str, 16) % int(self.ecc_table['n'], base=16)
        R = self._kg(k, self.ecc_table['g'])
        x1 = R[0:self.para_len]
        e_str = self.sm3_hash_str(x1 + data)
        e = int(e_str, 16)
        d = int(sk, 16)
        s = (k - d * e) % int(self.ecc_table['n'], base=16)
        return '%064x%064x' % (s, e)

    def verify(self, data, pk, signature, adjust):
        s = int(signature[0:self.para_len], 16)
        e = int(signature[self.para_len:2 * self.para_len], 16)
        sG = self._kg((s-adjust*e) % int(self.ecc_table['n'], base=16), self.ecc_table['g'])
        eP = self._kg(e, pk)
        R = self._add_point(sG, eP)
        R = self._convert_jacb_to_nor(R)
        x1 = R[0:self.para_len]
        e_str = self.sm3_hash_str(x1 + data)
        return e == int(e_str, 16)

    def _kg(self, k, Point):
        if (k % int(self.ecc_table['n'], base=16)) == 0:
            return '0' * 128
        Point = '%s%s' % (Point, '1')
        mask_str = '8'
        for i in range(self.para_len - 1):
            mask_str += '0'
        mask = int(mask_str, 16)
        Temp = Point
        flag = False
        for n in range(self.para_len * 4):
            if flag:
                Temp = self._double_point(Temp)
            if (k & mask) != 0:
                if flag:
                    Temp = self._add_point(Temp, Point)
                else:
                    flag = True
                    Temp = Point
            k = k << 1
        return self._convert_jacb_to_nor(Temp)

    def _double_point(self, Point):
        l = len(Point)
        len_2 = 2 * self.para_len
        if l < self.para_len * 2:
            return None
        else:
            x1 = int(Point[0:self.para_len], 16)
            y1 = int(Point[self.para_len:len_2], 16)
            if l == len_2:
                z1 = 1
            else:
                z1 = int(Point[len_2:], 16)

            T6 = (z1 * z1) % int(self.ecc_table['p'], base=16)
            T2 = (y1 * y1) % int(self.ecc_table['p'], base=16)
            T3 = (x1 + T6) % int(self.ecc_table['p'], base=16)
            T4 = (x1 - T6) % int(self.ecc_table['p'], base=16)
            T1 = (T3 * T4) % int(self.ecc_table['p'], base=16)
            T3 = (y1 * z1) % int(self.ecc_table['p'], base=16)
            T4 = (T2 * 8) % int(self.ecc_table['p'], base=16)
            T5 = (x1 * T4) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * 3) % int(self.ecc_table['p'], base=16)
            T6 = (T6 * T6) % int(self.ecc_table['p'], base=16)
            T6 = (self.ecc_a3 * T6) % int(self.ecc_table['p'], base=16)
            T1 = (T1 + T6) % int(self.ecc_table['p'], base=16)
            z3 = (T3 + T3) % int(self.ecc_table['p'], base=16)
            T3 = (T1 * T1) % int(self.ecc_table['p'], base=16)
            T2 = (T2 * T4) % int(self.ecc_table['p'], base=16)
            x3 = (T3 - T5) % int(self.ecc_table['p'], base=16)

            if (T5 % 2) == 1:
                T4 = (T5 + ((T5 + int(self.ecc_table['p'], base=16)) >> 1) - T3) % int(self.ecc_table['p'], base=16)
            else:
                T4 = (T5 + (T5 >> 1) - T3) % int(self.ecc_table['p'], base=16)

            T1 = (T1 * T4) % int(self.ecc_table['p'], base=16)
            y3 = (T1 - T2) % int(self.ecc_table['p'], base=16)

            form = '%%0%dx' % self.para_len
            form = form * 3
            return form % (x3, y3, z3)

    def _add_point(self, P1, P2):
        if P1 == '0' * 128:
            return '%s%s' % (P2, '1')
        if P2 == '0' * 128:
            return '%s%s' % (P1, '1')
        len_2 = 2 * self.para_len
        l1 = len(P1)
        l2 = len(P2)
        if (l1 < len_2) or (l2 < len_2):
            return None
        else:
            X1 = int(P1[0:self.para_len], 16)
            Y1 = int(P1[self.para_len:len_2], 16)
            if l1 == len_2:
                Z1 = 1
            else:
                Z1 = int(P1[len_2:], 16)
            x2 = int(P2[0:self.para_len], 16)
            y2 = int(P2[self.para_len:len_2], 16)

            T1 = (Z1 * Z1) % int(self.ecc_table['p'], base=16)
            T2 = (y2 * Z1) % int(self.ecc_table['p'], base=16)
            T3 = (x2 * T1) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * T2) % int(self.ecc_table['p'], base=16)
            T2 = (T3 - X1) % int(self.ecc_table['p'], base=16)
            T3 = (T3 + X1) % int(self.ecc_table['p'], base=16)
            T4 = (T2 * T2) % int(self.ecc_table['p'], base=16)
            T1 = (T1 - Y1) % int(self.ecc_table['p'], base=16)
            Z3 = (Z1 * T2) % int(self.ecc_table['p'], base=16)
            T2 = (T2 * T4) % int(self.ecc_table['p'], base=16)
            T3 = (T3 * T4) % int(self.ecc_table['p'], base=16)
            T5 = (T1 * T1) % int(self.ecc_table['p'], base=16)
            T4 = (X1 * T4) % int(self.ecc_table['p'], base=16)
            X3 = (T5 - T3) % int(self.ecc_table['p'], base=16)
            T2 = (Y1 * T2) % int(self.ecc_table['p'], base=16)
            T3 = (T4 - X3) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * T3) % int(self.ecc_table['p'], base=16)
            Y3 = (T1 - T2) % int(self.ecc_table['p'], base=16)

            form = '%%0%dx' % self.para_len
            form = form * 3
            return form % (X3, Y3, Z3)

    def _convert_jacb_to_nor(self, Point):
        len_2 = 2 * self.para_len
        x = int(Point[0:self.para_len], 16)
        y = int(Point[self.para_len:len_2], 16)
        z = int(Point[len_2:], 16)
        z_inv = pow(z, int(self.ecc_table['p'], base=16) - 2, int(self.ecc_table['p'], base=16))
        z_invSquar = (z_inv * z_inv) % int(self.ecc_table['p'], base=16)
        z_invQube = (z_invSquar * z_inv) % int(self.ecc_table['p'], base=16)
        x_new = (x * z_invSquar) % int(self.ecc_table['p'], base=16)
        y_new = (y * z_invQube) % int(self.ecc_table['p'], base=16)
        z_new = (z * z_inv) % int(self.ecc_table['p'], base=16)
        if z_new == 1:
            form = '%%0%dx' % self.para_len
            form = form * 2
            return form % (x_new, y_new)
        else:
            return None

    def assit(self, A):
        hpi = int(self.hashed_pwd, 16)
        n_sub_hpi = (-1 * hpi) % int(self.ecc_table['n'], base=16)
        rG = self._convert_jacb_to_nor(self._add_point(A, self._kg(n_sub_hpi, self.ecc_table['g'])))
        print('fake rG ->', rG)
        c_prime = self.sm3_hash_str(rG)
        return c_prime

Hash_m = 0x53b9edeb45a1175bad0ba15381a8676dff3611ad90629bf8fe0bae2f48d4a31d
n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
pk = '1f719bef8a35ec64ac88c0d4e5909201326fb3a84e39f45acc8dd34a8ae83ea595a8e7c877cd817204a1760b7dff10a34d50c3de4e48122aaaaed45a76752cd4'
cipher = 0x1cd3018bd12e647f91a19f02ce460685bd5c13eb2d7253da549baf62aa943da2
cipher_bin = bin(cipher)[2:].rjust(256, '0')
apake = APAKE(hashed_pwd=hex(Hash_m)[2:], pubkey=pk)

flag = ''

for i in range(256):
    p = remote('182.92.153.117', 30102)
    p.recvuntil('A = ')
    A = hex(int(p.recvuntil('\n'), 16))[2:].rjust(128, '0')

    p.recvuntil('PublicKey = ')
    tmp_pk = hex(int(p.recvuntil('\n'), 16))[2:].rjust(128, '0')

    p.recvuntil('Cipher = ')
    tmp_cipher = int(p.recvuntil('\n'), 16)

    p.recvuntil('B = ?')
    B = 'ed5794bb9114317bb0a502b82d3705216a325a2e15810bff91b8df5ad59d0e333e908d589d5ebb0ee2727768e81147d81f640d9d16a149282bd3fd20c5dbc895'
    p.send(B + '\n')
    p.recvuntil('c_prime = ?')
    balance = apake.assit(A)
    check = int(balance, 16) ^ cipher ^ int(('0' * (255 - i) + '1').ljust(256, '0'), 2)
    c_prime = hex(check)[2:]
    p.send(c_prime + '\n')

    p.recvuntil('Signature = ')
    tmp_signature = hex(int(p.recvuntil('\n'), 16))[2:].rjust(128, '0')
    data = A + B + c_prime

    if apake.verify(data, pk, tmp_signature, 2**i):
        flag = flag + '1'
    else:
        flag = flag + '0'
    p.close()

print(long_to_bytes(int(flag[::-1], 2) ^ cipher))

XNUCA 2020 crypto3

crypto1利用Blomer May的连分数求出x和y再利用Copper Smith恢复p,再恢复Twisted Edward即可,crypto2因为是分组我就没看,这里只给出crypto3的writeup~

这一题算是我第一次遇见格套娃,最难的一层应该就是恢复A了,比赛的时候7点多恢复出来了A,但忘记A的列顺序不影响B,故应该对A的所有列做个全排列再恢复LWE,恰逢S10决赛,于是乎并没有拿到三血orz,晚上十二点多经学长提醒才意识到2333

本题审题后发现有三层嵌套:

  1. 第一层是类背包问题,已知向量R,可知有

    $$ R_{64} = \sum_{i=0}^{63} T_i S_{y_i}, R_i = T_i $$

    可以发现和背包问题非常相似,但是系数$S_{yi}$ 并非为$0/1$, 而是落在$[0,1000)$ 上,故考虑对解决背包问题的格子做修改,可知一般解决背包问题使用如下格子:

    最后一行的向量1是用来均衡系数的,使得最后的解向量为$2x_i - 1 = -1/1$

    这里考虑到系数为$[0, 1000)$,故最后一行将1修改为1000,则有$2x_i - 1000 \in [-1000, 1000)$,则可成功规约出解向量,此部分代码如下:

    T = Matrix([i for i in R[:64]]).transpose()
    
    def decrypt(enc, publickey):
       n = len(publickey)
    
       d = 2 * identity_matrix(ZZ, n, n)
       col = publickey + [enc]
       col = matrix(col).transpose()
    
       last = matrix(ZZ, [[1000] * n])
       tmp = block_matrix(ZZ, [[d], [last]])
       grid = block_matrix(ZZ, [[tmp, col]])
    
       M = grid.LLL()
    
       return M[0][:-1]
    
    # got Sy with R
    Sy = decrypt(R[64], R[:64])
    Sy = [(x+1000)//2 for x in Sy]
    print(Sy)
  2. 第二层,也是最难的一层,即是通过矩阵B恢复矩阵A。

    这看起来是件很离谱的事情,只通过矩阵积恢复出来相乘的两个矩阵,但利用这题的bound确实可以做到这点orz。

    已知有$A r = B$, 其中A为$320\times5$的矩阵,r为$5\times 7$的随机矩阵,B即为$320 \times 7$的矩阵,特殊的地方在于,A的元素均在$[10, 1000)$上,而r的元素基本在1000位以上,故想到,我们可以对B为基底的格进行规约,从而可能得到A中某一列(因为考虑到广义逆,大概率有一个线性变换$r'$,使得$A = Br'$),但由于可能有多解,所以需要使用bound$[10, 1000)$约束一下。

    这里如果直接对B中的6列/7列进行全排列构造格子规约,则可以规约出两组320维的满足条件的A的列向量,但还有三列并不知道,这一点也是比赛中困扰我最久的问题,后来想到其实我们可以通过降低维度去扩大解空间范围,然后再取top5大概率即可找出A中所有的列向量。

    具体操作即是选取6/7个B的列向量部分,做全排列,我一开始取的是前140-220行遍历,这样可以找到7-8个满足条件的部分列向量,之前规约出的两个完整列向量也在其中,后来提高了维数为200-300行便只有五个了,这样成功找到了A的前200行,此部分代码如下:

    for limit in tqdm(range(200, 300)):
       base = []
       for i in range(7):
           base.append(B[i*320:(i+1)*320][:limit])
       for rows in range(6, 8):
           tmp = list(itertools.combinations(base, rows))
           for l in tmp:
               M = Matrix(ZZ, l)
               M = M.LLL()
               for i in M:
                   v = [abs(x) for x in list(i)]
                   if min(v) >= 10 and max(v) <= 1000 and v[0] not in had:
                       print(v)
                       print(limit)
                       had.append(v[0])
    # had = [706, 808, 626, 428, 717]

    找到了A的前200行后,可知有$A_{part} r = B_{part}$,故我们对得到五个列向量全排列,然后结合B矩阵前200行,即可解出r矩阵,再利用r矩阵,即可成功恢复A矩阵,此部分代码如下:

    B_matrix = Matrix(ZZ, _B).transpose()
    tmp = list(itertools.permutations(possible_A, int(cols)))
    A_num = 0
    for l in tqdm(tmp):
       A = Matrix(ZZ, l).transpose()
       try:
           R = A.solve_right(B_matrix)
           _B = []
           for i in range(7):
               _B.append(B[i * 320:(i + 1) * 320])
           B_matrix = Matrix(ZZ, _B).transpose()
           A = R.solve_left(B_matrix)
    
           for j in R.list():
               assert 1000 < int(j).bit_length() <= 1024
           break
       except:
           continue

    需要注意的是,由于B中元素是A中行元素线性和,故而其实A的列顺序不影响B的列顺序,故需要对A的5个列做个全排列才能找到正确的A。

  3. 最后一层,比较简单,即是恢复LWE,这里我直接用了之前N1CTF那个LWE的代码,加上A的列全排列即可:

    assert A.nrows() == 320
    assert len(A.columns()) == 5
    
    all_cols_comb = list(itertools.permutations(A.columns(), int(5)))
    total_sk = []
    for cols_comb in tqdm(all_cols_comb):
       tmp_A = Matrix(ZZ, cols_comb).transpose()
       tmp = [int(x).__xor__(int(y)) for x, y in zip(tmp_A.list(), xor_M)]
       LWE_a = []
       for i in range(64):
           LWE_a.append(tmp[i * 25:(i + 1) * 25])
       LWE_c = Sy
    
       module = 1000
       row = 64
       column = 25
       M = matrix(ZZ, row + column, row)
    
       for i in range(row):
           for j in range(column):
               M[row + j, i] = LWE_a[i][j]
           M[i, i] = module
    
       lattice = IntegerLattice(M, lll_reduce=True)
       target = vector(ZZ, LWE_c[:row])
       res = CVP(lattice.reduced_basis, target)
       R = IntegerModRing(module)
       M = Matrix(R, LWE_a[:row])
    
       total_sk.append(M.solve_right(res))
    
    print('total_sk =', total_sk)

最后的最后,遍历得到的所有可能私钥,解AES即可,代码如下:

iv_cipher = 0xc338be5406289b99332176593ae94b5e254df0e6b31b3155f370845e99d55f3a5b8b9e5576a126512b93eacacb6b7865f925120c3a221d0a2fcff362d841ad6be183a796f0c0a8111704737b6fc412f4
iv_cipher = long_to_bytes(iv_cipher)
for LWE_s in total_sk:
    key = hashlib.sha256(''.join(list(map(str, LWE_s))).encode()).digest()
    iv = iv_cipher[:16]
    cipher = iv_cipher[16:]
    aes = AES.new(key, AES.MODE_CBC, iv)
    flag = aes.decrypt(cipher)
    if b"X-NUCA{" in flag:
        print(flag)

最终得到flag:

HXB2020 crypto4

除了crypto4都比较简单,就crypto1还有点意思

这题其实即是改版的Wiener Attack,通过这篇paper 知道当存在$|ap - bq|$ 较小时,我们可以得到$p+q$ 的一个估计,$q<p<2q $ 时,这个估计为$\sqrt{\frac{(a+b)^2 N}{ab}}$ ,

于是有exp:

from Crypto.Util.number import *
from gmpy2 import *

def rational_to_quotients(x, y):  # calculate the series of continued fraction
    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):  # calculate the convergent series of continued fraction
    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

def WienerAttack_change(e, n, N, c):
    quotients = rational_to_quotients(e, n)
    convergents = convergents_from_quotients(quotients)
    for (k, d) in convergents:
        m = pow(c, d, N)
        flag = long_to_bytes(m)
        if b'DASCTF' in flag:
            print(flag)

n = 
e = 
c = 

a = 2
b = 11
WienerAttack_change(e, n - int(isqrt(((a+b)**2) * n // (a*b))) + 1, n, c)
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇