ふるつき

v(*'='*)v かに

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)

TSG Live CTF 6 writeup

先日行われたTSG Live! 6中の企画の一つ、TSG Live CTFに外部チームの一員として招待され、参加してきましたので記念writeupです。放送のアーカイブはこちら↓

チームは公式には kurenaifさんptr-yudai、私の3人でしたが、助っ人としてst98さんにもいくつかの問題を解いていただきました。正直私はいてもいなくても同じ結果になっただろうと思っていますが、このチームで参戦できて楽しかったです。私が解いた問題のうち、Fisherだけは正答数がすくなかったのでwriteupを書いておきます。


与えられるのは次のようなソースコードで、 string_to_signalsは文字列を[0, 1]からなるモールス符号に変換する関数です。素直に読むと、フラグ文字列をモールス符号に変換し、さらに01の符号データをsin波で表しています。それだけなら良いのですが、この波形データをランダムにシャッフルしたあと、wav形式で保存しています。

import soundfile as sf
import numpy as np
from utils import signals_to_string, string_to_signals

flag = open('flag.txt').read()
signals = string_to_signals(flag)

assert(len(signals) == 473)

wave = np.empty(len(signals) * 2000)
for i in range(len(wave)):
  if signals[i // 2000] == 0:
    wave[i] = 0.0
  else:
    # Generate 439.97Hz morse code
    wave[i] = np.sin(i * 439.97 / 44100 * (2 * np.pi))

# Fisher here :)
np.random.shuffle(wave)

sf.write('result.wav', wave, 44100, 'PCM_24')

結構困るように見え、また想定解法(賢い)では困った前提で xが小さいときに \sin(x) \approx x であることを利用しているのですが、実験をしてみると意外にもsin波を構成する点が、どのiに対応するかがほぼ一対一で対応付けられることに気が付きました。おそらく浮動小数点の演算誤差からくるものだとは思いますが、へーという感じです。

というわけで、自分で i を回しながら \sin(\frac{439.97i}{44100 * 2\pi}) に一致する点があるかないかで、その周辺が0/1のどちらを波形に変換したものかを判断することができます。一致の判定は浮動小数点でやると怖いので、多少の誤差を受け入れることにして小数を文字列に変換して、小数点以下n桁までが一致するかを見ました。

import soundfile as sf
import numpy as np
from utils import signals_to_string

filepath = 'result.wav'
data, _ = sf.read(filepath)

print(len(data))
size = len(data)
data = set(["{:.6f}".format(d) for d in data])

rev_data = []

for i in range(size):
  k = np.sin(i * 439.97 / 44100 * (2 * np.pi))
  ks = "{:.6f}".format(k)
  if ks in data:
    rev_data.append(k)
  else:
    rev_data.append("x")


signal = []
for i in range(0, len(rev_data), 2000):
  if rev_data[i:i+2000].count("x") > 500:
    signal.append(0)
  else:
    signal.append(1)

# print(len(rev_data))
# print(signal)
print(signals_to_string(signal))

重ねて申し上げますが、楽しい企画に誘ってくださり対戦どころか問題まで用意してくださったTSGの皆様、一緒にチームを組んでくれたkurenaifさん、ありがとうございました。楽しかったです

Midnightsun CTF 2021 writeup

Midnightsun CTFは毎年いくつか独自色の強い問題が出るな、という印象だったのですが、今年はBackupシリーズのcryptoがひどかった印象があります。その他AVRマイコンなどの組み込みに関連する問題が出るのはいつもどおりという感じ。

私は純粋cryptoを2問通しました。どちらもsolve数が二桁前半で、簡単というほどではないが難しい問題ではない、という感じでの面白い問題でした。なんとかチームメイトに怒られない程度の貢献はできたかな。

ocat_024

u = getrandbits(512)
p = next_prime(1337 * u + getrandbits(300))
q = next_prime(2021 * u + getrandbits(300))
n = p * q

sage: n                                                                                                                                                       
376347864369130929314918003073529176189619811132906053032580291332225522349124770927556541528827257242440708492473086949335591022991715583608318595770643139658398940858358366788472884935226392323475683663699450192657590965945792699658618476121298301964814904817629813971114882401961638885452623305901569855693667669
sage: e                                                                                                                                                       
310766221758298615381202293330340201483059349618898159596286032329366528507960364515724537815587119639645241427449290559721282531962504187828968370246921804939126848756614691757878117709116273156365166616707032588454229002048939764035908902821773289938766897121298435864096976179239412103595971947786698704390414999
sage: round(log(d, 2))                                                                                                                                        
376
sage: Zmod(n)(int.from_bytes(flag, 'big'))^e                                                                                                                  
303959676149267585825046248298946771045524761540948385119310381022731003152171453295355624619013005255259014408962058282203132797411290952180380162699236575669681289832696809724483816916203823843359489329046259936011464869397208487809073597880729992617105037777911285154649450892121090200338517719744860831555514222

 p = 1337u + a, q = 2021u + b となっているRSAの問題です。加えて、 dが比較的小さいことが分かっています。

まず第一に注目するのは素数が独特な構造になっていることです。これは過去にConfidence CTF 2019 TeaserでReally Suspicious Acronymとして出題されている形式で、 uが共通しており、 a, bのサイズが比較的小さいことから \frac{p}{q} = \frac{1337u + a}{2021u + b} \simeq \frac{1337}{2021}と近似ができるので、 n \times \frac{1337}{2021} \simeq n \times  \frac{p}{q} = p^2 という近似ができます。この近似により p, qの上位210ビット程度を求めることができます。

しかしこれだけの情報では、Coppersmith's methodを用いた素因数分解には不足です。そこで dが比較的小さいというヒントから、 ed = 1 \mod \phi(N)を使って立式していきます。

 \phi(N) = N - (p + q) + 1 ですから、  p + qを先程近似した値 p', q'と真の値との差 rを用いて p + q = p' + q' + rと表して以下の式が成り立ちます。

 ed = 1 + tN - t(p' + q' + r) + t

さらに \mod eをとります。

 0 \equiv 1 + tN - t(p' + q' + r) + t \mod e  \tag{△}

式(△)において、未知変数は r, t であり、 rは素因数 p, qの未知の部分なので300bit程度、また t = (ed - 1) / \phi(N) \simeq (2^{1045}\times 2^{376} - 1) / 2^{1045} \simeq 2^{376} であることから、 tの大きさは最大でも376bit程度になります。一方 eは1000bit以上ありますから、 r, tは剰余多項式(△)の比較的小さな整数根になっていると言えそうです。したがってCoppersmith's methodによって r, tの具体的な値を求められるかもしれません。多変数多項式の小さい根を求める実装としては、 defund/coppersmith が優れています。これを使って r, tを求めることができれば、 \phi(N)を計算しフラグを求められそうです。

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

from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence

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 = PolynomialSequence([], f.parent())
    for i in range(m+1):
        power = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = power
            for variable, shift in zip(f.variables(), shifts):
                g *= variable^shift
            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)
    B = B.change_ring(ZZ)

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

    return []


n = 376347864369130929314918003073529176189619811132906053032580291332225522349124770927556541528827257242440708492473086949335591022991715583608318595770643139658398940858358366788472884935226392323475683663699450192657590965945792699658618476121298301964814904817629813971114882401961638885452623305901569855693667669
e = 310766221758298615381202293330340201483059349618898159596286032329366528507960364515724537815587119639645241427449290559721282531962504187828968370246921804939126848756614691757878117709116273156365166616707032588454229002048939764035908902821773289938766897121298435864096976179239412103595971947786698704390414999
c =  303959676149267585825046248298946771045524761540948385119310381022731003152171453295355624619013005255259014408962058282203132797411290952180380162699236575669681289832696809724483816916203823843359489329046259936011464869397208487809073597880729992617105037777911285154649450892121090200338517719744860831555514222

p_ = int(sqrt(n * 1337/2021))
q_ = int(sqrt(n * 2021/1337))

PR.<r, t_> = PolynomialRing(Zmod(e))
f = 1 + k_*n - t_*(p_ + q_ + r) + t_
for ans in small_roots(f, [2^300, 2^377]):
    r = int(ans[0])
    phi = n - (p_ + q_ + r) + 1

    d = int(pow(e, -1, phi))

    m = pow(c, d, n)
    print(m)

求まりました。

dbcsig_64434

from hashlib import sha256


def keygen(password):
    while True:
        p = 2 * random_prime(2 ^ 521) + 1
        if p.is_prime(proof=False):
            break
    base, h = 3, password
    for i in range(256):
        h = sha256(h).digest()
    x = int.from_bytes(h * 2, "big")
    return base, p, pow(base, x, p), x


def sign(message, priv):
    h = int(sha256(message).hexdigest(), 16)
    k = next_prime(int.from_bytes(
        sha256(message + priv.to_bytes(128, "big")).digest() + sha256(message).digest(),
        "big"
    ))
    r = int(pow(g, (k - 1) / 2, p))
    s = int(Zmod((p - 1) / 2)(-r * priv + h) / k)
    return r, s


g, p, pub, priv = keygen(b"[redacted]")
r, s = sign(b"blockchain-ready deterministic signatures", priv)

(配布ソースコード中に存在した、問題と直接関係ないコメントを省略しています)

独自のデジタル署名アルゴリズムのようですが、プログラムはいわゆるDSAのそれと似通っています。目的は d = privを求めることで、 g, p, pub, r, sに加えて、平文から求められる hが分かっています。

このアルゴリズムを観察すると、2つ特徴的な部分が見つかります。まず1つ目は秘密鍵 dの構造で、int.from_bytes(h * 2, "big") のように、256bitの値を2回繰り返して並べることで512bitの値を作っています。値の大きさは512bitありますが、情報量としては256bitのものと等価と考えられます。2つめは kの値で、こちらも256bitの値を2つ並べて作られていますが、上位256bitが全くわからない一方、下位256bitは h + \alpha でありおよその値が分かっています。

式をたてて整理してみます。そもそものDSAアルゴリズムでは  ks \equiv -rd + h \mod q (ただしここで q = (p - 1) / 2です)がなりたち、それは今回も同様です。ここで k = 2^{256}k' + h + \alpha,  d = 2^{256}d' + d'と表しつつ、移項して式を整理すると次のような形になります。

 s(2^{256}k'  + h + \alpha) + r(2^{256}d' + d') - h \equiv 0 \mod q

ここで未知数は k', d', \alphaで、 k', d'はそれぞれ256bitの値です。 \alphaはどのくらいかわかりませんが、だいたい1000を超えることはないでしょう。他方、 qは521bit程度の値であり未知数と比較して大きいですから先ほどと同様にCoppersmith's methodが適用できそうです。

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

from hashlib import sha256

g = 3
p = 403564885370838178925695432427367491470237155186244212153913898686763710896400971013343861778118177227348808022449550091155336980246939657874541422921996385839128510463
pub = 246412225456431779180824199385732957003440696667152337864522703662113001727131541828819072458270449510317065822513378769528087093456569455854781212817817126406744124198
r = 195569213557534062135883086442918136431967939088647809625293990874404630325238896363416607124844217333997865971186768485716700133773423095190740751263071126576205643521
s = 156909661984338007650026461825579179936003525790982707621071330974873615448305401425316804780001319386278769029432437834130771981383408535426433066382954348912235133967
message = b"blockchain-ready deterministic signatures"
h = int(sha256(message).hexdigest(), 16)

q = (p-1) // 2
# assert q.is_prime ????????

PR.<d_, k_, a> = PolynomialRing(Zmod(q))

f = 2^256 * s * k_ + s * (h + a) + r * (d_ + 2^256 * d_) - h
roots = small_roots(f, [2^256, 2^256, 1000], d=4, m=4)

for root in roots:
    dval = Integer(root[0])
    dval = dval * 2^256 + dval
    if pow(g, dval, p) == pub:
        print("[+] found: {}".format(dval))
        break
    else:
        print("[-] wrong: {}".format(dval))

できました。ところで、この問題のkeygenに従って値が作られていれば pは最大でも522bit程度の値で安全素数になると思ったのですが、実際には pは557bitあり、また安全素数ではありませんでした。これは一体どういうことでしょうか 🤔

Securinets CTF 2021 Quals writeup

楽しく解ける問題ばかりで評価が高い。BOSS問という感じの問題はなかったので割と解かれていた印象。唯一PoWが面倒な形式だったのでもうちょっと丁寧に作ってほしかった感じはある

MiTM

from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secret import flag
import hashlib
import random
import os
import signal

class DHx():
    def __init__(self):
        self.g = 2
        self.p = 0xf18d09115c60ea0e71137b1b35810d0c774f98faae5abcfa98d2e2924715278da4f2738fc5e3d077546373484585288f0637796f52b7584f9158e0f86557b320fe71558251c852e0992eb42028b9117adffa461d25c8ce5b949957abd2a217a011e2986f93e1aadb8c31e8fa787d2710683676f8be5eca76b1badba33f601f45
        self.private = random.randint(1, self.p - 1)
        self.secret = None

    def getPublicKey(self):
        return pow(self.g, self.private, self.p)

    def share(self, x : int):
        assert x > 1 and x < self.p
        return pow(x, self.private, self.p)

    def getSharedSecret(self, x : int):
        assert x > 1 and x < self.p
        self.secret = pow(x, self.private, self.p)

    def getFingerprint(self):
        return hashlib.sha256(long_to_bytes(self.secret)).hexdigest()

    def checkFingerprint(self, h1 : str, h2 : str):
        return h1 == h2 == self.getFingerprint()

    def encryptFlag(self):
        iv = os.urandom(16)
        key = hashlib.sha1(long_to_bytes(self.secret)).digest()[:16]
        return iv.hex() + AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16)).hex()

signal.alarm(60)

Alice = DHx()
Bob = DHx()
Carol = DHx()

A = Alice.getPublicKey()
print("Alice sends to Bob: {}".format(A))
A = int(input("Forward to Bob: "))
B = Bob.share(A)
print("Bob sends to Carol: {}".format(B))
B = int(input("Forward to Carol: "))
Carol.getSharedSecret(B)

B = Bob.getPublicKey()
print("Bob sends to Carol: {}".format(B))
B = int(input("Forward to Carol: "))
C = Carol.share(B)
print("Carol sends to Alice: {}".format(C))
C = int(input("Forward to Alice: "))
Alice.getSharedSecret(C)

C = Carol.getPublicKey()
print("Carol sends to Alice: {}".format(C))
C = int(input("Forward to Alice: "))
A = Alice.share(C)
print("Alice sends to Bob: {}".format(A))
A = int(input("Forward to Bob: "))
Bob.getSharedSecret(A)

print("Alice says: ")
if (Alice.checkFingerprint(Carol.getFingerprint(), Bob.getFingerprint())):
    print(Alice.encryptFlag())
else:
    print("ABORT MISSION! Walls have ears; Be careful what you say as people may be eavesdropping.")

名前のとおりにAlice Bob Carol三者のDiffie Hellman鍵共有プロセスに介入して、任意のパラメータの交換を改竄できる。ただし三者は鍵共有のあと、互いの鍵が一致しているかを確かめるために、それぞれの鍵のfingerprintが一致することを確認している。したがって、三者の鍵を同じにしつつ、鍵の中身を知ることができるような改竄の仕方を考える必要がある。

一番簡単な方法は0や1を送って 0^a = 0 1^a = 1と計算してもらうことだが、三者は送られてきたパラメータ x 1 \lt x \lt p であることを確認しているのでこれはできない。それならば -1はどうか。三者秘密鍵 a,b,cが偶数の場合は -1^a \equiv 1 \mod pとなってしまうので途中でエラーになるが、すべて奇数ならば -1^a \equiv -1 \equiv p-1 \mod p p-1に落ち着く。

というわけで p-1を送りつつ a,b,cがそれぞれ奇数になる組み合わせを引くまでガチャする。実際はガチャ用のコードを整えている間にyoshikingがガチャを当てて解いていた。

from ptrlib import Socket
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
import hashlib
import time

while True:
    time.sleep(1)
    sock = Socket("crypto1.q21.ctfsecurinets.com", 1337)
    p = 0xf18d09115c60ea0e71137b1b35810d0c774f98faae5abcfa98d2e2924715278da4f2738fc5e3d077546373484585288f0637796f52b7584f9158e0f86557b320fe71558251c852e0992eb42028b9117adffa461d25c8ce5b949957abd2a217a011e2986f93e1aadb8c31e8fa787d2710683676f8be5eca76b1badba33f601f45

    sock.sendlineafter("Forward to Bob: ", str(p - 1))
    AB = int(sock.recvlineafter("Carol: "))
    if AB == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Carol: ", str(AB))
    print("[+] progress 1")

    sock.sendlineafter("Forward to Carol: ", str(p - 1))
    BC = int(sock.recvlineafter("Alice: "))
    if BC == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Alice: ", str(BC))
    print("[+] progress 2")

    sock.sendlineafter("Forward to Alice: ", str(p - 1))
    CA = int(sock.recvlineafter("Bob: "))
    if CA == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Bob: ", str(CA))
    print("[+] progress 3")

    print(sock.recvline())
    line = sock.recvline().decode()
    if "ABORT" in line:
        sock.close()
        continue

    key = hashlib.sha1(long_to_bytes(p - 1)).digest()[:16]
    iv, cipher = bytes.fromhex(line[:32]), bytes.fromhex(line[32:])
    aes = AES.new(key, AES.MODE_CBC, iv)
    print(aes.decrypt(cipher))

    break

あとでyoshikingに教えてもらったけど、 a,b,cがそれぞれ偶数の場合でも解けて、1度目の介入では適当な値を渡して、2度目でだけ p-1を送るようにすればshareが a,b,cの偶奇に応じて 1 p-1になるので、↑の方法より確率を上げることができる。

Shilaformi

import signal
from secret import flag
from Crypto.Random import random
from Crypto.Util.number import getPrime

#Odds and evens (hand game)
#https://en.wikipedia.org/wiki/Odds_and_evens_(hand_game)

def pad(choice, n):
    return 2*random.randint(1, n//2 - 1) + choice

def send(choice, n):
    choice = pad(choice, n)
    return pow(2, choice, n )

signal.alarm(360)
print ("Let's play odds and evens! If I win you loose 5 times the amount of money you have bet! I choose odd.\n")

WALLET = 10
while WALLET > 0:
    print("Your current wallet is {} $.\n".format(WALLET))

    if WALLET > 133337:
        print("Wow, You've got filthy rich. Here's your flag: {}".format(flag))
        exit()

    n = getPrime(1024)*getPrime(1024)
    print ("Public Modulus : {}\n".format(n))

    bet = int(input("Place your bet : "))
    assert bet <= WALLET and bet > 0

    choice = random.randint(0, 5)
    print ("Here's my choice : {}\n".format(send(choice, n)))

    player = int(input("Shilaaafooooooormi: "))
    assert player >= 0 and player < 6

    if (choice + player ) & 1:
        print("You lose.")
        WALLET -= 5*bet
    else:
        print("You win.")
        WALLET += bet

print("You got no money left in your wallet. Make sure to come back later!")

いわゆるOdds and evensというゲームらしく、相手が出してきた手と自分が出してきた手の和が偶数になるように値を選んで送れば勝ちとなる。相手は手 x 0 \le x \le 5の間から一つ選び、 n = pq と毎回ことなる乱数 rを用いて y = 2^{2r + x} \mod nとして渡してくれる。

このとき、 yから xの偶奇を判断する問題は、平方剰余問題(quadratic residuosity problem)として知られている 平方剰余問題と行った場合には aから a \equiv x^2 \mod nを満たす xを探す問題を指していそう。この問題は平方剰余の判定問題で、一般的な名前があるのかは知らない。ある値 aがある剰余の法 nの上で平方剰余か(= x^2 \equiv  a \mod nとなる xが存在するか)を調べるためにはルジャンドル記号、あるいはヤコビ記号を使うことができる。ルジャンドル記号は剰余の法が素数である場合に使える記号であり、ヤコビ記号はルジャンドル記号を拡張して合成数にも適用可能にしたものである。ただし、一部の正確性は失われている

大雑把に言えば、 Jacobi(a, n) = 1 のとき aは平方剰余かもしれないし、そうでないかもしれない。一方で Jacobi(a, n) = -1のとき、 aは必ず平方剰余ではない。したがって、与えられた手 y nについて Jacobi(y, n)をみて、その値が1の時はOdds and evensに勝てる確率は1/2であり、その値が1のときは必ず勝つことができる。

ところでここからがよくわかっていないんだけど、チームメイトのS3v3ru5に教えてもらい手元で実験した感じだと、 nの値によってヤコビ記号がうまく働いたり働かなかったりする。うまく働くケースに限って持金を全betし、勝てるかわからないときは1だけ掛けることで持金を増やした。

from ptrlib import Socket
import proofofwork
import gmpy2
import random

sock = Socket("crypto2.q21.ctfsecurinets.com", 1337)
pat = sock.recvregex(r"sha256\(([A-Za-z]+) \+ X\) = 000000")[0]
print(pat)

s = proofofwork.sha256(
        '000000??????????????????????????????????????????????????????????',
        text=pat + b'?????')
print(s)
sock.sendline(s[len(pat):])

# sock = Socket("localhost", 19999)

while True:
    current = int(sock.recvregex(r"wallet is ([0-9]+) \$.\n")[0])
    print(current)
    if current > 133337:
        sock.interactive()
    n = int(sock.recvlineafter("Modulus : "))
    print("[+] got modulus")

    # check n
    flag = True
    for choice in range(0, 6):
        x = 2*random.randint(1, n//2 - 1) + choice
        y = pow(2, x, n)
        if (x % 2 == 0) != (gmpy2.jacobi(y, n) == 1):
            flag = False
    print("[+] check: {}".format(flag))

    bet = 1
    if flag:
        # surely win
        bet = current
    sock.sendlineafter("bet : ", str(bet))

    y = int(sock.recvlineafter("choice : "))
    sock.sendlineafter("mi: ", str(1 if gmpy2.jacobi(y, n) == -1 else 0))
    if b"win" in sock.recvline():
        current += bet
        print("Win! current money: {}".format(current))
    else:
        current -= bet*5
        print("Loose... current money: {}".format(current))

        if current <= 0:
            print("LOOSE")
            break

Sign It!

from Crypto.Util.number import inverse
from Crypto.Random import random
from fastecdsa.curve import Curve
from fastecdsa.point import Point
import hashlib
import signal

class Server():
    def __init__(self, curve, G):
        self.G = G
        self.order = curve.q
        self.d = random.randrange(1, self.order - 1)
        self.P = (self.d * self.G)

    def sign(self, msg):
        z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
        k = random.randrange(1, self.order - 1)
        r = (k * self.G).x % self.order
        s = (inverse(k, self.order) * (z + r * self.d)) % self.order
        return (r, s)

    def verify(self, msg, sig):
        r, s = sig
        s %= self.order
        r %= self.order
        if s == 0 or r == 0:
            return False
        z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
        s_inv = inverse(s, self.order)
        u1 = (z * s_inv) % self.order
        u2 = (r * s_inv) % self.order
        W = u1 * self.G + u2 * self.P
        return W.x == r


signal.alarm(360)
# S256 curve params
p = 0x402969301d0ec23afaf7b6e98c8a6aebb286a58f525ec43b46752bfc466bc435
gx = 0x3aedc2917bdb427d67322a1daf1073df709a1e63ece00b01530511dcb1bae0d4
gy = 0x21cabf9609173616f5f50cb83e6a5673e4ea0facdc00d23572e5269632594f1d
a = 0x2ad2f52f18597706566e62f304ae1fa48e4062ee8b7d5627d6f41ed24dd68b97
b = 0x2c173bd8b2197e923097541427dda65c1c41ed5652cba93c86a7d0658070c707
q = 0x402969301d0ec23afaf7b6e98c8a6aeb2f4b05d0bbb538c027395fa703234883
S256 = Curve("S256", p, a, b, q, gx, gy)

PROOF = "Give me flag."
print("Welcome to the ECDSA testing of our probably secure S256 Curve. First choose your own generator then try to sign this message '{}' to prove us wrong.\n".format(PROOF))

print("Choose your point (x y) : ")

try:
    x = int(input("x : "))
    y = int(input("y : "))
    G = Point(x, y, curve=S256)
    S = Server(S256, G)

    sample = "No flags for you."
    print("Here's a sample signature: msg = '{}' , signature = {}".format(
        sample, S.sign(sample)))

    while True:
        msg = input("Message : ").strip()
        r = int(input("r : "))
        s = int(input("s : "))
        if S.verify(msg, (r, s)):
            print("Valid signature.")
            if msg == PROOF:
                from secret import flag
                print("Here you go : {}".format(flag))
                exit()
        else:
            print("Invalid signature.")

except Exception as e:
    print(e)
    exit()

ECDSAに関する問題。こちらからはいわゆるBase Point  Gを渡すことができ、かつ適当なメッセージに署名をしてもらえるので、向こうが指定したメッセージに署名するとフラグがもらえる。

楕円曲線上の離散対数問題が解けでもしない限りそんなことはできない。ところが与えられている楕円曲線のパラメータを見てみると、位数 qが小さい素因数として 157を持っているとS3v3ru5が教えてくれた。このとき、適当な楕円曲線上の点 Gに対して q/157をかけた G' = (q/157)G の位数は157になる。位数が小さければ離散対数問題は簡単にとける。

import hashlib
from ptrlib import Socket
import proofofwork

p = 0x402969301d0ec23afaf7b6e98c8a6aebb286a58f525ec43b46752bfc466bc435
gx = 0x3aedc2917bdb427d67322a1daf1073df709a1e63ece00b01530511dcb1bae0d4
gy = 0x21cabf9609173616f5f50cb83e6a5673e4ea0facdc00d23572e5269632594f1d
a = 0x2ad2f52f18597706566e62f304ae1fa48e4062ee8b7d5627d6f41ed24dd68b97
b = 0x2c173bd8b2197e923097541427dda65c1c41ed5652cba93c86a7d0658070c707
q = 0x402969301d0ec23afaf7b6e98c8a6aeb2f4b05d0bbb538c027395fa703234883

EC = EllipticCurve(GF(p), [a, b])
G = EC(gx, gy)
G2 = (q // 157) * G  # 157 is small factor of order

# sock = Socket("localhost", 19999)
sock = Socket("crypto2.q21.ctfsecurinets.com", 13337)
pat = sock.recvregex(r"sha256\(([A-Za-z]+) \+ X\) = 000000")[0]
print(pat)

s = proofofwork.sha256(
        '000000??????????????????????????????????????????????????????????',
        text=pat + b'?????')
print(s)
sock.sendline(s[len(pat):])

sock.sendlineafter("x : ", str(G2[0]))
sock.sendlineafter("y : ", str(G2[1]))

r, s = sock.recvregex(r"signature = \(([0-9]+), ([0-9]+)\)")
msg = "No flags for you."
z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
r, s = int(r), int(s)

for k in range(157):
    if (k*G2)[0] == r:
        print("[+] found k: {}".format(k))
        break
else:
    raise ValueError("[-] failed to calculate discrete log")

d = (s*k - z)*inverse_mod(r, 157) % 157
print("[+] found d: {}".format(d))


PROOF = "Give me flag."
z = int(hashlib.sha256(PROOF.encode()).hexdigest(), 16)
r = int((k * G2)[0])
s = (int(inverse_mod(k, 157)) * (z + r * d)) % 157


sock.sendlineafter("Message : ", PROOF)
sock.sendlineafter("r : ", str(r))
sock.sendlineafter("s : ", str(s))
sock.interactive()

LINE CTF 2021 babycrypto4 writeup

LINE CTF は cryptoに関しては満足行くクオリティの問題はありませんでした……。

overview

secp160r1上のECDSAに関する次の20 x 4個のパラメータが与えられます*1。左からr, s, kの上位16bit, hash(m) です。このときにいわゆる秘密鍵dを求めよ、という問題です。

0x92acb929727872bc1c7a5f69c1c3c97ae1c333e2 0xe060459440ebc11a7cd811a66a341f095f5909e5 0xef2b0000 0x68e548ef4984f6e7d05cbcea4fc7c83393806bbf
0xb0f5df566a323de9c9449b925d29b84a607c6b5d 0x84e39e417e47b4fcaf344255103c61ecaaec4129 0xc1c00000 0x1a79e7b0308805508d79f2600a01e70d4f56559e
0xc90081698382f98c817a137db22f11a846d699fe 0x2f8fbb7e74b789cd762b30930ef21862a5fd68ee 0x841b0000 0x95e3302e197be4d8335cf0d17cc70860ea5317f7
0x9d84669314b014bc83f3ac53ddcf3c9536c940b1 0x8b1a69d6e9d75f1698144badc7b93f9a2347839d 0xa1c90000 0xc7af08154a154ac8c58eb14380955834093b3863
0x96d5439a01f47e92be9ff40bee1fecb033b70d3f 0x1c23660695d16bf03ef40e5ef53bdc92a5d348e7 0x816e0000 0x9d3f0dc80e962b9377ed22de66d6421457bcaf5d
0x3ea39f6c446918690b395ba181f6d5d08444897a 0x4478e239338ec6652815d03b8decb2d4f58beaba 0x9d050000 0x478e00e6191477e6cdd17a29719d96d02e5e8960
0xbd1cbcd26fb6cb41878ec155fb2506534e803c97 0xd732fbda187222d85e9a14243b007cc25e1b6b7c 0x445a0000 0x2493379cf90246fe7316963c65f28cd9b0a6ecd4
0x727f7f05a9096beb6d5f65acce6fe42ec3a07dc9 0x8511715efb01ff83b04fe82fb7535dc7de40abef 0x91d0000 0x6ce034dddd5470034068c5146fae4dd039aacaf6
0x513ed0e15f8f3405bf0083a2186926fe60ccb65e 0x28892ebcc428f2a566b39a2dbe03ec436641c948 0x879d0000 0xfe4e2564369a23e07efbf82d01c5ae7e72cd8105
0xebf3e23fbe73c5f50032c8e4a3d8359fef203a03 0xa5b79ae6f8ed237a05b4325c02b8dfe7b9ff5aa7 0x98950000 0x762309f98ebac533fece5321736fc6ba95d8382b
0xc49cdbf6ec3b73188238291fa960675a099b74a0 0xeabb1e7dcd20115a47b94ecfe8780f676e237437 0x287a0000 0x523ea75c4310ac1ac64fa28cc5047b7223e8da0b
0x9e8a731a26f509793e2b8778cd75b518549ab9c8 0x27be029029db9d62cdb729bc592cb0a4e6168bf3 0xebc80000 0x9f0e9e95661f5e93c90b72af0dce38c673c7ef16
0xa74159f377749ad36efc28f9c7608a6758009af 0xa3ce2671944b01f633265a6458ce2cca8b72eda6 0x574c0000 0x16e12f9dece23681927be002d24a0e4e6ed3ae7e
0xcb0a427a05b3e3dcb18a1bb66f9340d2a0c721ab 0x4a242cca295c6018f4a65d1fadbdb45731cccd7a 0x23f40000 0xd7e0a09d8aed604bc1fda1f1965c4a8bf6b58621
0x5dc440585c88e75da002f941520867add07f93ef 0x3612124de46659ef7d79d46f1eb05707e313b84d 0x65850000 0xca6547a9e3f08bd36f700b7282a36033250971ad
0x6e009a8f5138a5b94d4e81b5f2a07ee29b413b39 0x8b3c33c15dca93248f840324d540b7956251d1e0 0xb4f80000 0xe916da678253ff7b31453ba1ec709eb909b37c5d
0x5091314db6155d7a96c1b19098ca235cf86d1f77 0x2c62bf21452a2b326e8db27fb3345e10c63b2821 0x452c0000 0x31dd06dcf95fb04a734149eed64b7b99a575d56e
0x2f6eed036a46ca6e309d8d7292bd3b0796607fcc 0x63b4524f47dcde603426c48bbb2f308bc474e5ce 0x63780000 0xe108d036a12b4f15cc9af89688d26634c5dfc32a
0x247ca1d3450a85612e6176ea5dfec4aeb90e2a3f 0x66b1f9f04e284e28f44402f1ca7803c90786d9c2 0x48a0000 0xd58c608cc4d3adfc131c73cccff952c1d310a1e0
0xab04fc0c4981b047622c786662091f7efbbbd807 0xa2853851df0aaed34dc972bcf7d7d5ffbbc2b401 0x9d040000 0x5bdd98b548b8b0f48a56fb4c41e6d09bf8bd1b0e

solution

いわゆるnonceであるkの上位16bitがわかっているのでこれを利用するのかな、と思うところですが、そもそも32bitのkでは小さすぎるので、半分が与えられていようがいまいが変わらず解けます。

(EC)DSAでは s \equiv (h + rd)k^{-1} \mod n ですから、これを展開して変形すると k - s^{-1}rd  - s^{-1}h \equiv 0 \mod n になります。いくつかのインスタンスを考えて、インスタンスごとに異なる値に添え字をつけると

 k_i - s_u^{-1}r_id  - s_i^{-1}h_i \equiv 0 \mod n

となります。このとき、 k_i, d がそれぞれ未知数で、 r_i, s_i, h_iはそれぞれ既知です。

一方、Hidden Number Problemは以下の式で t_i, a_i既知、 x_i, y未知に未知数を求める問題で、 x_iの最大値がある程度小さい時には、CVPを解いて x_i, yがそれぞれ求めることができます。

 x_i - t_iy + a_i \equiv 0 \mod p

2つの式を見比べてみると、 k_i \leftrightarrow x_i,  s_i^{-1}r_i \leftrightarrow t_i,  d \leftrightarrow y,  a_i \leftrightarrow -s_i^{-1}h_i という対応づけができそうです。そして、 x_iに対応する k_iは最大でも 2^{33} - 1 と小さいですから、CVPを解くことで k_i, xを求められそうです。今回は埋め込み法(embedded technique)と呼ばれる形のSVPを解くことでCVPを解いています。

from hashlib import sha1
import random

# https://neuromancer.sk/std/secg/secp160r1
p = 0xffffffffffffffffffffffffffffffff7fffffff
K = GF(p)
a = K(0xffffffffffffffffffffffffffffffff7ffffffc)
b = K(0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45)
E = EllipticCurve(K, (a, b))
G = E(0x4a96b5688ef573284664698968c38bb913cbfc82, 0x23a628553168947d59dcc912042351377ac5fb32)
E.set_order(0x0100000000000000000001f4c8f927aed3ca752257 * 0x01)

n = int(E.order())

dataset = []
with open("output.txt") as f:
    lines = f.read().strip().split("\n")
    for l in lines:
        # r_, s_, k_, h_ = [int(x, 16) for x in l.split(" ")]
        dataset.append( [int(x, 16) for x in l.split(" ")] )


r, s, k, h = zip(*dataset)
N = 20 # randint(2, 20) # len(h)
print("N = {}".format(N))
t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)]
u = [(h[i] * inverse_mod(-s[i], n) % n) % n for i in range(N)]

nonce_max = 2**32

B = matrix(QQ, N + 2, N + 2)
B.set_block(0, 0, matrix.identity(N) * n)
B.set_block(N, 0, matrix(QQ, 1, N, t))
B.set_block(N+1, 0, matrix(QQ, 1, N, u))
B[N,N] = nonce_max / n
B[N+1,N+1] = nonce_max

L = B.LLL()
for row in list(L):
    k1 = int(abs(row[0]))
    if k1 != 0 and k1 != nonce_max and k1 < nonce_max:
        x = (k1*s[0] - h[0]) * inverse_mod(r[0], n) % n
        kk = (k1 >> 16) << 16
        print(k1, x, kk in k)
        print(int(x)*G)

この問題では k_iがかなり小さいので、3インスタンス程度あればHNPが解けます。

*1:もともと問題文ではsecp160k1となっていましたが、正しくはsecp160r1のようでした。この間違いのアナウンスなしに解いたThe Duckはすごい

CTF crypto 逆引き

粗削りだけどとりあえず公開することにして、少しずつ情報を足していきたい。こういうケースがある、またこういう場合はどうすればよいのかという情報や質問をお待ちしています。

RSA

黙って Twenty Years of Attacks on the RSA CryptosystemRecovering cryptographic keys from partial information, by example を読んでおけば大体なんとかなる

e が 3など (Low Public Exponent)

例えば、 m^e \lt n であればe乗根を取ることで mが手に入る

出題例

nが多くの素因数に分解される

いわゆるMulti-Prime RSA nがどう素因数分解されようともオイラーのφ関数は定義できて、 \mod nでの位数がわかるので逆元 d \equiv e^{-1} \mod \phi(n)が求められる。

出題例

nがある素数と別の合成数までは素因数分解できる

実際には n = p*q*r だが、 p \lt q,r でnを素因数分解した結果 n = p*c (ここで c=q*r)までは得られたが、 c素因数分解は難しそう、というとき。このとき m \lt pであれば、 \mod pの世界で考えることで mを得られる。

出題例 募集中

nが同じでeが異なる複数の暗号文 (Common Modulus)

Common Modulus Attackが適用できる。複数の eが互いに素ではない場合には、それぞれの eの最大公約数を公開鍵とした暗号文が手に入ることになる

出題例 募集中

e, dがわかっているときにnを素因数分解する

def factorize(N, e, d):
    from math import gcd
    import gmpy2

    k = d*e - 1
    t = k
    while t % 2 == 0:
        t //= 2

    g = 3
    while True:
        x = pow(g, t, N)
        if x > 1:
            y = gcd(x - 1, N)
            if y > 1:
                return y, N//y
        g = gmpy2.next_prime(g)

出題例 募集中

φ(n)がわかっているときのnの素因数分解

そもそも \phi(n)がわかっているならsecret exponentが求められるのでわざわざ n素因数分解する必要はない。それでも素因数分解したい場合は n = pq, \phi(n) = pq - p - q + 1より、 b = n - phi + 1 = p + q としておくと、2次方程式の解と係数の関係から p,q = \frac{b \pm \sqrt(b^2 - 4n)}{2}として素因数が求まる

出題例 募集中

何度でも任意の暗号文を復号でき、復号結果のうち一部が手に入る (LSB Leak)

LSB Leak Attackが適用できる。一度に手に入る平文のbit数が多い代わりに、復号の試行回数に制限がある場合もある。LSB Leak Attackには2種類のアプローチがあると思っている。

一つはよく説明されるもので、次の通り。

 (2^eC)^d \equiv 2m \mod nについて考える。 2m \lt n であれば 2mは2倍されているので偶数、すなわちLSBは0となる。一方で 2m \gt nでれば、復号結果は 2m - n となるから( 2n \gt 2m \gt n )偶数と奇数の減算で奇数になる*1。すなわちLSBは1となる。ということは、 2^eCの復号結果のLSBが0ならば 0 \lt m \le \frac{n}{2}が、LSBが1ならば \frac{n}{2} \lt m \lt nがわかる。次に 4^eC についても同様に考えて、次々と mの範囲を2分探索的に縮めていき、 mの値を求める。

もう一つの方法は、次のようなもの。

 C \mod nの復号によって得られるLSB Oracle mの最下位bitである。では 2^{-e}C \mod nの復号結果から得られるLSB Oracleはどうか。 m = 2^{k}a_{k} + \cdots + 2^1a_1 + a_0 と書くと m2^{-1} \equiv a_1 + 2^{-1}a_0 \mod 2となる。ここで、 a_0は先程明らかになったため、簡単な計算で a_1を算出できる。同様に a_2, a_3, \dots と復元して a_{k}まで復元することで、 m全体を求めることができる。

出題例

pやqに関連する値を暗号化している

うまく暗号文同士のgcdをとったり、 \mod pなどについて考えることによって秘密鍵を入手できる場合がある。

出題例

mやp, q, dの値が一部わかっている、近似できる

LLLやCoppersmith methodを使ってmやp, q, dを求めることができる。Coppersmithも内部ではそれっぽい格子を生成してLLLをしているのでどちらでも解ける。sageに実装されているCoppersmith methodは一変数多項式に対するものだが、多変数多項式に対してはdefundさんが実装しているものが出来がよく、これを使っておけばだいたいなんとかなる。

github.com

出題例

dが同じでnやeが異なる暗号文 (Small Common Private Exponent)

かつ、dがある程度小さければSmall Common Private Exponent Attackができる。

出題例

かつ、 a,b 既知のとき、Franklin-Reiter's Related Message Attackが使える

出題例

ブロック暗号

ECBモードで、任意の平文+フラグが暗号化される

いわゆるChosen Plaintext Attackができる。

出題例

CBCモードで平文の先頭1ブロック程度を変更できれば良い (Bit Flipping)

Bit Flipping Attackで十分

出題例

CBCモードで復号の成否がわかる (Padding Oracle)

Padding Oracle (Encryption) Attackができる。

出題例

2段や3段の暗号化で、使われている鍵が短い (Meet in the Middle Attack)

Meet in the Middle Attackができる。

出題例

独自のS-BOXが使われている

Differential / Linear Cryptoanalysis だろうけど理解してないのでかけない

楕円曲線暗号

基本的な事項はだいたいすべて yoshi-gcc log - ふるつき にあります

その他の暗号

onetime pad

絶対にmany time padなので頻度解析をしながら鍵を当てていくとだんだん解けます。以前インタラクティブに解けるソルバを作ったので使い方を憶えると解きやすくなるはず

zer0pts / mtpsolver · GitLab

出題例

(EC)DSA で同一のnonceが複数回用いられている (Nonce Reuse)

いわゆるnonce-reuse attack

出題例

平文がフラグと連結、圧縮されてから暗号化される(圧縮サイドチャネル攻撃 / compression oracle

多くの圧縮手法では同一の平文が存在すると圧縮効率がよくなるため、もっとも圧縮効率がよくなる1文字を探索することでフラグに対するオラクルとすることができる。これはBEASTやCRIMEといった攻撃手法の原理(のはず)

出題例

*1:すなわち nが素因数に2を含んでいる時にはこの攻撃は成立しない、と思う