はじめに
完全準同型暗号①〜③では準同型性という便利な性質を使った秘密計算技術を紹介しました。準同型性は暗号化状態で演算をし復号したものが、平文状態で演算を施したものと一致するという性質でした。一見便利な性質ですが、これは脆弱性にもなり得ます。
今回の記事では、乗法準同型性を持つRSA暗号で実際に発見された脆弱性とその対策を紹介します。
RSA暗号
まずはRSA暗号を簡単に紹介します。
鍵生成
素数 $p, q$ に対して $n=pq$、$ed=1\mod{(p-1)(q-1)}$ を満たす整数 $n, e, d$ を作る。$(e,n)$ を公開鍵、$d$ を秘密鍵とする。
暗号化
平文空間は $\mathbb{Z}/n\mathbb{Z}$ とする。平文 $\mu \in \mathbb{Z}/n\mathbb{Z}$ を以下のように暗号化して暗号文 $c$ を作成する。
$$ c=\mu^e\mod{n} $$
復号
暗号文 $c$ から以下の方法で平文 $\mu$ を得る。
$$ \mu = c^d \mod{n} $$
RSA暗号の実装とその問題点
そもそもRSA暗号の規格を定める上で準同型性は問題点とされていました。準同型性を悪用すれば、通信などにRSA暗号を使う際に悪意のある第三者がメッセージを改変することができてしまうからです。
今回はPKCS#1 v1.5で考えられた対策とそこで起こった問題を紹介します。
PKCS#1 v1.5での取り組み
暗号の規格のうちの一つにPKCSがあります。これはRSA社（現在はEMC社の一部門になっています）が定めたもので、その一部は標準化団体によって標準規格として採用されています。PKCSは#1〜#15まであり、#1はRSA暗号の公開鍵と秘密鍵のフォーマットを規定しています。
前述の通り、RSA暗号の規格を定める上で準同型性は問題視されていました。そこでPKCS#1 v1.5では平文 $\mu$ を暗号化する際に以下のようなフォーマットを定めました。
先頭の $00$ は平文が $n$ 未満であること、次の $02$ はRSA暗号を使用していることを意味する固定値です。その次のPSは長さが8bit以上の疑似乱数列です。次の $01$ も固定値です。最後に暗号化したいメッセージ $m$ をくっつけます。これらを一つのブロックとし、このまま暗号化します。
このようなフォーマット定めると、準同型性を悪用しようと演算を施すとフォーマットが崩れてしまいます。そのため準同型性がなくなったわけではありませんが、実装で悪用を防ごうとしました。
Bleichenbacherによる攻撃手法
上記のフォーマットで準同型の悪用を防げたと考えられていましたが、1998年にBleichenbacherがPKCSに対する攻撃を発表しました。これはパディングオラクル攻撃の一つです
パディングオラクル攻撃
パディングオラクルというオラクル（定められた値を教えてくれる神のような存在）を使った攻撃がパディングオラクル攻撃です。パディングオラクルはビット列が正しいフォーマットに従っているかどうかを教えてくれる神様のような存在です。この攻撃は共通鍵暗号のCBCモードへのアタックが有名です。
パディングオラクル攻撃は任意の暗号文に対応する平文が得られるという条件下で成立するので、選択暗号文攻撃の一つです。選択暗号文攻撃については完全準同型暗号②の記事で解説しています。
Bleichenbacherの攻撃ではエラーメッセージを返すサーバがパディングオラクルとして働きます。
次に具体的な攻撃方法を見てみましょう。
攻撃手法
暗号文 $c$ は $c=0020PS01m$ の形になっています。これを単なる数字として考えると、このフォーマット $M$ は以下のような範囲にあることがわかります。
$00 02 00 00\cdots 00$ $< M <$ $00 03 00\cdots00$
つまり平文 $\mu$ は以下の範囲にあると言えます。
$200\cdots 00 < \mu < 300\cdots00$
暗号文はこの範囲内に含まれるという条件下でさらに範囲を絞っていきます。
具体的な攻撃手順は以下のとおりです。ここからは全て $mod {n}$ での計算です。
- 攻撃者は任意の値 S を用いて $c’＝S^e\times c$ という偽造暗号文を作る。
- $c’$ を復号オラクルに送信し復号に成功したかどうかを知る。
- 復号に成功した場合 $c’$ は $(c’)^d$ で復号することができる。これは $(c)^d=(S^e\times c)^d=S^{ed}\times c^d=S\times \mu$ なので $(c)^d/S=\mu$ の範囲がわかる。
- 以上を繰り返す。
手順１で暗号文の掛け算を利用しているため、これは準同型性を悪用した攻撃と言えます。
$c_1, c_2, c_3$ の三つの偽造暗号文で複合が成功したと仮定し、その時の任意の値をそれぞれ $S_1, S_2, S_3$ とします。 これを図示すると以下のようになります。
$c_1,c_2,c_3$ を含めて全ての場合で存在する範囲を絞ると一番下の赤い部分になることがわかります。こうして存在し得る範囲を絞っていくことでどこかのタイミングで平文を見つけることができます。実世界ではSSL/TLSサーバが復号オラクルとしての役目を果たしてしまうことがわかり、この攻撃が実際に起こる可能性がありました。実際にこの攻撃を成功させるためには約100万個の暗号文が必要なため、million message attack とも呼ばれます。
million message attack への対策
この攻撃は約100万個の暗号文が必要なため、現実的ではないと考えられています。これを改良した攻撃方法では実現可能性のあるものも含まれていました。PKCS#1 v1.5 を利用していたTLS1.0では攻撃者が復号できないというエラーを識別できないようにする、という対策を取りました。しかし、エラーを出さないプログラムというのはあり得ないので実行には限界があります。
また、この攻撃は先頭に固定値がついていたために可能になりました。そのため、フォーマットを作る際に固定値を利用しないという対策もあります。PKCS#1の新たなバージョンでは対策としてこちらを採用し、固定値を先頭につけないRSA-OAEPと呼ばれる暗号化方式を使用しました。
参考文献
- Romain Bardon, Riccard Focardi, Yusuke Kawamoto, Lorenzo Simionato, Graham steel, Joe-Kai Tsay, “暗号ハードウェアに対する効率的なパディングオラクル攻撃” SCIS 2013
- 清水祐太郎、藤原祐大、前田優人、米内貴志、渡部祐（2021）『詳解セキュリティコンテスト~CTFで学ぶ脆弱性攻略の技術』マイナビ出版
