Copyright NTT and Mitsubishi Electric Corporation 2000

Camellia: 様々な環境に適した 128 ビットブロック暗号
青木和麻呂 y 市川哲也 z 神田雅透 y
松井充 z 盛合志帆 y 中嶋純子 z 時田俊雄 z

y 日本電信電話株式会社〒 239-0847 神奈川県横須賀市光の丘 1-1

fmaro,kanda,shihog@isl.ntt.co.jp
z 三菱電機株式会社〒 247-8501 神奈川県鎌倉市大船 5-1-1

fichikawa,matsui,june15,tokitag@iss.isl.melco.co.jp
2000 年 7 月 13 日 (翻訳: 2000 年 9 月 22 日)

要旨 本稿では、新しい 128 ビットブロック暗号 Camellia を提案する。 Camellia は、ブロック長が 128 ビット、鍵長が 128/192/256 ビットのいずれかを利用でき、次期米国政
府標準暗号 (AES; Advanced Encryption Standard) のインタフェースに準拠している。

Camellia の特徴は、非常に高い安全性に加えて、ソフトウェアとハードウェアの両面で効率的な実装が可能な点である。まず安全性では Camellia は差分攻撃、線形攻撃に対して十分に安全であることを確認した。また、効率性ではソフトウェア、ハードウェアを問わず、 AES 最終候補暗号 (MARS, RC6, Rijndael, Serpent, Two sh) と比較して同程度以上の暗号化速度を実現している。アセンブラ言語による最適化された実装では、

Pentium III (800MHz) 上で 276 Mbps 以上の暗号化速度を実現できる。これは、最適化された DES 暗号よりもはるかに高速である。
さらに、特筆すべき点はハードウェアの小型実装であり、暗号化回路と復号回路の両方を有するハードウェアを約 11K ゲートで実現できる。この大きさは、我々が知る限りにおいて、 128 ビットブロック暗号の中でもっとも小さいものである。

Copyright NTT and Mitsubishi Electric Corporation 2000
もくじ
1

はじめに

1

2

設計指針

3

2.1 F 関数 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :2.2 P 関数 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :2.3 置換表 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :2.4 F L 関数と F L01 関数 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :2.5 鍵スケジュール : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

3
3
3
4
4

実装評価

6

3.1
3.2

6
8

3

4

11

効率的なソフトウェア実装法

4.1
4.2
4.3
5

: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :ハードウェア実装 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :ソフトウェア実装: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11データ撹拌部 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13
一般的な注意事項 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20
準備部

22

ハードウェア実装評価

5.1 Type 1: 高速実装 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22
5.2 Type 2: 小型実装 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23
5.3 Type 3: 小型実装 (FPGA への適用に特化した場合) : : : : : : : : : : : : : : : : : : 25
6

安全性

27

6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9

27
29
30
30
31
31
32
32
33

: : : : : : : : : : : : : : : : : : : : : : : :丸め差分攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :丸め線形攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :不能差分利用攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :ブーメラン攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :高階差分攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :補間攻撃と線形和攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :等価鍵不存在性 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :スライド攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :差分攻撃および線形攻撃に対する安全性i

Copyright NTT and Mitsubishi Electric Corporation 2000

7

6.10 関連鍵攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.11 統計量情報による評価 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.12 実装攻撃 (サイドチャネル攻撃) : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.13 ブルートフォース攻撃 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

33
33
33
34

まとめ

36

ii

Copyright NTT and Mitsubishi Electric Corporation 2000

1

はじめに

日本電信電話株式会社 (以下では NTT と略す) と三菱電機株式会社 (以下では三菱電機と略す) が共同で開発した 128 ビットブロック暗号 Camellia を提案する。 Camellia では、ブロック長が 128 ビット、鍵長が 128 または 192 または 256 ビットであり、次期米国政府標準暗号 (以下 AES; Advanced

Encryption Standard) のインタフェースに準拠している。また、設計目標は以下のとおりである。
高い安全性

最近の暗号解読技術の進展には目を見張るものがある。このため、差分攻撃 [BS93] や線形攻撃 [M94] に代表される強力な暗号解読技術に対する安全性を定量的に評価することが新しい暗号を設計する上で必要不可欠なことであると考えられている。我々は、最新の暗号解読技術を利用して Camellia の安全性を評価し、 20128 以上の確率を有するような差分特性や線形特性が Camalliaには存在しないことを確認した。さらに、それら以外の攻撃法、例えば高階差分攻撃 [K95, JK97]、
補間攻撃 [JK97, A00]、関連鍵攻撃 [B94, KSW96]、丸め差分攻撃 (truncated di erential attacks)[K95, MT99]、ブーメラン攻撃 [W99]、スライド攻撃 [BW99, BW00] などに対しても安全であるように設計されている。
さまざまなプラットフォーム上での高い効率性

暗号システムはさまざまなアプリケーションで必要となるので、暗号アルゴリズムは幅広いプラットフォーム上で効率的に実装できることが望まれる。
しかし、ソフトウェアとハードウェアの両面に適した 128 ビットブロック暗号アルゴリズムは数少ない。 Camellia は、さまざまなプラットフォーム上での処理速度とともに、ハードウェアでのゲート数やスマートカードでの使用メモリ量などを考慮して、ハードウェアとソフトウェア両面できわめて効率的な実装が可能となるように設計されている。

Camellia は、幅広いプラットフォーム上で効率的な実装が可能である 8 ビット入出力置換表 (s-box)と論理演算から構成されている。このため、低機能 IC カードで利用されている 8 ビット CPU から、PC で広く使われている 32 ビット CPU、さらには 64 ビット CPU まで、ソフトウエアで効率的な実装が可能である。また、 Camellia では、ソフトウェア実装に主眼を置いて設計されたいくつかの 128
ビットブロック暗号で広く使われている 32 ビット加算演算と乗算演算は使用しなかった。なぜなら、これらの算術演算は、 Pentium II/III や Athlon のような特殊なプラットフォーム上では高速に実行されるが、それ以外のプラットフォームでは高速な処理とはいえず、また、ハードウェア実装においては、長いクリティカルパスを構成し、かつ回路規模が大きくなる原因ともなるためである。

Camellia の置換表はハードウェア規模が最小になるように設計してある。つまり、 4 つの置換表
は GF(28 ) 上の逆数関数のアフィン変換によって構成され、さらにその逆数関数はいくつかの GF(24 )1Copyright NTT and Mitsubishi Electric Corporation 2000
上の演算によっても実現できる。これにより、置換表をより少ないゲート数で実装することが可能となっている。
鍵スケジュールは非常に簡単な構造を有し、暗号化処理の一部分を共用している。また、動的 (on-the- y) な副鍵生成が可能であり、そのとき暗号化・復号を問わず同じ効率で副鍵が生成される。副
鍵生成のためのメモリ使用量も極めて小さく、 128 ビット鍵では約 32 バイトの RAM、また 192 ビット鍵と 256 ビット鍵では約 64 バイトの RAM 使用量で実装できる。
NTT と三菱電機は、 ISO 国際標準化を目的とした ISO/IEC JTC 1/SC 27 からの公募に対し Camellia を提案している。また、 NESSIE (New European Schemes for Signature,
Integrity, and Encryption) プロジェクトに対しても安全性の高い暗号要素として Camellia を提案す
将来の標準化活動

る予定である。
本稿の構成

本稿の構成は以下のとおりである。第 2 章で Camellia の設計方針を、第 3 章で実装結果のまとめを述べる。第 4 章でソフトウェア実装における高速化手法を、第 5 章でハードウェア実装
評価方法をそれぞれ示す。第 6 章で既知の攻撃に対する Camellia の安全性を述べる。最後に、第 7章で本稿のまとめを記す。

Camellia の仕様については、別稿「Camellia 仕様書 { 128 ビットブロック暗号」を参照のこと。
また、本稿中での定義や表記は「Camellia 仕様書」の記述に従っていることにも注意されたい。

2

Copyright NTT and Mitsubishi Electric Corporation 2000

2

設計指針

2.1

F 関数

Camellia のラウンド関数 (以下 F 関数) の設計指針は、 E2 の F 関数の設計指針 [KMA+ 98] を踏襲している。 E2 と Camellia との主要な差異は、ラウンド関数の構造を 2 段換字置換網 (SPN; Substitution-Permutation Network) から 1 段換字置換網に変更した点である。 1 段換字置換網構造をFeistel 暗号のラウンド関数に利用したとき、差分特性確率や線形特性確率の上界値による理論的評価
はより複雑になるものの、差分攻撃や線形攻撃に対する実際の安全性が同じ程度としたときの暗号化
処理速度が改善されると期待される。この安全性評価については第 6 章で詳細を記しているので、そちらを参照されたい。
2.2

P 関数

Camellia の線形変換関数 (以下 P 関数) の設計方法は、 E2 の P 関数の設計方法 [KMA+ 98] を踏襲している。すなわち、実装効率性の観点から排他的論理和演算 (XOR) のみで構成され、また差分攻撃や線形攻撃に対する安全性の観点から分岐数 (branch number) が最良となるような線形変換関数を P 関数の候補としている。さらに、 8 ビット CPU での実装のほか、 32 ビット CPU [AU00] および高機能 IC カードでの高速なソフトウェア実装方法を考慮して、上記の候補の中から 1 つの P 関数を選択した。
2.3

置換表

高い安全性およびハードウェア小型化の観点から、 GF(28 ) 上の逆数関数をアフィン変換した関数を利用して置換表を構成した。

GF(28 ) 上の関数における最大差分確率の最小値は 206 であることが証明されており、また最大線形確率の最小値も 206 となると予想されている。この 206 となる最良の最大差分確率と最大線形確率を達成する GF(28 ) 上の逆数関数をアフィン変換した関数が存在することから、これらの関数を置換表として採用した。このような置換表でのすべての出力ビットに対するブール多項式での次数は高いので、高階差分攻撃によって Camellia を解読することは困難である。また、 GF(28 ) 上の逆数関数の入出力において実行される 2 つのアフィン関数によって置換表の GF(28 ) 上での表現が複雑になり、補間攻撃も効率的ではなくなる。さらに、 4 つの異なる置換表を作ることによって、丸め差分攻撃 [MT99] に対する安全性が多少改善される。

ハードウェアの小型設計において、 GF(28 ) 上の要素は部分体 GF(24 ) 上の係数の多項式としても表現することができることから、 GF(24 ) 上の演算を何回か行うことによって置換表を実装すること3

Copyright NTT and Mitsubishi Electric Corporation 2000が可能である [MIYY88]。また、 GF(28 ) 上の逆数関数の入出力において実行される 2 つのアフィン関数によって置換表の GF(24 ) 上での表現も複雑になる。
2.4

FL 関数と FL01 関数

F L 関数と F L01 関数は、構造の同型性を崩すために Feistel 構造の 6 段ごとに挿入される。このような関数を挿入する目的の 1 つは、現在知られていない攻撃に対する防護を図ることである。 Feistel 構造の同型性が有する特徴のひとつに、暗号化処理と復号処理が副鍵の挿入順序を除いて同じ処理となっている点が挙げられる。そこで、 Camellia は F L 関数と F L01 関数とを 6 段ごとに挿入するものの、上記の特性を損なわないようにしている。

F L 関数とその逆関数である F L01 関数の設計指針は、 MISTY の F L 関数の設計指針を踏襲している [M97]。 MISTY と Camellia との差異は、 1 ビット循環シフトを加えたことである。これは、Camellia に対するバイト単位での暗号解読を難しくすることを意図すると同時に、ハードウェア規模や処理速度に対して負の影響が出ないようにするためのものである。これらの関数の設計方針は、固定された鍵に対しては (固定された) 線形変換になる一方で鍵の値によってその変換方法そのものが変わるようにすることである。すなわち、鍵が固定されている限り、これらの関数は (固定された)線形変換となるので、平均差分確率や平均線形確率を大きくすることはない。さらに、論理積、論理
和、排他的論理和 (XOR)、および循環シフトという論理演算によって構成されているので、ソフトウェアでもハードウェアでも高速な処理となっている。
2.5

鍵スケジュール

鍵スケジュールの設計指針は以下のとおりである。

1. 簡単な構成であり、さらに暗号化・復号の処理の一部分を共用できること。
2. 128 ビット鍵、 192 ビット鍵、 256 ビット鍵すべてについて副鍵生成回路が同様の鍵スケジュー
ル回路で実行できること。さらに、 128 ビット鍵での鍵スケジュールはその回路の一部分を利用して実現できること。

3. 副鍵生成時間は暗号化処理時間よりも短いこと。
1 つの秘密鍵で大量のデータを暗号化する場合には鍵セットアップ時間はあまり重要ではないかもしれない。しかし、秘密鍵が頻繁に変更されるようなアプリケーションでは鍵軽快性 (keyagility) が重要となる。鍵軽快性の基本的要素の一つが副鍵生成時間である。
4. 動的 (on-the- y) 副鍵生成が可能であること。
4

Copyright NTT and Mitsubishi Electric Corporation 2000
5. 動的 (on-the- y) 副鍵生成時に、暗号化用の副鍵生成と復号用の副鍵生成の両方が同じ効率で計算できること
いくつかの暗号では、暗号化用の副鍵生成と復号用の副鍵生成とが異なるものがある。また、

Rijndael [DR98] や Serpent [ABK98] などのように、暗号化用の副鍵は逐次的に生成できるが、復号用の副鍵は最終の暗号化用副鍵から逆順に生成しなければならないような暗号もある。

6. 等価鍵が存在しないこと。
7. 関連鍵攻撃やスライド攻撃ができないこと。
指針 1 と 2 は主にハードウェアの小型実装を目的とした項目であり、指針 3、 4 および 5 は実際のアプリケーションにおける優位性を持たせるための項目である。指針 6 および 7 は安全性に関する項目である。
副鍵生成のために必要となるメモリ量は非常に小さい。 128 ビット鍵での Camellia の実装では、
秘密鍵 KL 用の 16 バイト (=128 ビット) と中間鍵 KA 用の 16 バイト (=128 ビット) との合計 32 バ
イトが必要なメモリ量である。同様に、 192 ビット鍵および 256 ビット鍵の実装では合計 64 バイト必要となる。

5

Copyright NTT and Mitsubishi Electric Corporation 2000

3

実装評価

3.1

ソフトウェア実装

現状のソフトウェア実装結果を表 1に示す。この表から Camellia は低機能 IC カード、 32 ビット、および 64 ビットプロセッサいずれでも効率よく実装できることがわかる。表中では 106 を M (mega)、

1003 を m (milli) と略記した。

この表は「点」の情報しか与えていないことに注意されたい。つまり、速度は遅くなるが、利用メ
モリ量が少なくなるようなプログラムも作成可能であること意味している。将来的には「連続」的な情報も示されるかもしれない。
最適化の度合プログラム作成時には第 4章で示した方法を使うよう努力した。しかしながら、全ての組合せを実験する時間がなかったので、ここに示されている数値はおそらく最適ではない。
もし、アセンブリ言語の実装が存在すれば通常それを使うので、 C 言語実装は重要でないと考えた。さらに、 C プログラムを最適化するときは以下に示すような手順を実行することになり、 C プ
ログラムの最適化は C コンパイラをリバースエンジニアすることにほかならない。
Step 1: C プログラムを作成、又は修正。
Step 2: C コンパイラによりアセンブリ言語を生成。
Step 3: もし、生成されたアセンブリ言語が適切でなければ Step 1に戻る。
Step 4: 実行時間を計測し、満足できなければ Step 1に戻る。

上に示したように、 C プログラムを最適化するときはコンパイラによってどのようなアセンブリ言語が生成されるか推測することになる。この手順は効率が悪く意味がないと考えられるので、 C プログ
ラムの最適化は行なわなかった。
どう速度計測するか

最近のプロセッサで速度計測するのは難しい。何故ならば、キャッシュの状態など制御が難しく速度に影響する要素がたくさんあるためである。我々は、速度計測にあたり、以下の状態などを仮定した。

 全てのプログラムやデータは適切にワード境界等に配置されている。
 暗号文と平文とプログラムは 1 次キャッシュに読み込まれている。
 分岐予測が当たっている。
 動的副鍵生成実装を除く、準備部関数は副鍵依存の定数を秘密鍵から生成し、その定数は暗号化又は復号関数で利用される。

6

Copyright NTT and Mitsubishi Electric Corporation 2000

表 1: Camellia のソフトウェア実装の性能

CPU

言語

時間a

鍵長

動的メモリbプログラムc表d(ビット) 準備部e (f ) 暗号化g (h ) 準備部e 暗号化g 準備部e 暗号化g

P IIIi アセンブリ 128
192
256
P IIj ANSI Ck 128
Alphal アセンブリ 128
192
256
128
8051m アセンブリ 128

160 (4.4M) 371 (242M)
222 (3.2M) 494 (181M)
226 (3.1M) 494 (181M)
263 (1.1M) 577 (67M)
118 (5.7M) 339 (252M)
176 (3.7M) 445 (192M)
176 (3.7M) 445 (192M)
158 (4.2M) 326 (262M)
0 (0)10217 (10m)

28
28
28
44
48
48
48
48

36
36
36
64
48
48
48
48

1,046
1,469
1,485
1,600
1,132
1,668
1,676
1,600

0

32

0

2,150 8,224
3,323 8,240
3,323 8,240
3,733 4,128
3,076 16,528
4,000 16,528
4,000 16,528
2,928 16,512
702

288

a 準備部や暗号化で必要なサイクル数。
b 動的に使われるメモリのバイト数。通常 RAM に配置される。スタックを含み、平文・暗号文・鍵を除く。
c プログラム規模のバイト数。しばしば ROM に配置される。
d 置換表の大きさのバイト数。しばしば ROM に配置される。
e 鍵スケジュールが含まれる場合もある。
f 8051 では秒、その他では毎秒鍵。
g Camellia は暗号化と復号の処理が対称であるので、この欄の数字は復号も同じ。
h 8051 では秒、その他では毎秒ビット。
i IBM PC/AT 互換 PC, インテル Pentium III (700MHz), ダイ (die) 上の L2 キャッシュ 256KB, FreeBSD 4.0R,

主記憶 128MB。
j IBM PC/AT 互換 PC, インテル Pentium II (300MHz), L2 キャッシュ 512KB, マイクロソフト Windows 95,
主記憶 160MB。
k マイクロソフト Visual C++ 第 6 版。使用最適化オプション: /G6 /Zp16 /ML /Ox /Ob2
l コンパック Professional Workstation XP1000, Alpha 21264 (667MHz), Compaq Tru64 UNIX 4.0F, 主記憶2GB。
m Unix 上のインテル 8051 (12MHz; 1 サイクル = 12 振動周期 (oscillator periods)) シミュレータ。

7

Copyright NTT and Mitsubishi Electric Corporation 2000

 動的副鍵生成実装を除く、暗号化または復号関数はブロック数の整数倍を暗号化又は復号する。
 キャッシュ外しやその他の制御不能要素を排除するため、何回も時間計測し最適なものを選んだ。

 大きなブロックの暗号化時間を 1 ブロックあたりに平均した。但し、この数値は繰り返し処理
や関数呼び出しの時間も含む。
3.2

ハードウェア実装

表 4 〜 表 7 に、 Camellia (128 ビット鍵) の ASIC (Application Speci c Integrated Circuit) 及
び FPGA (Field Programmable Gate Array) 上でのハードウェア実装評価結果を示す。ここでのハードウェア設計及び評価環境は次の表 2のようになっている。

表 2: ハードウェア設計及び評価環境 (ASIC, FPGA)(ASIC, FPGA) Verilog-HDL
シミュレータ (ASIC, FPGA) Verilog-XL
デザイン (ASIC) 三菱電機 0.35m CMOS ASIC ライブラリ
ライブラリ (FPGA) Xilinx XC4000XL シリーズ
論理合成 (ASIC) Design Compiler バージョン 1998.08
ツール(FPGA) Synplify バージョン 5.3.1 及び ALLIANCE バージョン 2.1i
記述言語

ここでは三つのタイプの回路 (Type 1 〜 Type 3) について評価を行った。それらの各タイプの回路の主な設計目標を表 3に示す。

表 3: ハードウェア設計方針 (概要)タイプ

主な設計方針Type 1 暗号化 (復号) 処理において高速実装を実現する
Type 2総回路規模において小型実装を実現する
Type 3
同上 (FPGA への適用に特化した場合)
各回路タイプの詳細については第 5章を参照のこと。

8

回路概要
図1
図2
図3

Copyright NTT and Mitsubishi Electric Corporation 2000

表 4: ハードウェア実装評価結果 (Type 1: 高速実装 [ASIC(0.35m CMOS)])暗号
アルゴリズム名 Enc.&Dec.a

DES
Triple-DES

42,204
124,888

MARS
RC6
Rijndael
Serpent
Two sh690,654741,641
518,508
298,533
200,165

Camellia

216,911回路規模 [Gate]

鍵セットアッ クリティカ スループット

Key expan.b Total logicc プタイム [ns] ルパス [ns]d12,201
23,20754,405
128,147

2,245,096 2,935,754
901,382 1,643,037
93,708612,834
205,096503,770
231,682
431,857
55,907

272,819[Mb/s]||

55.11
157.091161.31407.401740.992112.2657.39
114.0716.38

567.49627.5765.64
137.40324.80225.55203.96
1950.03931.58394.0824.36

109.351170.55a 暗号化及び復号回路 (出力レジスタを含む)
b 鍵拡大回路 (副鍵レジスタを含む)
c 総回路規模 (ファンアウト調整用バッファを含む)
d 暗号化 (または復号) 回路のクリティカルパス (図 1参照)

表 5: ハードウェア実装評価結果 (Type 2: 小型実装 [ASIC(0.35m CMOS)])暗号
アルゴリズム名 Enc.&Dec.a

Camellia

6,367

回路規模 [Gate]

鍵セットアッ クリティカ スループット

Key sched.b Total logic c プタイム [ns] ルパス [ns]d4,979

11,350a 暗号化及び復号回路 (出力レジスタ及びデータセレクタを含む)
b 鍵スケジュール回路 (副鍵レジスタ及び鍵拡大回路の一部を含む)
c 総回路規模 (ファンアウト調整用バッファを含む)
d 暗号化 (または復号) 回路のクリティカルパス (図 2参照)

9

110.2

27.67

[Mb/s]
220.28

Copyright NTT and Mitsubishi Electric Corporation 2000

表 6: ハードウェア実装評価結果 (Type 2: 小型実装 [FPGA(XC4000XL series)])
暗号

回路規模 [CLBs] クリティカ スループット

アルゴリズム名

Total

ルパス [ns]a[Mb/s]

Camellia

1,296

78.81577.34

a 暗号化 (または復号) 回路のクリティカルパス (図 2参照)

表 7: ハードウェア実装評価結果 (Type 3: 小型実装 [FPGA(XC4000XL series)])
暗号

回路規模 [CLBs] クリティカ スループット

アルゴリズム名

Total

ルパス [ns]a[Mb/s]

Camellia874

49.957122.01a 暗号化 (および復号) 回路のクリティカルパス (図 3参照)

10

Copyright NTT and Mitsubishi Electric Corporation 2000

4

効率的なソフトウェア実装法

この章では、 Camellia をソフトウェアで効率的に実装する方法を説明する。ほとんどの場合、プロ
グラムは準備部 (鍵スケジュールを含む) とデータ撹拌部 (暗号化又は復号) の 2 つの部分から構成される。まず準備部の最適化法を説明し、次にデータ撹拌部の最適化法を説明する。
この章では、 8、 32、 64 ビットプロセッサ向けの特別な方法も説明する。しかしながら、 8 ビッ
トプロセッサ向けの最適化法は 32 や 64 ビットプロセッサにも適用可能であり、 32 ビットプロセッ
サ向けの最適化法は 64 ビットプロセッサにも適用可能である。他の語長も必要に応じて考慮されたい。
この章では、まず Camellia が仕様通りに実装されていると仮定している。その後、その実装をどう最適化するかについて論じる。
この章では語長は対象プロセッサの自然な大きさを指す。例えば MMX なしの IA-32 では 32 ビット、 MMX ありの IA-32 や Alpha では 64 ビットを指す。
4.1
4.1.1

準備部
全ての副鍵の記憶

もし、十分にメモリがあれば、一旦生成した副鍵をメモリに保存し、データ撹拌部でそれを利用す
る。
4.1.2

副鍵の生成順序

副鍵は必ずしも利用される順に生成しなくてもよい。例えば、 128 ビット鍵の場合、まず KL に依存する副鍵だけを生成し、次に KA のみに依存する副鍵を生成する。そうすれば、 KA を保持しておくためのレジスタか、またはメモリを節約することができる。
4.1.3

鍵スケジュール中の排他的論理和による相殺

Camellia の鍵スケジュールは Feistel 構造に基づいている。 2 段目と 3 段目の間で KL が中間値と排他的論理和される。この構造は KL の相殺を引き起こす。正確には、 3 段目の入力は以下の式により計算できる。

8< (右半分) = F (KLL ; 61 ): (左半分) = F (KLR 8 (右半分); 62 )8< (右半分) = KRR 8 F (KLL 8 KRL ; 61 ): (左半分) = KRL 8 F (KLR 8 (右半分); 62 )11

128 ビット鍵
192 ビット鍵と 256 ビット鍵

Copyright NTT and Mitsubishi Electric Corporation 2000
上式を用いれば、 128 ビット鍵の場合は 3 回、 192 または 256 ビット鍵の場合は 2 回の L 上の排他的論理和を仕様通りの実装法に比べて削減することができる。
4.1.4

KL, KR , KA, KB の循環ビット数

副鍵生成時に、 KL , KR , KA , KB について、循環シフトした値を保持しておけば元の値を保持しておく必要はない。副鍵はこの保持した値を 16
4.1.5

6 1 の和だけ循環シフトすれば生成できる。

k11 と k12 から kl5 と kl6 の生成

192 と 256 ビット鍵では、 (kl5 ; kl6 ) は (k11 ; k12 )<<<32 に等しいので (k11 ; k12 ) から (kl5 ; kl6 ) の生
成にワード処理の循環シフトを利用できる。この事実を用いると、一般的な循環シフト方法に比べて、数命令削減できる。
4.1.6

動的副鍵生成副鍵は動的に生成することが可能である。全ての副鍵は KL , KR , KA , KB のいずれかを循環シフトしたものである。従って、最初に KL , KR , KA , KB を生成し、次にそれらを循環シフトすればよい。 KL , KR , KA , KB の循環シフトビット数については、第 4.1.4章を参照のこと。
4.1.7

128 ビット鍵と 192・ 256 ビット鍵

もし、 128 ビット鍵より長い鍵長が不要であるならば KB を生成する必要はない。つまり、最後の2 つの F 関数の計算を省略することができる。
4.1.8

Q 上の元をどう循環シフトするか

8 ビットプロセッサ

第 4.1.4章に述べたように、循環シフト量の合計は 16

6 1 の倍数の和である。

16 6 1 ビット循環シフトは 2 バイト移動の後に 1 ビットシフトすることにより実現できるので、 Q 上の元の循環シフトは効率的に実装できる。
32 ビットプロセッサ

もし IA-32 上の実装ならば、倍精度シフト命令である shrd や shld の利用を考慮されたい。
4.1.9

F 関数

鍵スケジュールは F 関数を含んでいるが、 F 関数は主にデータ撹拌部で用いられる。第 4.2章を参
照のこと。

12

Copyright NTT and Mitsubishi Electric Corporation 2000
4.1.10

鍵依存関数

Camellia は排他的論理和と論理和と論理積の 3 つの鍵依存命令を使っている。もし可能であるな
らば、これらの命令に対する自己書き換えプログラムの利用も検討されたい。
4.2
4.2.1

データ撹拌部
Endian 変換

Camellia は big endian を基本に構成されている。従って、 little endian などの big endian でない
プロセッサでの実装は endian 変換のためのちょっとしたプログラムの追加が必要である。
もっとも安易な実装法としてはメモリからレジスタに読み込むときと、レジスタからメモリに書き出す際に endian 変換を行なう方法がある。しかしながら、 F L 関数と F L01 関数のみが endian に依存している。より正確には、 F L 関数や F L01 関数中の 1 ビット循環シフトのみが endian 依存である。つまり、副鍵生成法を適切に調整すれば、 endian 変換を 1 ビット循環シフトとその直後に行
なえばよい。 1 ビット循環シフトと endian 変換を組み合わせた計算を行なうと Camellia の性能を向上できるかもしれない。この方針については、第 4.2.2章に詳細を記した。
いくつかのプロセッサは endian 変換のための特別な命令を持っている。例えば、 80486 以降の IA-

32 は bswap を具備している。これらの命令を使用されたい。但し [C98, Appendix A] に書いてある
endian 変換方法は使ってはいけない。この方法によりプログラム規模は小さくなるが、メモリ読み込
みや書き込みは遅延が大きいので高速にならない。
上に記した様に、 endian の問題は 32 ビットワードの 1 ビット循環シフトのみに影響する。従って、

64 ビットワード全ての endian 変換をする必要はない。
以下に 32 ビットレジスタ x に対する一般的な endian 変換法を示す。下記の方法で、式中の + の代わりに [ や 8 を、また、適切に mask 定数を変換すればシフトや循環シフトと論理和の計算順序を変換できることに注意されたい。
真正直な方法x(x 24 ) + ((x \ 0xff00) 8 ) + ((x 8 ) \ 0xff00) + (x 24 )この方法は並列度が高い。
循環シフトを使わない場合の命令数最小の方法

xx(x 16 ) + (x 16 )((x \ 0xff00ff) 8 ) + ((x 8 ) \ 0xff00ff)
13

Copyright NTT and Mitsubishi Electric Corporation 2000
循環シフトを利用する方法

x((x \ 0xff00ff)>>>8 ) + ((x<<<8 ) \ 0xff00ff)

Pentium III を含むインテルの新しいプロセッサ群は pshufw というデータの並び変えに非常に有効な命令が使える [I99]。 pshufw を使うと 64 ビットデータの endian 変換はわずか 5 命令(ops) で実現できる。
SSE の利用

4.2.2

Little endian 解釈の 1 ビット循環シフト

第 4.2.1章に書いたように、もし F L 関数や F L01 関数中の 1 ビット循環シフトを効率良く実装できるのであれば、平文や暗号文を読み込んだり書き出したりするときの endian 変換は必要ない。
ここで x を 1 ビット循環シフトすべき little endian でデータが格納されている 32 ビット長のレジスタとする。このとき x の 1 ビット循環シフトは以下の式で計算できる。

x((2x) \ 0xfefefefe) + ((x>>>15 ) \ 0xfefefefe)(1)

もちろん、この方法を使うには副鍵生成や他の関数群も適切に修正する必要がある。
式 (1) 中の + は[ または 8 に置き換えてもよく、また、 2x の計算は 1 または <<<1 または x 自身への加算に置き換えてもよい。さらに、適切に mask を変えればシフトや循環シフトと論理和の順
序を入れ換えることができる。

IA-32 の pandn や、 Alpha の bic の様な否定論理積 (ANDNOT) が Camellia を実装しようとしているプロセッサにあるかどうかを確認されたい。この場合は、定数 0xfefefefe を準備する必要はな
い。
4.2.3

初期及び最終排他的論理和 (whitening)

下記の式を用いれば kw2 と kw4 との加算は他の鍵加算に統合できる。

(x 8 k) 8 y = (x 8 y) 8 k;
(x 8 k) 8 l = x 8 (k 8 l);(x 8 k) \ l = (x \ l) 8 (k \ l);(2)(x 8 k)<<<1 = (x<<<1 ) 8 (k<<<1 );(x 8 k) [ l = (x [ l) 8 (k \ l);ここで、 x, y , k , l はビット列とする。この副鍵変換を準備部で行なえば L 上の 2 回の排他的論理和を省略できる。

14

Copyright NTT and Mitsubishi Electric Corporation 2000
4.2.4

副鍵との排他的論理和

式 (2) を用いれば、 S 関数を通過しない範囲で副鍵との排他的論理和の順序を任意の位置に変更できる。例えば、 F 関数の計算を P (S (X8 k)) から P (S (X )) 8 k0 と変更すれば、命令の依存性が改善されるかもしれない。
4.2.5

S 関数

s1 は GF(28 ) 上の四則演算により定義されている。しかしながら、 GF(28 ) 上の演算を計算してはいけない。代わりに事前計算し、その結果をプログラム中に埋め込むべきである。仕様の表 4 を参照のこと。
もし十分なメモリがあり、かつ 8 ビットデータの循環シフトが高コストならば、 s2 , s3 , s4 の表もs1 に加えて事前計算し、プログラムに埋め込むことを強く推奨する。もし、十分なメモリがないのであれば、 s2 , s3 , s4 は s1 の表と 1 回の循環シフトを使って計算されたい。 (仕様の第 4.5 章参照のこと)Java の仮想計算機 (virtual machine) のように表引き処理が重くまた十分なメモリがある環境であれば 2 つの置換表を合成した表、例えば (s1 (y1 ); s2 (y2 )) の利用も考慮されたい。
4.2.6

P 関数

(ZL ; ZR ) = ((z1 ; z2 ; z3 ; z4 ); (z5 ; z6 ; z7 ; z8 )) を P 関数の入力、 (ZL0 ; ZR0 ) =((z10 ; z20 ; z30 ; z40 ); (z50 ; z60 ; z70 ; z80 )) を P 関数の出力とする。
仕様の図 5 から P 関数は以下のように計算できることがわかる。

32 ビットプロセッサZL
ZR

ZL 8 (ZR <<<8 )ZR 8 (ZL <<<16 )ZL

ZL 8 (ZR >>>8 )

ZR
Z0

ZR

L

ZR0

ZR 8 (ZL >>>8 )ZL

15

Copyright NTT and Mitsubishi Electric Corporation 2000
この計算の命令依存性は高い。この計算は以下のように変更できる。

ZR
ZL 8 ZR ZR
ZL >>>8ZR
ZL 8 ZR ZR
ZL <<<8
ZR
ZR
ZR0

ZL
ZL
ZL
ZL
ZL0

ZR <<<8
ZR <<<8
ZR 8 ZLZR <<<16
ZR 8 ZL
ZL

上記計算法の命令依存度は減少している。この方法は 1 回余分な循環シフトを必要とするように見えるが、大抵の場合、最初の計算と S 関数の計算を追加命令なしで同時に計算することができるので、実質的な命令数増加はないであろう。
8 ビットプロセッサ (直交命令系)

もし、排他的論理和が任意のレジスタの組合せで計算でき、十分な数のレジスタがあるならば、仕様の図 5 に書いてある方法で、 P 関数を 16 回の排他的論理和で計算できる。
8 ビットプロセッサ (累算器型)

もし累算器型のプロセッサでの実装を考えている場合、排他的論理

和数を最小化することは必ずしも良い考えとは言えない。何故ならば排他的論理和数を最小化するに当たってメモリからレジスタへの読み込みや、レジスタからメモリへの書き込みが多数必要となることがあるからである。以下の計算は、累算器型プロセッサのために最適化してある。

z80
z0

4

z0

7

z30
z0

6

z20
z0

5

z10

z1 8 z4 8 z5 8 z6 8 z7
z 0 8 z1 8 z2 8 z38z40 8 z2 8 z7 8 z8
z 0 8 z1 8 z2 8 z47z30 8 z1 8 z6 8 z7
z 0 8 z1 8 z3 8 z46z20 8 z4 8 z5 8 z6
z 0 8 z2 8 z3 8 z4
5

もし、 zi0 の添字調整が重い処理の場合は、以下の方法が有効である。

z0
1z1 8 z2 8 z3 8 z4 8 z5 8 z6 8 z7 8 z8
 8 z 2 8 z5

16

Copyright NTT and Mitsubishi Electric Corporation 2000
z20
z0

 8 z 3 8 z6

 8 z 4 8 z7

3

z40
z0

 8 z 1 8 z8

 8 z 3 8 z4 8 z5

5

z60
z0

 8 z 1 8 z4 8 z6

 8 z 1 8 z2 8 z7

7

z80
4.2.7

 8 z 2 8 z3 8 z8

換字置換

この章では S と P を独立に計算するより効率良く P
64 ビットプロセッサ S を計算する方法について論じる。

もし、実装を考えているプロセッサの 1 次キャッシュが十分に大きいのであれば、文献 [RDP+ 96] の方法を使用されたい。この方法では、式 (3) で定義される表を用いる。

SP1 (y1 )SP2 (y2 )SP3 (y3 )SP4 (y4 )
SP5 (y5 )
SP6 (y6 )SP7 (y7 )
SP8 (y8 )

=
=
=
=
=
=
=
=

(s1 (y1 ); s1 (y1 ); s1 (y1 );0; s1 (y1 );0;0; s1 (y1 ))(0; s2 (y2 ); s2 (y2 ); s2 (y2 ); s2 (y2 ); s2 (y2 );0;0)(s3 (y3 );0; s3 (y3 ); s3 (y3 );0; s3 (y3 ); s3 (y3 );0)(s4 (y4 ); s4 (y4 );0; s4 (y4 );0;0; s4 (y4 ); s4 (y4 ))(0; s2 (y5 ); s2 (y5 ); s2 (y5 );0; s2 (y5 ); s2 (y5 ); s2 (y5 ))(s3 (y6 );0; s3 (y6 ); s3 (y6 ); s3 (y6 );0; s3 (y6 ); s3 (y6 ))(s4 (y7 ); s4 (y7 );0; s4 (y7 ); s4 (y7 ); s4 (y7 );0; s4 (y7 ))(s1 (y8 ); s1 (y8 ); s1 (y8 );0; s1 (y8 ); s1 (y8 ); s1 (y8 );0)

次に、以下の式を計算する。

(z0 ; z 0 ; z 0 ; z 0 ; z 0 ; z 0 ; z 0 ; z 0 )1 2 3 4 5 6 7 8

8
M

i=1

この方法の計算量は次の通り。

8
排他的論理和数
7
表の大きさ (KB) 16
表参照回数

17

SPi (yi )(3)

Copyright NTT and Mitsubishi Electric Corporation 2000
もし、プロセッサの 1 次キャッシュがそれなりに大きい場合は、式 (3) で定義される表のいくつかを下記の表に置き換える。

SP (y )SP (y )SP (y )SP (y )====(s1 (y); s1 (y); s1 (y); s1 (y ); s1 (y ); s1 (y); s1 (y); s1 (y))(s2 (y); s2 (y); s2 (y); s2 (y ); s2 (y ); s2 (y); s2 (y); s2 (y))(s3 (y); s3 (y); s3 (y); s3 (y ); s3 (y ); s3 (y); s3 (y); s3 (y))(s4 (y); s4 (y); s4 (y); s4 (y ); s4 (y ); s4 (y); s4 (y); s4 (y))(4)

次に、必要なバイト位置に 0 を埋め込む。もし式 (4) のみを利用した場合は、次の計算量を要する。

8
排他的論理和数7
論理和数
8
表の大きさ (KB) 8
表参照回数

この方法を Alpha アーキテクチャ [C98] 上で実装しており、適切なバイト位置に 0 を埋め込むためのマスク定数を保持するためのレジスタ数が十分でないなら、 zap または zapnot を利用されたい。
もし、利用するプロセッサが IA-32[I99] にある Pentium with MMX technology 以降で採用された punpckldq 命令や、 Pentium II 以降で採用された pshufw 命令の様に、レジスタの半分のビットを残りの半分に効率的に複写できるのであれば、式 (3) 中の SP1 , SP2 , SP3 , SP4 のみを準備する。
そして、以下の式を計算する。

(z10 ; z20 ; z30 ; z40 ; z50 ; z60 ; z70 ; z80 )

4
M

i=1

8
M

SPi (yi ) 8  (i=5SPi04 (yi ));ここで、  は最初の 4 バイトを後の 4 バイトに複写する演算とする。この方法は次の計算量を要する。

8
排他的論理和数
7
 の回数
1
表の大きさ (KB) 8
表参照回数

32 ビットプロセッサ

文献 [AU00] には Camellia 型の換字置換網の効率的な実装法が示されている。

そのうちの一つの方法は、まず次に示す式 (5) を準備する。

SP1110 (y)SP0222 (y)SP3033 (y)SP4404 (y)

=
=
=
=

(s1 (y); s1 (y ); s1 (y );0)( 0; s2 (y ); s2 (y ); s2 (y))(s3 (y);0; s3 (y ); s3 (y))(s4 (y); s4 (y );0; s4 (y))18(5)

Copyright NTT and Mitsubishi Electric Corporation 2000
そして、次の式を計算する。

SP1110 (y8 ) 8 SP0222 (y5 ) 8 SP3033 (y6 ) 8 SP4404 (y7 )D

SP1110 (y1 ) 8 SP0222 (y2 ) 8 SP3033 (y3 ) 8 SP4404 (y4 )U(z 0 ; z 0 ; z 0 ; z 0 )D8U(z 0 ; z 0 ; z 0 ; z 0 ) 8 (U>>>8 )1 2 3 4(z50 ; z60 ; z70 ; z80 )1 2 3 4

この方法は、次に示す計算量を要する。

8
排他的論理和数8
循環シフト数1
表の大きさ (KB) 4
表参照回数

文献 [AU00] は、循環シフト処理が非常に重いプロセッサのための実装法も示している。この方法
では、式 (5) で定義される表に加え次の式で定義される表も準備する。

SP1001 (y)SP2200 (y)SP0330 (y)SP0044 (y)

=
=
=
=

(s1 (y);0;0; s1 (y))(s2 (y); s2 (y );0;0)( 0; s3 (y ); s3 (y );0)( 0;0; s4 (y ); s4 (y))

そして、次の式を計算する。

D(z 0 ; z 0 ; z 0 ; z 0 )1 2 3 4(z50 ; z60 ; z70 ; z80 )SP1110 (y8 ) 8 SP0222 (y5 ) 8 SP3033 (y6 ) 8 SP4404 (y7 )D 8 SP1110 (y1 ) 8 SP0222 (y2 ) 8 SP3033 (y3 ) 8 SP4404 (y4 )D 8 SP1001 (y1 ) 8 SP2200 (y2 ) 8 SP0330 (y3 ) 8 SP0044 (y4 )この方法は次の計算量を要する。

12
排他的論理和数
11
表の大きさ (KB)
8
表参照回数

4.2.8

置換表の引数生成

置換表の引数は単純にシフトと論理積を用いることにより生成できる。しかしながら、いくつかのプロセッサはこの引数を生成するための特別な命令を持っている。例えば、 IA-32[I99] の movzx や、Alpha[C98] の extbl がある。
19

Copyright NTT and Mitsubishi Electric Corporation 2000
P6 で movzx は高速な演算であるが、下位 2 バイトに対してしか用いられない。素朴な方法として
eax, ebx, ecx, edx レジスタを (Lr ; Rr ) の保持に用い、 4 回の循環シフトを毎段実行する実装が考えられる。循環シフトのうち 2 回は、レジスタ中のバイト位置を元に戻すために必要である。しかしながら、もし循環シフトされた表を準備するのであれば毎段のバイト位置を補正するための 2 回の循環シフトを省略できる。この実装法によると、バイト位置は 4 段毎に復帰することに注意されたい。
4.3

一般的な注意事項

この章では、一般的な注意事項について述べる。これらの注意事項は、他のブロック暗号を最適化するのと同様 Camellia の最適化に際しても有効である。より詳しくは、それぞれのプロセッサに対する最適化のための取扱説明書を参照のこと。
データの整列 (align) 整列されていないデータの利用はほとんどのプロセッサにおいて、非常に重い処理である。データはワード境界に整列すべきである。
部分データの利用の回避 ほとんどのプロセッサでは、バイト処理などのワードより小さな大きさを利用するための機能を持っている。しかしながらこの機能はしばしば重い処理となっている。
もし、十分なメモリを使えるのであれば、ワードの大きさが必要でないとしても、ワード利用のみにすべきである。
キャッシュの大きさへの注意 もし、プログラムやデータの大きさがキャッシュの大きさを越えると、実行速度が急激に遅くなる。ループ展開や表展開は高速化のためのよい方法であるが、キャッシュの大きさを越えないよう注意すべきである。
組み込み (intrinsic) 関数の使用 いくつかのコンパイラでは組み込み関数を利用できる。例えば、 IA-

32 上のマイクロソフトの Visual C++ 第 6 版では、「#pragma intrinsic( lrotl)」と宣言
し、「 lrotl」を利用すればコンパイラはアセンブリ言語レベルで循環シフト命令を生成する。
詳細については利用しているコンパイラの取扱説明書を参照のこと。
正確な速度計測は困難 プログラムの実行速度はキャッシュ外しや、 OS 割り込みなどの非常に多くの要因に依存する。さらに、何ブロック暗号化したかなどの暗号学的な要素も実行時間に影響する。
いくつかのプロセッサにはプロセッサ起動時からの経過サイクル数を得る命令がある。例えばPentium 以降の IA-32 は rdtsc 命令があり [I99]、 Alpha には rpcc 命令がある [C98]。この様な命令を速度計測に用いることは良い考えであるが P6 や EV6 の様な非逐次実行 (out-of-order)
アーキテクチャにはそのまま適用してはいけない。

20

Copyright NTT and Mitsubishi Electric Corporation 2000
もし、正確な実行時間を計測したいのであれば適切な案内書を参照されたい。例えば、 Pentium
系のプロセッサについては文献 [F00] を参照のこと。

21

Copyright NTT and Mitsubishi Electric Corporation 2000

5

ハードウェア実装評価

第 3章において、 Camellia(128 ビット鍵) のハードウェア実装評価結果 (ASIC 及び FPGA) を示した。本章では、第 3章で示した 3 タイプの回路の設計方針について述べる。以下に各々のタイプの詳
細を示す。
5.1

Type 1: 高速実装

平文／暗号文

暗号化及び
復号回路部

副鍵レジスタ

暗号化(または復号)のクリティカルパス

Type 1 としては、回路規模に関しては制限を持たせずに、暗号化及び復号処理においてできるだけ高速実装を実現するような場合 (ここでは ASIC) について検討する。図 1は、 Type 1 回路の概要である。表 8に Type 1 回路の基本コンポーネントを示す。

鍵拡大回路部

鍵

鍵拡大のクリティカルパス

出力
レジスタ

暗号文／平文図 1: Type 1 回路の概要 (ASIC)

これらの基本コンポーネントの設計方針を以下に示す。

1. \ 暗号化及び復号回路 " 及び \ 鍵拡大回路 "(a) ループアーキテクチャは採用しない。
(b) パイプラインアーキテクチャは採用しない。
(c) 置換表は人手で最適化せず、論理合成ツールのみを用いて最適化を行う。
第 3章では、その他の暗号アルゴリズム (AES 最終候補暗号、 DES、トリプル DES) の評価結果を示しているが、それらのうちには算術計算 (加算、乗算、その他) を用いるものも含まれて

22

Copyright NTT and Mitsubishi Electric Corporation 2000
表 8: Type 1 回路の基本コンポーネント
暗号化及び組合せ回路より構成された暗号化及び復号回路復号のためのデータ撹拌部回路

出力レジスタ

暗号化 (復号) データのためのレジスタ

鍵拡大回路

組合せ回路より構成された暗号化鍵から副鍵を生成する回路

副鍵レジスタ 鍵拡大回路部の出力データのためのレジスタいる。これらの算術計算に関しては、 Synopsys Design Ware Basic Library [Synopsys (1998)]の中から最も高速なものを用いた場合について示している。

2. \ 出力レジスタ " 及び \ 副鍵レジスタ "(a) 出力レジスタのサイズは一ブロック分 (=128 ビット) とする。
(b) 副鍵レジスタのサイズはアルゴリズム中の全ての副鍵の長さ分とする。
以上の設計方針のもとで、 Camellia とその他のアルゴリズム (AES 最終候補暗号、 DES、トリプル

DES) を ASIC に実装した場合について評価検討を行った。それらの評価結果は第 3章において表 4に示したとおりである。ここで \ スループット (Throughput)" は次の式で定義されるものとする:
スループット [b/s] =5.2

ブロックサイズ (128 [bits])
暗号化 (復号) 回路のクリティカルパス [sec]Type 2: 小型実装

Type 2 としては、暗号化及び復号処理においてできるだけ小型実装を実現するような場合 (ここでは、 ASIC 及び FPGA) について検討する。図 2は Type 2 回路の概要である。表 9に Type 2 回路の基本コンポーネントを示す。
これらの基本コンポーネントの設計方針を以下に示す。

1. \ 暗号化及び復号回路 " 及び \ 鍵スケジュール回路 "(a) ループアーキテクチャを採用する。
(b) パイプラインアーキテクチャは採用しない。
(c) 置換表は設計者の手により最適化の後、論理合成ツールを用いて最適化を行う。
23

鍵

暗号化(または復号)回路のクリティカルパス

平文／暗号文

鍵スケジュール回路

データセレクタ

鍵拡大回路の一部(或は全部)を含む場合あり
一段分の暗号化及び復号回路
副鍵レジスタ

鍵拡大回路のクリティカルパス

Copyright NTT and Mitsubishi Electric Corporation 2000

鍵拡大回路の一部(或は全部)を含む場合あり

出力レジスタ

暗号文／平文図 2: Type 2 回路の概要 (ASIC, FPGA)

表 9: Type 2 回路の基本コンポーネント
暗号化及び組合せ回路から構成され、鍵拡大回路 (の一部) を含む

復号回路

一段分の暗号化及び復号のためのデータ撹拌部回路

出力レジスタ

出力 (および中間処理状態の) データのためのレジスタ

データセレクタ 暗号化 (復号) データまたは出力データを選択するセレクタ
鍵スケジュール 組合せ回路から構成され、暗号化及び復号回路部の中にある回路

鍵拡大回路 (の一部) を用いて副鍵を生成する回路

副鍵レジスタ

鍵スケジュール回路部の出力データのためのレジスタ

24

Copyright NTT and Mitsubishi Electric Corporation 2000(d) 鍵スケジュール回路部は、鍵拡大回路 (の一部) と制御回路から構成される。
2. \ 出力レジスタ "、 \ 副鍵レジスタ " 及び \ データセレクタ "(a) 出力レジスタのサイズは一ブロック分 (=128 ビット) とする。
(b) 副鍵レジスタのサイズは暗号化復号ロジック部で用いられる副鍵のサイズとする。
(c) データセレクタは一ブロック分 (=128 ビット) のセレクタとする。
以上の設計方針のもとで、 Camellia を ASIC 及び FPGA に実装した場合について評価検討を行った。
それらの評価結果は第 3章において表 5 (ASIC) 及び表 6 (FPGA) に示したとおりである。ここで\スループット (Throughput)" は次の式で定義されるものとする:
スループット [b/s] =5.3

ブロックサイズ (128 [bits])
暗号化 (復号) 回路のクリティカルパス [sec]2 ラウンド数

Type 3: 小型実装 (FPGA への適用に特化した場合)Type 3 としては、暗号化及び復号処理においてできるだけ小型実装を実現するような Type 2 における特殊な場合 (全ての副鍵を外部から入力し副鍵全てをメモリに蓄える方式。ここでは FPGA のみに特化) について検討する。図 3は Type 3 回路の概要である。表 10に Type 3 回路の基本コンポー
ネントを示す。
表 10: Type 3 回路の基本コンポーネント
暗号化及び組合せ回路から構成され、鍵拡大回路 (の一部) を含む

復号回路

一段分の暗号化及び復号のためのデータ撹拌部回路

出力レジスタ

出力 (および中間処理状態の) データのためのレジスタ

データセレクタ 暗号化 (復号) データまたは出力データを選択するセレクタ
副鍵メモリ

外部からロードされた副鍵を蓄えるためのメモリ

これらの基本コンポーネントの設計方針を以下に示す。

1. \ 暗号化及び復号回路 "(a) ループアーキテクチャを採用する (一段分の回路をもつ)。
(b) パイプラインアーキテクチャは採用しない。
(c) 置換表は設計者の手によって最適化の後、論理合成ツールを用いて最適化を行う。
25

Copyright NTT and Mitsubishi Electric Corporation 2000

暗号化(または復号)回路のクリティカルパス

平文／暗号文

一段分の
暗号化及び
復号回路

副鍵レジスタ

データセレクタ

副鍵

出力レジスタ

暗号文／平文図 3: Type 3 回路の概要 (FPGA)

2. \ 出力レジスタ "、 \ 副鍵メモリ " 及び \ データセレクタ "(a) 出力レジスタのサイズは一ブロック分 (=128 ビット) とする。
(b) 副鍵メモリのサイズはアルゴリズム内の全副鍵の長さとする。
(c) データセレクタは一ブロック分 (=128 ビット) のセレクタとする。
以上の設計方針のもとで、 Camellia を FPGA に実装した場合について評価検討を行った。それらの評価結果は第 3章において表 7 (FPGA) に示したとおりである。ここで \ スループット (Through-put)" は次の式で定義されるものとする:
スループット [b/s] =ブロックサイズ (128 [bits])
暗号化 (復号) 回路のクリティカルパス [sec]26

2 ラウンド数Copyright NTT and Mitsubishi Electric Corporation 2000

6

安全性

6.1

差分攻撃および線形攻撃に対する安全性

多くのブロック暗号に対する攻撃方法で最もよく知られておりかつ強力なものに Biham と Shamirが提案した差分攻撃 [BS93] と、松井が提案した線形攻撃 [M94] がある。これらの攻撃に対する安全性を評価する手法はいくつかあり、またそれらの間には一種の \ 双対性 " という関係 [M95, CV95]が存在している。つまり、両者の攻撃に対する安全性は同様の方法によって評価することができる。
いくつかのブロック暗号では、何段かの段数における差分活性置換表や線形活性置換表の最少個数を使って、差分特性確率や線形特性確率の上界を評価できることが知られている。神田は、伝統的な

1 段換字置換網 (S 関数 -P 関数) によるラウンド関数を利用した Feistel 暗号の差分活性置換表と線形活性置換表の最少個数を示している [K00]。これ以降、線形変換関数 (P 関数) は全単射であると仮定する。
定義 1 P 関数での分岐数

B を、
B = min(wH (x) + wH (P (x)));x6=0と定義する。ここで wH (x) は x のバイト単位のハミング重みを示す。
定義 2 差分活性置換表とは、非ゼロ入力差分が与えられた置換表のことであると定義する。また、
線形活性置換表とは、非ゼロ出力マスク値が与えられた置換表のことであると定義する。

B + 1 以上で定理 1 任意の連続する 8 段における差分活性置換表・線形活性置換表の最少個数は、 2ある。
定義 3 任意に与えられる 1x, 1y , 0x, 0y

2 GF(2m ) に対して、置換表 si: GF(2m ) ! GF(2m ) の差分確率と線形確率を以下のように定義する。

#fx 2 GF(2m )jsi (x) 8 si (x 8 1x) = 1y g
2mm
#fx 2 GF(2 )jx 1 0x = si (x) 1 0yg
Pr[x 1 0x = si (x) 1 0y] =x2mPr[s (x) 8 si (x 8 1x) = 1y] =x i
定義 4 ps と qs を全ての置換表

fs1; s2 ; : : :g での最大差分確率と最大線形確率であるとする。すなわ

ち、

ps = max max Pr[s (x) 8 si (x 8 1x) = 1y]i 1x=
6 0;1y x i2

qs = max max 2 Pr
[x 1 0x = si (x) 1 0y] 0 1
i 0y =
6 0;0x x27

Copyright NTT and Mitsubishi Electric Corporation 2000
定理 2

D と L をそれぞれ全体の差分活性置換表と線形活性置換表の最少個数であるとする。このとLき、最大差分特性確率と最大線形特性確率はそれぞれ pD
s と qs で抑えられる。

Camellia は S 関数 -P 関数となるラウンド関数を利用している Feistel 暗号であるので、上述した技法により、最大差分特性確率と最大線形特性確率の上界を示すことによって、 Camellia がこれらの攻撃に対する耐性を有することを証明する。

Camellia の場合、置換表の最大差分確率と最大線形確率は
ps = qs = 206
である。また、 P 関数の分岐数は 5、つまり

B=5
である。

p, q をそれぞれ F L 関数と F L01 関数を除いた 16 段に削減した Camellia の最大差分特性確率と最大線形特性確率であるとすると、定理 1と定理 2からB+1) = (206 )22 = 20132 ; q  q2(2B+1) = (206 )22 = 20132p  p2(2ssが得られる。どちらの確率も、 128 ビットブロック暗号の安全性閾値 20128 を下回っている。このことから、 F L 関数と F L01 関数を除いた 15 段を超える段数 (16 段以上) に削減した Camellia には有効な差分特性または線形特性が存在しないことが導かれる。 F L 関数と F L01 関数は、任意の固定された鍵に対して、 (固定された) 線形変換であるので、それらが暗号の平均差分確率や最大線形確率をより大きくすることはない。それゆえ、 Camellia は差分攻撃と線形攻撃に対して十分な安全性を有することが証明される。
上記の結果は、定理 1と定理 2とに基づいていることに注意されたい。両方の定理とも 1 段換字置
換網によるラウンド関数を利用した Feistel 暗号の一般的な場合を対象としているので、実際には、

Camellia は上述した結果で示された安全性よりもさらに安全であると考えられる。そのことを補強する証拠として、我々は段数を削減した Camellia の活性置換表の個数を数えた。個数を数えるためのアルゴリズムは、以下の 3 点を除いて [M99] に記載されたアルゴリズムと同様である。

 遷移確率表の代わりに活性置換表の個数を表した表を準備する
 遷移確率を計算する代わりに活性置換表の個数を数える
 F L 関数と F L01 関数は、表中の全ての要素を活性置換表の最少個数に置き換える。このことは、 F L 関数と F L01 関数の前後の各々の差分特性や線形特性が高い確率、すなわち活性置換28

Copyright NTT and Mitsubishi Electric Corporation 2000

3
4
5
6
7
8
9
10 11 12定理 1と 2による2012 2030
2042
2066
2096
評価
(2) (5)
(7)
(11)
(16)
Camellia
1 206 2012 2042 2054 2066 2072 2072 2078 20108 20120 20132(0) (1) (2) (7) (9) (11) (12) (12) (13) (18) (20) (22)F L/F L01 関数無 1 206 2012 2036 2054 2066 2078 2090 20108 20126 20132(0) (1) (2) (6) (9) (11) (13) (15) (18) (21) (22)
注: () 内の数字は活性置換表の個数である
段数# of rounds
定理 1と 2による

1

表 11: Camellia の差分特性確率の上界

12

表 12: Camellia の線形特性確率の上界

2

3
4
5
6
7
8
9
10 11 12
0
12
0
30
0
42
0
66
2
2
2
2
2096
評価
(2) (5)
(7)
(11)
(16)
Camellia
1 206 2012 2036 2054 2066 2072 2072 2078 20102 20120 20132(0) (1) (2) (6) (9) (11) (12) (12) (13) (17) (20) (22)F L/F L01 関数無 1 206 2012 2036 2054 2066 2078 2084 20108 20120 20132(0) (1) (2) (6) (9) (11) (13) (14) (18) (20) (22)
注: () 内の数字は活性置換表の個数である
表の最少個数と等しくなるように連結する可能性が存在するので、これらの関数を挿入したことによる上記の弱鍵の存在を考慮していることを意味する。
結果として、 F L 関数と F L01 関数を含む 12 段の Camellia は 20128 以上となる確率を有する差分特性および線形特性が存在しないことを確認した。 (表 11と表 12を参照のこと)
6.2

丸め差分攻撃丸め差分 (truncated di erentials) を利用した攻撃は Knudsen によって提案された [K95]。彼は、丸め差分を差分の一部分だけを予測できるような差分であると定義した。この丸め差分の概念は広い
が、バイト単位の暗号ではバイト単位の差分を丸め差分として研究するのが自然である [MT99]。
マルコフ暗号では、差分 (di erential) は同じ入力差分と同じ出力差分をもつ全ての差分特性の集29

Copyright NTT and Mitsubishi Electric Corporation 2000
合であるので、最大差分確率は差分解読法に対する厳密な安全性評価を与えると考えられているが[LMM91]、その値を計算することは一般には不可能である。一方、丸め差分は、解読に利用することができる差分の部分集合とみなすことができる。例えば、バイト単位の暗号などいくつかの暗号では、丸め差分の確率は簡単かつ正確に計算することができ、最大差分特性確率よりも厳密な評価を与えることになる。

E2 の段数削減版に対する丸め差分攻撃は、松井と時田によって FSE'99 で発表された [MT99]。彼らの解読は、バイト内での差分の値を非ゼロとゼロとで区別する \ バイト特性 " を基にしている。結果として、 IT (初期変換) 関数と F T (最終変換) 関数を除いた 8 段の E2 に対して攻撃可能となるような 7 段バイト特性を発見した。文献 [MSAK00] に示すように、 E2 に対する最も優れた攻撃では、
IT 関数または F T 関数のどちらかを含んだ 8 段の E2 を 294 個の選択平文によって解読できる。さらに同じ文献 [MSAK00] で、 IT 関数と F T 関数を含んだ 7 段の E2 を 291 個の選択平文を使ってランダム置換と区別する攻撃も示されている。

Camellia は E2 と同様のバイト単位の暗号であり、丸め差分に対する安全性を評価することは重要である。文献 [MT99, MSAK00] に記述したのと同様のアルゴリズムを使って丸め差分を探索した。
E2 と Camellia とのラウンド関数の大きな相違は、 2 段換字置換網 (つまり S-P-S) ではなく、 1 段
換字置換網を採用したことである。 E2 の丸め差分の探索では、 Feistel 構造の排他的論理和でのバイト単位の差分消失確率として約 208 を利用した。しかし、 Camellia のラウンド関数では第 2 の S 関
数がないため、複数バイトの差分消失確率が時々同時に約 208 になることがある。結果として、 Feistel 構造の排他的論理和での消失ルールを変更することによって、 F L 関数と F L01 関数の有無に関わらず、 10 段を超える (11 段以上の) 段数の Camellia はランダム置換と識別不可能である。
6.3

丸め線形攻撃我々は、丸め線形攻撃と呼ばれる新しい攻撃法を提案した。差分攻撃と線形攻撃の間の双対性により、上記と同様のアルゴリズムを使うことによって丸め線形攻撃に対する安全性を評価できる。具体的には、 P 関数の行列をその転置行列に置き換えることによって探索を実行することができる。結果

として、 F L 関数と F L01 関数を除いた 10 段を超える (11 段以上の) 段数の Camellia はランダム置

換と識別不可能である。
6.4

不能差分利用攻撃

不能差分とは、確率が 0 となる差分もしくは決して存在しない差分のことを意味する。そのような不能差分を使うと、副鍵の候補を狭めることが可能である。全単射のラウンド関数を利用するあらゆ
る Feistel 構造では少なくとも一つの 5 段不能差分が存在することが知られている。 Camellia は (630Copyright NTT and Mitsubishi Electric Corporation 2000
段ごとに F L 関数と F L01 関数が挿入された)Feistel 構造であり、かつラウンド関数が全単射である
ので、 Camellia には 5 段不能差分がある。しかし、我々は 6 段以上の不能差分を見つけることができなかった。さらに、 F L 関数と F L01 関数は鍵の値に応じて差分経路を変化させるため、これらの関数が不能差分を使って Camellia を攻撃することを困難にすると考えられる。したがって、仕様ど
おりの Camellia は不能差分を利用した攻撃法によって破られることはないと考えられる。
6.5

ブーメラン攻撃ブーメラン攻撃は 2 つの差分を利用する [W99]。この 2 つの差分の成立確率を p1 , pr とする。ブーメラン攻撃が全数探索より効率がよいためには

p1 pr  2064(6)が成り立つ必要がある。表 11から F L 関数と F L01 関数を除いた Camellia については、不等式 (6)を満たす組合せがないことがわかる。 F L 関数と F L01 関数を除いた Camellia に対する最適なブーメラン確率の上限は 8 段であり、 3 段 (p1 = 2012 ) と 5 段 (pr = 2054 ) の差分の組合せで抑えられる。 F L 関数と F L01 関数を除いた Camellia の攻撃可能段数は Camellia の仕様である 18 段より極めて少ないので、 Camellia はブーメラン攻撃に対して安全であると考えられる。
6.6

高階差分攻撃高階差分攻撃は、低次のブール多項式として表現可能な暗号に対して一般的に適用可能である。暗号化処理中の全ての中間ビットはブール多項式、すなわち平文のビット

fx1; x2 ; : : : ; xng による多項式 GF(2)[x1 ; x2 ; : : : ; xn ] として表現可能である。文献 [JK97, 定理 1] に記述されている高階差分攻
撃では、もし中間ビットが少なくとも d 次のブール多項式によって表現されているならば、そのブール多項式の d + 1 次差分は 0 になる。

Camellia の置換表のブール多項式の次数に関して考察する。 Camellia では置換表として GF(28 )上の逆数関数とのアフィン等価関数を採用していることに注意せよ。

GF(28 ) 上の逆数関数の各出力ビットのブール多項式の次数が 7 次であることが知られているが、Camellia の置換表の次数は自明ではない。そこで、我々は置換表の各出力ビットのブール多項式を見つけることによって、その次数が 7 次であることを確認した。 Camellia では、暗号化処理中の中間ビットの次数は、データが多くの置換表を通過するにしたがって増加すると期待される。例えば、3 個の置換表を通過した後、次数は 73 > 128 になる。従って仕様どおりの Camellia に対して高階差
分攻撃は成功しないと考えられる。
堀と金子は 1 階差分を使うことによって IT 関数と F T 関数を除いた 5 段 E2 が攻撃可能であることを示した [HK98]。しかし、彼らの攻撃は上述した高階差分攻撃というよりも従来の差分攻撃と同

31

Copyright NTT and Mitsubishi Electric Corporation 2000様であると我々は考える。なぜなら、彼らの技法の主要な点は、ある中間段で非自明な定数となるよ
うな平文と暗号文の組を見つけることにある。言い換えると、攻撃者は差分経路を調べ出すことを意味する。したがって、堀らの攻撃に対する Camellia の耐性は第 6.1章で記述した従来の差分攻撃に対する耐性と同等であると考える。
6.7

補間攻撃と線形和攻撃

文献 [JK97] で提案された補間攻撃は単純な代数的な関数を利用している暗号に対する典型的な攻撃である。
補間攻撃の原理は、大雑把に言うと、もし未知係数の個数が N である平文の多項式または有理表
現として暗号文が表現されるならば、 N 個の平文と暗号文の組を使って、その多項式または有理表
現を構成することができる。一度、攻撃者がその多項式または有理表現を構成すると、攻撃者は鍵を知ることになしに、任意の平文をその鍵に対応する暗号文へ暗号化し、また任意の暗号文を対応する
平文へ復号することが可能である。 N は攻撃複雑度と攻撃に必要な組数を決めるので、 N をできるだけ大きくすることが重要である。もし、攻撃者が N 個の平文と暗号文の組を集めることが現実的でないほど N が大きければ、その暗号は補間攻撃に対して安全である。
線形和攻撃 [A00] は補間攻撃 [JK97] の一般化である。線形和攻撃に対する実用的な安全性評価ア
ルゴリズムが文献 [A00] で提案されている。このアルゴリズムを用い、任意の平文バイトと暗号文バ

イトの GF(28 ) 上の線形和関係を探索した。表 13にその結果をまとめた。

表 13: 128, 192, 256 ビット鍵に対する最小未知係数の数
初期排他的論理和 + r 段 (r < 4)
初期排他的論理和 + 4 段
それ以上の段数

1255
256

表 13によると、 Camellia は補間攻撃を含む線形和攻撃に対して安全なことがわかる。このことは、
文献 [A00, Theorem 3] によると、 Camellia が Square 攻撃 [DKR97] に対しても安全であることを意味している。
6.8

等価鍵不存在性

鍵スケジュールによって生成される副鍵集合には元の秘密鍵を含んでいるので、別の秘密鍵から生成される副鍵集合に等価な集合は存在しない。それゆえ、異なる秘密鍵が多くの平文の各々に対して同じ暗号文に暗号化することになるようなことは存在しないと考えられる。

32

Copyright NTT and Mitsubishi Electric Corporation 2000
6.9

スライド攻撃先駆的研究 [B94, K93] を基にしたスライド攻撃が提案されている [BW99, BW00]。特に、同一のラウンド関数、すなわち全てのラウンド関数が同じ構造かつ同じ副鍵を利用しているような繰り返し
暗号は、スライド攻撃に弱点を有することが示された。

Camellia では、ラウンド間の同型性を崩すために Feistel 構造の 6 段ごとに F L 関数と F L01 関数が挿入されている。さらに鍵スケジュールの観点から、スライド攻撃は非常に成功しにくいと考えられる。 (第 6.10章を参照のこと)
6.10

関連鍵攻撃

Camellia の鍵スケジュールは関連鍵攻撃 [B94, KSW96] を非常に難しくすると考えられる。これらの攻撃では、攻撃者はいくつかの関連鍵を使って暗号化を行うことができなければならない。いってみれば、二つの鍵の間の関係を知っているとすると、副鍵の対応する関係を予測できさえすれば、それらの鍵が異なる平文の組をどのように暗号化するかを予測することが可能になる。しかし、副鍵は秘密鍵及びその暗号化の結果である KA と KB に依存しているので、攻撃者が望んだ副鍵の関係を持つような秘密鍵を得たいとしてもそのような秘密鍵を得ることができない。また逆に、秘密鍵を変えることによって副鍵の関係をコントロールしたり予測することは非常に難しい。
6.11

統計量情報による評価

ほとんどの統計的特性は差分攻撃やその他の暗号学的な攻撃に依存している。例えば平文の 1 ビットを反転させたとき、暗号文の何ビットが反転するかということがよく議論される。差分分布表の定義によれば、差分攻撃に対する耐性から反転ビット数がほぼ半分であることが導ける。もちろん、十分な計算機資源があれば、統計的な弱点を発見できるかもしれない。しかしながら 128 ビットブロッ
ク暗号に対してそのような統計的特性を計算できるほどの計算機資源は構築されていない。
また、次のことに注意されたい。計算機資源の制約から、しばしばラウンド関数に対して統計的性質が調べられる。しかしながら、我々はこのような探索はほとんど意味がないと考える。何故ならば、ラウンド関数に対して統計的に良い性質を満たすが、全体では統計的に良くない性質が存在する暗号を構成することも、また逆に、ラウンド関数に対して統計的に良くない性質があるが、全体では統計的に良い性質を満たす暗号も構成することも可能であるからである。
6.12

実装攻撃 (サイドチャネル攻撃)

時間攻撃 (timing attacks)[K96] や、電力解析攻撃 (power analysis attacks)[KJJ99] によって、十分な安全対策が取られていない実装から秘密情報を取り出すことが可能であることが知られている。

33

Copyright NTT and Mitsubishi Electric Corporation 2000
文献 [DR99] で提案されている分類法を用いると、 Camellia は論理命令と表参照と固定ビット循環
シフトしか用いてないので、有利 (favorable) に分類される。
一方、 Chari らは、全ての AES 候補暗号は電力解析攻撃に対して安全であるかどうか疑わしいと主張している [CJRR99]。これら 2 つの論文が矛盾しているように電力差分攻撃の研究ははじまったばかりなので、この攻撃に対する安全性は不明である。我々は現在の技術を考えると、 Camellia は
ハードウェア技術によって守られるべきであり、仕様からそのまま導ける安全性によっては評価すべきではないと考える。近い将来に電力差分攻撃の研究が進展することを期待する。
6.13

ブルートフォース攻撃

多くのブルートフォース攻撃は任意のブロック暗号に適用可能であり、攻撃複雑度は、攻撃対象の暗号の構造にかかわらず、ブロックサイズと鍵サイズにだけ依存している3 Camellia は 128 ビットのブロックサイズであり、 128 ビット、 192 ビット、 256 ビットの 3 つの鍵サイズを認めている。以下の議論では、 k は鍵のビットサイズを表す。
鍵の全数探索：

鍵の全数探索では、攻撃者は一組の平文と ECB モードで暗号化した暗号文を得ることができるならば、攻撃者は可能な 2k 個全ての鍵について平文を暗号化することによって正しい鍵を発見できる。
暗号の鍵スケジュールの弱点が鍵の全数探索攻撃の効率を改善することがあるが [K94]、 Camellia

ではそのような弱点を我々は発見できなかった。鍵の全数探索の攻撃複雑度は平均約 2k01 回の暗号化であると評価されている。したがって、必要な攻撃複雑度は、 128 ビット、 192 ビット、 256 ビットの鍵それぞれに対して 2127 、 2191 、 2255 の暗号化時間相当となる。それゆえ、鍵の全数探索に対する Camellia の安全性は十分である。
時間メモリトレードオフ攻撃：

平文の中でしばしば使われるいくつかの単語がある。もし、攻撃者がそのような単語で作られる平文ブロックを 2k 個の鍵を使って暗号化し、それらを 2k 個の暗号文に相当するメモリ空間に蓄えていたとすると、攻撃者は、対応する暗号文を得た後、対応する鍵を見つけるために該当する暗号文を探し出すだけでよくなる。この攻撃は表攻撃と呼ばれる。この攻撃では、2k 回の暗号化を終えた後、攻撃時間複雑度が鍵の全数探索の場合よりもはるかに小さくなる。
時間メモリトレードオフ攻撃 [H80, KM96] では、鍵の全数探索で必要とする攻撃時間複雑度と表攻撃で必要とする空間複雑度の両方を劇的に減少させることができる。
3

厳密にいえば、攻撃に必要な計算時間はそのブロック暗号の性能に依存する。しかし、性能は暗号化時間にだけ影響

し、攻撃時間複雑度では無視できる量しか変化しない。

34

Copyright NTT and Mitsubishi Electric Corporation 2000
しかしながら、上記の 2 つの攻撃は、ともに鍵の全数探索の攻撃時間複雑度に等しいだけの事前計算を必要とする。 Camellia が認める鍵サイズは、今日の技術による鍵の全数探索に対して安全であるのに十分な長さである。
辞書攻撃：

辞書攻撃では、攻撃者は同じ鍵を利用した平文と暗号文の組を集め、それらを \ 辞書 "として置いておく。攻撃者は、その鍵で暗号化された暗号文を見つけたときだけ、辞書の中にあるかを調べる。もし辞書の中にあれば、攻撃者はすでに平文を所有していることになる。 Camellia のブ
ロックサイズは 128 ビットであるので、辞書攻撃では、攻撃者が未知の鍵で任意のメッセージを暗号化または復号することを可能にする 2128 個の異なる平文ブロックを蓄積するだけの空間を必要とする。成功確率は辞書空間に依存し、ブロックサイズが大きくなるにつれて、同じ成功確率を達成するのに必要となる空間は指数関数的に増大する。 128 ビットブロック暗号である Camellia は、この攻撃に対して十分安全である。
暗号文一致攻撃：

暗号文一致攻撃では、 ECB モード、 CBC モード、 CFB モードのようないくつかのモード操作に対して、全ての暗号文のおおよそ平方根の個数が利用できるとき、 \ バースデーパ
ラドックス " によっておよそ 12 以上の確率で、同一の暗号文ブロックが存在することが期待できる。

そのとき、平文に関する価値のある情報を得ることができる。この攻撃がブロックサイズに依存することに注意されたい。 Camellia のブロックサイズは 128 ビットであるので、同じ鍵で 264 個と同じぐらい多くのブロックの暗号化を実行することがないならば、この攻撃に対する脅威は小さい。

35

Copyright NTT and Mitsubishi Electric Corporation 2000

7

まとめ

本稿では、 Camellia とその設計指針、ソフトウェアとハードウェア実装に対する適合性、ならびに我々の解析結果を示した。
本稿で示されている性能にはさらなる最適化の余地が残されている。最新の性能結果は、 Camel-lia ホームページ： http://info.isl.ntt.co.jp/camellia/ 上にて更新される。
我々が Camellia を解析した結果、重大な弱点は発見されなかった。この暗号は従来からある設計方針を踏襲しており、 Camellia に対する現実的な攻撃が発見されるためには暗号解読の分野における非常に大きな突破口が必要になるだろう。 Camellia が現存する最良のブロック暗号の安全性と同等の、非常に安全な暗号であると我々は考えている。

36

Copyright NTT and Mitsubishi Electric Corporation 2000
参考文献

[A00] K. Aoki. Practical Evaluation of Security against Generalized Interpolation Attack. IEICE
Transactions Fundamentals of Electronics, Communications and Computer Sciences (Japan),Vol. E83-A, No. 1, pp. 33{38, 2000. (A preliminary version was presented at SAC'99).
[ABK98] R. Anderson, E. Biham, and L. Knudsen. Serpent: A Flexible Block Cipher With
Maximum Assurance. In The First AES Candidate Conference, 1998.
[AU00] K. Aoki and H. Ueda. Optimized Software Implementations of E2. IEICE Transactions
Fundamentals of Electronics, Communications and Computer Sciences (Japan), Vol. E83-A,
No. 1, pp. 101{105, 2000. (The full paper is available on http://info.isl.ntt.co.jp/e2/
RelDocs/).
[B94] E. Biham. New Types of Cryptanalytic Attacks Using Related Keys. Journal of Cryptology, Vol. 7, No. 4, pp. 229{246, 1994. (The extended abstract was appeared at EUROCRYPT'93).
[BS93] E. Biham and A. Shamir. Di erential Cryptanalysis of the Data Encryption Standard.
Springer-Verlag, Berlin, Heidelberg, New York, 1993.
[BW99] A. Biryukov and D. Wagner. Slide Attacks. In L. Knudsen, editor, Fast Software Encryption | 6th International Workshop, FSE'99, Volume 1636 of Lecture Notes in Computer
Science, pp. 245{259, Berlin, Heidelberg, New York, 1999. Springer-Verlag.
[BW00] A. Biryukov and D. Wagner. Advanced Slide Attacks. In S. Vaudenay, editor, Advancesin Cryptology | EUROCRYPT2000, Volume 1807 of Lecture Notes in Computer Science,
pp. 589{606, Berlin, Heidelberg, New York, 2000. Springer-Verlag.
[C98] Compaq Computer Corporation. Alpha Architecture Handbook (Version 4), 1998. (Youcan download the manual from Compaq's technical documentation library: http://www.
support.compaq.com/alpha-tools/documentation/current/chip-docs.html).
[CJRR99] S. Chari, C. Jutla, J. R. Rao, and P. Rohatgi. A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards. In Second Advanced Encryption Standard Candidate
Conference, pp. 133{147, Hotel Quirinale, Rome, Italy, 1999. Information Technology Laboratory, National Institute of Standards and Technology.
37

Copyright NTT and Mitsubishi Electric Corporation 2000
[CV95] F. Chabaud and S. Vaudenay. Links Between Di erential and Linear Cryptanalysis.
In A. D. Santis, editor, Advances in Cryptology | EUROCRYPT'94, Volume 950 of Lecture
Notes in Computer Science, pp. 356{365. Springer-Verlag, Berlin, Heidelberg, New York,1995.
[DKR97] J. Daemen, L. R. Knudsen, and V. Rijmen. The Block Cipher Square. In E. Biham,
editor, Fast Software Encryption | 4th International Workshop, FSE'97, Volume 1267 of
Lecture Notes in Computer Science, pp. 54{68, Berlin, Heidelberg, New York, 1997. SpringerVerlag.
[DR98] J. Daemen and V. Rijmen. AES Proposal: Rijndael, 1998. (http://www.esat.
kuleuven.ac.be/~rijmen/rijndael/).
[DR99] J. Daemen and V. Rijmen. Resistance Against Implementation Attacks. A Comparative
Study of the AES Proposals. In The Second AES Candidate Conference, 1999.
[F00] A. Fog. How to optimize for the Pentium microprocessors, 2000. (http://www.agner.
org/assem/).
[H80] M. Hellman. A Cryptanalytic time-memory trade-o . IEEE Transactions on Information
Theory, Vol. IT-26, No. 4, pp. 401{406, 1980.
[HK98] Y. Hori and T. Kaneko. A study of E2 by higher order di erential attack. Technical
Report ISEC98-38, The Institute of Electronics, Information and Communication Engineers,
1998. (in Japanese).
[I99] Intel Corporation. Intel Architecture Software Developer's Manual (Volume 2: Instruction
Set Reference), 1999. (You can download the manual from Intel's developer site: http://developer.intel.com/).
[JK97] T. Jakobsen and L. R. Knudsen. The Interpolation Attack on Block Cipher. In E. Biham,
editor, Fast Software Encryption | 4th International Workshop, FSE'97, Volume 1267 of
Lecture Notes in Computer Science, pp. 28{40, Berlin, Heidelberg, New York, 1997. SpringerVerlag.
[K93] L. R. Knudsen. Cryptanalysis of LOKI91. In J. Seberry and Y. Zheng, editors, Advancesin Cryptology | AUSCRYPT'92, Volume 718 of Lecture Notes in Computer Science, pp. 196{
208. Springer-Verlag, Berlin, Heidelberg, New York, 1993.
38

Copyright NTT and Mitsubishi Electric Corporation 2000
[K94] L. R. Knudsen. Practically secure Feistel ciphers. In R. Anderson, editor, Fast Software
Encryption 1993 | Cambridge Security Workshop (FSE1), Volume 809 of Lecture Notes in
Computer Science, pp. 211{221, Berlin, Heidelberg, New York, 1994. Springer-Verlag.
[K95] L. R. Knudsen. Truncated and Higher Order Di erentials. In B. Preneel, editor, Fast
Software Encryption | Second International Workshop, Volume 1008 of Lecture Notes in
Computer Science, pp. 196{211. Springer-Verlag, Berlin, Heidelberg, New York, 1995.
[K96] P. Kocher. Timing Attacks on Implementations of Die-Hellman, RSA, DSS, and Other
Systems. In N. Koblitz, editor, Advances in Cryptology | CRYPTO'96, Volume 1109 of
Lecture Notes in Computer Science, pp. 104{113. Springer-Verlag, Berlin, Heidelberg, New
York, 1996.
[K00] M. Kanda. Practical Security Evaluation against Di erential and Linear Attacks for Feistel Ciphers with SPN Round Function. In SAC2000, Seventh Annual Workshop on Selected
Areas in Cryptography, 14-15 August 2000, Workshop Record, 2000.
[KJJ99] P. Kocher, J. Ja e, and B. Jun. Di erential Power Analysis. In M. Wiener, editor,
Advances in Cryptology | CRYPTO'99, Volume 1666 of Lecture Notes in Computer Science,
pp. 388{397. Springer-Verlag, Berlin, Heidelberg, New York, 1999.
[KM96] K. Kusuda and T. Matsumoto. Optimization of Time-Memory Trade-O Cryptanalysis
and Its Application to DES, FEAL-32, and Skipjack. IEICE Transactions Fundamentals ofElectronics, Communications and Computer Sciences (Japan), Vol. E79-A, No. 1, pp. 35{48,1996.
[KMA+ 98] M. Kanda, S. Moriai, K. Aoki, H. Ueda, M. Ohkubo, Y. Takashima, K. Ohta, andT. Matsumoto. A New 128-bit Block Cipher E 2 . Technical Report ISEC98-12, The Instituteof Electronics, Information and Communication Engineers, 1998. (in Japanese).
[KSW96] J. Kelsey, B. Schneier, and D. Wagner. Key-Schedule Cryptanalysis of IDEA, GDES, GOST, SAFER, and Triple-DES. In N. Koblitz, editor, Advances in Cryptology |CRYPTO'96, Volume 1109 of Lecture Notes in Computer Science, pp. 237{251. SpringerVerlag, Berlin, Heidelberg, New York, 1996.

39

Copyright NTT and Mitsubishi Electric Corporation 2000
[LMM91] X. Lai, J. L. Massey, and S. Murphy. Markov Ciphers and Di erential Cryptanalysis.
In D. W. Davies, editor, Advances in Cryptology | EUROCRYPT'91, Volume 547 of Lecture
Notes in Computer Science, pp. 17{38. Springer-Verlag, Berlin, Heidelberg, New York, 1991.
[M94] M. Matsui. Linear Cryptanalysis Method for DES Cipher. In T. Helleseth, editor, Advances in Cryptology | EUROCRYPT'93, Volume 765 of Lecture Notes in Computer Science,
pp. 386{397. Springer-Verlag, Berlin, Heidelberg, New York, 1994. (A preliminary version
written in Japanese was presented at SCIS93-3C).
[M95] M. Matsui. On Correlation Between the Order of S-boxes and the Strength of DES. In
A. D. Santis, editor, Advances in Cryptology | EUROCRYPT'94, Volume 950 of Lecture
Notes in Computer Science, pp. 366{375. Springer-Verlag, Berlin, Heidelberg, New York,1995.
[M97] M. Matsui. New Block Encryption Algorithm MISTY. In E. Biham, editor, Fast Software
Encryption | 4th International Workshop, FSE'97, Volume 1267 of Lecture Notes in Computer Science, pp. 54{68, Berlin, Heidelberg, New York, 1997. Springer-Verlag. (A preliminary
version written in Japanese was presented at ISEC96-11).
[M99] M. Matsui. Di erential Path Search of the Block Cipher E2. Technical Report ISEC99-19,
The Institute of Electronics, Information and Communication Engineers, 1999. (in Japanese).
[MIYY88] M. Matsui, T. Inoue, A. Yamagishi, and H. Yoshida. A note on calculation circuits over GF(22n ). Technical Report IT88-14, The Institute of Electronics, Information andCommunication Engineers, 1988. (in Japanese).
[MSAK00] S. Moriai, M. Sugita, K. Aoki, and M. Kanda. Security of E2 against TruncatedDi erential Cryptanalysis. In H. Heys and C. Adams, editors, Selected Areas in Cryptography| 6th Annual International Workshop, SAC'99, Volume 1758 of Lecture Notes in Computer
Science, pp. 106{117, Berlin, Heidelberg, New York, 2000. Springer-Verlag.
[MT99] M. Matsui and T. Tokita. Cryptanalysis of a Reduced Version of the Block Cipher
E2. In L. Knudsen, editor, Fast Software Encryption | 6th International Workshop, FSE'99,
Volume 1636 of Lecture Notes in Computer Science, pp. 71{80, Berlin, Heidelberg, New York,1999. Springer-Verlag. (Japanese version was presented at SCIS99.).

40

Copyright NTT and Mitsubishi Electric Corporation 2000
[RDP+ 96] V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers, and E. De Win. The Cipher
SHARK. In D. Gollmann, editor, Fast Software Encryption | Third International Workshop,
Volume 1039 of Lecture Notes in Computer Science, pp. 99{111. Springer-Verlag, Berlin,
Heidelberg, New York, 1996.
[W99] D. Wagner. The Boomerang Attack. In L. R. Knudsen, editor, Fast Software Encryption| 6th International Workshop, FSE'99, Volume 1636 of Lecture Notes in Computer Science,
pp. 156{170, Berlin, Heidelberg, New York, 1999. Springer-Verlag.

41