はじめに
security-camp2021 L-Ⅰ（暗号解読チャレンジゼミ）を履修しました。2か月間でCopperSmith's Methodの理解と実装を行いました。
ちなみに成果物はGitHubにもあります。
学んだこと
以降、hastad_broadcast_attack, shortpad_attack, stereotyped_message_attackの理解・実装を行ったので、それぞれ勉強したことを書きます。
Hastad Broadcast Attack
概要
同一の平文$M$を$k$人に対して送る例を考えます。このとき、$i$番目の人の暗号文$C_i$は以下の様に計算できます。
$$
C_i = M^e \mod N_i
$$
ここで仮に$e=3$と置いたとき、
$$
C∊Z^{*}_{N_1N_2N_3}
$$
となり、また平文$M$より$N$のほうが常に大きいことからCRTを用いて、
C≡M^3 \mod N_1N_2N_3 \\
C=M^3
がわかります。
このように平文をそのままブロードキャストする例だとCRTによって簡単に復号できそうな気がします。しかし、
$$
M_i=a_i・M + b_i \
C_i = M_i^e \mod N_i
$$
のように線形パディングをした場合はそのままCRTを適合することはできません。ここで役に立つのがCopperSmith's Methodです。
攻撃
M_i=a_i・M + b_i \\
C_i = M_i^e \mod N_i
の線形パディングでのCopperSmith's Method適応方法について考えてみます。
まずCRTで全ての$j$に対して$T_i=1 \mod N_i$で、$T_i=0 \mod N_{i≠j}$となるような$T_i$を求め、多項式環$g_i(x)$を以下の様に定めます。
$$
g_i(x)= \sum_{i=1}^{e} T_i・((a_i・M+b_i)^e-C_i)
$$
ここで全ての$i$に対して$T_j=0 \mod n_i (i≠j)$または$(a_i・M+b_i)^5=c_i \mod n_i$が成り立つので、$g(m) \mod n_i=0$となります。
この仮定のもと、全ての$i$に対して$(N_i, g_i)$の組が得られれば効率的に$M$を復号することができます。
条件
係数$T_i$を求めるのにCRTを使うのでまず$e$個以上の$(N_i, g_i)$の組が分かっている必要があり、またパディング方法は線形である必要があります。ランダムパディングについては有効な攻撃方法とはなりえません。
スクリプト
以降、攻撃スクリプトを示します。SageMath version 9.0を使用しました。
from Crypto.Util.number import *
from random import getrandbits
class RSA:
def __init__(self, bits):
self.A, self.B = [], [] # padding number
self.N = [] # public key
assert bits % 2 == 0
self.bits = bits // 2
def gen_new_key(self):
self.p = getPrime(self.bits)
self.q = getPrime(self.bits)
self.ni = self.p * self.q
self.N.append(self.ni)
self.e = 5
phi = (self.p - 1) * (self.q - 1)
self.d = inverse(self.e, phi)
def encryption(self, m):
c = pow(m, self.e, self.ni)
return c
def padding(self, m, bits):
a, b = getrandbits(bits), getrandbits(bits)
self.A.append(a)
self.B.append(b)
m = a * m + b
return m
def HastadBroadcastAttack(self, dig, ciphers):
G.<x> = PolynomialRing(Zmod(prod(self.N)), implementation='NTL')
H = []
for i in range(dig):
h = (self.A[i]*x + self.B[i])^e - ciphers[i]
h *= inverse_mod(int(h.lc()), self.N[i])
H.append(h)
# find coefficient T
T = []
for i in range(dig):
mat = [0] * dig
mat[i] = 1
t = CRT(mat, self.N)
T.append(t)
g = sum([t * h for t, h in zip(T, H)])
roots = g.small_roots()
if len(roots):
return long_to_bytes(int(roots[0]))
else:
return "Not found..."
bits = 2048
dig = 5
r = RSA(bits)
m = bytes_to_long(b"Hastad_Broadcast_attack!!!!!!!!")
ciphers = []
for i in range(dig):
r.gen_new_key()
cipher = r.encryption(r.padding(m, 512))
ciphers.append(int(cipher))
print(r.HastadBroadcastAttack(dig, ciphers))
Coppersmith's short-pad attack
概要
2つの平文の差が十分に小さい場合、Coppersmith's short-pad attackで復号することができます。Frankin-Reiter Related Message Attackと違い、平文の差$d$が判明している必要はありません。
定理
以下の式（パディング処理）について考えます。
m=\lfloor n/e^2 \rfloor \\
M_1=2^mM+r_1 \\
M_2=2^mM+r_2
ここで、$M$は長さが最大$n-m$ bitのメッセージ、$r_1, r_2$は、$0≤r_1,r_2<2^m$を満たす整数です。
このとき、攻撃者が公開鍵の組$N, e$と$M_1, M_2$の暗号文$C_1, C_2$を得られれば、$M$を復号することができます。
攻撃
以下のような$g_1, g_2$を定義します。
g_1(x, y)=x^e-C_1 \\
g_2(x, y)=(x+y)^e-C_2
ここで、$y=r2-r1$のとき、多項式は$x=M_1$を共通根を持つことが分かります。つまり、$d=r_2-r_1$は終結式(resultant)$h(y)$の根となります。これで2変数の式を$y$だけの式にできたので、Coppersmith's Methodで解くことで$d$を求めることができます。
あとはFranklin-Reiter Related Message Attackで平文に復号することができます。
条件
終結式は展開すると$e^2$の多項式になるので、Coppersmith's Methodで方程式を解くことができるのは、
$$
|d|<2^m<N^{1/e^2} (∵2^{\lfloor n/e^2 \rfloor}<2^{n/e^2})
$$
となります。
$e=3, n=1024$の場合でも$|d|<2^{113}$なので、$e$が非常に小さい場合でのみでしか効果を発揮できない方法になります。
スクリプト
以降、攻撃スクリプトを示します。SageMath version 9.0を使用しました。
from Crypto.Util.number import *
from random import getrandbits
class RSA:
def __init__(self, bits):
assert bits % 2 == 0
self.gen_new_key(bits)
def gen_new_key(self, bits):
self.p = getPrime(bits // 2)
self.q = getPrime(bits // 2)
self.N = self.p * self.q
self.e = 3
phi = (self.p - 1) * (self.q - 1)
self.d = inverse(self.e, phi)
def encryption(self, m):
c = pow(m, self.e, self.N)
return c
def pgcd(self, f, g):
while g:
f, g = g, f % g
return f
def shortpadAttack(self, c1, c2):
PR.<x, y> = PolynomialRing(Zmod(self.N))
PRS.<xs> = PolynomialRing(Zmod(self.N))
g1 = x^self.e - c1
g2 = (x + y)^self.e - c2
gg1 = g1.change_ring(PRS)
gg2 = g2.change_ring(PRS)
h = gg2.resultant(gg1) # 終結式の計算
h = h.univariate_polynomial().subs(y=xs).monic()
delta_ans = h.small_roots(epsilon=1/60) # なんとなく1/60
if len(delta_ans):
if 2**delta_bits + 1 < delta_ans[0]: # 負の値の場合それを環から戻す
print("Diff :", int(delta_ans[0]) - self.N)
else:
print("Diff :", delta_ans[0])
else:
return "Diff not found..."
# Franklin-Reiter Related Message Attack
PR.<x> = PolynomialRing(Zmod(self.N)) # yを消したので多項式環をまた用意
g1 = x^self.e - int(c1)
g2 = (x + int(delta_ans[0]))^self.e - int(c2)
ph = self.pgcd(g1, g2)
ph = ph.monic()
return int(-ph[0])
bits = 1024
e = 3
r = RSA(bits)
delta_bits = floor(bits / (e^2) / 2)
r1 = ZZ.random_element(2^delta_bits)
r2 = ZZ.random_element(2^delta_bits)
delta = r2 - r1
print("Diff 1 :", delta)
M = bytes_to_long(b"Coppersmiths_shortpad_attack!!!!!!!!!!!!!!!!!!!")
m1 = 2**delta_bits*M + r1
m2 = 2**delta_bits*M + r2
c1 = r.encryption(m1)
c2 = r.encryption(m2)
print("-*-*-*-*-*-*-*-*-*-*-*-")
print(long_to_bytes(r.shortpadAttack(c1, c2) >> delta_bits))
Stereotyped message attack
概要
平文の一部が既知のとき、未知の部分に対してCopperSmith's Methodを適用することができます。
攻撃
暗号文と既知部分をそれぞれ$C, B$とすると、
$$
f(x)=(B+x_0)^e - C \mod N
$$
で、$f(x)$は展開すると、
f(x)=x^e +
\begin{pmatrix}
e \\
1
\end{pmatrix}
Bx^{e-1}+ \dots +
\begin{pmatrix}
e \\
e-1
\end{pmatrix}
B^{e-1}+B^e-C \mod N
のようなモニック多項式になるので、$f(x_0)≡0 \mod N$を満たすような$x_0$を効率よく求めることができます。
条件
展開したとき$e$のモニック多項式になるので、
$$
|x_0| ≤ N^{1/e}
$$
という条件のもとで成り立つ攻撃となります。
スクリプト
以降、攻撃スクリプトを示します。SageMath version 9.0を使用しました。
from Crypto.Util.number import *
class RSA:
def __init__(self, bits):
assert bits % 2 == 0
self.gen_new_key(bits)
def gen_new_key(self, bits):
self.p = getPrime(bits // 2)
self.q = getPrime(bits // 2)
self.N = self.p * self.q
self.e = 3
phi = (self.p - 1) * (self.q - 1)
self.d = inverse(self.e, phi)
def encryption(self, m):
if isinstance(m, str):
m = bytes_to_long(m.encode("utf-8"))
if isinstance(m, bytes):
m = bytes_to_long(m)
c = pow(m, self.e, self.N)
return c
def decryption(self, c):
m = pow(c, self.d, self.N)
m = long_to_bytes(m)
return m
def stereotyped_message_attack(self, prefix, c):
PR.<x> = PolynomialRing(Zmod(self.N))
f = (prefix + x)^self.e - c
diff = f.small_roots()
if len(diff):
return long_to_bytes(int(diff[0]))
else:
return "not found..."
m = b"stereotyped_message_attack!!!"
prefix = b"Hello..."
m = bytes_to_long(m)
prefix = bytes_to_long(prefix) << (m.bit_length() + 1)
m += prefix
r = RSA(2048)
print(long_to_bytes(m))
cipher = r.encryption(m)
plane = r.decryption(cipher)
print("-*-*-*-*-*-*-*-*-*-*-")
print(r.stereotyped_message_attack(prefix, cipher))
print("-*-*-*-*-*-*-*-*-*-*-")
感想&今後について
- 感想
- 格子については多少の理解をしているつもりでしたが、原論文から追って基底の過程を見るのは初めてだったので新鮮で面白かったです。
- CopperSmith's Methodの方程式たてて、それを解くというメソッド1つ呼ぶだけの操作を深追いしてみて、ほんとにいろいろ応用ができそうなものだなと感じました。
- 今回勉強する上で参考にした資料がほぼすべて英語で、多少英語のサーベイを読んだ経験はあったものの、論文初めから全部読むみたいなことは初めてでした。とても楽しかったです。
- 今後について
- セキュリティキャンプでの2か月でいろいろやりたいことができたので忘れないうちに書いておきます。
- CopperSmith's Method以外の格子を用いる攻撃の実装
- 英語での情報収集の継続
- 頑張ります。
- セキュリティキャンプでの2か月でいろいろやりたいことができたので忘れないうちに書いておきます。
参考文献
たいへんお世話になった方々。
- Twenty Years of Attacks on the RSA Cryptosystem, Dan Boneh
http://www.ams.org/notices/199902/boneh.pdf - A Tutorial paper on Hastad Broadcast Attack, Abhay Chennagiri
http://koclab.cs.ucsb.edu/teaching/cren/project/2017/chennagiri.pdf - katagaitai workshop 2018 winterのスライド, Shiho Midorikawa
http://elliptic-shiho.github.io/slide/katagaitai_winter_2018.pdf - Finding a Small Root of a Univariate Modular Equation, Don Coppersmith
https://link.springer.com/content/pdf/10.1007/3-540-68339-9_14.pdf - New RSA Vulnerabilities Using Lattice Reduction Methods, Alexander May
https://www.math.uni-frankfurt.de/~dmst/teaching/WS2015/Vorlesung/Alex.May.pdf