hxpctf 2018 Writeups uff, curve12833227, daring, Blind
hxpctf 2018にnegainoidoで参加していました。
結果は写真の通り。わたしはsh1tty_AI以外の９問を解きました。
Cryptoの問題がなかなかおもしろかったのでWriteupにまとめます。
uff
問題概要
NaClの署名システムにたいしてChosen Plain Text Attackをしてくださいという問題。
接続しに行くと８個の公開鍵が与えられます。 それらを用いて任意のテキストを送ると、その署名を手に入れることができます。 このやり取りを何回か繰り返したあとに、今まで送った文章とは違う文章の署名済みテキストを偽造することが目的です。
この問題はプログラムのソースコードはもらえますが、肝心の署名ライブラリのコードは与えられません。 しかし"tweetnacl.h"というヘッダファイルをインポートしているので、おそらくこれのことだと思われます。 github.com
解法
さて、問題のソースをよく見ると、署名を生成するときに、署名結果を格納するポインタと、署名するテキストを格納するポインタで同じものを渡していることがわかります。
size_t sign(unsigned char *m, unsigned long long n, unsigned char const *pk, unsigned char const *sk) { struct keypair k; memcpy(k.sk, sk, sizeof(k.sk)); memcpy(k.pk, pk, sizeof(k.pk)); crypto_sign(m, &n, m, n, (char *) &k); return n; }
しかし、そのような渡し方をライブラリ側は想定していません。
int crypto_sign(u8 *sm,u64 *smlen,const u8 *m,u64 n,const u8 *sk) { u8 d[64],h[64],r[64]; i64 i,j,x[64]; gf p[4]; crypto_hash(d, sk, 32); d[0] &= 248; d[31] &= 127; d[31] |= 64; *smlen = n+64; FOR(i,n) sm[64 + i] = m[i]; FOR(i,32) sm[32 + i] = d[32 + i]; crypto_hash(r, sm+32, n+32); reduce(r); scalarbase(p,r); pack(sm,p); FOR(i,32) sm[i+32] = sk[i+32]; crypto_hash(h,sm,n + 64); reduce(h); FOR(i,64) x[i] = 0; FOR(i,32) x[i] = (u64) r[i]; FOR(i,32) FOR(j,32) x[i+j] += h[i] * (u64) d[j]; modL(sm + 32,x); return 0; }
FOR(i,n) sm[64 + i] = m[i];の部分で、smとmが同じポインタのエイリアスだった場合は署名テキストが先頭64バイトの繰り返しになってしまいます。
そして、そのように書き換えたテキストに対して署名をしてしまいます。
例えば平文が'deadbeef' * 16 + '00'だった場合、署名されたテキストとして[sign(64 bytes)]'deadbeef’*16 +'de'が返って来ます。
一方で、配列nopeには、変更される前のテキストを格納します。
したがって、もらった署名をそのまま、偽造した署名として提出すればフラグが得られます。
flag: hxp{Th3_m0sT_f00lpr00f_sYsT3m_br34kz_1f_y0u_4bU5e_1t_h4rD_eN0u9h} この解法だととくに複数個の公開鍵がもらえる理由が特になくて、署名クエリも１回だけなので想定解法ではないような気がします。
curve12833227
問題概要
楕円曲線上の離散対数問題を解く問題です。
#!/usr/bin/env python3 from random import randrange from Crypto.Cipher import AES p = 2**128 - 33227 i = lambda x: pow(x, p-2, p) def add(A, B): (u, v), (w, x) = A, B assert u != w or v == x if u == w: m = (3*u*w + 4*u + 1) * i(v+x) else: m = (x-v) * i(w-u) y = m*m - u - w - 2 z = m*(u-y) - v return y % p, z % p def mul(t, A, B=0): if not t: return B return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A) x = randrange(p) aes = AES.new(x.to_bytes(16, 'big'), AES.MODE_CBC, bytes(16)) flag = open('flag.txt').read().strip() cipher = aes.encrypt(flag.ljust((len(flag)+15)//16*16).encode()) print(*mul(x, (4, 10)), cipher.hex(), file=open('flag.enc', 'w'))
解法
ソースコードをよく読むと、楕円曲線が \( y2 = x3 + 2 x2 + x \) であることがわかります。 教科書でよく見る楕円曲線は \( y2 = x3 + a x + b \) の形なので違和感があります。
色々とググるとこのような曲線はSingular curveと呼ぶらしいです。stack exchangeに以下のような質問を見つけました。
Why not use singular curves? It turns out that the group structure on those curves is isomorphic to the multiplicative group of a (quadratic extension of) a field. Therefore the discrete logarithm problem is not harder than of that in a finite field, so there is little reason to use the curve in the first place.
つまり、この楕円曲線上の群構造は(Z/pZ)と同型になるようです。その同型射がわかれば、楕円曲線状の離散対数問題を(Z/pZ)上の 離散対数問題に帰着してSageで解くことができそうです。
更にググると、 Elliptic Curve Handbookを見つけました。 この中のProposition 1.8.1によると、 $$ (x, y) \to \frac{\mu_1(x-x_0) - (y-y_0)}{ \mu_2(x-x_0) - (y-y_0) } $$ が対応する写像のようです。pdfの中には各定数の計算方法も書いてあります。
これを参考にsageで以下のように計算を行いました
sage: p = 340282366920938463463374607431768178229 sage: K = GF(p) sage: K Finite Field of size 340282366920938463463374607431768178229 sage: K(-1024).square_root() 62339483394082122745023847371156527578 sage: c4 =16 sage: K(-1024).square_root() / K(2*c4) 150821644383975644101008385981747219462 sage: mu1 = K(-1024).square_root() / K(2*c4) sage: mu2 = -mu1 sage: mu1 150821644383975644101008385981747219462 sage: x0 = -1 sage: y0 = 0 sage: x0 = K(-1) sage: y0 = K(0) sage: x0 340282366920938463463374607431768178228 sage: x = K(104708042197107879674895393611622483404) sage: y = K(276453155315387771858614408885950682409) sage: (mu1 * (x-x0) - (y-y0)) / (mu2 * (x-x0) - (y-y0)) 21942627144369491015728137374841304324 sage: h = (mu1 * (x-x0) - (y-y0)) / (mu2 * (x-x0) - (y-y0)) sage: g = (mu1 * (K(4)-x0) - (K(10)-y0)) / (mu2 * (K(4) -x0) - (K(10)-y0)) sage: h.log(g) 35996229751200732572713356533972460509
あとは以下でフラグが得られます。
x= 35996229751200732572713356533972460509 # assert( mul(x,(4,10)) == h) aes = AES.new(x.to_bytes(16, 'big'), AES.MODE_CBC, bytes(16)) c = binascii.unhexlify('202bb05919b6f021d22a8baa7979ef6810761eb4c653b0fc5eebf2bc6ac6ecb052f887eedd075174abd884f84547df2d') plain = aes.decrypt(c) print(plain)
hxp{51n9uL4r1ti3s_r3duC3_tH3_G3nUs}
daring
RSA問です。 RSAの暗号結果とAESの暗号結果がもらえます。 public exponentが３なので三乗根を取る問題だと考えます。 aesの暗号文から平文の長さが４３バイトだとわかります。 平文をmsg.ljust(128, b’\x00’)でpaddingしているのでmodinv(pow(2, 3 * 8 (128-43),p ),p) をかければだいたい良さそうですが、 43 3 = 129なので１バイト文だけ溢れてしまってうまく復号できません。ただし１バイトだけなので 適当なｐの倍数を足してから三乗根を取るとうまく行きました。 hxp{DARINGPADS_1s_4n_4n4gr4m_0f_RSAPADDING}
Blind
問題概要
GF(p)と同型な体が与えられます。(p = 0xfffffed83c17)しかし、同型写像は暗号化されているため、どの元がどの元に対応しているのかはわかりません。 同型射をfとして、f(1)とf(y)が与えられます。 体上の演算子として加算(+)と加法逆元(-)と乗算(*)が0x400回行えるので、ｙを求めてください。
解法
p-1を素因数分解すると最大の素因数が151であることがわかります。 このとき、gをZ/pZ*の生成元として、 \( gx = y \) となるxを求める離散対数問題を暗号化された体上で考えます。 すなわち、f(g)とf(y)が与えられたときに \( f(g) ^ x = f(y) \) となるxを求める問題です。 このようなxがえられれば、 \( y = gx \) となり、yを求めることができます。
p-1が小さい素因数しか持たないときに使える離散対数アルゴリズムとして、 Pohlig-Hellmanのアルゴリズムというのがあるので、 wikipediaに書かれたアルゴリズム何も考えずに実装します。 Pohlig–Hellman algorithm - Wikipedia
書いたexploitが以下です 生成元g = 11としていますが、実はこれは誤りで、本当はg = 5とすべきです。 g = 11にしたせいで確率1/2くらいで失敗します。
gist8145390698e5759a8ae3c89b8882336a
これを書いて実行したらローカルでは解が得られたのですが、リモートでやると、 ネットワークが遅くて、0x200回くらいクエリを投げた時点で接続がタイムアウトしてしまいました。 仕方ないので、google cloud platformを使ってフランクフルトにVMインスタンスを立ててそこから問題サーバに接続させたらフラグを得ることができました。 世界中の様々な場所にVMインスタンスを安価かつ即座に建てれるとは便利な時代になったものです。 hxp{DLP_4nd_DHP_4re_H4mm1n9_d1sT4nc3_0Ne}
