AESが選ばれるまでの歴史

8219 ワード
暗号 aes アルゴリズム セキュリティ Rijndael アルゴリズム テキストリンク

米国商務省標準技術局(NIST)によって、AESが認定されたのは今から17年も前の2000年10月のことですが、当時公募で集められた沢山の暗号アルゴリズムの中から選考を経て、ある一つのアルゴリズムが選ばれたことは、あまり知られていません。
この記事では、AESが選ばれるまでの経緯について、簡単にまとめておきたいと思います。
なお、内容のほとんどは私が15年程前に書いた卒業論文を元に作成しています。

AESについて

AES(Advanced Encryption Standard)は、米国商務省標準技術局(NIST)によって選定された次世代の米国政府標準暗号の名称です。
NISTは、これまで標準暗号として認定してきたDES(Data Encryption Standard，FIPS 46-2）の安全性低下が深刻化していることから、1997年1月にDESに代わる標準暗号としてAESのアルゴリズムの要件や評価基準等を公表しました。
応募された暗号アルゴリズムの中から、最終的にはRijndael(ラインダール)というアルゴリズムがAESとして認定されています。

アルゴリズムの要件

AES候補アルゴリズムの要件としては、

(1) 共通鍵ブロック暗号であること
(2) 鍵長は 128bit, 192bit, 256bitのいずれも利用可能であること
(3) ブロック長は128bitが利用可能であること
(4) Triple-DES と同等以上の安全性と効率を有すること
(5) ロイヤリティ・フリーで使用できること

の5点が示されていました。

また、努力目標として 、標準的コード・ブック・モードのサポート（それぞれのモードは政府および銀行業界で使われていたため、 AES による情報処理方法との間で互換性が必要とされた。 ）
などが掲げられていました。

アルゴリズムの評価基準

アルゴリズムの評価基準は、

(1) 安全性（解読の困難性）
(2) コスト
(3) その他の特徴 (※)

の３点であり、この順序で優先順位が付けられていました。

※ その他の特徴とは、
- 通信上の効率
- メモリの必要量
- ハードウェア上およびソフトウェア上の適合性
- 単純さ
- 柔軟さ
などのこと。

選定スケジュール

AES選定までのスケジュールは以下の通りでした。

日付 内容
1997/1/2 AES策定方針を公表
1997/4/15 ワークショップを開催
1997/9/12 公募要領を公開
1998/6/15 公募締切り(21個の応募)
1998/8/20-22 第1回AES会議を開催(ベンチュラ、米国)
15個の認定候補を公開
1999/3/22-23 第2回AES会議を開催（ローマ、イタリア）
解析・評価レポートを発表、討論
- 第2回AES会議内容、評価コメントをもとに約5個を選抜。選抜されたものにつ いては、この段階で仕様のマイナーチェンジが認められる。
2000/4 第3回AES会議を開催
- 第3回AES会議内容、評価コメントをもとにAES最終候補を選抜
2000/10 AES最終候補に対する最終評価を経て、AESに認定、FIPS化

最終候補 MARS，RC6，Rijndael，Serpent，Twofish の5つの中から最終的には、 ベルギーの暗号開発者Joan Daemen氏とVincent Rijmen氏が開発した「Rijndael」という方式が選ばれました。

AES候補暗号の一覧(全15種)

AES候補に挙がったアルゴリズムの一覧です。

名称 提案先 国籍
CAST-256 Entrust Technologies, Inc. Canada
Crypton Future Systems, Inc. Korea
DEAL Richard Outerbridge, Lars Knudsen Canada
DFC Centre National Pour Ia Recherche Scientifique (CNRS) France
E2 NTT Japan
Frog TecApro Internacional S.A. Costarica
HPC Rich Schroeppel AG Ｕ.Ｓ.Ａ
LOKI97 Lawrie Brown, Josef Pieprzyk, Jennifer Seberry Australia
Magenta Deutsche Telekom Germany
Mars BM Ｕ.Ｓ.Ａ
RC6 RSA Laboratories Ｕ.Ｓ.Ａ
Rijndael Joan Daemen, Vincent Rijiman Belgium
Safer+ Cylink Corporation Ｕ.Ｓ.Ａ
Serpent Ross Anderson, Eli Biham, Lars Knudsen UK Israel Norway
Twofish Bruce Schneier, John Kelsey, Dong Whiting, David Wagner, Chris Hall, Niels Ferguson Ｕ.Ｓ.Ａ

処理速度比較

提案者は自分たちの方式の処理速度を明らかにするようNIST から要求されていましたが、処理速度の測定方法が明らかにされていないうえ、測定環境が各々異なるため、提案者が主張し ている処理速度だけで単純に比較することはできませんでした。

処理速度は、プログラマーの能力やコンパイラ性能、プラットフォームなどにも依存しますが、たとえそれらを統一したとしても、設計思想として安全性のマージンをどのように考えるかという点によって大きく変わります。

以下に世界中の暗号研究者によって測定された処理速度の大まかな順位を示します。

↑速い

  • RC6
  • Twofish
  • Mars
  • Crypton
  • Rijndael
  • E2
  • CAST-256
  • Serpent
  • DFC
  • Safer+
  • HPC
  • Frog
  • DEAL
  • LOKI97
  • Magenta

↓遅い

Gladmanが比較用に作成したDESの処理速度は、64 ビットあたり約450クロックです。
したがって、900クロック以下(200 MHz で28.5 Mbits/sec 以上)である RC6, Twofish, Mars, Crypton, Rijndael, E2, CAST-256の7つがDESよりも高速な暗号方式であるといえます。

一方、Frog, DEAL, LOKI97, Magenta は2000クロック以上（200 MHz で12.8 Mbits/sec 以下）かかってお り、Triple-DES 以下程度の処理速度しか出ていませんでした。

Rijndaelが選ばれた理由

NISTのサイトに掲載されたリリースによると、セキュリティ、パフォーマンス、効率、実装のしやす さ、柔軟性のバランスから選ばれたとのことです。
特に同アルゴリズムは各種のコンピューティング環境でパフォーマンスが高く、メモリもそれほど必要としなかったため、スマートカードのようにメモリに制限があるデバイスにも向いているとされました。

しかし、Forrester ResearchのアナリストFrank Prince氏は、ほかの4候補(MARS，RC6，Serpent，Twofish)にも強みがあり，そのためRijndaelの人気は多少下がるのではないかと見ていました。
同氏は他候補もRijndaelと同じくらい有効で、場合によってはより良い解決策ともなり得ると話しています。

参考サイト

Advanced Encryption Standard - Wikipedia
暗号利用モード - Wikipedia
RC6 - Wikipedia
Serpent (暗号) - Wikipedia
Twofish - Wikipedia
日米欧の暗号技術標準化・評価プロジェクトを終えて

参考文献

  • 現代暗号 1997年6月30日 著者 岡本龍明 山本博資 産業図書株式会社
  • E-Mailセキュリティ 平成7年5月25日 著者 Bruce Schneier オーム社
  • 暗号のすべてがわかる本 平成10年7月25日 著者 吹田智章 技術評論社
  • セキュリティＷＧ‐３ 暗号利用技術ハンドブック（第２版） 平成１２年３月 電子商取引実証推進協議会セキ ュリティWG（PDF)
  • AES 暗号について神田 雅透 NTT 情報通信研究所（PDF）
  • 共通鍵暗号を取り巻く現状と課題 -DES からAES へ- 宇根正志,太田和夫 (PDF)
5030-ノードとその祖先との最大差
プログラマーの修道仙の道--ユーザーのアクセス記録を極めて最適化