1080

Oct. 2008

科学

暗号への脅威「サイドチャネル攻撃」とその対策
﨑 山 一 男・太 田 和 夫 （電気通信大学情報通信工学科，暗号理論・暗号実装）
さきやまかずお

おおたかずお暗号技術 ―― 情報を保護する技術は，現代の情報化社会において不可欠な存在であり，その重要性は増すばかりである．その技術の基盤となっている暗号理論によれば「安全に利用できる」はずの暗号方式が，実装方法によっては「秘密が漏れてしまう」暗号方式となる危険性が報告されている．

今日，ディジタル情報通信技術は大いに発展し，花子が太郎にデートの待ち合わせについてメッセ個人の日常生活にも深く浸透している．情報を保ージを送る場合を考えよう．この待ち合わせの情護する暗号技術が情報化社会の利便性を享受する

報は，他の誰にもばれないようにしたい．しかし，ためのライフラインとして機能している．

通信路上のデータは誰でも取得できることが前提であるため，花子はメッセージの内容が読まれる

暗号理論と暗号実装ことのないように，メッセージを暗号化する．太郎だけが暗号化されたメッセージを復号化するこ

現在のディジタル情報システムにおいて，その営みを支えているのは，システムの心臓であるとができ，デートの待ち合わせ情報を花子と共有することができる．

LSI（large scale integrated circuit）
である．世の中太郎はあらかじめ用意した自分だけが知っていにあるすべてのディジタル情報が LSI で処理される秘密の情報（秘密鍵）を使って復号化を行う．実ている，といっても過言ではない．理論研究によ際には，太郎はディジタル機器を用いて復号化処り生み出された種々の暗号方式もまた LSI に実装

理を行う．秘密鍵は太郎が所有するディジタル機され，情報の保護を担うシステムとして広く普及器に格納されており，誰にも読みだされないようしている．銀行の IC カードがその代表である．

保護されている．秘密鍵が読みだされてしまうと，このように，暗号理論と暗号を安全に実装する技

太郎が復号化を行うときの処理を真似して，花子術（暗号実装）とは不可分な関係にあるといえる．

からの暗号化されたメッセージは復号化され，メ

ところが，1999 年に発表されたある論文が，ッセージの内容が読まれてしまうからである．つ

暗号理論と実装の関係に一石を投じることとなっまり，ディジタル機器に格納されている秘密の情た．理論的には安全な暗号でも，実装の仕方によ報は決して読みだされないということが，暗号理っては情報漏れの危険性があることが示されたの論では前提となっているのである．

である．暗号実装に思わぬ「落とし穴」が発見されたのである．

秘密情報が “脇道” から漏れる？

このことを説明するためには，まず，現代の暗号理論における暗号方式を簡単に説明する必要が次のクイズをご存知だろうか？ 「新しい家にある．暗号理論では有線・無線にかかわらず通信引っ越してきた．2 階には 3 つの白熱球の照明器

路（channel）上の情報の保護を考える．たとえば，があり，それらのスイッチは 1 階にしかない．3

Vol. 78

No. 10

暗号への脅威「サイドチャネル攻撃」とその対策

つの照明器を制御する 3 つのスイッチがあり，今サイドチャネル攻撃の実際:はすべてオフとなっている．どのスイッチがどのRSA 暗号処理 LSI のケーススタディから1081

ライトにつながっているかは不明だが，スイッチと照明器は組になっており，1 つのスイッチで，LSI にはデータを入力・出力するための信号ピ

1 つの照明器しか点灯・消灯できないようになっンが存在する．これらのピンは，本来の情報を伝ている．1 階のスイッチにラベルを貼って，照明達するための経路であり，暗号処理機能実現のた器との対応付けをしたいのだが，できる限り 1 階めに必要な信号のやりとりに使われる．LSI は微と 2 階の往復回数を少なくしたい．さて，1 階と細な電気回路が集積されており，その動作には電2 階を何往復すれば，すべてのスイッチに正しく力供給が必須である．つまり，LSI は機能のためラベルを貼ることができるだろうか？」の入出力ピンに加え，電力供給に必要なピンが存

一般に正解とされているのは，次の手順による在する．この電力供給のための経路がサイドチャ1 往復である．
「どれか 2 つのスイッチをオンにネルとなり，思いもよらぬ情報が漏れる可能性がし，しばらく経った後にオンした 2 つのスイッチある．もう少し詳しく説明しよう．先述のとおり，のうち 1 つをオフにし，2 階に上がる．照明は 1

暗号処理 LSI には通常，秘密鍵が組み込まれておつだけ点いており，その照明がオンとなっている

り，秘密鍵を用いて暗号化・復号化といった処理スイッチとつながっていることがわかる．残りのが実行される．したがって，秘密鍵の値により2 つの照明器のうち，白熱球を手で触り，熱を感LSI での処理は異なり，消費される電力もこの秘じられるほうが，オンからオフに切り換えたスイ密鍵の値により異なるのである．つまり，電力供ッチに対応しており，他方がまったく操作しなか給のためのピンから，処理中の消費電力を測定すったスイッチと対応している」というものである．

ると，秘密鍵が特定できる場合があるのである．

見ているだけでは，白熱球が点灯・消灯という公開鍵暗号で有名な RSA（1）暗号を例として，2 つの状態しかないと思いこんでしまう点にクイ消費電力と秘密鍵の関係を調べてみよう．まず，ズのおもしろさがある．白熱球は点灯時に熱が伴

RSA 暗号の暗号化・復号化の処理は，ある数のう．この当たり前の物理現象がこのクイズのミソ

べき乗を N で割ったときの余りを求めることでとなっているのだ．白熱球を交換する際に熱くて実現されている（剰余系におけるべき乗算）．ここ交換できなかった，という経験があれば，簡単にでは詳細は述べないが，復号化では，暗号文 C答を出すことができるかもしれない．

を秘密鍵である d を用いて C d mod N を計算する

このクイズの場合，発熱という物理現象を利用と，元のメッセージに復号できる．以下簡単のたした．つまり，白熱球の球面から手に熱が伝播す

め，べき乗算，乗算，自乗算はすべて剰余系におることにより，新たな情報が得られたのである．

ける演算を意味するものとする．

この情報の伝達経路（白熱球から手）
は，本来の情RSA 暗号の復号化処理に必要なべき乗算 C d に報の経路（白熱球から眼）とは別の “脇からの情報

おいて，素直に C を d 回乗算するというナイー路” と い う 意 味 で，サ イ ド チ ャ ネ ル（side chan-ブな方法は非現実的である．なぜなら，現在 d にnel）からの情報と呼ぶことができる．

は 1024 ビット以上の値が用いられるため，21024はたして，暗号処理システムにおいてもサイド回の乗算が必要となるからである．1 秒間に 1 兆チャネルは存在するのであろうか？ それはどの回の乗算を行う LSI が存在し，それを使ったとしようなものであるか？ 次に，暗号処理 LSI を例ても復号化処理には約 300 桁の年数を費やす．にあげ，LSI 内部の秘密情報が，サイドチャネル人は長くても 3 桁の寿命であるから，太郎が花子から漏えいする危険性があることを紹介する．のメッセージを復号し，読むことは不可能である．
そこで，乗算の回数を減らすための工夫を行う．

1082

Oct. 2008

科学れるようになった．

秘密鍵情報がビットごとに解読される危険
11001101

消費電力対策はあるのかでは，自乗算による計算の効率化と，サイドチM

S

M

S

S

S

M

S

M

S

S

M

ャネル攻撃への耐性強化を同時に実現させるには時間どうしたらよいだろうか？ 対策法として，大き図 1 ――RSA 復号化処理中の消費電力の時間変化．正確には，LSI と直列接続した抵抗における電圧差を測定し，電力に換算したもの．図中 S，M に対応する電力ピークはそれぞれ，剰余系における自乗算と乗算によるものである．S と M の出現パターンに不規則性が見られ，これにより秘密鍵が特定できる．

くは次の 2 つのアプローチに大別できる．1 つは，簡単な例をあげると，C205

C =C205を計算する際には，

128+64+8+4+12

S と M の出現パターンをランダムにし，鍵との依存性をなくすことを狙うもので，もう 1 つは，鍵の値によらず，常に同じパターンとなるようにすることを目標とする．どちらのアプローチにおいても，これまでに数多くの対策法が提案されて2 2 222 2= ((((((C # C ) ) ) # C ) # C) ) # C

いるが，ここでは，後者について説明する．とする．自乗算をうまく利用することで計算効率

S と M の出現パターンを規則的にするアルゴを大幅に良くすることができるのである．工夫なリ ズ ム と し て Montgomery Powering Ladder 法

しでは 204 回の乗算が必要であるのに対し，自がある（3）．C 205 を計算する際に図 2 に示すように乗算を利用することで 4 回の乗算と 7 回の自乗2 つの変数（2 本の縦のラインに相当）を準備し，算で計算可能なことを示している．通常の 1024

計算を進めていくとちょうど梯子のような形になビットの d の場合でも，およそ 500 回程度の乗る．本アルゴリズムは別の目的で提案されたもの

算と 1000 回程度の自乗算で復号化処理が可能とC 205なる．これならば，太郎は 1 秒もかからずにメッセージを復号することができ，花子とのデートの待ち合わせに遅れることもないであろう．
ここで，自乗算を取り入れた場合の RSA 暗号

C処理中の消費電力変化から，乗算の処理の部分M…，と処理されていることがわかるが，実は，M→S のペアが鍵のビット “1” に対応し，S が “0”に対応している．つまり，電力波形からいとも簡単に秘密情報を読み取ることができるのである．
計算の効率化によって，サイドチャネル攻撃に対する脆弱性が浮き彫りになったともいえる．
この電力解析によるサイドチャネル攻撃（電力解析攻撃）をベースに Kocher はさらに強力な攻撃法を考案し，1999 年に暗号に関する国際会議
CRYPTO において発表した（2）．以後，広く知ら

206

M

SS

M

M

S

M

S

S

M

S

M

M

SM

S

C 103
C 52

C 51

C 26

C 25

C 13

C 12（M）と自乗算（S）の処理の部分は，波形の形状により区別できてしまう．M→S→M→S→S→S→

C

102

処理 LSI を実装し，消費電力の時間変化を測定す
ると，たとえば図 1 のようになる．RSA 復号化

ゴール

C7

C6

C4

C3C2C

1スタート

C

図 2 ――Montgomery Powering Ladder 法．図 は C 205
を Montgomery Powering Ladder 法 で 計 算 し た 場 合（205は 2 進数で 11001101）．一般には，べき乗算 C d において，d の最上位ビットから 1 ビットごとに剰余系における自乗算（S）と乗算（M）の両方の演算を実行する．ビット値が 1の場合，左側に M，右に S の演算を置き，0 の場合はその逆とし，初期値（1 と C）から乗算と自乗算を進めていく．

Vol. 78

No. 10

暗号への脅威「サイドチャネル攻撃」とその対策

1083

して研究されていくであろう．日本においても，

秘密鍵の解読困難

消費電力（Cryptography Research and EvaluCRYPTREC（4）ation Committees）の電力解析実験ワーキンググ
ループを通じて，サイドチャネル攻撃に関する調S

M S

M

S

M

S

M

S

M

S

時間
図 3 ――Montgomery Powering Ladder 法によるサイドチャネル攻撃の対策を施した RSA 暗号処理 LSI における消費電力の時間変化．鍵 1 ビットごとに剰余系における自乗算と乗算が実行されている．これにより図 2 に示したよ
うな消費電力波形の不規則な S と M の出現パターンはなくなり，秘密鍵の特定が困難となる．

査・検討が行われている．
今のところ，サイドチャネル攻撃による被害は，社会問題として報告されてはいない．しかしながら，この状況を楽観することなく，サイドチャネル解析による暗号実装の安全性に関する研究動向は注視する必要がある．
＊＊

だが，RSA 暗号処理のサイドチャネル攻撃の防

これまでの暗号の理論研究は，サイドチャネル御策として用いることもできる．ここではアルゴからの情報漏れはないと仮定され，進められてきリズムの詳細な説明は省略する．

た．しかしながら先述の例に示したように，実装

図 3 は Montgomery Powering Ladder 法 を 用方法によっては，暗号システムから秘密情報が漏いた場合の消費電力の時間変化である．この方法えいする危険性がある．サイドチャネルからの情では，乗算と自乗算が鍵のビット値にかかわらず報漏えいの防御を最終目的とし，暗号の実装研究常に両方実行されるため，波形から秘密鍵を特定者は，新たな脅威となる攻撃を想定し，それを未することは図 2 の場合と比べて困難である．

然に防ぐための対抗策を研究している．暗号の理Montgomery Powering Ladder 法による対策で論研究者は，サイドチャネルからの情報漏れを前は，自乗算を利用した計算に比べ，より多くの乗提とした新たな暗号理論の構築を進めている．い算が必要となる．したがって，図 1 に示した処理ずにせよ，サイドチャネル攻撃の耐性を強化する結果と比べて処理速度が低下している．処理速度には処理性能の低下や製造コストの増加といったを犠牲にして安全性の向上が実現できた，という犠牲が生じてしまう．安全はタダでは手に入らな見方もできる．

いということだ．コストや性能といった利便性と攻撃に対する安全性のトレードオフを考える際のサイドチャネル解析をめぐる動向

選択肢を増やし，人が情報とうまく付き合える社会の実現に向けて，最適な技術を提供できるよう現代暗号におけるサイドチャネル解析の研究は，に暗号研究を進めている．

先に述べた Kocher の研究に端を発する．その研文献および注究は米国 Cryptography Research 社で進められ，（１） R. L. Rivest et al.: Comm. ACM, 21, 120（1978）（２） P. Kocher: in ‘Advances in Cryptology ―― Proc. ofCRYPTO ’96’, N. Koblitz ed., Springer-Verlag（1999）
pp. 104〜113（３） P. Montgomery: Math. Computation, 48, 243（1987）（４） 総務省および経済産業省が共同で開催する「暗号技術検討会」と，情報通信研究機構（NICT）及び情報処理推進機構（IPA）が共同で開催する「暗号技術監視委員会」，「暗号モジュール委員会」で構成されるプロジ
ェクト．電子政府推奨暗号の安全性を評価・監視し，暗号モジュール評価基準等の策定を検討する．

“サイドチャネル解析ビジネス” を広げようとして い る．欧 州 で は，NESSIE（New European
Schemes for Signatures, Integrity, and Encr yption: 2000〜2002 年）や ECRYPT（European Network of Excellence for Cr yptology: 2004〜2008年）
といった欧州委員会の研究プロジェクトを通じて，さらに強力なサイドチャネル攻撃の手法やその対策法が活発に研究されてきた．今後も継続