Google CTF 2021 writeup

Google CTF 2021 のCryptoの問題はどれも楽しかったです。着目すべき点はわかりやすいけど解ききるのは大変という印象でした。チームメイトのS3v3ru5と一緒に取り組んでチームとしてはCryptoは全部とけて非常によかったです。

[crypto] tiramisu
[crypto] H1

[crypto] tiramisu

go製のecho serverで、ECDHによって共通鍵を生成して暗号化されたメッセージをやりとりします。暗号文にはHMACによる認証符号を付与していて、認証が通らない場合はセッションを確立できません。また、フラグはサーバの秘密鍵 d から生成される鍵をつかってAESで暗号化されています。

脆弱性

ECDHの段階でサーバからは secp224r1 に準拠した鍵が送られてきます。また提供されるクライアントプログラムでもsecp224r1の鍵を生成してサーバに送っているのですが、プログラムやprotobuf*1をみるとどうやらsecp256r1の鍵を送ることもできるようでした。しかしプログラム上ではsecp224r1が送られてくることだけを想定しているらしく、次のようなコードがありました。

   // Load peer key.ecnrypted
    peer, err := proto2ecdsaKey(clientHello.Key)
    if err != nil {
        return err
    }

    // Key sanity checks.
    if !peer.Curve.IsOnCurve(peer.X, peer.Y) {
        return fmt.Errorf("point (%X, %X) not on curve", peer.X, peer.Y)
    }

    // Compute shared secret.
    P := server.key.Params().P
    D := server.key.D.Bytes()
    sharedX, _ := server.key.ScalarMult(new(big.Int).Mod(peer.X, P), new(big.Int).Mod(peer.Y, P), D)

    masterSecret := make([]byte, server.key.Params().BitSize/8)
    sharedX.FillBytes(masterSecret)

注目するのは sharedX を計算している部分で、ここではクライアント側が送信した公開鍵を $d$ 倍して共通鍵を生成しようとしているのですが、この演算はsecp224r1上で行われています。しかしここにsecp256r1上の座標を送ることもできます。InvalidCurveAttackが行えそうですね。

InvalidCurveAttackというのはサーバがある点の演算を行うときにその点が楕円曲線上に存在するかをきちんと確認できていないときに行える攻撃で、楕円曲線上の加算・乗算ではワイエルシュトラス標準形でいうところの $b$ を用いないことから、サーバ側が正規の楕円曲線 $y^2 \equiv x^3 + ax + b \mod p$ 上での演算をしているつもりでも $y^2 \equiv x^3 + ax + b' \mod p$ 上での計算をさせることができる、というものです。secp224r1は安全な楕円曲線なので位数の小さい点というものは存在しませんが、 $b$ の値を操作してうまい点をつくると小さい位数の点での演算を行わせることができます。

dの特定

InvalidCurveAttackをうまく使うことができれば目的であったサーバの秘密鍵 $d$ を求めることができそうです。典型的には曲線 $y^2 \equiv x^3 + ax + b' \mod p$ 上の小さい位数を持つ点 $P$ を送り、 $dP$ を得て離散対数問題を解くことで $d$ を計算するのですが、今回は共通鍵の計算ということで計算後のsharedXを直接得ることはできません。しかし小さい位数 $m$ 上では $dP$ は $O, P, 2P, \dots, (m-1)P$ のどれかになりますから、これを全探索して通信が確立できるかをみることで、擬似的にブルートフォースアタックによって小さいインスタンスの離散対数問題が解けていることになります。要するに位数 $m$ の点 $P$ を送り、 $0 \le d' \lt m$ を全探索して送って、通信が確立できたら $d' \equiv d \mod n$ が成り立っていると言えます。

今、小さい位数について考えていましたが中国剰余定理をつかって異なるたくさんの剰余 $m_i$ についての $d'_i \equiv d \mod m_i$ を得ることで $d$ が復元できそうです

小さい位数の点の発見

では小さい位数 $m$ を持つ点 $P$ はどのように発見すればよいのでしょうか。これは簡単で、 $b'$ の値をランダムに探索して楕円曲線 $E$ の位数 $ord(E)$ が小さい素因数を含むかどうかを見れば良いです。 $ord(E) = p_1 p_2 \dots p_n$ のように素因数分解ができるとき、 $E$ 上の適当な点 $Q$ を持ってきて $P = \frac{p_2 \dots p_n}{p_1}Q$ を計算すれば $P$ の位数は $p_1$ になります。このあたりについては yoshi-gcc log - ふるつきに書いています

今回気をつけるべきなのは、このように生成した点 $P$ がsecp256r1上の点である必要がある、ということです。というのも↑のコード辺にあるように、サーバは送られてきた点が楕円曲線上に存在するかをIsOnCurveメソッドによって調べています。しかしIsOnCurveはあたえられた座標 $(x, y)$ が $0 \le x, y \lt p$ であるかどうかはチェックしていませんから*2、secp224r1の剰余の法の上では $P$ に、secp256r1の剰余の法の上ではsecp256r1上の適当な点になるような巨大な値を渡せば問題は解決です。そして、このような点は中国剰余定理で求めることができます

dの特定

しかしここまでやってもまだ少し問題があります。それは今回の問題では共通鍵としてsharedXを使っている、という部分です。何が問題なのかといえば、 $dP$ と $-dP$ は同じX座標をもつので、ブルートフォースで得られた $d' \equiv d \mod p$ という式が実は $d' \equiv -d \mod p$ かもしれない、という点です。当然ここが異なれば中国剰余定理で復元できる最終的な $d$ にも差がうまれますから、これは重大な問題です。

しかしこれを区別する良い方法は思いつかなかったので符号は全探索することにしました。これにかかる時間は $2^k$ で $k$ は中国剰余定理で復元するときのペアの数です。ここであまりに小さい剰余をつかっているとペアの数が60個とかになって到底計算できないので、↑のスクリプトでは多少時間がかかっても剰余を1000〜10000とある程度大きくしています。

exploit

長くなったのでここにおいておきます

the solution script of tiramisu from Google CTF 2021 · GitHub

[crypto] H1

こちらもECDHによって鍵を共有する問題です。こちらはAliceとBobがECDHによって鍵を共有しており、またいくつかのメッセージを相互に送り合っています。メッセージは暗号化されていますが、フラグの部分以外はわかっています。また、メッセージには署名が行われています

脆弱性

ECDSA時の $k$ の生成に脆弱性があります。生成はこう↓なっているのですが、この方法だと $k$ のエントロピーは8 * 16 = 256bit程度しかありません。 $k$ の値が小さいとHNPなどで $k$ を復元して秘密鍵 $d$ を求めることができます。

def RNG(nbits, a, b):
    nbytes = nbits // 8
    B = os.urandom(nbytes)
    return a * sum([B[i] * b ** i for i in range(len(B))]) % 2**nbits

def Sign(msg, d):
    h = hashlib.sha512(msg)
    z = Transform(int.from_bytes(h.digest(), 'big'), h.digest_size*8)
    k = RNG(n.bit_length(), 16843009, 4294967296)
    x1, y1, z1 = Multiply(G, k)
    r = (x1 * pow(z1, -2, mod) % mod) % n
    s = pow(k, -1, n) * (z + r * d) % n
    return r, s

kを求める

今回はBobからメッセージが2回送られていることを利用して、 $(s_1k_1 - z_1)r_1^{-1} - (s_2k_2 - z_2)r_2^{-1} \equiv 0 \mod n$ という式をたててLLLでときました。ただし $k_1, k_2$ は8bitの値16個をRNG関数と同様に結合する形にして、33 x 32の格子を構成するような感じです。小さい変数をたくさん作ることになったのでMultivariate CoppersmithよりはLLLのほうが扱いやすそう、と判断しました。

LLLの部分ではrkm0959さんのInequality Solving with CVPのライブラリを使いました。便利

Qaを求める

$d_b$ を求めるパートは自明なので飛ばして、共通鍵を得るためにAliceの公開鍵 $Q_a$ を求めます。これは署名が正しいと仮定するとメッセージと署名から公開鍵を逆算することができます。このプログラムでは計算がヤコビアンで行われていて散々バグらせましたが、最終的にecdsaライブラリのrecover_public_keysを使う方法でうまくやりました

exploit

いろいろ試行錯誤していたあとが残っていますが整形も面倒なのでそのまま

https://gist.github.com/theoremoon/26c4d4cad1039cae1dba1a17e9ad3de9

*1:メッセージのエンコーディングのためにprotobufが使われていました。やりすぎ感あるし扱いが面倒になるだけなので素直にjsonとかで良いです

*2:modというのはそういうものですからチェックしないので正しいと思います