ふるつき

v(*'='*)v かに

CTF crypto 逆引き

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

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はどうか。これは 2^{-1}m \mod nの最下位bitであり、 mの下から2番目のbitの値である。さらに 2^{-2e}C \mod nの復号結果か得られるLSB Oracleは mの下から3番目のbitの値で……とこれを mのbit数だけ繰り返すことで 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ができる。

出題例

２つの平文の間にm1 = a*m2 + bという関係がある (Franklin-Reiter's Related Message 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を含んでいる時にはこの攻撃は成立しない、と思う