Copyright (C) NTT & Mitsubishi Electric Corp. 2001

Presentation on theme: "Copyright (C) NTT & Mitsubishi Electric Corp. 2001"— Presentation transcript:

1 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
128ビットブロック暗号 Camellia 青木　和麻呂* 市川　哲也† 神田　雅透* 松井　充† 盛合　志帆* 中嶋　純子† 時田　俊雄† * 日本電信電話株式会社 † 三菱電機株式会社 First , I‘ll introduce a 128-bit block cipher Camellia. Camellia was jointly developed by Mitsubishi Electric Corporation and NTT this March. It was designed by experienced crypto-analysts and programmers. CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

2 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
目次 Camelliaの特長 Camelliaの仕様 安全性評価 実装性能 知的所有権情報 標準化活動 まとめ <付録> 詳細な安全性評価コメント 設計方針 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

3 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
Camelliaの特長 NTTと三菱電機との共同開発。2000年に発表。 両社の暗号設計技術力を結集 NTT: 高速なソフトウェア実装に適した暗号設計 三菱: 小型・高速ハードウェア実装に適した暗号設計 両社: 安全性評価技術 次期米国政府標準暗号AESと同じインタフェースをサポート ブロック長: 128ビット 鍵長: 128, 192, 256ビット Camellia is a block cipher with 128-bit block size and supports 128-, 192-, and 256-bit keys. This is the same interface as the Advanced Encryption Standard, AES. These longer key lengths offer more security against exhaustive key search attack in the future. CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

4 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
Camelliaの特長 高い安全性 既知の解読法に対して安全 今後数十年の利用を考慮した高いセキュリティマージン 様々なプラットフォーム上で効率的な処理 ソフトウェア実装: 32ビットや64ビットプロセッサ上で高速 ICカード（メモリが制限されている8ビットや32ビットプロセッサ）上でコンパクトかつ高性能 ハードウェア実装: 小型かつ高性能 現存する128ビットブロック暗号のなかでは，世界 最小クラスの実装面積 優れた鍵交換高速性: 鍵セットアップ時間が短い Camellia is a block cipher with 128-bit block size and supports 128-, 192-, and 256-bit keys. This is the same interface as the Advanced Encryption Standard, AES. These longer key lengths offer more security against exhaustive key search attack in the future. CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

5 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
Camelliaの仕様 暗号化／復号処理: 18段 Feistel 構造 (128ビット鍵) 24段 Feistel 構造 (192, 256ビット鍵) ラウンド関数: SPN 構造 6段ごとにFL/FL-1関数を挿入 副鍵との排他的論理和による入出力ホワイトニング 副鍵生成処理: 簡明 暗号化処理と同じ 2段 Feistel 構造を共用 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

6 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
Camellia （128ビット鍵） 秘密鍵 (128ビット) 平文 (128ビット) 副鍵 F S1 バイト単位 線形変換 F S4 S3 F S2 F S4 S3 F ローテーションと副鍵選択 中間鍵生成 S2 F S1 Si ： 置換表（sボックス） 暗号化（復号） 処理 鍵生成処理 副鍵 FL FL-1 副鍵 暗号文 (128ビット) CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

7 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
Camellia （192, 256ビット鍵） 秘密鍵 (192, 256ビット) 平文 (128ビット) 副鍵 F S1 バイト単位 線形変換 F S4 S3 F S2 F S4 S3 F ローテーションと副鍵選択 中間鍵生成 S2 F S1 Si ： 置換表（sボックス） 鍵生成処理 副鍵 FL FL-1 副鍵 暗号文 (128ビット) CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

8 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
設計方針 (要約) 段関数 差分解読法・線形解読法に対して高い安全性を実現 様々なプラットフォーム上で高性能な処理を実現 小型のハードウェア実装が可能 FL/FL-1関数 構造の規則性を崩す 処理性能に大きな影響を与えない 鍵スケジュール 優れた鍵交換高速性を実現 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

9 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
考慮した安全性 以下のような攻撃に対し，十分な安全性を保つように設計 差分解読法，線形解読法 丸め差分攻撃，丸め線形攻撃 不能差分利用攻撃 ブーメラン攻撃 高階差分攻撃，Square攻撃 補間攻撃，線形和攻撃 等価鍵非存在性 スライド攻撃 関連鍵攻撃 実装攻撃， …… CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

10 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
安全性に関する第三者評価 公開された第三者評価 現在まで，FL/FL-1関数を除いた12段以上のCamellia（128ビット鍵）に対する攻撃は成功せず （仕様どおりの）Camelliaは安全であり，高いセキュリティマージンを有していると考えられる 著者 発表先 主な結果 (128ビット鍵) 攻撃可能段数 FL/FL-1 解読手法 Knudsen Camellia HP 7 段が識別可能 無 丸め差分 Bihamら NESSIE public report 9 段 差分 8 段が識別可能 川端，金子 2nd NESSIE workshop 8 段 高階差分 He, Qing ICICS2001 6 段 --- Square 杉田ら ASIACRYPT2001 9 段が識別可能 7 段の不能差分 不能差分 As you know, differential and linear cryptanalysis were proposed in 1990s. They are powerful cryptanalytic methods to many block ciphers. So designers should provide some evidences that the proposed cipher is secure against them. To evaluate the security, two security measures are known. One is the upper bound of probabilities of differentials and linear hulls. That is called provably secure. And the other is the upper bound of differential and linear characteristic probability. That is called practically secure. Here, the important thing is that they are focused on the upper bound of probability. We call this security measures with designer’s viewpoint. (101/128) CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

11 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
ソフトウェア実装性能（128ビット鍵） Pentium III (CPU clock: 1GHzの場合) (cycles/byte) 暗号化処理速度 (msec) 副鍵生成+1ブロック暗号化 74.9 Mbps 高速 高速 229.8 Mbps 415.6 Mbps 392.6 Mbps アセンブリ 自己評価 アセンブリ CRYPTREC* ANSI C 最適化未了 アセンブリ CRYPTREC* アセンブリ 自己評価 アセンブリ CRYPTREC* アセンブリ CRYPTREC* [出典] CRYPTREC*: 暗号技術評価報告書（2000年度版） CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

12 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
ソフトウェア実装性能（128ビット鍵） Z80上でのアセンブリ実装 (CPU clock: 5MHz) [出典] Rijndael*: 佐野ら, 第2回NESSIE会議予稿集 Camellia Rijndael* ROM使用量 [バイト数] 1,268 1,221 RAM使用量 [バイト数] (スタック，テキスト，鍵の各領域込み) 60 63 副鍵生成+1ブロック暗号化 [ステート数] (動的副鍵生成を利用) 35,951 (7.19 msec) 35,709 (7.15 msec) 副鍵生成+1ブロック復号 37,553 (7.51 msec) 52,094 (10.42 msec) CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

13 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
ソフトウェア実装性能（128ビット鍵） その他の結果 Pentium III上のJava実装 (自己評価) 鍵スケジュール: 9,091 サイクル 暗号化処理: 793 サイクル UltraSPARC，Alpha上でのアセンブリ実装 (暗号技術評価報告書2000年度版より) プロセッサ 暗号化／復号処理速度 1ブロック暗号化／復号 + 鍵スケジュール 暗号化 [サイクル数] 復号 暗号化+副鍵生成 復号+副鍵生成 UltraSPARCIIi 355 403 Alpha 21264 282 448 435 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

14 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
ハードウェア実装性能（128ビット鍵） 自己評価 – 最良の結果 (ASIC) 三菱 0.18mm ASIC CMOS (FPGA) Xilinx VirtexE 優先項目 実装サイズ [Kgates] スループット [Mbps] 処理効率 (=ｽﾙｰﾌﾟｯﾄ/ｴﾘｱ) 面積最小 8.12 177.62 21.87 最高処理効率 11.87 1,050.90 88.52 処理速度最速 44.30 1,881.25 42.47 優先項目 実装サイズ [slices] スループット [Mbps] 処理効率 (=ｽﾙｰﾌﾟｯﾄ/ｴﾘｱ) 面積最小 1,780 227.42 127.76 最高処理効率 (処理速度最速) 9,692 6,749.99 696.45 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

15 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
知的所有権情報 Camelliaを評価する際に必要となる知的所有権の利用が無償で行えることを宣誓します Camelliaの基本特許に関しては，Camelliaを 使用するものに対して，相互主義の下に，非排他的に，無償で実施許諾する方針です CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

16 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
標準化活動 NESSIE (New European Schemes for Signature, Integrity, and Encryption) プロジェクト 第2次評価フェーズへ進出 IETF Internet-Draftsを提案 Addition of the Camellia Encryption Algorithm to Transport Layer Security (TLS) A Description of the Camellia Encryption Algorithm ISO/IEC JTC 1/SC 27 日本国内委員会へ提案中 Encryption Algorithms (18033) CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

17 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
詳細情報の問い合わせ Camellia Home Page 仕様書およびサンプルコード 設計方針，実装性能，ソフトウェア実装技法，ハードウェア評価，および安全性評価の詳細などに関する技術 文書 For more information, see the Camellia home page. Specification of Camellia and a reference code are available. You will also find technical papers on design rationale, performance, software implementation techniques, and security evaluation. Internet-Draft on a description of Camellia will be coming soon! CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

18 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
まとめ 128, 192, 256ビット鍵が利用できる128ビットブロック暗号Camelliaの提案 明確な設計方針に基づく 高い安全性 攻撃に成功した解読法は知られていない 十分に大きなセキュリティマージンを取っている 様々なプラットフォーム上で効率的な処理 小型で効率的なハードウェア実装 高速なソフトウェア実装 ICカード（メモリが制限された低コストプラットフォーム)上での効率的な実装 ロイヤリティフリーのアルゴリズム  CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

19 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
ご質問をどうぞ CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

20 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
付録 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

21 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
安全性自己評価 差分解読法および線形解読法 FL/FL-1関数を含む12段Camelliaには，確率 以上となる差分特性・線形特性パスが存在しない 丸め差分攻撃および丸め線形攻撃 10段以上のCamelliaでは，ランダム関数との識別が 不可能 不能差分利用攻撃 FL/FL-1関数は鍵の値によって差分パスを変化させる ブーメラン攻撃 FL/FL-1関数を除いた8段Camelliaの最良ブーメラン確率は 2-66以下と抑えられる CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

22 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
安全性自己評価 高階差分攻撃およびSquare攻撃 Camelliaのブール多項式での次数が十分に大きくなると期待 補間攻撃および線形和攻撃 Camelliaの未知係数の最小個数が最大となると期待 実装攻撃 “有利な（Favorable）” アルゴリズムのグループに属す 実装攻撃に対する防御はもっとも簡単 いくつかの防御策は，実装性能に大きな影響を与えることなく実現可能 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

23 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
安全性自己評価 等価鍵非存在 鍵生成によって作られる副鍵の集合には，元々の秘密鍵が含まれる スライド攻撃 構造の規則性を崩すため，FL/FL-1関数をFeistel構造の 6段ごとに挿入 関連鍵攻撃 副鍵の関係を制御したり，予測したりすることは困難 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

24 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
設計方針 – ラウンド関数 P関数 バイト単位の排他的論理和だけで構成可能 様々な環境で効率的な処理 分岐数が最良 差分解読法や線形解読法に対する耐性 Sボックス ガロア体GF(28) での逆数関数のアフィン等価関数を利用 以下の攻撃に対する耐性 差分解読法及び線形解読法 高階差分攻撃 補間攻撃 ハードウェアでの小型実装 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

25 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
ラウンド関数の詳細 副鍵 s ﾎﾞｯｸｽ P 関数 S1 S4 S3 S2 S4 S3 S2 S1 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

26 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
設計方針 – FL/FL-1関数 構造の規則性を崩す スライド攻撃に対する耐性 将来の（未知の）攻撃に対する耐性 通常の Feistel 構造が有する特長を維持 副鍵の順序を除けば，暗号化処理と復号処理が同一 MISTYのFL関数の設計方針を踏襲 任意の固定された副鍵に対して線形変換であるが， その変換は副鍵の値によって変化する ソフトウェアでもハードウェアでも効率的な実装が可能な論理演算で構成 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

27 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
FL/FL-1関数の詳細 <<<1 副鍵 FL関数 FL-1関数 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

28 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
設計方針 – 副鍵生成 ハードウェア実装面 簡明で，暗号化（復号）処理と一部共用可能 128ビット鍵専用の副鍵生成は，128, 192, 256ビット すべての鍵に対する副鍵生成の一部分として実行可能 様々な環境での効率性 鍵セットアップ時間を暗号化時間よりも短くする 動的副鍵生成をサポート 暗号化処理と復号処理とで動的副鍵生成が同一の　　方法で計算可能 安全性 等価鍵の非存在 関連鍵攻撃への耐性 CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001

29 Copyright (C) NTT & Mitsubishi Electric Corp. 2001
副鍵生成の詳細 KL KR F KB Σ5 Σ6 定数Σi： i 番目の素数の平方根の2番目から 17番目までの16進表現の値 Σ1 F Σ2 F KL Σ3 F Σ4 F KA CRYPTREC Workshop Copyright (C) NTT & Mitsubishi Electric Corp. 2001