...

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

by user

on
Category: Documents
14

views

Report

Comments

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
Fly UP