Comments
Description
Transcript
講演内容 共通鍵暗号の標準化 標準化動向 - ブロック暗号
講演内容 中央大学COEプログラム 2003年4月16日 1. 共通鍵暗号の評価に関する 最新動向 暗号の標準化概要 、 、 NESSIEの最終選考結果 AES の最近の安全性評価 CRYPTRECの調査 AES CRYPTREC NESSIE 2. 3. 4. 富士通研究所 下山 武司 標準化動向 - ブロック暗号 共通鍵暗号の標準化 種類 ブロッ ク暗号 AES 1998.6.15 AES応募締め切り 2000.10.2 Rijndael に決定 2001.11.26 FIPS登録 CRYPTREC 2000.7.14 2001.9.27 2003.2.20 NESSIE 2000.7.29 2003.2.28 64bit Defact MD5 SHA-1 ~ 擬似乱 数生成 ストリー ム暗号 SHA-1 SHA-256 SHA-384 SHA-512 128-bit RC4 MULTI-S01 MUGI ISO CD Triple-DES MISTY1 IDEA CAST-128 Khazad AES AES AES Camellia Camellia Camellia SC2000 SHACAL-2 SEED CIPHERUNICORN-A Hierocrypt-3 : NESSIE SHA-256 SHA-384 SHA-512 Whirlpool 標準化動向 - 公開鍵暗号 ISO CD RIPEMD -family(2) SHA -family(4) Whirlpool ANSI X9.42 AnnexC.1 FIPS 186-2 FIPS186-2 Appendix 3.1 Appendix 3.1 FIPS 186-2 revised Appendix 3.1 RC4 NESSIE (http://www.meti.go.jp/feedback/downloadfiles/i30220ej.pdf) NESSIE : B.Preneel,“NESSIE project announce finalselection of crypto algorithm” (http://www.cosic.esat.kuleuven.ac.be/nessie/deliverables/press_release_feb27.pdf) ISO CD (18033-1) Alex Dent, “OPT7:Standards & evaluation criteria ”, (http://www.isg.rhul.ac.uk/msc/teaching/opt7) [2003.3.30 version] 最終選考結果発表 RIPEMD-160 SHA-1 SHA-256 SHA-384 SHA-512 CRYPTREC 文献 : 各暗号リストは下記より参照 CRYPTREC : 総務省,経済産業省, 電子政府推奨暗号リスト 平成15年2月20日 NESSIE 応募締め切り CRYPTREC AES 128bit 電子政府推奨暗号リスト発表 FIPS FIPS Triple-DES Triple-DES 3-key Triple DES MISTY1 MISTY1 CIPHERUNICORN-E Hierocrypt-L1 ブロッ ク暗号 応募締め切り(2000年度分) 応募締め切り(2001年度分) 標準化動向 - ハッシュ関数他 種類 ハッシュ 関数 Defact 種類 署名 守秘 鍵交換 Defact FIPS CRYPTREC RSA RSA RSA-PSS RSA-PSS RSASSA-PKCS1-v1_5 DSA ECDSA ECDSA DSA ECDSA RSA DH RSA-OAEP RSAES-PKCS1-v1_5 DH PSEC-KEM ECDH NESSIE ISO CD RSA-OAEP RSA-KEM ACE-KEM ECIES-KEM PSEC-KEM PSEC-KEM SFLASH EPOC-2 HIME(R) RSA-KEM ACE-KEM PANAMA 1 NESSIE 応募暗号一覧 (Phase 1st Evaluation) Block Cipher (64bit) NESSIE:最終選考結果 CS-Cipher HierocryptL1 IDEA Khazad MISTY1 Nimbus SAFER++64 NUSH Asymmetric ACE Sign ECDSA Digital ESIGN Signature FLASH QUARTZ RSA-PSS SFLASH Stream Cipher BMGL Leviathan LILI-128 SNOW SOBER-t16 SOBER-t32 Hash & MAC Whirlpool Two-Track-MAC Asymmetric Identification UMAC Block Anubis Cipher Camellia (128bit) Hierocrypt-3 Asymmetric ACE Encryption Noekeon Encryption ECIES Testing Q EPOC-1 methodology RC6 EPOC-2 SAFER++128 EPOC-3 SC2000 PSEC-1 Block SHACAL PSEC-2 Cipher PSEC-3 (160bit) RSA-OAEP NESSIE 第一次選考結果 (Phase 2nd Evaluation) [2001.Sep.] Block Cipher (64bit) Stream Cipher Block Cipher Camellia (128bit) Asymmetric ECDSA Digital ESIGN Signature SNOW SOBER-t16 SOBER-t32 IDEA Khazad MISTY1 SAFER++64 BMGL MAC & Hash Asymmetric Encryption Whirlpool Two-Track-MAC Asymmetric Identification UMAC NESSIE Asymmetric Digital ECDSA Signature Stream Cipher MISTY1 MAC & Hash GPS ACE Encryption ECIES Testing Block Cipher Camellia (128bit) Asymmetric Encryption Whirlpool SHA-2 Two-Track-MAC Asymmetric Identification UMAC EMAC HMAC RSA-PSS SFLASH GPS ACE-KEM Testing methodology methodology RC6 SAFER++64 Using the generate next bit predicter like an evaluation criteria 最終選考暗号一覧 [2003.Feb.] Block Cipher (64bit) QUARTZ RSA-PSS SFLASH GPS EPOC-2 AES Block SHACAL Cipher (160bit) PSEC-2 RSA-OAEP NESSIE最終選考レポート(1) 選考暗号 種類 暗号名 Block Stream Hash MAC コメント(いずれも安全性に問題なし) MISTY1 AES Camellia SHACAL-2 標準のKASUMIと似た性質を持つ 登録 多く面でAESと似た性質を持つ (特に記述なし) Whirlpool SHA-256,-384,-512 UMAC TTMAC EMAC (DMAC) HMAC 適切なセキュリティマージン。SHA-512より若干遅いが許容範囲。 NIST標準、大きなセキュリティマージン、処理速度は許容範囲。 AESの擬似乱数性を根拠とする証明可能安全性を持つ RIPEMD-160の擬似乱数性を根拠とする証明可能安全性を持つ ISO/IEC9797-1。ブロック暗号を根拠とする証明可能安全性。 ISO/IEC9797-1。ハッシュ関数を根拠とする証明可能安全性。 採用なし 3GPP FIPS Block SHACAL-2 Cipher (160bit) PSEC-KEM RSA-KEM NESSIE最終選考レポート(2) 非選考暗号 種類 暗号名 Block Khazad IDEA SAFER++64 Triple-DES RC6 SAFER++128 SHACAL-1 Stream SNOW SOBER-t16,-t32 BMGL Hash SHA-1 RIPEMD-160 非選考理由 対称的な構造に対する懸念 IPRの問題と鍵スケジュールに対する懸念 構造的特性が持つ安全性への懸念と処理速度の遅さ 安全と考えるが処理が遅い 深刻なIPRの問題 構造的特性とセキュリティマージンの少なさへの懸念 鍵スケジュールに対する懸念 鍵全数探索より効率的な攻撃法の存在 鍵全数探索より効率的な攻撃法の存在とサイドチャネル 攻撃に対する脆弱性への懸念 TMTF攻撃に対する脆弱性と処理速度の遅さ 出力ビット長 (160bit) が短い 出力ビット長 (160bit) が短い 2 AESの安全性評価の現状 最近「AESの解読に成功した」と主張する論文がいくつか 発表されているけど、本当のところはどうなのだろう? AES:最近の安全性評価 そこで、ここ一年以内に発表された以下の攻撃法について検討。 攻撃名 1. 2. 3. 4. XSL Attack PDRCAttack Cache Attack DFA 著者 他 角尾 他 青木 他) 他) Courtois . Filiol ,( Giraud, (Dusart 日付 2002.4.10 2002.7.2 2003.10.10 2003.1.2 解読計算量等 work factor of 2100 231 cipher texts 220 encryption 50 faulty cipher texts 1.XSL Attack 代数方程式をバリバリ使って秘密鍵を導出 AES 理論的攻撃 方法 ( )にてCourtois らの攻撃法の有効性が検討された。 からのコメント (2002/9/19) 「彼らの攻撃法には欠陥があると思われる。」 具体的には • 「論文中の “T’ method” において、独立な式をダブルカウントしている。」 • 「線型方程式として解くための十分な方程式が得られていない。」 Courtois からの反論 (2003/4/9) 「Coppersmithは “T’ method”を理解していないと思われる。」 事実、小さい例では完璧に動くことが確かめられている。 Coppersimith からの再コメント (2003/4/10) AES Forum NIST web page • Coppersimith • • 文献 「欠陥というのは強すぎる言い方だったかもしれない。 しかしAESに対して正しく動くことは、未だ証明されていない。」 D.Coppersmith, N.Courtois etc.“Re: Impact of Coutois and Pieprezyk results”, AES General Cryptanalysis Issues Forum (http://aes.nist.gov/aes) XY=1 AES全体を巨大な連立2次方程式とみなし、多変数多項式の項を 独立変数とみて線型方程式として解く 結論 1. 僅かな既知平文と2 回のAES計算量で、秘密鍵を導出可能。 2. AESの安全性は段数に関して、準指数的にしか増加しない。 100 文献 XSL Attack は有効か? の S-box の入出力ビットは2次の関係式 および、線形関係式で記述可能。 AES N.Courtois, J.Pieprzyk, “Cryptanalysis of Block Cipher with Overdefind Systems of Equation”, ASIACRYPT2002, LNCS2501 (http://eprint.iacr.org/2002/044/) 2.PDRC Attack 「独自」の乱数検定法で、AESの出力を乱数と区別可能。 方法 平文 : P = X&0xEFEFEF...EF, X in GF(2) 暗号文 : C = (c ,…,c ) 計算機実験の結果、次の式が確率 p=0.500029 で成立することが判明! 128 0 127 1+c71=k2+k3+k4+k6+…+k126 over GF(2) 文献 (下山注:単なる線形攻撃では?) E.Filiol, • “A New Statistical Testing for Symmetric Ciphers and Hash Functions”, ICICS2002, (http://eprint.iacr.org/2002/099) • “Plaintext-dependent Repetition Codes Cryptanalysis of Block Cipher”, (http://eprint.iacr.org/2003/003) • Complete sources of the AES cryptanalysis program. (http://www-rocg.inria.fr/codes/Eric.Filiol/PDRC.html) 3 Did Filiol Break AES? アメリカ、フランス、アイルランド、スイスの暗号研究者らが、Filiol の結果を詳細 に検討 z 検証法 論文に書かれた手法を独立に実装し実行(endian, mask等を複数考慮) Filiolが公開しているソースコードをコンパイルし実行 統計量に関する理論的な考察 z 結果 「複数の研究者が独立に検証したがFiliolの結果を誰も再現できなかった。」 z 原因の考察 プログラム中でのrand() の使用 マジックナンバー “N2” のバグ 統計量の扱い方に誤り 文献 AES サイドチャネル攻撃 N.Courtois, R.Johanson, P.Junod, T.Pornin, M.Scott, “Did Filiol Break AES?”, (http://eprint.iacr.org/2003/022) 3.Cache 攻撃 4.DFA (Differential Fault Analysis) 暗号装置を故意に故障させ、出力した暗号文から秘密鍵を導出 キャッシュメモリヒット、ミスの時間差を利用して秘密鍵を導出 仮定: ブロック毎の暗号化処理時間が精密に測定可能 処理開始時はキャッシュメモリ上にS-boxテーブルがない 原理: 演算時間が長い P P K K これを繰り返して キャッシュミス 秘密鍵情報を得る S S P +K ≠P +K 結果: 計算機を使った実験で、2 回の暗号化処理で 93%の確率で 秘密鍵を導出可能であることを確認 1. 2. 0 0 0 0 1 1 1 1 20.52 文献 Y.Tsunoo, E.Tsujihara, K.Minematsu, H.Miyauchi, “Cryptanalysis of Block Ciphers Implemented on Computers with Cache”, proceedings of ISITA2002, Oct.7-11, 2002. 青木, 山本, 植田, 盛合, “128ビットブロック暗号に対するキャッシュ攻撃”, Proceedings of SCIS2003, Jan.26-29, 2003. Optical Fault Induction Attack チップ上のデータを外的な操作で制御することは可能か? 条件さえそろえば可能 方法: SRAMチップ上の一点に焦点を集めた光を当てて、内部の ビット情報を任意に制御する。 結果: 実験では成功。 上のCMOS回路(1ビット) 文献 K8 P + Key Scheduling M8 Round K9 Key Scheduling + M9 Round K10 + による攻撃 仮定:暗号化処理中のテーブル参照出力をリセットさせた暗号文を入手 結果:128個の正規,故障暗号文対で秘密鍵導出可能 • Giraud による攻撃 仮定:暗号化処理中の特定のバイト中1ビットが反転した暗号文を入手 結果:50個以下の正規,故障暗号文対で秘密鍵導出可能(故障場所に依存) • Dusart らによる攻撃 仮定:暗号化最終段入力の不特定のバイトにエラーが入った暗号文を入手 結果:50個以下の正規,故障暗号文対で秘密鍵導出可能 C • Blomer 文献 J. Blomer, J.P.Seifert, “Fault based cryptanalysis of the AES,” (http://eprint.iacr.org/2002/075) C.Giraud, “DFA on AES”, (http://eprint.iacr.org/2003/008) P.Dusart, G.Letourneux, O.Vivolo, “Differential Fault Analysis”, (http://eprint.iacr.org/2003/010) チップが見える状態 SRAM memory むき出し 拡 大 実験装置 SRAM 光 K 光 MP-901& Vivitor550FD S.Skorobogatov, R.Anderson, “Optical Fault Induction Attacks”, CHES2002, LNCS2523, pp2-12, 2002. 拡大 参考:“Optical Fault Induction Attacks”, ) (http://www.ftp.cl.cam.ac.uk/ftp/users/rja14/faultpap3.pdf 4 CRYPTREC評価暗号 電子政府推奨共通鍵暗号リスト発表(平成15年2月20日) “Name” “Name” AES Rijndael Camellia CIPHREUNICORN-A Hierocrypt-3 SC2000 15800 11500 1150 54 77 169 25900 16500 1290 126 89 207 935000 70500 208000 282 128 31600 64bit DES Triple DES 3-key Triple DES CIPHERUNICORN-E Hierocrypt-L1 MISTY1 42800 10800 264 55 85 495 87100 16100 306 59 99 739 208000000 81400 477 92 130 2180 Stream MUGI MULTI-S01 RC4 128-bit RC4 70 49 9720 228 91 59 26700 527 19800 130 305000 7750 Etc. CRYPTREC NESSIE 166 678 198 1030 1220 105000 http://www.soumu.go.jp/s-news/2003/030220_1.html http://www.meti.go.jp/feedback/downloadfiles/i30220ej.pdf ※注意 この調査結果は、機械的な調査結果を述べたものであって、それ以上の意味はありません。 特に、暗号の優劣等を表すものではないことをご注意ください。 “Name” Cipher 128bit 総務省、経済産業省ホームページ 調査: 暗号名(共通鍵)が載ってるWebページ数はどれぐらいある? Google 検査ツール 方法 検索されたヒットページ数を出力 キーワード 1. 暗号名, 2. 暗号名 Cipher, 3. 暗号名 Block (Stream) Cipher, 調査日 2003年4月14日(月) “Name” Block (Stream) Cipher 5