h_nosonの日記

競プロ、CTFなど

VolgaCTF 2018 Quals writeup

Ping [Pwn 10]

python -c 'print "A" * 0x101' | nc ping2.quals.2018.volgactf.ru 45678

Lights [Rev 100]

armのELFが与えられる。qemuで実行すると/dev/gpiomemがないと言われるのでraspberry piで実行してみる。straceをすると750msと250msのsleepを繰り返していることがわかる。バイナリを読むとsleepの前後で特定のアドレスに書き込みをしているので、LEDを光らせているのだとあたりをつけ、sleepと合わせると長く光ったり短く光ったりすると推測できる。これをモールス信号だとして復号していくとV -> Oと読めたため、モールス信号と断定した。straceの結果をもとに-.かを判定して解いた。単語と単語の間は一度750msのsleepが入ることに注意(以下のコードで使っているtrace.txtでは消してある)。

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

'''
trace.txt:
execve("./lights", ["./lights"], [/* 43 vars */]) = 0
...
nanosleep({0, 250000000}, NULL)         = 0
nanosleep({0, 250000000}, NULL)         = 0
nanosleep({0, 250000000}, NULL)         = 0
nanosleep({0, 250000000}, NULL)         = 0
nanosleep({0, 250000000}, NULL)         = 0
nanosleep({0, 250000000}, NULL)         = 0
nanosleep({0, 750000000}, NULL)         = 0
nanosleep({0, 750000000}, NULL)         = 0
...
'''

with open('trace.txt') as f:
    data = f.read()
a = {'25': '.', '75': '-'}
lst = map(lambda x: a[x], re.findall(r', ([1-9]{2})0000000',data))
for i in range(0,len(lst),2):
    sys.stdout.write(str(lst[i]))
    if i + 1 < len(lst) - 1 and lst[i + 1] == '-':
        sys.stdout.write(' ')
print ''
ubuntu-xenial% ./solve.py
...- --- .-.. --. .- -.-. - ..-. .-- .. - .... .- -... .-.. .. -. -.- --- ..-. .- -. . -.-- . -.-- --- ..- ..-. .. -. .- .-.. .-.. -.-- ... . . - .... . .-.. .. --. .... -

これを Morse Code Translator に貼り付ければフラグが得られる。

CrackMe [Rev 100]

exeファイルが渡される。これは.NETのアプリケーションなのでdnSpyなどでデコンパイルできる。 CombineKeysでAESで使う鍵を作っているが、無駄な計算を省くと以下のようになる。

private byte[] CombineKeys(byte[] UserKey) // UserKey is an output of MD5
        {
            AppSettings appSettings = new AppSettings();
            byte[] bytes = Encoding.UTF8.GetBytes(appSettings.DefaultKey); // "DefaultKey"
            long num = BitConverter.ToInt64(bytes, 0);
            long num2 = BitConverter.ToInt64(bytes, 8);
            long num3 = BitConverter.ToInt64(UserKey, 0);
            long num4 = BitConverter.ToInt64(UserKey, 8);
            long num5 = num ^ num3;
            long num6 = num2 ^ num4;
            long num7 = (~num & num3) | (~num3 & num); // num ^ num3
            long num8 = (~num2 & num4) | (~num4 & num2); // num2 ^ num4
            int num9 = BitConverter.ToInt32(BitConverter.GetBytes(num5), 0);
            int num10 = BitConverter.ToInt32(BitConverter.GetBytes(num5), 4);
            int num11 = BitConverter.ToInt32(BitConverter.GetBytes(num6), 0);
            int num12 = BitConverter.ToInt32(BitConverter.GetBytes(num6), 4);
            num10 >>= 2;
            num10 <<= 1;
            num11 = num10;
            num12 = num10;
            num9 = ~num12;
            num9 = ~num9;
            byte[] bytes2 = BitConverter.GetBytes(num9);
            byte[] bytes3 = BitConverter.GetBytes(num10);
            byte[] bytes4 = BitConverter.GetBytes(num11);
            byte[] bytes5 = BitConverter.GetBytes(num12);
            byte[] array = new byte[16];
            for (int i = 0; i < 4; i++)
            {
                array[i] = bytes2[i];
                array[i + 4] = bytes3[i];
                array[i + 8] = bytes4[i];
                array[i + 12] = bytes5[i];
            }
            return array;
        }

コードを追っていくと、bytes2,bytes3,bytes4,bytes5は同じ値になっている。つまり、鍵の種類は2^32通りしかない(もう少し考えると2^30になる)。これ以上減らせなかったのでこのまま全探索させた(約4時間。想定解は違うものであってほしい)。

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cryptopp/aes.h>
#include <cryptopp/cryptlib.h>
#include <cryptopp/filters.h>
#include <cryptopp/modes.h>

std::string decrypt(unsigned char *enc, int len, unsigned char *key) {
    unsigned char iv[CryptoPP::AES::BLOCKSIZE], cipher[0x100];
    std::string decrypted;
    memcpy(iv,enc,CryptoPP::AES::BLOCKSIZE);
    memcpy(cipher,enc+CryptoPP::AES::BLOCKSIZE,len - CryptoPP::AES::BLOCKSIZE);

    CryptoPP::AES::Decryption aesDecryption(key, CryptoPP::AES::DEFAULT_KEYLENGTH);
    CryptoPP::CBC_Mode_ExternalCipher::Decryption cbcDecryption(aesDecryption, iv);

    CryptoPP::StreamTransformationFilter stfDecryptor(cbcDecryption, new CryptoPP::StringSink(decrypted));
    stfDecryptor.Put(cipher, len - CryptoPP::AES::BLOCKSIZE);
    stfDecryptor.MessageEnd();
    return decrypted;
}

int main(void) {
    FILE *fp = fopen("CrackMe.txt","r");
    unsigned char enc[0x100], key[16];
    int len = fread(enc,1,0xff,fp);

    // 0x36524421
    for (unsigned int i = 0; i < 0x40; i++) {
        for (unsigned int j = 0; j < 0x100; j++) {
            printf("\r0x%02x%02x0000",i,j);
            fflush(stdout);
            for (unsigned int k = 0; k < 0x100; k++) {
                for (unsigned int l = 0; l < 0x80; l++) {
                    for (unsigned int m = 0; m < 2; m++) {
                        for (int n = 0; n < 4; n++) {
                            key[n*4] = l << 1;
                            key[n*4+1] = k;
                            key[n*4+2] = j;
                            key[n*4+3] = i | (m * 0xc0);
                        }
                        try {
                            std::string decrypted = decrypt(enc,len,key);
                            if (decrypted.find("VolgaCTF") != std::string::npos) {
                                std::cout << decrypted << std::endl;
                            }
                        } catch(std::exception e){}
                    }
                }
            }
        }
    }
    return 0;
}

You Shall Not Pass (Rev 200) (追記 18/3/30)

crackme系の問題。本番中には解けなかった。 文字列を入力させ、40個のスレッドでチェックしている。シンボリック実行ではスレッドのようないつ来るかわからないイベントを扱うことが難しいらしいのでangrなどにそのまま突っ込むことはできない。チェックしている部分を1つ抜き出してみると以下のようになっている。

  4012f5:       mov    rax,QWORD PTR [r14]
  4012f8:       mov    rdx,QWORD PTR [rax+0xb8]
  4012ff:       mov    rdi,QWORD PTR [rax+0x120]
  401306:       lea    rcx,[rdx*4+0x0]
  40130e:       shl    rdx,0x5
  401312:       sub    rdx,rcx
  401315:       mov    rcx,QWORD PTR [rax+0x40]
  401319:       imul   rdx,QWORD PTR [rax+0x128]
  401321:       lea    rcx,[rcx+rcx*4]
  401325:       add    rdx,rcx
  401328:       mov    rcx,QWORD PTR [rax+0x68]
  40132c:       lea    rcx,[rcx+rcx*2]
  401330:       lea    rcx,[rdx+rcx*2]
  401334:       mov    rdx,QWORD PTR [rax+0x88]
  40133b:       mov    rsi,rdx
  40133e:       neg    rsi
  401341:       lea    rdx,[rdx+rsi*4]
  401345:       lea    rsi,[rcx+rdx*2]
  401349:       mov    rcx,QWORD PTR [rax+0xd0]
  401350:       mov    rdx,rcx
  401353:       neg    rdx
  401356:       lea    rdx,[rcx+rdx*4]
  40135a:       lea    rcx,[rdi+rdi*1]
  40135e:       mov    rdi,QWORD PTR [rax+0x18]
  401362:       add    rdx,rsi
  401365:       sub    rdx,rcx
  401368:       mov    rcx,QWORD PTR [rax+0xc8]
  40136f:       lea    rcx,[rcx+rcx*8]
  401373:       add    rdx,rcx
  401376:       mov    rcx,QWORD PTR [rax+0x20]
  40137a:       mov    rsi,rcx
  40137d:       neg    rsi
  401380:       lea    rcx,[rcx+rsi*4]
  401384:       lea    rsi,[rdx+rcx*2]
  401388:       mov    rcx,QWORD PTR [rax+0xe8]
  40138f:       mov    rdx,rcx
  401392:       neg    rdx
  401395:       shl    rdx,0x2
  401399:       sub    rdx,rcx
  40139c:       lea    rcx,[rdi*8+0x0]
  4013a4:       lea    rdx,[rsi+rdx*2]
  4013a8:       mov    rsi,rdx
  4013ab:       mov    rdx,QWORD PTR [rax+0x48]
  4013af:       sub    rsi,rcx
  4013b2:       lea    rdx,[rdx+rdx*2]
  4013b6:       mov    rcx,rdx
  4013b9:       shl    rcx,0x5
  4013bd:       add    rdx,rcx
  4013c0:       mov    rcx,QWORD PTR [rax+0x98]
  4013c7:       imul   rdx,QWORD PTR [rax+0xc0]
  4013cf:       add    rdx,rsi
  4013d2:       lea    rcx,[rdx+rcx*4]
  4013d6:       mov    rdx,QWORD PTR [rax+0x60]
  4013da:       lea    rsi,[rdx+rdx*4]
  4013de:       lea    rdx,[rdx+rsi*4]
  4013e2:       shl    rdx,0x2
  4013e6:       imul   rdx,QWORD PTR [rax+0x58]
  4013eb:       mov    rax,rdx
  4013ee:       add    rax,rcx
  4013f1:       cmp    rax,0x14f5c2
  4013f7:       je     401401 <pthread_mutex_unlock@plt+0x401>
  4013f9:       mov    BYTE PTR [r12],0x0
  4013fe:       mfence
  401401:       mov    rax,QWORD PTR [rsp+0x18]
  401406:       xor    rax,QWORD PTR fs:0x28
  40140f:       jne    401485 <pthread_mutex_unlock@plt+0x485>
  401411:       add    rsp,0x20
  401415:       pop    rbx
  401416:       pop    rbp
  401417:       pop    r12
  401419:       pop    r13
  40141b:       pop    r14
  40141d:       ret

r14には入力の文字列が、r12にはチェックを通ったかどうかのフラグが格納されている。他のスレッドでも同じようにチェックを行っているため、mov rax,QWORD PTR [r14]からcmp ~を抜き出してシミュレートすれば同じ動作を行うことができ、z3pyですべてのチェックを通るような解を求めることで解くことができる。

#!/usr/bin/env python
from z3 import *
import commands
import re

def fcommon(a,b,op):
    code = '%s %s ' % (a,op)
    if b.find('[') != -1:
        if b.find('+') != -1:
            reg, offset = re.search('\[(.*)\+(.*)\]', b).groups()
            code += '%s[%d]' % (reg, int(offset,16) // 8)
        else:
            code += '%s[0]' % re.search('\[(.*)\]', b).group(1)
    else:
        code += b
    return code

def fmov(a,b):
    return fcommon(a,b,'=')

def fadd(a,b):
    return fcommon(a,b,'+=')

def fsub(a,b):
    return fcommon(a,b,'-=')

def fmul(a,b,c = None):
    if c is None:
        return fcommon(a,b,'*=')
    code = a + ' = '
    if b.find('[') != -1:
        if b.find('+') != -1:
            reg, offset = re.search('\[(.*)\+(.*)\]', b).groups()
            code += '%s[%d] * %s' % (reg, int(offset,16) // 8, c)
        else:
            code += '%s[0] * %s' % (re.search('\[(.*)\]', b).group(1), c)
    else:
        code += '%s * %s' % (b,c)
    return code

def flea(a,b):
    code = a + ' = ' + re.search('\[(.*)\]', b).group(1)
    return code

def fshl(a,b):
    return '%s = %s << %s' % (a,a,b)

def fneg(a):
    return '%s = -%s' % (a,a)

def fcmp(a,b):
    return '%s == %s' % (a,b)

def get_instructions():
    found = False
    blocks = []
    for line in commands.getoutput('objdump -d -M intel --no-show-raw-insn ysnp').split('\n'):
        if line.find('mov    rax,QWORD PTR [r14]') != -1:
            block = []
            found = True
        if found:
            block.append(line.split('\t')[-1])
        if found and line.find('cmp') != -1:
            blocks.append(block)
            found = False
    return blocks

def addconstraints(s):
    for i in range(length):
        s.add(X[i] >= 0x20, X[i] <= 0x7e)
    known = "VolgaCTF{"
    for i in range(len(known)):
        s.add(X[i] == ord(known[i]))
    s.add(X[length-1] == ord('}'))

    ops = {'mov': fmov, 'add': fadd, 'sub': fsub, 'imul': fmul, 'lea': flea, 'shl': fshl, 'neg': fneg, 'cmp': fcmp}
    blocks = get_instructions()
    r14 = [X]
    for block in blocks:
        for line in block:
            op, operand = re.search(r'([a-z]+) *(.+)',line).groups()
            operand = operand.split(',')
            code = ops[op](*operand)
            if op == 'cmp':
                s.add(eval(code))
            else:
                exec(code)

length = 45

X = [BitVec('x%d' % i,8) for i in range(length)]

s = Solver()
addconstraints(s)

flag = list('*' * length)
if s.check() == sat:
    m = s.model()
    for i in range(length):
        flag[i] = chr(m.evaluate(X[i]).as_long())
    print ''.join(flag)