講演内容 共通鍵暗号の標準化 標準化動向 － ブロック暗号

講演内容
中央大学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最終選考レポート（１）
選考暗号
種類 暗号名
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最終選考レポート（２）
非選考暗号
種類 暗号名
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
１．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/)
２．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)
３．Cache 攻撃
４．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