ブロック暗号

ブロック暗号とは、共通鍵暗号の一種で、固定長のデータを単位として処理する暗号の総称である。これに対して、ビット単位やバイト単位で処理を行う暗号はストリーム暗号と呼ばれる。

1. 概要
-----

ブロック暗号は、 ビットのブロックと ビットの鍵を入力として、 ビットのブロックを出力する。暗号化  と復号  の2つのアルゴリズムからなる。任意の鍵 について、復号アルゴリズムは暗号化アルゴリズムの逆関数になっていて、

を満たすようになっている。暗号化アルゴリズムの入力ブロックおよび復号アルゴリズムの出力ブロックは通信文、暗号化アルゴリズムの出力ブロックおよび復号アルゴリズムの入力ブロックは暗号文という。任意の長さの通信文を扱うために、暗号利用モードが用意されている。ブロック暗号は確定的暗号であり、鍵を一つ固定すると、同じ平文は必ず同じ暗号文に暗号化される。すなわち、同じ暗号文があった場合、そのブロックの平文は同じであるという情報が漏れてしまう。暗号利用モードでは、このような問題を解決する機能ももつ。

換字と転置を組み合わせた共通鍵暗号でも、複数の法に基づく大きなブロックの換字式ストリーム暗号と転置式暗号を組み合わせることで解読の著しく難しい暗号が構成できる。

代表的なブロック暗号として、米NISTが制定したDES やトリプルDES、AES  がある。日本製のブロック暗号として、MISTY1やCamelliaなどが知られている。

2. 構造
-----

ブロック暗号は、メインのスクランブラと拡大鍵を生成する鍵スケジューラから構成されているものが多い。さらに、鍵スケジューラは鍵を入力として複数個の拡大鍵を出力し、スクランブラは複数のラウンドからなり、個々のラウンドで拡大鍵を使って入力の置換・転置等を行う構成になっているものが多い。この構成の暗号をProduct cipherという。また、ラウンドが同じ関数の繰り返しになっている場合にはIterated cipherという。

ラウンド関数は置換や転置、論理演算、算術演算などのシンプルな部品で構成されていて、ラウンド関数を複数段、重ねることで十分な強度のスクランブルを行うものである。ラウンド段数は、通常、アルゴリズムの仕様によって指定されているが、セキュリティパラメータとして利用者が選択するものもある。

ラウンド関数の主な構成法にはFeistel構造とSPN構造の2つがある。DES, MISTY1, CamelliaはFeistel構造で、AESはSPN構造の暗号である。

3. 用途
-----

ブロック暗号は公開鍵暗号に比して高速であるため、公開鍵暗号と組み合わせたハイブリッド暗号では公開鍵暗号で暗号化されたセッション鍵を用いた本文の暗号化・復号に用いられる。

また、パスワードの保存のための一方向性関数として用いられたり  、メッセージ認証コード  に用いられる。

擬似乱数列の生成にも用いられる  。

4. 標準
-----

暗号標準として採用されているブロック暗号には次のものがある。

64bit
TDEA - ISO/IEC_18033, CRYPTREC
MISTY1 -ISO/IEC_18033, CRYPTREC, NESSIE
CAST-128 -ISO/IEC_18033
CIPHERUNICORN-E - CRYPTREC
Hierocrypt-L1 -CRYPTREC
MULTI2 - ARIB限定受信方式
KASUMI - 3GPP W-CDMAおよびGSM用の暗号
128bit
AES -ISO/IEC_18033, CRYPTREC, NESSIE
Camellia -ISO/IEC_18033, CRYPTREC, NESSIE
SEED -ISO/IEC_18033
CIPHERUNICORN-A - CRYPTREC
Hierocrypt-3 -CRYPTREC
SC2000 -CRYPTREC
256bit
SHACAL-2 -NESSIE

5. 安全性
------

5.1. 計算量的安全性
------------

ブロック暗号は、もとより鍵長ビットに対しての計算量的安全性以上の安全性をもたない。すなわち、鍵の全数探索で必ず解読可能である。 これは、ブロック暗号の鍵長を定める際に最も重要な要素の一つであり、現在DESが推奨されないのもその鍵長の短さが原因の一つである。

ただし、ブロック長がである場合、ある通信文と暗号文の対に対して、平均しての鍵候補が存在する。一つの通信文暗号文対では、鍵候補の中に真の暗号化鍵は存在するが、どの鍵候補が真の暗号化鍵であるかは判定できない。個の通信文暗号文対が存在して、ならば、真の暗号化鍵が得られることが期待できる。

5.2. ショートカット法
-------------

ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵を求める手法を総称してショートカット法と呼ぶ。ショートカット法には多くの種類があるが、ここでは代表的なものを列挙する。

差分解読法 :en:Differential cryptanalysis 
不能差分解読法 :en:Impossible differential cryptanalysis
切詰差分解読法 Truncated Differential Cryptanalysis
高階差分解読法 Higher Order Differential Cryptanalysis
Square攻撃 :en:Square attack
飽和攻撃 Saturation Attack
ブーメラン攻撃 :en:Boomerang attack
補間攻撃 :en:Interpolation attack 
線形和攻撃 Linear Sum Attack 
線形解読法 :en:Linear cryptanalysis 
差分線形攻撃 :en:Differential-linear attack
切詰線形攻撃 Truncated Linear Attack
スライド攻撃 :en:Slide attack 
カイ2乗攻撃 Attack
mod n攻撃 :en:Mod n cryptanalysis
XSL攻撃 :en:XSL attackショートカット法が存在するアルゴリズムは学術的には「解読可能」と呼ばれるが、その必要な計算量が現実的であるかどうかは考慮されない。学術的に解読可能であることは、必ずしもその暗号を利用したシステムの破綻につながるわけではない。しかしながら、設計者が想定した強度を有していないという事実は、その暗号アルゴリズムが信頼性の低い暗号アルゴリズムであることを意味する。

5.3. サイドチャネル攻撃
--------------

ハードウェアやソフトウェアに実装された暗号を、アルゴリズムではなく消費電力や実行時間等の情報を用いて攻撃する手法をサイドチャネル攻撃と呼ぶ。サイドチャネル攻撃は実装とアルゴリズムの両方に影響される。

単純電力解析 Simple Power Analysis
電力差分攻撃 en:Differential power analysis
タイミング攻撃 :en:Timing attack

6. 歴史
-----

1971年 - 1976年1971年頃にIBMでHorst Feistelにより開発されたLuciferが最初のブロック暗号とされている。Luciferは、換字式暗号と転字式暗号を組み合わせた、換字-転字暗号  である。1977年にLuciferをベースにして、DESが制定された。1987年 - 1991年1987年にNTTの清水明宏と宮口庄司により FEAL が発表された。FEALは8ビットCPU上のソフトウェアで高速に実行することを意図して、算術加算およびシフトを非線形関数として採用していた。1991年にEli Bihamとアディ・シャミアにより差分解読法が発表され、FEALは差分解読法によって効率的に解読できることが判明した。1992年 - 1995年1992年に三菱電機の松井充により線形解読法が発表され、1993年 - 1994年にかけてDESの解読と実験が行われた。1995年に線形攻撃法と差分攻撃法に対して証明可能安全性を有する暗号として MISTY1およびMISTY2 が発表された。その後、様々な攻撃方法の開発と線形差分特性などを指標とする安全性評価の研究が進んだ。1997年 - 2001年計算機とネットワークの進化を背景に、全数探索によるDESの解読可能性を示すために、1997年にRSAセキュリティ社がDESチャレンジを企画、96日後に鍵が発見された。1998年にはハードウェアによる鍵探索専用機 DES cracker が開発され、DESの鍵を56時間で探索した。1997年に次世代暗号  の制定準備が始められると共に、1999年にはAESができるまでの中継ぎとしてTripleDESが制定された  。2001年11月にAESが制定された。また、ヨーロッパではNESSIE、日本ではCRYPTRECといった標準化プロジェクトが実施された。2002年 -AESや、CRYPTREC, NESSIEの標準暗号とは別に、ある種の特殊用途に特化したブロック暗号の設計が研究されている。FPGAやICチップで実装した際に回路規模や実行速度が最適化されることを意図して設計されたCLEFIA等があげられる。また、実装されたハードウェアやソフトウェア
に対する攻撃も活発になった。

7. 脚注
-----

8. 関連項目
-------

ストリーム暗号
共通鍵暗号
暗号理論
Feistel構造
SPN構造