ふるつき

v(*'='*)v かに

SageMathのalarmが便利

この記事の内容は

ask.sagemath.org

を見て書かれました

プログラムを書いていると「とりあえず factor してみて、小さい素因数を持っているかどうか確かめる」ということがよくあります。Invalid Curve AttackをしたいのでPohlig-Hellmanに向いた「位数が小さい素因数に持つ楕円曲線を探す」みたいな場合です。

しかし、 factor （や discrete_log）はうまい値ならばすぐ終わりますが、そうでない場合は時間がかかってしまいます。そこでこれまでは https://github.com/pnpnpn/timeout-decorator を使っていたのですが、スレッドだとうまくいかないのでシグナルを使わないとだめだとか（逆だったかも）そもそもデコレーターなので処理を関数に切り出さないといけないとかがあって面倒でした。

調べたところによるとSageには alarm と cancel_alarm という関数があって、これが便利に使えます。たとえば位数に小さい素因数を含む楕円曲線を探してみます

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = int(-3 % p)
# b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

for b in range(1000):
    try:
        E = EllipticCurve(GF(p), [a,b])
        alarm(5)
        order = E.order()
        factors = factor(order, limit=100000)
        cancel_alarm()
    except (AlarmInterrupt, ArithmeticError):
        continue

    if prod([p**e for p, e in factors if p < 100000]) > 1000000000:
        print(b)
        quit()

上記の例から読み取れるように alarm は数値を引数に取って即座に処理を返しますが、バックグラウンドで動いていてそのn秒後に AlarmInterrupt 例外を投げます。それよりもさきにcancel_alarmが呼び出されるとアラームは投げられなくなります。

これがimport不要で使えて便利、というメモでした。

Google CTF 2021 writeup

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

[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というのはそういうものですからチェックしないので正しいと思います

3kCTF 2021 - Digital writeup

まずスクリプトを眺めます。

from Crypto.Util.number import inverse
import hashlib
import os

rol = lambda val, r_bits, max_bits: (val << r_bits%max_bits) & (2**max_bits-1) | ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))

class Random():
    def __init__(self, seed):
        self.state = seed
        self.bits = self.state.bit_length()

    def next(self):
        self.state ^= self.state << 76
        self.state = rol(self.state, 32, self.bits)
        self.state ^= self.state >> 104
        self.state = rol(self.state, 20, self.bits)
        self.state ^= self.state << 116
        self.state = rol(self.state, 12, self.bits)
        return self.state

def sign(message):
    h = int(hashlib.sha256(message).hexdigest(), 16)
    k = random.next()
    r = pow(g, k, p) % q
    s = inverse(k, q) * (h + x*r) % q
    return (r, s)

def verify(message, r, s):
    h = int(hashlib.sha256(message).hexdigest(), 16)
    w = inverse(s, q)
    u1 = h * w % q
    u2 = r * w % q
    v = (pow(g, u1, p) * pow(y, u2, p) % p ) % q
    return v == r

random = Random(int(os.urandom(16).hex(), 16))
p = 0x433fd29e6352ba4f433aaf05634348bf2fa7df007861ec24e1088b4105307a9af5645fff0bb561f31210b463346f6d2990a8395e51f0abf6f0affad2364a09ef3ab2cfa66497ebb9d6ac7ed98710634c5a39ddc9d423294911cfa787e28ac2943df345ed6b979ed9a383e1be05e35b305c797f826c9502280dd5b8af4ff532527eed2e91d290b145fac6d647c81127ed06eaa580d64bcf2740ee8ed2aa158cc297ca9315172df731f149927ba7b6e72adf88bde00d13cc7784c717ce1d042cbc3bd8db1549a75fb5c4d586ed1d67fe0129e522f394236b8053513905277b8e930101b0660807598039a4796e66018113fbf3f1703303bb3808779e3613995cb9
q = 0xc313d1a2bf3516a555c54875798a59a3d219ea76179b712886beec177263cec7
g = 0x21ac05c17f3cc476fa34ea77b5e2252e848f2ab35cf4e1f6cc53f15349af6e56f1c5ad36fe7cdf0a00c8162032b623d1271b4f586d26dba704706c32d0cefa01937e82d8af632596e9d27ff10a7cad23766ae97c07bb7dc3b2e24a482ab30c02435c8ce99b0cc356146c371bda04582ee1b40b2f29227ba8225aa490b4bd788662168929fdd2cfbce0e0dc59da3db76651ee91fbc654d36f277003f96ff6b045b2ab5187b0d4024a32281672c606206aebb1f3fe9b75877e38dcd38c73aa588ec01ae3fca344befbdf745a47f7a45b4d06643fea5e4e9b02f763cc5b2e7e8488945b0fe12b56b83a29cbe47ec9d276197d0245d11abc8833f88d114f3a897f81

x = int(open("flag.txt",'rb').read().hex(), 16)
y = pow(g, x, p)

MSG1 = b'Joe made the sugar cookies.'
MSG2 = b'Susan decorated them.'
r1, s1 = sign(MSG1)
r2, s2 = sign(MSG2)
assert verify(MSG1, r1, s1)
assert verify(MSG2, r2, s2)
print ("y = ", y)
print ("r1 = ", r1)
print ("s1 = ", s1)
print ("r2 = ", r2)
print ("s2 = ", s2)

"""
y =  5624204323708883762857532177093000216929823277043458966645372679201025592769376026088466517180933057673841523705217308006821461505613041092599344214921758292705684588442147606413017270932589190682167865180010809895170865252326994825400330559172774619220024016595462686075240147992717554220738390033531322461011161893179173499597221230442911598574630392043521768535083211677909300720125573266145560294501586465872618003220096582182816143583907903491981432622413089428363003509954017358820731242558636829588468685964348899875705345969463735608144901602683917246879183938340727739626879210712728113625391485513623273477
r1 =  53670875511938152371853380079923244962420018116685861532166510031799178241334
s1 =  6408272343562387170976380346088007488778435579509591484022774936598892550745
r2 =  3869108664885100909066777013479452895407563047995298582999261416732594613401
s2 =  63203374922611188872786277873252648960215993219301469335034797776590362136211
"""

いくつか注目すべき点があります。与えられているのは y = g^x \mod pという離散対数問題のインスタンスがひとつと、同じ pを使い、また離散対数問題のときの xを秘密鍵として用いたDSAのインスタンスがふたつです。また、DSAの署名時の乱数 kは、なにやら怪しげな乱数生成器によって与えられています。

離散対数問題はまず解けないので無視します。今回は p-1の大きな素因数 qが明らかになっており、例えばPohlihg-Hellmanのような攻撃は有効に動作しません。他の攻撃手法が刺さる可能性は残されていますが、おそらくそういう問題ではないでしょう。

ということでDSAのインスタンスに注目します。ここで、 qおよびその他の変数はおよそ256bitの値であるのに対して、 kはseedが128bitであることから最大でも128bitの値であるとわかります。この値だけ比較的小さいので、LLLやそれを用いたCoppersmith法で求められる可能性があります。今回は2インスタンスしかありませんから、適当に制約をつないでmultivariate Coppersmithを試してみます。

まず式を立てます。 s \equiv k^{-1}(h + xr) \mod qを変形して x \equiv r^{-1}(ks - h) \mod q です。これが2インスタンスありますから、それぞれ r_1, r_2, \dots などと適当に番号を振って、式同士を減算すると r_1^{-1}(k_1s_1 - h_1) - r_2^{-1}(k_2s_2 - h_2) \equiv 0 \mod q です。これを満たすような適当な根 k_1, k_2は見つけられるでしょうか。

これは見つけられます。見つけられますが、この根が正しい（問題のインスタンスで使われたものと一致する）根ではない可能性があります。これは運ですが、今回のインスタンスについてはだめでした。そこで、さらなる条件を付け加えてやる必要があります。これはチームメイトの S3v3ru5 が教えてくれたのですが、 k_2の上位64bitと k_1の下位64bitは共通です。これはたとえば下記のようなスクリプトを書いて確認することができます

from z3 import *

rol = lambda val, r_bits, max_bits: (val << r_bits%max_bits) & (2**max_bits-1) | ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))

class Random():
    def __init__(self, seed):
        self.state = seed
        # self.bits = self.state.bit_length()

    def next(self):
        self.state ^= self.state << 76
        self.state = RotateLeft(self.state, 32)
        self.state ^= LShR(self.state, 104)
        self.state = RotateLeft(self.state, 20)
        self.state ^= self.state << 116
        self.state = RotateLeft(self.state, 12)
        return self.state


xs = [BitVec("x{}".format(i), 1) for i in range(16 * 8)]
x = Concat(*xs)
r = Random(x)
print(simplify(r.next()))

この性質を使うと128bit 2変数の多項式を64bit 3変数の多項式にできます。こちらの多項式を使ったMultivariate Coppersmithで正しい k_1, k_2を得られ、 xを復元してフラグを得ることができました。

from Crypto.Util.number import *
from hashlib import sha256


# https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []


p = 0x433fd29e6352ba4f433aaf05634348bf2fa7df007861ec24e1088b4105307a9af5645fff0bb561f31210b463346f6d2990a8395e51f0abf6f0affad2364a09ef3ab2cfa66497ebb9d6ac7ed98710634c5a39ddc9d423294911cfa787e28ac2943df345ed6b979ed9a383e1be05e35b305c797f826c9502280dd5b8af4ff532527eed2e91d290b145fac6d647c81127ed06eaa580d64bcf2740ee8ed2aa158cc297ca9315172df731f149927ba7b6e72adf88bde00d13cc7784c717ce1d042cbc3bd8db1549a75fb5c4d586ed1d67fe0129e522f394236b8053513905277b8e930101b0660807598039a4796e66018113fbf3f1703303bb3808779e3613995cb9
q = 0xc313d1a2bf3516a555c54875798a59a3d219ea76179b712886beec177263cec7
g = 0x21ac05c17f3cc476fa34ea77b5e2252e848f2ab35cf4e1f6cc53f15349af6e56f1c5ad36fe7cdf0a00c8162032b623d1271b4f586d26dba704706c32d0cefa01937e82d8af632596e9d27ff10a7cad23766ae97c07bb7dc3b2e24a482ab30c02435c8ce99b0cc356146c371bda04582ee1b40b2f29227ba8225aa490b4bd788662168929fdd2cfbce0e0dc59da3db76651ee91fbc654d36f277003f96ff6b045b2ab5187b0d4024a32281672c606206aebb1f3fe9b75877e38dcd38c73aa588ec01ae3fca344befbdf745a47f7a45b4d06643fea5e4e9b02f763cc5b2e7e8488945b0fe12b56b83a29cbe47ec9d276197d0245d11abc8833f88d114f3a897f81

y =  5624204323708883762857532177093000216929823277043458966645372679201025592769376026088466517180933057673841523705217308006821461505613041092599344214921758292705684588442147606413017270932589190682167865180010809895170865252326994825400330559172774619220024016595462686075240147992717554220738390033531322461011161893179173499597221230442911598574630392043521768535083211677909300720125573266145560294501586465872618003220096582182816143583907903491981432622413089428363003509954017358820731242558636829588468685964348899875705345969463735608144901602683917246879183938340727739626879210712728113625391485513623273477
r1 =  53670875511938152371853380079923244962420018116685861532166510031799178241334
s1 =  6408272343562387170976380346088007488778435579509591484022774936598892550745
r2 =  3869108664885100909066777013479452895407563047995298582999261416732594613401
s2 =  63203374922611188872786277873252648960215993219301469335034797776590362136211


MSG1 = b'Joe made the sugar cookies.'
MSG2 = b'Susan decorated them.'
h1 = int(sha256(MSG1).hexdigest(), 16)
h2 = int(sha256(MSG2).hexdigest(), 16)
r1inv = int(inverse_mod(r1, q))
r2inv = int(inverse_mod(r2, q))

s1inv = int(inverse_mod(s1, q))
s2inv = int(inverse_mod(s2, q))


PR.<k1u, k2l, k> = PolynomialRing(GF(q))

k1 = k1u*2^64 + k
k2 = k*2^64 + k2l

f = r1inv*(k1*s1 - h1) - r2inv*(k2*s2 - h2)
roots = small_roots(f, [2^64, 2^64, 2^64], m=2, d=2)
print(roots)
for root in roots:
    k1u, k2l, k = [int(r) for r in root]
    k1 = k1u*2^64 + k
    k2 = k*2^64 + k2l

    x1 = (r1inv*(k1*s1 - h1)) % q
    x2 = (r2inv*(k2*s2 - h2)) % q

    print(x1)
    print(int(x1).to_bytes(100, "big"))
    print(int(x2).to_bytes(100, "big"))
    print(pow(g, int(x1), p) == y)
    print(pow(g, int(x2), p) == y)