  |
はてなキーワード: Diffie-Hellmanとは
[B! セキュリティ] フェイスブックの暗号化、日米英などが見直し要求へ （写真=AP） 日本経済新聞
平文に一定のアルゴリズムに従って暗号鍵から生成したノイズデータを掛け合わせ、意味が読み取れない暗号文を作るのが暗号化である。逆に意味が取れない暗号文から平文を求める操作を復号と呼ぶ。アルゴリズムがよく知られていながら暗号鍵が無ければ復号できないものがよい暗号と言われる。一般には256bitAESでも使っておけばまずパッと見ても聞いても数学的にもほぼ乱数と区別できなくなる。
ノイズデータの生成方法には色々あり、事前に送り付けた乱数表を使い使用後は破棄するもの、事前に送り付けた共通鍵や公開鍵を使うもの、都度生成するものなどがある。掛け合わせる方法も色々あり、乱数表に書いてある数字と暗号文を足し合わせると平文になるもの、共通鍵を暗号文に使うと平文になるもの、公開鍵を使うと平文になるものなどがある。
共通鍵を平文に使うと暗号文になり、共通鍵を暗号文に使うと平文になるものを、対称暗号とか共通鍵暗号と呼ぶ。
公開鍵を平文に使うと暗号文になり、暗号文に秘密鍵を使うと平文になるものを公開鍵暗号と呼ぶ。非対称暗号ともいう。
共通鍵暗号でも公開鍵暗号でも「平文が、暗号文になり、平文に戻る」というところは同じだが、
共通鍵では「平文→ 鍵→暗号文→鍵 →平文」と同じ鍵を使い、
公開鍵では「平文→ 公開鍵→暗号文→秘密鍵 →平文」と二種類の鍵を順に使う。
なお、この二種類の鍵は順に使えば順序はどっちでも良い。先に秘密鍵で処理して公開鍵で処理することも可能だ。とにかく2種類両方を使えば良い。
共通鍵暗号は分かりやすい。zipのパスみたいなもんだ。Wi-Fiのパスワードも同じだ。だが公開鍵暗号については、二種類の鍵を順番に使うと何が良いのかと思う人も多いだろう。どうせ暗号で読めないのだからいいじゃないかと思うだろう。実は名前の通り鍵を公開しても全くノーダメージというところがメリットなのだ。書かなかったが公開鍵から秘密鍵を数学的に求めることは不可能である。逆も不可能である。そして処理する順番もどっちでもいい。つまり適当な暗号文と鍵の片割れを公開しておくことで、もう片割れの所有を証明できるのである。これが公開鍵暗号の醍醐味である。
この技術はHTTPSの証明書に使われている。というかすべての公開鍵基盤で使われている。.pemとか.cerとかid_rsa.pubはこの片割れであり、ウェブブラウザの「証明書の検証」とは、ネットを見てる時にサーバが送ってくる「適当な暗号文」として"*.hatena.ne.jp"のハッシュを知らん鍵で暗号化したもののハッシュを知らん鍵で暗号化したもののハッシュを暗号化したものに対して、事前にWindowsをインストールした時に付いてきたHatena-Masuda Ultra Global Root CAとかいったけったいな鍵の片割れを使ってみてちゃんと復号出来てるかチェックしているのである。
暗号化通信を行うには、暗号鍵でデータを暗号化すればいい。暗号化には共通鍵暗号を使うのが高速で便利だ。公開鍵暗号は原理的に計算量が多く低速である。しかし、どうやって共通鍵を事前に知らせればいい? 公開鍵暗号で共通鍵を暗号化すれば、受け取り手は自分の秘密鍵で復号できるだろう。しかし、秘密鍵は本当に秘密か? 暗号文と秘密鍵が手に入れば、公開鍵暗号でも解読できてしまうのではないか? HTTPS化しているウェブサービスでも、TLSをロードバランサで終端してデータセンタ内は平文だったりするのではないか? そこで鍵交換、セッション鍵生成の議論が登場する。
Diffie-Hellman-Merkle(Diffie-Hellman)鍵交換方式とは、ディッフィー君とヘルマン君が下宿で階段をドタドタやってる時に天啓のように降ってきたと言われる、ネット上に数字そのものを公開することなく、2者間で同じ1つの乱数を得る方法である。
送信者と受信者の間で共通の1つの乱数を得ることができ、その乱数を第三者に知られることがない。
上で何度か「公開鍵暗号の秘密鍵と公開鍵は、平文に対して両方使えば平文に戻り、順序は関係ない」と書いたのを覚えているだろうか。Diffie-Hellmanはこれに似た方式だ。まず、AさんとBさんは送信者がお互い本人であることを証明できるようにする(公開鍵基盤を使う)。そして、それぞれ手元で乱数AとBを生成する。次に、鍵用の乱数Aを適当な乱数で暗号化した鍵Aと、鍵用の乱数Bを適当な乱数で暗号化した鍵Bを計算し、お互いに送り付ける。この暗号Aと暗号Bは盗聴されているものとする。
AさんとBさんはそれぞれ鍵Bと鍵Aに対して暗号化を行う。すると鍵BAと鍵ABが生まれる。このとき数学的な都合により鍵BA == 鍵ABである。
では、暗号A、暗号B、適当A、適当Bのみから鍵ABや乱数Aを求めることはできないのか? 可能だが式変形などで「解く」ことができず、総当たりになるため計算量が膨大になる。従って実質的にはできない。
或は、暗号A、暗号Bを掛け合わせれば、鍵ABになるのではないか? これもできない。暗号AまたはBと掛け合わせるのは生の乱数AまたはBでなければ意味がない。第三者が乱数Cを作って暗号AやBと掛け合わせても、鍵ACや鍵BCになってしまい、鍵ABと一致しない。
これにより、手元で生成した乱数以外のすべての情報が公開で既知で盗聴されているにもかかわらず、2者間で秘密の暗号鍵用乱数を得ることができる。
原始的なDiffie-Hellman鍵交換の実際の計算は非常に簡単であり、この「暗号化」は事前に決めた別の方法で生成する既知の2つの整数X, Yと乱数A, Bに対して、
暗号A = XをA乗してYで割った余り、
暗号B = XをB乗してYで割った余り、
鍵AB = 暗号BをA乗してYで割った余り、
である。
なお、くれぐれも簡単と聞いてPython 2.7とかで実装しようとしないように。算数の上手い人が作ったライブラリを使え。暗号処理の自作は絶対バグらせて割られるのがオチだ。ちなみにDiffie-Hellman-Merkleの三人目のマークル氏というのは両名と何のゆかりもないので普通は名前に入れないのだが、Merkle氏の先行研究が直接の元ネタなので入れるべきだと主張する派閥もある。俺はどっちでもいいと思うが折角なので入れておく。
ここでやっとE2E暗号化が登場する。上のセクションでしれっと書いたが、DH鍵交換が完了した時に送信者と受信者が得る共通の乱数は、各々ローカルで都度生成する乱数を元にしている。身許保証は公開鍵によるが、鍵は公開鍵に縛られないのだ。つまり、SNSやメールサーバその他、身許を保証する機能と文章をやり取りする機能があるツールと、そのツールで間違いなく本人にDH鍵交換の暗号を送れるクライアントアプリがあれば、その経路で本人同士の間だけで共通の乱数を生成し、それを「セッション鍵」として共通鍵暗号方式による通信経路が設定できる。
この「公開鍵認証基盤で本人確認し、DH鍵交換でセッション鍵を設定し、鍵を端末に出し入れすることなく、受信側端末のメモリに入るまで暗号化を解くこともないまま、共通鍵暗号で通信する」のがいわゆる「End-to-End 暗号化」である。
E2E暗号化を行うと、鍵はDH鍵交換で生成され、端末の外に出ないし書き出す必要もなく、通信の中で割り出す事もできず、通信が終われば破棄してもよい。好きなだけ定期再生成してもよい。認証に使う公開鍵と数学的な関係もない。一度設定してしまえば、SNS運営にチャットログを出させても鍵交換した意味不明な履歴と意味不明な暗号文が出てくるのみで、盗聴者をなりすまさせて鍵を再設定させても前の鍵と何も関係のない新しい鍵が出てくるだけで、意味不明な暗号文の解読の助けにはならない。ちょっと量子コンピュータめいているが、端末となりすましの両方で鍵を一致させることもできない。
ざっくり言えば送信側端末と受信側端末に残っている平文か鍵をバレる前にぶっこ抜く以外に解読方法がない。
これは盗聴関係者にとって非常に大きな問題で、米国のFBIなどは盗聴能力を維持するには法規制以外に策がないと考えている。DH鍵交換のアルゴリズムは上に書いた剰余以外にも楕円曲線を用いた数学的に更に複雑なものもあり、ソースはネットにいくらでも転がっているし、電子計算機アルゴリズムの常でやたら強力な癖に計算量的には全然負担にならない。NSAなどは数学者を揃えて最高のアルゴリズムを提供する振りをして、規格書で事前に決めた一定の数学的特徴を備えているべき定数に備えていないものを指定するとか、実装でミスが出やすい関数を選ぶなど小細工を入れているが俺は二次関数も分からんので詳しいことは知らん。しばしば政府の陰謀にキレた若いITキッズが小細工を抜いて差し替えた再実装を公開したりして揉めている。
実際にSNSなどでE2E暗号化を実装する上での問題点は、本人確認、機種変とマルチデバイス、嫌がらせ対応がある。まず本人確認がコケればMITMは可能だ。E2Eでは鍵を外に出さないのがメリットなので複数端末ログインができず(鍵が変わって別端末で書いたメッセージは解読できなくなる)、運営で常時メッセージを監視できない(したら意味がない)ので嫌がらせ対応が多少困難になる。またMITBというか、改造偽アプリで抜かれる可能性は、まあ、ある。
http://www.alexkyte.me/2016/10/how-textsecure-protocol-signal-whatsapp.html これエキサイト翻訳か？主語が全部theyという支離滅裂な英語なんだが。
----
TextSecureの目標は「経路末端までのセキュリティ、否認性、前方秘匿性、将来の秘匿性のすべて」を提供することである。具体的には、可能な限り短い時間だけ鍵情報を保持するメッセージストリームを二者の間に構築するということを目指す。将来に鍵の危殆化があっても、現在観測されたトラフィックを復号化できなくするのだ。
以下にSignal Protocolの批評的分析を羅列してある。実装の構造を研究し、発見した欠陥を記述し、上述の目標がどれほど実現されているかを評価するものである。まず仕組みの説明をしてから、より詳細な分析を続けることにする。
TextSecureは、今ではSignalと呼ばれているアプリに与えられた名の一つだ。コードも文書も一貫してTextSecureという名を使っている。一貫性を保つため、システム全体をTextSecureと呼ぶことにする。
TextSecureは、非同期整合性に焦点を当ててOff-The-Recordというチャットプロトコルを改造したものだ。OTRが対話的ハンドシェイクを必要とする一方、TextSecureは不確定な遅延を認めない。メッセージを送れるようになるまでアプリを表示したままにしてハンドシェイクを遂行しなければならないというのであれば、ユーザ体験はひどいことになる。
そうではなく、通常の鍵交換においてサーバが果たす役割の部分だけ、将来のクライアントが取得しに来るよう中央サーバに格納される。このサーバは、すべてを復号化できる鍵情報は預けておかない、信用なし経路となる。すべての暗号化は末端どうしだ。
TextSecureは暗号学の基礎のほんの一部を使うものである。公開鍵暗号は楕円Diffie-Hellmanを通し、Curve25519を用いて実行される。AESがパディングなしカウンター(CTR)モードとサイファーブロックチェーン(CBC)モードの双方で対称暗号に使われる。HMAC-SHA256がメッセージ認証に使われる。これらが信頼の基礎(TCB)である。
TextSecureの暗号化エンジンの中心部はAxolotlダブルラチェット・アルゴリズムである。大まかに言うと、一方向にだけ回ることのできるラチェットが二つあり、一つは受信ラチェット、もう一つは送信ラチェットである。この構造により、鍵交換の前半を保管しておいて、後から非同期的に再生し完全なハンドシェイクを得ることが可能になっている。
受信ラチェットはメッセージが受信されるときに使われるが、そこには次の鍵交換のための新しい材料が含まれていなければならない。この材料が後ほど暗号化やメッセージ認証に使う対称鍵の生成に用いられる。
送信ハッシュラチェットは前回の整合性ある共有秘密から生成された鍵ストリームを使って新たな鍵セットを生成する。このラチェットは、受信ラチェットが進んで共有秘密が変化するとリセットされる。
ここで注目すべきは、メッセージを送信するために送信者が待つ必要は一切ないということだ。いつでも送信の第一歩を踏み出すことができ、その一歩は必ず有限の時間で終わる。メッセージはすべて異なる対称鍵で暗号化されるが、これにより、ある時点の鍵は、どちら側のデバイス上のものであっても、過去に送信されたメッセージを復号化するためには使えないことになる。(ただし後で一つ警告がある。)
登録は、クライアントに言って、連絡用の電話番号をサーバに教えてもらうことから始まる。また同時に、トークンを通話とSMSどちらで受け取りたいかの希望も登録してもらう。このトークンが持ち主の証明となり、TextSecureで情報を登録できるようにしてくれる。
クライアントはメッセージ認証と暗号化の対称鍵('signaling'鍵)、および長期公開鍵を送る。
また、複数のプレ鍵も送信する。これはクライアントが受信者になる時の鍵交換の半分、クライアント側部分の使い捨てコピーである。こうして保管されているプレ鍵のおかげで、将来の送信者はクライアントの応答を待つ必要もなく鍵交換を完了でき、こうして遅延を劇的に減らすことができる。クライアントは「最後の手段のプレ鍵」もアップロードするが、これは最後に使われ、受信者が新しいプレ鍵を追加するまでのセッションでずっと共有され続ける。
他のクライアントからも使われるプレ鍵に頼ることについてSignalが警告をしないというのは、筆者の意見では、理想と程遠い。
クライアントは次にGoogle Cloud Messagingに登録して、登録IDをTextSecureに出す。このTextSecureへの登録には、クライアントがSMSを受け取りたいかデータだけにしたいかの情報も含まれる。
TextSecureはクライアントどうしがお互いの長期鍵のフィンガープリントを比較して本人確認できるようになっている。鍵をQRコードとして表示して便利に検証できるようにする機能も含まれている。
送信者は、まず相手のプレ鍵を要求し、プレ鍵インデックス、プレ鍵、登録ID、長期公開鍵をもらう。これらを使い、HKDFという鍵派生アルゴリズムを通して共有秘密を取り決める。この秘密情報をルート鍵と呼ぶ。
このメッセージだけの一時鍵ペアが生成される。ルート鍵を使ってHKDFで新しいルート鍵とつなぎ鍵を派生させる。このつなぎ鍵は、暗号化とMACの鍵を生成するのに使われる。
最後にAESカウンターが初期化される。カウンターは二つある: ctrとpctrだ。ctrカウンターはメッセージ送信ごとに増える一方で、pctrカウンターは、最後の既読メッセージの番号を保持する。これにより、受信者側にバラバラの順番で届いたメッセージを正しく並べ直すことができる。
これらを使って相手にメッセージを暗号化し、それをSignalサーバに送る。このメッセージには、相手が鍵交換ハンドシェイクを完了できるだけの必要情報が含められている。
SignalサーバはGoogle Cloud Messenger登録IDが件の電話番号に合っているかチェックし、メッセージを'signaling'鍵で暗号化してからクラウドサーバに送る。この遠回しな方法により、Google Cloud Messengerがメッセージの送信元を知らずにいることが保障される。
受信者はプレ鍵インデックスを受け取り、送信者がどのプレ鍵を使ったかをそれで調べる。そして送られてきた情報を使ってハンドシェイクを完了したり送信者と同じルート鍵を持ったりする。送られてきたメッセージを復号化するために使う鍵は、このルート鍵が生成する。
相手が返信する前に、もとの送信者から続きのメッセージを送りたい場合は、新しいつなぎ鍵を生成して、これを使って新しい暗号化およびメッセージ認証の鍵を得る。
受信者が返事を出したい時は、まず新しい一時鍵ペアを選ぶ。送信者の一時公開鍵と自分の一時秘密鍵を使って、新しい共有秘密を生成する。これを使って新しいつなぎ鍵を得て、そこから新しい暗号化と認証の鍵を得る。これを使ってメッセージを暗号化し、さきほどの新しい一時公開鍵と一緒に送信する。
TextSecureは、サーバとクライアント間の共有秘密、いわば機械生成パスワードを使って、新しいプレ鍵のアップロードを認証する。これは送信メッセージの認証にも使われる。このパスワードを漏らしてしまうと、それだけでメッセージの送信も鍵アップもそのユーザになりすましてできてしまうことになる。エキスポート機能があった頃はTextSecureクライアントを別のスマホに移行することができたが、この機能は削除された。エキスポート情報には機械生成パスワードが含まれていたからだ。この平文バックアップはデバイスのSDカードに置かれていたので、他のアプリから読むことができたのだ。
この機能はそれ以来削除されたままだ。なくて困る人がいるとしても、これはユーザビリティの問題ではなく、現実の問題であり、それに対する後ろ向きな対策なのである。
この攻撃は偽配送の一種だ。攻撃者がUKS攻撃を実行すると、ある送信者が攻撃者に向けて送ったつもりのメッセージが、攻撃者から別の人(標的)へのメッセージとして送信される。
これは能力のある攻撃者にとっては簡単にできる。TextSecureサーバ上にある自分の公開鍵を、標的の公開鍵に変えればいい。これは自分の電話番号を再登録すればできる。送信者はQRコードを使って、相手のフィンガープリントが合っていることを検証できるが、これが本当に標的の鍵のフィンガープリントになるのである。
それから、今度は送信者のアカウントを再登録して、その検証SMSか確認通話が送信者に到達しないよう横取りしなければならない。これは太っ腹に権限を与えられた人には造作もないことだ。こうして、送信者として認証し、既知の署名つきメッセージを送信できるようになる。
この攻撃はTextSecureでは解決されていない。プレ鍵の署名は追加したが、まだ暗号学的にIDと関連付けられているわけではないので、奪われて再生される危険がある。
できることがあるとすれば、送信者と受信者の双方がメッセージの暗号化された本文内で言及されるようにすることなどだ。
TextSecureはその構造のおかげで前方秘匿性を獲得している。前方秘匿性(forward secrecy)は、もし長期公開鍵が安全なままであれば、ある時点の対称鍵が漏れても、そのセキュリティ突破は限定的な時間範囲にしか有効でないとする。新しいラチェットのそれぞれに公開鍵が必要であることから、これは達成されている。
完全前方秘匿性(perfect forward secrecy)は、クライアントの持つある時点の鍵が奪取されても、それ以前に送信したメッセージの復号化が不可能である性質と定義されている。このことはTextSecureのwire protocolにより施行されるが、少々ことば遊びに入ってくる。というのも鍵はデバイス上にのみ格納されているので、アプリ上の他の鍵にアクセスすることなく鍵が暴露されることはありそうにない。長期鍵だけではメッセージを復号化できず、ラチェットのステートに対応する一時鍵が必要になるが、これはそのスマホから引き出すことができるので、送信したものの返信されていない(前回のラチェットを使用した)メッセージを復号化できる。これは技術的に言えば「以前の」メッセージの暴露である。
否認性(アリバイ)はさらにあやふやだ。ある特定のメッセージについて、それはだれにでも作成できたのだと言うことは可能だが、その一方で、プレ鍵は公開されているので、TextSecureの中央集中構造が脅威をもたらす。TextSecureサーバは認証とメッセージ転送をするものだが、それを記録することもできる。内容は末端どうしで暗号化されているとはいえ、メタデータは違う。
Analysis Whitepaper:
http://ieeexplore.ieee.org/document/7467371/
Marlinspike, Moxie (30 March 2016). "Signal on the outside, Signal on the inside". Open Whisper Systems. Retrieved 31 March 2016. https://whispersystems.org/blog/signal-inside-and-out/
