前のページ 1/2 次のページ

ストリーム暗号(-あんごう、stream cipher)とは、平文をビット単位あるいはバイト単位などで逐次、暗号化する暗号である。

これに対して、平文を64ビットや128ビットなどの固定長のブロックに分割して暗号化する暗号はブロック暗号という。ストリーム暗号とブロック暗号とに大別される共通鍵暗号と公開鍵暗号とで、現代暗号の主要な暗号方式をなす。

◆ 概要

ストリーム暗号は、鍵ストリーム(key stream)を生成する鍵ストリーム生成部と、鍵ストリームと平文を結合する結合部から構成されることが多い。典型的な方式では、秘密鍵をシードとして擬似乱数列を生成し、平文との排他的論理和 (XOR、$\backslash oplus$) を取ることによって暗号文を作る。復号時には、同じシードから生成した擬似乱数と暗号文との排他的論理和を取ることによって平文を得る。

:$(m\; \backslash oplus\; k)\; \backslash oplus\; k\; =\; m\; \backslash oplus\; (k\; \backslash oplus\; k)\; =\; m$

ブロック暗号はブロック単位で暗号化するので、ブロックサイズ分のデータがそろうまで暗号化処理が開始できない。一方、ストリーム暗号の多くは、疑似乱数を先行して生成できるので、待ち時間が少ない。また、ブロック暗号では、平文がブロックサイズの整数倍ではない場合に必要なパディング処理も、ストリーム暗号では不要であり、常に平文サイズ=暗号文サイズとなる。処理遅延が少ないこと、データサイズが増加しないことは通信などに利用する場合にメリットとなりうる。

しかし、暗号利用モードのOFB, CFB, CTRなどでブロック暗号を利用するとストリーム暗号が構成できるので、ストリーム暗号専用アルゴリズムは、ブロック暗号と比べて何かしらの点で特長(メリット)がなければ存在する意味がない。

一度の暗号化処理で1bitあるいは1byteしか扱わないストリーム暗号は、ソフトウェアで実装すると性能が悪くなりがちである。そのため、近年ではMUGIの様に一度の処理で64bitといったサイズの鍵ストリームを出力し、まとめて暗号化処理できるアルゴリズムも提案されている。近年提案されているストリーム暗号はAESより高速であることをアピールするものが多い。

ストリーム暗号の安全性についての研究は、ブロック暗号に比べて遅れている。安全性の評価手法の研究には長い時間を要するので、ブロック暗号に基づくストリーム暗号を利用すべきとの意見もある。ブロック暗号をCTRモードで利用した場合、ブロック暗号が疑似ランダム置換であれば、計算量的に安全である。

◆ 構造

鍵ストリーム生成部は、128bit程度の秘密鍵を用いて擬似乱数を生成する。通常、共通鍵方式であるが、公開鍵暗号方式(非対称暗号)のストリーム暗号も提案されている。擬似乱数ではなく、真の乱数を利用する場合もある(バーナム暗号)。また、一度使用した鍵ストリームは、再使用しないように制御する必要がある為、平文毎に異なる初期値 (初期化ベクトルまたは IV) を使用する。IVは乱数かカウンタで作る。

鍵ストリーム生成のアルゴリズムとしては、専用のアルゴリズムによるものと、ブロック暗号を元にした生成方法がある。専用アルゴリズムによる鍵ストリーム生成部は、フィードバックシフトレジスタにもとづくものが多い。シフトレジスタとフィードバック関数から構成される。

フィードバックの構成方法に、暗号文を鍵ストリームにフィードバックする方式(同期式、外部同期)と、フィードバックしない方式(非同期式、自己同期)がある。暗号文がビットスリップしたときのエラーの伝播が異なる。

・ 同期式(Synchronous stream cipher) - 送信側・受信側とも、平文・暗号文とは独立して鍵シーケンスを生成する。bitエラーが発生したときに他のbitにエラーが波及しないという特徴がある。逆に、攻撃者が暗号文を操作(例:bit反転)することで、平文を変更できてしまうというデメリットにもなる。場合によってはMACなどのメッセージ認証が必要となる。また同期がずれた場合には、再同期の仕組みが別途必要となる。外部同期式ともいう。

・ 非同期式(asynchronous stream cipher)- 自己同期式(Self-synchronising stream cipher)とも呼ばれ、同期がずれたときでも自動的に再同期できるメリットがある。エラーが発生してもレジスタ長だけ経過すると送信・受信側のレジスタ値が一致し、同期を自動的に回復させることができる。しかし1bitエラーが他のbitにも波及し、エラーが拡大するというデメリットもある。非同期式の例として暗号利用モードの CFB がある。

結合部は、典型的にはXORなどで平文と鍵ストリームを結合する。XOR以外に、加算やテーブルを用いた方式もある。

鍵ストリーム生成部と結合部を別の装置にすると、前者はセキュアに保管運用する必要があるが、後者は通信装置に組み込み可能になる。暗号装置を通信装置と結合する際には注意が必要なので、メリットとなる。

◆ 種類

◇ LFSR型

鍵ストリーム生成の方式として、線形帰還シフトレジスタ (LFSR; Linear Feedback Shift Register) を用いた方法が知られている。LFSRはハードウェアを用いて容易に実装することができる。しかし、LFSRは数学的に容易に解析可能であるため、そのまま暗号に使用することは推奨されない。相関攻撃 (Correlation attack) の餌食となる。非線形なFSRを使うものもある(NFSR:Nonlinear Feedback Shift Register)。

・コンバイナ型:複数のLFSRを非線形関数で結合した方式

・フィルタ型:LFSRの全状態をFilterに入れる方式。例:よく研究対象にされている方式としてTOYOCRYPTがある。

・クロック制御型:LFSRを非連続的動作させる方式。一つのLFSRに他方のLFSRのクロックを制御する。例:ベス&パイパーによる stop-and-go generator (Beth and Piper, 1984)、GSM音声暗号化で使っているA5/1

◇ 状態遷移型

RC4やSEALのような、状態変数を逐次更新することで、鍵ストリーム生成する方式もある。stub

◇ カオス関数

カオス暗号として知られている暗号もある。過去に多くの提案があったがその多くの安全性は厳密に評価されていない物が多い。カオス自体は周期を持たない等優れた性質があるが、デジタルで実装する場合はそのような性質を持たない。近年の研究では、単純な実装の場合極端に短い周期を持つ可能性があることが指摘されている。

◆ 用途

ストリーム暗号は、平文がいつ何バイト発生するか不確定なアプリケーションによく採用される。例えば、秘匿通信(秘話)である。

ウェブブラウザで使用される暗号化通信SSLの暗号方式としてRC4が採用 (オプション) されている。無線LAN (WEP,WPA) でもRC4が使用される。他に、携帯電話用に A5/1, A5/2 などがある。

◆ 標準

暗号標準として採用(or推奨)されているストリーム暗号には次のものがある。

・ OFB,CFB,CTR --- ISO/IEC_18033(asブロック暗号利用モード)

・ SNOW 2.0 ------ ISO/IEC_18033

・ MUGI ---------- ISO/IEC_18033, CRYPTREC

・ MULTI-SO1 ----- ISO/IEC_18033(as MOF), CRYPTREC

・ RC4 ----------- RFC 2246 (TLS), WEP, WPA, CRYPTREC(128bit-RC4のみ)

◆ 安全性

ストリーム暗号の安全性の条件としては:

・ 統計的乱数性

・ 非線形性

・ 無相関性

・ 長周期性

・ 線形複雑度(linear complexity)

などがあげられる。

鍵ストリーム生成部は、通常、内部状態を記憶するレジスタがあり、レジスタ長が安全性の上限の一つとなる。レジスタの初期値を決める秘密鍵のサイズも安全性の上限を決める。これらのサイズは安全性の上限を決めるのであって下限ではない。

安全性の証明については:

・ 鍵ストリームとして完全なランダムシーケンスを採用すると、OTP(One Time Pad)となって情報理論的安全性を持つ。しかし、平文と同じ長さの乱数が必要であり、OTPは広くは採用されていない。

・ 鍵ストリーム生成部にブロック暗号を部品として使用し、ストリーム暗号の安全性をブロック暗号の安全性に帰着させるものがある。

・ ブロック暗号のCTRモードは、ブロック暗号が疑似ランダム関数と見なせるのならば計算量的安全性を持つが、バースデイパラドックスからブロック長 n に対して $2^$ ブロック程度の出力で自然乱数と識別可能である。

◆ 歴史

前のページ 1/2 次のページ

・ストリーム暗号 page1

・ストリーム暗号 page2