情報社会における脆弱性にかかわる研究動向:2.情報システムを構成する基盤技術における脆弱性1.暗号における脆弱性について

全文

(1)2. 情報システムを構成する基盤技術における脆弱性. 1. 暗号における脆弱性について筑波大学システム情報工学研究科岡本栄司 okamoto@risk.tsukuba.ac.jp 東京大学生産技術研究所松浦幹太 kanta@iis.u-tokyo.ac.jp 富士通（株）フロンティアセキュリティインフラプロジェクト冨高政治 tomitaka@jp.fujitsu.com 科学技術振興機構社会技術研究開発センター猪俣敦夫 inomata@ristex.jst.go.jp . 暗号における脆弱性とは. 暗号における脆弱性例. 脆弱性とは，一般には傷つけられやすいことを指すが，. ◆共通鍵暗号の脆弱性例. 情報技術においては何か異常時にそこから大きな不具合. 共通鍵暗号は歴史が古く，暗号理論の歴史といえば. が生じることをいう．この意味で言えば，暗号における. ほとんど共通鍵暗号の脆弱性の発見と解決の歴史である．. 脆弱性とは，暗号の安全性や信頼性の反対語であり，主. ここでは特にアメリカ標準暗号 DES の脆弱性について. に暗号が所定の機能を果たさないことを指すと見られる．. 述べる．. 暗号といってもアルゴリズム自体の脆弱性だけでなく，. DES は 1977 年に制定された共通鍵暗号で，次のイン. 暗号を利用する際の脆弱性もある．表 -1 に PKI (Public. ボルーション g を繰り返し用いる．. Key Infrastructure) の脆弱性を挙げておく．暗号の脆弱性のうち，ここでは全体に影響を及ぼす脆. g (x, y, k) = (y, x 5 P (S (E (y) 5 k))). 弱性，すなわち，暗号アルゴリズムの脆弱性を中心に述べる．その主なものには， • 解読に対する弱さ • 異常時の暗号動作の不具合. 入力 x, y は各々 32 ビット，k は 48 ビット，出力は 32 ビットである．P と E はビット転字変換，S は換字変換である．ここで，S のみが非線形変換で残りはすべて線形変換である．したがって，DES の安全性はこの S に帰着されて. などがある．本文では主に前者，すなわち解読に対する. いる．逆に言うと，DES の脆弱性はこの S にあると当初. 安全性を扱うが，後者の例としては，たとえばエラー伝. から見られていた．この推測が正しかったことはその後. 播や同期はずれなどが挙げられる．すなわち，暗号アル. の歴史が示している．. ゴリズムによっては，伝送中の 1 ビットエラーが暗号の. S に潜んでいる可能性のある線形性，拡散性などの脆. 復号処理により，その時点以降ずっと続いてしまうこと. 弱性は，設計の段階から注意深く除去されていた．しか. があり得るが，これは暗号の脆弱性の一種である．実際. し，解明できる脆弱性はそのときの技術レベルに依存す. にはこういうことが起きないような仕組み，あるいは対. るため，必ずしもすべて分かるわけではない．実際，開. 策を組み込んである．なお，暗号ではないが改ざん検出. 発者は差分脆弱性を知っており，その対策も織り込んで. 符号ではこのエラー伝播を有効に利用している．. いたが，線形脆弱性は知らなかったため，1993 年につ. さて，本特集においては，一見どうということないよ. いに解読されてしまった．ここで，差分とは，2 つの. うなことが攻撃の糸口を与えるような要素を特に暗号の. ビットパターン x1, x2 に対するビットごとの排他的論理. 脆弱性として取り上げる．まず，例をいくつか挙げよう．. 和 x = x 1 5 x 2 をいう．S の差分特性は，S の入力差分と. 1）. 出力差分の間に存在する統計的な偏りであり，これを利用して解くのが差分解読である．同様に，S の線形特性とは，S の入出力変数間に存在する線形近似であり，こ IPSJ Magazine Vol.46 No.6 June 2005. 625.

(2) 特集情報社会における脆弱性にかかわる研究動向. 想定される脆弱性例. CA. RA. クライアント. ・物理的な脆弱性. ・災害等によるサーバ破壊・災害等による・事故等による秘密鍵の紛失業務続行困難の可能性. ・暗号アルゴリズムに係る脆弱性. ・当該暗号アルゴリズムの計算量的安全性担保の限界. ・システム実装に係る脆弱性. ・通信路における盗聴. ・新たな攻撃法・システムにおけるバグ・秘密鍵利用モジュールの耐タンパー性不足による秘密鍵の露呈. ・鍵に係る脆弱性. ・通信路における盗聴. ・証明書に係る脆弱性・相互認証時の CRL の交換. ・秘密鍵利用モジュールの耐タンパー性不足による秘密鍵の露呈. ・秘密鍵の流出・暗号アルゴリズム危殆化後の以前の証明書・CRL 掲載後の秘密鍵による以前の証明書の扱い. ・運用に係る脆弱性. ・内部. ・本人確認に係・秘密鍵の流出るリスク. ・その他法制度等. ・電子署名法における非改ざん性に係る記述がないことによるトライアルエラーのリスク・保険等. 表 -1 PKI の脆弱性. の偏りを利用して解くのが線形解読である．. が無視できない確率で存在するというものである．したがって，ビット長の半分の安全性しかないことになる．. ◆ハッシュ関数の脆弱性. 実際によく用いられている暗号用ハッシュ関数に. 一般に，ハッシュ関数とは，長いデータを短いビット. RSA 社の MD5 があるが，これに対しては衝突ペアが報. 長に圧縮する変換を指す．一方，暗号におけるハッシュ. 告されている．したがって MD5 にはある種の脆弱性. 関数はさらに一方向性が要求される．暗号分野ではハッ. が潜んでいると見られるが，まだ詳細は発表されていな. シュ関数は署名や認証子の計算に補助的に用いられてい. い．この脆弱性は MD5 だけでなく，他のハッシュ関数. たが，その後安全性の根幹にかかわる重要なプリミティ. にも存在していると見られる．. 2）. ブであることが次第に明らかになってきた．特に，ランダムオラクルモデルでは，理想的なハッシュ関数がハッ. ◆公開鍵暗号の脆弱性. シュオラクルとして中心的プリミティブとして利用さ. 代表的な公開鍵暗号に RSA 暗号があり，よく用いら. れている．理想的なハッシュ関数では，ある値 x のハッ. れている．発表以来，さまざまな脆弱性が指摘されて. シュ関数値 h(x) が，x 以外のどんな値 y に対する値 h(y) に. きたが，多くは代数的性質によるものである．ここで，. 対しても独立である．. RSA 暗号の暗号化鍵を (e, n)，復号鍵を (d, n) とする．指. 暗号用ハッシュ関数の要件としては，衝突困難性，一. 数 e が小さいと同報メッセージが解読できるという脆弱. 方向性がある．ここで，衝突困難性とは h(x1) ＝ h(x2) を. 性はよく知られているが，他には次のようなものがある．. 満たす相異なる x1, x2 が容易に見出せないことを言い，一方向性は出力に対して入力を求めるのが困難である. メッセージに関連した脆弱性. ことを言う．暗号用ハッシュ関数例には MD5 ，SHA-1 ，. たとえば，2 つのメッセージ M1, M2 の間に低次の関数. SHA-n (n ＝ 256, 384, 512, …) などがある．. f により M1 ＝ f(M2) という関係があったとする．C1, C2 を. ハッシュ関数の脆弱性には，昔から知られているバー. M1, M2 の暗号文とすると，M2 は f (x) − C1 と x -C2 の共通. スディパラドックスがある．これは，ハッシュ関数の出. 根であるため，この 2 つの多項式の最大公約数は x − M2. 力ビット長が n のとき，2. を含むことになる．. n/2. 626. 個の入力があれば衝突ペア. 46 巻 6 号情報処理 2005 年 6 月. e. e.

(3) 2. 情報システムを構成する基盤技術における脆弱性 1. 暗号における脆弱性について. また，メッセージにプレフィックスとして固定パター. 可能となる場合がある．たとえば IC カードで実行中の. ンをつけておくと，メッセージが求められてしまうケー. 電力消費量や処理時間の情報から，鍵を割り出すことが. スがある．たとえばメッセージ・フォーマットが. 可能となっている．主に，公開鍵暗号に有効な攻撃であり，研究成果も多い．たとえば，RSA 暗号のタイミングアタックでは，たとえ e と e' の重みが同じでも，x. M = P data. e. mod n と x mod n の計算時間が異なっていることを利 e'. の形をしていたとして，これが暗号化されて送られる. 用して，解読に成功している．したがって，これらサイ. とする．ここで，P が固定プレフィックスである．プロ. ドチャネル情報は脆弱性になる．. トコルとして，受信側で復号した結果がこの形をしていない場合にエラー通知するとしよう．このとき，盗聴者はメッセージ M に対する暗号文 C から M を次のように. 暗号の脆弱性の影響. して得ることができる．まず，盗聴者は乱数 r から C1 ＝. 暗号には以上述べたようにさまざまな脆弱性が報告. r C(mod n) を計算して受信者に送る．受信者は C1 (mod. されており，まだ見出されていないものもあるであろう．. n) ＝ rM(mod n) を計算して，その最初に固定パターン P. 未知の脆弱性を含め，これらが発見されたときに放置し. がないとエラー通知をするので，盗聴者は rM(mod n) の. ておくと，多方面に影響が現れることになる．そのため，. 最初が P か否かを知ることができ，r を変えることによ. その影響について技術的，経済学的見地から調査検討が. り，徐々に M が求められることになる．特に，P が短い. 行われている．. と rM(mod n) のプレフィックスが P と一致することが多. 科学技術振興機構・社会技術システム・ミッションプ. くなる．. ログラムⅡ・暗号リスクワーキンググループでは，暗号. e. d. の脆弱性が修復不可能になった場合の新暗号への切り替. 因数分解. え，顧客保障等についてリスクの観点からの検討を行っ. 以上は RSA 暗号の代数的脆弱性であるが，修復可能な. ている．また，暗号利用システムの経済学的リスクにつ. ものである．しかし，RSA 暗号は因数分解の困難さに依. いても調査検討を行っている．. 存しているため，ここに脆弱性があると修復不可能となる．では，実際，因数分解はどのくらい困難なのであろう. 暗号の危殆化の影響. か．RSA 暗号の最初の論文では，80 桁整数の因数分解. 暗号の脆弱性が修復不可能になった場合には，新しい. が不可能であると書かれていたが，その後のハードウェ. 暗号への切り替えが必要となる．その時期は旧暗号の危. アやアルゴリズムの改良により，1999 年時点で 512 ビッ. 殆化の進み具合とそれに伴う被害の広がり，新暗号開発. ト長整数（154 桁）の因数分解は可能となっている．2 次. コスト，新暗号利用コストなどに依存する．ここで，被. 篩法や数体篩法あるいは楕円曲線法などが因数分解アル. 害の広がりについては，単なる被害額よりも風評や集. ゴリズムとして提案されているが，結局のところ，整数. 団心理にも依存する面が大きいので，評価は困難を極め. の分布に関する性質が脆弱性になっている．. る．このため，これだけでなく，視点を変えて，通信品. 量子計算機が実現できれば，因数分解を多項式時間. 質や接続性，可用性の観点からサービス提供者とユーザ. で求められることが文献 3）で示されている．量子重ね. 間の取り決めとして導入されている SLA（Service Level. 合わせにより n 量子ビットで 2 の状態を一度に表現でき. Agreement）を，暗号システムにおいても導入すること. るため，並列処理が可能となる．これにより fa(x) ＝ a. を検討している．これはサービスレベルに見合ったコス. n. x. mod n の離散フーリエ変換を行い，fa(x) の周期 L を求め，. トを明確にすることにより，サービス提供側と利用側が. gcd(a. 妥協できる点を見出せるため，信頼の構築にもつながる．. L/2. ± 1, n) から因数を計算する．なお，周期を求め. ることは離散対数問題を解くことに通じるので，量子計算機により離散対数問題も解けることになる．現在，量. 経済学的考察. 子ビットの実現が精力的に行われているが，暗号で用い. たとえ標準暗号に基づいた暗号システムであっても，. られている整数の因数分解には千のオーダーの量子ビッ. 実際には適切に利用・運用されずリスクが最小化されて. トが必要となるため，その実現にはまだかなり時間がか. いない恐れが高い．そこで，この問題の具体的な発現. かると見られている．. の仕方を観測可能なデータで調査するとともに公共政策学的分析を行い，とくに非個人ユーザ（またはユーザ. ◆サイドチャネルアタック. グループ）のリスク管理に関して我が国が取り組むべき. 暗号処理中に得られる付随的な情報によって，解読が. 課題を抽出する．まず，暗号利用システムのリスク管理 IPSJ Magazine Vol.46 No.6 June 2005. 627.

(4) 特集情報社会における脆弱性にかかわる研究動向. 図 -1 RSA-OAEP (Optimal Asymmetric Encryption Padding). を「情報セキュリティへの最適投資」の観点で研究する. トのメッセージ M を，次式により，k ＋ k0 ＋ k1 ビットの. ため，中程度の脆弱性対策を最重要視する基本的な理論. 暗号文 C に変換する．. モデルの検証を地方自治体のデータを用いて行うとともに，Gordon-Loeb 評価モデル，CERT/CC 評価モデルおよび Idaho 評価モデルなど米国の動向調査を行った．総じて米国の情報セキュリティ投資評価モデル研究は最も効果的な対策額を算出するコストパフォーマンス重視で. C = RSA( s r 5 H (s)) k ここで， s = ( M 0 k1) 5 G ]rg，r は k0 ビット乱数，0 1. は k1 ビットのオール 0 ，G, H はランダム関数である．な. あるが，我が国における評価モデルは，対策をしない場. お，ランダム関数とは，各入力に対して出力がランダム. 合の被害額と，した場合の被害額の差を最大化する被害. な数となる関数である．この OAEP はランダムオラク. 最小化モデル重視である．これからは我が国でもコスト. ルモデルのきっかけになったもので，その後の暗号系の. パフォーマンスを考慮した評価モデルが求められよう．. 安全性証明に多大な影響を与えた．ランダムオラクルモデルでは，たとえば OAEP を破ることが RSA の復号を. 暗号の脆弱性対策. 行うことになるように（復号鍵を持たずに），ハッシュ. 暗号の脆弱性対策には，事前対策と事後対策がある．. の道具を与え，それを用いて解読をしてもらう．その際，. 技術的には事前対策に目を向けがちであるが，脆弱性対. 貸した道具に仕掛けがしてあって解読するには RSA 復. 策では事後対策が重要である．いくら事前対策を行って. 号が避けられないようにする．この際，ハッシュ関数の. も，予想できない脆弱性があるからで，完全に脆弱性を. 性質，すなわち，ある値 x のハッシュ関数値 h(x) が，x 以. 除くことは不可能である．. 外のどんな値 y に対する値 h(y) に対しても独立であると. まず，事前対策例をいくつか挙げよう．共通鍵暗号で. いう性質が決定的に重要である．. は，差分解読と線形解読を通して，差分脆弱性と線形脆. 整数の因数分解や離散対数に対する脆弱性が無視し得. 弱性に対する評価尺度として，最大差分特性確率と最大. なくなった場合には，これらを使わないような暗号を用. 線形特性確率が生まれ，耐脆弱性を定量的に示すことが. いるしかなくなる．たとえば，楕円曲線暗号は現時点で. できるようになった．したがって，共通鍵暗号を考案す. 考えられる対策の 1 つである．しかし，楕円曲線は双線. るときには，この評価尺度が安全性基準をパスするよう. 形関数を持つような群をなしており，整数環よりも特殊. に設計すれば差分解読と線形解読には耐性を持つことが. なので，未知の脆弱性もむしろ多いかもしれない．この. 保障できる．これはその後の暗号設計に大きな影響を与. ため，共通鍵暗号のみで暗号システムを組むという研究. えた．ハッシュ関数では，最近の衝突発見につながった. 提案もなされている．. 脆弱性が明らかにされていないので，それを待たなけれ. それでも，暗号が危殆化することは避けられないであ. ばならない．. ろう．そのため，そういう事態になった場合の事後対策. 公開鍵暗号では，図 -1 に示す Optimal Asymmetric. が重要となる．その例として，ここでは暗号変更容易な. Encryption Padding（OAEP）によって，代数的脆弱性を. 汎用暗号方式について紹介しよう. 取り除くことができる．RSA に対する OAEP では k ビッ. と復号プログラムを一体化した情報自己保護機構ともい. 628. 46 巻 6 号情報処理 2005 年 6 月. 関数を仕組む．すなわち，解読者にハッシュ関数や復号. 4），5）. ．これは暗号文.

(5) 2. 情報システムを構成する基盤技術における脆弱性 1. 暗号における脆弱性について. M. 送信側. 受信側. Enc(K,M)＋Dec(). Dec(K,C). 鍵K. 鍵K. M. 図 -2 汎用暗号方式. える，オブジェクトオリエンティドな考えかたに基づく. 者のマスター鍵のようなものが必要となろう．これらの. 方式である（図 -2）．鍵はあらかじめ，共有しておく必. ディメリットを取り除く研究も進められており，今後が. 要がある．. 期待できる．. アイディアは簡単であるが，次のようなメリットがある． • 受信側であらかじめ復号プログラムを持っている必要がない． • 暗号の変更が容易である． • 暗号の危殆化に際し，新暗号への移行が容易である． • 送信側の責任で自由に暗号を選べるため，標準暗号が使えないケースでも，独自暗号を使うことが容易である．一方，ディメリットとしては， • 復号プログラムの信頼性が求められる（トロイの木馬となっていない保障）． • 別途，鍵配送・変更スキームが必要となる．などがある．最初の信頼性については，java 機構の利用である程度確保できる．暗号アルゴリズム自体の信頼性については，ディフォルトとして安全性が確保されている暗号アルゴリズムを利用すればよい．一方，独自暗号を利用する場合は送信側に暗号利用のメリットがある場合が多いので，解読防止義務は送信側にある．2 番目の鍵配送等については今後の重要な課題であるが，受信. あとがき暗号に限らず，IT 技術には脆弱性が付き物であり，完全に取り除くことはできない．そのため，脆弱性の除去と同時に脆弱性が見出されたときの対策，いわば Contingency Planning が今後事後対策として重要になる．謝辞本研究の一部は，社会技術研究システムミッション・プログラム II「高度情報社会の脆弱性の解明と解決」の研究として行われたものである．土居範久統括をはじめ関係各位に深謝する．参考文献 1）Matsui, M. ：Linear Cryptanalysis Method for DES Cipher, Proc. of Eurocrypt'93, LNCS765, pp.386-397（1993）． 2）Wang, X., Feng, D., Lai, X. and Yu, H.：Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, 2004/199, Cryptology ePrint Archive of IACR（2004）． 3）Shor, P. W. ：Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Computing, Vol.26, No.5, pp.1484-1509（1997）． 4）Nam, S., Okamoto, E., Shinoda, Y. and Mambo, M. ：A Design and Implementation of a Platform for Self-Deciphering Secret Communication, Proc. of International Symposium on Information Theory and Its Applications, pp.242-245 （1996）． 5）金岡晃，岡本栄司：SePO（Self Protected Object）の提案とその実現方法について，CSS'02 予稿集，pp.197-202 （2002）．（平成 17 年 4 月 1 日受付）. IPSJ Magazine Vol.46 No.6 June 2005. 629.

(6)