CTFするぞ

CTF以外のことも書くよ

LLLで殴る【yoshi-camp 2020 Spring備忘録】

はじめに

去年に続き、今年もyoshi-campがありました。 今年はコロナ殿の影響でDiscordを使ってリモートで講義をしました。 今回は、ふるつきがLLLの理論を、yoshikingがLLLの実践を講義してくれました。 私は楕円曲線暗号の攻撃手法を出来る限りたくさんスクリプトを書かせる形式で講義しました。 チームで分からないところを勉強して共有する目的なので、理解した内容に誤りがあるかもなので、そのつもりで読んでください。

みんな暗号にあんまり自信が無いのでスクリプトも講義資料も基本非公開で...... :bow:

1日目 LLL

1日目はふるつきがLLLの理論と、sageを使った攻撃方法を教えてくれました。

格子

互いに独立なn次元の基底ベクトルb_i (i \in {1, 2, \cdots, m})に対して、格子Lは次のように定義される集合です。(はてなtex集合の括弧が出てない?)


L = { \sum{{a_i}{b_i}} \mid a_i \in \mathbb{Z} }

要するに基底ベクトルを組み合わせて表現できるすべての座標を表しています。 なお、暗号の世界では基底や係数として整数を使います。

基底ベクトルを列に持つn×m行列BL基底と呼びます。 また、Lの基底をノルムが小さい順に並べたとき、i番目にくるベクトルを\lambda_i({L})と表します。

CVPとSVP

当たり前ですが、格子Lを貼る基底は複数存在します。

しかし、対象とするベクトル空間に含まれるベクトルvLに含まれるとは限らない)が与えられたとき、vに最も近い格子L上の点を見つけることは困難とされています。 これをClosest Vector Problem(CVP)と呼びます。

また、基底の組を使って表される非零な最短ベクトルを求めることも困難とされています。 これをShortest Vector Problem(SVP)と呼びます。

LLLの概要

LLLとは、格子Lの基底Bを与えた時、格子Lを貼る小さな基底B'を求めるアルゴリズムです。 基底のノルムを小さくするのでLLL base reductionとも言われます。 LLLを使うと、B'の各ベクトルのノルムは次のLLL条件を満たすことが知られています。


|b_i| \leq 2^{\cfrac{n-1}{4}}vol(L)^{\cfrac{1}{n}}

LLLはSVPを解くのに使えます。 SVPは次元数が2のとき厳密に解くことが可能で、3〜100程度になるとLLLで現実的な時間で解くことが可能で、それ以上になると計算能力やsegment-LLLと呼ばれる高速化手法で殴るらしいです。

LLLを利用した攻撃

Markle-Hellman Knapsack暗号

LLLがそのまま適用できる攻撃対象として、Markle-Hellman Knapsack暗号があります。

nビットの平文(m_{0}, m_{1}, \cdots, m_{n-1})を暗号化するために、まず超増加列w = (w_{0}, w_{1}, \cdots, w_{n-1})を生成します。 次に整数qq > \sum^{n-1}_{i=0} w_{i}を満たすようにランダムに選び、更に\gcd(r, q) = 1なる整数rをランダムに選びます。 このとき公開鍵は\beta = (\beta_{0}, \beta_{1}, \cdots, \beta_{n-1}) \ \ (\beta_{i} = rw_{i} \mod q)で、秘密鍵(w, q, r)です。

暗号化するにはc = \sum^{n-1}_{i=0} \beta_{i} m_{i}を計算します。

これをLLLで解きます。 ここで

V= \begin{pmatrix} u_0 & u_1 & \cdots & u_{n-1} & 1 \end{pmatrix}

を定義します。さらに


M = \begin{pmatrix}
1 & \cdots & 0 & b_0 \\
\vdots & \ddots & \vdots & \vdots \\
0 & \cdots & 1 & b_{n-1} \\
0 & \cdots & 0 & -c
\end{pmatrix}

と定義します。単位行列になっている部分は、線形独立にしてかつ単純という理由でそう置いているだけです。

このときもしumと一致すれば、VM = (u_0 \ u_1 \ \cdots \ u_{n-1} \ 0)になることが分かります。 VMは基底ベクトルの線形結合なので、基底Mの貼る格子Lに含まれます。 また、VMの要素は(ビットなので)0または1で、VML中の短いベクトルの1つであることが想像できます。

つまり、Mが貼る格子をLLLに投げればmが求まるかもしれませんし求まらないかもしれません。 適当に聞こえるかもしれませんが、講義で扱った攻撃はなんとなくパラメータを調整するなど案外適当でした。

Rolling Hash

Rolling Hashとは文字列ハッシュ関数の1つで、結果だけ説明すると定数H, B, Nに対して

RH(s) = (HB^{n} + \sum{s_{n-i-1} B^{i}}) \mod N

で計算される関数のことです。pythonで書くとコロコロしている感がありますね。(はてなシンタックスハイライトと行列が同時に使えないので色無し)

def rollingHash(s):
    h = H
    for c in s:
        h = ((h + ord(c)) * B) % N
    return h

ハッシュ値が与えられたとき、指定した長さで同じハッシュ値を得られる別の入力をLLLで求めます。

方法としては、sの末尾k文字に差分a_iを与えます。 このとき、\sum{a_{i} B^{i}} \equiv 0 \mod Nが成り立てばハッシュ値が変わらないことが分かります。 ここで、次のような基底Bを考えます。

B = \begin{pmatrix}
1 & 0 & \cdots & 0 & B^k \\
0 & 1 & \cdots & 0 & B^{k-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & B^1 \\
0 & 0 & \cdots & 0 & -tN
\end{pmatrix}

これを基底とし、V = (a_{0} \ a_{1} \ \cdots \ a_{k-1} \ 1)で線形結合すれば良さそうです。 ということで、BをLLLに投げます。(tの値は分からないので総当りします。)

for t in range(1, 100):
    M = [
        [0 for j in range(k+1)]
        for i in range(k+1)
    ]
    for i in range(k):
        M[i][i] = 1
        M[i][k] = pow(B, k-i, N)
    M[k][k] = -t*N
    M = matrix(ZZ, M)
    for row in M.LLL():
        if row[-1] != 0: continue
        s2 = list(plain)
        for i, a in enumerate(row[:-1]):
            s2[-k+i] = chr(ord(s2[-k+i]) + a)
        s2 = "".join(s2)
        print("RH({}) = {}".format(repr(s2), hex(rollingHash(s2))))

例えば"Hello, World!"に対して半分くらい残した状態でハッシュ値が同じものを探索すると、いくつか見つかりました。

RH('Hello, World!') = 0x919b3cf0
RH('Hello, \\iRQ\\\x0e') = 0x919b3cf0
RH('Hello, Bh\x85Zn ') = 0x919b3cf0
RH('Hello, \\iRQ\\\x0e') = 0x919b3cf0
RH('Hello, gPx_l\x05') = 0x919b3cf0
RH('Hello, \\iRQ\\\x0e') = 0x919b3cf0
RH('Hello, bV\x98zt\x18') = 0x919b3cf0
RH('Hello, ffss\x84 ') = 0x919b3cf0
RH('Hello, \x1d\\\x94gW%') = 0x919b3cf0
RH('Hello, Ru\x92\x87l4') = 0x919b3cf0
RH('Hello, al\x93\x8e\x8c3') = 0x919b3cf0
RH('Hello, w\x81\x83z\x83/') = 0x919b3cf0

2日目 LLL + 楕円曲線

2日目の序盤はyoshikingがLLLを使って解ける難しい問題を説明してくれました。 後半は私が楕円曲線に対する攻撃手法を、過去にCTFに出題されたものを優先的に片っ端から実装させました。

CTFの問題を解く - not so hard RSA

HITCON 2019 Qualsの暗号問題です。以下のスクリプトと実行結果が与えられます。

from Crypto.Util.number import *
from secrets import d, flag
from os import urandom

T = 10
def encrypt(data):
    num = bytes_to_long(data)
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    assert num < n
    phi = (p-1)*(q-1)
    e = inverse(d,phi)
    a = pow(num,e,n)
    enc = hex(a)
    return (n,e,enc)

print(d.bit_length())
for _ in range(T):
    data = flag + urandom(40)
    print(encrypt(data))

フラグに40バイトのゴミを付けてRSAで暗号化した結果と公開鍵が貰えます。秘密鍵のdが固定になっているので、これを得ることがとりあえずの目標です。 また、dのビット数が465bitであることが分かっています。nが1024ビットなのに対して小さいので、LLLの予感がします。

まずは分かっている情報から基底を作ります。

\begin{align}
e_{i}d - 1 &= k_{i}\phi(n_{i}) \\
&= k_{i}(p_{i}-1)(q_{i}-1) \\
&= k_{i}(n_{i} - p_{i} - q_{i} + 1) \\
k_{i}n_{i} - e_{i}d +1 &= k_{i}(p_{i} + q_{i} - 1)
\end{align}

ここで、k_iのビット数は1以上\min(e_i, d)以下なので、k_{i}n_{i}のビット数は最大465+1024=1489ビットです。 同様に、e_{i}dのビット数は最大1489ビット、k_{i}(p_{i} + q_{i} - 1)は最大465+512=977ビットです。 とりあえず次のような基底を考えます。

\begin{pmatrix}
-e_{1} & n_{1} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
-e_{10} & 0 & \cdots & n_{10} \\
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 1
\end{pmatrix} ^T

V = (d \ k_1 \ k_2 \ \cdots \ k_{10})で考えます。 ここでdなどは465ビットと小さいので、次のように格子を変更してビット数を揃えます。

\begin{pmatrix}
-e_{1} & n_{1} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
-e_{10} & 0 & \cdots & n_{10} \\
2^{512} & 0 & \cdots & 0 \\
0 & 2^{512} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 2^{512}
\end{pmatrix} ^T

この操作をスケーリングと言うそうです。 ただ、残念ながらこの基底でも正しいshort vectorは見つかりません。 そこで、VMのビット数をできるだけ減らすことを考えます。

\begin{align}
k_{i}n_{i} - e_{i}d +1 &= k_{i}(p_{i} + q_{i} - 1) \\
k_{i}(n_{i} - p_{i} - q_{i}) - e_{i}d &= - k_{i} - 1 \\
k_{i}(n_{i} - 2\sqrt{n_{i}}) - e_{i}d &\simeq - k_{i}
\end{align}

偉い人にはこの変換が思いつくらしい。 あとはこれで基底を作ります。

\begin{pmatrix}
-e_{1} & n_{1} - 2\sqrt{n_{1}} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
-e_{10} & 0 & \cdots & n_{10} - 2\sqrt{n_{10}} \\
2^{512} & 0 & \cdots & 0 \\
0 & 2^{512} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 2^{512}
\end{pmatrix} ^T

あとはLLLが正しいshort vectorを見つけてくれることを :pray: してスクリプトを回します。

B = [
    [0 for j in range(21)]
    for i in range(11)
]
for i in range(10):
    B[0][i] = -e[i]
    B[1+i][i] = n[i] - int(2*sqrt(n[i]))
    B[i][10+i] = 2**512

for i in range(11):
    print(i, [x.bit_length() for x in B[i]])
M = matrix(ZZ, B)

for row in M.LLL():
    if row[10] % 2**512 == 0:
        d = abs(row[10] // 2**512)
        if pow(2, e[0]*d, n[0]) == 2:
            print(bytes.fromhex(hex(power_mod(c[0], d, n[0]))[2:]))

うっほい。

0 [1020, 1022, 1024, 1024, 1018, 1022, 1023, 1023, 1022, 1023, 513, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1 [1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2 [0, 1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0, 0, 0, 0, 0, 0, 0, 0]
3 [0, 0, 1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0, 0, 0, 0, 0, 0, 0]
4 [0, 0, 0, 1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0, 0, 0, 0, 0, 0]
5 [0, 0, 0, 0, 1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0, 0, 0, 0, 0]
6 [0, 0, 0, 0, 0, 1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0, 0, 0, 0]
7 [0, 0, 0, 0, 0, 0, 1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0, 0, 0]
8 [0, 0, 0, 0, 0, 0, 0, 1023, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0, 0]
9 [0, 0, 0, 0, 0, 0, 0, 0, 1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513, 0]
10 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b"hitcon{recover_everything_by_amazing_LLL_algorithm!!}\x97\xe4\xa2_\x81\x15(5b\xcf\x9d\x01\x1f^g\x03\x12\xc0\xbfAm\xb5\xf4H\x98+\xab\xc2\xd4\x1d\x9a\xfaZ/\xb8\x91y'\x87\x04"

楕円曲線

私が講義したので特に記録することはなし。 Pohlig-Hellman Attack、Singularな曲線に対する攻撃、Anomalousな曲線に対する攻撃を実装させました。 Supersingularな曲線に対するMOV Attackはソースコードだけポイして、Invalid Curve Attackは原理だけ説明して実装は宿題にしました。 (資料作る時間なくてごめん。) といっても実質Pohlig-Hellmanなので終了。

@yoshiking @theoremoon 言ってなかったけどSingularでNode型の曲線に対する攻撃も宿題にします。

疑問点

分からなかった部分もいっぱい。

  • LLLで解けたり解けなかったりする条件がよく分からない
  • LLLで基底ベクトルを近似して良い理由や、その精度がよく分からない
  • パラメータに対するInvalid Curve Attackで、楕円曲線に脆弱な位数を持たせるBを効率的に求める方法が分からない
  • ベースポイントに対するInvalid Curve Attackで、Twist上で脆弱な点を効率的に求める方法が分からない

感想

前回と違いリモートなので疲労が少なかったですが、進捗が分からないのと接続の調子によって画質や音質が変わるのでやっぱりオフラインがいいです。 まだLLLを使いこなせる気がしませんが、ちょくちょく問題を解いて身につけようと思います。 まぁyoshikingとtheoremoonがLLLは全部やってくれるので、私は変わらず楕円曲線暗号担当ということで......。 ところで、はてなブログ数式使いにくすぎてお怒りです。