まえおき

LSB Oracle Attackについての記事です。この記事は証明ではなく、この攻撃が成立する性質についての理論解説になります。

2分探索によって元の暗号文が得られるのですが、なぜ2分探索を利用することができるのかということの解説ではなく、2分探索で攻撃成功するのはなぜかということの解説になります。

簡単に言うと、ある条件のときにこんな面白い性質(LSB Decryption Oracle Attack)があるけれど、なぜこの性質があるのかという説明になります。

この記事ではRSA暗号の平文をm, 暗号文をc,公開鍵はnとe,秘密鍵はd,p,qとして説明をします

前提知識

RSAの暗号の前提と剰余算に関しての前提となる式を書いておく。

以下の式はLSB Decryption Oracle Attackを導出するのに利用するので、式の展開でなぜこうなるのかの説明がなければこの式を使っている

RSA暗号の前提

暗号化： $c=m^{e}\ mod\ n$

暗号化関数： $enc(m)=m^{e}\ mod\ n$

復号： $m=c^{d}\ mod\ n$

復号関数： $dec(c)=c^{d}\ mod\ n$

このように暗号化・復号しているので以下の等式も成り立つ

$c=(c^{d})^{e}\ mod\ n$

剰余算で使える式

等式： $(a\ mod\ n)\ mod\ n\ =\ a\ mod\ n$

分配則: $ab\ mod\ n\ = (\ (a\ mod\ n)(b\ mod\ n)\ )\ mod\ n$

LSB Oracle Attack(LSB Leak Attack)の概要

LSB Oracle Attackとは任意の暗号文を復号した結果の最下位1bitが分かるときに平文を求めることができるという攻撃手法である。

かみ砕くと任意の暗号文の偶奇が分かるとき、ある暗号文の平文を求めることが可能となる攻撃手法である。

LSB Decryption Oracle Attackの条件

この攻撃を行うにはいくつかの条件が必要である

暗号文c, 公開鍵n, e, そして $f(x)=dec(x)\ mod\ 2$ となる関数fを攻撃者は持っている必要がある。

またこの攻撃ではcを復号した結果のmはわかるが、秘密鍵d,p,qを知ることはできない

LSB Decryption Oracle Attackの理論

まずenc(km)について考える。

$enc(km)\ =\ (km)^{e}\ mod\ n\ =\ k^{e}m^{e}\ mod\ n\ =\ k^{e}c\ mod\ n$ が成り立つ

▶細かい説明

次にk=2の時を考える.k=2の時の関数fを考えることで2分探索が成り立つことがわかる。実際には $2^{i}$ についてのfを計算することでmの範囲が狭まり，2分探索によって平文を求めることが可能となる

$a=2^{e}\ mod\ n$ とすると $f(a^{i}c)=(2^{i}m\ mod\ n)\ mod\ 2$

▶細かい説明

さてここでRSA暗号の性質から以下の2式が成り立つ

$0 \leq m \lt n$
$0 \leq m \lt 2(n-1)\ \ (n \gt 2)$

第一式は大前提です。RSAの平文はnより小さいです． nは大きい素数であるのでn > 2が成り立ちます。またとするとn < 2(n-1)なので第二式が成り立ちます。

ここからi=1,2,3...と増やしていくことでmの範囲を狭めていく。

`i=1`の時

$f(ac)=(2m\ mod\ n)\ mod\ 2$

である．ここで2mが偶数であり，nが奇数であり，2m<2nであることから2mをnで割った商は1か0であることがわかる．

上記より，

f(ac)=1のときは $2m\ mod\ n\ ⇒\ 2m \gt \ n$ が成り立つ．つまり $\frac{n}{2} \ \lt \ m\ \lt n$ であり $2m\ mod\ n=2m-n$

f(ac)=0のときは $2m\ mod\ n\ ⇒\ 2m\ \leq \ n$ が成り立つ．つまり $0 \ \leq \ m \leq \frac{n}{2}$ であり $2m\ mod\ n=2m$

`i=2`の時

$f(a^{i}c)=(2^{2}m\ mod\ n)\ mod\ 2$ つまり $f(ac)=(2(2m\ mod\ n)\ mod\ n)\ mod\ 2$

ここではi=1の時のf(ac)の結果を用いる

$f(ac)=1かつf(a^{2}c)=1$ のとき

\begin{align} f(a^{2}c)\ &=\ (2(2m\ mod\ n)\ mod\ n) \\ &=\ (2(2m-n)\ mod\ n) \\ &=\ (4m-2n-n) \\ &=\ 4m-3n \\ \end{align}

2m-nはnより小さい，それにより2(2m-n) < 2nである．つまり2(2m-n)をnで割った商も1か0にしかならなく，かつ2(2m-n)は偶数，nは奇数なため， $f(a^{2}c)=1$ ならば上の式が成り立つ．これにより $4m\ \gt \ 3n⇒ m \gt \frac{3}{4}n$ が導き出され $f(ac)=1$ を考えると $\frac{3}{4}n \lt m \lt n$ となる

このようにして残りの条件も書き出す

$f(ac)=1かつf(a^{2}c)=0$ のとき

\begin{align} f(a^{2}c)\ &=\ (2(2m\ mod\ n)\ mod\ n) \\ &=\ (2(2m-n)\ mod\ n) \\ &=\ (4m-2n) mod\ n\\ &=\ 4m-2n \\ \end{align}

この結果より $\frac{1}{2}n \lt m \leq \frac{3}{4}n$

$f(ac)=0かつf(a^{2}c)=1$ のとき

$f(a^{2}c)\ =\ 4m\ mod\ n=\ 4m-n$ より $\frac{1}{4}n \lt m \leq \frac{1}{2}n$

$f(ac)=0かつf(a^{2}c)=0$ のとき

$f(a^{2}c)\ =\ 4m\ mod\ n=\ 4m$ より $0 \leq m \leq \frac{1}{4}n$

となる

i=2以降

これ以降は同様の計算を行っていくことによりmの範囲が狭まり元の平文を求めることができる．

実際の問題(Sharif CTF LSB_Oracle)

理論が分かったところで実際の問題を解いてみる。今回はSharif CTF 2016の問題を解く。

与えられるのはexeの入った実行ファイルとpythonのファイル、実行ファイルはリンクを、pythonは直接示しておく

https://github.com/ctfs/write-ups-2016/tree/master/sharif-ctf-2016/crypto/lsb-oracle-150

#! /usr/bin/env python3
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
n = -1  # get it from the provided EXE file
e = -1  # get it from the provided EXE file
flag = b'' # redacted
key = RSA.construct((n, e))
cipher = PKCS1_v1_5.new(key)
ctxt = bytes_to_long(cipher.encrypt(flag))
print(ctxt)
# output is:
# 2201077887205099886799419505257984908140690335465327695978150425602737431754769971309809434546937184700758848191008699273369652758836177602723960420562062515168299835193154932988833308912059796574355781073624762083196012981428684386588839182461902362533633141657081892129830969230482783192049720588548332813

exeを動かすと、nとeは教えてくれます。また悪い罠にかかって下位1bitしか返せないと教えてくれます。またpythonの中に暗号文はあるので、典型的なlsb_oracleです。

理論はすでに説明したので残りはコードだけ

# -*- coding:utf-8 -*-
# solver.py sharif-ctf lsb-oracle

from fractions import Fraction
from subprocess import Popen,PIPE
from math import ceil
from binascii import unhexlify

n = 120357855677795403326899325832599223460081551820351966764960386843755808156627131345464795713923271678835256422889567749230248389850643801263972231981347496433824450373318688699355320061986161918732508402417281836789242987168090513784426195519707785324458125521673657185406738054328228404365636320530340758959
e = 65537

def long_to_bytes (val, endianness='big'):
    width = val.bit_length()
    width += 8 - ((width % 8) or 8)
    fmt = '%%0%dx' % (width // 4)
    s = unhexlify(fmt % val)

    if endianness == 'little':
        s = s[::-1]

    return s

def get_oracle(c):
    p = Popen(['lsb_oracle.vmp.exe','/decrypt'], stdin=PIPE, stdout=PIPE,stderr=PIPE,encoding='utf8')
    #print("sent ciphertext\n"+ str(cc))
    result = p.communicate(str(c)+"\n-1")
    lsb = int(result[0][96])
    #print(lsb)
    return lsb

def generate_ciphertext(p):
    return pow(p,e,n)

def solver():
    decision = [0,Fraction(n)]
    i = 0
    c = 2201077887205099886799419505257984908140690335465327695978150425602737431754769971309809434546937184700758848191008699273369652758836177602723960420562062515168299835193154932988833308912059796574355781073624762083196012981428684386588839182461902362533633141657081892129830969230482783192049720588548332813
    #c = generate_ciphertext(m)
    while decision[1] - decision[0] >= 1:
        i += 1
        print(i)
        cc = (c * pow(2,e,n)) % n
        oracle = get_oracle(cc)
        if oracle == 1:
            decision[0] = Fraction(sum(decision)/2)
        else:
            decision[1] = Fraction(sum(decision)/2)
        c = cc
    return ceil(decision[0])
        


if __name__ == '__main__':
    ans = solver()
    print(long_to_bytes(ans))

このコードを実行すると

> python solver.py
1
2
(snip)
1024
b'\x02\xa9\x12\xa7uA\x94\x8e\x8c2\xd5(\xda\x1eq?\xf7\xd0TL\xe8\xde1$\xbf\xe4w\xe1\x18\x12\x1f\xef\x03\x8b{\x7f\xb2\x9c\xa6Bs\xd2\xfe&\xe8+k7\xd8\xe7\xa5\x0b\xaf\xa8R\x12\x93\x0e,\xdfp\xff\x9a\xe7\x9b\xbduN4\x85I\xde3\x07\xb2n\xa4\xdb"\xd5\xfaf\x84\x00
SharifCTF{65d7551577a6a613c99c2b4023039b0a}'

という感じでflagを入手することが可能である。