安全でない (と思われる) 認証方式について

Tomo’s HotLine:[P2P][DHT]ゼロ知識証明によるP2P認証方法の提案
前提や設定が書かれていないので詳しいことは言えないがコメント欄に書こうとしたら長くなったので, こっちで. 設定次第では何とかやりようはあると思う (本当に?)

記法が分かりづらい(ユーザーにAを使った上で, 数にもAを使っている)ので, 適当に書き直す.

プロトコル

ハッシュ関数が要るので書いておく. H:{0,1}^{2k+1}→{0,1}^{l(k)}, ただしl(k)は適当な整数値関数 (k辺りで良いか).

  • 鍵生成
    • Pはp,q:k-bit safe primeを生成しn=pqとする. rを2k-bitの乱数とし, ID = H(n+r)とする.
  • 認証
    • P,Vの共通入力をIDとする. Pへの補助入力を(n,r,p,q)とする. 追記: 共通入力は(ID,r), 補助入力は(n,r,p,q)
    • Pは(n,r)をVに送る
    • VはID=H(n+r)を確認する
    • POK:PとV間でPがn=pqの(p,q)を知っていることをゼロ知識で証明する
    • Vは上のPOKが正しければ認証する

ノードを変更しない場合の簡単な攻撃方法

追記: 共通入力が(ID,r)になったのでこの攻撃は回避可能.

攻撃者をMとする.

  • 一度PとV間の通信を盗聴する. Mはn,rが分かる.
  • Mは適当にp,qを選んでn'=p'q'とする. r'=n-n'とする. r'が負になったらやりなおし.
  • MはVに「自分がPであること」を以下で認証させる.
    • 共通入力をIDとする
    • Mは(n',r')をVに送る
    • Mはn'の素因数分解(p',q')を知っているので, 上のPOKを行う
    • VはMをPであると認証する

これを防ぐにはrを使わなければいい.

なおノードIDにrという要素が必要な理由は、大きく分けて2つである。
理由1:たまたまノードID=nでユーザAとユーザBが一致した場合、ユーザBはユーザAの成りすましが可能である。(ユーザAもユーザBもnを素因数分解できるため。ちなみにある数Rは一意に素因数分解できることが知られている)
理由2:ノードID=nとすると、ノードIDは相当大きな数になってしまい、ハッシュ空間にノードIDを均一に存在させる事が難しくなる。

理由1はユーザAとユーザBで作った素数の積nがたまたま一致した場合を言っている. しかしこの確率はkが十分大きければnegligibleなのであまり考える必要はない.
理由2はナンセンスだと思う. ハッシュ空間がHの値域のことだとしたらそんな偏るようなハッシュを使うなという話になる.
またハッシュを使わずにID=n+rにした場合は, 攻撃者Mは盗聴する必要無しになりすまし可能. ハッシュに入れた場合でも上の攻撃方法により一度盗聴すれば成りすまし可能. 以上より, rを使うのは欠点になっている.

もっと簡単な方法

Vは「IDがPのもの」というのはどこで分かるのだろうか? この問題に対する解決法が全く無いのでこれを認証と呼ぶことは出来ない.
[1]ユーザBはユーザAがIDを保有していることが分かっている。ここで、ユーザAはユーザBにn,rを渡す。 ユーザBはユーザAがIDを保有していることが分かっているということが, すでにPKI等を要求している.

一般的な攻撃方法

認証しか行わないのなら, Man-in-the-Middle attackの餌食. nを使って共通鍵を暗号化(KEM), のちそれをPに送信し共通鍵を共有するのなら安全かも.

ノードIDを毎回変更する場合

これはこれで変. やっぱりVは「IDがP」のものということを確認できない. (より困難になっていると思う.)

まとめ

今回提案したプロトコルを使えば、認証の際にPKIPGPを使う必要がない。非常にシンプルなプロトコルなので、実装も容易である。簡易なP2Pの認証方法として期待できそうだ。

素直にPKIPGPを使った方が良いと思いました.
改良出来たらSCIS 2007で是非発表を.