1001001

73。CTFのWrite-upや技術的な備忘録を書きとめたいです。

CODEBLUE CTF 2017 Paillier Oracle Writeup

CODEBLUE CTF 2017に参加いたしました。Paillier Oracleという問題だけ解いたのでそのWriteupです。

問題概要

Paillier 暗号のLSB Oracleがサーバで動いている。LSB Oracleというのは、何らかの暗号文をサーバ側に与えた時、復号結果の最下位ビット(偶奇)を返すオラクルのこと。Paillier 暗号が加法準同型暗号であることを知っていればLSB Oracle Attackで解けることは自明。

Paillier 暗号

Paillier暗号について簡単に示す。

鍵生成

 p, q : 素数
 n = p*q
 g = 1+kn\ (mod \ n^2)
 公開鍵: (n, g)
 秘密鍵: (p, q)

以下、復号時に使用する値

 \lambda = lcm(p-1, q-1)
 \mu = L(g^\lambda \ mod \ n^2) \ (mod \ n)
ただし、 L(u)=\frac{u-1}{n}

暗号化

 c \equiv g^mr^n\ (mod \ n^2) (rは乱数)

復号

 m \equiv L(c^\lambda \ mod\ n^2)\mu^-1 \ (mod \ n)

Paillier 暗号の準同型性

加法における準同型性を持つ。

 c_1 \equiv g^{m_1}r_1^n\ (mod \ n^2)
 c_2 \equiv g^{m_2}r_2^n\ (mod \ n^2)
 c_1c_2 \equiv g^{m_1+m_2}(r_1r_2)^n\ (mod \ n^2)

LSB Oracle Attack (LSB: Least Significant Bit)

平文 mに対し、 2m, 2^2m, 2^3m... (mod \ n)における偶奇を調べることで、mの範囲を絞り込むことができる。

 LB = 0, UB = n とし、
 2^kmが偶数 (LSB=0) の時、 UB = \frac{LB+UB}{2}
 2^kmが偶数 (LSB=1) の時、 LB = \frac{LB+UB}{2}

これをnのビット数分程度繰り返すことで 平文mを一意に特定することが可能。
( (mod \ n)でなければ 2^kmは全て偶数になるはずだが、 nを法としているため 2^km nを超えることで偶奇が変化する。)

解法

今回、フラグの暗号文(cとする)が得られている。Paillier 暗号の準同型性から、以下のように  2m, 2^2m, 2^3m... の暗号文を得ることが可能。

 c^2 \equiv g^{2m}(r^2)^n\ (mod \ n^2)
 c^4 \equiv g^{2^2m}(r^4)^n\ (mod \ n^2)
 c^8 \equiv g^{2^3m}(r^8)^n\ (mod \ n^2)

ここで、rの累乗も変化していることに気づくが、復号の際にrの値は関わらないため、期待通りLSB Oracle Attackが可能である。

ソースコード

以下に本問題のソルバを記載する。なお、LSB Oracle Attackの際、単純に2.0で除算を行うとlong -> floatでエラーが出たり、LSB Oracle Attackの結果が変わってしまう場合がある。今回は本記事の末尾のリファレンスのサイトを参考に有理数演算を行っている。


gist0ff38748cdc07747857b4688ea5f1f6a


りふぁれんす

inaz2.hatenablog.com