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

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

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

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行列 $B$ を $L$ の基底と呼びます。また、 $L$ の基底をノルムが小さい順に並べたとき、 $i$ 番目にくるベクトルを $\lambda_i({L})$ と表します。

CVPとSVP

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

しかし、対象とするベクトル空間に含まれるベクトル $v$ （ $L$ に含まれるとは限らない）が与えられたとき、 $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})$ を生成します。次に整数 $q$ を $q > \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で解きます。ここで

を定義します。さらに

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

このときもし $u$ が $m$ と一致すれば、 $VM = (u_0 \ u_1 \ \cdots \ u_{n-1} \ 0)$ になることが分かります。 $VM$ は基底ベクトルの線形結合なので、基底 $M$ の貼る格子 $L$ に含まれます。また、 $VM$ の要素は（ビットなので）0または1で、 $VM$ は $L$ 中の短いベクトルの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$ を考えます。

これを基底とし、 $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日目の序盤は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の予感がします。

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

ここで、 $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ビットです。とりあえず次のような基底を考えます。

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

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

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

あとは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は全部やってくれるので、私は変わらず楕円曲線暗号担当ということで......。ところで、はてなブログ数式使いにくすぎてお怒りです。