ふるつき

v(*'='*)v かに

CTF crypto 逆引き

theoremoon/ctf-crypto-dict へのコントリビュートお待ちしております。こういう内容についても書いてほしいみたいな場合もissueとか建ててくれるとそのうちやるかも

RSA

黙って Twenty Years of Attacks on the RSA Cryptosystem や Recovering 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

Coppersmith method適用のための典型的な立式

基本的には以下の2種類の式か、この式のmodを開いて（＝ a \equiv b \mod mを適当な整数 kを持ってきて a = b + kmと変形して）別の変数でmodを取り直した形の式で小さい根が求められないか考えることになります。

  • c \equiv m^e \mod n または c^d \equiv m \mod n
  • ed \equiv 1 \mod \phi

RSAの基本的な変数の他に特別な値が渡されている場合（ nや p, qの構成方法が特殊で、構成に用いる一部の値や式が公開されているなど）はその式やその式と上式、 n = pq, \phi = (p-1)(q-1) = N - (p+q) + 1などを組み合わせて立式します。

出題例

pやqに関連する値が追加で渡されている

r = f(p, q)や x = f(p, q)としてRSAのパラメータ n, e, cの他に p, qのヒントとなるような値を与えられているときは rや xについて \mod p, \mod qの式を立ててCoppersmith Methodをすると良いです。

出題例 - Leaky RSA - RTACTF upsolve - ふるつき

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

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

出題例

端的に言うと f_1, f_2という多項式があって、これらが同じ根を持つときに Franklin-Reiter's Related Message Attackが使える。典型的には c_1 = m^e \mod n, c_2 = (am + b)^e \mod nで a, bが明らかになっている場合には、未知数を xとおいて f_1 = c_1 - x^e, f_2 = c_2 - (ax + b)^eというような式を建てると2つの多項式が同じ根 mを共有します

出題例

ブロック暗号

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ができる。

出題例

複数のラウンドで同じ鍵が使われている / 同じ鍵によって複数段の暗号化が行われている (slide attack)

平文と暗号のペアを十分な数得られる場合にはslide attackが適用可能かもしれません。詳しくは slide attack - Plaid CTF 2022 choreography upsolve - ふるつき をご参照ください

出題例

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

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

楕円曲線暗号

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

位数が小さい素因数の積に分解できる (Pohlig-Hellman Attack)

楕円曲線に限った話ではなく一般の離散対数問題について言えることですが、位数が小さい素因数の積に分解できる時、元の群を小さい位数を持つ別の群に移してから離散対数問題を解き、CRTで元の群での離散対数問題を解くというPohlig-Hellman 攻撃が可能です。

雑に数式を持ってきて説明すると、ある曲線 Eがあって Q = xPなる P, Qが与えられて xを求めたいといういわゆる(EC)DLPを解きたいとします。このとき、 Eの位数 nが小さい素因数 p_1, p_2, \dotsの積に素因数分解できているとして、 n = \prod p_i ^ {e_i}と表しておきます*2。

このとき Q = xPのかわりに、ある素因数 p_iを持ってきて (n/p_i)Q = y_i(n/p_i)Pという式を考えるというのがPohlig-Hellman Attackのアイデアです。 (n/p_i)P, (n/p_i)Qは p_i倍すると p_i * (n / p_i)P = nP = G というふうに単位元と一致するので、点 (n/p_i)P, (n/p_i)Qの位数は p_iです*3。点の位数 p_iが十分小さければ、 (n/p_i)Q = y(n/p_i)Pとなるような yを求めることは容易く、 y_i \equiv x \mod p_iです。いろんな素因数 p_iについてかんたんな離散対数問題を解き、集めた y_i \equiv x \mod p_iの組から中国剰余定理を用いて xを求めることができます。

出題例 - PicoCTF 2017 - ECC2

位数と剰余の法が同じであるような楕円曲線である（SSSA Attack）

楕円曲線 y^2 \equiv x^3 + ax + b \mod pの剰余の法 pとその位数（ここでは nとします）が同じであるとき（つまり n = pであるとき）、その曲線はAnomalousであるといい、SSSA Attackと言われる手法を用いることで2点 P, Qから Q = xPとなるような xを求める(EC)DLPが簡単にとけます。この手法について簡潔に説明するのは難しいので私がめちゃくちゃ説明上手になるまではこのページには説明はかけません。ごめん

出題例

楕円曲線にcusp型の特異点が存在する（Singularな楕円曲線）

特異点が存在するような楕円曲線の場合、特殊な形式になっているため楕円曲線よりも簡単な演算を行う別の群への同型写像が定義できる場合があります。特にcusp型と呼ばれる楕円曲線は加法群への写像が定義できるため、離散対数問題が整数の除算と対応し簡単に解けます。 曲線がsingularか、またcusp型かどうか判別する手段についてはこのページでは解説を省きますが、Sagemathを使っている場合Singularな楕円曲線をEllipticCurveクラスを使用して定義しようとすると例外が発生することで気がつけると思います

実際にcusp型の楕円曲線に遭遇した場合には、特異点が原点になるように楕円曲線を平行移動すると y^2 = x^3 \mod pという非常に単純な式になります。曲線上の点 (x, y)は (x, y) \to x / y \mod pという写像によって \mathbb{F}_p上の値に写すことができ、また z \in \mathbb{F}_pは[z \mod p → (z^{-2} \mod p, z^{-3} \mod p)]という逆写像によって楕円曲線上の点に戻すことができます。

したがって、cusp型の楕円曲線上の離散対数問題 Q = dPは P, Qを平行移動して y^2 = x^3 \mod p上の点にしてから、 (x, y) \to x / y \mod pという写像で有限体上の値に移し、 \mod pの除算で dを求めることができます。

出題例

楕円曲線上に存在しない点の演算ができる（Invalid Curve Attack)

例えば楕円曲線 E: y^2 \equiv x^3 + ax + b \mod p上の点 Pをこちらが指定するとそれを x倍した点 Qを返してくれるので xを求めよという問題は楕円曲線のパラメータが安全であれば基本的に解くことは難しいです。

しかし、うっかりこちらが指定した点が楕円曲線上に存在するかどうかが判定されていない場合、別の楕円曲線 E': y^2 \equiv x^3 + ax + b' \mod p上の点 P'を指定することで Q' = xP'を計算させることができます。ここで上述されているような脆弱なパラメータの楕円曲線を指定しておけばそれらの手法を利用して xを求めることができます。

なぜ E上の乗算処理が行われるはずのロジックに対して E'上の点を渡して正しく x倍されるのかといえば、楕円曲線の加算（及びその繰り返し二乗法で実装されている乗算）では曲線のパラメータのうち bが使われていないからです。したがって、定数項 bの値のみが異なる Eと E'の２つの楕円曲線上の点の演算は同じロジックになります。

出題例

乱数

線形合同法を用いている

線形合同法は x_{i+1} \equiv Ax_{i} + B \mod Mという漸化式で表される単純な乱数生成器です。ある時点の出力が得られれば前後すべての出力を計算できるほか、 A, B, Mといったパラメータが未知の場合でも、複数の出力からこれらのパラメータを復元することもできます。

詳しくは kurenaif さんの動画で解説されているのでそちらを参照してください

出題例

LFSR

単純なLFSRならz3で殴ると解けます。それより難しい問題については魔女のお茶会 2022/春でy011d4さんが発表していたLFSRの超難問を解くというスライドを参照されてください

mersenne twisterで624個の連続した出力が得られる

mersenne twisterは624個の値からなる内部状態を持っており、複数の値に対してtwist処理を行って周期が長く予測が困難な乱数を生成しますが、出力をuntwistして内部状態を復元することができ、624個の連続した出力が得られれば内部状態を完全に復元できます。

内部状態の復元には kmyk/mersenne-twister-predictor が便利です。

また、出力の一部が欠落しているような場合にも十分な数の出力が得られるならば、z3などを用いて内部状態を探索可能であることも知られています。こちらは icemonster/symbolic_mersenne_cracker に実装があります。

出題例 - SECCON Beginners CTF 2022 Unpredictable Pad

その他の暗号

onetime pad

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

https://github.com/zer0pts/mtpsolver

出題例

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

いわゆるnonce-reuse attack

出題例

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

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

出題例

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

*2:どの素因数 p_iもある数 Bより小さい時 nはB-smoothであると言ったりします

*3:この説明だと位数は p_iの約数ですとまでしか言えないんですが、 p_iは素数なので1か p_i自身のみしか候補がありません