PFS（Perfect Forward Secrecy）

SSL/TLSの問題

なぜPFSが注目されているか

PFS (Perfect Forward Secrecy)とは暗号化された通信と暗号化するための秘密鍵が両方漏洩しても複合化できません、という鍵交換に関する概念です。 PFSは概念なのでを実装する仕組みが別にあります。２０１４年１月現時点ではPFSはまだあまり普及していないので、主に使われてい鍵交換方式はPFSではありません。

Edward SnowdenがアメリカのNSAの諜報活動をリークしたことをきっかけにPFSは有名になりました。

NSAは

何らかの方法でWebサーバとクライアント間の通信を盗聴する(いわゆる中間者攻撃)
通信は暗号化されていてもとにかく保存
将来、何らかの方法で暗号化に使われた鍵が手に入ったら保存していた通信を解読

ということを行っていました。PFSではない仕組みを使って通信した場合、このようにして通信の時点では暗号を解読されなくても、将来解読されるという不安が残るわけです。

SSL/TLSとRSA鍵交換方式

SSL/TLSはもっとも普及しているWebサーバとクライアント間で通信を暗号化する仕組みです。SSL/TLSにはセッションとコネクションという概念があります。セッションはサーバとクライアントが通信時に一度確立され、信頼できるサーバかどうか、暗号方式には何を使うかなどの情報をやりとりします。コネクションで実際にサーバとクライアント間の通信、例えばHTTP GETなどが行われます。コネクション上の通信は暗号化されていますが、この暗号化には共通鍵暗号方式が使われます。共通鍵暗号方式とは暗号化と複合化に同じ鍵を使う方式のことです。

普段、僕たちが生活していて思い浮かべる暗号化はすべて共通鍵暗号方式です。

ボブ&アリス: 二人だけの秘密のメッセージを交換しよう
ボブ: 「アイシテイル」。このメッセージを暗号化するために、各文字を３文字前にずらした、「エオソニオワ」という文字をアリスに教える
アリス: 「エオソニオワ」を３文字後ろにずらして、「アイシテイル」というメッセージを複合化できた

この例だと３文字が暗号の鍵です。ボブが暗号化するのにもアリスが複合化するにも同じ「３」を使っているので共通鍵暗号方式です。

共通鍵暗号方式は便利な暗号方式ですが、ひとつ問題があります。それは、どうやって全く知らない二人(SSL/TLSだとサーバとクライアント)が暗号に使う鍵を共有するかということです。暗号には鍵が必要ですが、鍵を共有するために平文で通信して鍵が第3者に盗み見られたら元も子もありません。ボブとアリスの例だと3という数字を鍵として使うためには、二人の間で3を鍵にしようと何らかの方法で決めなければいけません。もし、この取り決めを第三者に覗き見された場合、それ以降の通信が全部解読されてしまいます。鍵は絶対に安全な方法で共有されないければいけないのです。

SSL/TLSでもコネクションで使う共通鍵を共有する時にこの問題に出くわします。一つの、そして、もっとも普及している解決方法はRSA鍵交換方式です。この記事ではRSA鍵交換方式については説明しませんが、簡単にいうサーバとクライアントで別々の鍵を使って共通鍵を暗号化してから共有します。複合化にも別々の鍵を使います。

別々の鍵を使うことで、鍵共有問題を解決しているのですが、ここにPFSが解決しようとする問題があります。それは、もし共通鍵を暗号化する時に使った秘密鍵が盗まれた場合、その鍵ですべての通信の暗号を解読されてしまうという問題です。

Big Brother社のサーバとクライアント間の暗号化された通信を盗聴してハードディスクにとりあず保存
3年後、Big Brother社のサーバリプレース時に廃棄されたハードディスクを盗んでそこに保存されていた秘密鍵をゲット
秘密鍵を使って保存していた３年分の暗号化された通信を解析して、暗号化に使われた共通鍵をゲット
共通鍵で通信の複合化

PFSではない仕組みを使って通信した場合、通信した時点では安全でも将来秘密鍵が何らかの方法で漏洩した場合、過去の暗号化された通信が保存されていれば内容が解読されてしまうという脆弱性が存在します。

ちなみに、PFSのFはForwardで、これは前方_という意味ではなく将来とか”未来”とかの意味だと思われます。つまり、PFSは完全に(P)に未来(F)においても通信の秘密(S)が保たれるという意味になります。

EDH鍵交換方式

RSA鍵交換方式の問題点は実際の通信の内容を暗号化するための共通鍵を暗号化するために、サーバに保存されている秘密鍵を使っていることでした。EDH鍵交換方式を使うと、決まった鍵の代わりにセッション毎にクライアントとサーバ側でそれぞれ生成する異なったランダムな数字を鍵と使うことができます。こうすれば、暗号化されて通信を盗聴されていても、それぞれの通信はセッション毎にランダムで生成された鍵で暗号化されているので複合化は格段に難しくなります。

これを実現するためにEDHはDiffie-Hellman鍵共有という方法を使います。DH鍵共有使えば、全く知らない二人の間で事前に何の準備もせずに鍵を共有することができます。

離散対数問題

この魔法のような仕組みは離散対数問題という数学的性質を応用しています。

離散対数問題とは、

g^a mod p を計算して A を求めることは簡単だけど、g, p, Aがわかってもそこからaを求めるのはとても時間がかかってしまうという性質のことです。

下記の計算は簡単にできる。

a=3, g=5, p=7 とする
g^a mod p は 5^3 mod 7 となる
これの答えは6となる

だけど、下記の計算は難しい。

a=x, g=5, p=7, A=6 とする
5^x mod 7 = 6 となるxは何か？
x=1と仮定すると、5^1 mod 7 = 5 となり、6ではないので間違い
x=2と仮定すると、5^2 mod 7 = 4 となり、6ではないので間違い
x=3と仮定すると、5^3 mod 7 = 6 となるのでx=3が正解

今回はxが小さいから運良く3回の計算で答えにたどり着いたけど、もしxが大きかったら順番に計算するのはとても時間がかかってしまう。これが離散対数問題です。

Diffie-Hellman (ディフィー・ヘルマン)鍵共有

Diffie-Hellman鍵共有、(以下DHと省略)は離散対数問題を使って、第3者に知られることなく鍵を共有することができます。

例としてアリスとボブの間で暗号化するための鍵を共有する場合を考えます。ただし、アリスとボブは事前に鍵が何かは知りません。

アリスはランダムに数字を生成して、3という数字を得ます。この数字は誰にも教えずアリスだけの秘密の数字とします。
ボブも同じくランダムな数字を生成して、4という数字を得ます。これも誰にも教えません。
二人は、g=4, p=7と決めます。二人とも知っているので、gとpは秘密ではありません。秘密ではないので平文で送ります。
アリスはg^a mod p (4^3 mod 7)を計算します。これは、1になります。この1という数字をボブに教えます。これは平文で送ります。
ボブも4^4 mod 7を計算します。これは、4になります。この4という数字をアリスに教えます。これは平文で送ります。
アリスはボブからもらった4という数字を使って、4^3 mod 7 という計算をします。これは、1となります。
ボブはアリスからもらった1という数字を使って、1^4 mod 7 という計算をします。これは、1となります。
アリスとボブは1という数字を共有することができたので、これを共有鍵として使うことができます。

ポイントは

アリスとボブはランダムで別々に生成した数字をお互いに秘密にしておくこと
これ以外の数字、g, pと自分の秘密のランダム数字を使って計算したg^a mod pは盗聴されても構わないので平文で送る
お互いに決めたpと相手から送られてきたg^a mod pに対して、自分の秘密ランダム数字を使って計算するとアリスとボブは同じ数字を得ることができる。

最後のポイントが一番重要です。なぜ、二人は別々の秘密ランダム数字を使っているのに最終的に同じ値を得ることできるのか？

さっきのやりとりを具体的な数字を記号に置き換えて計算してみます。

x、yをアリスとボブそれぞれの秘密ランダム数字とする
g, pを共有する
g^x mod p = A、g^y mod p = Bとする
アリスはB^x mod pを計算する。Bはg^y mod pなので、(g^y mod p)^x mod pに置き換えるられる。これはさらに、g^(xy) mod p* に置き換えることができる。
ボブはA^y mod pを計算する。Aはg^x mod pなので、(g^x mod p)^y mod pに置き換えるられる。これは、g^(xy) mod p* に置き換えることができる。

つまり、アリスのB^x mod pとボブのA^x mod pは同じ値を計算していることになるので、二人は同じ値を得ることができます。

離散対数問題の性質上、g, p, A, Bがわかってもxとyを計算するのはとても難しいので、第3者はたとえアリスとボブの通信を盗聴できたとしても共通鍵は知ることができません。

また、xとyはランダムに生成される数字で各セッションで使い切りです。xとyがランダムなのでそこから生成される共通鍵もランダムなので、RSA鍵共有方式のように同じ鍵を使い回すことがありません。 EDHのEは「Ephemeral」で、はかないとか短命とかいう意味で、これはEDHで生成される鍵が使い捨てということから来ています。