RSA暗号システムに対するタイミング攻撃の情報理論的安全性評価
小林 靖幸 (1351042)
暗号システムに対するタイミング攻撃は，サイドチャネル攻撃の一種であり，攻撃者がシステムの実行時間を観測し分析することで，内部で使用されている鍵の情報を推測する攻撃手法である．タイミング攻撃は比較的容易に実行可能であるため，どのようなシステムであっても，タイミング攻撃の脅威に晒される恐れがある．
処理時間と機密情報の関係性
について世界中の機関において検討をしているが，暗号システムが利用される環境は多種多様である
ため，ある環境での関係性を実験ベースで示したとしても，その結果を汎用的な評価に昇華させるこ
とは難しい．
タイミング攻撃に対するシステムの耐性を定量的に評価するため，情報理論的手法を活用することが検討されている．情報理論的な見地からは，暗号システムを，未知の鍵を入力とし実行時間を出力とする通信路であると解釈することができる．通信路の出力(実行時間)から入力(鍵)を推測する行為がタイミング攻撃に相当するが，攻撃者が得ることのできる情報量は，通信路入出力間の相互情報量を超えることはない．本発表では，暗号システムとしてRSA暗号の復号アルゴリズムを想定し，上記のように定義される通信路の入出力の相互情報量を精密に評価する．具体的には，通信路の出力が多項分布により特徴づけられることを示し，多項分布のエントロピーの近似式を適用することで，漏洩する鍵情報量の上界式を導き出した．この上界式を用いることで，実際のシステムから漏洩するおそれのある情報量について，具体的な値が決定する．
数値評価の結果から，先行研究は漏洩情報量を2倍以上過大に見積もっていることが明らかになった．また，
RSA暗号の2種類の異なった実装方式について，
タイミング攻撃の対策手法であるbucketing法の有無による漏洩情報量の
評価を行い，対策手法を施せば漏洩情報量はほぼ同じになることを示した．
総括として，漏洩情報量より多くの漏洩は，
原理的に不可能であるというきわめて理論的な議論から，実用上の具体的な知見が得られた．