Home ierae ctf writeup
Post
Cancel

ierae ctf writeup

Posted Sep 18, 2024
By
6 min read

IERAECTF

なんか参加してました。

fortress [hard 1 solve]

書くことないです。revで死んでました。なんかいい方法ないですかね…気合なのだろうか…

enjoyable-lattice [hard 7 solve]

chall

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

from sage.all import *
from Crypto.Random import random, get_random_bytes
from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

Q = getPrime(32)
N, k = 32, 2

PR.<x> = PolynomialRing(GF(Q))
R.<z> = PR.quotient_ring(x^N + 1)

def load_flag(filename='flag.txt'):
    with open(filename, 'rb') as file:
        return file.read().strip()

def centered_binomial_noise(size):
    return [sum(random.choice([-1, 1]) // 2 for _ in range(4)) for _ in range(size)]

def gen_small_poly_vector(size):
    while True:
        v = [R(centered_binomial_noise(N)) for _ in range(size)]
        if len(set(v)) == len(v):
            return vector(v)

def keygen():
    A = random_matrix(R, k, k)
    s = gen_small_poly_vector(k)
    e = gen_small_poly_vector(k)
    return s, (A, A * s + e)

def decompress(m):
    return R(m) * ((Q + 1) // 2)

def encrypt(pk, m):
    A, t = pk
    r = gen_small_poly_vector(k)
    e1 = gen_small_poly_vector(k)
    e2 = gen_small_poly_vector(1)
    u = A.T * r + e1
    v = t * r + e2[0] + decompress(m, Q)
    return u, v

def aes_encrypt(key, data):
    iv = get_random_bytes(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    padded_data = pad(data, AES.block_size)
    ciphertext = cipher.encrypt(padded_data)
    return iv + ciphertext

def main():
    aes_key = get_random_bytes(16)  
    s, pk = keygen()  
    A, t = pk
    FLAG = load_flag()  
    encrypted_flag = aes_encrypt(aes_key, FLAG)

    ciphertexts = []
    for i in range(0, len(aes_key), N // 8):
        aes_key_int = bytes_to_long(aes_key[i:i + N // 8])
        aes_key_bin = list(map(int, bin(aes_key_int)[2:].zfill(N)))
        encrypted_part = encrypt(pk, aes_key_bin)
        ciphertexts.append(encrypted_part)

    print(f"{Q = }")
    print(f"{A = }")
    print(f"{t = }")
    print(f"{ciphertexts = }")
    print(f"{encrypted_flag = }")

if __name__ == "__main__":
    main()

solve

まぁ、はい見た目通りPQCのkyberですね…ただNTT実装されていない所謂プレーンな実装です。

kyberはセキュリティレベルが3つあり、今回はKYBER-512から何か変更したものかぁと思いつつ、、、nが256から32に変更してあるのでただ単にsecurity levelが落ちているものでした。

さて、だから何だという話ですがもう一つ変更点があり$\mathcal{B}$はbytes列です。ただ、問題の実装ではここの部分が-4から0までしかとらない形でした。

image-20241003135627627

まぁ、lattice attackですよね…特にCirculant matrixみたいなやつですね。今回は$\phi=x^n+1 \mod q$なので、Circulant matrixに少し手を加えます。

まずは定義から$\boldsymbol{A}$は2×2の行列で各要素が多項式の$pk$です、$\boldsymbol{t}$が各要素が多項式のベクトルかつ暗号文です。

ある多項式$f$に対して$f*x^i\mod \phi$の係数に対する係数列ベクトルを\(\boldsymbol{coff}_i(f)\)としておき、これを$dig(\phi)$分だけ集めた行列\(\boldsymbol{ROT}(f) = [\boldsymbol{coff}_0(f),...,\boldsymbol{coff}_{dig(\phi)-1}(f)]^T\)とします。

これらを使ってkeygenの関数を行列で表すと以下になります。

\([e_{0},...,e_{2n-1},s_{0},...,s_{2n-1}] = [k_0,...,k_{2n-1},s_{0},...,s_{2n-1}]^T\begin{bmatrix} qI & & &\\ & qI & & \\ \mathbf{ROT}(\boldsymbol{A}_{00}) & \mathbf{ROT}(\boldsymbol{A}_{10}) & I& \\ \mathbf{ROT}(\boldsymbol{A}_{10}) & \mathbf{ROT}(\boldsymbol{A}_{11}) & & I\\ -\boldsymbol{coff}_0(\boldsymbol{t}_0) & -\boldsymbol{coff}_0(\boldsymbol{t}_1) \end{bmatrix}\)ですね。

なので、これにLLLすれば小さい係数のベクトルが見つかり、それが$sk$にあたるので復号の部分を実装すれば答えがおのずと出ますね。

GGです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

from Crypto.Random import random, get_random_bytes
from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *

Q = 4183169813
N, k = 32, 2
PR.<x> = PolynomialRing(GF(Q))
R.<z> = PR.quotient_ring(x^N + 1)
key = b""

---omit---
A = ---omit---
t = ---omit---
ciphertexts = ---omit---
encrypted_flag = ---omit---


def make_mat(_A):
    _A_list = []
    for i in range(32):
        _A_list.append([int(i) for i in _A.list()])
        _A = _A*z
    return matrix(_A_list)

for ciphertext in ciphertexts:
    A00 = make_mat(A[0][0])
    A01 = make_mat(A[0][1])
    A10 = make_mat(A[1][0])
    A11 = make_mat(A[1][1])

    N2 = N
    QI1 = Matrix.identity(ZZ, N2)*Q
    QI2 = Matrix.identity(ZZ, N2)*Q
    I1  = Matrix.identity(ZZ, N)
    I2  = Matrix.identity(ZZ, N)
    zero0 = zero_matrix(N2,N2)
    zero1 = zero_matrix(N2,N)
    zero2 = zero_matrix(N,N2)
    T0 = matrix([[int(i) for i in t[0].list()]])
    T1 = matrix([[int(i) for i in t[1].list()]])
    zero = zero_matrix(1,N)

    MAT = block_matrix(ZZ,[[QI1, zero0, zero1, zero1],
                        [zero0, QI2, zero1, zero1],
                        [A00,A10, I1, zero2],
                        [A01,A11, zero2, I2],
                        [-1*T0, -1*T1, zero, zero]], subdivide=False )

    MAT = MAT.LLL()
    s0 = MAT[1][64:64+32]
    s1 = MAT[1][64+32:]

    s0 = sum([s0[i]*z^i for i in range(32)])
    s1 = sum([s1[i]*z^i for i in range(32)])

    def dec(s, ct):
        u,v = ct
        u = vector(u)
        tmp = v -s*u
        return tmp

    pt = ""

    for x in dec(vector([s0,s1]), ciphertext):
        if 2000000890 < x < 2191584890:
            pt += "1"
        else:
            pt += "0"

    key += long_to_bytes(int(pt,2))

# key = b'\xdc\n\xe9\x0f\x9c\x1e\xb8}\xd9-\xb7\xaez\xec\xf7\xa8'
iv =encrypted_flag[:16]
ct =encrypted_flag[16:]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.decrypt(ct))
# b'IERAE{1n5p1r3d_3ncrypt10n_R1dd135_4nd_3xpl01t4t10n5}\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'
writeup
writeup
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents