LSB Leak Attackを実装した

,

解説

LSB Leak Attackとは、RSA暗号に対する次のような攻撃: 公開鍵$(e, n)$と任意の値に対する復号結果の偶奇を与える神託$f(x) = \mathrm{dec}(x) \bmod 2 = (x^d \bmod n) \bmod 2$が与えられているとき、任意の暗号文$c = \mathrm{enc}(m) = m^e \bmod n$から平文$m$を復号できる。二分探索を利用する。

まず$f( c) = m \bmod 2$である。 また、整数$k$に対し$\mathrm{enc}(km) = (km)^e \bmod n$は$k^ec \bmod n$として計算できる。 特に$k = 2$の時のため、$b = 2^e \bmod n$としておく。 $f(b^ic) = (2^im \bmod n) \bmod 2$である。

まず$i = 1$のとき。$f(bc) = (2m \bmod n) \bmod 2$。 $2m$は常に偶数、$n$は常に奇数、$0 \le m \lt n$より$0 \le m \lt 2n-2$なので、以下が言える。

  • $2m \bmod n$の偶奇$f(bc) = 1$の場合: $2m \bmod n = 2m - n$
  • $2m \bmod n$の偶奇$f(bc) = 0$の場合: $2m \bmod n = 2m$

これは$f(bc) = 1 \iff 2m \ge n$を意味する。 切り捨て誤差が出るので、有理数の不等式$\frac{n}{2} \le m$の形で持つ。

次に$i = 2$のとき。$f(b^2c) = (4m \bmod n) \bmod 2$。 同様に、

  • 先程$f(bc) = 1$であった場合:
    • $4m \bmod n$の偶奇$f(b^2c) = 1$の場合: $4m \bmod n = 2(2m \bmod n) \bmod n = (4m - 2n) \bmod n = (4m - 2n) - n = 4m - 3n$
    • $4m \bmod n$の偶奇$f(b^2c) = 0$の場合: $4m \bmod n = 2(2m \bmod n) \bmod n = (4m - 2n) \bmod n = (4m - 2n) = 4m - 2n$
  • 先程$f(bc) = 0$であった場合:
    • $4m \bmod n$の偶奇$f(b^2c) = 1$の場合: $4m \bmod n = 4m - n$
    • $4m \bmod n$の偶奇$f(b^2c) = 0$の場合: $4m \bmod n = 4m$

例えば $f(bc) = 1 \land f(b^2c) = 0 \iff 2n \le 4m \lt 3n$となる。 つまり$m \in [\frac{1}{2}n, \frac{3}{4}n)$。

このように繰り返していけば区間$[l, r)$が十分に縮まり$m \in [l, r)$を満たす$m$が唯一になる。そのような$m$として平文$m$が得られる。

implementation

実装の注意としては、誤差を防ぐため区間の端点を有理数で持つこと。 整数で処理すると少しずれる。 またCPython組込みのpowは少し遅いのでgmpy2.powmodを使うと速くなる。

# Python Version: 3.x
from fractions import Fraction
from math import ceil
from gmpy2 import powmod as pow  # fast

def attack(e, n, c, oracle):
    l, r = 0, n  # [l, r)
    i = 1
    while r - l >= 1:
        m = Fraction(l + r, 2)
        if oracle(pow(2, i * e, n) * c % n):
            l = m
        else:
            r = m
        i += 1
    return ceil(l)
# unittest
import Crypto.Util.number
import gmpy2
import random
e = 65537
p = Crypto.Util.number.getPrime(1024)
q = Crypto.Util.number.getPrime(1024)
n = p * q
d = int(gmpy2.invert(e, (p-1)*(q-1)))
m = random.randint(0, n-1)
c = pow(m, e, n)
oracle = lambda x: pow(x, d, n) % 2
assert attack(e, n, c, oracle) == m

参考資料