HarekazeCTF 2019 Write-up

はじめに

2019/05/18 ~ 2019/05/19に開催されたHarekazeCTFにチームで参加しました．
今回は自分が解いた問題についてのWrirte-upです．

成績

510pts獲得して68位(523チーム中)でした．

ONCE UPON A TIME [Crypto, 71solves, 100pts]

Now!! Let the games begin!!
- problem.py
- result.txt

prblem.py

#!/usr/bin/python3

import random
import binascii
import re
from keys import flag

flag = re.findall(r'HarekazeCTF{(.+)}', flag)[0]
flag = flag.encode()
#print(flag)

def pad25(s):
    if len(s) % 25 == 0:
        return b''
    return b'\x25'*(25 - len(s) % 25)

def kinoko(text):
    text = text + pad25(text)
    mat = []
    for i in range(0, len(text), 25):
        mat.append([
            [text[i], text[i+1], text[i+2], text[i+3], text[i+4]],
            [text[i+5], text[i+6], text[i+7], text[i+8], text[i+9]],
            [text[i+10], text[i+11], text[i+12], text[i+13], text[i+14]],
            [text[i+15], text[i+16], text[i+17], text[i+18], text[i+19]],
            [text[i+20], text[i+21], text[i+22], text[i+23], text[i+24]],
            ])
    return mat

def takenoko(X, Y):
    W = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
    for i in range(5):
        for j in range(5):
            for k in range(5):
                W[i][j] = (W[i][j] + X[i][k] * Y[k][j]) % 251
    return W

def encrypt(m1, m2):
    c = b""
    for mat in m1:
        g = random.randint(0,1)
        if g == 0:
            mk = takenoko(m2, mat)
        else:
            mk = takenoko(mat, m2)
        for k in mk:
            c += bytes(k)

    return c


if __name__ == '__main__':
    m1 = kinoko(flag)
    m2 = [[1,3,2,9,4], [0,2,7,8,4], [3,4,1,9,4], [6,5,3,-1,4], [1,4,5,3,5]]


    print("Encrypted Flag:")
    enc_flag = binascii.hexlify(encrypt(m1, m2)).decode()
    print(enc_flag)

result.txt

Encrypted Flag:
ea5929e97ef77806bb43ec303f304673de19f7e68eddc347f3373ee4c0b662bc37764f74cbb8bb9219e7b5dbc59ca4a42018

アプローチ：逆行列

problem.pyとresult.txtを確認すると以下のことが分かります．

• padding済のflag長は50文字っぽい
• kinokoではflagを行列に変換している
• takenokoではを計算している
• encryptでは乱数に応じて行列演算の順番を決定している

そのため，

$$ {m_{2}}^{-1} \cdot W_{i} $$

または

$$ W_{i} \cdot m_{2}^{-1} $$

を計算すればflagを復号できることが分かります．

ここで， は

$$ m_{2} = \begin{bmatrix} 1 & 3 & 2 & 9 & 4 \\ 0 & 2 & 7 & 8 & 4 \\ 3 & 4 & 1 & 9 & 4 \\ 6 & 5 & 3 & -1 & 4 \\ 1 & 4 & 5 & 3 & 5 \end{bmatrix} $$

なので

$$ m_{2}^{-1} = \frac{1}{243} \begin{bmatrix} 247 & 11 & -194 & 121 & -148 \\ -935 & 41 & 757 & -278 & 332 \\ -198 & 63 & 126 & -36 & 36 \\ -59 & 20 & 67 & -23 & -4 \\ 932 & -110 & -733 & 248 & -221 \end{bmatrix} $$

となります．

通常の行列演算であればあとはやるだけになるのですがこの問題の行列演算は上で行われているためもうひと工夫必要になります．

ここで は 上での逆元となるので として扱えます ．したがって，演算結果にを乗じて すれば復号が可能になります．

以下ソルバです．

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import binascii
import numpy as np

def kinoko(text):
    mat = []
    for i in range(0, len(text), 25):
        mat.append([
            [text[i], text[i+1], text[i+2], text[i+3], text[i+4]],
            [text[i+5], text[i+6], text[i+7], text[i+8], text[i+9]],
            [text[i+10], text[i+11], text[i+12], text[i+13], text[i+14]],
            [text[i+15], text[i+16], text[i+17], text[i+18], text[i+19]],
            [text[i+20], text[i+21], text[i+22], text[i+23], text[i+24]],
            ])
    return mat

def decrypt(mat):
    flag = ''
    for row in mat:
        for x in row:
            flag += chr((int((round(x) * 94) % 251)))

    return flag

def main():
    encode_flag = 'ea5929e97ef77806bb43ec303f304673de19f7e68eddc347f3373ee4c0b662bc37764f74cbb8bb9219e7b5dbc59ca4a42018'
    W = kinoko(binascii.unhexlify(encode_flag))
    w1 = W[0]
    w2 = W[1]
    m2 = np.array([[1,3,2,9,4], [0,2,7,8,4], [3,4,1,9,4], [6,5,3,-1,4], [1,4,5,3,5]])
    inv_m2 = np.linalg.inv(m2) * np.linalg.det(m2)
    print(decrypt(np.dot(w1, inv_m2)))
    print(decrypt(np.dot(w2, inv_m2)))

if __name__ == '__main__':
    main()

Op3n_y0ur_3y3s_1ook_up_t0
_th3_ski3s_4nd_s33%%%%%%%

HarekazeCTF{Op3n_y0ur_3y3s_1ook_up_t0_th3_ski3s_4nd_s33}

まとめ

• さんすうができない
• バイトで時間がとれなかった(これは言い訳)
• Cryptoできるようになりたい