読者です 読者をやめる 読者になる 読者になる

Hack.lu 2013 CTF FluxArchiv 1&2 Write-up

気が向いたのでWrite-upを書く。

FluxArchiv (Part 1) (Reversing 400)

These funny humans try to exclude us from the delicious beer of the Oktoberfest! They made up a passcode for everyone who wants to enter the Festzelt. Sadly, our human informant friend could not learn the passcode for us. But he heard a conversation between two drunken humans, that they were using the same passcode for this intercepted archive file. They claimed that the format is is absolutely secure and solves any kind of security issue. It's written by this funny hacker group named FluxFingers. Real jerks if you ask me. Anyway, it seems that the capability of drunken humans to remember things is limited. So they just used a 6 character passcode with only numbers and upper-case letters. So crack this passcode and get our ticket to their delicious german beer!
Here is the challenge: https://ctf.fluxfingers.net/static/downloads/fluxarchiv/hacklu2013_archiv_challenge1.tar.gz

こんな感じ。

% tar zxvf hacklu2013_archiv_challenge1.tar.gz
hacklu2013_archiv_challenge1/
hacklu2013_archiv_challenge1/archiv
hacklu2013_archiv_challenge1/FluxArchiv.arc
% file hacklu2013_archiv_challenge1/archiv
hacklu2013_archiv_challenge1/archiv: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.26, BuildID[sha1]=0x0fa7f6566e2ff973c4d045b10f6f751898c70053, not stripped
% file hacklu2013_archiv_challenge1/FluxArchiv.arc
hacklu2013_archiv_challenge1/FluxArchiv.arc: data
% xxd -g 1 hacklu2013_archiv_challenge1/FluxArchiv.arc | head
0000000: 46 6c 75 58 41 72 43 68 69 56 31 33 37 29 42 df  FluXArChiV137)B.
0000010: 27 12 82 45 05 d8 17 1f 4f 0b cb 14 15 3d 39 ba  '..E....O....=9.
0000020: 94 75 7c 42 2d e5 a1 d1 7f 19 09 1a 61 d4 d2 85  .u|B-.......a...
0000030: d3 19 09 1a 61 d4 d2 85 c4 19 09 1a 61 d4 d2 85  ....a.......a...
0000040: 2d f3 33 48 35 14 8a ff 24 8a e9 fc 98 66 29 76  -.3H5...$....f)v
0000050: b3 6d 7d 7f 0f a0 bb ea 9f 42 6a 79 e1 e7 f6 ed  .m}......Bjy....
0000060: 52 5a 92 fb 17 a9 7d 8f 0e 48 09 af ff 4d b4 04  RZ....}..H...M..
0000070: e1 6f 19 5a a9 60 e8 20 25 6a 93 27 ed 09 b6 88  .o.Z.`. %j.'....
0000080: 93 f6 26 1d 27 26 3f 67 6b 77 54 8c cf cb 72 9c  ..&.'&?gkwT...r.
0000090: 70 1e bf 00 51 84 8f bd 54 d8 94 5b c5 81 17 73  p...Q...T..[...s

archivというのが独自形式のアーカイバで、そのアーカイバで作成されたFluxArchiv.arcというアーカイブファイルのパスワードを求めればいいらしい。

IDAで処理の流れを追った所、hash_of_passwordという配列にパスワードのSHA1ハッシュが格納されていて、そのハッシュを秘密鍵としてRC4でファイルを暗号化していた。hash_of_passwordを参照している部分を中心に見ていくと、verifyArchiv関数が以下の様な処理をしている事を発見した。

#!/usr/bin/env python
import sys
import hashlib

archive = ""
hash_of_password = ""

def verifyArchiv():
    SHUFFLE_TABLE = [0, 7, 14, 1, 8, 15, 2, 9, 16, 3, 10, 17, 4, 11, 18, 5, 12, 19, 6, 13]

    hash1_correct = ""
    with open(archive) as f:
        hash1_correct = f.read()[0x0C:0x20]

    hash0 = hash_of_password
    hash0_shuffled = ''.join([hash0[SHUFFLE_TABLE[i]] for i in xrange(20)])

    sha1 = hashlib.sha1()
    sha1.update(hash0_shuffled)
    hash1 = sha1.digest()

    return 1 if hash1 == hash1_correct else 0

def main(argv):
    global archive, hash_of_password
    archive = argv[1]
    password = argv[2]
    sha1 = hashlib.sha1()
    sha1.update(password)
    hash_of_password = sha1.digest()

    print 'OK' if verifyArchiv() else 'NG'

if __name__ == '__main__':
    main(sys.argv)

問題文によればパスワードは英数字大文字6文字という事だから、36 ** 6 = 約22億通りなのでなんとか総当りできるか。こんな感じのコードを書いた。

#!/usr/bin/env python
import hashlib
import string
import itertools
import multiprocessing
import sys

HASH1_CORRECT = open('FluxArchiv.arc').read()[0x0C:0x20]
CHARS = string.ascii_uppercase + string.digits
SHUFFLE_TABLE = [0, 7, 14, 1, 8, 15, 2, 9, 16, 3, 10, 17, 4, 11, 18, 5, 12, 19, 6, 13]

def test_password(pw):
    sha1 = hashlib.sha1()
    sha1.update(pw)
    hash0 = sha1.digest()

    hash0_shuffled = ''.join([hash0[SHUFFLE_TABLE[i]] for i in xrange(20)])

    sha1 = hashlib.sha1()
    sha1.update(hash0_shuffled)
    hash1 = sha1.digest()

    return hash1 == HASH1_CORRECT

def process(headch):
    for _pw in itertools.product(CHARS, repeat=5):
        if test_password(headch + ''.join(_pw)):
            print headch + ''.join(_pw)
            break

def main(argv):
    num_pool = int(argv[1])

    for i in xrange(0, len(CHARS), num_pool):
        pool = multiprocessing.Pool(processes=num_pool)
        pool.map(process, CHARS[i:min(i + num_pool, len(CHARS))])
        pool.close()

if __name__ == '__main__':
    main(sys.argv)

(multiprocessingの使い方これでいいのか知らない)

最初はシングルプロセスのコードだった。i5-3317U上のシングルプロセスで2~3時間程度回していたらヒットした。

% ./bruteforce.py
PWF41L

マルチプロセスのコードも書いて他の環境でも回してみたところ、Xeon X5570 * 2上の16プロセスとi7-3770上の8プロセスで、どちらも15分程度でヒットした。

FluxArchiv (Part 2) (Reversing 500)

These sneaky humans! They do not just use one passcode, but two to enter the Festzelt. We heard that the passcode is hidden inside the archive file. It seems that the FluxFingers overrated their programming skill and had a major logical flaw in the archive file structure. Some of the drunken Oktoberfest humans found it and abused this flaw in order to transfer hidden messages. Find this passcode so we can finally drink their beer!

(only solvable when FluxArchiv (Part 1) was solved)
Here is the challenge: https://ctf.fluxfingers.net/static/downloads/fluxarchiv/hacklu2013_archiv_challenge1.tar.gz

archivのロジックの欠陥を利用してFluxArchiv.arcの中にフラグが隠してあるという事らしい。FluxArchiv.arcに格納されているファイル4つを全てarchivで展開して調べたが、もちろん何も無かった。

FluxArchiv.arcは先頭32bytesのヘッダと1040bytesのブロックの繰り返しで構成されているので、全てのブロックの中にどのファイルでも使われていないブロックが有るのではないかという推測が立った。格納されているファイルが使用しているブロックの一覧等の情報を出力するコードを書いた。

#!/usr/bin/env python
import hashlib
import sys
from struct import pack, unpack
from Crypto.Cipher import ARC4

# 'FluXL1sT'
MAGIC_FILEENTRY = pack('<Q', 0x5473314C58756C46)
# sha1('PWF41L')
KEY = '328042503975adb0c62f536d8416b5f78babea15'.decode('hex')
ARCFILE = open(sys.argv[1])
BLOCKSIZE = 0x410

def read_archive(length):
    rc4 = ARC4.new(KEY)
    dec = rc4.decrypt(ARCFILE.read(length))
    return dec

def list_blocks(blocki, blocknum):
    blocklist = [blocki]

    for blockcnt in xrange(blocknum - 1):
        ARCFILE.seek(0x20 + blocki * BLOCKSIZE)
        blocki = unpack('<Q', read_archive(0x08))[0]
        blocklist.append(blocki)

    return blocklist

def main(argv):
    blocki = 0
    ARCFILE.seek(0x20)
    while read_archive(0x08) == MAGIC_FILEENTRY:
        for filei in xrange(8):
            ARCFILE.seek((0x20 + 0x10 + blocki * BLOCKSIZE) + filei * 0x80)
            blocki_start = unpack('<Q', read_archive(0x08))[0]
            blocknum = unpack('<Q', read_archive(0x08))[0]
            if blocki_start != 0:
                print 'FILE %d:' % filei
                print '  index of start block: 0x%08x' % blocki_start
                print '  number of blocks: 0x%08x' % blocknum
                print '  md5sum: %s' % read_archive(0x10).encode('hex')
                print '  filename: %s' % read_archive(0x60).rstrip('\x00')
                print '  blocks: %s' % ', '.join(map(str, list_blocks(blocki_start, blocknum)))

        # next file entry
        ARCFILE.seek(0x20 + 0x08 + blocki * BLOCKSIZE)
        blocki = unpack('<Q', read_archive(0x08))[0]
        if blocki != 0:
            print '\nindex of next file entry block: 0x%08x\n' % blocki
            ARCFILE.seek(0x20 + blocki * BLOCKSIZE)
        else:
            break

if __name__ == '__main__':
    main(sys.argv)

(元のコードが残念だったので終わってからかなり書き直した。)

出力結果。

FILE 0:
  index of start block: 0x00000001
  number of blocks: 0x00000016
  md5sum: ffea3a5254c0587ad5b2ece81be8bab5
  filename: attentionzombie.mp3
  blocks: 1, 3, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157
FILE 1:
  index of start block: 0x00000002
  number of blocks: 0x00000086
  md5sum: ec5638da4810f75e0735a3df9e30c1b0
  filename: Did_You_Know.jpg
  blocks: 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136
FILE 3:
  index of start block: 0x00000089
  number of blocks: 0x00000009
  md5sum: 2bee8bec6c1a8ad658dffbe14bc14792
  filename: fluxfingers.png
  blocks: 137, 162, 163, 164, 165, 166, 167, 168, 169

index of next file entry block: 0x000000ad

FILE 4:
  index of start block: 0x000000b2
  number of blocks: 0x0000007e
  md5sum: f1df033f0179fe101d11700fe796b4fd
  filename: th_oh-noes-everybody-panic.gif
  blocks: 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303

使用されているブロックを調べるとブロック158-161, 170-177のがどのファイルからも使われていない事が分かったので、適当に復号して調べたら、ブロック160でflagを見つけた。

#!/usr/bin/env python
import sys
from struct import pack, unpack
from Crypto.Cipher import ARC4

# sha1('PWF41L')
KEY = '328042503975adb0c62f536d8416b5f78babea15'.decode('hex')
ARCFILE = open(sys.argv[1])
BLOCKSIZE = 0x410

def read_archive(length):
    rc4 = ARC4.new(KEY)
    dec = rc4.decrypt(ARCFILE.read(length))
    return dec

def main(argv):
    blocki = int(argv[2])
    outfile = argv[3]

    ARCFILE.seek(0x20 + blocki * BLOCKSIZE)
    with open(outfile, 'w') as f:
        f.write(read_archive(0x08) + read_archive(BLOCKSIZE - 0x08))

if __name__ == '__main__':
    main(sys.argv)
% xxd -g 1 block160.bin
0000000: 00 00 00 00 00 00 00 00 65 20 65 6c 65 63 74 72  ........e electr
0000010: 6f 6e 20 61 6e 64 20 74 68 65 20 73 77 69 74 63  on and the switc
0000020: 68 2c 20 74 68 65 0a 62 65 61 75 74 79 20 6f 66  h, the.beauty of
...
00003a0: 20 4d 65 6e 74 6f 72 2b 2b 2b 0a 0a 46 6c 61 67   Mentor+++..Flag
00003b0: 3a 20 44 33 6c 65 74 69 6e 47 2d 31 6e 64 33 78  : D3letinG-1nd3x
00003c0: 5f 46 34 69 4c 0a 0a 1f 16 f8 73 37 72 64 c5 5c  _F4iL.....s7rd.\
...

どうでもいいけどこんなのとかもあった。

% xxd -g 1 block161.bin | head -n 2
0000000: 00 00 00 00 00 00 00 00 44 69 64 20 59 6f 75 20  ........Did You
0000010: 4b 6e 6f 77 00 00 00 00 00 00 00 00 00 00 00 00  Know............
% xxd -g 1 block170.bin | head -n 2
0000000: 00 00 00 00 00 00 00 00 54 68 61 74 20 47 6f 64  ........That God
0000010: 73 20 4f 66 20 44 65 61 74 68 00 00 00 00 00 00  s Of Death......
% xxd -g 1 block171.bin | head -n 2
0000000: 00 00 00 00 00 00 00 00 4c 6f 76 65 73 20 41 70  ........Loves Ap
0000010: 70 6c 65 73 3f 00 00 00 00 00 00 00 00 00 00 00  ples?...........