B06班：暗号システムに対する実装攻撃の適用と限界に関する計算的研究代表：櫻井幸一（九州大学）分担：酒井康行（三菱電機, H16年博士（工学）＠九州大学）高木剛（公立はこだて未来大学）田端利宏（岡山大学）目的：暗号システム（アルゴリズム・プロトコル）への種々の実装攻撃に対して計算論的な立場からその限界を明かし、現実性のある脅威かどうかの客観的評価指標を与えることを目的とする 1 研究背景／目的 • ICカードが普及しつつあり、暗号化も内蔵のICチップで処理でき、より安全になる、という利点がうたわれている – しかし、ICカードへ実装した暗号技術に対するハードウエア攻撃の問題点は現実レベルで指摘されている • 種々の実装攻撃に対する学術的な体系化、現実性のある脅威かどうかの客観的評価指標は未だ確立されてない • 暗号アルゴリズム・暗号通信プロトコルの特性を利用した実装に対するさまざまな攻撃（サイドチャネル攻撃）を体系的に論じる – 特にサイドチャネル攻撃では、前提となっている物理的な仮定の強弱を相対的に比較することで、どの攻撃がどのような環境で現実的な脅威となりえるか、客観的な尺度を与える 2 研究組織 • 櫻井幸一（九州大） – 暗号理論・情報セキュリティ – 研究の計画、遂行、監督 • 田端利宏（岡山大） – コンピュータシステムセキュリティ – 実装攻撃評価ツール開発と実装 • 酒井康行（三菱電機） – 公開鍵暗号システムの設計と実装 – 評価実装攻撃技術の分類と攻撃の前提条件の実験的比較 • 高木剛（公立未来はこだて大） – 数論アルゴリズムと公開鍵暗号理論 – 実装攻撃の理論解析・防御アルゴリズムの設計 3 暗号システムに対する実装攻撃の適用と限界に関する計算的研究１．楕円曲線暗号のための剰余算に対するサイドチャネル解析楕円点倍算 ⇒ 高速化研究の対象楕円曲線ドメインパラメータ ⇒ ECDLPが困難になるように選択することが必須かつ高速実装可能なパラメータを選択することが望ましい高速化手法を使ったためにサイドチャネル漏洩が起きることがある例：Montgomery乗算を用いたRSA暗号(べき乗剰余演算) に対するタイミング攻撃 [Kocher ’96, Dhem他 ’98] 4 研究の背景，動機楕円点倍算の単純電力解析(SPA)対策 Always ADD-DBL法 Unifiedアプローチ…点加算と点2倍算を同じ公式で計算する Walter CHES’04 Brier-Joyeのunified code + Montgomery乗算による楕円点倍算実装に対するSPA より一般的な剰余算実装に対するサイドチャネル攻撃を検討本研究：楕円曲線暗号でよく用いられる一般化メルセンヌ素数とその素数専用の剰余算法による実装の脆弱性は？ NIST推奨の素体上楕円曲線について，剰余算実装の SPAに対する脆弱性を考察 5 一般化メルセンヌ素数剰余算への攻撃法 SPA対象の実装楕円点倍算：左バイナリ法楕円点加算および点2倍算：unified code (by Brier-Joye) 剰余算：一般化メルセンヌ素数によるextra reduction付き実装 (NIST推奨ドメインパラメータ) 攻撃者実装されているアルゴリズムが上記であることを知っている剰余算におけるextra reductionの有無を検出できる * Extra reduction: （法乗算への）入力に依存した条件付処理  extra reductionに起因するサイドチャネル情報を利用した暗号解析法を提案（extra reductionの有無を手がかりに，秘密べき指数のビットを推定できる） 6 攻撃法のまとめ NIST推奨曲線のような一般化メルセンヌ素数による専用剰余算実装とunified codeとの組み合わせは SPAに対して脆弱となることをシミュレーションで確認  192ビットの曲線に用いられている素数p=2192-264-1による剰余算実装は特に脆弱（extra reductionの発生確率が高い） unifiedアプローチは、有限体レイヤー演算レベルでの unifyではSPA対策として不十分防御法 extra reductionが起きにくいGを選択する ランダム点による加算よりも，G加算の方が，extra reduction が生じる確率は小さい条件付処理の生じない剰余算アルゴリズムにする  ベースポイントの座標地を適切に選択すれば，extra reduction の確率を減らせる 7 ２．暗号モジュール関連の標準化：国際 (1/2) 国際 ISO/IEC 15408 国際セキュリティ評価基準：CC (Common Criteria) 米国/カナダ米国：NIST (National Institute of Standard and Technology) カナダ：CSE (National Institute of Standard and Technology) FIPS 米国連邦政府調達規準 AESなど様々な暗号アルゴリズムの仕様を策定 FIPS 140-2: 暗号モジュールのセキュリティ要件 http://csrc.nist.gov/CryptoToolkit/ 8 暗号モジュール関連の標準化：国際 (2/2) CMVP (Cryptographic Module Validation Program) 1995年にNIST(米国)およびCSE(カナダ)により創設された，暗号モジュール検証制度 http://csrc.nist.gov/cryptval/cmvp.htm ベンダが開発した暗号モジュールが FIPS140-2 (暗号モジュールのセキュリティ要件)に適合しているかどうかの検証を行う．アプリケーション/ システム暗号モジュール暗号アルゴリズム現時点ではサイドチャネル攻撃に関して考慮されていない． 9 暗号モジュール関連の標準化：国内 (1/2) CRYPTREC (Cryptographic Research & Evaluation Committees) (http://www.cryptrec.jp/) 事務局：情報処理推進機構(IPA)および情報通信研究機構(NICT) 委員：国内の大学および企業の一線の暗号研究者電子政府推奨暗号を決定(2003年3月) 暗号技術動向の監視活動暗号モジュール委員会：暗号実装関連技術の調査評価財団法人日本規格協会情報技術標準化研究センター (INSTAC) サイドチャネル攻撃や耐タンパ技術の調査評価基準の策定および提案 10 暗号モジュール関連の標準化：国内 (2/2) J-CMVP 事務局：情報処理推進機構(IPA) 委員：国内大学，企業の暗号研究者日本における暗号モジュール評価制度 2007年度運用開始 11 • 啓蒙活動＠酒井 – サイドチャネル攻撃の解説記事を、一般向けに日経エレクトロクスに発表、この方面の研究現状の啓蒙につとめた。特に、実装攻撃に対する安全なハードウエアの評価認証の現状と市場製品の動向も調査 2. 学術的なアプローチ -- ソフトウエア工学との融合 12 ３．楕円曲線暗号に関する研究 • 楕円曲線暗号の効率性評価 - スカラー倍算 dP ‐整数dの冗長2進表現 (e.g., Frac-wNAF, Frac-wMOF) • 非零桁分布の理論的見積もり - 連続非零桁の分布解析 13 主要論文 • [OSST04] Katsuyuki Okeya, Katja Schmidt-Samoa, Christian Spahn, Tsuyoshi Takagi, "Signed Binary Representations Revisited", CRYPTO 2004, LNCS 3152, pp.123-139, 2004. • [SST06] Katja Schmidt-Samoa, Olivier Semay, Tsuyoshi Takagi, "Analysis of Fractional Window Recoding Methods and Their Application to Elliptic Curve Cryptosystems", IEEE Transactions on Computers, Vol.55, No.1, pp.48-57, 2006. • [OT06] Katsuyuki Okeya, Tsuyoshi Takagi, "Security Analysis of CRT-Based Cryptosystems", International Journal of Information Security, IJIS, Vol.5, No.3, pp.177-185, Springer-Verlag, 2006. • [KTHKL06] Tae Hyun Kim, Tsuyoshi Takagi, Dong-Guk Han, Ho Won Kim, Jongin Lim, "Side Channel Attacks and Countermeasures on Pairing Based Cryptosystems over Binary Fields", 5th International Conference on Cryptology and Network Security, CANS 2006, LNCS 4301, pp.168-181, Springer-Verlag, 2006. 14 報道発表１日経新聞2004年8月6日 CRYPTO2004 [OSST04]の成果 15 報道発表２日経新聞2004年6月11日 Int. Journal. Inf. Security [OT06]の成果 16 報道発表３北海道新聞2006年7月２7日 CANS2006 [KTHKL06]の成果 17 CRYPTO2004 [OSST04], IEEE Transaction [SST06] 今後の展開 18 スカラー倍算 n-1+d[n-2]2n-2+…+d[1]21+d[0]20 d = d[n-1]2 dP   P  P    P ,   , d i  桁集合T d Square & Multiply Method Q=P for i=n-2 down to 0 Q = ECDBL(Q) if d[i] = 1, then Q = ECADD(Q,P) return(Q) Example d = 345 345 = 1 0 P D 2P D 1 4P A 5P 0 10P D 1 D 1 42P 20P A 21P 0 D A 43P 0 86P D D 1 172P D 344P A 345P 19 wMOF [OSST04] • wNAF : ハミング重み(di≠0の桁数)が最小のクラス ‐（桁集合Tw={0, ±1, ±3,…,±(2w-1-1)}） • Booth Encoding ： • wNAF = BoothEncoding + 幅w窓法（下位桁から） • wMOF = BoothEncoding + 幅w窓法（上位桁から） 20 Frac-wMOFの生成法[SST06] 桁集合 T3.5 = {±1, ±3, ±5} w=3.5のFrac-wMOF 2d – d = 1 0 0 0 0 1 0 0 0 0 -1 1 0 -1 1 0 0 -1 1 0 1 0 0 0 0 0 0 -1 1 -1 0 -1 1 0 0 -1 1 -1 0 0 -5 1 0 0 -1 1 -1 0 1 0 0 0 0 0 0 0 -5 1 1 0 0 0 0 0 0 0 -5 1 00 00 0-1 71 -1 0 0 0 0 0 -3 0 (Frac-3.5MOF) 21 今後の予定 1 0 0 0 0 0 0 0 -5 1 0 0 0 0 -3 0 (Frac-3.5MOF) 平均連続非零桁濃度の見積もり平均ゼロラン長の見積もり楕円曲線暗号の効率性見積もりに応用 22 櫻井先生のemail： [email protected]