Writeup: EBCTF 2013 - Challenge CRY300 “Curves”(時間内に解けなかった)

CTF

時間内に通せなかったが、最後のわからなかった部分が後でわかったのでとりあえず書いておく。

アクセスすると最初に指定された8bytesで始まる64bytesの16進文字列で、md5が0000で始まるものを要求される。なお、この値はこれ以降使っていないので、サーバの負荷を調整するためのものだろうか。

import sys
import hashlib
def hashcash(cash):
    i = 0
    while True:
        resp = "%s%056x" % (cash, i)
        if hashlib.md5(resp).hexdigest().startswith('0000'):
            break
        i += 1
    return resp

print hashcash(sys.argv[1])

続いてパスワードを聞かれる。service.py中にハッシュ化されたパスワードがあるが、検索すれば簡単に元のパスワードがわかる。括弧内はアクセスレベルである。

  • f56334fbe02eaa05218c31b01a80f2f6 (0): Hotz
  • 00b37cb56bb57705348610253b1b82e4 (0): Bushing
  • 6fa95b1427af77b3d769ae9cb853382f (0): Peter
  • 58cd57027cf126fcc9bd93dea9d74c1a (0): Segher
  • f1cd318e412b5f7226e5f377a9544ff7 (1): Kevin
  • 98c131f9fb31f732b136f87e64ff686a (1): Butler
  • 6f3249aa304055d63828af3bfab778f6 (2): 31337

アクセスレベル2のユーザはそのままフラグが表示され、アクセスレベル1のユーザはECDSAで追加の認証が必要となる。しかし、パスワードに数字は許されていないためLevel 2のところへはアクセスできない。その認証トークンをLevel 0のものについて1000個集めたものが captured-sessions.txt である。

認証トークンは全体が一つのECDSA署名である。base64でデコードした後、16進文字列に変換して、先頭64文字がr、後半64文字がsとなる。 これがtoken(パスワードのmd5)の署名となっていれば良い。

さて、Level 0用の認証トークンを作るために用いられたget_ephemeral_keyを見ると、ランダムでなければならないkの空間がやけに小さい。

def get_ephemeral_key():
        k = ""
        while len(k) < 32:
                k += hashlib.md5(seed + str(random.randint(0,255))).digest()
        return int(k.encode('hex'),16)

md5は16bytesなので、kの空間は65536通りしか無い。1000個も集めれば十分に衝突していることが期待される。これはDSA/ECDSAの有名な誤用である。

ECDSAの仕様から、kの値が同じなら、rの値が等しくなるので、そのような認証トークンをcaptured-sessions.txtから探した。二つkが同じ認証トークンの組があることが分かる。

$ awk '{print $2}' captured-sessions.txt | perl -MMIME::Base64 -lpe '$_ = encode_base64(substr(decode_base64($_),0, 32)); s/\n//g' | sort | uniq -c | awk '$1 != 1 {print}'
      2 KVKN3KKUwmAMMDUC9QrKvBmPyu2h5tkqCqRG7NTjdOg=
      2 g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHk=
      2 wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5w=

$ grep -F KVKN3KKUwmAMMDUC9QrKvBmPyu2h5tkqCqRG7NTjdO captured-sessions.txt 
Bushing KVKN3KKUwmAMMDUC9QrKvBmPyu2h5tkqCqRG7NTjdOiU66IYqtYejrnlwpfYdr4079fFeLM4RC5ni4P9JF+4Tw==
Bushing KVKN3KKUwmAMMDUC9QrKvBmPyu2h5tkqCqRG7NTjdOiU66IYqtYejrnlwpfYdr4079fFeLM4RC5ni4P9JF+4Tw==

$ grep g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxH captured-sessions.txt 
Hotz g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlW9NTSxduU5nPoqdQt4Cn58GL17cq37J1SrbrK1/b67w==
Bushing g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHmOCiSFewnBx/EQ3Ij7ZX+iE+dPiDSBMezXcwzWWeVm1w==

$ grep -F wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv captured-sessions.txt 
Hotz wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5xCxqlIuZkMQDSpRWffZGG4NdkaOvAfttTtQuCaJZonxA==
Bushing wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5xiKYZxm648bajMuJ9Dy1SyHEpu/MBHkViuCM4P9Fd78Q==

Wikipediaに書かれている式からプログラムを書いたが、この問題、公開鍵が与えられていないのでまだ群の位数(n)がわかっていない。

import hashlib
import ecdsa
import base64

n = 0 # Unknown

z  = int(hashlib.md5("Kevin").hexdigest(), 16)
z1 = int(hashlib.md5("Hotz").hexdigest(), 16)
z2 = int(hashlib.md5("Bushing").hexdigest(), 16)
t1 = "g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlW9NTSxduU5nPoqdQt4Cn58GL17cq37J1SrbrK1/b67w=="
t2 = "g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHmOCiSFewnBx/EQ3Ij7ZX+iE+dPiDSBMezXcwzWWeVm1w=="

def parse_security_token(sig):
    tmp = base64.b64decode(sig).encode('hex')
    return (int(tmp[:64],16), int(tmp[64:],16))

def sig_security_token(r, s):
        rhex = "%064x" % r
        shex = "%064x" % s
        return base64.b64encode(rhex.decode('hex') + shex.decode('hex')) 

(r1, s1) = parse_security_token(t1)
(r2, s2) = parse_security_token(t2)
assert r1 == r2
r = r1
k = ((z1 - z2) * ecdsa.inverse_mod(s1 - s2, n)) % n
dA = ((s1 * k - z1) * ecdsa.inverse_mod(r, n)) % n
s = (ecdsa.inverse_mod(k, n) * (z + r * dA)) % n
print sig_security_token(r, s)

さらに言えば楕円曲線もまだ決定できていないので、まず楕円曲線を決定することにした。
ecdsa.pyとservice.pyよりy^2 \equiv x^3 - 3x + b \;\pmod{p}で表される楕円曲線であることがわかる。bとpの値が未知である。
service.pyの先頭で楕円曲線上の点が3つ与えられていることに注目した。

#some points that really should be on the curve we're going to use
_Gx = 0x337ef2115b4595fbd60e2ffb5ee6409463609e0e5a6611b105443e02cb82edd8L
_Gy = 0x1879b8d7a68a550f58166f0d6b4e86a0873d7b709e28ee318ddadd4ccf505e1aL

_Qx = 0x2a40fd522f73dc9f7c40b2420e39e62c5742ff2f11805a1577ed7f60153a0be1L
_Qy = 0x3085e99246006b71b4211eff47ff3efc0f93103ee7379dc3bcc6decdc46073a3L

_Rx = 0xbd0a442367bdc24cb09c49404e3d307ba99122e7b78e14f0d84870d0df97aa59L
_Ry = 0x22c88612db6b6af6f196cd815fc5f57fe871d3b6588b0c7a59e06cc759d736b2L

C_i = y_i^2 - x_i^3 + 3x_iとおき、\gcd(c_1 - c_2,\, c_2 - c_3)からpの値を決定した。

b = 28285296545714903834902884467158189217354728250629470479032309603102942404639
p = 89953523493328636138979614835438769105803101293517644103178299545319142490503

これでbとpを決定することができたが、まだ必要な位数がわかっていない。結局、この計算を行うプログラムを探しまわっている途中でタイムアップとなった。


終了後、PARI/GPで計算できることに気づいた。

$ gp
? b = 28285296545714903834902884467158189217354728250629470479032309603102942404639
? p = 89953523493328636138979614835438769105803101293517644103178299545319142490503
? E = ellinit([0, 0, 0, -3, b])
? allocatemem(1000000000)
? n = ellgroup(E, p)
%4 = [89953523493328636138979614835438769106005948670998555217484157791369906305783]

サーバはもう停止してるので通るか確認できない……