128ビットブロック暗号 CLEFIA
白井 太三† 渋谷 香士† 秋下 徹†
盛合 志帆† 岩田 哲††
†
ソニー株式会社
†† 名古屋大学
© 2007 Sony Corporation
目次
•
•
•
•
•
•
2
背景
アルゴリズム仕様
設計方針
安全性評価
実装性能評価
まとめ
© 2007 Sony Corporation
背景
• AESプロジェクト開始(1997～)から10年
AESプロジェクト
攻撃法の進化
・代数攻撃
・関連鍵攻撃
…
新しい攻撃法への対策
暗号設計法の進化
ICカード, RFIDなどの
アプリケーション拡大
・制約条件の厳しい環境下でも
実装可能なブロック暗号のニーズ
3
© 2007 Sony Corporation
設計の動機
• 最新の研究成果, 設計手法により どこまで安全かつ
小さく、高速な128ビットブロック暗号を設計できるか?
安全性
実装コスト
4
速度
© 2007 Sony Corporation
CLEFIAのアルゴリズム仕様
• 共通鍵ブロック暗号
– ブロック長：128ビット
– 鍵長：128/192/256ビット
• 基本構造
– Type-2 一般化Feistel構造 (GFN)
• データ処理部, 鍵スケジュール部ともに
– ラウンド数：18 (128ビット鍵)
22 (192ビット鍵)
26 (256ビット鍵)
5
© 2007 Sony Corporation
Type-2 一般化Feistel構造
32 ビット
6
F0
F1
F0
F1
F0
F1
F0
F1
© 2007 Sony Corporation
４系列
平文
鍵
F0
F1
F0
F1
DoubleSwap
(ラウンド数を
削減した)
データ処理部
DoubleSwap
：
DoubleSwap
：
：
：
F0
F1
F0
F1
DoubleSwap
DoubleSwap
暗号文
7
© 2007 Sony Corporation
データ処理部
鍵スケジュール部
DoubleSwap
F 関数
• SP型
S0
S1
S0
S1
S1
S0
S1
S0
8
行列 M0
1246
2164
4612
6421
行列 M1
182a
81a2
2a18
a281
F0
F1
F0
F1
F0
F1
F0
F1
F0
F1
© 2007 Sony Corporation
設計方針
• 全体構造
– 一般化Feistel構造
• 拡散行列
– DSM: Diffusion Switching Mechanism の利用
• S-box
– 異なる代数構造に基づくコンパクトなS-box
• 鍵スケジュール部
– 安全性とコンパクト実装が両立可能
9
© 2007 Sony Corporation
Feistel vs. 一般化Feistel
F
F
F
F
F
F
F
F
F
F
F
F
一般化Feistel構造
の特徴
10
• F 関数のサイズが小さい
• 複数のF 関数が同時に実行できる
• 多くのラウンド数が必要
拡散行列切り替え法(DSM)
© 2007 Sony Corporationにより削減可能
拡散行列切り替え法 (DSM)
• DSM：Diffusion Switching
Mechanism [SS04,SP04,SS06]
• Feistel構造において,複数の拡散
行列を組み合わせることにより
差分/線形攻撃への耐性を高める
手法
M0: MDS行列, M1: MDS行列 でかつ
M0| M1: MDS行列となるように設計
*MDS: Maximum Distance Separable
11
© 2007 Sony Corporation
M0
M0
M1
M1
M0
M0
DSMの効果
• 差分/線形攻撃に対する耐性の向上
– 隣接するラウンド関数間の difference
cancellation / linear mask cancellation を防止
– 同じラウンド数の差分/線形特性に含まれる
Active S-boxの最少個数が多くなることを
保証できる
– 必要な総ラウンド数を削減可能
• CLEFIAのケースでは25%ラウンド数が削減
12
© 2007 Sony Corporation
DSMの効果(最小active S-box数の比較)
従来技術
DSM適用時, D:差分, L:線形
ラウンド数
CLEFIAの場合、
28個以上active
s-boxが必要.
従来技術では最低
16ラウンド必要だった.
DSMを用いることで
12ラウンドで達成.
13
© 2007 Sony Corporation
2種類のS-box
S0
S1
SS0
8
SS1
⎛1 2⎞
⎜⎜
⎟⎟
2
1
⎝
⎠
SS2
f
x-1 in
GF(28)
g
8
SS3
f, g: GF(2)上 affine 変換
・４ビットS-boxベース
使用例：Whirlpool, FOX
・GF(28)上逆元関数ベース
使用例：AES, Camellia
• 異なる代数構造
– 代数攻撃系への耐性向上
• 2種類のS-boxの利用（配置も考慮）
– 飽和攻撃(Saturation Attack)等への耐性向上
14
© 2007 Sony Corporation
鍵スケジュール部 (128ビット鍵)
128ビット鍵
:
12ラウンド
F0
F0
F0
F1
F1
F1
DoubleSwap
RK0 ,..,RK3
DoubleSwap
RK4 ,..,RK7
DoubleSwap
RK8,..,RK11
DoubleSwap
RK12 ,..,RK15
DoubleSwap 関数
DoubleSwap
RK16 ,..,RK19
7
57bit
DoubleSwap
F0
57bit
128ビット中間鍵
© 2007 Sony Corporation
7
RK20 ,..,RK23
F1
:57bit
15
ラウンド鍵
7 7
:
57bit
:
鍵スケジュール部
• 一般化Feistel構造
– データ処理部と共有可能
– 関連鍵攻撃に対する耐性を向上
• DoubleSwap関数
– シンプルなビット置換演算ながら攪拌効果大
– 暗号化時も復号時も同じ処理でラウンド鍵生成
– 最終ラウンドから第１ラウンドへ”戻る”のも容易
16
© 2007 Sony Corporation
安全性評価
•
•
•
•
•
•
•
•
•
•
17
差分攻撃
線形攻撃
差分線形攻撃
Boomerang攻撃
Amplified Boomerang攻撃
Rectangle 攻撃
Truncated 差分攻撃
Truncated 線形攻撃
不能差分攻撃
飽和攻撃
•
•
•
•
•
•
•
•
•
•
Gilbert-Minier Collision攻撃
高階差分攻撃
補間攻撃
XSL/代数攻撃
χ2/Statistical攻撃
スライド攻撃
関連暗号攻撃
関連鍵攻撃
関連鍵Boomerang攻撃
関連鍵Rectangle攻撃
© 2007 Sony Corporation
差分攻撃 線形攻撃
４ビットS-box
ベース
GF(28)上
逆元関数ベース
S-box 最大差分確率 最大線形確率
S0
2-4.678
2-4.385
S1
2-6
2-6
• 差分特性: 12ラウンド中に28個のactive S-box
– 最大差分特性確率 ≤ 2-4.678×28 = 2-130.984
• 線形特性: 12ラウンド中に30個のactive S-box
– 最大線形特性確率 ≤ 2-4.385×30 = 2-131.55
• 12ラウンドCLEFIA をランダム置換と識別するために有効な
差分/線形特性は存在しない
18
© 2007 Sony Corporation
DSMの効果(最小active S-box数の比較)
従来技術
DSM適用時, D:差分, L:線形
ラウンド数
128-bit key
192-bit key
256-bit key
19
© 2007 Sony Corporation
不能差分攻撃
• 現在、CLEFIA に対して最も有効な攻撃
• Kimらによる探索アルゴリズムを用いて
２つの９ラウンド不能差分パスを発見
9r
9r
(0, α, 0, 0) → (0, α, 0, 0) と (0, 0, 0, α) → (0, 0, 0, α)
但し α ∈{0, 1}32 はあらゆる非ゼロの差分値
20
© 2007 Sony Corporation
各種関連鍵攻撃
• 鍵スケジュール部を強固にすることで防御
– Step.1 一般化Feistel構造により中間鍵 L を生成
– Step.2 中間鍵をDoubleSwap関数で攪拌させながら
もとの鍵 K とラウンド定数をマスクしてラウンド鍵を生成
鍵K
F0
F0
:
12ラウンド
F1
F1
F0
F1
F0
F1
中間鍵 L
21
ラウンド鍵
DoubleSwap
RK0 ,..,RK3
DoubleSwap
RK4 ,..,RK7
DoubleSwap
RK8,..,RK11
DoubleSwap
RK12 ,..,RK15
DoubleSwap
RK16 ,..,RK19
DoubleSwap
RK20 ,..,RK23
:
© 2007 Sony Corporation
:
:
各種関連鍵攻撃
• 一般化Feistel構造 (GFN)
– 128ビット鍵: １２ラウンド４系列GFN
– 192/256ビット鍵: １0ラウンド8系列GFN
あらゆるΔK からΔL への遷移確率が十分小さく
なるようにラウンド数を決定
• ラウンド定数
– 鍵長によって異なるラウンド定数のセットを用い
ることで、スライド攻撃や関連暗号攻撃を防御
22
© 2007 Sony Corporation
Type-2 一般化Feistel構造
８系列
32 ビット
23
F0
F1
F0
F1
F0
F1
F0
F1
F0
F1
F0
F1
F0
F1
F0
F1
© 2007 Sony Corporation
ハードウェア実装性能
• ASICで5Kgate以下で実装可能*
• 面積当たり速度でAESを上回る最高性能**
* 0.09μmCMOS標準セルライブラリ使用
** 使用ASICライブラリの差(0.09μm, 0.13μm)を考慮した公平な比較のためにCLEFIAの性能を1.5で割っても.
24
© 2007 Sony Corporation
高速・コンパクトH/W実装への寄与点
• 一般化Feistel構造
– 小さな F 関数
– 逆関数が不要
• DSMによりラウンド数を削減
• データ処理部と鍵スケジュールが共有可能
• 各パーツが非常にコンパクト
– 拡散行列(遅延も小さい)
– S-box
– DoubleSwap関数
25
© 2007 Sony Corporation
ソフトウェア実装性能
• Athlon64上で12.9cycles/byte, 1.48Gbpsを
達成
* AMD Athlon 64プロセッサ 4000+ (2.4GHz)を使用し,
Windows XP 64-bit Edition上で動作. コードはアセンブラ実装.
26
© 2007 Sony Corporation
ソフトウェア実装性能
• S-box参照回数はAESより少ないものの,
データ依存性が高い.
– AES: 160回, CLEFIA: 144回
• 2ブロック並列実装では依存性は低減.
* AMD Athlon 64プロセッサ 4000+ (2.4GHz)を使用し,
Windows XP 64-bit Edition上で動作. コードはアセンブラ実装.
27
© 2007 Sony Corporation
まとめ
• 128ビットブロック暗号
を提案
• 高速かつコンパクトな実装が可能
– ハードウェア実装：単位ゲートあたりの速度において
最高記録を達成
– ソフトウェア実装：128ビットブロック暗号において
最も高速なグループ
• 既知の暗号解読法に対する安全性を確認
実装コスト
28
© 2007 Sony Corporation
安全性
速度