わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

"order is important"な暗号プロトコル

本日の情報セキュリティの授業のテーマは,「信頼される第三者を用いないセキュリティ」でした.前半はDiffie-Hellman鍵交換,後半はPGPおよびGnuPGを取り上げました.終わりのほうでホワイトボードを使って,PGPにおける公開鍵を用いた暗号化,そして復号の流れを殴り書きし,学生はノートに整理したり,デジカメ撮影を行ったりしていました.
さて今年度は,Diffie-Hellman鍵交換の改良版について,説明を増やしました.よく知られているとおりそのオリジナルの暗号プロトコルでは,中間者攻撃(man-in-the-middle arrack)によって,AliceとBobとの間で(それ以外には知り得ない)秘密の値を共有するのではなく,Aliceと敵対者Mallory,BobとMalloryとの間でそれぞれ,秘密の値が共有できてしまいます.
改良版には,以下で述べられている,Basic STSを採用しました.授業では淡々と説明し,終了時の小テストで,これに対する中間者攻撃がうまくいかない理由を書いてもらいました.

通信の手順を,抜き出しておきます.

  1. Alice→Bob : g^x*1
  2. Alice←Bob : g^y, E_K(S_B(g^y,g^x))
  3. Alice→Bob : E_K(S_A(g^x,g^y))

英文ではこの前に,より詳しい処理手順が書かれています.その中で2度出現する,"(order is important)"が気になりました.取り決めではE_K(S_B(g^y,g^x))そしてE_K(S_A(g^x,g^y))となっているけれども,前者をE_K(S_B(g^x,g^y))に変えるのでは,なぜいけないのかという疑問が浮かびました.
はじめに思いついたのは,リプレイ攻撃に使えるかもしれない,だったのですが,Bobによって署名されていますし,暗号化の鍵Kg^{xy},言い換えると秘密の指数xおよびyによって決まるので,どうもそうでもなさそうです.
文献をたどっていくと,次の論文を見つけました*2

このPDFのp.9に,Basic STS Protocolの図があり,直後に,順序についてコメントされていました.

It is possible to create a more symmetric version of this protocol where the parties exchange exponentials first and then exchange encrypted signatures in separate messages. This would make it permissible for the exponential messages to cross, and then the encrypted signature messages to cross. In such a case, neither Alice nor Bob need know who initiated the call. This is desirable, as situations exist in practice (e.g. in both voice telephony and X.25 data transfer) in which at certain implementation levels, it is not known which party initiated a call. This explains why each party forms his signature with his own exponential listed first. If the exponentials were in the same order in both signatures, then Alice and Bob would have to find a way to agree on whose exponential should be listed first (such as by basing the decision on which party initiated the call).

最初の文の"a more symmetric version"(より対称的なバージョン)は,次のように表せます.

  1. Alice→Bob : g^x
  2. Alice←Bob : g^y
  3. Alice→Bob : E_K(S_A(g^x,g^y))
  4. Alice←Bob : E_K(S_B(g^y,g^x))

このとき,「鍵交換」と「相互認証」のための,2種類の情報のやりとりがクロスして行えます.
さらに言うと,やりとりをAliceから始める必然性はなくなってきます.すなわち,番号づけられた4つのステップではなく,次の「2つが2つ」によって,やりとりをしてもいいとなります.
1. 鍵交換

    • Alice→Bob : g^x
    • Alice←Bob : g^y

2. 相互認証

    • Alice→Bob : E_K(S_A(g^x,g^y))
    • Alice←Bob : E_K(S_B(g^y,g^x))

ここで前述の「取り決めではE_K(S_B(g^y,g^x))そしてE_K(S_A(g^x,g^y))となっているけれども,前者をE_K(S_B(g^x,g^y))に変えるのでは,なぜいけないのか」に基づき,BobからAliceに送るのをE_K(S_B(g^x,g^y))に置き換えると,次のようになります.
1. 鍵交換

    • Alice→Bob : g^x
    • Alice←Bob : g^y

2. 相互認証

    • Alice→Bob : E_K(S_A(g^x,g^y))
    • Alice←Bob : E_K(S_B(g^x,g^y))

あるいはこうでしょうか.

  1. Alice→Bob : g^x
  2. Alice←Bob : g^y
  3. Alice→Bob : E_K(S_A(g^x,g^y))
  4. Alice←Bob : E_K(S_B(g^x,g^y))

見た目として,対称性を損なうことになりますが,むしろ重要なのは,このやりとりではAliceが最初の発信者となるのを,その鍵交換プロトコルが含んでしまう点です.
やりとりの非順序性を保証するために,メッセージの中に順序を持たせる---Aliceの署名ではg^xが先,Bobの署名ではg^yが先とする("each party forms his signature with his own exponential listed first")---というのは,面白い考え方でした.
とはいえ現実はというと,4回の通信よりも3回の通信のほうが時間を短くでき,3ステップのBasic STSのほうが望ましいわけです.こうすると,Aliceがinitiatorとなります.
他のセキュリティ上の懸念がなければ,"(order is important)"のところは,"(order is historical)"とすべきなのかもしれません.


本日の記事は,いわゆる「かけ算の順序論争」とは関係ありませんが,「掛け算の順序論争」を検索語として,当ブログの某記事(記事中には「掛」の字はないにもかかわらず)へのアクセスがあるのには,情報技術の進歩を感じる次第です.

(最終更新:2015-06-21 晩)

*1:単なるべき乗ではなく,素数pで割った余りとなります."All exponentials are in the group specified by p."と書かれてありました.

*2:RFC 2142のBIBLIOGRAPHYで,[STS]と書かれている文献です.