128ビットブロック暗号
CLEFIA
3/2-3/3 2010 応募暗号説明会

堅木 雅宣
ソニー株式会社© 2010 Sony Corporation

はじめに• CLEFIA– 国際会議FSE2007にて発表– 共通鍵ブロック暗号• ブロック長 128ビット• 鍵長128/192/256ビット• AESと同じインターフェース– 設計者• 白井，渋谷，秋下，盛合（ソニー），• 岩田（名古屋大）
2© 2010 Sony Corporation

目次• 技術仕様– アルゴリズム概要– 設計方針• 安全性評価• 実装性能評価• 公開状況等の情報• まとめ3© 2010 Sony Corporation

技術仕様

アルゴリズム概要

4© 2010 Sony Corporation

CLEFIAアルゴリズム概要• 共通鍵ブロック暗号

32 ビット– ブロック長：128ビット– 鍵長：128/192/256ビット

F0F1

F0F1F0F1F0F1• 基本構造– Type-2 一般化Feistel構造 （GFN）• データ処理部, 鍵スケジュール部ともに– ラウンド数：18 (128ビット鍵)22 (192ビット鍵)
26 (256ビット鍵)
5© 2010 Sony Corporation

4系列Type-2一般化Feistel構造

平文

鍵F0F1F0F1DoubleSwap

DoubleSwap：

DoubleSwap：：：

F0F1F0F1DoubleSwap

DoubleSwap

暗号文6© 2010 Sony Corporation

データ処理部

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

DoubleSwap

F 関数• Substitution-Permutation (SP)型

S0
S1S0
S1

S1
S0
S1S07

行列 M01246216446126421

行列 M1182a81a2
2a18a281

F0F1F0

F1F0

F1F0F1F0F1© 2010 Sony Corporation

技術仕様

設計方針

8

© 2010 Sony Corporation

設計方針（1/2）• 背景– 現リスト選定以降の暗号解析技術の進歩– 実装制約の厳しい環境への実装ニーズ• 動機
128ビットブロック暗号の設計：
最新の設計解析技術をもちいて，「実用的な暗号に求められる３つの基本要素」のバランスをさらに追究する

実装コスト

9

© 2010 Sony Corporation

安全性速度

設計方針（2/2）• 主な特長1. 全体構造： 一般化Feistel構造•

コンパクトなF関数の実現

2. Ｆ関数： 拡散行列切り替え法（ＤＳＭ）•

差分・線形攻撃への耐性向上

3. 鍵スケジュール部：一般化Feistel構造•

関連鍵攻撃への耐性向上

4. 各コンポーネント：効率的な実装が可能•
10

安全性だけでなく実装性も十分考慮© 2010 Sony Corporation

１．全体構造：一般化Feistel構造の採用
Feistel
FF

FF

FF

F

FFFF

F

一般化Feistel構造の特徴

11

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

２．F関数：拡散行列切り替え法 (DSM)• 拡散行列切り替え法の採用– DSM：Diffusion Switching
Mechanism– Feistel typeの構造において,複数の拡散行列を組み合わせることにより差分/線形攻撃への耐性を高める手法

M0M1M0

M1M0

M1M0

M1

• 必要なラウンド数の削減に成功– CLEFIAの場合• DSMなし：１６ラウンド• DSMあり：１２ラウンド
12© 2010 Sony Corporation

M0,M1:拡散行列

３．鍵スケジュール部 ：一般化Feistel構造
128ビット鍵:

12ラウンド
F0

F0

F0

F0F1

F1F1

F1

DoubleSwap

RK0 ,..,RK3

DoubleSwap

RK4 ,..,RK7

DoubleSwap

RK8,..,RK11DoubleSwap

RK12 ,..,RK15

DoubleSwap

RK16 ,..,RK19

DoubleSwap
RK20 ,..,RK23
一般化Feistel構造•データ処理部と共有可能•関連鍵攻撃に対する耐性を向上:128ビット中間鍵
13

ラウンド鍵

© 2010 Sony Corporation::4. 各コンポーネント• 効率的な実装を考慮したコンポーネント

14© 2010 Sony Corporation

安全性評価15© 2010 Sony Corporation

自己評価
既知の攻撃について網羅的に安全性評価を実施
••
•
•
•
•
•
•
•
•
16差分攻撃線形攻撃
差分線形攻撃Boomerang攻撃
Amplified Boomerang攻撃
Rectangle 攻撃Truncated 差分攻撃
Truncated 線形攻撃
不能差分攻撃
飽和攻撃

••
•
•
•
•
•
•
•
•

Gilbert-Minier Collision攻撃
高階差分攻撃補間攻撃
XSL/代数攻撃
χ2/Statistical攻撃
スライド攻撃関連暗号攻撃関連鍵攻撃
関連鍵Boomerang攻撃
関連鍵Rectangle攻撃© 2010 Sony Corporation

外部評価• 第三者評価（CLEFIA設計時）– 下記研究者に安全性評価を依頼．問題ないことを確認• Prof. Alex Biryukov• Prof. Vincent Rijmen• Prof. Serge Vaudenay• ABT(Prof. Lars R. Knudsen and Prof. Bart Preneel)• 攻撃論文（CLEFIA発表後）– 不能差分攻撃（段数を減らしたCLEFIAに対して）– 現時点でフルラウンドCLEFIAに対する安全性上の懸念点は指摘されていない
17© 2010 Sony Corporation

実装性能評価18© 2010 Sony Corporation

ソフトウェア実装性能• 12.9cycles/byte, 1.48Gbpsを達成* CPU:AMD Athlon 64 processor 4000+ (2.4GHz)
Windows XP 64-bit Edition上で動作. コードはアセンブラ実装.

19© 2010 Sony Corporation

ハードウェア実装性能• ASICで5Kgate以下で実装可能• ゲート当たりの速度で高い性能

20© 2010 Sony Corporation

ハードウェア実装性能（参考）18033-3 128ビットブロック暗号とのハードウェア実装比較 (ASIC,180nm)
4000

Throughput(Mbps)

3500
3000
2500

CLEFIAAESCamellia
SEED2000
1500
1000
500
0020406080

Area (Kgates)
T. Sugawara, N. Homma, T. Aoki, and A. Satoh, “ASIC Implementations of the 128-bit Block Cipher CLEFIA." inProceedings of Computer Security Symposium 2007 (CSS2007), pp. 175-180, 2007. (in Japanese)© 2010 Sony Corporation

公開状況等の情報

22© 2010 Sony Corporation

公開情報等（1/3）• CLEFIA website– www.sony.co.jp/clefia– CLEFIAに関する技術情報（公開資料，関連論文リスト）等を公開

23© 2010 Sony Corporation

公開情報等（2/3）• 国際会議– Fast Software Encryption 2007
• T. Shirai, K. Shibutani, T. Akishita, S. Moriai, T. Iwata, “The 128-bitBlockcipher CLEFIA.” FSE 2007, LNCS 4593, pp. 181-195,Springer-Verlag, 2007.

• 標準化– ISO/IEC JTC 1/SC27 下記に提案中• ISO/IEC 29192 – Information technology –Security techniques –Lightweight cryptography – Part 2: Block ciphers– IETF Internet draftとして提出• M. Katagi, S. Moriai, “The 128-bit Blockcipher CLEFIA”, October19,
2009. http://tools.ietf.org/html/draft-katagi-clefia-00
24© 2010 Sony Corporation

公開情報等（３/３）• バージョン情報– CLEFIA のアルゴリズム仕様はこの暗号技術仕様書の記載で一意に定められ，他のバージョンは存在しない．
– CLEFIA は，同一の名称，かつ同一の仕様で発表および応募を行っている．

• ライセンス条件– CLEFIA技術に必須な登録特許又は特許出願について，CLEFIA技術を実施する者(政府機関を含む）に対し， 妥当かつ非差別的な条件で許諾します．

25© 2010 Sony Corporation

まとめ• 128ビットブロック暗号CLEFIA– 安全性• 既存の攻撃法に対して十分な安全性を確認– 実装性能• 高速かつコンパクトな実装が可能• 特に，ハードウェア実装性能では既存暗号に対する優位性が十分期待できる．
安全性

実装コスト
26

© 2010 Sony Corporation速度