粗削りだけどとりあえず公開することにして、少しずつ情報を足していきたい。こういうケースがある、またこういう場合はどうすればよいのかという情報や質問をお待ちしています。
- 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さんが実装しているものが出来がよく、これを使っておけばだいたいなんとかなる。
出題例
- 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ができる。
出題例
独自のS-BOXが使われている
Differential / Linear Cryptoanalysis だろうけど理解してないのでかけない
楕円曲線暗号
基本的な事項はだいたいすべて yoshi-gcc log - ふるつき にあります
その他の暗号
onetime pad
絶対にmany time padなので頻度解析をしながら鍵を当てていくとだんだん解けます。以前インタラクティブに解けるソルバを作ったので使い方を憶えると解きやすくなるはず
https://gitlab.com/zer0pts/mtpsolver
出題例
(EC)DSA で同一のnonceが複数回用いられている (Nonce Reuse)
いわゆるnonce-reuse attack
出題例
平文がフラグと連結、圧縮されてから暗号化される(圧縮サイドチャネル攻撃 / compression oracle)
多くの圧縮手法では同一の平文が存在すると圧縮効率がよくなるため、もっとも圧縮効率がよくなる1文字を探索することでフラグに対するオラクルとすることができる。これはBEASTやCRIMEといった攻撃手法の原理(のはず)
出題例
Hack.lu CTF 2016 供養(Writeup) - ももいろテクノロジー (cornelius1)
insomnihack-teaser-ctf-2019/drinks at master · newjam/insomnihack-teaser-ctf-2019 · GitHub
*1:すなわちが素因数に2を含んでいる時にはこの攻撃は成立しない、と思う