A Study on Performance Enhancement of Symmetric-Key Cryptography and its VLSI Implementation Zaldy ANDALES 大阪大学大学院工学研究科情報システム工学専攻 白川研究室.

Presentation on theme: "A Study on Performance Enhancement of Symmetric-Key Cryptography and its VLSI Implementation Zaldy ANDALES 大阪大学大学院工学研究科情報システム工学専攻 白川研究室."— Presentation transcript:

1 A Study on Performance Enhancement of Symmetric-Key Cryptography and its VLSI Implementation
Zaldy ANDALES 大阪大学大学院工学研究科情報システム工学専攻 白川研究室

2 内容 １．序論 ２．暗号方式と暗号モード ３．高速化手法：Burstモード ４．暗号強度の解析 ５．実装結果 ６．結論

3 第１章 １．序論 ２．暗号方式と暗号モード ３．高速化手法：Burstモード ４．暗号強度の解析 ５．実装結果 ６．結論

4 暗号処理の必要性 ネット社会に 溢れる各種情報 保護 付加価値 暗号

5 問題点 暗号解読試行に対する耐性の向上： 暗号強度の向上のみで， 処理速度は変わらない 処理速度の向上： ハードウェア規模が大きい
ブロック暗号に暗号モードを適用する 例: ECB, CBC, CFB, OFB, Counterモード 暗号強度の向上のみで， 処理速度は変わらない 処理速度の向上： 付加的な処理回路を用いる 例: マルチプロセッサによる並列処理 専用アクセラレータ 汎用リコンフィギュラブルロジック ハードウェア規模が大きい

6 目的 高速化暗号モードの設計 Burstモード アルゴリズムの考案 暗号強度の解析 VLSI化設計 暗号処理速度の向上 暗号強度の向上
低ハードウェアコスト Burstモード アルゴリズムの考案 暗号強度の解析 VLSI化設計

7 第２章 １．序論 ２．暗号方式と暗号モード ３．高速化手法：Burstモード ４．暗号強度の解析 ５．実装結果 ６．結論

8 共通鍵暗号方式 同一の鍵を用いて，暗号化，復号化処理を行う 例: DES, IDEA, AES （ブロック暗号）
鍵長が比較的短い（56～256ビット） 演算処理が高速 大量データの暗号化処理に適する 共通鍵 共通鍵 平文 暗号文 平文 暗号化 復号化

9 暗号解読試行 全数探索法 取り得る全ての鍵について検証 鍵の長さに依存 統計/解析的探索法 差分解読法や線形解読法など
解読アルゴリズムに依存 例: DES Challenge III (RSA Data Security Conference, San Jose, California, Jan 18, 1999) - winner: Electronic Frontier Foundation - DES Cracker: supercomputer + 100,000 PCs - Attack speed: 245 Billion keys/sec - Key found in 22 hours15 minutes - award: $10,000　

10 次世代ブロック暗号 1970- 64ビットブロック暗号 - DES, LOKI, IDEA, FEAL, MISTY AES!!!
次世代128ビットブロック暗号 - AES (Advanced Encryption Standard)候補: Rijndael, RC6, Twofish, Mars, Serpent - Japan: E2, Cipherunicorn, Heirocrypt, Camellia 2000- AES!!!

11 Cipher block chaining (CBC)
暗号モード ブロック暗号を変形 平文： ブロック暗号処理 Electronic code book (ECB) P1 P2 共通鍵 E E 暗号文： C1 C2 Cipher block chaining (CBC) Counterモード IV Pi E C1 P1 C2 P2 IV 共通鍵 ストリーム鍵 counter SKi 共通鍵 E Ci IV (Initialization Vector)＝初期化ベクトル ＃ブロック暗号処理 : ＃平文ブロック＝1:1

12 第３章 １．序論 ２．暗号方式と暗号モード ３．高速化手法：Burstモード ４．暗号強度の解析 ５．実装結果 ６．結論

13 第３章. 高速化手法：Burstモード １．設計目標 ２．特徴 ３．構成 Extended Key 生成部
Combination Key 生成部 Stream Key 生成部

14 １．Burstモードの設計目標 高性能 - 速度の向上 暗号強度の向上 - 解読試行に対する耐性 実装効率 - 低ハードウェアコスト
高性能 速度の向上 暗号強度の向上 - 解読試行に対する耐性 実装効率 低ハードウェアコスト 128ビット ブロック暗号に対応 （例： AES）

15 ２．Burstモードの特徴 処理性能の向上するため 計算量の削減 複雑度の向上 暗号強度を向上するため 実装コストを削減するため
Counterモード : 64 ブロック暗号処理 → 64 ストリーム鍵 Burstモード : 16 ブロック暗号処理 → 64 ストリーム鍵 複雑度の向上 ブロック暗号の出力値に対して ランダムな組合わせ と ランダムな攪拌処理 を行う 暗号強度を向上するため 単純な論理演算を用いる: XOR, シフト 実装コストを削減するため

16 ３．全体構成 (1 burst cycle) 64 SKs 64 CK pairs 16 EKs Stage 1 Stage 2
Combination key Initialization vector Extended key Stream key 64 SKs CK/CK’の 組合わせ 64 CK pairs EKの拡張 counter P0 SK0 CK0 Secret Key E0 128bit CK’0 EK0 C0 128bit 128bit CK 生成部 SK 生成部 P1 CK1 E1 SK1 EK1 AES CK’1 128bit C1 16  EK14 EKテーブル ランダム アドレス生成部 128bit CK63 P63 EK 生成部 E15 CK’63 SK63 EK15 128bit 128bit C63 Secret Key 16 EKs

17 Combination Key (CK) 生成部
EKテーブル EKA EK0 EK1 EK15 EK2 EK3 EK14 EK-to-CK 変換部 CKi EKB EKC EKD CK’i EKE EKF EK segment 32 b i 14 b i = 0…63 Pseudo-random Rotation values 18 b ランダム アドレス生成部 6 Pseudo-random EK addresses

18 Combination Key (CK) 生成部
EKテーブル EK segment 128 b EKA EK0 EK-to-CK 変換部 CKi EKB EK1 EKC EKD CK’i EKE EKF EK segment 32 b i 14 b i = 0…63 Pseudo-random Rotation values 18 b EK15 ランダム アドレス生成部 EK segment 63 6 Pseudo-random EK addresses

19 Combination Key (CK) 生成部
EKテーブル EKA EK0 EK-to-CK 変換部 CKi EKB EK1 EKC ランダム アドレス生成部 EKD CK’i EKE EKF EK segment 32 b i 14 b i = 0…63 Pseudo-random Rotation values 18 b EK15 ランダム アドレス生成部 6 Pseudo-random EK addresses

20 Combination Key (CK) 生成部
EKテーブル EKA EK0 EK-to-CK 変換部 EK-to-CK 変換部 CKi EKB EK1 EKC EKD CK’i EKE EKF EK segment 32 b 14 b i = 0…63 Pseudo-random Rotation values 18 b EK15 ランダム アドレス生成部 XOR, シフト 6 Pseudo-random EK addresses

21 EKテーブルランダムアドレス Region 1 Region 2 Region 3 Region 4
EKA EK3 EK4 Region 2 EKC EK7 EK8 Region 3 EKB EK11 EK12 Region 4 EK15 ランダムアドレス（A,B,C）は必ず異なる値をとる

22 全体構成 (1 burst cycle) 64 SKs 64 CK pairs 16 EKs Stage 1 Stage 2 EKの拡張
Combination key Initialization vector Extended key Stream key 64 SKs 64 CK pairs EKの拡張 CK/CK’の 組合わせ counter P0 SK0 CK0 Secret Key E0 128bit CK’0 EK0 C0 128bit 128bit CK 生成部 SK 生成部 P1 CK1 E1 SK1 EK1 AES CK’1 128bit C1 16  EK14 転置関数 巡回シフタ 128bit CK63 EK 生成部 P63 E15 CK’63 SK63 EK15 128bit 128bit C63 Secret Key 16 EKs

23 Stream Key (SK) 生成部 EK0 S0 SK0 CK0 Rev RotL CK’0 S1 SK1 CK1 Rev RotL
64 SKs S63 SK63 CK63 Rev RotL CK’63

24 Stream Key (SK) 生成部 EK0 S0 SK0 CK0 Rev RotL CK’0 S1 SK1 CK1 Rev RotL
X Rev(X) 32 b 128 b 転置関数 64 SKs S63 SK63 CK63 Rev RotL CK’63 Rev - CK = CK’の場合、 XORによる打ち消しを防ぐ

25 Stream Key (SK) 生成部 攪拌 EK0 S0 SK0 CK0 Rev RotL 左可変巡回シフト CK’0 S1 SK1
X <<< Y RotL(X,Y) 各32ビット セグメントの 下位５ビット 左可変巡回シフト 32 b 5 b 128 b CK’0 S1 SK1 CK1 Rev RotL 攪拌 CK’1 64 SKs S63 SK63 CK63 Rev RotL CK’63 RotL - 前の攪拌処理結果からのフィードバックを反映させる - 攪拌性能の向上（SKの衝突防止）

26 第３章 まとめ 高速化手法: Burstモードを考案 処理速度の向上： 暗号強度の向上： 実装コストの削減：
16 回のブロック暗号処理で 64の平文ブロックを暗号化 暗号強度の向上： ブロック暗号の結果に対して攪拌処理を実行 実装コストの削減： 単純な論理演算で構成

27 第４章 １．序論 ２．暗号方式と暗号モード ３．高速化手法：Burstモード ４．暗号強度の解析 ５．実装結果 ６．結論

28 第４章. 暗号強度の解析 １．従来暗号モードとの比較 ２．暗号解読試行に対する耐性 ３．ストリーム鍵 (SK) のランダム性

29 １．従来暗号モードとの比較 マルチレベル強度：３階層 中間鍵攪拌 （SK生成部） 中間鍵拡張（CK生成部） ブロック暗号の
繰り返し（EK生成部）

30 ２．暗号解読試行に対する耐性 A. 差分解読法、線形解読法 B. 相関性解析

31 ２．暗号解読試行に対する耐性 A. 差分解読法、線形解読法
EK テーブル c++ Secret key E0 E1 EK0 EK1 EK8 9  EKA , EKB , EKC EK0 EK8 128 b EK15 EKA , EKB , EKCのうち、少なくとも１つは EK8 - EK15の中から選択される SKを生成するためには、ブロック暗号を少なくとも ９回行う必要がある.

32 ２．暗号解読試行に対する耐性 A. 差分解読法、線形解読法
最大差分確率（DPmax）と最大線形確率（LPmax）により 差分解読法と線形解読法に対する耐性を評価 差分解読法 Burst モードのDPmax = (ブロック暗号の DPmax)9 従来モードの DPmax = (ブロック暗号の DPmax)1 線形解読法 Burst モードのLPmax = (ブロック暗号の LPmax)9 従来モードの LPmax = (ブロック暗号の LPmax)1 Burst mode は、従来モードに対して ９剰倍の暗号強度を実現

33 ２．暗号解読試行に対する耐性 B. ストリーム鍵 (SK)の相関性解析
Generate 16 EKs Form CK pair i SK i IV c CK pair i+1 SK i+1 EKset, i+1 EKset, i Rotation value 20 b CK i CK’ i CK i＋１ CK’ i＋１ EK テーブル SKの相関性解析における問題点： SKi とSKi+1の間に非線形なEKテーブルが存在 SKi から CKi 、CK’i を特定することは不可能 SKの相関性解析のためのデータ量が少ない：64個の SKのみ

34 ３．ストリーム鍵(SK)のランダム性 衝突検証 （Collision Test） 16-b SK 4,096 平均衝突回数：
対象ビット長：１６ビット（ストリーム鍵） セグメント数：４,０９６個 検証回数：４０回 16-b SK 4,096 平均衝突回数： 実験結果：132.4 理想値 ：128 (119  ave 134) Burstモードは理想的なストリーム鍵を 生成することが可能である．

35 第４章 まとめ Burstモードの暗号強度の特徴: マルチレベルの強度 解読試行に対する耐性が高い ストリーム鍵は十分にランダム

36 第５章 １．序論 ２．暗号方式と暗号モード ３．高速化手法：Burstモード ４．暗号強度の解析 ５．実装結果 ６．結論

37 第５章. 実装結果 １．ソフトウェア（SW)実装 ２．ハードウェア（HW）実装 A. Burstモードアクセラレータコア

38 １．ソフトウェア(SW)実装結果 AES 暗号化 スループット （ECB およびBurstモード）
Ave. ECB (Mbps) 114.3 97.7 85.3 99.1 Burst (Mbps) 213.3 196.9 182.9 197.7 Speed-up 1.87 2.02 2.14 2.01 Celeron 600MHz, 128MB memory , Linux, gcc 付加的な回路としては、256Byte のワークメモリのみ必要 Burst モードにより約２倍処理速度向上

39 各種ブロック暗号への適用結果 処理速度 (Mbps) 処理速度 向上比率 300 200 100 AES Mars Twofish RC6
ECBモード 200 Burstモード 処理速度 (Mbps) 100 AES Mars Twofish RC6 Serpent 3 処理速度 向上比率 2.2 2 1 AES Mars Twofish RC6 Serpent

40 ２．ハードウェア(HW)実装 Ａ．Hybrid SW-HW: Stage 1 in SW - Stage 2 in HW
CK’0 c++ Secret key CK0 EK0 EK1 EK14 EK15 CK 生成部 SK0 SK1 SK63 16  SK CK’1 CK1 CK’63 CK63 アクセラレータコア Ａ．Hybrid SW-HW: Stage 1 in SW - Stage 2 in HW Ｂ．HW-HW : Stage 1 in HW - Stage 2 in HW 1チップ化設計

41 A. Hybrid SW-HWアクセラレータコアInput/Output パイプライン処理
Load P Enc Output C ・・・ Load 16 EKs Encrypt 64 Plaintext Blocks 5 cycles 5 cycles 5 cycles 5 cycles 5 cycles Load P0 Encrypt P0  C0 Output C0 Load P1 Encrypt P1  C1 Output C1 Load P2 Encrypt P2  C2 ・

42 アクセラレータコアのブロック図 XOR and 入力 shift circuits Rev RotL 出力 3 selected EKs:
(EKA,EKB,EKC) or (EKD,EKE,EKF) EKテーブル CK生成部 EK0,..,EK15 CK XOR and shift circuits 128 EK from block cipher 入力 128 128 SK生成部 32 128 128 Rev and RotL 32 EKアドレス CK’ EKアドレス 生成部 S EKsegment SK 出力 平文 P 暗号文 C 128

43 暗号化処理(1/5) 1 XOR and 入力 shift circuits Rev RotL EKsegmentiの読出し 出力
3 selected EKs: (EKA,EKB,EKC) or (EKD,EKE,EKF) EKテーブル CK生成部 EK0,..,EK15 CK XOR and shift circuits 128 EK from block cipher 入力 128 128 SK生成部 32 128 128 Rev and RotL 32 EKアドレス CK’ 1 EKアドレス 生成部 S EKsegment EKsegmentiの読出し SK 出力 平文 P 暗号文 C 128

44 EKテーブルよりEKA,EKB,EKC の読出し
暗号化処理(2/5) 3 selected EKs: (EKA,EKB,EKC) or (EKD,EKE,EKF) EKテーブル CK生成部 EK0,..,EK15 CK XOR and shift circuits 128 EK from block cipher 入力 128 128 SK生成部 32 128 2 128 Rev and RotL EKテーブルよりEKA,EKB,EKC の読出し 32 EKアドレス CK’ 1 EKアドレス 生成部 S EKsegment SK 出力 平文 P 暗号文 C 128

45 CK生成部よりCKを生成しレジスタに格納
暗号化処理(3/5) CK生成部よりCKを生成しレジスタに格納 3 selected EKs: (EKA,EKB,EKC) or (EKD,EKE,EKF) EKテーブル CK生成部 EK0,..,EK15 CK XOR and shift circuits 128 EK from block cipher 3 入力 128 128 SK生成部 32 128 2 128 Rev and RotL 32 EKアドレス CK’ 1 EKアドレス 生成部 S EKsegment SK 出力 平文 P 暗号文 C 128

46 EKテーブルよりEKD,EKE,EKFの読出し
暗号化処理(4/5) 3 selected EKs: (EKA,EKB,EKC) or (EKD,EKE,EKF) EKテーブル CK生成部 EK0,..,EK15 CK XOR and shift circuits 128 EK from block cipher 3 入力 128 128 SK生成部 32 128 2 4 128 Rev and RotL EKテーブルよりEKD,EKE,EKFの読出し 32 EKアドレス CK’ 1 EKアドレス 生成部 S EKsegment SK 出力 平文 P 暗号文 C 128

47 暗号化処理(5/5) 3 2 4 1 5 XOR and 入力 shift circuits Rev RotL 出力 CK’の生成
3 selected EKs: (EKA,EKB,EKC) or (EKD,EKE,EKF) EKテーブル CK生成部 EK0,..,EK15 CK XOR and shift circuits 128 EK from block cipher 3 入力 128 128 SK生成部 32 128 2 4 128 Rev and RotL 32 EKアドレス CK’ 1 EKアドレス 生成部 S EKsegment SK 出力 平文 P CK’の生成 SKの生成 暗号文Cの生成 暗号文 C 128 5

48 アクセラレータコアの実装結果 SW AESの４倍の処理速度を実現 ゲート数 54.6K 最大動作周波数 66.7MHz 最大スループット
1.32Gbps テクノロジ 0.35 m CMOS 3LM 供給電圧 3.3V コアサイズ 3.7 x 3.7 mm2 I/O ピン 32-bit in/ 32-bit out Cadence Virtuoso, Synopsys Design Compiler, Avant! Apollo SW AESの４倍の処理速度を実現

49 B. １チップ化実装結果 1.9倍の回路規模で， HW AESの2.2倍の処理速度を実現 AESをハードウェアで実装した場合 HW AES
HW AES + Burstモードコア ゲート数 69.4K 133.6K 最大動作周波数 66.7MHz 66.7MHz 最大スループット 0.60Gbps 1.32Gbps 1.9倍の回路規模で， HW AESの2.2倍の処理速度を実現

50 第５章 まとめ AES 暗号化 スループット vs Platform (Stage1-Stage2) ECB Burstモード
第５章 まとめ AES 暗号化 スループット Platform vs (Stage1-Stage2) ECB Burstモード Cost, Speed-up SW SW Additional 256Bytes working memory SW-SW 2.0 x faster Ave. throughput 99Mbps 198Mbps SW SW-AES + HW accelerator Gates 54.6K SW-HW Additional 54.6K gates Max. clock freq. 66.7MHz 4.0 x faster Max. throughput (0.33Gbps) 1.32Gbps HW HW 93% increase in gates Gates 69.4K 133.6K HW-HW Max. clock freq. 66.7MHz 66.7MHz 2.2 x faster Max. throughput 0.60Gbps 1.32Gbps

51 第６章 １．序論 ２．暗号方式と暗号モード ３．高速化手法：Burstモード ４．暗号強度の解析 ５．実装結果 ６．結論

52 第６章. 結論 高性能暗号モード （Burstモード）の考案 Burstモードにより，暗号強度と処理速度の向上を低コストで実現可能
暗号処理速度の向上 16回のブロック暗号で64ブロックの平文を暗号化 暗号強度の向上 マルチレベル暗号処理により、解読試行に対する高い安全性 低ハードウェアコスト SW実装： 256Byteのメモリ HW実装： 55KGatesのBurstモードアクセラレータコア Burstモードにより，暗号強度と処理速度の向上を低コストで実現可能

53

54 質疑応答 ・ 鍵配送はどのようにするのか： 公開鍵暗号利用 ・ 暗号強度の向上とは？ 数値的には？ 何と比較して向上？ 他のモードと比較？
・ メリット，デメリットは？ ・ 本当に解読できないのか？ ・ 回路規模はデメリットということか？