CODEBLUE CTF 2017に参加いたしました。Paillier Oracleという問題だけ解いたのでそのWriteupです。
問題概要
Paillier 暗号のLSB Oracleがサーバで動いている。LSB Oracleというのは、何らかの暗号文をサーバ側に与えた時、復号結果の最下位ビット(偶奇)を返すオラクルのこと。Paillier 暗号が加法準同型暗号であることを知っていればLSB Oracle Attackで解けることは自明。
Paillier 暗号
Paillier暗号について簡単に示す。
鍵生成
以下、復号時に使用する値
ただし、
暗号化
復号
Paillier 暗号の準同型性
加法における準同型性を持つ。
LSB Oracle Attack (LSB: Least Significant Bit)
平文に対し、 の における偶奇を調べることで、mの範囲を絞り込むことができる。
とし、
が偶数 () の時、
が偶数 () の時、
これをnのビット数分程度繰り返すことでを一意に特定することが可能。
(でなければは全て偶数になるはずだが、を法としているためがを超えることで偶奇が変化する。)
解法
今回、フラグの暗号文(cとする)が得られている。Paillier 暗号の準同型性から、以下のように の暗号文を得ることが可能。
ここで、rの累乗も変化していることに気づくが、復号の際にrの値は関わらないため、期待通りLSB Oracle Attackが可能である。
ソースコード
以下に本問題のソルバを記載する。なお、LSB Oracle Attackの際、単純に2.0で除算を行うとlong -> floatでエラーが出たり、LSB Oracle Attackの結果が変わってしまう場合がある。今回は本記事の末尾のリファレンスのサイトを参考に有理数演算を行っている。
gist0ff38748cdc07747857b4688ea5f1f6a