安全でない (と思われる) 認証方式について
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という要素が必要な理由は、大きく分けて２つである。
理由１：たまたまノードID＝nでユーザAとユーザBが一致した場合、ユーザBはユーザAの成りすましが可能である。（ユーザAもユーザBもnを素因数分解できるため。ちなみにある数Ｒは一意に素因数分解できることが知られている）
理由２：ノード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」のものということを確認できない. (より困難になっていると思う.)
