CLEFIA_ISEC発表

Size: px

Start display at page:

Download "CLEFIA_ISEC発表"

あいりすえがら
7 years ago
Views:

1 128 ビットブロック暗号 CLEFIA 白井太三渋谷香士秋下徹盛合志帆岩田哲ソニー株式会社名古屋大学

2 目次背景アルゴリズム仕様設計方針安全性評価実装性能評価まとめ 2

3 背景 AES プロジェクト開始 (1997~) から 10 年 AES プロジェクト攻撃法の進化代数攻撃関連鍵攻撃新しい攻撃法への対策暗号設計法の進化 IC カード, RFID などのアプリケーション拡大制約条件の厳しい環境下でも実装可能なブロック暗号のニーズ 3

4 設計の動機最新の研究成果, 設計手法によりどこまで安全かつ小さく高速な 128 ビットブロック暗号を設計できるか? 安全性実装コスト速度 4

5 CLEFIA のアルゴリズム仕様共通鍵ブロック暗号ブロック長 :128 ビット鍵長 :128/192/256 ビット基本構造 Type-2 一般化 Feistel 構造 (GFN) データ処理部, 鍵スケジュール部ともにラウンド数 :18 (128 ビット鍵 ) 22 (192 ビット鍵 ) 26 (256 ビット鍵 ) 5

6 Type-2 一般化 Feistel 構造 4 系列 32 ビット 6

7 データ処理部スケジュール部7 鍵鍵スケジュール部鍵 ( ラウンド数を削減した ) データ処理部 : : : : 部平文暗号文

8 F 関数 SP 型 S0 S1 S0 S1 行列 M S1 S0 S1 S0 行列 M a 8 1 a 2 2 a 1 8 a

9 設計方針全体構造一般化 Feistel 構造拡散行列 DSM: Diffusion Switching Mechanism の利用 S-box 異なる代数構造に基づくコンパクトな S-box 鍵スケジュール部安全性とコンパクト実装が両立可能 9

10 Feistel vs. 一般化 Feistel F F F F F F F F F F F F 10 一般化 Feistel 構造の特徴 F 関数のサイズが小さい複数の F 関数が同時に実行できる多くのラウンド数が必要拡散行列切り替え法 (DSM) により削減可能

11 拡散行列切り替え法 (DSM) DSM:Diffusion Switching Mechanism [SS04,SP04,SS06] Feistel 構造において, 複数の拡散行列を組み合わせることにより差分 / 線形攻撃への耐性を高める手法 M 0 : MDS 行列, M 1 : MDS 行列でかつ M 0 M 1 : MDS 行列となるように設計 M 0 M 0 M 1 M 1 M 0 *MDS: Maximum Distance Separable M 0 11

12 DSM の効果差分 / 線形攻撃に対する耐性の向上隣接するラウンド関数間の difference cancellation / linear mask cancellation を防止同じラウンド数の差分 / 線形特性に含まれる Active S-boxの最少個数が多くなることを保証できる必要な総ラウンド数を削減可能 CLEFIAのケースでは25% ラウンド数が削減 12

13 DSM の効果 ( 最小 active S-box 数の比較 ) 従来技術 DSM 適用時, D: 差分, L: 線形ラウンド数 CLEFIA の場合 28 個以上 active s-box が必要. 従来技術では最低 16 ラウンド必要だった. DSM を用いることで 12 ラウンドで達成. 13

14 2 種類の S-box S 0 S 1 SS 0 SS SS 1 SS 8 3 f x - 1 in GF(2 8 ) g 4 ビット S-box ベース使用例 :Whirlpool, FOX f, g: GF(2) 上 affine 変換 GF(2 8 ) 上逆元関数ベース使用例 :AES, Camellia 異なる代数構造代数攻撃系への耐性向上 2 種類の S-box の利用 ( 配置も考慮 ) 飽和攻撃 (Saturation Attack) 等への耐性向上 14

15 鍵スケジュール部 (128 ビット鍵 ) 128 ビット鍵 12 ラウンド : ラウンド鍵 RK 0,..,RK 3 RK 4,..,RK 7 RK 8,..,RK ビット中間鍵 RK 12,..,RK 15 関数 RK 16,..,RK bit 57bit 7 RK 20,..,RK 23 : : : 57bit bit

16 鍵スケジュール部一般化 Feistel 構造データ処理部と共有可能関連鍵攻撃に対する耐性を向上関数シンプルなビット置換演算ながら攪拌効果大暗号化時も復号時も同じ処理でラウンド鍵生成最終ラウンドから第 1 ラウンドへ戻るのも容易 16

17 安全性評価差分攻撃線形攻撃差分線形攻撃 Boomerang 攻撃 Amplified Boomerang 攻撃 Rectangle 攻撃 Truncated 差分攻撃 Truncated 線形攻撃不能差分攻撃飽和攻撃 Gilbert-Minier Collision 攻撃高階差分攻撃補間攻撃 XSL/ 代数攻撃 χ 2 /Statistical 攻撃スライド攻撃関連暗号攻撃関連鍵攻撃関連鍵 Boomerang 攻撃関連鍵 Rectangle 攻撃 17

差分攻撃線形攻撃 4 ビット S-box ベース GF(2 8 ) 上逆元関数ベース S-box 最大差分確率最大線形確率 S 0 2-4.

385 S 1 2-6 2-6 差分特性 : 12 ラウンド中に 28 個の active S-box 最大差分特性確率 2-4.

18 差分攻撃線形攻撃 4 ビット S-box ベース GF(2 8 ) 上逆元関数ベース S-box 最大差分確率最大線形確率 S S 差分特性 : 12 ラウンド中に 28 個の active S-box 最大差分特性確率 = 線形特性 : 12 ラウンド中に 30 個の active S-box 最大線形特性確率 = ラウンド CLEFIA をランダム置換と識別するために有効な差分 / 線形特性は存在しない 18

19 DSM の効果 ( 最小 active S-box 数の比較 ) 従来技術 DSM 適用時, D: 差分, L: 線形ラウンド数 128-bit key 192-bit key 256-bit key 19

20 不能差分攻撃現在 CLEFIA に対して最も有効な攻撃 Kim らによる探索アルゴリズムを用いて 2 つの 9 ラウンド不能差分パスを発見 9r (0, α, 0, 0) (0, α, 0, 0) と (0, 0, 0, α) (0, 0, 0, α) 但し α {0, 1} 32 はあらゆる非ゼロの差分値 9r 20

21 :12 ラウンド各種関連鍵攻撃鍵スケジュール部を強固にすることで防御 Step.1 一般化 Feistel 構造により中間鍵 L を生成 Step.2 中間鍵を関数で攪拌させながらもとの鍵 K とラウンド定数をマスクしてラウンド鍵を生成鍵 K ラウンド鍵 RK 0,..,RK 3 RK 4,..,RK 7 RK 8,..,RK 11 RK 12,..,RK 15 RK 16,..,RK 19 RK 20,..,RK 23 中間鍵 L : : : 21

22 各種関連鍵攻撃一般化 Feistel 構造 (GFN) 128 ビット鍵 : 12 ラウンド 4 系列 GFN 192/256 ビット鍵 : 10 ラウンド 8 系列 GFN あらゆる ΔK から ΔL への遷移確率が十分小さくなるようにラウンド数を決定ラウンド定数鍵長によって異なるラウンド定数のセットを用いることでスライド攻撃や関連暗号攻撃を防御 22

23 Type-2 一般化 Feistel 構造 8 系列 32 ビット 23

24 ハードウェア実装性能 ASIC で 5Kgate 以下で実装可能 * 面積当たり速度で AES を上回る最高性能 ** * 0.09μmCMOS 標準セルライブラリ使用 ** 使用 ASIC ライブラリの差 (0.09μm, 0.13μm) を考慮した公平な比較のために CLEFIA の性能を 1.5 で割っても. 24

25 高速コンパクト H/W 実装への寄与点一般化 Feistel 構造小さな F 関数逆関数が不要 DSM によりラウンド数を削減データ処理部と鍵スケジュールが共有可能各パーツが非常にコンパクト拡散行列 ( 遅延も小さい ) S-box 関数 25

26 ソフトウェア実装性能 Athlon64 上で 12.9cycles/byte, 1.48Gbps を達成 * AMD Athlon 64 プロセッサ (2.4GHz) を使用し, Windows XP 64-bit Edition 上で動作. コードはアセンブラ実装. 26

27 ソフトウェア実装性能 S-box 参照回数は AES より少ないものの, データ依存性が高い. AES: 160 回, CLEFIA: 144 回 2 ブロック並列実装では依存性は低減. * AMD Athlon 64 プロセッサ (2.4GHz) を使用し, Windows XP 64-bit Edition 上で動作. コードはアセンブラ実装. 27

28 まとめ 128ビットブロック暗号高速かつコンパクトな実装が可能を提案ハードウェア実装 : 単位ゲートあたりの速度において最高記録を達成ソフトウェア実装 :128ビットブロック暗号において最も高速なグループ既知の暗号解読法に対する安全性を確認安全性実装コスト速度 28

Microsoft PowerPoint - 6-盛合--日文.ppt

Microsoft PowerPoint - 6-盛合--日文.ppt CLEFIA Sony s s Lightweight Block Cipher Shiho Moriai Sony Corporation 1 目次ソニーにおける暗号技術ソニーのブロック暗号 :CLEFIA 設計の背景アルゴリズム仕様設計方針実装性能評価まとめ 2 ソニーにおける暗号技術暗号 / 情報セキュリティ技術搭載製品の増加各種暗号アルゴリズム著作権保護機器認証電子マネー