2018-07-04

LSB Decryption Oracle Attack

Crypto

まえおき

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を入手することが可能である。

おわりに

計算ミスや表記ミスがあったら教えてください

参考

LSB Leak Attackを実装した

plain RSAに対するLSB decryption oracle attackをやってみる - ももいろテクノロジー

2018-05-30

WindowsのPythonでMySQL80を触ろうとしたら躓いた話

Win MySQL80

本題

MySQLが8.0になった際、認証周りで変更があったため、Pythonから触ろうとしたらいろいろ躓いたのでそれらをまとめた。

なお環境は下記のとおりである。

OS:Windows 10
Mysql 8.0
Driver: mysql-connector-python-rf

発生したエラー

Traceback (most recent call last):
  File "****.py", line 46, in <module>
    charset = 'utf8')
  File "C:\Users\***\Local\Programs\Python\Python35\lib\site-packages\mysql\connector\__init__.py", line 179, in connect
    return MySQLConnection(*args, **kwargs)
  File "C:\Users\***\Local\Programs\Python\Python35\lib\site-packages\mysql\connector\connection.py", line 95, in __init__
    self.connect(**kwargs)
  File "C:\Users\***\Local\Programs\Python\Python35\lib\site-packages\mysql\connector\abstracts.py", line 716, in connect
    self._open_connection()
  File "C:\Users\***\Local\Programs\Python\Python35\lib\site-packages\mysql\connector\connection.py", line 210, in _open_connection
    self._ssl)
  File "C:\Users\***\Local\Programs\Python\Python35\lib\site-packages\mysql\connector\connection.py", line 142, in _do_auth
    auth_plugin=self._auth_plugin)
  File "C:\Users\***\Local\Programs\Python\Python35\lib\site-packages\mysql\connector\protocol.py", line 102, in make_auth
    auth_data, ssl_enabled)
  File "C:\Users\***\Local\Programs\Python\Python35\lib\site-packages\mysql\connector\protocol.py", line 58, in _auth_response
    auth = get_auth_plugin(auth_plugin)(
  File "C:\Users\***\Local\Programs\Python\Python35\lib\site-packages\mysql\connector\authentication.py", line 191, in get_auth_plugin
    "Authentication plugin '{0}' is not supported".format(plugin_name))
mysql.connector.errors.NotSupportedError: Authentication plugin 'caching_sha2_password' is not supported

発生した理由はMySQL8.0で追加されたchaching_sha2_password機能のせい

簡単な理由説明

MySQL8.0になってからユーザ認証方式として従来のmysql_native_passwordとは別にcaching_sha2_passwordが追加された。しかしプログラミング言語からMySQLにつなぐためのドライバの多くがcaching_sha2_passwordに対応していないために認証時にエラーが発生する。

やること

検索すると下記二つのどちらかでいいという記事が出てくるが、私は両方やらないと解決しなかった。

MySQLの特定のユーザの認証方式を変える。
MySQLのパスワードの認証方式を変える。

MySQLの特定のユーザの認証方式を変える。

MySQLにrootでログインし、変更したいユーザのパスワードを変更する。usernameとpasswordは各々の設定したいユーザ名と認証するときに利用するパスワードを入れてください。

mysql> alter user 'username'@'localhost' identified WITH mysql_native_password by 'password';

設定が反映されたことの確認

mysqlのプロンプトからSELECT user, host, plugin FROM mysql.user;と打ち込んでください。

設定したユーザのpluginがmysql_native_passwordになっていればよいようです。

この段階でうまくいく人もいるらしいです。わたしはうまくいかなかったのでmysql自体の設定をいじりに行きます。

mysql> SELECT user, host, plugin FROM mysql.user;
+------------------+-----------+-----------------------+
| user             | host      | plugin                |
+------------------+-----------+-----------------------+
| ******           | localhost | caching_sha2_password |
| mysql.infoschema | localhost | mysql_native_password |
| mysql.session    | localhost | mysql_native_password |
| mysql.sys        | localhost | mysql_native_password |
| root             | localhost | caching_sha2_password |
| ****             | localhost | mysql_native_password |
+------------------+-----------+-----------------------+

MySQLの認証方式を変える

MySQLの設定ファイルであるmy.iniを変更しに行きます。

my.iniはC:\Program Data\MySQL\MySQL Server 8.0\にあります。

このProgram Dataというディレクトリは通常隠しファイル扱いになるのでエクスプローラの表示から隠しファイルのチェックボックスを入れてください。

f:id:kataware8136:20180530213537p:plain

my.iniの変更ですが、default_authentication_plugin=mysql_native_passwordとしてください。

[mysqld]

---(snip)

#default_authentication_plugin=caching_sha2_password
default_authentication_plugin= mysql_native_password

設定ファイルを変更したらMySQLのデーモンを再起動します

コマンドプロンプトから再起動

管理者用のコマンドプロンプトで実行してください

> net stop MySQL80
> net start MySQL80

サービス管理画面から再起動

win + rかここに入力して検索のところでservices.mscと打ち込むとサービス管理画面を起動できます。

ここからMySQLのサービスを選んで右クリック、再起動してください。

設定が反映されたことの確認

mysqlのプロンプトからshow variables like 'default_authentication_plugin';を打ち込み、valueがmysql_native_passwordとなっていれば大丈夫です。

mysql> show variables like 'default_authentication_plugin';
+-------------------------------+-----------------------+
| Variable_name                 | Value                 |
+-------------------------------+-----------------------+
| default_authentication_plugin | mysql_native_password |
+-------------------------------+-----------------------+

さいごに

pythonのドライバだけではなくphpのドライバでも同様の問題は起こっているみたいです。直にドライバも対応していくでしょうし、ドライバのほうがcaching_sha2_passwordに対応したら今回の設定内容を直すのが無難です。

というのもmysql_native_passwordよりも安全な認証方式になっているようです。なので今回の方法は一時しのぎといった感じでしょうが役に立てば幸いです。

参考文献

MySQL8.0新機能 (caching_sha2_password 認証プラグイン)

caching_sha2_passwordをサポートされているコネクタ一覧

2018-05-01

コンボリューションを考える

数学ガールの第7章、コンボリューションを読んでるだけでは理解できなかったので手を動かしてみることにした

母関数の積までは読んでて理解できたので図書室からスタート

前提の問題

$\displaystyle$

\begin{align} 0 + 1 + 2 &= (0 + (1 + 2) ) \\ &= ((0 + 1) + 2) \\ \end{align} 2なら2通り ( $C_2 = 2$ ) \begin{align} 0 + 1 + 2+ 3 + ... + n &= ? \\ \end{align} nなら何通りか( $C_n = ?$ )

だいたいこんな感じ、正直詳しく知りたい人は本買おう

ミルカさんの解

私が理解したところ

$C_n =(SからGまでの経路数) - (SからG'までの経路数)$

やること

下降階乗冪をフル回転

下降階乗冪をフル回転

\begin{align} \begin{split} C_n &= \begin{pmatrix} 2n \\ n \end{pmatrix} - \begin{pmatrix} 2n \\ n+1 \end{pmatrix} \\ &= \frac{(2n-0)(2n-1)(2n-2)...\bigl(2n - (n-1) \bigr) }{(n-0)(n-1)(n-2)...\bigl(n-(n-1) \bigr)} - \\ &\quad \frac{(2n-0)(2n-1)(2n-2)...\bigl(2n-(n+1-1)\bigr)}{(n+1-0)(n+1-1)(n+1-2)...\bigl(n+1-(n+1 -1)\bigr)} \\ &= \frac{(2n)^\underline{n}}{(n)^\underline{n}} - \frac{(2n)^\underline{n+1}}{(n+1)^\underline{n+1}} \end{split} \end{align}

でこの後通分を行う。書籍にはない2番目の式を見ると

分子は \begin{align} &\quad(2n-0)(2n-1)(2n-2)...\bigl(2n-(n+1-1)\bigr) \\ &=(2n-0)(2n-1)(2n-2)...\bigl(2n-(n-1)\bigr)(n) \\ &= (2n)^\underline{n}・n \end{align}

分母は \begin{align} &\quad(n+1-0)(n+1-1)(n+1-2)...\bigl(n+1-(n+1 -1)\bigr) \\ &=(n+1)・(n-0)・(n-1)・...・3・2・1 \\ &= (n+1)・(n)^\underline{n} \end{align}

ということで最終的な式は以下のようになる

\begin{align} \frac{(n+1)・(2n)^\underline{n}}{(n+1)・(n)^\underline{n}} -\frac{(2n)^\underline{n}・(n)}{(n+1)・(n)^\underline{n}} \end{align}

後は計算をするだけだった。要は私は下降階乗冪がよくわかってなかったため理解できなかった。

結論は

\begin{align} C_n = \frac{1}{n+1} \begin{pmatrix} 2n \\ n \end{pmatrix} \end{align}

母関数へ旅をする

読んでて理解したのは母関数の閉じた式を入手したところ、そこから先を「僕」と同じように手を動かして進める。

まずは母関数の式

\begin{align} C(x) = \frac{1 \pm \sqrt{1-4x}}{2x} \end{align}

C(0)を考えると $C_+(x)$ は不適であることになる。そのため下の式を考える \begin{align} C(x) = \frac{1 - \sqrt{1-4x}}{2x} \end{align}

$\sqrt{1-4x}$ が邪魔なのでこれを冪級数 [tex:\sum_{k=0}^∞ K_k x^k]を利用する

で、ここまで来て何なのだが、texで書くの疲れたのでこっからは写真.....、メモに見えてる某企業は何も関係ありません。たまたま近くにあったメモだったので使いました。

f:id:kataware8136:20180501151810j:plain

f:id:kataware8136:20180501152450j:plain

母関数の国から数列の国へと帰ってきました。

感想

手を動かしてみると、読んでる時わからなかったのが理解できるようになったので、もし読んでるだけでわかりにくかったら手を動かすといいと思います。

無限級数の時の和の順序の変更には条件をきちんと述べる必要があるらしいのでそこらへんを調べにいってきます。

まえおき

前提知識

RSA暗号の前提

剰余算で使える式

LSB Oracle Attack(LSB Leak Attack)の概要

LSB Decryption Oracle Attackの条件

LSB Decryption Oracle Attackの理論

i=1の時

i=2の時

i=2以降

実際の問題(Sharif CTF LSB_Oracle)

おわりに

参考

本題

発生したエラー

簡単な理由説明

やること

MySQLの特定のユーザの認証方式を変える。

設定が反映されたことの確認

MySQLの認証方式を変える

コマンドプロンプトから再起動

サービス管理画面から再起動

設定が反映されたことの確認

さいごに

参考文献

前提の問題

ミルカさんの解

下降階乗冪をフル回転

母関数へ旅をする

感想

`i=1`の時

`i=2`の時