INS'hAck 2019 Writeup

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

Sanity (Misc 1)

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

INSA{Welcome}

Telegram (Misc 50)

Telegramのリンク先にアクセスすると、フラグが書かれている。
f:id:satou-y:20190509071807p:plain

INSA{is_e2e_8annEd_1n_Russi4_too}

Dashlame - Part 1 (Reverse 50)

Easy Python Decompilerでpycをデコンパイルする。

# Embedded file name: dashlame.py
from Crypto.Cipher import AES
import os
import random
import sys
import sqlite3
import time
import zlib
HEADER = "      /.m.\\\n     /.mnnm.\\                                              ___\n    |.mmnvvnm.\\.                                     .,,,/`mmm.\\\n    |.mmnnvvnm.\\:;,.                           ..,,;;;/.mmnnnmm.\\\n    \\ mmnnnvvnm.\\::;;,                    .,;;;;;;;;/.mmmnnvvnnm.|\n     \\`mmnnnvvnm.\\::;::.sSSs      sSSs ,;;;;;;;;;;/.mmmnnvvvnnmm'/\n       \\`mmnnnvnm.\\:::::SSSS,,,,,,SSSS:::::::;;;/.mmmnnvvvnnmmm'/\n          \\`mnvvnm.\\::%%%;;;;;;;;;;;%%%%:::::;/.mnnvvvvnnmmmmm'/\n             \\`mmmm.%%;;;;;%%%%%%%%%%%%%%%::/.mnnvvvnnmmmmm'/ '\n                \\`%%;;;;%%%%s&&&&&&&&&s%%%%mmmnnnmmmmmm'/ '\n     |           `%;;;%%%%s&&.%%%%%%.%&&%mmmmmmmmmm'/ '\n\\    |    /       %;;%%%%&&.%;`    '%.&&%%%////// '\n  \\  |  /         %%%%%%s&.%%   x   %.&&%%%%%//%\n    \\  .:::::.  ,;%%%%s&&&&.%;     ;.&&%%%%%%%%/,\n-!!!- ::#:::::%%%%%%s&&&&&&&&&&&&&&&&&%%%%%%%%%%%\n    / :##:::::&&&&&&&&&&&&&&&&&&&&&%%%%%%%%%%%%%%,\n  /  | `:#:::&&&&&&&&&&&&&&&&&&&&&&&&%%%%%%%%%%%%%\n     |       `&&&&&&&&&,&&&&&&&&&&&&SS%%%%%%%%%%%%%\n               `~~~~~'~~        SSSSSSS%%%%%%%%%%%%%\n                               SSSSSSSS%%%%%%%%%%%%%%\n                              SSSSSSSSSS%%%%%%%%%%%%%.\n                            SSSSSSSSSSSS%%%%%%%%%%%%%%\n                          SSSSSSSSSSSSS%%%%%%%%%%%%%%%.\n                        SSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%\n                      SSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%.\n                    SSSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%%%\n                  SSSSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%%%%.\n\n                          WELCOME TO DASHLAME\n"
PEARSON_TABLE = [199,
 229,
 151,
 178,
 53,
 6,
 131,
 42,
 248,
 110,
 39,
 28,
 51,
 216,
 32,
 14,
 77,
 34,
 166,
 213,
 157,
 150,
 115,
 197,
 228,
 221,
 254,
 172,
 84,
 27,
 36,
 156,
 69,
 96,
 12,
 220,
 225,
 137,
 246,
 141,
 44,
 208,
 191,
 109,
 163,
 21,
 173,
 250,
 98,
 227,
 203,
 162,
 188,
 3,
 105,
 171,
 215,
 15,
 207,
 218,
 234,
 56,
 136,
 235,
 97,
 79,
 189,
 102,
 134,
 11,
 224,
 117,
 177,
 222,
 100,
 129,
 78,
 18,
 130,
 187,
 9,
 184,
 99,
 108,
 202,
 13,
 238,
 17,
 94,
 70,
 180,
 144,
 185,
 168,
 123,
 71,
 176,
 91,
 4,
 153,
 103,
 242,
 80,
 127,
 198,
 82,
 169,
 148,
 48,
 120,
 59,
 55,
 230,
 209,
 50,
 73,
 31,
 49,
 142,
 149,
 167,
 249,
 116,
 1,
 7,
 86,
 143,
 101,
 29,
 52,
 114,
 154,
 160,
 128,
 19,
 170,
 46,
 214,
 38,
 67,
 186,
 252,
 181,
 145,
 212,
 183,
 22,
 231,
 107,
 43,
 47,
 122,
 251,
 217,
 5,
 62,
 88,
 244,
 200,
 93,
 240,
 219,
 124,
 58,
 161,
 89,
 211,
 158,
 247,
 60,
 236,
 65,
 106,
 113,
 66,
 81,
 165,
 194,
 223,
 40,
 233,
 126,
 139,
 72,
 132,
 61,
 135,
 57,
 87,
 182,
 164,
 35,
 159,
 118,
 8,
 83,
 210,
 243,
 104,
 76,
 75,
 119,
 90,
 138,
 20,
 206,
 95,
 16,
 74,
 33,
 245,
 237,
 111,
 64,
 253,
 125,
 23,
 232,
 193,
 37,
 175,
 92,
 30,
 241,
 255,
 133,
 0,
 140,
 2,
 155,
 85,
 10,
 146,
 179,
 25,
 26,
 226,
 201,
 195,
 121,
 190,
 63,
 68,
 152,
 45,
 147,
 41,
 204,
 192,
 205,
 196,
 54,
 174,
 239,
 112,
 24]

def pad(s):
    mark = chr(16 - len(s) % 16)
    while len(s) % 16 != 15:
        s += chr(random.randint(0, 255))

    return s + mark


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


def get_random_passphrase():
    sys.stdout.write('Getting random data from atmospheric noise and mouse movements')
    sys.stdout.flush()
    for i in range(10):
        sys.stdout.write('.')
        sys.stdout.flush()
        time.sleep(random.randint(1, 20) / 10.0)

    print ''
    with open('wordlist.txt', 'rb') as fi:
        passwords = fi.read().strip().split('\n')
    return (random.choice(passwords), random.choice(passwords))


def get_pearson_hash(passphrase):
    key, iv = ('', '')
    for i in range(32):
        h = (i + ord(passphrase[0])) % 256
        for c in passphrase[1:]:
            h = PEARSON_TABLE[h ^ ord(c)]

        if i < 16:
            key += chr(h)
        else:
            iv += chr(h)

    return (key, iv)


def encrypt_stream(data, passphrase):
    key, iv = get_pearson_hash(passphrase)
    aes = AES.new(key, AES.MODE_CBC, iv)
    data = pad(data)
    return aes.encrypt(data)


def decrypt_stream(data, passphrase):
    key, iv = get_pearson_hash(passphrase)
    aes = AES.new(key, AES.MODE_CBC, iv)
    data = unpad(aes.decrypt(data))
    return data


def encrypt_archive(archive_filename, passphraseA, passphraseB):
    with open(archive_filename, 'rb') as db_fd:
        with open(archive_filename.replace('.db', '.dla'), 'wb') as dla_fd:
            enc1 = encrypt_stream(db_fd.read(), passphraseA)
            enc2 = encrypt_stream(enc1, passphraseB)
            dla_fd.write(enc2)
    os.unlink(archive_filename)


def decrypt_archive(archive_filename, passphraseA, passphraseB):
    with open(archive_filename, 'rb') as dla_fd:
        with open(archive_filename.replace('.dla', '.db'), 'wb') as db_fd:
            dec1 = decrypt_stream(dla_fd.read(), passphraseB)
            dec2 = decrypt_stream(dec1, passphraseA)
            db_fd.write(dec2)
    os.unlink(archive_filename)


def createArchive():
    archive_name = raw_input('Please enter your archive name: ')
    passphraseA, passphraseB = get_random_passphrase()
    print 'This is your passphrase :', passphraseA, passphraseB
    print 'Please remember it or you will lose all your passwords.'
    archive_filename = archive_name + '.db'
    with open(archive_filename, 'wb') as db_fd:
        db_fd.write(zlib.decompress('x\x9c\x0b\x0e\xf4\xc9,IUH\xcb/\xcaM,Q0f`a`ddpPP````\x82b\x18`\x04b\x164>!\xc0\xc4\xa0\xfb\x8c\x9b\x17\xa4\x98y.\x03\x10\x8d\x82Q0\n\x88\x05\x89\x8c\xec\xe2\xf2\xf2\x8c\x8d\x82%\x89I9\xa9\x01\x89\xc5\xc5\xe5\xf9E)\xc5p\x06\x93s\x90\xabc\x88\xabB\x88\xa3\x93\x8f\xab\x02\\X\xa3<5\xa9\x18\x94\xabC\\#Bt\x14J\x8bS\x8b\xf2\x12sa\xdc\x02\xa820W\x13\x927\xcf0\x00\xd1(\x18\x05\xa3`\x08\x03#F\x16mYkh\xe6\x8fO\xadH\xcc-\xc8I\x85\xe5~O\xbf`\xc7\xea\x90\xcc\xe2\xf8\xa4\xd0\x92\xf8\xc4\xf8`\xe7"\x93\x92\xe4\x8cZ\x00\xa8&=\x8f'))
    encrypt_archive(archive_filename, passphraseA, passphraseB)
    print 'Archive created successfully.'


def updateArchive():
    archive_name = raw_input('Please enter your archive name: ')
    passphrase = raw_input('Please enter your passphrase: ')
    passphraseA, passphraseB = passphrase.split()
    website = raw_input('Website: ')
    username = raw_input('Username: ')
    password = raw_input('Password: ')
    dla_filename = archive_name + '.dla'
    db_filename = archive_name + '.db'
    decrypt_archive(dla_filename, passphraseA, passphraseB)
    conn = sqlite3.connect(db_filename)
    cur = conn.cursor()
    cur.execute('INSERT INTO Passwords VALUES(?,?,?)', (website, username, password))
    conn.commit()
    conn.close()
    encrypt_archive(db_filename, passphraseA, passphraseB)
    print 'Update done.'


def accessArchive():
    archive_name = raw_input('Please enter your archive name: ')
    passphrase = raw_input('Please enter your passphrase: ')
    passphraseA, passphraseB = passphrase.split()
    website = raw_input('Website: ')
    dla_filename = archive_name + '.dla'
    db_filename = archive_name + '.db'
    decrypt_archive(dla_filename, passphraseA, passphraseB)
    conn = sqlite3.connect(db_filename)
    cur = conn.cursor()
    cur.execute('SELECT Username, Password FROM Passwords WHERE Website=?', (website,))
    results = cur.fetchall()
    conn.close()
    encrypt_archive(db_filename, passphraseA, passphraseB)
    if len(results) == 0:
        print 'No results.'
    else:
        for result in results:
            print result[0], ':', result[1]


if __name__ == '__main__':
    print HEADER
    print '1. Create a new password archive'
    print '2. Add a password to an archive'
    print '3. Access a password from an existing archive'
    try:
        res = raw_input()
        if res == '1':
            createArchive()
        elif res == '2':
            updateArchive()
        elif res == '3':
            accessArchive()
        else:
            print 'Wrong choice'
    except:
        print 'Error.'

dbを暗号化してdlaを作成したあと、dbを削除している。dbを削除する処理をコメントアウトして実行してみる。

$ python dashlame.py
      /.m.\
     /.mnnm.\                                              ___
    |.mmnvvnm.\.                                     .,,,/`mmm.\
    |.mmnnvvnm.\:;,.                           ..,,;;;/.mmnnnmm.\
    \ mmnnnvvnm.\::;;,                    .,;;;;;;;;/.mmmnnvvnnm.|
     \`mmnnnvvnm.\::;::.sSSs      sSSs ,;;;;;;;;;;/.mmmnnvvvnnmm'/
       \`mmnnnvnm.\:::::SSSS,,,,,,SSSS:::::::;;;/.mmmnnvvvnnmmm'/
          \`mnvvnm.\::%%%;;;;;;;;;;;%%%%:::::;/.mnnvvvvnnmmmmm'/
             \`mmmm.%%;;;;;%%%%%%%%%%%%%%%::/.mnnvvvnnmmmmm'/ '
                \`%%;;;;%%%%s&&&&&&&&&s%%%%mmmnnnmmmmmm'/ '
     |           `%;;;%%%%s&&.%%%%%%.%&&%mmmmmmmmmm'/ '
\    |    /       %;;%%%%&&.%;`    '%.&&%%%////// '
  \  |  /         %%%%%%s&.%%   x   %.&&%%%%%//%
    \  .:::::.  ,;%%%%s&&&&.%;     ;.&&%%%%%%%%/,
-!!!- ::#:::::%%%%%%s&&&&&&&&&&&&&&&&&%%%%%%%%%%%
    / :##:::::&&&&&&&&&&&&&&&&&&&&&%%%%%%%%%%%%%%,
  /  | `:#:::&&&&&&&&&&&&&&&&&&&&&&&&%%%%%%%%%%%%%
     |       `&&&&&&&&&,&&&&&&&&&&&&SS%%%%%%%%%%%%%
               `~~~~~'~~        SSSSSSS%%%%%%%%%%%%%
                               SSSSSSSS%%%%%%%%%%%%%%
                              SSSSSSSSSS%%%%%%%%%%%%%.
                            SSSSSSSSSSSS%%%%%%%%%%%%%%
                          SSSSSSSSSSSSS%%%%%%%%%%%%%%%.
                        SSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%
                      SSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%.
                    SSSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%%%
                  SSSSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%%%%.

                          WELCOME TO DASHLAME

1. Create a new password archive
2. Add a password to an archive
3. Access a password from an existing archive
1
Please enter your archive name: nora
Getting random data from atmospheric noise and mouse movements..........
This is your passphrase : foundationalist oudated
Please remember it or you will lose all your passwords.
Archive created successfully.

作成されたdbをDB Browserで開き、Passwordsテーブルを見ると、フラグが格納されていた。
f:id:satou-y:20190509072056p:plain

INSA{Tis_bUt_a_SCr4tch}

Dashlame - Part 2 (Crypto 400)

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

パスフレーズ2つをwordlist.txtから選択
・DBファイルを生成
・パスフレーズAでAES暗号化、さらにパスフレーズBでAES暗号化

ブルートフォースパスフレーズを探り、復号してSQLiteファイルのヘッダ部になるよう復号する。

from Crypto.Cipher import AES
import random

PEARSON_TABLE = [199,
 229,
 151,
 178,
 53,
 6,
 131,
 42,
 248,
 110,
 39,
 28,
 51,
 216,
 32,
 14,
 77,
 34,
 166,
 213,
 157,
 150,
 115,
 197,
 228,
 221,
 254,
 172,
 84,
 27,
 36,
 156,
 69,
 96,
 12,
 220,
 225,
 137,
 246,
 141,
 44,
 208,
 191,
 109,
 163,
 21,
 173,
 250,
 98,
 227,
 203,
 162,
 188,
 3,
 105,
 171,
 215,
 15,
 207,
 218,
 234,
 56,
 136,
 235,
 97,
 79,
 189,
 102,
 134,
 11,
 224,
 117,
 177,
 222,
 100,
 129,
 78,
 18,
 130,
 187,
 9,
 184,
 99,
 108,
 202,
 13,
 238,
 17,
 94,
 70,
 180,
 144,
 185,
 168,
 123,
 71,
 176,
 91,
 4,
 153,
 103,
 242,
 80,
 127,
 198,
 82,
 169,
 148,
 48,
 120,
 59,
 55,
 230,
 209,
 50,
 73,
 31,
 49,
 142,
 149,
 167,
 249,
 116,
 1,
 7,
 86,
 143,
 101,
 29,
 52,
 114,
 154,
 160,
 128,
 19,
 170,
 46,
 214,
 38,
 67,
 186,
 252,
 181,
 145,
 212,
 183,
 22,
 231,
 107,
 43,
 47,
 122,
 251,
 217,
 5,
 62,
 88,
 244,
 200,
 93,
 240,
 219,
 124,
 58,
 161,
 89,
 211,
 158,
 247,
 60,
 236,
 65,
 106,
 113,
 66,
 81,
 165,
 194,
 223,
 40,
 233,
 126,
 139,
 72,
 132,
 61,
 135,
 57,
 87,
 182,
 164,
 35,
 159,
 118,
 8,
 83,
 210,
 243,
 104,
 76,
 75,
 119,
 90,
 138,
 20,
 206,
 95,
 16,
 74,
 33,
 245,
 237,
 111,
 64,
 253,
 125,
 23,
 232,
 193,
 37,
 175,
 92,
 30,
 241,
 255,
 133,
 0,
 140,
 2,
 155,
 85,
 10,
 146,
 179,
 25,
 26,
 226,
 201,
 195,
 121,
 190,
 63,
 68,
 152,
 45,
 147,
 41,
 204,
 192,
 205,
 196,
 54,
 174,
 239,
 112,
 24]

def pad(s):
    mark = chr(16 - len(s) % 16)
    while len(s) % 16 != 15:
        s += chr(random.randint(0, 255))

    return s + mark

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

def get_pearson_hash(passphrase):
    key, iv = ('', '')
    for i in range(32):
        h = (i + ord(passphrase[0])) % 256
        for c in passphrase[1:]:
            h = PEARSON_TABLE[h ^ ord(c)]

        if i < 16:
            key += chr(h)
        else:
            iv += chr(h)

    return (key, iv)

def encrypt_stream(data, passphrase):
    key, iv = get_pearson_hash(passphrase)
    aes = AES.new(key, AES.MODE_CBC, iv)
    data = pad(data)
    return aes.encrypt(data)


def decrypt_stream(data, passphrase):
    key, iv = get_pearson_hash(passphrase)
    aes = AES.new(key, AES.MODE_CBC, iv)
    data = unpad(aes.decrypt(data))
    return data

with open('admin.dla', 'rb') as f:
    dla = f.read()

with open('wordlist.txt', 'r') as f:
    wl = f.read()

words = wl.split('\n')[:-1]

SQLITE_HEADER = 'SQLite format 3\x00'

enc_list = {}
for word in words:
    enc = encrypt_stream(SQLITE_HEADER, word)
    enc_list[enc[:16]] = word

for word in words:
    dec1 = decrypt_stream(dla, word)
    if dec1[:16] in enc_list:
        word2 = enc_list[dec1[:16]]
        print word2, word
        dec2 = decrypt_stream(dec1, word2)
        break

with open('admin.db', 'wb') as f:
    f.write(dec2)

復号を試した結果、以下のパスフレーズで暗号化したことがわかる。

spanish inquisition

復号したdbをDB Browserで開き、Passwordsテーブルを見ると、フラグが格納されていた。
f:id:satou-y:20190509072331p:plain

INSA{D0_you_f1nD_it_Risible_wh3N_I_s4y_th3_name}

Jean-Sébastien Bash (Crypto 500)

コマンドをAES-CBC暗号化したものを指定すると、そのコマンドが実行される。例としてls -l の暗号化データのみがわかっている。flag.txtがあるので、その内容を見ることができればよい。いろいろ試した結果、CBC Oracle Padding Attackで2ブロック目でcat flag.txtに復号できるような暗号データを割り出すことができればフラグが得られそう。
本来はプログラムでやりたいところだが、SSHでこのttyに接続する方法がわからず、手動でCBC Oracle Padding Attackを実行する。

$ ssh -i ~/.ssh/id_inshack -p 2227 user@jean-sebastien-bash.ctf.insecurity-insa.fr
The authenticity of host '[jean-sebastien-bash.ctf.insecurity-insa.fr]:2227 ([51.83.110.181]:2227)' can't be established.
ECDSA key fingerprint is SHA256:Hp/VF/ZZ75+zXkpM05kpIoN/0YXe5Fqlt+pTr3O/kVE.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[jean-sebastien-bash.ctf.insecurity-insa.fr]:2227,[51.83.110.181]:2227' (ECDSA) to the list of known hosts.
 ___           _   _            _      ____   ___  _  ___
|_ _|_ __  ___| | | | __ _  ___| | __ |___ \ / _ \/ |/ _ \
| || '_ \/ __| |_| |/ _` |/ __| |/ /   __) | | | | | (_) |
| || | | \__ \  _  | (_| | (__|   <   / __/| |_| | |\__, |
|___|_| |_|___/_| |_|\__,_|\___|_|\_\ |_____|\___/|_|  /_/

===========================================================

      You are accessing a sandbox challenge over SSH
        This sandbox will be killed soon enough.
       Please wait while we launch your sandbox...

===========================================================
Welcome on my server. /help for help  

>/help
This is a tool so that only me can execute commands on my server
(without all the GNU/Linux mess around users and rights).

- /help for help
- /exit to quit
- /cmd <encrypted> to execute a command

Notes (TODO REMOVE THAT) ---------------------------
Ex: 
/cmd AES(key, CBC, iv).encrypt(my_command)
/cmd 7bcfab368dc137d4628dcf45d41f8885


>/cmd 7bcfab368dc137d4628dcf45d41f8885
Running b'ls -l'
total 8
-rw-r--r-- 1 root root   21 Apr 25 21:18 flag.txt
-rwxr-xr-x 1 root root 2066 Apr 25 21:50 server.py

/cmd 7bcfab368dc137d4628dcf45d41f88007bcfab368dc137d4628dcf45d41f8885
What do you mean?!

/cmd 7bcfab368dc137d4628dcf45d41f88017bcfab368dc137d4628dcf45d41f8885
What do you mean?!

/cmd 7bcfab368dc137d4628dcf45d41f88027bcfab368dc137d4628dcf45d41f8885
What do you mean?!

/cmd 7bcfab368dc137d4628dcf45d41f88037bcfab368dc137d4628dcf45d41f8885
What do you mean?!

/cmd 7bcfab368dc137d4628dcf45d41f88047bcfab368dc137d4628dcf45d41f8885
What do you mean?!

/cmd 7bcfab368dc137d4628dcf45d41f88057bcfab368dc137d4628dcf45d41f8885
What do you mean?!

/cmd 7bcfab368dc137d4628dcf45d41f88067bcfab368dc137d4628dcf45d41f8885
What do you mean?!

/cmd 7bcfab368dc137d4628dcf45d41f88077bcfab368dc137d4628dcf45d41f8885
Running b'\x1c\x01\xae\xa8\x95\x1b\x02\xa4\x1b{\xe8\x152,\xcb\xf96\xe6\xba]\xda\xe7\x0c\x86\x02\xd6\xa1-\xe3r\xcc'
sh: 1: ����{�2,��6��]��
                             �֡-�r�: not found

これでXORする前の7bcfab368dc137d4628dcf45d41f8885の復号したデータがわかった。あとは前がどんな文字列であっても2ブロック目が ; cat flag.txtに復号できる暗号データを計算してやる。

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

def pad(s):
    p = 16 - len(s) % 16
    return s + chr(p) * p

ct1 = '7bcfab368dc137d4628dcf45d41f88077bcfab368dc137d4628dcf45d41f8885'.decode('hex')
pt1 = '\x1c\x01\xae\xa8\x95\x1b\x02\xa4\x1b{\xe8\x152,\xcb\xf96\xe6\xba]\xda\xe7\x0c\x86\x02\xd6\xa1-\xe3r\xcc'

ct1_1 = ct1[:16]
pt1_2 = pad(pt1[16:])

pt2_2 = pad(' ; cat flag.txt')
ct2_1 = str_xor(str_xor(ct1_1, pt1_2), pt2_2)
ct2_2 = ct1[16:]

ct2 = (ct2_1 + ct2_2).encode('hex')
print ct2

この結果、暗号データは以下のようになる。

6d12310836521b340c3a0946431530077bcfab368dc137d4628dcf45d41f8885
>/cmd 6d12310836521b340c3a0946431530077bcfab368dc137d4628dcf45d41f8885
Running b'.\x15\xabh\xa1\x18\xd2\x88\xbeF\x7f\xdb\x12\xf9\xc4\xd7 ; cat flag.txt'
sh: 1: .�h�҈�F����: not found
INSA{or4cle_P4dd1ng}
INSA{or4cle_P4dd1ng}

Yet Another RSA Challenge - Part 1 (Crypto 500)

RSA暗号で、N、e、pの16進表記で'9F'を'FC'に置換したものと、cがわかっている。pの'FC'の一部を'9F'に置換することをブルートフォースで試して、Nを割り切れるものを探す。pがわかれば、qもわかり復号することができる。

from Crypto.Util.number import *
import itertools

def gen_p(str_p, t):
    p = str_p
    for e in t:
        p = p[:e] + '9F' + p[e + 2:]
    return eval(p)

with open('output.txt', 'r') as f:
    N = int(f.readline().rstrip())
    str_p_rep = f.readline().rstrip()
    c = int(f.readline().rstrip())

e = 65537

idxes = []
index = 0
while True:
    index = str_p_rep.find('FC', index)
    if index < 0:
        break
    idxes.append(index)
    index += 1

found = False
for i in range(1, len(idxes) + 1):
    for j in list(itertools.combinations(idxes, i)):
        p = gen_p(str_p_rep, j)
        if N % p == 0:
            found = True
            break
    if found:
        break

assert N % p == 0

q = N / p

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)

flag = long_to_bytes(m)
print flag
INSA{I_w1ll_us3_OTp_n3xT_T1M3}

Yet Another RSA Challenge - Part 2 (Programming 222)

Part1と同様の問題。ただ、pが複数の文字のセットを置換しているので、難易度が上がっている。解き方は同様だが、プログラムとしては複雑化しているので、さまざまな箇所で注意が必要。

from Crypto.Util.number import *
import itertools

def get_idx(str_p, to_str):
    idxes = []
    index = 0
    while True:
        index = str_p.find(to_str, index)
        if index < 0:
            break
        idxes.append(index)
        index += 1
    return idxes

def gen_p(str_p, t, from_str):
    p = str_p
    for e in t:
        p = p[:e] + from_str + p[e + 2:]
    return p

with open('output.txt', 'r') as f:
    N = int(f.readline().rstrip())
    str_p_rep = f.readline().rstrip()
    c = int(f.readline().rstrip())

e = 65537

found = False
str_p = str_p_rep

idx0 = get_idx(str_p, '3E')
for i0 in range(1, len(idx0) + 1):
    for c0 in list(itertools.combinations(idx0, i0)):
        str_p0 = gen_p(str_p, c0, '59')

        idx1 = get_idx(str_p0, 'E0')
        for i1 in range(0, len(idx1) + 1):
            for c1 in list(itertools.combinations(idx1, i1)):
                str_p1 = gen_p(str_p0, c1, '9E')

                idx2 = get_idx(str_p1, '89')
                for i2 in range(0, len(idx2) + 1):
                    for c2 in list(itertools.combinations(idx2, i2)):
                        str_p2 = gen_p(str_p1, c2, '6B')

                        idx3 = get_idx(str_p2, '38')
                        for i3 in range(0, len(idx3) + 1):
                            for c3 in list(itertools.combinations(idx3, i3)):
                                str_p3 = gen_p(str_p2, c3, 'E4')

                                idx4 = get_idx(str_p3, '95')
                                for i4 in range(0, len(idx4) + 1):
                                    for c4 in list(itertools.combinations(idx4, i4)):
                                        str_p4 = gen_p(str_p3, c4, '09')

                                        idx5 = get_idx(str_p4, 'FF')
                                        for i5 in range(0, len(idx5) + 1):
                                            for c5 in list(itertools.combinations(idx5, i5)):
                                                str_p5 = gen_p(str_p4, c5, '5E')

                                                idx6 = get_idx(str_p5, 'D4')
                                                for i6 in range(0, len(idx6) + 1):
                                                    for c6 in list(itertools.combinations(idx6, i6)):
                                                        str_p6 = gen_p(str_p5, c6, '33')

                                                        idx7 = get_idx(str_p6, '8D')
                                                        for i7 in range(0, len(idx7) + 1):
                                                            for c7 in list(itertools.combinations(idx7, i7)):
                                                                str_p7 = gen_p(str_p6, c7, '12')

                                                                p = eval(str_p7)
                                                                if N % p == 0:
                                                                    found = True
                                                                    break
                                                            if found:
                                                                break

                                                        if found:
                                                            break
                                                    if found:
                                                        break

                                                if found:
                                                    break
                                            if found:
                                                break

                                        if found:
                                            break
                                    if found:
                                        break

                                if found:
                                    break
                            if found:
                                break

                        if found:
                            break
                    if found:
                        break

                if found:
                    break
            if found:
                break

        if found:
            break
    if found:
        break

assert N % p == 0

q = N / p

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)

flag = long_to_bytes(m)
print flag
INSA{Uh_never_give_4w4y_your_Pr1mes_I_m34n_duhhh}