Sunshine CTF 2018 Writeup

この大会は2018/4/6 5:00(JST)~2018/4/8 5:00(JST)に開催されました。
今回もチームで参戦。結果は1951点で780チーム中23位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (Forensics 1)

問題にフラグが書いてある。

sun{take_this_free_FLAG}

My Secret Stash (Forensics 100)

gitのファイル群が添付されている。

$ cd .git
$ xxd -g 1 index
0000000: 44 49 52 43 00 00 00 02 00 00 00 01 5a ab 13 05  DIRC........Z...
0000010: 2f ad 33 86 5a ab 13 05 2f 55 fc 4e 01 00 00 04  /.3.Z.../U.N....
0000020: 00 5d 74 3d 00 00 81 a4 00 00 01 f5 00 00 00 14  .]t=............
0000030: 00 00 01 3c 9f ee ea b8 2f 7a fe 27 eb 0f 67 21  ...<..../z.'..g!
0000040: 2f 95 2d c8 6c 23 03 e9 00 07 73 65 63 72 65 74  /.-.l#....secret
0000050: 73 00 00 00 54 52 45 45 00 00 00 19 00 31 20 30  s...TREE.....1 0
0000060: 0a ce 69 c6 ab c7 c9 9b 63 50 5d f3 81 22 77 d6  ..i.....cP].."w.
0000070: 9b a4 67 4b 9d 8b 25 e0 4f a8 48 6f a2 6c c8 27  ..gK..%.O.Ho.l.'
0000080: 28 4e 8a 8f b8 2a 75 67 55                       (N...*ugU

$ python -c 'import zlib; print zlib.decompress(open("objects/9f/eeeab82f7afe27eb0f67212f952dc86c2303e9").read())'
blob 316I'm so very sorry, you will not find my secrets in here. There was a time at which I wanted to share my secrets with someone, but that was long ago and I don't trust anyone anymore. I want to keep all of my secrets to myself for now on! Good luck trying to find them, there's nothing to find. hehehehehehehehe!!!!!!

$ cat logs/refs/heads/master
0000000000000000000000000000000000000000 7e2927361b7e4101e07fc5a475bb244622a275e3 Carlos Staszeski <cstaszeski@gmail.com> 1521160193 -0400	commit (initial): vegan!
7e2927361b7e4101e07fc5a475bb244622a275e3 92fb7e7ebbc65d04ac311c3f1d4e496cd867e94d Carlos Staszeski <cstaszeski@gmail.com> 1521160586 -0400	commit: is
92fb7e7ebbc65d04ac311c3f1d4e496cd867e94d 3fe304a91a3049d9589e379b843f4dca9c47aafc Carlos Staszeski <cstaszeski@gmail.com> 1521160985 -0400	commit: Bobby

$ python -c 'import zlib; print zlib.decompress(open("objects/7e/2927361b7e4101e07fc5a475bb244622a275e3").read())'
commit 185tree 74967e81c7d6b83bb2647abc6890a3adfae0e96a
author Carlos Staszeski <cstaszeski@gmail.com> 1521160193 -0400
committer Carlos Staszeski <cstaszeski@gmail.com> 1521160193 -0400

vegan!

$ python -c 'import zlib; print zlib.decompress(open("objects/74/967e81c7d6b83bb2647abc6890a3adfae0e96a").read())' | xxd -g 1
0000000: 74 72 65 65 20 33 35 00 31 30 30 36 34 34 20 73  tree 35.100644 s
0000010: 65 63 72 65 74 73 00 8a de a5 38 cd 0f d8 27 09  ecrets....8...'.
0000020: 09 4b 9c 77 2d c3 a2 15 76 d4 d3 0a              .K.w-...v...

$ python -c 'import zlib; print zlib.decompress(open("objects/8a/dea538cd0fd82709094b9c772dc3a21576d4d3").read())'
blob 225So, you've discovered how to travel back in time did you? Well that's not going to help you much here, you see, my stash is so well hidden you will never ever ever find it! hahahahahahahahhahahahahahahahahahahah!!!!!!!!!!!!!

$ python -c 'import zlib; print zlib.decompress(open("objects/92/fb7e7ebbc65d04ac311c3f1d4e496cd867e94d").read())'
commit 229tree ed91e6d10fdb88d4a9e2f4471e7b60170ba70a37
parent 7e2927361b7e4101e07fc5a475bb244622a275e3
author Carlos Staszeski <cstaszeski@gmail.com> 1521160586 -0400
committer Carlos Staszeski <cstaszeski@gmail.com> 1521160586 -0400

is

$ python -c 'import zlib; print zlib.decompress(open("objects/ed/91e6d10fdb88d4a9e2f4471e7b60170ba70a37").read())' | xxd -g 1
0000000: 74 72 65 65 20 33 35 00 31 30 30 36 34 34 20 73  tree 35.100644 s
0000010: 65 63 72 65 74 73 00 94 7f 94 13 31 a9 eb 2d 90  ecrets.....1..-.
0000020: 87 05 45 34 89 cd 56 e0 61 7d a5 0a              ..E4..V.a}..

$ python -c 'import zlib; print zlib.decompress(open("objects/94/7f941331a9eb2d908705453489cd56e0617da5").read())'
blob 304I feel like we are becoming good friends you and I. Yes. I even considered letting you in on one of my secrets just now, but I didn't want to risk it falling into the wrong hands. So instead I stashed it away and destroyed it so that no one would ever be able to recover my secrets! muahahahahahah!!!!!!

$ python -c 'import zlib; print zlib.decompress(open("objects/3f/e304a91a3049d9589e379b843f4dca9c47aafc").read())'
commit 232tree ce69c6abc7c99b63505df3812277d69ba4674b9d
parent 92fb7e7ebbc65d04ac311c3f1d4e496cd867e94d
author Carlos Staszeski <cstaszeski@gmail.com> 1521160985 -0400
committer Carlos Staszeski <cstaszeski@gmail.com> 1521160985 -0400

Bobby

$ python -c 'import zlib; print zlib.decompress(open("objects/ce/69c6abc7c99b63505df3812277d69ba4674b9d").read())' | xxd -g 1
0000000: 74 72 65 65 20 33 35 00 31 30 30 36 34 34 20 73  tree 35.100644 s
0000010: 65 63 72 65 74 73 00 9f ee ea b8 2f 7a fe 27 eb  ecrets...../z.'.
0000020: 0f 67 21 2f 95 2d c8 6c 23 03 e9 0a              .g!/.-.l#...

$ python -c 'import zlib; print zlib.decompress(open("objects/9f/eeeab82f7afe27eb0f67212f952dc86c2303e9").read())'
blob 316I'm so very sorry, you will not find my secrets in here. There was a time at which I wanted to share my secrets with someone, but that was long ago and I don't trust anyone anymore. I want to keep all of my secrets to myself for now on! Good luck trying to find them, there's nothing to find. hehehehehehehehe!!!!!!

フラグが見つからない。手あたり次第調べる。

$ python -c 'import zlib; print zlib.decompress(open("objects/7b/82ac03c49c0b55a4a8b8ffb3c04c5fe565fba6").read())'
commit 258tree 74967e81c7d6b83bb2647abc6890a3adfae0e96a
parent 7e2927361b7e4101e07fc5a475bb244622a275e3
author Carlos Staszeski <cstaszeski@gmail.com> 1521160299 -0400
committer Carlos Staszeski <cstaszeski@gmail.com> 1521160299 -0400

index on master: 7e29273 vegan!

$ python -c 'import zlib; print zlib.decompress(open("objects/14/a5c7088e7638abb2232c8cac1c7dd4687819f0").read())'
commit 304tree c9936edd0f107fc91fdaa876def0dc960b000760
parent 7e2927361b7e4101e07fc5a475bb244622a275e3
parent 7b82ac03c49c0b55a4a8b8ffb3c04c5fe565fba6
author Carlos Staszeski <cstaszeski@gmail.com> 1521160299 -0400
committer Carlos Staszeski <cstaszeski@gmail.com> 1521160299 -0400

WIP on master: 7e29273 vegan!

$ python -c 'import zlib; print zlib.decompress(open("objects/c9/936edd0f107fc91fdaa876def0dc960b000760").read())' | xxd -g 1
0000000: 74 72 65 65 20 33 35 00 31 30 30 36 34 34 20 73  tree 35.100644 s
0000010: 65 63 72 65 74 73 00 bd 12 73 6e 7c 80 5c 83 49  ecrets...sn|.\.I
0000020: 4a 71 c3 66 a7 f8 85 0e e7 a3 79 0a              Jq.f......y.

$ python -c 'import zlib; print zlib.decompress(open("objects/bd/12736e7c805c83494a71c366a7f8850ee7a379").read())'
blob 17sun{git_gud_k1d}
sun{git_gud_k1d}

Source Protection (RE 100)

https://sourceforge.net/projects/pyinstallerextractor/からPyInstaller Extractorをインストール、展開する。

>pyinstxtractor.py passwords.exe
[*] Processing passwords.exe
[*] Pyinstaller version: 2.1+
[*] Python version: 27
[*] Length of package: 3188825 bytes
[*] Found 18 files in CArchive
[*] Beginning extraction...please standby
[+] Possible entry point: pyiboot01_bootstrap
[+] Possible entry point: passwords
[*] Found 194 files in PYZ archive
[*] Successfully extracted pyinstaller archive: passwords.exe

You can now use a python decompiler on the pyc files within the extracted directory

passwordsファイル内にフラグがあった。

sun{py1n574ll3r_15n7_50urc3_pr073c710n}

Visionary (Crypto 150)

スペースを除くprintableな文字をすべて使ったVigenere暗号。

chars = '!\"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~'

with open('visionary/Cipher1.txt', 'r') as f:
    c1 = f.read().strip()

with open('visionary/Decipher(Cipher1).txt', 'r') as f:
    p1 = f.read().strip()

with open('visionary/cipherFlag.txt', 'r') as f:
    encFlag = f.read().strip()

key = ''
for i in range(len(encFlag)):
    index = chars.index(c1[i]) - chars.index(p1[i])
    if index < 0:
        index += len(chars)
    key += chars[index]

print key

flag = ''
for i in range(len(encFlag)):
    index = chars.index(encFlag[i]) - chars.index(key[i])
    if index < 0:
        index += len(chars)
    flag += chars[index]

print flag
sun{Why_would_Any0n3_use_A_T@bl3_tH@t_LaRg3}

Missing Bytes (Scripting 200)

再帰を使いながら、ディレクトリのサイズが配下のサイズの合計と一致しない場合にsendコマンドでディレクトリ名を指定する。
コードは以下の通り。20ラウンド正解すると、フラグが表示される。

import socket
import re

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

def check_dir(name, size):
    # 0: ok
    # 1: ng
    # 2: finish
    cmd = 'cd ' + name
    #print cmd
    s.sendall(cmd + '\n')
    data = recvuntil(s, '$ ')
    #print data

    cmd = 'ls'
    #print cmd
    s.sendall(cmd + '\n')
    data = recvuntil(s, '$ ')
    #print data

    rows = data.split('\r\n')
    num = get_entries_num(rows[0])
    sum_size = 0
    for i in range(num):
        name2, fd, size2 = get_row_info(rows[i+1])
        sum_size += size2
        if fd == 'DIR':
            res = check_dir(name2, size2)
            if res == 1:
                s.sendall('send ' + name2 + '\n')
                data = recvuntil(s, '\n')
                data += recvuntil(s, ' ')
                if 'Hooray!' in data:
                    data += recvuntil(s, '\n')
                    data += recvuntil(s, '\n')
                    print data
                    return 2
                else:
                    data += recvuntil(s, '$ ')
                    #print data
            elif res == 2:
                return 2

    cmd = 'cd ..'
    #print cmd
    s.sendall(cmd + '\n')
    data = s.recv(256)
    #print data

    if size == sum_size:
        return 0
    else:
        return 1

def get_entries_num(row):
    m = re.search('\((.+) entries\)', row)
    num = int(m.group(1))
    return num

def get_row_info(row):
    name = row[:7].strip()
    fd = row[8:12].strip()
    size = int(row[13:])
    return name, fd, size

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('chal1.sunshinectf.org', 30001))

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

print 'start'
s.sendall('start\n')

for i in range(20):
    print '**************************'
    print '******** Round %02d ********' % (i+1)
    print '**************************'
    data = recvuntil(s, '$ ')
    print data

    cmd = 'ls'
    print cmd
    s.sendall(cmd + '\n')
    data = recvuntil(s, '$ ')
    print data

    rows = data.split('\r\n')
    num = get_entries_num(rows[0])
    for j in range(num):
        name, fd, size = get_row_info(rows[j+1])
        if fd == 'DIR':
            print name
            res = check_dir(name, size)
            if res == 1:
                s.sendall('send ' + name + '\n')
                data = recvuntil(s, '\n')
                data += recvuntil(s, ' ')
                if 'Hooray!' in data:
                    data += recvuntil(s, '\n')
                    data += recvuntil(s, '\n')
                    #print data
                    break
                else:
                    data += recvuntil(s, '$ ')
                    #print data
            elif res == 2:
                break
sun{a11_ur_byt3s_4re_b3long_t0_m3}

0CTF/TCTF 2018 Quals Writeup

この大会は2018/3/31 10:00(JST)~2018/4/2 10:00(JST)に開催されました。
今回もチームで参戦。結果は225点で700チーム中85位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (Misc)

freenodeで#0ctf2018チャネルに入ったら、フラグが表示された。

10:08 *topic : "Welcome to 0CTF / TCTF 2018". flag{Welcome_to_0CTF_2018!}. Any question, please mailto: ctf@0ops.net"
flag{Welcome_to_0CTF_2018!}

h4x0rs.club 1 (Web)

admin/admin(パスワードは何でも可)でキャプチャの値を正しく入力すればログインできる。
[PROFILE]ボタンを押すと、フラグが書かれている画面が表示された。
f:id:satou-y:20180410202704p:plain

flag{h0w_d1d_y0u_get_thiSs_gud_luck_for_next_one}

Nuit du Hack CTF Quals 2018 Writeup

この大会は2018/3/31 7:00(JST)~2018/4/1 7:00(JST)に開催されました。
今回もチームで参戦。結果は1451点で490チーム中40位でした。
自分で解けた問題をWriteupとして書いておきます。

Mendeleev Kitten (Steganography 1)

太字を連結する。

the flag is ndhlovegues$ing
ndhlovegues$ing

Kebab STO (Network 350)

パケットNo.532からメールデータをエクスポートする。さらに添付のdocs.zipを取り出す。解凍すると公開鍵と暗号ファイルが入っている。

n = 132119157511680658111880682548963924051331705861454986711768309171053164036215035682846853400693298308407159092441565764240671045694580814479569353657242905803474941835516889801663312750421436789466405483162627315243202964702067817108771735145199423231066261892116799167192950216724527627610107225490309235963
e = 65537
c = 72873754879996948796542757182427480866384878894019674005699447004829908491467629529161961884224325941110935083467870715412599916138560976722953815670278067115980556377912852138532905866093650699880301357138301236748217037629036311469031537013958415575513723738671978421707050599317605219729945496472798064172

復号サービスを使って、復号する。

$ nc kebabsto.challs.malice.fr 8888
What message do you want to decrypt: 72873754879996948796542757182427480866384878894019674005699447004829908491467629529161961884224325941110935083467870715412599916138560976722953815670278067115980556377912852138532905866093650699880301357138301236748217037629036311469031537013958415575513723738671978421707050599317605219729945496472798064172
72873754879996948796542757182427480866384878894019674005699447004829908491467629529161961884224325941110935083467870715412599916138560976722953815670278067115980556377912852138532905866093650699880301357138301236748217037629036311469031537013958415575513723738671978421707050599317605219729945496472798064172


Here is the cleartext of your input :


123360975347216093033775350245751721746535757669936
>>> ('%x' % 123360975347216093033775350245751721746535757669936).decode('hex')
'Th1s1s2P@ss_W0rd%M0f0'

何かのパスワードっぽい。
今度はパケットNo.384からZIPファイルをエクスポートする。解凍すると、lkdjflknezczが展開される。

$ file lkdjflknezcz 
lkdjflknezcz: tcpdump capture file (little-endian) - version 2.4 (802.11, capture length 65535)
$ mv lkdjflknezcz lkdjflknezcz.pcap
$ aircrack-ng -w dict/rockyou.txt lkdjflknezcz.pcap
Opening lkdjflknezcz.pcap
Read 1358 packets.

   #  BSSID              ESSID                     Encryption

   1  F0:D7:AA:77:BD:46  wifiAccess                WPA (1 handshake)

Choosing first network as target.

Opening lkdjflknezcz.pcap
Reading packets, please wait...

                                 Aircrack-ng 1.1


                   [00:00:01] 604 keys tested (392.00 k/s)


                           KEY FOUND! [ abcdefgh ]


      Master Key     : 46 DE 68 77 59 26 52 28 68 59 E3 E9 27 C2 75 66 
                       77 A0 C0 C2 59 7C B7 6A 52 06 A3 B8 5D 7F 33 29 

      Transient Key  : C8 2A 89 4B 43 93 57 73 35 B7 9E 21 99 8A 5A F2 
                       B6 89 B8 10 F6 AF 77 68 A8 B4 69 E7 30 E4 A7 9B 
                       88 32 93 FF AA B5 8E CE 9E AC 4A 05 05 0C EC BB 
                       37 C9 12 11 5B DA 0C E9 D8 25 02 5E F3 D2 AA 4F 

      EAPOL HMAC     : 76 32 AE BA 65 FD A2 64 BD FD 8E 76 BA 1F B7 84

WiresharkIEEE 802.11の設定で、wpa-pwdでキーをabcdefghと設定し、lkdjflknezcz.pcapを開く。
パケットNo.1292からftpでやり取りしているZIPを取り出す。解凍するときに先ほどのパスワード Th1s1s2P@ss_W0rd%M0f0 を指定すると、slkfdsfljファイルが展開される。
ファイルの内容は以下の通り。

The flag is : ndh2k18{M4k3M4tr10cHKa9r34T4g41n}
ndh2k18{M4k3M4tr10cHKa9r34T4g41n}

SwampCTF 2018 Writeup

この大会は2018/3/30 7:00(JST)~2018/4/1 7:00(JST)に開催されました。
今回もチームで参戦。結果は5610点で938チーム中12位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome! (MISC 50)

問題にフラグが書いてある。

flag{w3lc0m3_to_th3_Sw4mp}

Locked Dungeon (CRYPTO 500)

$ nc chal1.swampctf.com 1450
a
3093544369609e4c2f5f26df2aa78919037bd1387ce3892b819b684df891444b901e13b8930c546a9a0adcf1a9833d47
aa
3093544369609e4c2f5f26df2aa78919037bd1387ce3892b819b684df891444b45c8cd48c8290ab80e019654ddcc5e7e
aaa
3093544369609e4c2f5f26df2aa78919037bd1387ce3892b819b684df891444bde20f2cf2d966c306ef7b9c354aa27c9
aaaa
3093544369609e4c2f5f26df2aa78919037bd1387ce3892b819b684df891444b86bb631359f4eda8ad02f48a1bd939ae
aaaaa
3093544369609e4c2f5f26df2aa78919037bd1387ce3892b819b684df891444b4e12b2f258ca77a4d0bff5c44de3095dea6098e410f2e26f0f5e5ee117982362

16バイトずつ、ブロック単位で区切ると以下のようなイメージ。

flag{xxxxxxxxxxx
xxxxxxxxxxxxxxxx
xxxxxxxxxx}#####

flag{xxxxxxxxxxx
xxxxxxxxxxxxxxxx
xxxxxxxxxx0#####

フラグを後ろから1文字ずつ、暗号結果が同じものを探り当てる。

import socket
import string

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('chal1.swampctf.com', 1450))

pad_str = '#####'
#print pad_str
s.sendall(pad_str + '\n')
data = s.recv(256)
#print data
correct = data.strip()[:96]

flag = ''
for i in range(0x1900):
    for c in string.printable:
        try_str = c + flag + pad_str
        print try_str
        s.sendall(try_str + '\n')
        data = s.recv(256)
        #print data
        try_enc = data.strip()
        if try_enc == correct:
            flag = c + flag
            break
    if len(flag) == (48 - len(pad_str)):
        break

print flag
flag{rem3mber_the_pic_of_tux_aes_3ncrypted}

Orb of Light 1: Secret (CRYPTO 500)

以下の通り、英大文字以外を使っていない英大文字に置換する。

\xe2\x80\x99 -> '
2 -> B
9 -> C
a -> D
d -> F
g -> H
f -> I
i -> J
h -> K
l -> M
o -> O
n -> P
r -> Q
t -> U
z -> V

これをquipqiupにかけると、復号できる。

DOMINION OF SHADOWS AND UNUSUAL THINGS

"TOXIC DOMAIN OF DARK ILLUSION
LAND THAT SHROUDS LOATHING LIGHT
BOUNDARY OF WORLDS UNKNOWN"

LAND OF SHADOWS, A TWILIGHT DOMAIN THAT IS A DARK MIRROR, OR COPY, OF OUR WORLD. A POINT OF BLIGHT AND CORROSION, A DOMAIN OUT OF SYNC, A LAND WITH HORRORS RIGHT BY YOU AND YOU DON'T KNOW.

ARTISANS OF A THAUMATURGICAL KIND DO NOT USUALLY CROSS INTO LANDS OF SHADOW FOR IN SUCH DOMAINS AN UNKNOWN HORROR IS SAID TO LURK.  ARRIVAL ALWAYS BRINGS ABOUT DISSOLUTION OF ASPIRATIONS FOR SHADOWS QUICKLY SWALLOW SOULS OF LIGHT IN A MYSTIC IMPOSSIBILITY.  A SOLITARY AUGURY WAS PROOF: KINGDOMS WILL FALL AS CONJURATION OF SHADOW GLOOMS MIDDAY WITH DARK MALICIOUS FOG, A LUMINOUS CHARM WILL CAST A RAY THAT AGAIN ALIGNS OUR WORLD.

ここからチームのメンバが解いてくれた。文字の置換のマッピングが関係していたらしい。復号したアルファベット順に並べると、フラグになる。

A=f
B=l
C=a
D=g
F=S
G=T
H=R
I=A
J=N
K=G
L=E
M=2
N=t
O=h
P=i
Q=n
R=9
S=z
T=W
U=o
V=r
W=L
X=d
Y=Z
flag{STRANGE2thin9zWorLdZ}

Securinets CTF Quals 2018 Writeup

この大会は2018/3/25 4:00(JST)~2018/3/26 4:00(JST)に開催されました。
今回もチームで参戦。結果は5200点で216チーム中11位でした。
自分で解けた問題をWriteupとして書いておきます。

IRC (Misc 50)

IRCタグから#ctf_securinetsチャネルに入る。

Welcome to CTF Securinets Channel :D Flag{W3Lc0m3_T0_CTFSecurinets_Quals_2018}
Flag{W3Lc0m3_T0_CTFSecurinets_Quals_2018}

Easy (Reverse Engineering 100)

$ strings easy | grep Flag
Flag{This_Is_A_Hidden_Flag!!}
Flag{This_Is_A_Hidden_Flag!!}

looser (Crypto 150)

キー1文字でXORしていそう。PNGに復号することを想定して復号する。

with open('flag.png.crypt', 'rb') as f:
    c = f.read()

key = ord(c[0]) ^ 0x89

flag = ''
for i in range(len(c)):
    code = ord(c[i]) ^ key
    flag += chr(code)

with open('flag.png', 'wb') as f:
    f.write(flag)

f:id:satou-y:20180402213006p:plain

Flag{Hopefully_headers_are_constants}

The worst RSA Joke (Crypto 350)

公開鍵と暗号ファイルが与えられている。まず、公開鍵を見てみる。

$ openssl rsa -pubin -text < public.pem
Public-Key: (2049 bit)
Modulus:
    01:21:3b:05:7d:6f:de:bc:45:27:b5:b7:42:1a:c1:
    e9:3c:cf:fe:a7:6c:4f:08:74:99:1c:f3:fa:cf:0e:
    ab:9e:f6:46:a2:18:39:82:0b:4d:65:3a:91:6b:68:
    f2:58:e9:d3:f7:c2:ba:05:4e:4a:f0:5f:3e:4d:61:
    b3:de:77:2d:2a:d2:33:8b:0e:ae:6e:a0:8f:20:76:
    e4:e4:b0:8a:b2:09:20:fa:68:85:e6:c4:4d:ec:1b:
    ee:28:a8:76:53:c7:4b:cb:9e:9f:12:94:de:8a:48:
    bd:61:46:52:a3:d6:59:df:ce:7b:89:44:61:0f:25:
    bf:af:93:6e:9a:54:16:7c:4d:22:7d:16:d3:2e:65:
    ea:45:8b:69:d6:0d:ec:d7:fa:03:4c:1b:3b:d8:62:
    71:71:64:e7:78:5e:b0:6d:cc:5b:88:ba:a2:62:e4:
    31:20:e5:46:65:c0:cb:cb:3e:ad:51:b0:a0:08:19:
    b4:e9:1d:48:72:d3:fb:e7:72:4e:03:ab:71:bc:af:
    8b:b8:4c:74:de:c9:6a:ad:fc:b1:86:53:a8:f0:53:
    93:d6:66:06:99:23:bc:7b:9b:31:36:3d:6d:6d:9b:
    45:9f:46:db:5b:af:96:f8:40:4a:af:1a:83:1f:0d:
    b8:aa:d7:d9:3a:42:56:e8:15:6b:2b:70:75:7a:01:
    20:93
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEBITsFfW/evEUntbdCGsHp
PM/+p2xPCHSZHPP6zw6rnvZGohg5ggtNZTqRa2jyWOnT98K6BU5K8F8+TWGz3nct
KtIziw6ubqCPIHbk5LCKsgkg+miF5sRN7BvuKKh2U8dLy56fEpTeiki9YUZSo9ZZ
3857iURhDyW/r5NumlQWfE0ifRbTLmXqRYtp1g3s1/oDTBs72GJxcWTneF6wbcxb
iLqiYuQxIOVGZcDLyz6tUbCgCBm06R1IctP753JOA6txvK+LuEx03slqrfyxhlOo
8FOT1mYGmSO8e5sxNj1tbZtFn0bbW6+W+EBKrxqDHw24qtfZOkJW6BVrK3B1egEg
kwIDAQAB
-----END PUBLIC KEY-----
n = 0x01213b057d6fdebc4527b5b7421ac1e93ccffea76c4f0874991cf3facf0eab9ef646a21839820b4d653a916b68f258e9d3f7c2ba054e4af05f3e4d61b3de772d2ad2338b0eae6ea08f2076e4e4b08ab20920fa6885e6c44dec1bee28a87653c74bcb9e9f1294de8a48bd614652a3d659dfce7b8944610f25bfaf936e9a54167c4d227d16d32e65ea458b69d60decd7fa034c1b3bd862717164e7785eb06dcc5b88baa262e43120e54665c0cbcb3ead51b0a00819b4e91d4872d3fbe7724e03ab71bcaf8bb84c74dec96aadfcb18653a8f05393d666069923bc7b9b31363d6d6d9b459f46db5baf96f8404aaf1a831f0db8aad7d93a4256e8156b2b70757a012093
  = 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611

nを素因数分解してみる。

$ python -m primefac 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611
36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611: 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611

nが素数のようだ。RSA暗号の仕組みを考える。

c = m^e % n
 ↓
c = m^e % (素数 * n)

この場合は復号結果が複数出るが、文字として読み取れるものをブルートフォースで探す。

from Crypto.PublicKey import RSA

def is_prime(d):
    if d < 2:
        return False
    if d == 2:
        return True
    if d % 2 == 0:
        return False

    a = 3
    while a ** 2 <= d:
        if d % a == 0:
            return False
        a = a + 2

    return True

def is_printable(s):
    for i in range(len(s)):
        if ord(s[i]) < 32 or ord(s[i]) > 126:
            return False

    return True

with open('RSA_Worst_Joke/public.pem', 'r') as f:
    pub_data = f.read()

pubkey = RSA.importKey(pub_data)
p = pubkey.n
e = pubkey.e

with open('RSA_Worst_Joke/flag.enc', 'r') as f:
    c = int(f.read().decode('base64').encode('hex'), 16)

for q in range(50):
    if is_prime(q):
        n = p * q

        phi = (p - 1) * (q - 1)

        x = 0
        while True:
            if (phi * x + 1) % e == 0:
                d = (phi * x + 1) / e
                break
            x = x + 1

        m = pow(c, d, n)

        hex_flag = '%x' % m
        if len(hex_flag) % 2 == 1:
            hex_flag = '0' + hex_flag
        flag = hex_flag.decode('hex')
        if is_printable(flag):
            print 'q =', q
            print flag

実行結果は以下の通り。

q = 47
The empire secret system has been exposed ! The top secret flag is : Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}
Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}

Improve the quality (Crypto 800)

decription.txtには以下のように記載されている。

Hello Every one,
We didn't know what to do, so we are asking for your help.

A friend of us sent us the following text:

I used an elliptic curve encrytion for the first time.
The only thing that i kown about elliptic curve is that a number K must always be hidden.
so i made multiple encryption to send some information.

Here is all the informations about the elliptic curve that i used excep the K number.

The elliptic curve is : 
y^2 = x^3 + A*x + B
A = 658974
Sorry i forget the B :/ , I just remember that it's most significant number is  6

As an order of a finite field must be a prime power, i used p = 962280654317 (FiniteField(p)).
as a starter point, i used the generator G for this elliptic curve: (518459267012 : 339109212996 : 1)
and each time i reuse it to encrypt again

let my secret message be K .
for exemple I divided my K to 2 elements k1 and k2
then Q1 is k1*G
and Q2 is k2*G

here are the Qi that i got:

[(656055339629 : 670956206845 : 1), 
(714432985374 : 30697818482 : 1), 
(519532969453 : 833497145865 : 1), 
(606806384185 : 353033449641 : 1), 
(370553209582 : 211121736115 : 1), 
(95617246846 : 666814491609 : 1), 
(474872055371 : 795112698430 : 1), 
(249845085299 : 222352033875 : 1), 
(850954431245 : 810446463695 : 1), 
(188731559428 : 877002121896 : 1), 
(168665615402 : 464872506873 : 1), 
(26722558561 : 269217869309 : 1), 
(16403346294 : 478534963882 : 1), 
(539749282946 : 332444159141 : 1), 
(932295517649 : 23439478940 : 1), 
(765194933041 : 920187938377 : 1), 
(853124087439 : 845601917928 : 1), 
(246454416048 : 212483699689 : 1), 
(312547608490 : 688107262695 : 1), 
(43261158649 : 439444472742 : 1), 
(320785434805 : 477080449838 : 1), 
(741706320740 : 672809544395 : 1), 
(361762297756 : 858805805323 : 1), 
(782235980044 : 600673464737 : 1), 
(69196762074 : 327427680437 : 1), 
(876001563166 : 573218279075 : 1), 
(117946101727 : 954797129239 : 1), 
(771781111553 : 314018907599 : 1), 
(579549799021 : 322325160055 : 1), 
(857081196493 : 464260539273 : 1), 
(852938568103 : 429083796488 : 1), 
(850954431245 : 810446463695 : 1), 
(55203632714 : 255470537391 : 1), 
(600464434215 : 605840305721 : 1), 
(620532163623 : 575613893944 : 1), 
(215810002861 : 481354983411 : 1), 
(538481263994 : 666638294130 : 1), 
(528666082457 : 895034116069 : 1), 
(296218553972 : 899557390183 : 1), 
(428618251485 : 445768511836 : 1), 
(632412058600 : 685699421425 : 1), 
(634041855232 : 495546745721 : 1), 
(570481762204 : 252944477333 : 1), 
(760959783781 : 435626456209 : 1)]
y^2 = x^3 + a*x + b mod n 
→b = y^2 - x^3 - a*x mod n

この場合は以下の文字になるので、まずはBを求める。

a -> A
b -> B
n -> p
p = 962280654317
A = 658974
G = (518459267012, 339109212996)

x = G[0]
y = G[1]
B = (pow(y, 2) - pow(x, 3) - A * x) % p
print 'B =', B
B = 618

Bの値はわかったので、Pohlig–Hellman algorithmを使って、k1から順番に求める。その値を見ながらメッセージになるようASCIIコード(10進数)として2桁ずつ読み込む。
コードは以下の通り。

# solve.sage
p = 962280654317
A = 658974
B = 618
G = (518459267012, 339109212996)
Q = [(656055339629, 670956206845), 
(714432985374, 30697818482), 
(519532969453, 833497145865), 
(606806384185, 353033449641), 
(370553209582, 211121736115), 
(95617246846, 666814491609), 
(474872055371, 795112698430), 
(249845085299, 222352033875), 
(850954431245, 810446463695), 
(188731559428, 877002121896), 
(168665615402, 464872506873), 
(26722558561, 269217869309), 
(16403346294, 478534963882), 
(539749282946, 332444159141), 
(932295517649, 23439478940), 
(765194933041, 920187938377), 
(853124087439, 845601917928), 
(246454416048, 212483699689), 
(312547608490, 688107262695), 
(43261158649, 439444472742), 
(320785434805, 477080449838), 
(741706320740, 672809544395), 
(361762297756, 858805805323), 
(782235980044, 600673464737), 
(69196762074, 327427680437), 
(876001563166, 573218279075), 
(117946101727, 954797129239), 
(771781111553, 314018907599), 
(579549799021, 322325160055), 
(857081196493, 464260539273), 
(852938568103, 429083796488), 
(850954431245, 810446463695), 
(55203632714, 255470537391), 
(600464434215, 605840305721), 
(620532163623, 575613893944), 
(215810002861, 481354983411), 
(538481263994, 666638294130), 
(528666082457, 895034116069), 
(296218553972, 899557390183), 
(428618251485, 445768511836), 
(632412058600, 685699421425), 
(634041855232, 495546745721), 
(570481762204, 252944477333), 
(760959783781, 435626456209)]

F = FiniteField(p)
E = EllipticCurve(F, [A,B])
G = E.point(G)

factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]

str_num = ''
for i in range(len(Q)):
    dlogs = []
    for fac in primes:
        t = int(G.order()) / int(fac)
        dlog = discrete_log(t*E.point(Q[i]), t*G, operation='+')
        dlogs += [dlog]

    k = crt(dlogs, primes)
    print k
    #print k * G == E.point(Q[i])
    str_num += str(k)

msg = ''
for i in range(0, len(str_num), 2):
    msg += chr(int(str_num[i:i+2]))

print msg

実行結果は以下の通り。

CONVERT THIS TO LOWER CASE FIRST :
THIS IMAGE CONTAINS THE FLAG, TRY TO GET IT
THE SUBMITTED FLAG MUST BE IN THIS FORMAT: 
FLAG-EC[WHAT YOU'LL FIND IN THE IMAGE]
IMAGE URL:
HTTP://CRYPTO.CTFSECURINETS.COM/1/STEG-PART.PNG

上記で大文字、小文字が関係するところは小文字にする。
http://crypto.ctfsecurinets.com/1/steg-part.pngのファイルを見たら、フラグが書いてあった。
f:id:satou-y:20180402213759p:plain

flag-ec[EC_St!e-g1(a)no]

VolgaCTF 2018 Quals Writeup

この大会は2018/3/24 0:00(JST)~2018/3/26 0:00(JST)に開催されました。
今回もチームで参戦。結果は860点で411チーム中59位でした。
自分で解けた問題をWriteupとして書いておきます。

Nonsense (crypto 200)

ECDSAの問題だが、ほぼ数学の問題。xの値を求めればよい。

state = seed
state = (a * state + b) % m
k = state
(r, s) = signature.sign(message, k)
state = (a * state + b) % m
k = state
(r, s) = signature.sign(message, k)
   :

h1 = int(hashlib.md5(m1).hexdigest(), 16)
h2 = int(hashlib.md5(m2).hexdigest(), 16)
r1 = pow(g, k1, p) % q
s1 = int((x * r1 + h1) * invert(k1, q) % q)
r2 = pow(g, k2, p) % q
s2 = int((x * r2 + h2) * invert(k2, q) % q)
k2 = a * k1 + b (mod m)

m = qになっていることを使い、mod q を前提に式を変形していく。

s1 * k1 = x * r1 + h1
s2 * k2 = x * r2 + h2
    ↓
s1 * k1 = x * r1 + h1
s2 * (a * k1 + b) = x * r2 + h2
    ↓
s1 * s2 * k1 * a = x * r1 * s2 * a + h1 * s2 * a
s1 * s2 * k1 * a + s1 * s2 * b = x * r2 * s1 + h2 * s1
    ↓
s1 * s2 * b = x * (r2 * s1 - r1 * s2 * a) + (h2 * s1 - h1 * s2 * a)
    ↓
x = (s1 * s2 * b - (h2 * s1 - h1 * s2 * a)) * invert(r2 * s1 - r1 * s2 * a, q)

コードにすると、以下の通り。

import hashlib
import gmpy2

q = 1118817215266473099401489299835945027713635248219
a = 3437776292996777467976657547577967657547
b = 828669865469592426262363475477574643634

r1 = 1030409245884476193717141088285092765299686864672
s1 = 830067187231135666416948244755306407163838542785
r2 = 403903893160663712713225718481237860747338118174
s2 = 803753330562964683180744246754284061126230157465
msg1 = 'VolgaCTF{nKpV/dmkBeQ0n9Mz0g9eGQ==}'
msg2 = 'VolgaCTF{KtetaQ4YT8PhTL3O4vsfDg==}'

h1 = int(hashlib.md5(msg1).hexdigest(), 16)
h2 = int(hashlib.md5(msg2).hexdigest(), 16)

x = ((s1 * s2 * b - (h2 * s1 - h1 * s2 * a)) * gmpy2.invert(r2 * s1 - r1 * s2 * a, q)) % q
flag = '%x' % x
print flag
9d529e2da84117fe72a1770a79cec6ece4065212

angstromCTF 2018 Writeup

この大会は2018/3/17 5:30(JST)~2018/3/22 5:00(JST)に開催されました。
今回もチームで参戦。結果は2955点で1516チーム中16位でした。
自分で解けた問題をWriteupとして書いておきます。

IRC (MISC 10)

freenodeで#angstromctfチャネルに入る。

11:04 *topic : Need help from an admin? All of the channel operators are admins. | You didn't forget your password, login is currently down! All will be well soon. | IRC flag: actf{irc} | ?ngstromCTF 2018 will start sometime soon PM EDT :: https://angstromctf.com/ | Everything is dead sorry...but soon it shall be reborn
actf{irc}

WARMUP (CRYPTO 10)

暗号はパッと見た感じシーザー暗号。

myjd{ij_fkwizq}

しかし復号できず。問題文の「it's a fine cipher.」からAffine暗号と推測。https://www.dcode.fr/affine-cipherブルートフォースで復号。

A=19,B=12	ACTFITBEGIN
actf{it_begins}

BACK TO BASE-ICS (CRYPTO 20)

Part 1: 011000010110001101110100011001100111101100110000011011100110010101011111011101000111011100110000010111110110011000110000
Part 2:	165 162 137 145 151 147 150 164 137 163 151 170 164 63 63 
Part 3: 6e5f7468317274797477305f733178
Part 4: dHlmMHVyX25vX20wcmV9

それぞれエンコードしているものを復号し、結合する。

Part1: 2進数
Part2: 8進数
Part3: hexエンコード
Part4: Base64エンコード
e1 = '011000010110001101110100011001100111101100110000011011100110010101011111011101000111011100110000010111110110011000110000'

flag1 = ''
for i in range(0, len(e1), 8):
    flag1 += chr(int(e1[i:i+8], 2))

e2 = '165 162 137 145 151 147 150 164 137 163 151 170 164 63 63 '
e2 = e2.split(' ')

flag2 = ''
for i in range(len(e2) - 1):
    flag2 += chr(int(e2[i], 8))

e3 = '6e5f7468317274797477305f733178'
flag3 = e3.decode('hex')

e4 = 'dHlmMHVyX25vX20wcmV9'
flag4 = e4.decode('base64')

flag = flag1 + flag2 + flag3 + flag4
print flag
actf{0ne_tw0_f0ur_eight_sixt33n_th1rtytw0_s1xtyf0ur_no_m0re}

XOR (CRYPTO 40)

XORキーは1文字のようなので、平文がactfで始まることを前提に復号する。

with open('ciphertext.txt', 'r') as f:
    data = f.read().strip().decode('hex')

key = ord(data[0]) ^ ord('a')

flag = ''
for i in range(len(data)):
    flag += chr(ord(data[i]) ^ key)

print flag
actf{hope_you_used_a_script}

INTRO TO RSA (CRYPTO 50)

p, q, e, cがわかっているので、そのまま復号する。

p = 169524110085046954319747170465105648233168702937955683889447853815898670069828343980818367807171215202643149176857117014826791242142210124521380573480143683660195568906553119683192470329413953411905742074448392816913467035316596822218317488903257069007949137629543010054246885909276872349326142152285347048927
q = 170780128973387404254550233211898468299200117082734909936129463191969072080198908267381169837578188594808676174446856901962451707859231958269401958672950141944679827844646158659922175597068183903642473161665782065958249304202759597168259072368123700040163659262941978786363797334903233540121308223989457248267
e = 65537
c = 4531850464036745618300770366164614386495084945985129111541252641569745463086472656370005978297267807299415858324820149933137259813719550825795569865301790252501254180057121806754411506817019631341846094836070057184169015820234429382145019281935017707994070217705460907511942438972962653164287761695982230728969508370400854478181107445003385579261993625770566932506870421547033934140554009090766102575218045185956824020910463996496543098753308927618692783836021742365910050093343747616861660744940014683025321538719970946739880943167282065095406465354971096477229669290277771547093476011147370441338501427786766482964
n = p * q

phi = (p - 1) * (q - 1)

x = 0
while True:
    if (phi * x + 1) % e == 0:
        d = (phi * x + 1) / e
        break
    x = x + 1

m = pow(c, d, n)

flag = ('%x' % m).decode('hex')
print flag
actf{rsa_is_reallllly_fun!!!!!!}

OFB (CRYPTO 120)

4の倍数の長さになるよう\x00を付ける。その後4バイトずつの配列にする。
4バイト単位で暗号化しているが、PNGのフォーマットを前提にx, a, cがわかる。

x1 = a * x0 + c mod m
x2 = a * x1 + c mod m
x3 = a * x2 + c mod m

x2 - x1 = a * (x1 - x0) mod m
x3 - x1 = a * (x2 - x0) mod m

a = (x2 - x1) * modinv(x1 - x0, m)
c = x1 - (x0 * a) mod m

これで4バイト単位にxor鍵が割り出せるので、復号できる。

import struct

def lcg(m, a, c, x):
    return (a * x + c) % m

def egcd(a, b):
   if a == 0:
       return (b, 0, 1)
   else:
       g, y, x = egcd(b % a, a)
       return (g, x - (b // a) * y, y)

m = pow(2, 32)

with open('flag.png.enc', 'rb') as f:
    ciphertext = f.read()

PNG_HEAD = '\x89PNG\x0d\x0a\x1a\x0a\x00\x00\x00\x0d'

x = []
for i in range(0, len(PNG_HEAD), 4):
    iXor = int(ciphertext[i:i+4].encode('hex'), 16)
    iPlain = int(PNG_HEAD[i:i+4].encode('hex'), 16)
    x.append(iXor ^ iPlain)

x1 = x[2] - x[1]
alpha = x[1] - x[0]

g1, p1, q1 = egcd(alpha, m)

if g1 == 1:
    mod_inv = p1 % m
elif g1 == -1:
    mod_inv = - p1 % m
else:
    modinv = 0
a = (x1 * mod_inv) % m

c = (x[1] - x[0] * a) % m

flag = ''
x = x[0]
for i in range(0, len(ciphertext), 4):
    flag += struct.pack('>I', x ^ struct.unpack('>I', ciphertext[i:i+4])[0])
    x = lcg(m, a, c, x)

while True:
    if flag[-1] == '\x00':
        flag = flag[:-1]
    else:
        break

with open('flag.png', 'wb') as f:
    f.write(flag)

復号したPNG画像にフラグが書いてあった。
f:id:satou-y:20180326201114p:plain

actf{pad_rng}

SSH (CRYPTO 150)

公開鍵をPEM形式に変換し、内容を確認する。

$ ssh-keygen -f id_rsa.pub -e -m PKCS8 > id_rsa.pub.pem
$ openssl rsa -pubin -text < id_rsa.pub.pem
Public-Key: (2048 bit)
Modulus:
    00:be:5d:95:8b:09:b2:29:1c:f0:bd:36:51:1c:91:
    55:e2:29:f8:ae:8d:cc:ae:e1:55:2c:96:69:b8:1b:
    53:2a:36:3b:4f:34:76:94:12:86:7c:cf:92:cb:40:
    ad:de:f5:20:0a:05:dc:de:f0:9c:8d:a3:09:82:fa:
    54:13:d9:52:f4:e7:db:3d:a7:39:51:9f:ab:77:d5:
    74:de:52:36:6c:96:03:ac:e8:87:c0:cb:f3:2c:52:
    47:ce:c1:42:28:e8:a7:2a:a5:25:67:99:e5:4c:40:
    f3:a2:2d:46:42:cd:af:5e:0d:d0:77:33:11:58:e7:
    d8:4d:ba:87:56:d5:31:a4:bb:4d:2b:a3:e7:9c:29:
    97:2f:27:eb:8d:0b:f9:df:81:e2:e9:cd:a2:3b:0d:
    de:ad:23:c0:0a:ae:bf:a0:f5:38:32:77:a2:21:77:
    72:9a:9c:b5:ee:58:c4:70:19:b6:cb:32:2d:7f:b9:
    a4:1d:f3:a2:d5:62:df:d2:02:f9:06:3b:5e:5e:50:
    42:cf:ef:6d:dc:fe:41:23:28:67:e1:c1:22:a8:dc:
    c1:8c:e5:1e:fb:b8:cc:5f:9b:c0:f3:29:6f:10:91:
    ca:30:10:ed:85:12:73:d4:ca:40:67:57:53:da:89:
    6a:e5:fc:fa:01:59:3a:7c:84:d5:18:c5:03:c0:ae:
    e5:81
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAvl2ViwmyKRzwvTZRHJFV
4in4ro3MruFVLJZpuBtTKjY7TzR2lBKGfM+Sy0Ct3vUgCgXc3vCcjaMJgvpUE9lS
9OfbPac5UZ+rd9V03lI2bJYDrOiHwMvzLFJHzsFCKOinKqUlZ5nlTEDzoi1GQs2v
Xg3QdzMRWOfYTbqHVtUxpLtNK6PnnCmXLyfrjQv534Hi6c2iOw3erSPACq6/oPU4
MneiIXdympy17ljEcBm2yzItf7mkHfOi1WLf0gL5BjteXlBCz+9t3P5BIyhn4cEi
qNzBjOUe+7jMX5vA8ylvEJHKMBDthRJz1MpAZ1dT2olq5fz6AVk6fITVGMUDwK7l
gQIDAQAB
-----END PUBLIC KEY-----
n = 0x00be5d958b09b2291cf0bd36511c9155e229f8ae8dccaee1552c9669b81b532a363b4f34769412867ccf92cb40addef5200a05dcdef09c8da30982fa5413d952f4e7db3da739519fab77d574de52366c9603ace887c0cbf32c5247cec14228e8a72aa5256799e54c40f3a22d4642cdaf5e0dd077331158e7d84dba8756d531a4bb4d2ba3e79c29972f27eb8d0bf9df81e2e9cda23b0ddead23c00aaebfa0f5383277a22177729a9cb5ee58c47019b6cb322d7fb9a41df3a2d562dfd202f9063b5e5e5042cfef6ddcfe41232867e1c122a8dcc18ce51efbb8cc5f9bc0f3296f1091ca3010ed851273d4ca40675753da896ae5fcfa01593a7c84d518c503c0aee581

秘密鍵は大部分がマスクされている。与えられた情報から秘密鍵を復元することができれば、フラグが得られそう。
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
}

バイナリで構成を見てみる。

version         0x0000 - 0x0006 (30 82 04 A3 02 01 00)	7
modulus         0x0007 - 0x010b (02 82 01 01)		261(257)
publicExponent  0x010c - 0x0110 (02 03) 010001		5(3)
privateExponent 0x0111 - 0x0214 (02 82 01 00)		260(256)
prime1          0x0215 - 0x0298 (02 81 81)		132(129)
prime2          0x0299 - 0x031c (02 81 81)		132(129)
exponent1       0x031d - 0x03a0 (02 81 81)		132(129)
exponent2       0x03a1 - 0x0423 (02 81 80)		131(128)
coefficient     0x0424 - 0x04a6 (02 81 80)		131(128)

最初の624バイトが不明。625バイト目以降144バイト分がわかっている。prime1の後半とprime2の前半しかわからない。

prime1: 625-665(下41バイトのみ判明)
prime2: 669-768(上100バイトのみ判明)

片方の素数の上位ビット半分以上が判明しているため、Coppersmith's Attackを行い、素数を割り出す。

# solve.sage
n = 0x00be5d958b09b2291cf0bd36511c9155e229f8ae8dccaee1552c9669b81b532a363b4f34769412867ccf92cb40addef5200a05dcdef09c8da30982fa5413d952f4e7db3da739519fab77d574de52366c9603ace887c0cbf32c5247cec14228e8a72aa5256799e54c40f3a22d4642cdaf5e0dd077331158e7d84dba8756d531a4bb4d2ba3e79c29972f27eb8d0bf9df81e2e9cda23b0ddead23c00aaebfa0f5383277a22177729a9cb5ee58c47019b6cb322d7fb9a41df3a2d562dfd202f9063b5e5e5042cfef6ddcfe41232867e1c122a8dcc18ce51efbb8cc5f9bc0f3296f1091ca3010ed851273d4ca40675753da896ae5fcfa01593a7c84d518c503c0aee581
e = 65537

priv_part = '''
YC2/ZTbmSZFL9t5Em+ic2ayw0nNUSI6XO7+3tcT9TABzh94t9YLhiDcCgYEA0LFZ
OUTgvmnWAkwGSo/6huQOu/7VmsM7OBdFntgotOJXALXFqCeT2PMXyWVc9/6ObUZj
z9LQUlT6mnzYwFrX4mPPOTY5nvCyjepQlSDA7w49yaRhXKCFRHmEieeFJqzrZoQG
'''

der = priv_part.decode('base64')
q_pre = der[44:].encode('hex')

kbits = 29 * 8
q_bar = int(q_pre + '0' * (29 * 2), 16)

PR.<x> = PolynomialRing(Zmod(n))
f = x + q_bar

x0 = f.small_roots(X=2^kbits, beta=0.3)[0]
q = x0 + q_bar
print q

この結果から、p, qは以下の通りとわかる。

q = 146549045227354172989110651205310632574067392372993711861623526130946979713469625772410411197033006823693645223316947254702263484103463390279967082549781844195965622071604103417650285219901124684816890970225510506869249766243257198851929421990982433654502509027141033118789478594390852225097012248592818058247
p = 163982139712862418555526520701188853132435025142588334581109287244065993155706892302449577647543501705795708316995057467949529976798218410513821698432879399377481736303821213515873396833696040164615779257072417113571942677691455176550027493593024586313878742269786944829130979576180492741390980797445630429239

秘密鍵を生成する。

$ rsatool.py -f PEM -o privkey.pem -p 163982139712862418555526520701188853132435025142588334581109287244065993155706892302449577647543501705795708316995057467949529976798218410513821698432879399377481736303821213515873396833696040164615779257072417113571942677691455176550027493593024586313878742269786944829130979576180492741390980797445630429239 -q 146549045227354172989110651205310632574067392372993711861623526130946979713469625772410411197033006823693645223316947254702263484103463390279967082549781844195965622071604103417650285219901124684816890970225510506869249766243257198851929421990982433654502509027141033118789478594390852225097012248592818058247
Using (p, q) to initialise RSA instance

n =
be5d958b09b2291cf0bd36511c9155e229f8ae8dccaee1552c9669b81b532a363b4f34769412867c
cf92cb40addef5200a05dcdef09c8da30982fa5413d952f4e7db3da739519fab77d574de52366c96
03ace887c0cbf32c5247cec14228e8a72aa5256799e54c40f3a22d4642cdaf5e0dd077331158e7d8
4dba8756d531a4bb4d2ba3e79c29972f27eb8d0bf9df81e2e9cda23b0ddead23c00aaebfa0f53832
77a22177729a9cb5ee58c47019b6cb322d7fb9a41df3a2d562dfd202f9063b5e5e5042cfef6ddcfe
41232867e1c122a8dcc18ce51efbb8cc5f9bc0f3296f1091ca3010ed851273d4ca40675753da896a
e5fcfa01593a7c84d518c503c0aee581

e = 65537 (0x10001)

d =
620075bb457b95d4d34ee586ae6957c87e090b7beeb2dd486712ec4c1ead1adf1e7b712bd6a10ee1
744f431a0228f512d076223617b2d0ebed3aa3bae3190faf0b2a003c75b2c2bb988ea882c7da42de
9bf7c922122c2cfd5542a87b2f9f35ded18281962b51338780a5ae1f2cc70d1023967db729a8167b
71d0a45a1c99590f3c4bfa59f6cb99808d1b8c4e5c0ca7feeec7f2c88f6cee0a343be1f1217c23c2
ec0e779740374cffda319dc8797a0b010a58b0ad79e33adc3ca088dcbf4fdb68da954c49b3aa693f
0e0545d6845e3413d720a2df5c98158e4b45d2bd6e2ea08672db20644ea9aec7c192c1087b970564
cd929d43e5ea32f1c1e19a266adb84ed

p =
e984b0820151d7ed6a86569073ea12e64d36fa33bc360082cd1e87ad0618f6dd6f0dbac674170c3d
11f1e8ea1208c48ee3c6313f7703138fc2d2dc8e94fdd4a427bd92a420de8a025d0423e80351acaa
2c92bfe5e11729602dbf6536e649914bf6de449be89cd9acb0d27354488e973bbfb7b5c4fd4c0073
87de2df582e18837

q =
d0b1593944e0be69d6024c064a8ffa86e40ebbfed59ac33b3817459ed828b4e25700b5c5a82793d8
f317c9655cf7fe8e6d4663cfd2d05254fa9a7cd8c05ad7e263cf3936399ef0b28dea509520c0ef0e
3dc9a4615ca08544798489e78526aceb668406cb284ebe0ee0120defe7405ffe7d76fb6bb469183c
b262822c9b6f3407

Saving PEM as privkey.pem

この秘密鍵SSH接続する。

$ ssh -i privkey.pem ctf@web.angstromctf.com -p 3004
The authenticity of host '[web.angstromctf.com]:3004 ([162.243.30.173]:3004)' can't be established.
ECDSA key fingerprint is 85:61:bc:f6:51:7c:c9:44:ec:b3:bd:e3:f6:fc:d0:d6.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[web.angstromctf.com]:3004,[162.243.30.173]:3004' (ECDSA) to the list of known hosts.
Welcome to Ubuntu 16.04.4 LTS (GNU/Linux 4.4.0-116-generic x86_64)

 * Documentation:  https://help.ubuntu.com
 * Management:     https://landscape.canonical.com
 * Support:        https://ubuntu.com/advantage
actf{ssh_keys_not_broken_enough}
Connection to web.angstromctf.com closed.
actf{ssh_keys_not_broken_enough}