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$ が手に入る

出題例

InterKosenCTF writeup - ふるつき

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

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

出題例

Fireshell CTF 2019 Biggars writeup - ふるつき

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

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

出題例

PrimeParty - SECCON Beginners CTF 2022

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$ 全体を求めることができる。

出題例

$\mod 3$ でのLSB Leak Attack BambooFox CTF 2019 Oracle writeup - ふるつき

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

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

出題例

Harekaze mini CTF 2020 作問者writeup - ふるつき

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$ などを組み合わせて立式します。

出題例

mの一部がわかっている例 [InterKosenCTF 2019] E_S_P - HackMD
p, q がそれぞれ一部わかっている例 pwn2win 2020 writeup - ふるつき

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

出題例

3kCTF 2020 writeup - ふるつき

端的に言うと $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$ を共有します

出題例

Defenit CTF 2020 writeup - ふるつき

ブロック暗号

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

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

出題例

CSA Capture The Flag 2019 Writeup - よっちんのブログ（Flag Server）

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

Bit Flipping Attackで十分

出題例

ångstromCTF 2019 writeup - ふるつき

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

Padding Oracle (Encryption) Attackができる。

出題例

3kCTF 2020 writeup - ふるつき

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

Meet in the Middle Attackができる。

出題例

writeups/README.md at master · TFNS/writeups · GitHub

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

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

出題例

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$ を求めることができます。

出題例

nullcon HackIM 2019 Singular

楕円曲線上に存在しない点の演算ができる（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'$ の２つの楕円曲線上の点の演算は同じロジックになります。

出題例

TJCTF 2015 Curvature

乱数

線形合同法を用いている

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

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

出題例

kurenaif valentine problems the_big_five

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

出題例

https://yocchin.hatenablog.com/entry/2019/03/27/195800:title

(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$ 自身のみしか候補がありません

ふるつき

v('=')v かに

CTF crypto 逆引き

RSA

e が 3など (Low Public Exponent)

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

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

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

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

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

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

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