theoremoon/ctf-crypto-dict へのコントリビュートお待ちしております。こういう内容についても書いてほしいみたいな場合もissueとか建ててくれるとそのうちやるかも
- RSA
- e が 3など (Low Public Exponent)
- nが多くの素因数に分解される
- nがある素数と別の合成数までは素因数分解できる
- nが同じでeが異なる複数の暗号文 (Common Modulus)
- e, dがわかっているときにnを素因数分解する
- φ(n)がわかっているときのnの素因数分解
- 何度でも任意の暗号文を復号でき、復号結果のうち一部が手に入る (LSB Leak)
- pやqに関連する値を暗号化している
- mやp, q, dの値が一部わかっている、近似できる
- pやqに関連する値が追加で渡されている
- dが同じでnやeが異なる暗号文 (Small Common Private Exponent)
- 2つの平文の間に線形に表される関係がある (Franklin-Reiter's Related Message Attack)
- ブロック暗号
- 楕円曲線暗号
- 乱数
- その他の暗号
RSA
黙って Twenty Years of Attacks on the RSA Cryptosystem や Recovering cryptographic keys from partial information, by example を読んでおけば大体なんとかなる
e が 3など (Low Public Exponent)
例えば、 であればe乗根を取ることで
が手に入る
出題例
nが多くの素因数に分解される
いわゆるMulti-Prime RSA。がどう素因数分解されようともオイラーのφ関数は定義できて、
での位数がわかるので逆元
が求められる。
出題例
nがある素数と別の合成数までは素因数分解できる
実際には だが、
でnを素因数分解した結果
(ここで
)までは得られたが、
の素因数分解は難しそう、というとき。このとき
であれば、
の世界で考えることで
を得られる。
出題例
nが同じでeが異なる複数の暗号文 (Common Modulus)
Common Modulus Attackが適用できる。複数のが互いに素ではない場合には、それぞれの
の最大公約数を公開鍵とした暗号文が手に入ることになる
出題例 募集中
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の素因数分解
そもそもがわかっているならsecret exponentが求められるのでわざわざ
を素因数分解する必要はない。それでも素因数分解したい場合は
より、
としておくと、2次方程式の解と係数の関係から
として素因数が求まる
出題例 募集中
何度でも任意の暗号文を復号でき、復号結果のうち一部が手に入る (LSB Leak)
LSB Leak Attackが適用できる。一度に手に入る平文のbit数が多い代わりに、復号の試行回数に制限がある場合もある。LSB Leak Attackには2種類のアプローチがあると思っている。
一つはよく説明されるもので、次の通り。
について考える。
であれば
は2倍されているので偶数、すなわちLSBは0となる。一方で
でれば、復号結果は
となるから(
)偶数と奇数の減算で奇数になる*1。すなわちLSBは1となる。ということは、
の復号結果のLSBが0ならば
が、LSBが1ならば
がわかる。次に
についても同様に考えて、次々と
の範囲を2分探索的に縮めていき、
の値を求める。
もう一つの方法は、次のようなもの。
の復号によって得られるLSB Oracleは
の最下位bitである。では
の復号結果から得られるLSB Oracleはどうか。
と書くと
となる。ここで、
は先程明らかになったため、簡単な計算で
を算出できる。同様に
と復元して
まで復元することで、
全体を求めることができる。
出題例
でのLSB Leak Attack BambooFox CTF 2019 Oracle writeup - ふるつき
pやqに関連する値を暗号化している
うまく暗号文同士のgcdをとったり、などについて考えることによって秘密鍵を入手できる場合がある。
出題例
mやp, q, dの値が一部わかっている、近似できる
LLLやCoppersmith methodを使ってmやp, q, dを求めることができる。Coppersmithも内部ではそれっぽい格子を生成してLLLをしているのでどちらでも解ける。sageに実装されているCoppersmith methodは一変数多項式に対するものだが、多変数多項式に対してはdefundさんが実装しているものが出来がよく、これを使っておけばだいたいなんとかなる。
Coppersmith method適用のための典型的な立式
基本的には以下の2種類の式か、この式のmodを開いて(=を適当な整数
を持ってきて
と変形して)別の変数でmodを取り直した形の式で小さい根が求められないか考えることになります。
または
RSAの基本的な変数の他に特別な値が渡されている場合(や
の構成方法が特殊で、構成に用いる一部の値や式が公開されているなど)はその式やその式と上式、
などを組み合わせて立式します。
出題例
- mの一部がわかっている例 [InterKosenCTF 2019] E_S_P - HackMD
- p, q がそれぞれ一部わかっている例 pwn2win 2020 writeup - ふるつき
pやqに関連する値が追加で渡されている
や
としてRSAのパラメータ
の他に
のヒントとなるような値を与えられているときは
や
について
の式を立ててCoppersmith Methodをすると良いです。
出題例 - Leaky RSA - RTACTF upsolve - ふるつき
dが同じでnやeが異なる暗号文 (Small Common Private Exponent)
かつ、dがある程度小さければSmall Common Private Exponent Attackができる。
出題例
2つの平文の間に線形に表される関係がある (Franklin-Reiter's Related Message Attack)
端的に言うとという多項式があって、これらが同じ根を持つときに Franklin-Reiter's Related Message Attackが使える。典型的には
で
が明らかになっている場合には、未知数を
とおいて
というような式を建てると2つの多項式が同じ根
を共有します
出題例
ブロック暗号
ECBモードで、任意の平文+フラグが暗号化される
いわゆるChosen Plaintext Attackができる。
出題例
- CSA Capture The Flag 2019 Writeup - よっちんのブログ(Flag Server)
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 攻撃が可能です。
雑に数式を持ってきて説明すると、ある曲線があって
なる
が与えられて
を求めたいといういわゆる(EC)DLPを解きたいとします。このとき、
の位数
が小さい素因数
の積に素因数分解できているとして、
と表しておきます*2。
このときのかわりに、ある素因数
を持ってきて
という式を考えるというのがPohlig-Hellman Attackのアイデアです。
は
倍すると
というふうに単位元と一致するので、点
の位数は
です*3。点の位数
が十分小さければ、
となるような
を求めることは容易く、
です。いろんな素因数
についてかんたんな離散対数問題を解き、集めた
の組から中国剰余定理を用いて
を求めることができます。
出題例 - PicoCTF 2017 - ECC2
位数と剰余の法が同じであるような楕円曲線である(SSSA Attack)
楕円曲線の剰余の法
とその位数(ここでは
とします)が同じであるとき(つまり
であるとき)、その曲線はAnomalousであるといい、SSSA Attackと言われる手法を用いることで2点
から
となるような
を求める(EC)DLPが簡単にとけます。この手法について簡潔に説明するのは難しいので私がめちゃくちゃ説明上手になるまではこのページには説明はかけません。ごめん
出題例
楕円曲線にcusp型の特異点が存在する(Singularな楕円曲線)
特異点が存在するような楕円曲線の場合、特殊な形式になっているため楕円曲線よりも簡単な演算を行う別の群への同型写像が定義できる場合があります。特にcusp型と呼ばれる楕円曲線は加法群への写像が定義できるため、離散対数問題が整数の除算と対応し簡単に解けます。
曲線がsingularか、またcusp型かどうか判別する手段についてはこのページでは解説を省きますが、Sagemathを使っている場合Singularな楕円曲線をEllipticCurve
クラスを使用して定義しようとすると例外が発生することで気がつけると思います
実際にcusp型の楕円曲線に遭遇した場合には、特異点が原点になるように楕円曲線を平行移動するとという非常に単純な式になります。曲線上の点
は
という写像によって
上の値に写すことができ、また
は[z \mod p → (z^{-2} \mod p, z^{-3} \mod p)]という逆写像によって楕円曲線上の点に戻すことができます。
したがって、cusp型の楕円曲線上の離散対数問題は
を平行移動して
上の点にしてから、
という写像で有限体上の値に移し、
の除算で
を求めることができます。
出題例
楕円曲線上に存在しない点の演算ができる(Invalid Curve Attack)
例えば楕円曲線上の点
をこちらが指定するとそれを
倍した点
を返してくれるので
を求めよという問題は楕円曲線のパラメータが安全であれば基本的に解くことは難しいです。
しかし、うっかりこちらが指定した点が楕円曲線上に存在するかどうかが判定されていない場合、別の楕円曲線上の点
を指定することで
を計算させることができます。ここで上述されているような脆弱なパラメータの楕円曲線を指定しておけばそれらの手法を利用して
を求めることができます。
なぜ上の乗算処理が行われるはずのロジックに対して
上の点を渡して正しく
倍されるのかといえば、楕円曲線の加算(及びその繰り返し二乗法で実装されている乗算)では曲線のパラメータのうち
が使われていないからです。したがって、定数項
の値のみが異なる
と
の2つの楕円曲線上の点の演算は同じロジックになります。
出題例
乱数
線形合同法を用いている
線形合同法はという漸化式で表される単純な乱数生成器です。ある時点の出力が得られれば前後すべての出力を計算できるほか、
といったパラメータが未知の場合でも、複数の出力からこれらのパラメータを復元することもできます。
詳しくは 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といった攻撃手法の原理(のはず)
出題例