鍵配送問題

ここでは、鍵を共有する時に発生する鍵配送問題について紹介します。
以下、2人の会話をご覧ください。

せんぱ～い (^ー^)

ん。
じゃ、続きやる？

はい、お願いします。
やっと、フェーズ1とかフェーズ2の話に入れるんですよね？

うん、まだ説明してない話もあるけど、とりあえず支障はないよ。
フェーズ1で構築したトンネルを利用して、フェーズ2のトンネルを生成するんだ。

あれっ？
フェーズ1でもトンネルを作るんでしたっけ？

あ、そうだった～！
その話をするには、あと2つ大事な話があったのを忘れてた。

ん、今までの話とは別の話ですか？

うん、そう。
まず先に、「鍵配送問題」っていう重要な問題があるんですよ～。

また、なんか難しそうなフレーズが出てきましたね。
フェーズ1のトンネルと、何か深い関係があるんですか？

うん、暗号で使用する鍵を交換する場合に関連する考え方だよ。
暗号を使うには、どうしても鍵をお互いに共有する必要があるでしょ？

あ、そういえばそうですね。
今まで話題に出てないです。

何かしらの方法で相手に教えなきゃいけないけど、どうやって情報を共有したらいいだろうか？

うーん、、、
電話やFAXとか、メールとか？

たとえば、暗号化したデータをメールで送るとして、そのメールでパスワードも送ったらどうだろうか？

あぁ、それはダメですよ。
そのメールを盗聴できた人は、みんな復号できちゃいますから。

そうだね、ここまでは普通の話。
じゃあ、別のメールでパスワードだけを送るのはどうだろう？

うーん、微妙じゃないですか？
ダメ、とまでは言わないですけど。

うん、実はそのとおりなんだけど、なぜ微妙なのかという点が重要なんだ。
理由は色々あるとして、一番のネックは何だろうか？

やっぱ、暗号化したデータと同じ方法で送る、っていうところじゃないかと思うんですけど。
盗聴されているという前提で暗号化しているわけですから、同じ方法で送ったパスワードが見られないっていう理屈はないですよ。

さすが、話が分かるね～！
まさに、おっしゃるとおりだよ。

えへへへ～

暗号データのメールとパスワードのメールを紐付けるのが手間だけど、本文や件名を見れば推測できてしまうだろう。
メールを使わないとなると他の手段を考えなきゃいけないけど、どんな条件で選べばいいだろうか？

実際にはそんなに選択肢がないですけど、少なくとも確実に伝わって安全じゃないとダメですよね。

あ、もう結論が出ちゃったね。
そういう手段を選ばなかった場合に発生する問題が「鍵配送問題」だよ。

えっ、どういうことですか？

ある経路を使って暗号データを送る時、復号する鍵はその経路よりも安全な別の経路を使って伝えなければならない、っていうことだよ。
逆に言うと、同じ経路で鍵を安全に送れるくらいだったら最初からその経路は安全だったということになるので、そもそも暗号は不要じゃないのか、っていうこと。

なんか、文章にすると理屈っぽくて分かりにくいですけど、言いたいことは分かります。
まぁ、当たり前といえば当たり前なんですよね。

この考え方を説明するのに都合がいいアルゴリズムに、「使い捨てパッド」というのがあるよ。

えっ？
何かの生理用品みたいな名前ですけど、だいじょうぶですか？

だいじょうぶですかって、、、
確かにソレっぽいけど、そういう名前なんだから仕方がない。

わ、わかりました。
いちおう最後まで聞いてから判断します。

いや、だからだいじょうぶだっつーのに。
ほとんど使われていないけど、理論上は絶対に破られないアルゴリズムだよ。

えっ？
「絶対に」なんて言っちゃっていいんですか？

うん、言っちゃっていい。
本当のことだから。

そんなスゴいアルゴリズムがあるなら、みんな使えばいいじゃないですか？

うん。
みんなそう思ってるんだけど、このアルゴリズムが抱えている最大のネックである鍵配送問題を解決できないので、使い物にならないんだよ。

え～っ？
もったいぶらずに教えて下さいヨ～！

じゃあ、最初に使い捨てパッドの説明をしようか。
まず、実データと同じ長さの鍵を生成する。

それは、ずいぶん長い鍵ですね。

で、実データと排他的論理和を計算して終了。
排他的論理和だから、もう一度同じように計算すれば復号できる。

？
それだけ？

うん、それだけ。
簡単でしょ？

簡単ですけど、、、
それが、絶対に解読されないアルゴリズムの正体ですか？

意外かもしれないけど、必ずしも複雑だから堅牢、っていうことはないよ。

あ～、それはそうですけど、、
でも、解読されないという最大のポイントはどこにあるんですか？

それは、やっぱり鍵長だね。
ここから少し話が難しくなるので、よく聞いてね。

また、頭を柔らかくしましょうか？
やわらかあたまっ！

だから、その呪文は何なんだ？
また、元に戻らなくなっちゃうよ？

あっ、そうでした。
ヤバイヤバい、、、

今までの話を思い出しながら聞いてくれれば大丈夫だよ。
例えば鍵長が2ビットだったら、鍵が取り得る値の数はいくつ？

普通に、4つですよね。

では、実データの暗号処理後に取り得る値の数はいくつ？

ん、急にややこしくなりましたね。
でも、鍵が4つしかないんだから、やっぱり暗号処理後も4パターンしかないはずです。

おっ、なかなか鋭いね。
同じ考え方で、鍵長が実データと同じ長さだったらいくつになるだろうか？

当然、鍵の数も暗号処理後の数も、実データが取り得る全ての値の数、っていうことになりますね？

おぉ、正解だ！
この、「暗号処理後に取り得る全ての値の数が、実データが取り得る全ての値の数と同じ」っていうところが最大のポイントなんだよ。

うー、まだピンと来ません。。。

まぁ、そりゃそうか。
例えば、英数字と記号10文字で表現できるデータって無数にあるよね。

ん～、「All right.」みたいなことですか？

おぉ、ずいぶんスッと出てきたね。
そういう意味のある文章が出来る場合もあるし、全く無意味な文字列が出来る場合もある。

きっと、人が読んで意味がある文章になるのは、比率にしたらほんの僅かなんでしょうけど。

10文字以内で表現できることは結構多いだろうけど、比率にしたらそうだろうね。
で、これに対して試しに総当たり攻撃を仕掛けてみよう。

鍵の数がハンパじゃないですから、かなりキツいですね。

それもあるけど、そこには頼っていない。
全て試したら、10文字で表現可能な全ての文字列が出てくるはずだ。

あれっ？
途中で鍵が見つかるから、最後までやらなくてもいいんじゃないですか？

さぁ、そこだ！
復号に成功したかどうかを、どうやって判定する？

えっ？
最後まで処理が進んだかどうかで判断すればいいんじゃ、、、

単に排他的論理和を取っているだけだから、処理は必ず成功するでしょ？

あ、確かに。
じゃあ、出力結果を見て判断したら、、、

10文字で表現可能な全ての文字列が候補になってしまうのに、正しい結果をどうやって見つければいい？

じゃあ、元のデータをヒントに、、、
っていうか、元のデータが分からないから解読しようとしてるんでしたね。。。

極端な話、「It's fine.」のような全く別の文章から一字違いの文章、さらには全く意味を持たない文字列まで全て候補に入ってしまうわけだから、その文字列を見て正解かどうか判断できるのは送った本人だけだろう。

ポカーン。。。。

ん？
まだ、ちょっと難しいかな？

こ、これはスゴいですね～！
パスワードの長さをデータと同じにすると、単に鍵が長くなる効果だけじゃなくて、急に世界が変わるんですね！

普通のアルゴリズムは、パスワードが違うと処理が進まなかったりするから、間違っていることを判断できる。
使い捨てパッドではパスワードが違っていてもそれなりの結果が出てしまうから、正解がどれなのか分からない。

すご～い！
これを考えた人って、そこまで分かった上で思いついたんでしょうか？

こういうことばっかり考えてる人が作ったんだろうから、きっとそうなんだろうね。

私、感動しました！
これ作った人に抱かれてもいいぐらいです！

コラコラ、、、
それに、まだ感動するのは早いぞ。

あ、そうか。
鍵配送問題が解決してないんでしたっけ？

すでに、うすうす気付いてるかもしれないけど。
多分、話を聞いたらガッカリすると思うよ。

いや、何が問題なのか分かんないです。
送った本人しか判断できないなんて、まさに理想的じゃないですか？

鍵配送問題の原点を思い出してみそ？

えっと、、、
その経路で安全にパスワードを送れるくらいだったら、そもそも最初からその経路には暗号なんて必要ない、ですね。

そう。
それを使い捨てパッドに照らし合わせると、どうなるだろう？

ポカーン。。。
ポカーン。。。

あ、分かっちゃった？

、、、分かっちゃいました。
元データと同じ長さの鍵を安全に送れる方法があるなら、最初からそっちを使ってデータを送ればいいじゃないですか～！？

バレたか。

何コレ？
ぜんぜん使えないじゃないですか～。。。

鍵に対して色々と工夫しようと考えても、あんまり意味がない。
結局、その工夫を元データに適用すればいいじゃん、という結論になっちゃうので。

そんな～。
さっきの感動を返してくださいヨ～！

いや、そこまで邪険にしなくても。
こういうことって、よくあるじゃない？

えっ、どういうことですか？

作った当時はみんなにバカにされていたけど、後々に技術が進んでから本当のスゴさにみんなが気付き始めて、急に崇め出す、みたいな。

はぁ～、さすが！
なかなかウマいフォローですねぇ。

そういうことだから、さっきの感動は素直に受け止めてあげてくれ。

はい、分かりました。
でも、鍵配送問題の教材としてはピッタリのテーマでしたね。

デショ？
とは言っても、通常は複数の経路を持てる環境のほうが珍しいから、この問題が発生するケースは多いんだよ。

そっか。
インターネットVPNも、インターネットを使って鍵を交換するしかないってことになりますよね。

うん、そう。
で、これをどうにかする方法として「ハイブリッド暗号」が使用されているんだよ。

あ、それが2つ目の話ですね。

そうなんだけど、また面倒な話なので少し休憩しよ？

あ、分かりました！
じゃ、お菓子でも買ってきます。

また雑談が始まっちゃうとアレだから、話題性の少ないものを買ってきてね。

了解です。

以下、「ハイブリッド暗号」につづく。。。

ネットワークセキュリティ関係者の部屋 > ネットワークセキュリティ実践劇場 > 鍵配送問題

お品書き

鍵配送問題