OMH 2021 CTF Writeup - よっちんのブログ

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

Sanity Check (misc)

IRCでfrreenodeの#p4teamに入り、メッセージを見ると、フラグが書いてあった。

p4{covids,they_wont_bring_us_down}

Almost perfect (crypto)

暗号処理は以下の通り。

・key: 14バイト英小文字文字列
・data: 英小文字のみ文字列の配列、配列の各要素は14バイト以下
・dataの各要素をkeyで暗号化
　・shifts: keyの各要素について、'a'を0としたインデックスの配列
　・pt: dataの各要素について、'a'を0としたインデックスの配列
　・ptの各要素でshiftの対応する要素分だけシフトする。
　→ヴィジュネル暗号のようになっている。

単語ごとに同じシフトで英文になるよう試行錯誤して復号する。1文字の単語(a)、2文字の単語(as)などから推測を進める。

import string

key_len = 14

def decrypt(word, key):
    shifts = [ord(k) - ord('a') for k in key]
    pt = [ord(c) - ord('a') for c in word]
    return ''.join([chr(((p - shifts[i]) % len(string.ascii_lowercase)) + ord('a')) for i, p in enumerate(pt)])

with open('output.txt', 'r') as f:
    enc = f.read().split(' ')

# guess
key = 'hhdcfdzqtblrlk'

data = []
for c in enc:
    m = decrypt(c, key)
    #print '[+]', m
    data.append(m)

msg = ' '.join(data)
print msg

復号結果は以下の通り。

if one uses a key that is truly random is at least as long as the encrypted message and is used only once the vigenere cipher is theoretically unbreakable however in that case the key not the cipher provides cryptographic strength and such systems are properly referred to collectively as onetime pad systems irrespective of the ciphers employed confederate cipher wheel captured at the surrender of mobile alabama in may national cryptologic museum vigenere actually invented a stronger cipher an autokey cipher the name vigenere cipher became associated with a simpler polyalphabetic cipher instead in fact the two ciphers were often confused and both were sometimes called le chiffre indechiffrable babbage actually broke the muchstronger autokey cipher but kasiski is generally credited with the first published solution to the fixedkey polyalphabetic ciphers a simple variant is to encrypt by using the vigenere decryption method and to decrypt by using vigenere encryption that method is sometimes referred to as variant beaufort it is different from the beaufort cipher created by francis beaufort which is similar to vigenere but uses a slightly modified enciphering mechanism and tableau the beaufort cipher is a reciprocal cipher despite the vigenere ciphers apparent strength it never became widely used throughout europe the gronsfeld cipher is a variant created by count gronsfeld josse maximilaan van gronsveld ne van bronckhorst it is identical to the vigenere cipher except that it uses just different cipher alphabets corresponding to the digits to a gronsfeld key of is the same as a vigenere key of abcd the gronsfeld cipher is strengthened because its key is not a word but it is weakened because it has just cipher alphabets it is gronsfelds cipher that became widely used throughout germany and europe despite its weaknesses the flag is flat curly brace notsoperfect polyalphabetic shenanigans curly brace

文章の終わりにこう書いてある。

the flag is flat curly brace notsoperfect polyalphabetic shenanigans curly brace

flat{notsoperfect polyalphabetic shenanigans}

Fiend (crypto)

サーバの処理概要は以下の通り。

・flagの長さは16バイト
・timestamp: datetime.now()の文字列
・IVはタイムスタンプのmd5ダイジェスト
・keyはランダム16バイト
・timestamp表示　→ IVはわかる。
・以下繰り返し
　・base64でmsgを入力
　・msg = 入力文字列のbase64デコードした文字列 + flag
　・plaintext: msgをパディング
　・plaintextをAES-CBC暗号化(key, IV)して表示
　・IV: IVのmd5ダイジェスト

IVが毎回変わるが、IVが何かはわかるので、1文字ずつはみ出させ、1ブロック目で平文とIVのXORが同じになり、暗号が同じになるものを探す。

import socket
import base64
import hashlib
from Crypto.Util.strxor import strxor

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('fiend.zajebistyc.tf', 17002))

timestamp = recvuntil(s, '\n').rstrip()
print timestamp

IV = timestamp.encode('ascii')

data = recvuntil(s, '\n').rstrip()
print data

flag = ''
for i in range(16):
    IV = hashlib.md5(IV).digest()
    msg = base64.b64encode('x' * (15 - i))
    data = recvuntil(s, '\n').rstrip()
    print data
    print msg
    s.sendall(msg + '\n')
    data = recvuntil(s, '\n').rstrip()
    print data
    enc0 = base64.b64decode(data)
    iv0 = IV

    for code in range(32, 127):
        print '[+] flag =', flag + chr(code)
        pt = 'x' * (15 - i) + flag + chr(code)
        IV = hashlib.md5(IV).digest()
        msg = base64.b64encode(strxor(strxor(pt, iv0), IV))
        data = recvuntil(s, '\n').rstrip()
        print data
        print msg
        s.sendall(msg + '\n')
        data = recvuntil(s, '\n').rstrip()
        enc = base64.b64decode(data)
        if enc0[:16] == enc[:16]:
            flag += chr(code)
            break

print '[*] flag =', flag

実行結果は以下の通り。

2021-05-16 04:02:01.171028
Hello to FIEND encryption service!
Give me message (base64 encoded):
eHh4eHh4eHh4eHh4eHh4
59mmj7xokzAc1CTjOOFO6A1Z2L0Zvzn2NN8lZTmc+2c=
[+] flag =  
Give me message (base64 encoded):
GchInNKnQnpfQ6LUX3UpVQ==
[+] flag = !
Give me message (base64 encoded):
Z1vztqAu/4ca4a+NVSXMVg==
[+] flag = "
Give me message (base64 encoded):
iyn3W/ISHlFyjFvz5YfTJQ==
[+] flag = #
Give me message (base64 encoded):
ZQTzE95UaLc5b1dlgZKw1w==
　　　　　　　　：
[+] flag = flat{baby_BEASTz
Give me message (base64 encoded):
8E+G3ZOS/8GusB5k4VHg0Q==
[+] flag = flat{baby_BEAST{
Give me message (base64 encoded):
LCCrHta+Dl1GvUjsY1FrzA==
[+] flag = flat{baby_BEAST|
Give me message (base64 encoded):
YNDPWuXcO00Wd/nAIwYPyQ==
[+] flag = flat{baby_BEAST}
Give me message (base64 encoded):
FVl7wAB7j+rOXbxT692ygQ==
[*] flag = flat{baby_BEAST}

flat{baby_BEAST}

Jamal (crypto)

ElGamal暗号。フラグが分割されて問題が分かれている。

■Part1
r1が1であることがわかっているので、簡単に復号できる。

■Part2
2つの暗号があり、以下の条件がある。
・r2 == r3
・f1 == f2

inv_s1 = inverse(pow(r1, x, p), p) = 1
f1 = long_to_bytes(c1 * inv_s1 % p)

inv_s2 = inverse(pow(r2, x, p), p)
f2 = long_to_bytes(c2 * inv_s2 % p)

c2 * inv_s2 % p = c1 % p
→inv_s2 = (c1 * inverse(c2, p)) % p

inv_s3 = inverse(pow(r3, x, p), p)
       = inverse(pow(r2, x, p), p) = inv_s2

f3 = long_to_bytes(c3 * inv_s3 % p)
   = long_to_bytes(c3 * inv_s2 % p)

■Part3
2つの暗号があり、以下の条件がある。
・r5 == pow(r4, 2, p)
・f3 == f4

inv_s4 = inverse(pow(r4, x, p), p)
f4 = long_to_bytes(c4 * inv_s4 % p)

c4 * inv_s4 % p = c3 * inv_s3 % p
→inv_s4 = (c3 * inv_s3 * inverse(c4, p)) % p

inv_s5 = inverse(pow(r5, x, p), p)
       = inverse(pow(pow(r4, 2, p), x, p), p)
       = inverse(pow(r4, x*2, p), p) = pow(inv_s4, 2, p)

f5 = long_to_bytes(c5 * inv_s5 % p)

■Part4
2つの暗号があり、以下の条件がある。
・r7 == g * r6 % p
・f5 == f6

inv_s6 = inverse(pow(r6, x, p), p)
f6 = long_to_bytes(c6 * inv_s6 % p)

c6 * inv_s6 % p = c5 * inv_s5 % p
→inv_s6 = (c5 * inv_s5 * inverse(c6, p)) % p

inv_s7 = inverse(pow(r7, x, p), p)
       = inverse(pow(g * r6, x, p), p)
       = (inverse(pow(g, x, p), p) * inverse(pow(r6, x, p), p) % p
       = (inverse(h, p) * inv_s6) % p

以上を元にフラグにする。

from Crypto.Util.number import bytes_to_long, inverse, long_to_bytes

p = 23913162461506241913954601592637284046163153526897774745274721709391995411082414294401609291264387860355671317653627011946189434760951108211821677155027175527596657912855025319457656605884632294211661524895665376213283136003484198594304828143112655895399585295073436422517502327322352675617692540534545273072811490753897471536886588395908046162672249608111996239705154693112925449400691756514248425452588443058856375927654703767484584645385639739363661773243428539784987039554945923457524757103957080876709268568549852468939830286998008334302308043256863193950115079756866029069932812978097722854877041042275420770789


with open('out.txt', 'r') as f:
    h = int(f.readline().rstrip().split('=')[1])
    c1 = int(f.readline().rstrip().split('=')[1])
    c2 = int(f.readline().rstrip().split('=')[1])
    c3 = int(f.readline().rstrip().split('=')[1])
    c4 = int(f.readline().rstrip().split('=')[1])
    c5 = int(f.readline().rstrip().split('=')[1])
    c6 = int(f.readline().rstrip().split('=')[1])
    c7 = int(f.readline().rstrip().split('=')[1])

#### get f1 ####
r1 = 1
s = r1
inv_s1 = inverse(s, p)
f1 = long_to_bytes(c1 * inv_s1 % p)
print '[+] f1 =', f1.strip()

#### get f3 ####
inv_s2 = (c1 * inverse(c2, p)) % p
inv_s3 = inv_s2
f3 = long_to_bytes(c3 * inv_s3 % p)
print '[+] f3 =', f3.strip()

#### get f5 ####
inv_s4 = (c3 * inv_s3 * inverse(c4, p)) % p
inv_s5 = pow(inv_s4, 2, p)
f5 = long_to_bytes(c5 * inv_s5 % p)
print '[+] f5 =', f5.strip()

#### get f7 ####
inv_s6 = (c5 * inv_s5 * inverse(c6, p)) % p
inv_s7 = (inverse(h, p) * inv_s6) % p
f7 = long_to_bytes(c7 * inv_s7 % p)
print '[+] f7 =', f7.strip()

print 'Flag is', (f1 + f3 + f5 + f7).strip()

実行結果は以下の通り。

[+] f1 = flat{
[+] f3 = s0_m4ny_
[+] f5 = r3lati0n5_
[+] f7 = 5uch_s3cur1ty}
Flag is flat{s0_m4ny_r3lati0n5_5uch_s3cur1ty}

flat{s0_m4ny_r3lati0n5_5uch_s3cur1ty}