ICHSA CTF 2021 Writeup

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

Pikatchu's Fault (Fault Injection 100)

RSA CRT Fault Attackで素因数分解する。

from Crypto.Util.number import *
import re

N = 14428106165822100311240179104702593030922229606910261061860621459798477042443217675708638511393783602097391544907229222395222465303690975922805833664159517707002845392996861764206707180372733989400577838887924912395532925065643238637812097531657082837158436848594708309238918390308191361234059534178077141595873018313112575974600539522798755895311426362091301356794727864093165846318233065617022292712839240223002241134094765005135404901074586741323378531189871102865921045940469715763216120732916020528427859371641401521785824628585853094123501351577248220567930583676467206786442597142305655569749177107891502253803
e = 65537
M = 0x4c6f766520616e64206b69737365732c206d697373696e6720796f7521000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2
M2 = 0x1a36d7ecad4b18bc765ff0e3d3ecde7cae84bf1cc445a6fdcb48c335d9d3a043817fc014d55bfad94b51eb522b4ff719d33f012afe1498efafe660b97d1cb806d4ff7985a40a14f9bec9d93e2eb20f3820423ba0e34302adc82156673fa164822779174e9b7a84a417873358d1d774ccdfdb1f36de6aa8249b00184aac2feb003782f16fb3f5d7b113387989f662062452793bbaad87014b1ebd4a020342a11a19d95f4d3b29dd5449c57ea0fd3b881542a7b8b0bdbc9dcb7b19337f40e723439365dc29625cb775e91aef886d79d1403725c5aefa21b3d69f8cacbbbafb8b35c86822113e71bd272ca7cdf68da0ab397c658cb6cc14225732bc07726155ecd1

C = pow(M, e, N)
C2 = pow(M2, e, N)

p = GCD(pow(C2 - C, e, N), N)
q = N / p

p_str = long_to_bytes(p)
q_str = long_to_bytes(q)

pattern = '(ICHSA_CTF{.+})'
m = re.search(pattern, p_str)
if m is not  None:
    flag = m.group(1)
    print flag

m = re.search(pattern, q_str)
if m is not  None:
    flag = m.group(1)
    print flag

ICHSA_CTF{who_needs_more_than_1_fault_with_crt}

Crime Cloud (Crypto 150)

同じ部分文字列が複数あると圧縮後のサイズが小さくなる性質を使って、一文字ずつ特定するCRIMEの問題。何回か試し、圧縮できると文字列長が95になることがわかったので、そのことを使った。

import socket
import string
import base64

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

def send_req(s, inp):
    data = recvuntil(s, ': ')
    print data + inp
    s.sendall(inp + '\n')
    data = recvuntil(s, '\n').rstrip()
    print data
    result = base64.b64decode(data)
    return len(result)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('crime.ichsa.ctf.today', 8008))

flag = 'ICHSA_CTF{'
while True:
    found = False
    while True:
        for c in string.lowercase + '_}':
            length = send_req(s, flag + c)
            if length == 95:
                found = True
                flag += c
                break
        if found:
            break
    if '}' in flag:
        break

print flag

実行結果は以下の通り。

Wellcome!
Input an empty line to exit.

Your input: ICHSA_CTF{a
hYdfGqhcCslKVKOZs2IqD2a6Pkk5VY5xoXKL2+3xTtBphMYy32GlD+tqhwnC1bRsPq7Rmn+wI33WDXnmRdQytCBtdppS1PpHD6eFeM+eiS+r8jvGGNePa3/O2eZ9aC4Gmg==

Your input: ICHSA_CTF{b
4bMWx8xuv1WFm9L3CEYMVisIzRINZ+vQ6Des5vxVGwxQ5ejMyuS7qgnr9wULW0U+ZkK3pAEYIjAF4Og+eoegDvn8KTuveTen/PLh+noJqsBGL3F7Km8cZVhJK2DHobG7

Your input: ICHSA_CTF{c
XWOWujVqSDPHFD1iZbin3i6cjqc4TVyUI/RzzwjH9O5iJFTCNyYBPjbLwR+suKAKC2v6/FGoR5RS2FZGsdX9G4AZqCoC4HV3WsrCXPWe+WET2g6wz1zQBRC75b4D0yFB

　　　　　　　　　　　　　　：

Your input: ICHSA_CTF{compressing_secret_with_input_is_a_crimex
5T8szXe3sbLs7QMqhPuLNvgMndeLdSNMTKVph61YSMZ0vFepclTdZLNBOpy3+3DiJK5+vZmomj0ZvUQMDGQNqu1xT1Q11Qz4+o94dEb6cYouIai48YtxZhxTRDElfPnnTQ==

Your input: ICHSA_CTF{compressing_secret_with_input_is_a_crimey
ipc/khikilO0Nol0u7WJzzq9SzzlgUukLXZywjDShyxVh3ccG66lWf9psRWlrLGOInPYnWWVZ+Htckvv9p5hlhDCN+KosGvxIomyw8dot7uJ1wc5dafI+fjK/Ec7fgwd

Your input: ICHSA_CTF{compressing_secret_with_input_is_a_crimez
7yEVcxMNh6VI9I59S5YwRycJo2KeKDuMtl3KeIupONCQPkSk72rEnXbwUoRuGHHk7S/fSYd7NrqSnveIfwTdvvBJAuo9GBmOV5gdhyY/22ZdEiNl0tjKwFy7uO0Zvb+ONw==

Your input: ICHSA_CTF{compressing_secret_with_input_is_a_crime_
+4kUG+Kr99nzEscVKE59NOXyAbKaNe1Lwm5y6cEkYxlw0OX/F9nX5liOTOAfedA5nUSynzBhqGuZA2y3e5I3pbChrUKLAwLFtQyfv3meZDvesXmL7fHo/EuTseD4tmJQ

Your input: ICHSA_CTF{compressing_secret_with_input_is_a_crime}
JGVzIGu6kyAvKFhETysHb39JpWUb/zhPNZ7E3cqCf9qhVZjC1vYivT2HTNgkJH4ZdfwkHR2UH9rDW75pv2+vrw5Z0e0ZxVsRxat2NDtaJoGL9pqmJCSaz5FBvgLbQdg=
ICHSA_CTF{compressing_secret_with_input_is_a_crime}

ICHSA_CTF{compressing_secret_with_input_is_a_crime}

Baby Homework (Crypto150)

入力＋FLAGがAES暗号化される。1文字ずつはみ出させて該当する暗号ブロックを比較しながら、1文字ずつフラグを割り出す。

$ nc baby_homework.ichsa.ctf.today 8010
Hello! What do you want to encrypt today?
a
88d8390cee4a0b215d1b94e76240f9b07c35ee865d8de8676072d9b798c6e848

$ nc baby_homework.ichsa.ctf.today 8010
Hello! What do you want to encrypt today?
aa
c8b86dfb1d472aab7fc76e7840923af08fedccacc986bf96ad39a7218107079e

$ nc baby_homework.ichsa.ctf.today 8010
Hello! What do you want to encrypt today?
aaa
56bea9a8e003b77d540c509f89094fa3c1a68e6228cf6dcf80d3585f41a66f8d

$ nc baby_homework.ichsa.ctf.today 8010
Hello! What do you want to encrypt today?
aaaa
8d61319569762f580a991128cb825a795a8c7ec693f69900b71da9e365ee72f4

$ nc baby_homework.ichsa.ctf.today 8010
Hello! What do you want to encrypt today?
aaaaa
a93071ba224344256e4e6b461a7cb9e47929019756343aa26e8c2e15fc7ca914

$ nc baby_homework.ichsa.ctf.today 8010
Hello! What do you want to encrypt today?
aaaaaa
db3c7f3f162f1c478cc7acbb54357e5ff6ef6ff296c93f4f8d23a5a276489dad

$ nc baby_homework.ichsa.ctf.today 8010
Hello! What do you want to encrypt today?
aaaaaaa
8547849b18d7e0fca1aa795d52d956896a5121b13076b6afa043b02b0b930c1c3cf284e29ab154b48e8c11fb9e65cc04

以下のようなイメージになる。

0123456789abcdef
XXXXXXXFFFFFFFFF
FFFFFFFFFFFFFFFF
PPPPPPPPPPPPPPPP

以下のようなイメージで1文字ずつ割り出す。

0123456789abcdef
XXXXXXXXXXXXXXX?
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXF
FFFFFFFFFFFFFFFF
FFFFFFFFPPPPPPPP

比較するブロックは1ブロック目と3ブロック目。

import socket

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

flag = ''
for i in range(25):
    for code in range(32, 127):
        if i < 16:
            try_inp = 'X' * (15 - i) + flag + chr(code) + 'X' * (31 - i)
        else:
            try_inp = flag[-15:] + chr(code) + 'X' * (31 - i)

        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.connect(('baby_homework.ichsa.ctf.today', 8010))

        data = recvuntil(s, '?\n').rstrip()
        print data
        print try_inp
        s.sendall(try_inp + '\n')

        data = recvuntil(s, '\n').rstrip()
        print data
        b0 = data[:32]
        b2 = data[64:96]
        if b0 == b2:
            flag += chr(code)
            break

print flag

実行結果は以下の通り。

　　　　　　　　　：
Hello! What do you want to encrypt today?
t_DeF4uL7_V4lu3vXXXXXXX
f7e2482f4ded017ed447307088a68c9a1964750ffb854741e05b71deb6afc0ef6a5121b13076b6afa043b02b0b930c1cf25ad892a7e0256af842d1c6a709e777
Hello! What do you want to encrypt today?
t_DeF4uL7_V4lu3wXXXXXXX
5d1c67ccc026686bea22df5f4c92020d1964750ffb854741e05b71deb6afc0ef6a5121b13076b6afa043b02b0b930c1c6134fd11f55e338884ec6bf1c50dfe3c
Hello! What do you want to encrypt today?
t_DeF4uL7_V4lu3xXXXXXXX
e9e27e8ec5f4cffd0e2936d4843789811964750ffb854741e05b71deb6afc0ef6a5121b13076b6afa043b02b0b930c1c1b646dd9b79f3f5352a8b8bde6ae65c2
Hello! What do you want to encrypt today?
t_DeF4uL7_V4lu3yXXXXXXX
7fd0994e1e4d361a39ad3647bee39d621964750ffb854741e05b71deb6afc0ef6a5121b13076b6afa043b02b0b930c1cc8b1fa40240694818015d8be8fd3b640
Hello! What do you want to encrypt today?
t_DeF4uL7_V4lu3zXXXXXXX
6a5121b13076b6afa043b02b0b930c1c1964750ffb854741e05b71deb6afc0ef6a5121b13076b6afa043b02b0b930c1c6cd49de5bb815da7f6f6dea44abb6efc
d0n7_7ruzt_DeF4uL7_V4lu3z

ICHSA_CTF{d0n7_7ruzt_DeF4uL7_V4lu3z}

Poodle1 (Crypto 200)

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

・flagを特定のkeyとランダムなivでAES-CBC暗号化して表示
・msg入力(hex)
・hexデコードし、AES-CBC復号
・パディングエラーになったら、メッセージ表示

CBC Padding Oracle Attackで復号する。

import socket

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

def str_xor(s1, s2):
    return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2))

def unpad(s):
    return s[:-ord(s[-1])]

def is_valid(s, enc):
    data = recvuntil(s, '>> ')
    print data + enc
    s.sendall(enc + '\n')

    data = recvuntil(s, '\n').rstrip()
    print data
    if data != 'invalid padding >:(':
        return True
    else:
        return False

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('poodle1.ichsa.ctf.today', 8003))

data = recvuntil(s, 'poodle?\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data
enc = data.decode('hex')

enc_blocks = []
for i in range(0, len(enc), 16):
    enc_blocks.append(enc[i:i+16])

xor_blocks = []
for i in range(len(enc_blocks)-1, 0, -1):
    xor_block = ''
    for j in range(16):
        for code in range(256):
            print '%d - %d - %d: %s' % (i, j, code, xor_block.encode('hex'))
            print '****', str_xor(xor_block, enc_blocks[i-1][-j:]), '****'
            try_pre_block = '\x00' * (16 - j - 1) + chr(code) + str_xor(xor_block, chr(j+1)*j)
            try_cipher = (try_pre_block + enc_blocks[i]).encode('hex')
            if is_valid(s, try_cipher):
                xor_code = (j+1) ^ code
                xor_block = chr(xor_code) + xor_block
                break

    xor_blocks.append(xor_block)

xor_blocks.reverse()

flag = ''
for i in range(len(xor_blocks)):
    flag += str_xor(enc_blocks[i], xor_blocks[i])

flag = unpad(flag)
print flag

実行結果は以下の通り。

hi there!
I am the oracle :D
searching for a poodle, huh?
what about that cute and encrypted poodle?

14bfcca6528034a7bb309e7a8fbd4299fbb3cecff54817a54bc1080965d4011b71fac255e72e39fa6d42baa6462c2531
2 - 0 - 0: 
****  ****

BTW, if you want to tell me something don't forget to encrypt it
(with my secret key, of course ;))


What do you want to tell me? ('nothing' to exit)
>> 0000000000000000000000000000000071fac255e72e39fa6d42baa6462c2531
invalid padding >:(
2 - 0 - 1: 
****  ****

What do you want to tell me? ('nothing' to exit)
>> 0000000000000000000000000000000171fac255e72e39fa6d42baa6462c2531
invalid padding >:(

　　　　　　　　　：

What do you want to tell me? ('nothing' to exit)
>> 4aec94e503cf67e3ed5bc735fb9d3cfdfbb3cecff54817a54bc1080965d4011b
invalid padding >:(
1 - 15 - 75: fc84f513df77f3fd4bd725eb8d2ced
**** CHSA_CTF{I_d0nt ****

What do you want to tell me? ('nothing' to exit)
>> 4bec94e503cf67e3ed5bc735fb9d3cfdfbb3cecff54817a54bc1080965d4011b
invalid padding >:(
1 - 15 - 76: fc84f513df77f3fd4bd725eb8d2ced
**** CHSA_CTF{I_d0nt ****

What do you want to tell me? ('nothing' to exit)
>> 4cec94e503cf67e3ed5bc735fb9d3cfdfbb3cecff54817a54bc1080965d4011b
invalid padding >:(
1 - 15 - 77: fc84f513df77f3fd4bd725eb8d2ced
**** CHSA_CTF{I_d0nt ****

What do you want to tell me? ('nothing' to exit)
>> 4dec94e503cf67e3ed5bc735fb9d3cfdfbb3cecff54817a54bc1080965d4011b
mmm... very interesting... thank you!
ICHSA_CTF{I_d0nt_like_oracl3s}

ICHSA_CTF{I_d0nt_like_oracl3s}

Poodle2 (Crypto 300)

考え方はPoodle1と同じ。"givemetheflag"は16バイト未満なので、適当な暗号1ブロックに対して、復号したものを求め、それとXORをとればよい。

import socket
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

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

def str_xor(s1, s2):
    return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2))

def is_valid(s, enc):
    data = recvuntil(s, '>> ')
    print data + enc
    s.sendall(enc + '\n')

    data = recvuntil(s, '\n').rstrip()
    print data
    if data != 'invalid padding >:(':
        return True
    else:
        return False

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('poodle2.ichsa.ctf.today', 8004))

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

enc_blocks = ['X' * 16, 'X' * 16]

xor_blocks = []
for i in range(len(enc_blocks)-1, 0, -1):
    xor_block = ''
    for j in range(16):
        for code in range(256):
            print '%d - %d - %d: %s' % (i, j, code, xor_block.encode('hex'))
            try_pre_block = '\x00' * (16 - j - 1) + chr(code) + str_xor(xor_block, chr(j+1)*j)
            try_cipher = (try_pre_block + enc_blocks[i]).encode('hex')
            if is_valid(s, try_cipher):
                xor_code = (j+1) ^ code
                xor_block = chr(xor_code) + xor_block
                break

    xor_blocks.append(xor_block)

xor_blocks.reverse()

msg = pad('givemetheflag', AES.block_size)
iv = str_xor(msg, xor_blocks[0])
cipher = (iv + enc_blocks[1]).encode('hex')

data = recvuntil(s, '>> ')
print data + cipher
s.sendall(cipher + '\n')
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

hi there!
it's the oracle again :)
ok ok, I promise to give you your poodle this time - not encrypted
just send me the word: givemetheflag
encrypted
with my secret key
that only I know
>:)
(add padding if needed of course... I know you can do it)
1 - 0 - 0: 


What do you want to send me? ('nothing' to exit)
>> 0000000000000000000000000000000058585858585858585858585858585858
invalid padding >:(
1 - 0 - 1: 

What do you want to send me? ('nothing' to exit)
>> 0000000000000000000000000000000158585858585858585858585858585858
invalid padding >:(

　　　　　　　　：

What do you want to send me? ('nothing' to exit)
>> 178d7ef913f2d24c87e9194c0f03f25c58585858585858585858585858585858
invalid padding >:(
1 - 15 - 24: 9d6ee903e2c25c97f9095c1f13e24c

What do you want to send me? ('nothing' to exit)
>> 188d7ef913f2d24c87e9194c0f03f25c58585858585858585858585858585858
invalid padding >:(
1 - 15 - 25: 9d6ee903e2c25c97f9095c1f13e24c

What do you want to send me? ('nothing' to exit)
>> 198d7ef913f2d24c87e9194c0f03f25c58585858585858585858585858585858
mmm... very interesting... thank you!

What do you want to send me? ('nothing' to exit)
>> 6ef4188c6e87b634f29f653d7810e14f58585858585858585858585858585858
nice work! b'ICHSA_CTF{y3s_y0u_c4n_als0_encrypt_in_tha7_w4y_a660a2}'

ICHSA_CTF{y3s_y0u_c4n_als0_encrypt_in_tha7_w4y_a660a2}

Pwn2Win CTF 2021 Writeup

この大会は2021/5/29 1:37(JST)～2021/5/31 1:37(JST)に開催されました。
今回もチームで参戦。結果は50点で720チーム中413位でした。
参加表明問題しか解いていませんが、自分で解けた問題をWriteupとして書いておきます。

~Rhiza - founded on the human being (bonus)

問題文にフラグが書いてあった。

CTF-BR{join_Lauras_fight_against_opression_and_discover_the_truth!}

SECCON Beginners CTF 2021 Writeup

この大会は2021/5/22 14:00(JST)～2021/5/23 14:00(JST)に開催されました。
この大会はチーム戦でしたが、1人チームで参加。結果は1811点で943チーム中76位でした。
自分の弱点を強化するための1人チーム参戦なので、結果はあまりよくないですが、勉強にはなりました。
今後のためにも自分の解けた問題をWriteupとして書いておきます。

welcome (welcome)

Discordに入り、#announcementsチャネルのメッセージを見ると、フラグが書いてあった。

ctf4b{Welcome_to_SECCON_Beginners_CTF_2021}

git-leak (misc)

$ cd .git
$ cat refs/heads/master
e0b545f42cd1b3d51defe4cf6fe235f143e73d93

$ cat logs/HEAD
0000000000000000000000000000000000000000 c27f346b227d2ac4d267dcdb26d14ff6d9e9f365 task4233 <29667656+task4233@users.noreply.github.com> 1620483366 +0900	commit (initial): initial commit
c27f346b227d2ac4d267dcdb26d14ff6d9e9f365 656db59e6f8afccfccbe80a2826ed28cecad8b36 task4233 <29667656+task4233@users.noreply.github.com> 1620483390 +0900	commit: feat: add README.md
656db59e6f8afccfccbe80a2826ed28cecad8b36 6d21e224d5c7c952797a0a7c6a8e456eda8f2bf6 task4233 <29667656+task4233@users.noreply.github.com> 1620488159 +0900	commit: feat: git addの説明を追加
6d21e224d5c7c952797a0a7c6a8e456eda8f2bf6 9fcb00646c821ae57679ad7564a611dbf2f56245 task4233 <29667656+task4233@users.noreply.github.com> 1620488580 +0900	commit: feat: git commitの説明追加
9fcb00646c821ae57679ad7564a611dbf2f56245 a4f7fe94c8c5a710e65a040557eddbe9512bc7ee task4233 <29667656+task4233@users.noreply.github.com> 1620488745 +0900	commit: feat: git logの説明を追加
a4f7fe94c8c5a710e65a040557eddbe9512bc7ee d5aeffe8052a0fde365005c18cc5ce77372df28d task4233 <29667656+task4233@users.noreply.github.com> 1620489336 +0900	commit: feat: resetの説明を追加
d5aeffe8052a0fde365005c18cc5ce77372df28d f66de64cb24616fe4e8b2cce9adf9b8648dbef83 task4233 <29667656+task4233@users.noreply.github.com> 1620489506 +0900	commit: feat: reflogの説明追加
f66de64cb24616fe4e8b2cce9adf9b8648dbef83 d3b47fe3fc6fd790e1dc4bf261f75cd9d55bb099 task4233 <29667656+task4233@users.noreply.github.com> 1620489901 +0900	commit: feat: fsckを追記する
d3b47fe3fc6fd790e1dc4bf261f75cd9d55bb099 8fc078d4d404e2ae9b9e10c94a63d459c1f973ef task4233 <29667656+task4233@users.noreply.github.com> 1620490469 +0900	commit: feat: git cat-fileの説明を追加
8fc078d4d404e2ae9b9e10c94a63d459c1f973ef 9ac9b0cdcde2e15a05764062117d81442a9cb4f5 task4233 <29667656+task4233@users.noreply.github.com> 1620490513 +0900	commit: change: 順番を変更
9ac9b0cdcde2e15a05764062117d81442a9cb4f5 36a4809f1ae8013432eb52cfd2f9f062a3269499 task4233 <29667656+task4233@users.noreply.github.com> 1620490831 +0900	commit: feat: commit-treeの説明を追加
36a4809f1ae8013432eb52cfd2f9f062a3269499 73879828a8ecac85c705508cdc9398f26c697249 task4233 <29667656+task4233@users.noreply.github.com> 1620491725 +0900	commit: feat: めもを追加
73879828a8ecac85c705508cdc9398f26c697249 73879828a8ecac85c705508cdc9398f26c697249 task4233 <29667656+task4233@users.noreply.github.com> 1620491734 +0900	reset: moving to HEAD
73879828a8ecac85c705508cdc9398f26c697249 36a4809f1ae8013432eb52cfd2f9f062a3269499 task4233 <29667656+task4233@users.noreply.github.com> 1620491768 +0900	rebase -i (start): checkout HEAD~2
36a4809f1ae8013432eb52cfd2f9f062a3269499 73879828a8ecac85c705508cdc9398f26c697249 task4233 <29667656+task4233@users.noreply.github.com> 1620491768 +0900	rebase -i: fast-forward
73879828a8ecac85c705508cdc9398f26c697249 b3bfb5c80e48bba23ab820ff91442cc3800c393a task4233 <29667656+task4233@users.noreply.github.com> 1620491811 +0900	commit (amend): feat: めもを追加
b3bfb5c80e48bba23ab820ff91442cc3800c393a b3bfb5c80e48bba23ab820ff91442cc3800c393a task4233 <29667656+task4233@users.noreply.github.com> 1620491834 +0900	rebase -i (finish): returning to refs/heads/master
b3bfb5c80e48bba23ab820ff91442cc3800c393a 80f3044ec17bd6be63f428e87e0a5fce690c50c5 task4233 <29667656+task4233@users.noreply.github.com> 1620491866 +0900	commit (amend): feat: めもを追加
80f3044ec17bd6be63f428e87e0a5fce690c50c5 e0b545f42cd1b3d51defe4cf6fe235f143e73d93 taro hoge <taro@secc0n.jp> 1620491902 +0900	commit (amend): feat: めもを追加

$ python -c 'import zlib; print zlib.decompress(open("objects/73/879828a8ecac85c705508cdc9398f26c697249").read())'
commit 276tree a5b6b52f47aba96730ab61471ddcdff864e5dd8c
parent 36a4809f1ae8013432eb52cfd2f9f062a3269499
author task4233 <29667656+task4233@users.noreply.github.com> 1620491725 +0900
committer task4233 <29667656+task4233@users.noreply.github.com> 1620491725 +0900

feat: めもを追加

$ python -c 'import zlib; print zlib.decompress(open("objects/a5/b6b52f47aba96730ab61471ddcdff864e5dd8c").read())' | xxd -g 1
00000000: 74 72 65 65 20 31 30 38 00 31 30 30 36 34 34 20  tree 108.100644 
00000010: 52 45 41 44 4d 45 2e 6d 64 00 16 29 08 35 a0 f7  README.md..).5..
00000020: 4c cf 30 cb f3 0d 79 1c 84 39 2a 9d cc e6 31 30  L.0...y..9*...10
00000030: 30 36 34 34 20 66 6c 61 67 2e 74 78 74 00 4c bb  0644 flag.txt.L.
00000040: 03 5d 2f f0 72 12 7b 4e 22 91 94 85 12 7d 22 73  .]/.r.{N"....}"s
00000050: e8 8e 31 30 30 36 34 34 20 6e 6f 74 65 2e 6d 64  ..100644 note.md
00000060: 00 62 33 7f db 59 ce b0 48 f7 da 9e af 76 89 23  .b3..Y..H....v.#
00000070: d7 44 93 08 42 0a                                .D..B.

$ python -c 'import zlib; print zlib.decompress(open("objects/4c/bb035d2ff072127b4e22919485127d2273e88e").read())'
blob 40ctf4b{0verwr1te_1s_n0t_c0mplete_1n_G1t}

ctf4b{0verwr1te_1s_n0t_c0mplete_1n_G1t}

rewriter (pwnable)

$ ./chall

[Addr]              |[Value]             
====================+===================
 0x00007ffe2f791a80 | 0x0000000000000000  <- buf
 0x00007ffe2f791a88 | 0x0000000000000000 
 0x00007ffe2f791a90 | 0x0000000000000000 
 0x00007ffe2f791a98 | 0x0000000000000000 
 0x00007ffe2f791aa0 | 0x0000000000000000  <- target
 0x00007ffe2f791aa8 | 0x0000000000000000  <- value
 0x00007ffe2f791ab0 | 0x0000000000401520  <- saved rbp
 0x00007ffe2f791ab8 | 0x00007f9a114a0bf7  <- saved ret addr
 0x00007ffe2f791ac0 | 0x0000000000000001 
 0x00007ffe2f791ac8 | 0x00007ffe2f791b98 

Where would you like to rewrite it?

実行すると、stackの情報が見える。ソースコードを見ると、win関数があり、フラグを表示させている。

$ readelf -s chall | grep win
    67: 00000000004011f6    69 FUNC    GLOBAL DEFAULT   15 win

ret addrをwin関数のアドレスに書き換えれば、フラグが表示される。

$ nc rewriter.quals.beginners.seccon.jp 4103

[Addr]              |[Value]             
====================+===================
 0x00007fffbb1a1530 | 0x0000000000000000  <- buf
 0x00007fffbb1a1538 | 0x0000000000000000 
 0x00007fffbb1a1540 | 0x0000000000000000 
 0x00007fffbb1a1548 | 0x0000000000000000 
 0x00007fffbb1a1550 | 0x0000000000000000  <- target
 0x00007fffbb1a1558 | 0x0000000000000000  <- value
 0x00007fffbb1a1560 | 0x0000000000401520  <- saved rbp
 0x00007fffbb1a1568 | 0x00007f942ab9ebf7  <- saved ret addr
 0x00007fffbb1a1570 | 0x0000000000000001 
 0x00007fffbb1a1578 | 0x00007fffbb1a1648 

Where would you like to rewrite it?
> 0x00007fffbb1a1568
0x00007fffbb1a1568 = 0x00000000004011f6

[Addr]              |[Value]             
====================+===================
 0x00007fffbb1a1530 | 0x3030303030307830  <- buf
 0x00007fffbb1a1538 | 0x3131303430303030 
 0x00007fffbb1a1540 | 0x00000000000a3666 
 0x00007fffbb1a1548 | 0x0000000000000000 
 0x00007fffbb1a1550 | 0x00000000004011f6  <- target
 0x00007fffbb1a1558 | 0x00007fffbb1a1568  <- value
 0x00007fffbb1a1560 | 0x0000000000401520  <- saved rbp
 0x00007fffbb1a1568 | 0x00000000004011f6  <- saved ret addr
 0x00007fffbb1a1570 | 0x0000000000000001 
 0x00007fffbb1a1578 | 0x00007fffbb1a1648 

ctf4b{th3_r3turn_4ddr355_15_1n_th3_5t4ck}

ctf4b{th3_r3turn_4ddr355_15_1n_th3_5t4ck}

only_read (reversing)

Ghidraでデコンパイルする。

void main(void)

{
  ssize_t sVar1;
  long in_FS_OFFSET;
  undefined8 local_28;
  undefined8 local_20;
  undefined4 local_18;
  undefined2 local_14;
  char local_12;
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  local_28 = 0;
  local_20 = 0;
  local_18 = 0;
  local_14 = 0;
  local_12 = '\0';
  sVar1 = read(0,&local_28,0x17);
  *(undefined *)((long)&local_28 + sVar1) = 0;
  if (((((((char)local_28 == 'c') && (local_28._1_1_ == 't')) && (local_28._2_1_ == 'f')) &&
       (((local_28._3_1_ == '4' && (local_28._4_1_ == 'b')) &&
        ((local_28._5_1_ == '{' && ((local_28._6_1_ == 'c' && (local_28._7_1_ == '0')))))))) &&
      (((char)local_20 == 'n' &&
       ((((((local_20._1_1_ == '5' && (local_20._2_1_ == 't')) && (local_20._3_1_ == '4')) &&
          ((local_20._4_1_ == 'n' && (local_20._5_1_ == 't')))) &&
         ((local_20._6_1_ == '_' && ((local_20._7_1_ == 'f' && ((char)local_18 == '0')))))) &&
        (local_18._1_1_ == 'l')))))) &&
     ((((local_18._2_1_ == 'd' && (local_18._3_1_ == '1')) && ((char)local_14 == 'n')) &&
      ((local_14._1_1_ == 'g' && (local_12 == '}')))))) {
    puts("Correct");
  }
  else {
    puts("Incorrect");
  }
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return;
}

文字を比較している部分の比較文字を順に並べる。

ctf4b{c0n5t4nt_f0ld1ng}

children (reversing)

straceでPIDを答えていく。最後に子プロセスの数を答えたら、フラグが表示される。

$ strace ./children
execve("./children", ["./children"], 0x7fffa79a50a0 /* 54 vars */) = 0
brk(NULL)                               = 0x5606fbe07000
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=124482, ...}) = 0
mmap(NULL, 124482, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f6511236000
close(3)                                = 0
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\20\35\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=2030928, ...}) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f6511234000
mmap(NULL, 4131552, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f6510c3b000
mprotect(0x7f6510e22000, 2097152, PROT_NONE) = 0
mmap(0x7f6511022000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1e7000) = 0x7f6511022000
mmap(0x7f6511028000, 15072, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f6511028000
close(3)                                = 0
arch_prctl(ARCH_SET_FS, 0x7f6511235500) = 0
mprotect(0x7f6511022000, 16384, PROT_READ) = 0
mprotect(0x5606fa69e000, 4096, PROT_READ) = 0
mprotect(0x7f6511255000, 4096, PROT_READ) = 0
munmap(0x7f6511236000, 124482)          = 0
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 2), ...}) = 0
brk(NULL)                               = 0x5606fbe07000
brk(0x5606fbe28000)                     = 0x5606fbe28000
write(1, "I will generate 10 child process"..., 36I will generate 10 child processes.
) = 36
write(1, "They also might generate additio"..., 51They also might generate additional child process.
) = 51
write(1, "Please tell me each process id i"..., 58Please tell me each process id in order to identify them!
) = 58
write(1, "\n", 1
)                       = 1
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79373
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79373, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
fstat(0, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 2), ...}) = 0
read(0, 79373
"79373\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79374
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79375
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79374, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
write(1, "Please give me my child pid!\n", 29) = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79375, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
read(0, 79375
"79375\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79378
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
read(0, 0x5606fbe07670, 1024)           = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79378, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
read(0, 79378
"79378\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79379
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79380
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79379, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79380, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
read(0, 79380
"79380\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79381
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
read(0, 0x5606fbe07670, 1024)           = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79381, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
read(0, 79381
"79381\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79384
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79384, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
read(0, 79384
"79384\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79441
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
read(0, 0x5606fbe07670, 1024)           = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79441, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
read(0, 79441
"79441\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79443
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
read(0, 0x5606fbe07670, 1024)           = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79443, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
read(0, 79443
"79443\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79444
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
read(0, 0x5606fbe07670, 1024)           = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79444, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
read(0, 79444
"79444\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79445
write(1, "Please give me my child pid!\n", 29Please give me my child pid!
) = 29
read(0, 0x5606fbe07670, 1024)           = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
--- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79445, si_uid=1000, si_status=1, si_utime=0, si_stime=0} ---
read(0, 79445
"79445\n", 1024)                = 6
write(1, "ok\n", 3ok
)                     = 3
wait4(-1, NULL, 0, NULL)                = 79373
write(1, "How many children were born?\n", 29How many children were born?
) = 29
read(0, 12
"12\n", 1024)                   = 3
write(1, "ctf4b{p0werfu1_tr4sing_t0015_15_"..., 40ctf4b{p0werfu1_tr4sing_t0015_15_usefu1}	) = 40
lseek(0, -1, SEEK_CUR)                  = -1 ESPIPE (Illegal seek)
exit_group(0)                           = ?
+++ exited with 0 +++

ctf4b{p0werfu1_tr4sing_t0015_15_usefu1}

be_angry (reversing)

正しい結果のルートを確認し、angrで解く。

import angr

base = 0x400000
ok = [0x00002539]
ng = [0x0000258d, 0x00001435, 0x00001378, 0x00001f78, 0x000026c4, 0x00001963, 0x00002031, 0x00001947, 0x00001eb4, 0x0000251d]
for i in range(len(ok)):
    ok[i] = ok[i] + base
for i in range(len(ng)):
    ng[i] = ng[i] + base

p = angr.Project('./chall')
state = p.factory.entry_state()
sim = p.factory.simulation_manager(state)
sim.explore(find=ok, avoid=ng)
if len(sim.found) > 0:
        print(sim.found[0].posix.dumps(0))

ctf4b{3nc0d3_4r1thm3t1c}

osoba (web)

リンクされているページにアクセスすると、以下のURLに遷移する。

https://osoba.quals.beginners.seccon.jp/?page=public/wip.html

pageパラメータでページが指定できる。ディレクトリトラバーサルの問題のようだ。https://osoba.quals.beginners.seccon.jp/?page=../flagにアクセスしてみるとフラグが表示された。

ctf4b{omisoshiru_oishi_keredomo_tsukuruno_taihen}

cant_use_db (web)

$20,000しか持っていないが、$10,000のNoodleを2つ、$20,000のSoupを1つ購入する必要がある。プログラムを見ると、きちんとセッション管理されていないので、素早く、Noodles→Soup→Noodlesの順にBuyをクリックすれば購入できる。この後、Eatしたら、フラグが表示された。

ctf4b{r4m3n_15_4n_3553n714l_d15h_f0r_h4ck1n6}

simple_RSA (crypto)

eが小さいため、Low Public-Exponent Attackで復号する。

import gmpy
from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    n = int(f.readline().rstrip().split(' = ')[1])
    e = int(f.readline().rstrip().split(' = ')[1])
    c = int(f.readline().rstrip().split(' = ')[1])

m = gmpy.root(c, e)[0]
assert pow(m, e, n) == c

flag = long_to_bytes(m)
print flag

ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}

Logical_SEESAW (crypto)

暗号処理の概要は以下の通り。

・flag: flagの2進数のlist
・key : flagと同じ長さの0, 1のリスト
・16回以下を繰り返す。
　・m = 0.5
　・flagの長さだけ以下を繰り返す。
　　・n: 1以下のランダム
　　・nがmより大きい場合、各ビットでkeyとの&を結合したものを結合する。

16回の&の計算で"1"が1個でもある場合は"1"にし、それ以外は"0"にする。

from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    cipher = eval(f.read().split(' = ')[1])

bin_flag = ''
for i in range(len(cipher[0])):
    found_1 = False
    for j in range(16):
        if cipher[j][i] == '1':
            found_1 = True
            break
    if found_1:
        bin_flag += '1'
    else:
        bin_flag += '0'

flag = long_to_bytes(int(bin_flag, 2))
print flag

ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

GFM (crypto)

enc = key * M * key
→ M = key.inverse() * enc * key.inverse()

この計算をすれば、フラグがわかる。

#!/usr/bin/sage

p = 331941721759386740446055265418196301559
key = [
[116401981595413622233973439379928029316, 198484395131713718904460590157431383741, 210254590341158275155666088591861364763, 63363928577909853981431532626692827712, 85569529885869484584091358025414174710, 149985744539791485007500878301645174953, 257210132141810272397357205004383952828, 184416684170101286497942970370929735721],
[42252147300048722312776731465252376713, 199389697784043521236349156255232274966, 310381139154247583447362894923363190365, 275829263070032604189578502497555966953, 292320824376999192958281274988868304895, 324921185626193898653263976562484937554, 22686717162639254526255826052697393472, 214359781769812072321753087702746129144],
[211396100900282889480535670184972456058, 210886344415694355400093466459574370742, 186128182857385981551625460291114850318, 13624871690241067814493032554025486106, 255739890982289281987567847525614569368, 134368979399364142708704178059411420318, 277933069920652939075272826105665044075, 61427573037868265485473537350981407215],
[282725280056297471271813862105110111601, 183133899330619127259299349651040866360, 275965964963191627114681536924910494932, 290264213613308908413657414549659883232, 140491946080825343356483570739103790896, 115945320124815235263392576250349309769, 240154953119196334314982419578825033800, 33183533431462037262108359622963646719],
[53797381941014407784987148858765520206, 136359308345749561387923094784792612816, 26225195574024986849888325702082920826, 262047729451988373970843409716956598743, 170482654414447157611638420335396499834, 270894666257247100850080625998081047879, 91361079178051929124422796293638533509, 34320536938591553179352522156012709152],
[266361407811039627958670918210300057324, 40603082064365173791090924799619398850, 253357188908081828561984991424432114534, 322939245175391203579369607678957356656, 63315415224740483660852444003806482951, 224451355249970249493628425010262408466, 80574507596932581147177946123110074284, 135660472191299636620089835364724566497],
[147031054061160640084051220440591645233, 286143152686211719101923153591621514114, 330366815640573974797084150543488528130, 144943808947651161283902116225593922999, 205798118501774672701619077143286382731, 317326656225121941341827388220018201533, 14319175936916841467976601008623679266, 112709661623759566156255015500851204670],
[306746575224464214911885995766809188593, 35156534122767743923667417474200538878, 35608800809152761271316580867239668942, 259728427797578488375863755690441758142, 29823482469997458858051644485250558639, 137507773879704381525141121774823729991, 29893063272339035080311541822496817623, 292327683738678589950939775184752636265]
]

enc = [
[133156758362160693874249080602263044484, 293052519705504374237314478781574255411, 72149359944851514746901936133544542235, 56884023532130350649269153560305458687, 67693140194970657150958369664873936730, 227562364727203645742246559359263307899, 98490363636066788474326997841084979092, 323336812987530088571937131837711189774],
[244725074927901230757605861090949184139, 63515536426726760809658259528128105864, 297175420762447340692787685976316634653, 279269959863745528135624660183844601533, 203893759503830977666718848163034645395, 163047775389856094351865609811169485260, 103694284536703795013187648629904551283, 322381436721457334707426033205713602738],
[17450567396702585206498315474651164931, 105594468721844292976534833206893170749, 10757192948155933023940228740097574294, 132150825033376621961227714966632294973, 329990437240515073537637876706291805678, 57236499879418458740541896196911064438, 265417446675313880790999752931267955356, 73326674854571685938542290353559382428],
[270340230065315856318168332917483593198, 217815152309418487303753027816544751231, 55738850736330060752843300854983855505, 236064119692146789532532278818003671413, 104963107909414684818161043267471013832, 234439803801976616706759524848279829319, 173296466130000392237506831379251781235, 34841816336429947760241770816424911200],
[140341979141710030301381984850572416509, 248997512418753861458272855046627447638, 58382380514192982462591686716543036965, 188097853050327328682574670122723990784, 125356457137904871005571726686232857387, 55692122688357412528950240580072267902, 21322427002782861702906398261504812439, 97855599554699774346719832323235463339],
[298368319184145017709393597751160602769, 311011298046021018241748692366798498529, 165888963658945943429480232453040964455, 240099237723525827201004876223575456211, 306939673050020405511805882694537774846, 7035607106089764511604627683661079229, 198278981512146990284619915272219052007, 255750707476361671578970680702422436637],
[45315424384273600868106606292238082349, 22526147579041711876519945055798051695, 15778025992115319312591851693766890019, 318446611756066795522259881812628512448, 269954638404267367913546070681612869355, 205423708248276366495211174184786418791, 92563824983279921050396256326760929563, 209843107530597179583072730783030298674],
[662653811932836620608984350667151180, 304181885849319274230319044357612000272, 280045476178732891877948766225904840517, 216340293591880460916317821948025035163, 79726526647684009633247003110463447210, 36010610538790393011235704307570914178, 284067290617158853279270464803256026349, 45816877317461535723616457939953776625]
]

key = matrix(Zmod(p), key)
enc = matrix(Zmod(p), enc)
M = key.inverse() * enc * key.inverse()

flag = ''
end = False
for i in range(8):
    for j in range(8):
        c = chr(M[i][j])
        flag += c
        if flag[-1] == '}':
            end = True
            break
    if end:
        break

print flag

ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

Imaginary (crypto)

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

■1._save()
・re: Real part入力
・im: Imaginary part入力
・numbers['<re> + <im>i'] = [re, im]

■2._show()
・numbersの一覧を表示

■3._import()
・data: 入力(hex文字列)
・enc: dataのhexデコード
・固定のkeyでencをAES-ECB復号
・復号したデータをjsonとして読み込み
・numbersの一覧を表示

■4._export()
・numbersのダンプ文字列をパディング→表示
・AES-ECB暗号化→表示

■5._secret()
・numbers一覧に1337iがあったら、フラグを表示

以下の状況を作り、暗号を入手したら、星印の暗号ブロックを取り出す。

0123456789abcdef
{"10000000000 + ★
1337i": [1000000★
0000, 1337], "1
+ 1i": [1, 1], "★
100 + 100i": [10
0, 100]}PPPPPPPP★

取り出した暗号ブロックを以下の順に並べればよい。

0123456789abcdef
{"10000000000 + 
+ 1i": [1, 1], "
1337i": [1000000
0, 100]}

import socket

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(('imaginary.quals.beginners.seccon.jp', 1337))

im_numbers = [(10000000000, 1337), (1, 1), (100, 100)]

for im_num in im_numbers:
    data = recvuntil(s, '> ')
    print data + '1'
    s.sendall('1\n')
    re = str(im_num[0])
    im = str(im_num[1])
    data = recvuntil(s, '> ')
    print data + re
    s.sendall(re + '\n')
    data = recvuntil(s, '> ')
    print data + im
    s.sendall(im + '\n')

data = recvuntil(s, '> ')
print data + '4'
s.sendall('4\n')
data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data
enc = data.decode('hex')
print len(enc)

new_enc = (enc[:16] + enc[48:64] + enc[16:32] + enc[80:]).encode('hex')
data = recvuntil(s, '> ')
print data + '3'
s.sendall('3\n')
data = recvuntil(s, '> ')
print data + new_enc
s.sendall(new_enc + '\n')
data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '-' * 50 + '\n').rstrip()
print data
data = recvuntil(s, '-' * 50 + '\n').rstrip()
print data

data = recvuntil(s, '> ')
print data + '5'
s.sendall('5\n')
data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

Welcome to Secret IMAGINARY NUMBER Store!
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 10000000000
Imaginary part> 1337
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 1
Imaginary part> 1
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 100
Imaginary part> 100
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 4
{"10000000000 + 1337i": [10000000000, 1337], "1 + 1i": [1, 1], "100 + 100i": [100, 100]}
Exported:
e54884837e5c0ff5d78f65863c10af962a49fc4019c3b5747d3b8c655849bcd8b08f9fb9e87f357604d073668c66dc3979e462c995a4501631c7f1cdf8a1a2360d08e7159e40d7384a2f4c2690c78c21dae1dd7583814f94d85f26d5996c714e
96
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 3
Exported String> e54884837e5c0ff5d78f65863c10af9679e462c995a4501631c7f1cdf8a1a2362a49fc4019c3b5747d3b8c655849bcd8dae1dd7583814f94d85f26d5996c714e
Imported.
--------------------------------------------------
10000000000 + + 1i: (1, 1)
1337i: (10000000, 100)
--------------------------------------------------
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 5
Congratulations!
The flag is ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

Field_trip (crypto)

ナップザック暗号。LLLを使って復号する。

from Crypto.Util.number import long_to_bytes

def is_valid_vector(b):
    if b[0] != 0:
        return False
    for i, x in enumerate(b):
        if i != 0 and abs(x) != 1:
            return False

    return True

pub_key = [1627727230910376679190305250495462377673127325457772051463473603239280851247844857775094804468541458382943793317239787693930638537905012556126829098198853, 11390077915029058809550131014512708496324218365383793403681859478983277851788559377973666759678894435638593981031042225181697704452107123180828946159773515, 8179148350749291474514716907983121255146115753248586194447416551426945499482207275600097490935543753034574160607266468264368850157525750760264486882342004, 10941812031082272057798702874172927467797501065302416966001023128384698906928085390135010716098940533908593173515390255250462556662539593195364174183111378, 3614745341275480428658319936106342479447545475997102535381861144548202616710068200734103360803941309632252623075660097928171614636575252144104941167875823, 823178354506932008674641402551278888372261897630495965386060191754392263016108442664620321118524856044971184623847186758394463971043188530296897451771186, 6126448477839481210946440528787637248330004648968502621267179732866433426925983876878526325407025084527441161833253484921016836135453814544622972372789122, 7466110955532217718350434679985113267727029661150471938943244057893689660733974538173921362412025690616586611377720710981300593198085731197422760123486823, 8494763827840222748734700648979436004399105472251068803766808893440611752185480154140145100605542790978072404829682982969121103538123360622748789468463235, 11189720630530432372988722422207131896593163626212669159020725119617893436033981396794415249303994853786917522131094575897127888600143225647812363683556711, 1715148450280854136862317182605666023423823213970399964487054641958918804151884265498646179998842243400236338074592006759506277918874694729594147582035223, 5540431799313225600289987101975658390666115836842131612473239501357335750526216599306611213275093940185339830230979569745307094862150569297375944630143685, 6065288708774786746551562482382919833260656987958350973874133802701002919726540869583838838759287884702711861900261459529790522631020994523440533144502775, 7234486161196695664277498569820928727263659579862329533231742765775361673322113762206501017047056413054134570841827024859772736445100885511621826030636721, 5790466157587780811391418203868871988082506102567632509545303269169653572768191738557448523974150628231236540920327049499163032154806889411357922070960923, 614487011969781591950160360975242589085019947676643049152128264494968822101147186721613098402364118730615692871650144954496839040414405067974702421023905, 2278335646833352836053675691559323543806718574568397090218657707516163081796224967487437830189535674711866517339720796812479305160299543957122930902733680, 134879407361379889128094711300170056598390106523526115878191161673136372971584663792937617159109985222609270062841930765578765868002121297161450924875670, 9519287056894525158582578864977452979099306021811340603346876269211863740542948640369599220180050455648379571390554225127442591697808606219706674595426234, 8402285089367247619745011222681496327228844899382581802919813910782074703470238610758895365966927878107041275900491204851884282695630780037206677089073743, 5406457121320262339650448405765205909738170940504528472739736687195948514104117332533865686024659827591710796087546713263642562769582609048315709994928120, 3801142902357168548686125964812533589729813463183268403565815227989154972362571932731819983704767934865803934241215040857671291683075724662922338415917182, 5436947858801618770870878269048974285422847359285195936610682423767931295811884290027916455982229786770673284249525164815726004308812462166914799567512132, 3815052792278989714677334168820537877167491234877274326563177152219263932218376863319752340985935154603585067421571719480783708315218297849199545235122158, 7027654996878753275961749122684655552094983534693747937102146760033187963841168663352245494579053154889790710851894666675012966264073470852357878798185461, 1902120513092875903338226046347919002820646057582844141644280347474263924997621676201569803130224359726311851288100274056706312976734099927488849060865100, 11761048354354487182165243290860187512062141561289470397986167013898235429358707127696368115069038004916028536939325487876797540965691324574012326619996716, 9757529573128395073155274559294819779368946395358435204233094762544296369601908201919613288263346489553542399982377228944641012976067072706476767936937491, 2453946098113482646488949231406349598804639726542182990917700647199960018577504360015030201773257233191736013580250768440614299316063045659162111320187018, 9319706037803173583171999553640056770008389931059980211073835507260771807765054342788152787019226685278576061693822692868824482538539619437423931723867638, 2415898081000285885317495095869472168214386057550401076099272996668473089357177847144038836740891535925645870811083042646884362664103196192764729813731836, 6831371739629516878762522327702302241691133397282458321594420516244457682248807904681947662649834044913983745000847132408435191823193733626430289939177704, 8911487453444536593323920821809421883218471526912139746762963559650262957593522887117811194390719914863010957953813489075136297325877225195754168400092143, 10827165969679594628739062220054978610293037445161650396571452340162805594515879042614168001849163738612474327713960410907001062746512950632119899645486165, 704502156006234895839438994186203068165985741674000184830486957231155986311282679180631398966930213171517941820858545126492495344870861094407012184640823, 4290415868027081329996593194887552166008805715995986555372686051077953073250496320908121226211705000105956461168744315858180066368242874040891532657113169, 10545064273500469407002351635866768900216078230158001025925896743623392315718385811101431137913336305418674086955813416589952935610377379991777656464560904, 222038761397496749360785916329206840697038382632411616626840724191778442228487034550449387870944140465498765132320783016190199911880849496664880021486811, 1441186128607304956019821803029517117342542746331149661877318328445155144327519269434552605831697245827929704875263722242762828396110183771144964459394537, 6262035322760676455872259557860354851246503548034172638052912261395035948982118234312601487324050800839022328905285373880135361896745345697099469992851131, 4524184613244291795109754414667150818999629856838115549409097166729848395081524481473123941545320222662731732155390386071843025802825179816381298820729824, 5283966263613790830455133450578806522976393376747821388280595897660468710659040194781402893846259456267710256514673635793738636888433235312976117540997670, 734269568748111640052090946231180906652495087236442702545338576377208172123085276589342632556585327179776362520321678519591781841790141214498484270905176, 9451656806863570616172924236279721588970386798009311529339115014539046020513297990270343561908720603044124605812085133334217197137400578937155121179082520, 3051642371650657054700521038491519744705758620980094104902981323717627057520029747610177450175370083995813698968822095618298179968058178062764130608659423, 7138952449752237733780319852689997148652360533005590188952403508900689828377062768778919668480243722079246374005954390574613559146429228635500313866647830, 338855726414699556488111033893516095818452279804805254966111715246104055445804382690731870669031649972111753917285671926417016391990572580298041758371253, 9434338110989485656020470689018936204735538469042920590064694759331237737230785701304245293791165210985574378910680725501788497370867036347820422455861008, 11743357680578349359162842808973807055764041927045206000202223764225228589230152100644412242832121778126080931892859490461297768718139167127509484426935516, 10809477666198375316415855765052746110763351926084144990851771467019653102707561871201368035835499988211685995329231458471783072292334735121148934257474481, 8361290012462548161951254835930186683493837370922544617362025529237532210142924359445724137459698924851513253914440872353889163895924265960022186220544709, 9110331121231523509307877539206254496672950206166437894520019335519961179869340990239003361109383043974388021961851540679419112950782472645836218947069184, 10393081243233784801735338636405290390807650076446916623218248492311682427662136868388090954521461644084639834083277464607638024855738147795387101337574226, 8635144191933378357854933636265474571012056586049858041465470568749464263500256261392037808005866345720862774122069273582266436367817433458956532049780774, 4418352683953086382401924269854964217677896486679104773071252777228873262401683489714714052284264053149769016874563276933086640659387489800484854697533082, 11405236243645314277535277368602821528967628188171456747788000113810218023475667423693365373226884179614448925519215120109302962469860586286886119774049347, 2771015879550163030165657530654451086641677020792616747235577420773494369048734442366451848062127222028674614372620701644053503582161481006114727140581880, 9898040106597885401583759646390295107361734996622402136464938780239784598493749472168979827154809586241421519720993011993090134889937532355080074694914236, 5777113427214185313997366187449136632797879082988812318910143048720548368905732814341066506919809935796023024351923191808765189492249761422655292085807672, 629078785533612849316912686429345503590958550796433801577651410881398124391524995844450352946049732397726053930432847836219823262977515490137563736301854, 10801401295641411092684548694395594070024865629243283117987852161404597651908799260812686233176670601757986605943575400167658544559357084608391881834446315, 230070532084711979714073115090944140276333108429708057888154566997156763934572283796043255414920534623439966012683795418379115522344166096620802666822158, 2653141234649791159270555987752178497577182383710867439287180210805265047951979750613536416122211396079337182535060893836409041761200653941413783366601647, 9819385030911488229711423422290746871860893626170080234281491318242107780563809621339193314159985954076683835744606911808745839075685015953738930366461504, 10787755099446585851067558577389646651361480328446469420228814545570006340103348743933813554961768885774075313271971611985063086273746596057549133130286996, 10263252536258338191094138495727374812304043040018874292736338983366473600613438579330512622405111321614329014124397343691422153751941094425939148115419144, 8264896351960310713538344637075442139532971304017521357074393238425679130058257615139742072920826381868768043200623504461528962772634922574219204008611446, 2147098598151809758012396937896797587780500058011635682566222787994691651248284456431917338694337594118487127099227127261521149212812046027401283431626653, 835919714553401942404334437551365593064566099647192274874446759913634276581629201627681467376279981880841428500989955273531853693899249169333824801078750, 3137791999402738811435798454665497017869650524841428289369351443750201278747862575707706000714058324362992205288888567315278677490077727774835379088436006, 1349083629045995316048152731789283957044698996027937078185713363080897115381735648010571340344037922487894330206612400451771128607496786215899669980572631, 7151470156920468764362424494490172229163475650617111710841057240618925425354832625922496799292567847545183967966217669595274609257135294729383362095738774, 969214900808450132888751546918076429566821040071276149919254643349125098280414720732281136532422094620745562927599642733412626063657268885891539827291347, 6837332378607129931141030022171984123309503518721395037825344337090610567350813310712435580992877616537619887480522470873869606202135747709672130000907665, 8364995496256554616029977590294874242060213310040785018239136897992699511676399955908119484626044885062103507697132148339409250907597810483796867399165984, 11150349307177473530307176249702818877580126605366046220776402492478240524483158185915502079277290319184145846124682470893997182480458282506949040910499392, 1658289696192983790897943272438520487042075314752724083703126291291970666851342327974958388331127028328164897980277317490557958037865872463479747423524926, 9131362533429004401441350892122360841764586109487383276247013461128740601257141642707756754491618871428100079351302334977304105019443858133126184771545043, 9330397298855941369542973735462725696662687125148526787140181659060684716824505001027119473890099274372275476966877359227102525263938755962082724482518050, 10253738743836159588621071259178219022563765128400530571588761301542176945143921956862350468019119752368079008322471485199577898502308114141549691485328119, 11600594703900902422866629561800220560103998368093720941938164737980026015168964844534647856810134441227007791139257922310172433764469537384240765031240277, 2244615925157610777383156726581397246130116260122731876532858274705570510773554286422504200282490618833439009494062776847822891629410146208293931139019598, 9733004403706149967520978404543771261324511435667728541178207212979721154676382281225409760729300022193360065470568452825325123972934958237623605165978375, 254354500603048544344274289207513537562120915759345747274593609495132631100017756321505502767286130589730909912096517138306900867943453650871702051139820, 8370794524988243638695092359570003691661556745490662742148202903860415924783217755602807126418561604959238898020252625472585689205979031497593592055937411, 8794340191988240556017659906713384748965043778452355164633928970799666465022803989063363371175889737930849051628085913544959957566363686438835153843412939, 5332480590532842430323558618578543509309546254138522597994235482505696944206135906595816348986471057105575982103534851867035705911825105890554636399117959, 3950651369214765379669331091209846132473398609747032844881769499832818398279627204457821432880778469543121042120812033753781942045800062715602362551437446, 8764597745555787966301901389786365105087694140863727334245233470132110641169237259387203997461935069288656230569502194991969216616783525833400312149135717, 10893671311442357810344005102450557175906931304022699347689646165105262580304776183017675980891676148589951193879822475240682617753093939204073908090934123, 9279851910251720350566986284138542667714345125643347097239195337905126099452241423018671935749811042002501428789486379723371928823690546158499167561377363, 7467311785687010437555773880658735452282769858571517461749051862992815684658577766003123130545826154620513903602757430481744043605817836120355235645161971, 5108725545796520008985875560900754734992617221769641586339788732236758184078757049778190729232684046606028473386534748941226434872542329986204159374865318, 11867699353985069790536624225866578465253057547038747367192323201103495572410886289392307344367210629571626846502738311475794548637804314691361883633660854, 3307955753584481516914855590837996820524452980430232447056686239509247300748140903481811349702734702088092190468590865868219632872299773637242697461456553, 10198102385245501857792898248520943901262126311232584209734399129163853603686024999279049967928201510400871689285418724239616764378384016527780204413216674, 8228299095729026478677409017032361626919004386605335618535716218424202290478453122140182082896822897053196677144530584164608155945616171423914566350006168, 5112786368092391279903606929743330066336471986263730056133931970470350367734928619591357871627106533582770983308703750603891628446704447489958729107713715, 10469735493230359064821542968197039289870670760006858877107911033538981312661996508702709711101453750156345711233887576764596618880116679535070758686367835, 9196198524335526563875694798089709262412006598320807967509365313289345737999012223767852725432769548784378062829358869705294718633979410353031005678221802, 6683277380933096532362852252484564886247729619973370408526339212096381484171620318859617374568197001310631889191807697663323642106913958849690224925461694, 9529613981769374073447341366884871937833846177760706872163980387662932372533823749575103833419092123484129940660046036074238463645988110467224610841798396, 2266794669069907087687293539109983357111262788594707965340396512153714241039180932421689734859164235712168843370543545431747673801363827867496870372125336, 1866657295458158454881522810715564591136349581564835527057025586296173873670918151349885379247546649061814138440749434231115994040006915887222214832216793, 9148338051604628974249176335472004157326441570701111334833644249222513670344916886670861683334321358810579899657217206257613558265823876085505454588007968, 3150970195117521652874271187992011688081846017889819628953971423349119288736936005559152214262722455740251518841347209225787560336272283302792820677155456, 2654815978280349195745421700490321540189264095484815485625765415487938591288435811537239820689235000000161324407221020096227903798822533164408384845279219, 10613712470437968081140979473098189731268139640670987306626304368616232817231479865616941989006606100283262512680880271451166161316286745812304949833618532, 584771700542193176410575206781719730381455972184594687314858310873745548037581699189913439808225843016877940196620523275735084018626160581660280994642977, 7752227206782612731330946605694126516789657852557775310044628700046190614760547318085553165126745983752673912673179603938501945102414356429679923126279635, 6181114125680462568335637321427121237211288385454147219539532450576260468665546332121469615286892296528834796051391696892578291511969538036639317451275393, 9135050673473900291782130971149267435204316475664597051965244543275596770270798810469766060093645817494350474433396115526366874458378951375630266775342673, 10823484837094701160540558686227927842943057819522139544135134044387262556730658594806349353577086449873005218586065819838718307881055159834974985844681301, 9983072533960933746418223838369711407232082297937881132317170649759456192810500555555337035974971942717934370671547654549936811199706777826630199849997893, 9496860292179603670920445704807780801671759827403400028732735007396868161785125605066594722355616018953537321578676302542059539384517799908274423326672419, 1703385660623950359050969801655519572699157230875334655419427425211519057467450009673619270811656302454948012601207060423808873812556848095400818203864, 1124824934298417769296957031482302153675496794359839176778073940948277366770010987547411988487713939288525606195470668176368430409031376391243742928188737, 3229481917557768819829086515377643522962590749891024608854142700316113763497423916549064184792610168714433142930480984048981188717417434429561511671863340, 8294104032436327777486159971264402767334649287841961190030297139466131416369517365641129837491598616986084921647405266807970727164692073754656655602529261, 10841558702848626512201447043784390704658214933053467482697472164169627348933072901533434861934797167954203691251466593055982136720490185778511573725463091, 3178930784687138843088596584997903179579922587867410882667347234930875487458734591193687966659517370268916417823125671401884196339836390571169682168714634, 7454151195962571505291413229201537150280824884428852910895643182678249719784935336643779191181482778848818993208221255258132534583411781119205078130090493, 2015156865486836120778682378960560170098671955237858754748152131638573845290736893280308181218687853014604174145816633360273506979314685066746558185772213, 7518280147605752377356085467400615547824826179564770315069235526007505409683817948956679988243512932507522237221929606038316891387806953147114552195723037, 2024819075929565623167333132137655283846300903116425428839619347379614001726638635657985601976090872185635173118822397894048579095835679930797308966510161, 6215993704628241793832033783162789293924516338030608992171516163123272062860326445636293235015378684705933988212973591046212191958652259015996841348525233, 10721074643733864954970318017687419861549782195881708432332255884413370619291750997381857646366632973722794738669419561902209255528214363399300572318598976, 11051099778413936201588813479333950625696456591449077944829525186174150306810041964709311295480133149976157065280899311313708649194744567649855692630214364, 1688310516465382129824706766300320323086828782213510237597315430363470883127564821837914550530086658434882374985922949368294443247364921794573340486906238, 3192364479471168028710837283899918625935362325330335301033556406770563105461096419504116373286876626652315031493543268384008485267512339959435053933841313, 10572194847482440812332986591051630462883201860708366563698662854481883222498284684687782612499400666528966898408853346133591660937905688329633621416854553, 3947736123018809396047345259826555348314283757126565484195977099646537310353904000152697460719528310696082204835098702895122864267256319395558913520116392, 11182766638391936877995854197520085129151384977709217790829422656082419193097932980148237939707803168327610358370853571892812158944282257498680855767229677, 3785005419673190260210131419611296437580991153996528806706953071932484677468263744891384933085989064774778069519276028906778427000799962507340099134917935, 5080917081750594708323405365145453207238012111759111382500875071859284459953169985334929889554817530710648209427731938198054042780871188922340543142924939, 4048618658491596677603187303911377706030641697591465631347400097836527581077675625158162761353955215178164330226108795767011183973412955473474219799087197, 10756640002316419897851435267941668380681904604159814743578516612294764433749019434802471420890142162949979364053015555721098798895592890837753394402601600, 9576566069431525883762715341983732560085629671089897559307942342017237423144442133049657728319197511124149519512976698322385517896297503762943044451831682, 7165568955290222509156785556616132982441722968221047749287853532522706162989495783845174854505888062434423314563689608447591958198763443599582520354403262, 4886305788841254495561906932817366567996456189096683440102055315067086182866905742486434971809212556403255604320990070575999450589283865669827032247378026, 7974570179507384046793957867326714371457957470114044411785079610018843160599140562038134667373750144719208045822373607909523650049764790454624533560094438, 4699399884541021847518656224539601167184097708756378716924596672912033629859806682769146527434005646171138846377909985611374237928982199839841484034595124, 284699436285137586151623117958887854384067390251467180741921703094848380911015079304006363413374407709029807303242873481239873129968266824381074061576781, 7424603511991768566970306812540965037304046015506639020124822754523996481221874622779988256386434795599778401964853467233299073228923733026307559753461753, 10204802163769309817146573619091345092885022518990654924014656950712859972992223551924164346235264566717972681978724897809251721761375877244325753782176857, 9438420831957673445603305728093735430853841298036258989011836327310515846466591187953907621823894906525289199249629125784422458200828675239244266235272346, 10890020912636917421687599720986965506018026168566001306712363618691959621006154914816267736938077225993112076739368505752571167457735320815453253378863503, 7612905558494937122786907665601018921881673472453283960241071713931932464659066013897727134859798086411171769879216045995689241333798042462244230212212984, 6550836530141701911622212575637172610040961303781916329326618809093764882252631974098246519703546676024381344519501504247292099463026478299004729842120794, 810463246670448806288456723577253991309434245269230870268065162161683791423034382984779736398143238385314386270683813736785640795616980760740211633626680, 7987182793636123387405676060009070849539867837366546908532424481956731048800366776798314558709408103425915728898034756937642304986810890072970609409560920, 7214351975158893076759227293921988348242566545977916782340607663706728189002123227844454484007467068046595059915519900187040379326564702309329878614144193, 11014878924638095287994257524709668434779725530794695530401129023156413550436897097358726050238680106826431375584530778605250124880702844280402008225394872, 6027887507568715893917001583622263960984925990340905403518345783740595181396031310602841240588909634580493242079149694551634238251017289222201905339455410, 416347896819517370094008870355298145260975680342177838528189406107683995143464927834127034596304824694484130253280370972827705469927428341950098126774907, 11163457967473117384909170091800080756098465652817504823829957246101519582406623920562879665741186067843806160145308672039236647314452825448974599553726514, 9053783100187331404171412931836385824515184111948767809413867380276679820649936390889334178130847227206809033839795986237398002538596094506862090790079370, 9819981805416004420939228090848428270273275315135728420672592580587456849727183520386676637280961225785470170028563422457684520710033836815957352641076656, 9099422152831608846445523884690686488729801810193179742928892208927495088869678721490572756945304623223593124143301850937075818103925239158419916092455832, 4423577950698286460626059676874777666863173105923291070406075608137350484265775306538076488967427903876263455370640828955831433683427915837489787681571104, 8756602113276572584327515563541785021885156596606825926384196017746588797560380054132379478133281808160622488923734499010823093056004931483459821079878584, 333126719900068218649984650898276581721876314324829547579365535415969541796750123020026055084245123391225191139147600319762747033880097952001528586613619, 7369702367521762727060275952126910129673008169982509956632808176742772738596846920777046904811187475688291150543995266534651134952974656031439986139640279, 2082799199108465498916580083784704029374798612211554268896160342266763106031569342542856087063877321514991732991254030062209651901743851475358154981091336, 8372258715871921984711084318371475306529362956110229335731717773030170640559593876258151246392797433258993127356247484151533876227372092507704978818762299, 11363939608613542162316118345022960798510877466323811731267325707620939632567030190215087390814765739175622571243027333413495842968402118709843171345209057, 3369719356483561545444940792209404189671394809909673685150113895593885526741601117980579861293222360031506015395948410107943057618465847851857629017021337, 3891507040973395370891557095282687378471080702589144672203318739556917713281013957214254764662956395750402238983505175330658129247692117209748428646988979, 4841437298113170733673811622315491999860260018197250450712753745063206624775276093082643398955242651840094676440631824725064149754775763109535437072598329, 5285163136257383594317771821481380172518348255388334236768828515368456565257150986678782783096670986106218219974638745661030434504183981097992990683389834, 7244116929896986409152403472296524576447775663505970094108789986102399989798939651538136211134583253147368128866311176849015387662060018429204373203882917, 7148506525887590405588915139400704234523641207593915972629337111053532230604043569291551513966362985886466513012302064587708085238549323074532238261929105, 9963569892216434098358658807251534860655159021141499917379945920250313978770919657650973084221026686207963270148354989236871921037008125320635811012429562, 4083231038473288903981795364527141098698470950916969669140777386661810905824053818094335667187521576982089894722121785936689098719720641047141775887885619, 2783788314467957767626366294911171310778689255399742535622249802506963607071489599250401846151948395505808426552847045942384003413532965612237381621803281, 9480491617103309579842630556508755350939077789372196051463181228494854894713982210404024973543443376963252760676054552352172548702910903277458343177156566, 3635429364237267158097629083423075371334216134912102395399443587668365674217468957824903594013330904699195406402865693233751839584364352027341368755854935, 10512981667787343474434123766399499997477931436681258061313671140829123476643229877218327020307534330562667672313170203756349669502382157014339683250964247, 9523260882926982368319161046924327498415945065442619931245103165210783676690576930491155298561540325169832005257298960723638671214008183533978109799943226, 8821529840762200230987342601372713314571576667046848202753835140978481743059025729341547664906327089784889179309805528352373783300015409440694498526802453, 3889011833429464584665382058129163296830025770986703817534403311481298622682949913268185847076341119959231106603819499559066684839808723190986345797294730, 6297833894994750508332367344339230109576795350737018003925458747380227258991762309042244773127464626474655334235127595180446112677686417583728900997000407, 1760580993763018538952442776136678506892159758376177668343574661932032517138571264664041285910343183567929592789229684581190582868840885043494028059145548, 1878349075050149698900567649931858097059976052165743708683218061733003305198473269136227375120889463183154947939758601333339524877223521121998759362189694, 1153881028955172548796413995891509447158808154001092914831702555572321224472153757269063442351457270745992276168611327881189379302990513606066403785037397, 1354358223850339886669589906081771646741444582933245990266741503788401468880301111475162932826849753299053269048808168611803883992487116859632452934337117, 2543377884923981424206502982559952756662944312446884306172193873371281396271026877421637622091903368826348654608641732603862340627036661889590442947531927, 11180070331634863421659326942954695855354411135806527591627639434182163636572574833713806184536037752699260808146541362264028865594295761466526576972822841, 1876044157639270095152731171181080065397794949339134253513517014818122966068827775030685216937939154007734964960492393433966781954313208696759345941096572, 10371430099994185472204699548408748044905813408067850241238238375805107275941350946511274188710313819596480556092765947208731899524618164738003278717300827, 11062773114779865261456167102313685917798343978846196446106343403832714394829785645472593554347810116685987941912922522999627132764032557020449831422203646, 10054072863070251371743882375307803093121932615191109140649824301459981488908599582245204018730319415235637278900632334082353686886849433443418405120003345, 11899130436532794506852251375418519516682965538478411626134165694080477666467891621837514385290629527954317340066073791969068384836623478676900518078492144, 3800279300556347862463102798984354928617374220518396876660726722145475720924549768399286700699390419995192400567218086102399360340221316874256916817269786, 1454947148349065856463673503402856502963580434612167600249860095631651888047663819039861980434456089663660230397115050479224033897345798648510977653561999, 2042470330662475573678989377098661429766022525672425312136276901388618218130280731245706624788119897930174958967595406027605059992960882778388524742722706, 1234466316196775376839414369545576872418957414559143172775038206383525000927730516952675718815486990989447248421995842318819533894488233801079449620739194, 9271029179787872970578591499796305060434913207434694840381590014888853464622436665409168097643583816031775853388603609072558269628091676020362129748533199, 4774006049363181543707013424043619624722110752475263766809952707315716132555412365539258234954892899737076119368604420130439903122534513533911949833743235, 623110557039911730730761834817043413841225662260405544713333348288325346206246696815306384870033925067051567408116233686600986656157873843902741673267719, 2069564772459439803719938786548180498693262686543372238863965419552080267984035520909550576789640672747255124939459370750757373319167495387965403174747875, 7009930087547627207463341159618322389574790808227199206178856629902591585272159790554326172427287447472376543486549214941749592725452858178087430338966770, 1949579642601550445176938316267401962008340575271606619055456197313569922910186952978532646082714333411065815595963623697989602613867680323849962329445328, 11473102336200916747844954216116155097772201756920091057358990979985199603080222884336057264448248212309791104537148189404198070915699582464690841703029405, 1149619512535738601211196767922880108257082979896142736945084581216263253245359015735818442104694183806457438676420946219043390360617857622541114743356625, 2728451593413071164353755775705571417160504975979542074503589190184105228575509775437861194810114128293804518550015503478674215376973558551801959937646423, 7348551730526134269844474344843320874593220152077150721293689908105376303123526293549457485523388054871559487100009886469120877549640875229125679910062900, 3980652757335090376997966895588998245582192975449382011909532268728853465365643067981211212812543763607316362585146788052930930128811388536930969342059979, 6027435835414897879227982281610804883898257447430395373655482693982905460207165696577025993816548891414301115457107032212880895723138070720653764226458649, 4935176743833633453254610852208777179108847720614483842026980697614902097198030677572108382421721697955784940692357115100326157600867058374344306754345335, 11380188380193543686552603209635990889129830058847840211484047666443921358239983121578443798338622961931123079081312386043081771886474890372630867350934523, 302987216748498327772215483663698180358086916475422751109337904686429747813576273027596185544180584711869887380062832681724092251772710838738355782182450, 811143629811997853354681978704899746490333224184384674857937414780703218886854529258709525197480284388948037380964255401025910568649894324446856632636592, 1912197174748050506709090151289853815332962565872780585712134602155119195678387971652769864474405775662028797382605103443081542911360430369860062463563893, 7291021864361814150510118731044864385204363543462889467753348110602838791870962501076106462997795429050059428094480878740697465713025274178808092567542212, 10470454741786470619594017615965958273332950307267197723934552764686005671405407576286379932688897606971338908824726882615845921705580372546409941175331037, 10181553581483434681781949968008741740061264764289389453230798650897899608022705896680919782100794147183000150901376195723151791411050033951290283786019977, 4258448968850182298881050787339455844058983218447958438955469542872009797484665292406639737321421521390721898187715427947024660792416519473288140642795272, 665126950818270052200683167429361468415424104577516367369570410295667254789977695909839338561441230603199269238113935924286711971526139364836371465706219, 5778603245576121661625744968094217982871142011195728227336698796177623583983932093421170892589521281377735094971545437150524492567792401307382096969659571, 9041169568361270824631079916805143667485107440403819673118982324331196605243710736252243694585470054722017092703832685314107118663876738553603881090379765, 8431011838980342769799616288411243768347548689119233157208349141492002200386542305507576767212556262869263553150643023836392407323405139253427329269366753, 8553706268926206579355730973791660092353863784751509372422644440790878753983928717623545538807559356829947772453965617876985508934310354104621043687587875, 6085701268163349706176631571460435367494457139886003603182612764217346443544862940087286859921717077555924920693652181971614741028158787295175507903805498, 8258027474231127629757419236092115748878321896277358390666269357460217304432166604893188156062734768320200621455881016473474077406349529408491337579070619, 217331193100935107368229358299722097535960890408924136554062054994468178500442930497503537444463416350072629320109394984373121597844999496670174734623901, 2615530940468368976430415020232745908496491487732778845358342691984855337966644151086347954705207248347432846086811344429509626971772151674138828479034407, 9960118652490492442626264557722940366236550945756405929154467678797068007119691196073161215135625171292061966393931591117075379707418718493207613281734128, 11883479956336240751620508565956647791575906464658043904847102787653384413540737438954113122506827116919889512801006983398795266218225358709015970474796209, 6152285147387893134308305627413716697035724893956326980324894196703036047676192332607132054448632203410660151536148743152836146945863580679445515576633313, 3087204177300702725903801544645938527062384514542059207838072215532344688679150676602943592074143292505943525492596313110869017003113441178426953737136320, 3757237385014563017951360020497685657808716037369726973798008159647192565347911506203832144238975399303316833405799994094392890515318875781045298318308651, 4174290778215893394677957264252893474678237242610027055294712957192373957647857206677916027186240373718927301908828095938016364127818908516883960408679053, 3748803300372512770866385104654922154470904205965026771319291886728164245927197518590781953321238268806575463481225816414707349949847056384636893007457721, 8034791604871081754393742620809047036249538255482307958153762277184366357510690505406748023739482129037447179804389566282826743874110772660769989993214140, 3647010606069854412551850026099222166287473701386238939796403152511252931742239857496752497988938568540423402614995772990646648482450299155961694607003150, 7806003716386838238944347755133023427857127411524200971653891977428639559902033732325074590574245675288515664031976582135757036821962959301244591185185836, 562123165970750916018523521274665280554207579150705704505991893938951905226252420500731924279293805682202106917135997949779952378356926548090996464183261, 10017225347599062251185778825601433952376955965940785104804810153710575101527601556073680944735221687545673318069762612385520657594749285103779943556203859, 11034121495368102793824149104460238045159050590264281508159716286752391769866225931653206949515929308837443453281068270892449202454489663082251103597579414, 1393756984740491625980042801423925923652694124513215825983448770637319821986725266222696274322782094225350417979883496797845297892870351570641796736429365, 3894233430764171021978166251097684223603711526228678617083090942307219791681305224470393733859806270321706191768448575635613494955972821171942019155576022, 5038527951098793046808059643802686028797058725403977118364390586086699770072322326201266880837915838731709376700104758344376656110092506598359671395752201, 9060876869828818448898852928359252910511417178029126609685283138824053964178895354434001568085161220224819591618740459295638904077934235248948941835465621, 1213284553098562533791961352335340028855774866108118873722749495214290050781676187996449060540282711962596299780371703456279525985966066640468482695387037, 9458104547506301061680450860449196327062010922531182109678643885802054328886528832025671540545677869267828858508683156236410816570296275103437238768105346, 10040054309381342148323598117554716384177326501952268974305486266186254782754797649740498654297024089530806441993039549600316509292085634401892126157777725, 2276927462611754797775080537543333252522721301228205773464099348201834053373985987075600025798802656981615274790492592630699705223288330490059041063861371, 11556387618265616484447806363024761014562917993396940861921977454240032115257066203918497109784248023494996743861411413922697151976403744004551897333587419, 9889259553854405678741508034426455964451772337345174356626295292298205602394952451135449468310970347202594428138122580204423010430923553611754754581066813, 7868119367862772149704911491499473892301419246641480987785226518125812257513053330287476237691301677750429689882087996945744571488509040895507410804183873, 11508002714196611606395235648239725836815494703321432338230737422973329400113158960696048138066722457604799065695576108785835121800314850011501948179743038, 10619053976801844838774915437764267913028709258001605358060442557707903258319114013374183185245387748828857617374056519624892149856249176171314055188176610, 201114180079927977316442203939901331713590891511639359168566794984727753167419382266922071288806881033628450144449718352186865225718313149653818834069046, 2190019323352646788039891107369737594638195699052572482340522786006963164742529768845844542244804881489436879523607337606022137474264008443779753796524324, 8994078524243073711186983175744445990617668670221279088217344780392324816856868718135841406968011026331111428134944981275543409823808438028673340180600361, 6533284532224150900776455616895133851200922713727543406843945334153660021579927964092546898761699064888593901931845363003227384361960946837683468780536186, 2900049820355985276596651350970201641910754953548208005611546296295010850954727597768565027123529585734943900449339351229077414389982399805851238537614728, 1005880173354315818215910490344169033790331192510294503391908220666556408162907870924876819721045548763740285934029434904116009033147300587812755020644144, 4429054545144565886236734238945768223549483534284407724097387393750175064863874353898699526770177337528927941471007913087408339512025427531471222352188598, 1285938780473331065877152772696342220861565553509736020905508189616388274844286113355903326372890919435684927488271321733483666403913781504709399179873478, 4159150342515004345261144815031223818657482125521340153877247384204372764658422497390807502845508068305611676258953299381534589394265725368949773437475664, 6576053057257377078820906137528289451395389785096859241738114487306122040955968123160457777083015623663591073050698149441279744926252972821085393074005333, 1378738974519907914149249225442590530115602428508531939708952252356105515635440550944988163800986109078848963934554394890364246215667532562795230121599389, 7530997786399165063460850133858426260366809458237917996971974273555406375229986518119701973615401731228222820028200964035186619721317616016026502478833825, 11371420348305380659910667615045099750167009510608284140696036190712641050353322760033584623633845930207049409269889108127939128060387804390620146397391005, 1406722966782959654726752002298837227734989674210304975712947321382221136256184622554373120305519551329471835182546103526035414290130221817761536912957815, 5758051768032037692984394788957178321113409313718798728174793963781211431894591306550233406904077870173730087305011890560525061122641038861810843224356132, 8375592464786617292066912032437580000072737070264996613521303068301506481293691262141521386631735548118808483692010811823373696054502206285565746271896624, 9625907624488495507256482396243781284122158414224512296964826016170998792851176860574572431609386683318175698871706280650379052753758050216492793527676711, 6077121672943640395277987812076880734154021482921918507769764026301498404990781416398855464804098928307277904801175596028922879606596629086997501055486057, 10938317339216777969309005338771442572315779569919804097449082853678275737846462681571834649938887549054815344340466436822987440964989371612298886307178807, 10266683373756264194186447415036327152615834323531488817490014686098650065547689251785469369732777946066207328196236032745636606950149996263882005409859068, 8427162246188488278348961620437187641769838216136551139544284534863388602834144470655144389658677000026573199236022413391175268573166429748835445411482658, 5717464833792973913319562092059026311110221447664287634460947091552289507231429020487445388817891744834227397036749333830249281129481189357590616693269535, 6388818019678030249042408529039004378409245276686402664154657767440109416203769306619383018656924981215056511384850552069151122129846170533781262522748912, 8058907696340647071107754590699635637331185362322234472755551469964443477794313636568312465633167061469262463754899612550256454461142900371675688057900157, 2650747991231745389958958911304551569853139256346350929307683312550450872545634238374819072544315331311085466011529241531384249952089342273098825176365572, 1795582396480470137527176284050645710132884527117486543781042591101197373917145734791679886383698097545356710330294515054344795103981124797423720912065788, 3052494597227398062986766578785396078205343919129668957958403133104993465160270251274373731365131485657799744057254790666584712327793616306716481909813582, 10125274627175346533926610345531381215155487891981319401506773913530942967488666544216346832250066513931463806744742351603339791989023259173734707387511997, 4905680337396302183882293200926552057123452464915594706482473859546742047185066973667304120028692253252104621914547092876701216499304788257812361954677824, 6788406585087459374008868766038523502662818879678483645630850915173078456811145138541048171988301388863438344097400187657040868535924005858978037488288657, 7987535346230340897650689272410982431583013895248851443363614799158842046321593827278953603690586270590653576153599776704899221489125881490179734913546180, 8668917726517583777868824898842831799933140622366155997499295528164949892618224804058794268889856672657589162182942581708183617533722037397902258002530895, 9655881640658079998109185276195348247028848976437592393891872239361101495373466311759967129786284249009503363294866452781555176175074514406596570855032885, 2243254436239103264649148279923978439297113563084946410869285186376198427685827681488062426734892419878174177945847856801922284074524600494618385520306773, 1370395445224087129252981159080973354642721975377684037523867648255769044694663959614655088192001525836838035825117690852844390101675187401512396538329654, 4656356018264588713126970771096540938860534429248562594457229986461965010462394518948976087164472484086375527533066794826178852068228773967304732965776642, 399595104452867236939487452774442870382730185220898620972098982860940846257358797206676225999483077781771650287888749325035861259261575979039839692262492, 6713094317103593591035416401288016658374527895040216154450781797709219652499792405003768632192355326331160459215694094704931391013755418496926953624700285, 1355018836283025742708846544067619719808654650957172598457945625126225415187893386450296522915846040605946952638451856428941453174991662324580099164411759, 8507312388193815039448605936770163526583300978792064893979853487224838987061551285368575763268148426788906220831176609730056029700392843807931184213757186, 2390915763452094063824684068272365759171848406604147217738985384144180505204991956237689281338506240218745984753955055494680218520622041831641785650384604, 5078775779350968152334228179925283860790974436015640731121894535584508877508449803458104048591112435333313257450614663322502851401769525184404429846816662, 1425564122989501182786990586943993793473032764333069827246235450438848390559886137108308116686220076822910325740852447268122991165884941809370496785162762, 3241557185717009458583866491496790535555873425192682369967408484532454523143616622825602173631183439057048896614677331862355583135778598344467632239621265, 11153886486498005363601960922463467341760192139357482824612504299845068740009509797094949564531439906328941599335110459532334944225340180499338091922473414, 4750339554868896196047869851866222454424215998958859589162250220636186354219417775182461279765710413851720284554693629603182622333067705806099109845670979, 3931689678588961771487503092252686799044554895341999274823183685441609027829749616204909660105256179107533811726668939651921392965108014523612326438454763, 11187638131483583043295930937674327604068710567565996413543552914014991119808667664531916767958198065684486668485361079752275150252491497563209373369489026, 7951154730710536892216170200330921561976344676074745084927394513732709335427919379562575393123463516219422246176438982950570737516171571233794420196666886, 1672105185912794004124818038268311924305321636283766784591904708276129195324814049081791432685559117731983780119720703133146952521104542489075767958624517, 5961298351722930109958690694504209488357119642165137305859737050609557432218480991926525556188466406512020308464626017185419266848018117342271389200068990, 2614791092577719712081127427916398870473955060880008274836166534656201118982263931935400058828969825633552149733933209355913619475322640831081073991096019, 7585989640990063110599210948433357802190782090362288612653066977287873913659636348347931158157250612988653924395845263983389111801086659635847485205155792, 4431808088762149440258933713632651937723965113354466368892895978425300447231680836376644074059558059224711681073893610493216931561336057461872809335815419, 7803424065303659891769090326828845084396802995889011459387130902032712116540019926662218626165288561308869447406929573895286984344209221478683590810037836, 11333465632518722706044944069452368469429296564009722650087924377614457953420253199332209735022605809814036297664863446336960387614479076573269329031750987, 9015046896873406255435786931788379566338694649982989302643634589663708173842716795343443511577662905506449004999936754531825070165614729532129356052128575, 11605497784351360234525700004313542522479606465344927573861628615111353117631482629714381940820675064966051516229437449884465509791106407640656382300239363, 3618112506546716532317705417297714426926133719388251635042604657890418824749256430743547870156065078623067964196242241099881802766943775618184489388984614, 2961952780271618644341511265207741924062876582075139491069703688326317506273106501877576791814338926919371801113717337612487657355874282727562430403186215, 1959860827301876193534452473130565833580576931994622570402458534809572211163546248253809832512083364950948854715506995993724605349255618000388575898620819, 9522502213326349795872611375564340926065360170250620972307193996920225151270140085190219961878238320516211124175040938476084033356336641564459714925394556, 6822893241651652944802867129943790227179941374865599671130155956732332020891862363512840518812230889010452540282244203720602490116223523996809092557679690, 6857422579671283864309505737866570751014092920497487113429028085441724197811232340915656160313885768238889308579776669697849014732800696848033650297379889, 4018143097421566596818458699109838662675933060812340723092984957628021473520663072311941893877060261979047503976803401869798199151609532367574647600368003, 6194607058501590733164566924844005093710661715500276174295952934514177124661068706559499237499314609830082367219229089919247640185368549101514384767175538]
cipher = 1010137180395931262752398681857488526009620802401167859543237801022630704004744078316133982172587856565491470015404484864890095896964409269987597733836611756

matrix_size = len(pub_key) + 1
m_list = [
    [0 for _ in range(matrix_size)] for _ in range(matrix_size)
]

for i in range(matrix_size - 1):
    m_list[i][0] = pub_key[i]
    m_list[i][i+1] = 2
    m_list[matrix_size - 1][i+1] = -1

flag = ''
m_list[matrix_size - 1][0] = -cipher

llled = Matrix(ZZ, m_list).LLL()

flag_vecs = []
for basis in llled:
    if is_valid_vector(basis):
        flag_vecs.append(basis)

for v in flag_vecs:
    m = ''
    for _bit in reversed(v[1:]):
        c = ("1" if _bit == 1 else "0")
        m = c + m
    flag += long_to_bytes(int(m, 2))

print flag

ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}

DCTF 2021 Writeup

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

Sanity Check (Welcome 50)

トップページのSANITY CHECKのエリアにフラグが書いてあった。

dctf{welc0m3_t0_dCTF}

Dragon (Misc 100)

StegSolveで開き、Blue plane 0を見ると、フラグが書いてあった。

dctf{N0w_Y0u_s3e_m3}

Don't let it run (Misc 100)

PDF Stream Dumperで開くと、Object 3にJavaScriptが書いてある。

<<
	
	/Type /Action
	/S /JavaScript
	/JS var _0x4ac9=['663aCYhYK','9qwaGGO','log','1PtCftm','1068uRYmqT','dctf{pdf_1nj3ct3d}','768577jhhsbr','717342hAzOOQ','722513PAXCbh','833989PQKiti','1447863RVcnTo','125353VtkXUG'];(function(_0x3b1f6b,_0x1ad8b7){var _0x566ee2=_0x5347;while(!![]){try{var _0x2750a5=parseInt(_0x566ee2(0x16e))+-parseInt(_0x566ee2(0x16d))+parseInt(_0x566ee2(0x16c))+-parseInt(_0x566ee2(0x173))*-parseInt(_0x566ee2(0x171))+parseInt(_0x566ee2(0x172))*-parseInt(_0x566ee2(0x16a))+parseInt(_0x566ee2(0x16f))*parseInt(_0x566ee2(0x175))+-parseInt(_0x566ee2(0x170));if(_0x2750a5===_0x1ad8b7)break;else _0x3b1f6b['push'](_0x3b1f6b['shift']());}catch(_0x5764a4){_0x3b1f6b['push'](_0x3b1f6b['shift']());}}}(_0x4ac9,0x8d97f));function _0xa(){var _0x3c6d20=_0x5347;console[_0x3c6d20(0x174)](_0x3c6d20(0x16b));}var a='bkpodntjcopsymlxeiwhonstykxsrpzy',b='exrbspqqustnzqriulizpeeexwqsofmw';_0xb(a,b);function _0x5347(_0x37de35,_0x19ac26){_0x37de35=_0x37de35-0x16a;var _0x4ac9ea=_0x4ac9[_0x37de35];return _0x4ac9ea;}function _0xb(_0x39b3ee,_0xfae543){var _0x259923=_0x39b3ee+_0xfae543;_0xa();}

>>

このスクリプトをChromeのデベロッパーツールのConsoleで実行する。

dctf{pdf_1nj3ct3d}

Hidden message (Misc 100)

$ zsteg fri.png 
b1,rgb,lsb,xy       .. text: "dctf{sTeg0noGr4Phy_101}"
b3,g,lsb,xy         .. text: "I@4I)$Xl"
b3,abgr,msb,xy      .. text: "v\rWv)WvM"
b4,r,lsb,xy         .. text: "\nfb@DHfBHH"
b4,r,msb,xy         .. text: "E`@Q'g3@D@tr"
b4,g,msb,xy         .. text: "ND@&B$rp"
b4,b,lsb,xy         .. text: "D\"$ \"\"\"$bN"
b4,b,msb,xy         .. text: "DDD$Fr0U3p@f"
b4,rgb,lsb,xy       .. text: "HDd(\"b(Dd\""
b4,rgb,msb,xy       .. text: "GpD@FdD#"
b4,bgr,lsb,xy       .. text: "H$b(\"dH$`"
b4,bgr,msb,xy       .. text: "t@@DFd$#"
b4,rgba,lsb,xy      .. text: "`OP/S/b/b?"
b4,abgr,msb,xy      .. text: "O@OdOdO2/"

dctf{sTeg0noGr4Phy_101}

Bell (Reverse 100)

Ghidraでデコンパイルする。

undefined8 main(void)

{
  int iVar1;
  uint uVar2;
  time_t tVar3;
  
  tVar3 = time((time_t *)0x0);
  srand((uint)tVar3);
  iVar1 = rand();
  uVar2 = iVar1 % 5 + 8;
  printf("%d\n",(ulong)uVar2);
  process(uVar2);
  return 0;
}

undefined8 process(int param_1)

{
  long lVar1;
  bool bVar2;
  long lVar3;
  long in_FS_OFFSET;
  int local_24;
  long local_20;
  
  lVar1 = *(long *)(in_FS_OFFSET + 0x28);
  bVar2 = true;
  local_24 = 1;
  while (local_24 <= param_1) {
    lVar3 = triangle(param_1,local_24,local_24);
    __isoc99_scanf();
    if (lVar3 != local_20) {
      bVar2 = false;
    }
    local_24 = local_24 + 1;
  }
  if (bVar2) {
    system("cat flag.txt");
  }
  else {
    puts("Better luck next time.");
  }
  if (lVar1 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

long triangle(int param_1,int param_2)

{
  long lVar1;
  long lVar2;
  
  if (param_1 < param_2) {
    lVar1 = 0;
  }
  else {
    if ((param_1 == 1) && (param_2 == 1)) {
      lVar1 = 1;
    }
    else {
      if (param_2 == 1) {
        lVar1 = triangle(param_1 + -1,param_1 + -1,param_1 + -1);
      }
      else {
        lVar2 = triangle(param_1,param_2 + -1,param_2 + -1);
        lVar1 = triangle(param_1 + -1,param_2 + -1,param_2 + -1);
        lVar1 = lVar1 + lVar2;
      }
    }
  }
  return lVar1;
}

このコードを元に、param_1回、triangle()の結果を答える。

import socket
from Crypto.Util.number import *

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

def triangle(n1, n2):
    if n1 < n2:
        lVar1 = 0
    else:
        if n1 == 1 and n2 == 1:
            lVar1 = 1
        else:
            if n2 == 1:
                lVar1 = triangle(n1 - 1, n1 - 1)
            else:
                lVar2 = triangle(n1, n2 - 1)
                lVar1 = triangle(n1 - 1, n2 - 1)
                lVar1 = lVar1 + lVar2
    return lVar1

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('dctf-chall-bell.westeurope.azurecontainer.io', 5311))

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

param1 = int(data)
for i in range(1, param1 + 1):
    lVar3 = triangle(param1, i)
    print lVar3
    s.sendall(str(lVar3) + '\n')

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

実行結果は以下の通り。

10
21147
25287
30304
36401
43833
52922
64077
77821
94828
115975
dctf{f1rst_step_t0wards_b3ll_l4bs}

dctf{f1rst_step_t0wards_b3ll_l4bs}

Tiny interpreter (Reverse 400)

binファイルをパラメータとして指定して、実行するだけ。

$ ./interpreter bin
I
n
t
e
r
p
r
e
t
e
r
_
w
r
i
t
t
e
n
_
i
n
_
C
_
i
s
_
a
_
g
r
e
a
t
_
i
d
e
a

dctf{Interpreter_written_in_C_is_a_great_idea}

Very secure website (Web 200)

ソースコードを見ると、こう書いてある。

<?php
    if (isset($_GET['username']) and isset($_GET['password'])) {
        if (hash("tiger128,4", $_GET['username']) != "51c3f5f5d8a8830bc5d8b7ebcb5717df") {
            echo "Invalid username";
        }
        else if (hash("tiger128,4", $_GET['password']) == "0e132798983807237937411964085731") {
            $flag = fopen("flag.txt", "r") or die("Cannot open file");
            echo fread($flag, filesize("flag.txt"));
            fclose($flag);
        }
        else {
            echo "Try harder";
        }
    }
    else {
        echo "Invalid parameters";
    }
?>

"51c3f5f5d8a8830bc5d8b7ebcb5717df"を検索すると、"admin"のtiger128,4ハッシュであることがわかる。
"0e132798983807237937411964085731"は該当するものが見つからないが、"0e(10進数値のみ)"となっているので、0と同等である。tiger128,4が0eから始まり、他が10進数値のものであれば、何でもよい。
調べると、https://blog.csdn.net/fastergohome/article/details/102514264 にこの手法の代表的な値が掲載されていた。
以下でログインしてみると、フラグが表示された。

Username: admin
Password: 479763000

dctf{It's_magic._I_ain't_gotta_explain_shit.}

Strong password (Crypto 100)

$ zip2john strong_password.zip > hash.txt
ver 2.0 efh 9901 strong_password.zip/lorem_ipsum.txt PKZIP Encr: cmplen=5171, decmplen=17174, crc=CEFA3672
$ john --wordlist=dict/rockyou.txt hash.txt --rules
Using default input encoding: UTF-8
Loaded 1 password hash (ZIP, WinZip [PBKDF2-SHA1 256/256 AVX2 8x])
Will run 2 OpenMP threads
Press 'q' or Ctrl-C to abort, almost any other key for status
Bo38AkRcE600X8DbK3600 (strong_password.zip/lorem_ipsum.txt)
1g 0:00:03:06 DONE (2021-05-15 06:30) 0.005372g/s 61022p/s 61022c/s 61022C/s Bobo64..Bitchybo#1
Use the "--show" option to display all of the cracked passwords reliably
Session completed

パスワード "Bo38AkRcE600X8DbK3600" でzipを解凍すると、lorem_ipsum.txtが展開される。この長文の中にフラグが含まれていた。

dctf{r0cKyoU_f0r_tHe_w1n}

Just Take Your Time (Crypto 200)

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

・a * bを答える。
　→正しければ、次へ進む。
・key: UNIXTIMEを16バイト"0"パディングした文字列
・secret: ランダム16バイト(16進数文字列、長さ32)
・DES3でkey、iv="00000000"を使って、secretを暗号化して表示
・secretを正しく答えられたら、フラグが表示される。

UNIXTIMEでkeyがわかるので、復号する。

import socket
from Crypto.Cipher import DES3
from time import time

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(('dctf-chall-just-take-your-time.westeurope.azurecontainer.io', 9999))

data = recvuntil(s, '> ')
print data
formula = data.split('\n')[1].split(' =')[0]
ans = eval(formula)
print ans
s.sendall(str(ans) + '\n')

key = str(int(time())).zfill(16).encode('utf-8')
print key

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

cipher = DES3.new(key, DES3.MODE_CFB, '00000000')
secret = cipher.decrypt(encrypted)
print secret
s.sendall(secret + '\n')
data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

Show me you are worthy and solve for x! You have one second.
2080010430383378 * 7569301504130155 =
>
15744226079307314149567060563590
0000001621028971
You have proven yourself to be capable of taking on the final task. Decrypt this and the flag shall be yours!
9fb7657b8db178abe3411b0b051972b29755b6866e57cd73c224a7f5da22bdc9
1c18c21f26151b7d27b1b1e619014718
> Congratulations! Here is your flag.
dctf{1t_0n1y_t0Ok_2_d4y5...}

dctf{1t_0n1y_t0Ok_2_d4y5...}

Private Encryption Mistake (Crypto 300)

秘密鍵の見えている部分を書き出す。

-----BEGIN RSA PRIVATE KEY-----
MIIJKQIBAAKCAgEAupQ7hhy0AQR0LRMZgP/Kl6J3l2+U+wp1YyVB8oDYvslE3AXU
3igwX2LOYgG/JIHQ5UI2G/0Fu5iPPikh3JoUABGFyPwWsBLnohdBBtpvfRLprhbB
lsKwjZfLJIrRex+sSFkcT9zVs1VH4JfcJAbeBNK/aQdMqc1i4JQ1xsQny4ZH7TZe
CXBigK99+V05C+ENRS1uWi9ixgcbMWCCBHsTq0Kl5FIfPvVJVBr075bf7DdARSRU
Wx/FtKVMlWe/nGUTz/ezu2jOx69kd+hvtzX1JVkeY+AFi7Ldta2tNaH/8kitzoXK
JC+6A+LQXynmjQdH9RGsg7QygFjPvIcgwE8LHsMt62OKcIx5LMHlW4lvLK/EZMnr
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
ZEt6WwyEqHhPyP0CggEBAMplAvElBwRTMaT6FfWwi149Q+C1+ogaRc686CkCEs7p
zWjt4+Tg3cndxj/p2Q3Z1AzJH8h/vfZruAQHF/UFwXIAPmuzS1K0HgnNHxr355vs
AYfArpTJeyZoRttQOXvRhM+c887RWGXX278VVS5e5mh16Dn0rKpDcRnsVMahBhTg
+4XheX0zJRa3lOnoWgRLFGcJj9px4Gk7PkZnx24S2bCb7GUbisvtELkLfAvVcGIS
vvJGbeovAGpArRoaCbpnRL96N50zOWGqHeXJFljvNDvfpVAbykf+50d2VApvElQ3
/v7UHVZEfszMk3g1z+RLpgVmtltCsFvDSkDW9omfoJ0CggEBAIBfu08VPrN+B8iD
QpyO2BBUDei8fjdskpvehjWGDqzKNYDxdVcAdERtk6DSWuzpvwPNbTRm6u3v66yu
QkHn9gBlxX1sYe5P9ExqP2p+Au8hR/8s7bhVa8G53WX1Dl47QVSwbKVOWSWtQSwB
hiB9s1YqgAlhcKBWP6vFbavr3VBYY5ln/018rYvR1euDVTUVZdSMmbq3gScF4fhv
NESMd1Je7XjygbVTPJPi1PcT/SgyDRUwz0RPYIvLlA3qT9ae7s5WTp1fanv5MV6p
4LnekTQ/CVjWSorY7xdXTCMfBK1GF7WhVGG4fVSPX8QeIPKUxKkQXgKAFJrCSjj7
CLG5pPkCggEAflfmKUDTC4kfkXwoXzHxHkgialFPbszvzOmyB39q3E2pU5pFTChv
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
[                           Snipped!                           ]
-----END RSA PRIVATE KEY-----

秘密鍵は部分的に2か所がマスクされている。与えられた情報から秘密鍵を復元することができれば、フラグが得られそう。https://tls.mbed.org/kb/cryptography/asn1-key-structures-in-der-and-pemを参考にした。

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

バイナリで構成を見てみると、q, dpがわかる。さらにeは通常の65537と推測して、pを割り出す。あとはdを算出後、n, e, dから秘密鍵を生成する。

from Crypto.Util.number import *
from Crypto.PublicKey import RSA

key1 = '''
MIIJKQIBAAKCAgEAupQ7hhy0AQR0LRMZgP/Kl6J3l2+U+wp1YyVB8oDYvslE3AXU
3igwX2LOYgG/JIHQ5UI2G/0Fu5iPPikh3JoUABGFyPwWsBLnohdBBtpvfRLprhbB
lsKwjZfLJIrRex+sSFkcT9zVs1VH4JfcJAbeBNK/aQdMqc1i4JQ1xsQny4ZH7TZe
CXBigK99+V05C+ENRS1uWi9ixgcbMWCCBHsTq0Kl5FIfPvVJVBr075bf7DdARSRU
Wx/FtKVMlWe/nGUTz/ezu2jOx69kd+hvtzX1JVkeY+AFi7Ldta2tNaH/8kitzoXK
JC+6A+LQXynmjQdH9RGsg7QygFjPvIcgwE8LHsMt62OKcIx5LMHlW4lvLK/EZMnr
'''

key1 = key1.decode('base64')
hex_n_head = key1[12:].encode('hex')

key2 = '''
ZEt6WwyEqHhPyP0CggEBAMplAvElBwRTMaT6FfWwi149Q+C1+ogaRc686CkCEs7p
zWjt4+Tg3cndxj/p2Q3Z1AzJH8h/vfZruAQHF/UFwXIAPmuzS1K0HgnNHxr355vs
AYfArpTJeyZoRttQOXvRhM+c887RWGXX278VVS5e5mh16Dn0rKpDcRnsVMahBhTg
+4XheX0zJRa3lOnoWgRLFGcJj9px4Gk7PkZnx24S2bCb7GUbisvtELkLfAvVcGIS
vvJGbeovAGpArRoaCbpnRL96N50zOWGqHeXJFljvNDvfpVAbykf+50d2VApvElQ3
/v7UHVZEfszMk3g1z+RLpgVmtltCsFvDSkDW9omfoJ0CggEBAIBfu08VPrN+B8iD
QpyO2BBUDei8fjdskpvehjWGDqzKNYDxdVcAdERtk6DSWuzpvwPNbTRm6u3v66yu
QkHn9gBlxX1sYe5P9ExqP2p+Au8hR/8s7bhVa8G53WX1Dl47QVSwbKVOWSWtQSwB
hiB9s1YqgAlhcKBWP6vFbavr3VBYY5ln/018rYvR1euDVTUVZdSMmbq3gScF4fhv
NESMd1Je7XjygbVTPJPi1PcT/SgyDRUwz0RPYIvLlA3qT9ae7s5WTp1fanv5MV6p
4LnekTQ/CVjWSorY7xdXTCMfBK1GF7WhVGG4fVSPX8QeIPKUxKkQXgKAFJrCSjj7
CLG5pPkCggEAflfmKUDTC4kfkXwoXzHxHkgialFPbszvzOmyB39q3E2pU5pFTChv
'''

key2 = key2.decode('base64')
q = bytes_to_long(key2[0x000f:0x000f+0x0101])
dp = bytes_to_long(key2[0x0114:0x0114+0x0101])

e = 65537

for kp in range(3, e):
    p_mul = dp * e - 1
    if p_mul % kp == 0:
        p = (p_mul // kp) + 1
        if isPrime(p):
            break

n = p * q
assert hex(n)[2:].startswith(hex_n_head)

phi = (p - 1) * (q - 1)
d = inverse(e, phi)

key = RSA.construct(map(long, (n,e,d)))
priv_pem = key.exportKey()

with open('privkey.pem', 'w') as f:
    f.write(priv_pem)

秘密鍵生成後、内容を確認し、この鍵でssh接続する。

$ cat privkey.pem
-----BEGIN RSA PRIVATE KEY-----
MIIJKQIBAAKCAgEAupQ7hhy0AQR0LRMZgP/Kl6J3l2+U+wp1YyVB8oDYvslE3AXU
3igwX2LOYgG/JIHQ5UI2G/0Fu5iPPikh3JoUABGFyPwWsBLnohdBBtpvfRLprhbB
lsKwjZfLJIrRex+sSFkcT9zVs1VH4JfcJAbeBNK/aQdMqc1i4JQ1xsQny4ZH7TZe
CXBigK99+V05C+ENRS1uWi9ixgcbMWCCBHsTq0Kl5FIfPvVJVBr075bf7DdARSRU
Wx/FtKVMlWe/nGUTz/ezu2jOx69kd+hvtzX1JVkeY+AFi7Ldta2tNaH/8kitzoXK
JC+6A+LQXynmjQdH9RGsg7QygFjPvIcgwE8LHsMt62OKcIx5LMHlW4lvLK/EZMnr
W1v8D+ixrv6MOzheFofU2gmDLNM57DYrjylhrtKHzUmPi73wJuHSaOYCS6jVY0EF
4UhWyoV6GZykFhON4/y64Ppv6v20V3vbeql8i2pzxGnHWjaYHLi4Vjr8kzzwEYel
IiePd/M646PuIznUHUXjZ1FfkhBZwmE067gTBGVbt5nPL+JXGSzin1xW2VCp3BG7
CouAZ6hCm72gHZdfVLVdb5emK630pf4nR1al5hleOEBB+Z1lmgLg2kwAJor4IdW/
QZ3p8iy3ZGM7YWDm/XEjSNJUToS+Dv7X8mAkHWcbD2KxYHzu5oqzvuCvYykCAwEA
AQKCAgEAiuMnQBkDwbIgDSGnnYhLtf7ByV/NZeaOJYSph6x0K+lFMgfBQrJl98tk
WD52m+VqrA5SmxkJeHEDSEF0LHQhqT9h+I/3D5CzDs0Coehej5tRij70UpaQuIYj
OQuBDocwRxbWZXi9N2anP7+rpsHZ6Xs78yH05n22Ofj54wFHolBOIH2VGK+pE6QP
QV4sxfP8Xd+Iwud9Pm4xxtrRTiaUKKtPNBwRmFsc/9elNuh3va4PUKjPhpmrIWLf
FGSLlQ8E5Y29JCfLrYeZYU0MRDSNTQT/A1fSqQA33DLxuffiv+dsQk0DgVZpwNTJ
Sd21+otN/FbwtYWhBjuWP//S2HS+kBxiE9e69MEjBNM4yg2CXFHQPno/1gh/PpqB
lCwCs//91PsTH14OSENVc91q4bTSzgRpPzANjH4CFz+Q8DgIP5OchET9gY11AcnT
ffUm/VYYyDNhjbnHxoUHQI1Sl4ktKyomd6185KJwufwuaEKidQebM7cpb58xgj9N
8RHnhUt78MBN5Zld3abtJqggslOXhK71GCHgRNC2L3Vf5F5w7h1dgoAZq2xsXT8C
K2wMyNDxeATMp3TyubQJj5gLJwL24MKPEdbk1TlWaTnYMrcSGJ2L2DROKsP1RaRn
T31FpsRMoI4u6O4kRX2U8ZcNvwxDvi3ct8yY50KmVSsl+2tkOpECggEBAMplAvEl
BwRTMaT6FfWwi149Q+C1+ogaRc686CkCEs7pzWjt4+Tg3cndxj/p2Q3Z1AzJH8h/
vfZruAQHF/UFwXIAPmuzS1K0HgnNHxr355vsAYfArpTJeyZoRttQOXvRhM+c887R
WGXX278VVS5e5mh16Dn0rKpDcRnsVMahBhTg+4XheX0zJRa3lOnoWgRLFGcJj9px
4Gk7PkZnx24S2bCb7GUbisvtELkLfAvVcGISvvJGbeovAGpArRoaCbpnRL96N50z
OWGqHeXJFljvNDvfpVAbykf+50d2VApvElQ3/v7UHVZEfszMk3g1z+RLpgVmtltC
sFvDSkDW9omfoJ0CggEBAOv+4KO6pSNK1ZuTN5CP/xMshgBytwbe4b4lCi7SUP4Y
ofeE4LzQU+iEaqsXtahlxH7gMht18vcwHAKKpEWkZkJK7MrcOFFb65SBZilB6rH5
PmB1+YR7XnOnPMrdSiyBMjG7u7x2nicjkOfgiL1CXWiU8r4/aFoDEtBtVTCY4FzC
1R0x2uZOd1m+JieedaBlwqGlTpGb+65NiEvWyVn0G4JK4a5lU9uOcK1B05QBd3Ln
StzmG966bEhMZ2qCly32pXUoWWoiYZlIHtklUnMXPsRivBxRqDMnNRkFaSG63FAa
AIPZaOgQpyaYaQn3Y/paj3WWfb6GZEt6WwyEqHhPyP0CggEAflfmKUDTC4kfkXwo
XzHxHkgialFPbszvzOmyB39q3E2pU5pFTChva0eNLXK+c14KeFzJAXF01TJTMfh3
pRYNtyudy7+mAp+7rKSmiUA+DeCa5/KJSQopXUV1Dg0bhUa6oJu6ut2GUDUa0ULw
5LyLGqSX7i3l53eoT+Vu2nvEfx4fBWlGXLijq3W4ePf50XpI5zVZ3qR90VMRQgQg
w37y88OyIz+5Oinn6YvYyM5ZlG9dUYJTtP/YQ3vSU1vzvLAgg2M4+mHyrRv0A/Cu
iZ/xPHsVCFgAw0bFe5/LQKQrjfVSsiMZmTOy8Ae4+y6kc0AiCHcg2QFddDsJzEYk
qq7CJQKCAQEAgF+7TxU+s34HyINCnI7YEFQN6Lx+N2ySm96GNYYOrMo1gPF1VwB0
RG2ToNJa7Om/A81tNGbq7e/rrK5CQef2AGXFfWxh7k/0TGo/an4C7yFH/yztuFVr
wbndZfUOXjtBVLBspU5ZJa1BLAGGIH2zViqACWFwoFY/q8Vtq+vdUFhjmWf/TXyt
i9HV64NVNRVl1IyZureBJwXh+G80RIx3Ul7tePKBtVM8k+LU9xP9KDINFTDPRE9g
i8uUDepP1p7uzlZOnV9qe/kxXqngud6RND8JWNZKitjvF1dMIx8ErUYXtaFUYbh9
VI9fxB4g8pTEqRBeAoAUmsJKOPsIsbmk+QKCAQBhZ15iWWnEwGKI2lCbUbZQYvtc
BHQktmhqYLl8p8GFJ4TeiybOz+MlIhhFaqHUFzJzkaqYQHLH5E7g8BDr/IS9/3wo
LNDI3suL9RLMd45CSYN52irJwKS8oVJuJDsGH/KWX/gM6c0MzXtFb8IyDvi6Z0rn
PwYZs+46Cafh30G0AWlRhDCXhdWN1b7PeWwAHZAOzphvnd/Z6k4Je9z1DMgqKM2r
rYQu21jF66BbTNuQOm/Z/PPEFYo3YkISwEF9cALzVF+hRN+REFA+qGBKtY2Uxmwz
i1+rFieUo+yRxBPsJt8cXYX9vso2OPNKHuy0R4+VyWL/WJCa/J3LoKCWvfzY
-----END RSA PRIVATE KEY-----

$ ssh -i privkey.pem user@dctf1-chall-private-encryption-mistake.westeurope.azurecontainer.io -p 2222
The authenticity of host '[dctf1-chall-private-encryption-mistake.westeurope.azurecontainer.io]:2222 ([20.67.120.180]:2222)' can't be established.
ECDSA key fingerprint is SHA256:P5sEp/Iaie3GJcsicYtMk0gi5FZREmFhLLMh8jjPSy4.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[dctf1-chall-private-encryption-mistake.westeurope.azurecontainer.io]:2222,[20.67.120.180]:2222' (ECDSA) to the list of known hosts.
Welcome to OpenSSH Server


dctf{Y0u_Are_N0w_Br34thing_M4nua11y}

Connection to dctf1-chall-private-encryption-mistake.westeurope.azurecontainer closed.

dctf{Y0u_Are_N0w_Br34thing_M4nua11y}

A Simple SP Box! (Crypto 300)

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

・フラグを暗号化して表示
・15回以下を繰り返し
　・フラグを推測し、正しければ、フラグが表示される。

■暗号化
・平文の長さが奇数の場合は、"_"をパディング
・rounds = int(2 * ceil(log(len(message), 2))) 
・rounds回以下を繰り返し
　・message = [S_box[c] for c in message]
　・最終回以外は奇数番目グループと偶数番目グループで連結

※rounds = 2の場合
　message = [S_box[c] for c in message]
　0バイト目と1バイト目を交換
　message = [S_box[c] for c in message]

暗号化したフラグの長さからround = 12。S_boxの2回の対応表はわかるので、逆変換で6回行えば元に戻る。奇数番目と偶数番目の連結は11回行われるので、その逆変換も行えばフラグを得られる。

import socket
from string import ascii_letters, digits
from math import ceil, log

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

def inv_perm(s):
    l = len(s) / 2
    odd_s = s[:l]
    even_s = s[l:]
    d = ''
    for i in range(l):
        d += even_s[i]
        d += odd_s[i]
    return d

def inv_sub(s, inv_sbox):
    d = ''
    for c in s:
        d += inv_sbox[c]
    return d

ALPHABET = ascii_letters + digits + "_!@#$%.'\"+:;<=}{"

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('dctf1-chall-sp-box.westeurope.azurecontainer.io', 8888))

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

inv_S_box = {}

for i in range(0, len(ALPHABET), 2):
    data = recvuntil(s, '> ')
    print data + ALPHABET[i] + ALPHABET[i+1]
    s.sendall(ALPHABET[i] + ALPHABET[i+1] + '\n')
    data = recvuntil(s, '\n').rstrip()
    print data
    data = recvuntil(s, '\n').rstrip()
    print data
    inv_S_box[data[1]] = ALPHABET[i]
    inv_S_box[data[0]] = ALPHABET[i+1]

rounds = int(2 * ceil(log(len(enc_flag), 2)))
inv_S_box_rounds = rounds / 2
perm_rounds = rounds - 1

tmp_flag = enc_flag
for i in range(rounds // 2):
    tmp_flag = inv_sub(tmp_flag, inv_S_box)

for i in range(rounds - 1):
    tmp_flag = inv_perm(tmp_flag)

flag = tmp_flag.rstrip('_')
print flag

実行結果は以下の通り。

Here's the flag, please decrypt it for me:
RMXXE'oosXIBc6XBXdcCXR''3cxBCX6dTM}=csRJXT
> ab
That doesn't look right, it encrypts to this:
+=
> cd
That doesn't look right, it encrypts to this:
MI
> ef
That doesn't look right, it encrypts to this:
uJ
> gh
That doesn't look right, it encrypts to this:
qX
> ij
That doesn't look right, it encrypts to this:
Ya
> kl
That doesn't look right, it encrypts to this:
jc
> mn
That doesn't look right, it encrypts to this:
vP
> op
That doesn't look right, it encrypts to this:
fz
> qr
That doesn't look right, it encrypts to this:
kB
> st
That doesn't look right, it encrypts to this:
1s
> uv
That doesn't look right, it encrypts to this:
"o
> wx
That doesn't look right, it encrypts to this:
x$
> yz
That doesn't look right, it encrypts to this:
OL
> AB
That doesn't look right, it encrypts to this:
DA
> CD
That doesn't look right, it encrypts to this:
SN
> EF
That doesn't look right, it encrypts to this:
:i
> GH
That doesn't look right, it encrypts to this:
42
> IJ
That doesn't look right, it encrypts to this:
%8
> KL
That doesn't look right, it encrypts to this:
wV
> MN
That doesn't look right, it encrypts to this:
n5
> OP
That doesn't look right, it encrypts to this:
mU
> QR
That doesn't look right, it encrypts to this:
hK
> ST
That doesn't look right, it encrypts to this:
Z<
> UV
That doesn't look right, it encrypts to this:
Hd
> WX
That doesn't look right, it encrypts to this:
9C
> YZ
That doesn't look right, it encrypts to this:
eE
> 01
That doesn't look right, it encrypts to this:
!b
> 23
That doesn't look right, it encrypts to this:
rG
> 45
That doesn't look right, it encrypts to this:
py
> 67
That doesn't look right, it encrypts to this:
tl
> 89
That doesn't look right, it encrypts to this:
'R
> _!
That doesn't look right, it encrypts to this:
g7
> @#
That doesn't look right, it encrypts to this:
_@
> $%
That doesn't look right, it encrypts to this:
Q;
> .'
That doesn't look right, it encrypts to this:
#.
> "+
That doesn't look right, it encrypts to this:
3{
> :;
That doesn't look right, it encrypts to this:
WT
> <=
That doesn't look right, it encrypts to this:
06
> }{
That doesn't look right, it encrypts to this:
F}
dctf{S0_y0u_f0und_th3_cycl3s_in_th3_s_b0x}

dctf{S0_y0u_f0und_th3_cycl3s_in_th3_s_b0x}

This one is really basic (Crypto 300)

繰り返しbase64デコードする。

with open('cipher.txt', 'r') as f:
    data = f.read().rstrip()

while True:
    try:
        data = data.decode('base64')
    except:
        break

print data

dctf{Th1s_l00ks_4_lot_sm4ll3r_th4n_1t_d1d}

3kCTF-2021 Writeup

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

sponsors (Misc)

添付されているPDFの最後のページにフラグが書いてあった。

3k{saNiTy_ch3K_2732832}

crypto warmup (Crypto)

ナップザック暗号。24ビットごとにビットの有無に対応するBの各要素の合計が暗号になっている。LLLを使って復号する。

#!/usr/bin/sage
from Crypto.Util.number import long_to_bytes

def is_valid_vector(b):
    if b[0] != 0:
        return False
    for i, x in enumerate(b):
        if i != 0 and abs(x) != 1:
            return False

    return True

B = [4267101277, 4946769145, 6306104881, 7476346548, 7399638140, 1732169972, 1236242271, 5109093704, 2163850849, 6552199249, 3724603395, 3738679916, 5211460878, 642273320, 3810791811, 761851628, 1552737836, 4091151711, 1601520107, 3117875577, 2485422314, 1983900485, 6150993150, 2045278518]
ct_list = [34451302951, 58407890177, 49697577713, 45443775595, 38537028435,
    47069056666, 49165602815, 43338588490, 32970122390]

matrix_size = len(B) + 1
m_list = [
    [0 for _ in range(matrix_size)] for _ in range(matrix_size)
]

for i in range(matrix_size - 1):
    m_list[i][0] = B[i]
    m_list[i][i+1] = 2
    m_list[matrix_size - 1][i+1] = -1

flag = ''
for ct in ct_list:
    m_list[matrix_size - 1][0] = -ct

    llled = Matrix(ZZ, m_list).LLL()

    flag_vecs = []
    for basis in llled:
        if is_valid_vector(basis):
            flag_vecs.append(basis)

    for v in flag_vecs:
        m = ''
        for _bit in reversed(v[1:]):
            c = ("1" if _bit == 1 else "0")
            m = c + m
        flag += long_to_bytes(int(m, 2))

print flag

CTF{w4rmup-kn4ps4ck-ftw!}

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}

m0leCon CTF 2021 Teaser Writeup

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

Proof-of-Work (mics, warmup)

そのまま添付のコードを実行する。

[+] Opening connection to challs.m0lecon.it on port 1337: Done
Solving PoW...
Solved!
[*] Switching to interactive mode
ptm{w3lc0me_t0_m0lecon_2021_t34ser_ctf_chall3ng3_++++}
[*] Got EOF while reading in interactive

ptm{w3lc0me_t0_m0lecon_2021_t34ser_ctf_chall3ng3_++++}

babysign (crypto, warmup)

signするメッセージは64バイトで切られるので、超えるまでmsgを指定して、signの値が変わらなくなる長さを見つける。その結果、フラグの長さは25バイトであることがわかる。
signの計算は以下のようになっている。

m[0]: msgの前半32バイト
m[1]: msgの後半32バイト

sign = pow(sha256(m[1]) ^ m[0], d, n)
→ pow(sign, e, n) = sha256(m[1]) ^ m[0]

前半32バイトと後半32バイトで分けて、signの値を出している。後半32バイトを含めて指定して、flag+msgのsignを出せば、m[0]を算出でき、フラグがわかる。

from pwn import remote #pip install pwntools
from hashlib import sha256
from Crypto.Util.number import *

def solvepow(p, n):
    s = p.recvline()
    starting = s.split(b'with ')[1][:10].decode()
    s1 = s.split(b'in ')[-1][:n]
    i = 0
    print("Solving PoW...")
    while True:
        if sha256((starting+str(i)).encode('ascii')).hexdigest()[-n:] == s1.decode():
            print("Solved!")
            p.sendline(starting + str(i))
            break
        i += 1

def exploit(p):
    p.interactive()

if __name__ == '__main__':
    p = remote('challs.m0lecon.it', 7012)
    solvepow(p, n = 5)

    # get flag length
    pre_sign = ''
    for i in range(1, 65):
        s = p.recvuntil('t\n').rstrip()
        print(s)
        print '2'
        p.sendline('2')
        msg = '1' * i
        print msg
        p.sendline(msg)
        s = p.recvline().rstrip()
        print(s)
        if pre_sign != s:
            pre_sign = s
        else:
            flag_len = 64 - (i - 1)
            sign = s
            print '[+] flag_len =', flag_len
            break

    # get parameter
    s = p.recvuntil('t\n').rstrip()
    print(s)
    print '4'
    p.sendline('4')
    s = p.recvline().rstrip()
    print(s)
    N = int(s.split(':')[1])
    s = p.recvline().rstrip()
    print(s)
    e = int(s.split(':')[1])

    # get flag
    xor_val = pow(int(sign, 16), e, N)
    val1 = bytes_to_long(sha256('1' * 32).digest())
    val2 = (xor_val ^ val1)
    flag = long_to_bytes(val2).rstrip('1')
    print flag

実行結果は以下の通り。

[+] Opening connection to challs.m0lecon.it on port 7012: Done
Solving PoW...
Solved!

1. Sign
2. Sign but better
3. Verify
4. See key
0. Exit
2
1
7654e86a9217f2cb45e6ccfd4a5c49ba9920f0ab021027e9905e5668dc319911d734ca7109c6d12e461ad8b491150466a1b20050b0e6020faf830e0fa720082e127ef5294bfeb9f92202ec0be604ac0a0e5dc75a33ec42d0936b8fe24dab171c4794c3870335aa36f5dc70cfc15c44bf30fc61f885ca8bc8c8991dc38a53be2047b70f7a5b3801c52d1c63be029065a09c94fb0f24896d4a5ed23f0d62b1a0d4c5d8bbca45b917ce059b7067e98052deb2f4f21bddd663d7d1f2b5d695534ae7bd51df7a264c36bca3c2e30162f67b155b7eb0b1836e36ed2379d3900b38e0030580ef1e5f5bfc7ba88525ffa088d3a143e94167d2eeca1a193cbfd5c7aedcaa

1. Sign
2. Sign but better
3. Verify
4. See key
0. Exit
2
11
90794aff81934d8e66dc01d8a48a0234ac258bfc01b13b0d2227965ccd7bdf66daba91e32ebb51272af4abff859e5c0b0f7b75eb3d5c2375105becb2688ab74c53d00fcbba0863a8974d9463910819d17867343097c03984c3eacec4e2462f675971cdffd66e415eb3c6e5d3f4a5030d84469293a64f39ef87b569edea04f26ff9d211e16d4e4e5964f5feb5e8b4adec4f330465ec9978e017938491cb94ec87a76aa936cf963825b62eb758dbf9c524893515ecf599f9dca28e48d47c277dd01225aebce78ff3b7e87df21423a779d946fd852bd3325c93ad61f92a627319846e52f0a7fce7d8d698b9f83fcd77a4270574f2a5c42a47e73b9f6c368069449b

1. Sign
2. Sign but better
3. Verify
4. See key
0. Exit
2
111
6534c3b2223db6f80dd2478920c85b5f83a4fc055a1cf598e37fca704581daa16f4d7a260b8a85bbb2bcbe5d414dd6cc893171cdee882392d4dfa2b44ce1df5d2f228046e34123dda8d958b32d0972b8e386c0304fda003b13e371a4c7b99ba8684e649057860cb2b1d43a8ee918bd57e770db8d26e24c42d745c7d26c7c9e67fe2cef22fc7fd98093e463852683d329bdb09ccb89e469f131cd283007fb976357bcca7bcfad2d78f5fd53b60a26fd59806fb2b3ca48f13f9e2a324af2389c0a98cc9cfaa25184117912bf5a00ada18187f32601a89e5b89c9d3e783b73241b0b232d10a780cfa9c8a9a6f4bffa8895d3f031ef18e293fb0f2ae1f37f7083b44

1. Sign
2. Sign but better
3. Verify
4. See key
0. Exit
2
1111
4668a6ec7f59235f43936abcc1a9981c44d1895d1a8a1bffbfd5a5346f40b7ec370aefac6a5d94aa29fa44e37d1da88464ebc72b2a5fd09915086bc0f246544c45ffa9789b295dbd8ade42fedb048a55f896ffe2a983cdb80570f650eb2a1cfcc3168f56ba1979cc089008676ba70f8a5cf6d6e364856d5709b275566385591d1f0cef3022d2ae64ea13f8459bdf99d289f82842a910b9c38d49d44ef2de16260460a1721e5c79983523970a2d779b0de4b6cf17c9ee69c4c2fce4986bd518f64ed31314dc4a0d2f542a104ed80c3c05cc876ac857af6e32981c705da842a4e82086d23beea873bd9be3916e1f41eb272360a3ae603b9d77e1c7ffb67826fbbc

　　　　　　　　　　　　　　　　：

1. Sign
2. Sign but better
3. Verify
4. See key
0. Exit
2
111111111111111111111111111111111111111
3f482ae9b380ae40bf7baf5b7d9b20d9776bf4f7e9f1cfdb9a6c6520b41d93f82b7b975a98feab12856e5ee09dbf3edac9b2e66cce0b66ee4ac17e1beb9acc330a95f6c895038e26857327335013495156ad07fae53391fabe4fe1bb457b63347d6f2696fc7dfe7987cf81663f3b328fff517e6166256e2b8adbdc0a053599a7f49893c6debbe905944170735a367c05dc9377a792ec85734cda44049aa373a32efa1bb4957bd4b445d0e611456ce6c68b489d39de2620f34b9036090c3f154acdb1f5e6e3109973e84d6eacb8e8f5244b3c270e490904aec1302c61c8a3c8fd12f90870f0a84b9115df9a9b1e25b298df3d7e5a840fd75669cd9c8cbbe27b0c

1. Sign
2. Sign but better
3. Verify
4. See key
0. Exit
2
1111111111111111111111111111111111111111
3f482ae9b380ae40bf7baf5b7d9b20d9776bf4f7e9f1cfdb9a6c6520b41d93f82b7b975a98feab12856e5ee09dbf3edac9b2e66cce0b66ee4ac17e1beb9acc330a95f6c895038e26857327335013495156ad07fae53391fabe4fe1bb457b63347d6f2696fc7dfe7987cf81663f3b328fff517e6166256e2b8adbdc0a053599a7f49893c6debbe905944170735a367c05dc9377a792ec85734cda44049aa373a32efa1bb4957bd4b445d0e611456ce6c68b489d39de2620f34b9036090c3f154acdb1f5e6e3109973e84d6eacb8e8f5244b3c270e490904aec1302c61c8a3c8fd12f90870f0a84b9115df9a9b1e25b298df3d7e5a840fd75669cd9c8cbbe27b0c
[+] flag_len = 25

1. Sign
2. Sign but better
3. Verify
4. See key
0. Exit
4
N: 19444496506668057565703830709849574320119296023394552743554841106288876599982744410824562139626939984799109105140756569415987962251605405845574431989522509087927660918203612673476669357567232593612283314538320313077153463307443372271764546196165597912289325099399933625991423985237269731742331704718635784230127944001937032123837083823100411218004555265023043907327356201192573706917175963092954167020576450218169479787879017269282697810966173088094066379117109022908457751989745785332187858364088369306396333542665150480610191515201381727392976960502629656117629021217476064093045075121509083820256945142151229305921
e: 65537
ptm{n07_3v3n_4_ch4ll3n63}
[*] Closed connection to challs.m0lecon.it port 7012

ptm{n07_3v3n_4_ch4ll3n63}