Trend Micro CTF 2018 - Raimund Genes Cup - Online Qualifier Writeup

この大会は2018/9/15 13:00(JST)～2018/9/16 13:00(JST)に開催されました。
今回もチームで参戦。結果は 3000点で165チーム中21位でした。
自分で解けた問題をWriteupとして書いておきます。

Analysis-Offensive 300

Alice, Bob, CyrilのメッセージがRSA暗号で暗号化されている。
eはすべて65537。Nはすべて異なる。お互いの組、3組について、公約数を求めてみる。
1以外になったので、素因数分解できた。あとはそのまま復号する。

from Crypto.Util.number import inverse

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    return m

N1 = 23795719145225386804055015945976331504878851440464956768596487167710701468817080174616923533397144140667518414516928416724767417895751634838329442802874972281385084714429143592029962130216053890866347

N2 = 46914096084767238967814493997294740286838053572386502727910903794939283633197997427383196569296188299557978279732421725469482678512672280108542428152186999218210536447287087212703368704976239539968977

N3 = 24543003393712692769038137223030855401835344295968717177380639898023646407807465197761211529143336105057325706788229129519925129413109571220297378014990693203802558792781281981621549760273376606206491

p1, _, _ = egcd(N1, N2)
p2, _, _ = egcd(N2, N3)
p3, _, _ = egcd(N1, N3)

assert p1 * p3 == N1
assert p1 * p2 == N2
assert p2 * p3 == N3

e = 65537

#### decrypt message for Alice
c1 = 18700320110367574655449823553009212724937318442101140581378358928204994827498139841897479168675123789374462637095265564472109735802305521045676412446455683615469865332270051569768255072111079626023422

m1 = decrypt(p1, p3, e, c1)
msg1 = ('%x' % m1).decode('hex')
print msg1

#### decrypt message for Bob
c2 = 27979368157170890767030069060194038526134599497456846620984054211906413024410400026053694007247773572972357106574636186987337336771777265971389911503143036021889778839064900818858188026318442675667707

m2 = decrypt(p1, p2, e, c2)
msg2 = ('%x' % m2).decode('hex')
print msg2

#### decrypt message for Cyril
c3 = 24084879450015204136831744759734371350696278325227327049743434712309456808867398488915798176282769616955247276506807739249439515225213919008982824219656080794207250454008942016125074768497986930713993

m3 = decrypt(p2, p3, e, c3)
msg3 = ('%x' % m3).decode('hex')
print msg3

実行結果は以下の通りで、Bobのメッセージにフラグが含まれていた。

Hi Alice, party is tommorow at 8
Hi Bob, remember, that the flag is TMCTF{B3Car3fu11Ab0utTh3K3ys}
Hi Cyril, could you bring beer tommorow?

TMCTF{B3Car3fu11Ab0utTh3K3ys}

Forensics-Crypto1 400

ブロック暗号のFeistel構造の問題。ただf(x)がXOR関数になっているため、簡単に計算できる。

n: ブロック長の半分( = 144)
h: ラウンド数
l: 鍵サイズ( = 288)
M: 平文空間(2n)
C: 暗号空間(2n)
K: 鍵空間(l)

hが1の場合はMの後半とCの前半が同じになるが、この場合同じになっていない。まずhが2の場合を考える。

M = (m0, m1)

m0, m1 -> m1, m2 = m1, m0 ^ (m1 ^ k1)
m1, m2 -> m2, m3 = m2, m1 ^ (m2 ^ k2) = C

m2 = m0 ^ (m1 ^ k1)
m3 = m1 ^ (m2 ^ k2) = m1 ^ (m0 ^ (m1 ^ k1) ^ k2)
   = m0 ^ k1 ^ k2

このことから逆算して復号する。

M = '010000010110111000100000011000010111000001110000011011000110010100100000011000010110111001100100001000000110000101101110001000000110111101110010011000010110111001100111011001010010000001110111011001010110111001110100001000000111010001101111001000000101010001110010011001010110111001100100'
C = '000100100011000101110101001101100110001100110001001110100011110101100000011110010010111000110011001110000000110100100101011111000011000000100001010000100110011100100001011000000111001101110100011011100110000000100000011011010110001001100100001011010110111001100110001010110110110101110001'
SECRET = '000000110000111001011100001000000001100100101100000100100111111000001001000001100000001100001001000100100010011101001010011000010111100100100010010101110100010001000010010101010100010101111111010001000110000001101001011111110111100001100101011000010010001001001011011000100111001001101011'

m0 = int(M[:144], 2)
m1 = int(M[144:], 2)
m2 = int(C[:144], 2)
m3 = int(C[144:], 2)

k1 = m0 ^ m1 ^ m2
k2 = m0 ^ m3 ^ k1

SECRET1 = int(SECRET[:144], 2)
SECRET2 = int(SECRET[144:], 2)

PLAIN1 = SECRET2 ^ k1 ^ k2
PLAIN2 = SECRET1 ^ PLAIN1 ^ k1

flag1 = ('%036x' % PLAIN1).decode('hex')
flag2 = ('%036x' % PLAIN2).decode('hex')
flag = flag1 + flag2
print flag

TMCTF{Feistel-Cipher-Flag-TMCTF2018}