当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。
暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。
興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。
ブロック暗号の欠点はnビット以上使えないということである。利用モードとはブロック長nのブロック暗号Eを用いて、nより長い平文M=(m1,…,mt)を暗号化するための技術である。もう少し厳密にいうと、長さnの(擬似)ランダム置換が与えられたときに、長さntの擬似ランダム置換を作るのが、利用モードの目的である。
ここで、|mi|によってmiの長さ(ビット長)を表すことにする。特に断らない限り、|mi|=n(ブロック長がn)とする。
利用モードは安全に長い擬似ランダム置換を作るのが目的である。つまり、安全な擬似ランダム置換が作れたら、その利用モードは安全といえる。
メリットとデメリットのところで、再生攻撃に弱いといったことも言及しているが、仮に弱いとしても利用モードの安全性には実は関係がない。そもそも利用モードとは再生攻撃をするような能動的なアドバーサリーに対する安全のことを考えて設計されていないのである。だから基本的に能動的アタックに弱いといえる。しかしながら、あらゆる攻撃を考えることは、アドバーサリー脳を作る訓練としては無駄ではない。そのため、あえて言及している。
また、通信におけるビット反転やビット欠損などの誤り伝播(同期はずれ)についてを利用モードの場面で触れている解説書もある。昔はそういったことも利用モードで議論されていたが、現在の暗号理論では誤り伝播は利用モードで議論しないようになってきている。本ページで誤り伝播に触れているのは、思考訓練のためと思っておいてもらいたい。
ECB(Electronic CodeBook:電子符号表)モードとは、次の仕様にしたがい各miを単純に暗号化する方式である。
[1]暗号化
平文M=(m1,…,mt)に対して、c1=Ek(m1),…,ct=Ek(mt)を計算して、暗号文をC=(c1,…,ct)とする。
[2]復号
暗号文C=(c1,…,ct)に対して、m1=Dk(c1),…,mt=Dk(ct)を計算して、平文をM=(m1,…,mt)とする。
なお、最後の平文ブロックがブロック長に満たない場合には、パディングと呼 ばれるデータの詰め物を入れる。
図を見てもらえればわかるように、mi=mjならci=cSUB{jとなる。つまり平文ブロックと暗号文ブロックが一対一対応の関係にあるわけだ。これは安全性 の議論に直結する。
直観的にも安全性に問題があることがわかる。例えば、平文の中に同じ値を持つ平文ブロックが複数存在したとする。それらをブロック暗号のECBモードで暗号化しますと、同じ値を持つ平文ブロックは同じ値の暗号文ブロックに変換されてしまう。これでは暗号文全体を見るだけで、平文の中に同じ値の繰り返しがあることが推測されてしまう。というのも、本来は暗号化の結果はあたかもランダム値に見えるのが理想的であり、同じビット長の繰り返しが何度も登場する確率はほとんどありえないことである。それにもかかわらず登場しているということは、アタッカーは暗号文だけを見ただけでECBモードのような脆弱な方式などを採用していると推測できるわけだ。さらに何らかのきっかけで暗号文の一部分が判明した場合、それがきっかけとして暗号解読が行われてしまう危険性もあるわけである。
ランダム関数・擬似ランダム関数の概念を使えば、次の図のようにもう少し数学的・暗号学的に議論できる。
アドバーサリー(アタッカーと同意)のAは適当にmを作る。そして、m=m1=m2として、ペア(m1,m2)を暗号アルゴリズムMecb(Ek)に送信する。ここでMecbとはモードのMでECBを利用していることを明示する記号とする。そうすると、暗号文のペア(c1,c2)が送られてくる。そのときMecb(Ek)が本当のランダム関数ならばc1=c2になる確率はほとんどない。しかしMecb(Ek)はE CBモードの暗号化アルゴリズムなので、c1=c2となる。そうするとAはDが本当のランダム関数でなく、擬似ランダム関数であると認識できる。つまり、暗 号化アルゴリズムが認識できたということはECBの暗号化は安全でないことになる。
このように2つの同じ平文が、同じ暗号文になってしまうと、別のレイヤーの特徴と併用されて、アドバーサリーは何らかの得をすることがある。
したがって、ECBモードはデータを暗号化する場合にはあまり用いられない。ワーク鍵を暗号化するときなどに用いられることがある。
能動的アドバーサリーのMallory*1がいたとする。
ブロック長が8ビットと仮定する。また、3つのブロックが次のように要素に対応しているようなシステムがあったとする。
例えば、Alice(銀行口座番号は3番)が銀行のATMを操作して、Bob(銀行口座番号は5番)に8万円を振り込みしたいとする。ATMと銀行間では上記のシステムに乗っ取り、次の平文ブロックがECBモードで暗号化されたとする。
これに対応する暗号文ブロックは次の通りである。暗号化アルゴリズムは平文ブロックを鍵KでXOR演算する仕組みだっとたとする。ATMと銀行は秘密に鍵K=0010を共有していて、それを使っている。
この暗号文を盗聴しても、Malloryは鍵Kを知らないので、どんなEK内部で何でXOR演算されているかわからない。つまり、暗号文から平文を知らない。ところが、Malloryが暗号文ブロックのc1とc2の内容を入れ替えて、銀行に送信する。すると、銀行側には次のようなデータが到着する。
銀行は普通に復号しようとする。鍵はK=0010なので、0010でXOR演算して復号しようとする。復号した結果、次のような値になる。
銀行は、この復号結果から、「Bob(銀行口座番号は5番)からAlice(銀行口座番号は3番)に8万円送信する」という指示と解釈してしまう。つまり、Malloryの攻撃が悪影響を与えていることがわかる。
単に悪影響を与えるだけなら、Malloryがstaticアドバーサリーであっても可能だが、Malloryがadaptiveアドバーサリー(完全に中間者攻撃ができる)とすると、もっと有益な攻撃ができる。Mallory自身がATMで「自分からAliceへ100万円送る」ように指示したとする。
[補足]ただし、自分の銀行口座に100万円がなかったら、別のレイヤーでチェックされることが多いので、それはクリアしておく。また、「Aliceから自分へ100万円送る」という指示は別のレイヤーでのチェックにより、できないとする。これも一般的な考え方だろう。入金者と送金元の銀行口座番号が一致しなければ、そもそも変である。
すると、ATMは仕様にしたがって、Kの値でXORして、暗号化して銀行に送る。この通信をMalloryが一旦奪ってしまう。そして先ほどと同じように第1暗号文ブロックと第2暗号文ブロックを入れ換えて、銀行に送信する。銀行側は「AliceからMalloryへ100万円送る」という指示が来たと思ってしまう。つまり、Malloryにとって有益な攻撃が成功したといえるだろう。
[補足]Aliceの銀行口座に100万円以上存在しないと、銀行員がおかしいと気付いてしまう可能性がある。よって、Malloryは念には念を入れて、Aliceの残高を調べておくとよい。
あるコンピュータシステムのパスワードファイルが、次のようにECBモードで暗号化されていたとする。ただし、ブロック長は128ビット(=16バイト)である。
システムの仕様は一般的に公開されているので、アドバーサリーはECBモードで暗号化されているのを知ることができるは妥当といえる。
アドバーサリーはm2にm1のデータを上書きしたとする。同様に、m4にm1のデータを上書きしたとする。
パスワードファイル上すべてのユーザーがJoeアカウントになっているので、ユーザー名を列挙に成功したら、ログインさえも成功できるわけだ。
暗号文に1ビットのエラー(ビット反転)が起こったとして復号すると、そのエラーが1ブロック全体に拡大する。エラー率は最大n倍、平均n/2倍となる(あるビットがランダムに選んだビットと一致する確率は0.5とする)。
CTR(CounTR:カウンタ)モードとは、次の仕様にしたがい各miを暗号化する方式である。カウンタの役割を果たす変数c+rを利用する。
[1]暗号化
平文M=(m1,…,mt)に対して、c1=m1+Ek(ctr+1),…,ct=mt+Ek(ctr+1)を計算して、暗号文をC=(c1,…,ct)とする。
[2]復号
暗号文C=(ctr,c1,…,ct)に対して、m1=c1+Ek(ctr+1),…,mt=ct+Ek(ctr+t)を計算して、平文をM=(m1,…,mt)とする。ここで、DではなくEを使うことに 注意。
このCTRモードはECBモードから比べると若干複雑になっている。
特徴としてまずブロックを任意の順番で暗号化・復号化できるということがいえる。これはECBモードでも同様である。この特徴は実際に暗号をプログラムとして実装したときに各々の暗号化・復号の処理を並列処理させることができることを意味する。
また、暗号化と復号はまったく同じ構造をしている。まして復号アルゴリズムは必要なく暗号化アルゴリズムを復号処理でも利用している。つまりプログラムとして実装するときはわざわざ復号アルゴリズムに対応する関数などを用意する必要がないということである。これは次回以降紹介するOFBモードと同じストリ ーム暗号の特徴である。
それではECBモードのときと同様に図で考えていこう。
同じ平文のペア(m1,m2)をMctr(Ek)に投げてみる。すると暗号文(c1,c2)が返ってくるが、CTRモードの仕様によりc1≠c2となる。これだけ見てもECBモードよりも安全性の意味で強くなっていることがわる。
実はAが2nの計算能力があれば、CTRモードは安全でないことが証明されている。しかしながら一般のコンピュータはそれほどの能力は持たないので(多項式時間しか計算できないから当たり前)、CTRモードは推奨されている。
CTRモードではctrを必ず違う値に更新させてしまうと、情報理論的に安全でなくなる。一方、ctrをランダムに作ると、小さい確率でctrは変わらない。そうすると情報理論的に安全になるので、ctrはランダムに作ったほうがよい。
問題を解きながら考えてみる。
問:CTRモードについて、次の設問を解け。
(1)平文M=(m1,m2)に対する暗号文がC=(ctr,c1,c2)であった。このときのEk(ctr+1)およびEk(ctr+2)の値を求めよ。
(2)ランダム関数族をブロック暗号として用いるCTRモードを考える。アタッカーが暗号文C=(ctr,c1,c2)を入手した。このとき、平文が(m1,m2)である確率を求めよ。
(3)ランダム関数族をブロック暗号として用いたCTRモードは、情報理論的に安
全であることを証明せよ。
(4)ランダム置換族をブロック暗号として用いるCTRモードを考える。アタッカーが暗号文C=(ctr,c1,c2)を入手した。このとき、平文が(m1,m2)である確率を求めよ。
(5)ランダム置換族をブロック暗号として用いたCTRモードは、情報理論的に安
全でないことを証明せよ。
まず(1)から解いていく。カウンターモードの暗号化では、平文M=(m1,…,mt)に対して、c1=m1+Ek(ctr+1),…,ct=mt+Ek(ctr+t)を計算する。わ かりやすいように縦に並べてみる。
…
ただし問題の中では平文はm1とm2だけなので実質2つの式だけしかない。
ここで+はXOR演算であることを思い出す。XOR演算の特徴として同じものを 足し合わせると消えるというのがある。例えば1+1=0になるわけである。2進数 で考えればこれは明らかである。101と101をXOR演算したとする。XOR演算は0+0= 0,0+1=1,1+0=1,1+1=1であるので、101+101=000になる。
上に列挙した中で一番最初の式を変形していく。
(∵両辺にm1をXOR演算する)
(∵右辺と左辺を入れ替えた)
同様に2番目の式を変形していく。
次に(2)を解く。(2)の問題文が云わんとすることは、「M=(m1,m2)∧ C=(ctr,c1,c2)」が成り立つ確率を求めなさいということである。つまり、次のよ うに計算していくことができる。
(EKを共有しているので、一般的に分解できない。ここでは擬似ランダム関数なので独立になり、分解できる)
ところで、数学の問題が小さい問が連続して出題されているときは、前の問題がヒントになっていることが多い。ここでも(1)の答えを使って、上記の式変形の1つ目から2つ目に式変形していく。
3つ目から4つ目の変換で実際に確率の計算している。前半の「Pr(Ek(ctr+1)=c1+m1)=1/2^n」部分を見ていく。c1やm1はnビットなので、それをXOR演算したc1+m1はnビットである。つまりc1+m1の総パターンは2^n通りである。これがEk(ctr+1)とちょうど一致するのは、1/2^nとなる。後半のPr(Ek(ctr+2)=c2+m2)=1/2^n」部分も同様に考えればよい。
それでは(3)を解く。情報理論的な安全性ということなので、示したいことは次が成り立つことになる。
ここで平文は一様分布していていることに注意しておこう。そうすると 左辺は次のように求めることができる。
一方、右辺は(2)より次が成り立つことはすでに判明している。
よって確率が等しくなったので、情報理論的に安全であることが示せた。
次に(4)を考える。Ekは置換でctr+1≠ctr+2なので、Ek(ctr+1)≠Ek(ctr+2)となる。これは置換の性質から明らかである。置換の性質上、違う値を入れて置換すると、その結果も異なることになる。Ek(ctr+1)≠Ek(ctr+2)ということは、(1)から右 辺と左辺を書き換えることができて、c1+m1≠c2+m2になる。
EKは置換だから、(2)のようにPrの中を単純に分解できない。
Pr[S]=(Sに属する場合の数)/(すべての場合の数)だから、次が成り立つ。
分母は(2n)!である。
一方、分子は2箇所行き先がfixされているから、次のようになる。
よって、次のように2つに場合分けができる。
[1]c1+m1=c2+m2のとき
[補講]次の図のように考えてもよい。前半部で総パターンの2n通りのうちからひとつが決定したので、後半部では総パターンから1を引いたもの総パターンになる。図にすると次のようになる。
[2]c1+m1≠c2+m2のとき
最後に(5)を考える。今度は(3)のようにランダム関数族ではなく、ラン ダム置換族を使う場合である。本当の暗号ではこんなことはしないが、あくまで理解を確かめるためにあえてランダム置換族にするということである。このように条件を若干変更して、結果がどう変わってくるのかを自分で確かめるということは非常にためになる。暗号の仕様だけを追いかけていても力はなかなかつかないのだ。
この暗号が情報理論的に安全であるには次が成り立たなければならない。
しかし、(4)から必ずしも成り立たないので(場合分けの結果が異なっている ので明らか)、情報理論的に安全でないことになる。
少し解説が長くなってしまったが、どうだっただろうか? それほど難しい数学などは使っていない。あくまで「情報理論的に安全」「関数と置換の違い」「ビット列がある特定のビット列に一致するときの確率の求め方」の3つをしっかり理解しておけば、類似問題は完璧に解けることになるだろう。
CBC(Cipher Block Chaining:暗号ブロック連鎖)モードとは、次の仕様にしたがい各miを暗号化する方式である。
[1]暗号化
平文M=(m1,…,mt)に対して、nビットの初期化ベクトルIV(Initial Value)をランダムに選び、c1=Ek(IV+m1),c2=Ek(c1+m2),…,ct=Ek(ct-1+mt)を計算して、暗号文をC=(c_1,…,c_t)とする。
[2]復号
暗号文C=(IV,c1,…,ct)に対して、m1=Dk(c1)+IV,m2=Dk(c2)+c1,…,m t=Dk(ct)+ct-1を計算して、平文をM=(m1,…,mt)とする。
mとcでEkを挟んだような仕組みになっています。このEkがなければ一種の関数と見れる。
IVを定数(ブロック暗号の処理を施す度に)とすると安全でなくな る。IVを定数にしてしまうと、ある平文を決まった鍵で暗号化したときと同 じになってしまい、いつも暗号文が同じになってしまう。例えばアタッカー がターゲットの通信路をずっと監視していたとする。そのとき同じ暗号文が1週 間ごとの決まった時間に傍受したとする。通常規則性のある時間に同じ暗号文 が流れてくる確率はほとんどない。それにも関わらずそのような規則性が あるということは、同じ平文を通信していて、しかもそれに対応する暗号文が同 じになってしまうという欠陥のある暗号を利用していると推測できる。後はこ の情報からどんどん情報が漏れていく可能性がある。
1ビット分のエラーがある暗号文を復号すると、2ブロックにその影響が広がってしまう。エラー率は最大n+1倍、平均倍になる。
CFB(Cipher Feed Back:暗号フィードバック)モードとは、次の仕様にしたがい各miを暗号化する方式である。
[1]暗号化
平文M=(m1,…,mt)に対して、nビットの初期化ベクトルIV(Initial Value)をランダムに選び、c1=m1+Ek(IV),c2=m2+Ek(c1),…,ct=mt+Ek(ct-1)を計算して、暗号文をC=(c1,…,ct)とする。
[2]復号
暗号文C=(IV,c1,…,ct)に対して、m1=c1+Ek(IV),m2=c2+Ek(c1),…,mt=ct+Ek(ct-1)を計算して、平文をM=(m1,…,mt)とする。復号アルゴリズムDkではないことに注意。
図から平文ブロックは暗号アルゴリズムによって直接暗号化されないというこ とがわかる。
CFBモードで暗号アルゴリズムが生成するビット列のことを鍵ストリームと呼ぶ。CFBモードでは鍵ストリームを生成するための擬似乱数生成器として暗号ア ルゴリズムを用いている。IVは擬似乱数生成器の種に相当する。なおEkは置換である必要がありません。
またIVをカウンターモードにおけるctrのようにインクリメントするような設計 にしてもならない。
1ビットCFBモードは、非同期式(自己同期式)暗号となる。
伝送中でエラーが起きたり同期がはずれたりして、シフトレジスタの内容が暗号側と復号側でずれても、少なくともnクロック経過すれば、再びシフトレジスタの内容が一致して、正常動作に戻る。
伝送中のエラーは、エラーが復号側のシフトレジスタに残っている間影響を受け続ける。よって、エラー率は最大倍になり、平均
倍になる。
特に、1ビットCFBモードの場合は、エラー率は最大n+1倍、平均倍に拡大される。k=1のときは、同期を取る必要はないが、処理速度は小さくなる。そのため、k=nのときと比べると、n分の1になるのである。
OFB(Output Feed Back:暗号フィードバック)モードとは、次の仕様にしたがい各miを暗号化する方式である。
[1]暗号化
平文M=(m1,…,mt)に対して、nビットの初期化ベクトルIV(Initial Value)
をランダムに選び、
z1=Ek(IV),z2=Ek(z1),…,zt=Ek(zt-1)
c1=m1+z1,c2=m2+z2,…ct=mt+zt
を計算して、暗号文をC=(c1,…,ct)とする。
[2]復号
暗号文C=(IV,c1,…,ct)に対して、
z1=Ek(IV),z2=Ek(z1),…,zt=Ek(zt-1)
m1=c1+z1,m2=c2+z2,…,mt=ct+zt
を計算して、平文をM=(m1,…,mt)とする。復号アルゴリズムDkではないことに注意。
図から平文ブロックは暗号アルゴリズムによって直接暗号化されないというこ とがわかる。平文ブロックと暗号アルゴリズムの出力とをXOR演算して、暗号 ブロックを作り出す。OFBモードはこの点でCFBモードに似ている。
IVは暗号化の度ごとに異なるランダムビット列を用いるのが普通である。なおEkは置換である必要はない。
EKはランダム関数なので、IVがカウンターであっても大丈夫である。つまり脆弱でない。
以上でブロック暗号の主要な利用モードのすべての解説が終った。実際にブロック暗号を設計するときはCBCモード・CTRモードの使用が推奨され ている。実際にインターネットではCBCモードがよく登場している。
最後に関連する定理を少しだけ紹介する。
[定理]
ECBモード以外の各モードは、{Ek}が擬似ランダム置換族であると仮定すると、選択平文攻撃に対して安全である。
[定理]
CTRモードが最も安全である。