Develop with pleasure!

福岡でCloudとかBlockchainとか。

決定性nonceを利用したMuSigの脆弱性に対処したMuSig-DN

Bitcoin Schnorr Cryptography zk

Blockstreamは以前、Schnorr署名を利用したマルチシグを構成する際にKey-Rogue攻撃への耐性を持たせる署名スキームMuSigを発表していた。Key-Rogue攻撃やMuSigの内容について以前解説した↓を参照。

goblockchain.network

techmedia-think.hatenablog.com

そんなMuSigについて、決定性nonceを利用できるようにしたMuSigの変形であるMuSig-DN（MuSig with Deterministic Nonces）というSchnorr署名スキームをBlockstreamおよびYannick Seurinが発表した↓

medium.com

ペーパーは↓

https://eprint.iacr.org/2020/1057.pdf

決定性nonceの役割

Schnorr署名やECDSAでは、署名作成時に選択するnonceの値のランダム性がとても重要になる。例えば同じnonceを使って異なる２つのメッセージに署名すると、秘密鍵が漏洩してしまう。

具体的には、メッセージm1およびm2について、同じnonce kを使ってそれぞれ下記のデータを使って署名を生成すると、

Schnorr署名の署名値sの値は、それぞれ

  • s1 = k + H(P || R || m1) x
  • s2 = k + H(P || R || m2) x

となり、署名データは（R.x, s1）と（R.x, s2）となる。nonceが同じ値であることはR.xから分かる。この場合s1 - s2を計算すると、

s1 - s2 = (H(P || R || m1) - H(P || R || m2)) x

となり、P, R, m1, m2は公知であるため、

x = (s1 - s2) / (H(P || R || m1) - H(P || R || m2))

と秘密鍵xを計算できる。

このようなことが起きないよう、RFC6979などでnonceを秘密鍵と署名対象のメッセージから決定論的に導出する仕様が定義され、決定性nonceを使用するのが主流になっている。この場合、署名対象のメッセージが異なれば必ず異なるnonceが導出されるため上記のような攻撃から保護される。

決定性nonceを利用したMuSigの脆弱性とは？

単一の鍵を使ったSchnorrであれば決定性nonceを使用するのは特に問題ないが、MuSigのようにマルチシグを構成する場合、逆に秘密鍵漏洩のリスクになる。

  • 被害者の鍵ペア： P1 = x1G
  • 攻撃者の鍵ペア： P2 = x2G
  • 署名対象のメッセージ： m
  • 被害者のnonce： R1 = k1G
  • 攻撃者のnonce：
    • R2 = k2G（1回目のセッションで使用するnonce）
    • R3 = k2G（2回目のセッションで使用するnonce）

として、攻撃者が同じメッセージで2回署名セッションを実行した場合、MuSigスキームを実行すると、

  1. L = H(P1 || P2)を計算する。
  2. X = H(L || P1)P1 + H(L || P2)P2を計算する。
  3. Public nonceは
    • １つめのセッションではR = R1 + R2
    • ２つめのセッションではR' = R1 + R3
  4. 署名値sを計算する。
    • 被害者の１つめのセッションではs1 = k1 + H(P || R || m) * H(L || P1)x1
    • 被害者の２つめのセッションでははs3 = k1 + H(P || R' || m) * H(L || P1)x1
    • 攻撃者の１つめのセッションでははs2 = k2 + H(P || R || m) * H(L || P2)x2
    • 攻撃者の２つめのセッションでははs4 = k3 + H(P || R' || m) * H(L || P2)x2

最終的な２つの署名値は（R.x, s1 + s2）と(R'.x, s3 + s4)になる。この内、被害者が計算したs1とs3について、s1 - s3を計算すると、

s1 - s3 = (H(P || R || m) - H(P || R' || m)) * H(L || P1)x1

となり、H(P || R || m)およびH(P || R' || m)、H(L || P1)は攻撃者も知る値であるため、

x1 = (s1 - s3) / ((H(P || R || m) - H(P || R' || m)) * H(L || P1))

と被害者の秘密鍵x1を計算することができる。nonce kは署名値から秘密鍵を逆算できないようにするためのものなので、↑のように（異なるメッセージのパターンでも同様に）nonceを消せる計算が出来てしまうとまずい。

MuSigにおける決定性nonceの使用の問題は自分が決定性nonceを使っていても、他の参加者が同様の導出ルールで決定性nonceを導出しているか分からない点にある。RFC6979では秘密鍵と署名対象のメッセージからnonceを導出するが、相手の秘密鍵を知り得ないため、同じルールで導出されたかをプロトコルで検出することができない。そのため逆に決定性nonceを使わずに毎回ランダムに生成する方が安全になる。

MuSig-DNのアプローチ

MuSigでも決定性nonceを安全に利用するためMuSig-DNでは、nonceが決まったルールの下で導出された値であることをゼロ知識証明を使って検証できるようにしている。

  • 各署名者はnonce keyとよばれる秘密鍵を使って署名対象のメッセージと全署名者の公開鍵のセットを入力として擬似ランダム関数Fを実行してnonce kiを導出する。
  • Public nonce Ri = kiGとそれがFで指定通りに計算されたことを示す非対話型のゼロ知識証明を生成し、他の参加者に送信する。
  • ↑のゼロ知識証明はhost keyとよばれる公開鍵を使って他の署名者が検証できるようになっている。
  • もし署名者の誰かが２つの異なるnonceを送信しチートしようとした場合、その内の１つのゼロ知識証明は無効と判定される。
  • 無効なゼロ知識証明を持つnonceに対しては自身が担当する署名値sの計算はせずプロトコルを中止する。

↑のnonceを導出するために使われる関数FがPurifyという特殊関数で、SHA256などのハッシュ関数と比べてゼロ知識証明用に最適化されている模様。Purifyは演算回路で、secp256k1のような256 bitの楕円曲線に対応したものでは2030個の乗算ゲートを持つ。

MuSig2？

↑のブログだと現在ゼロ知識証明を必要とせず2ラウンドで実行可能、また最初のラウンドの前処理により１ラウンドの最適化も可能という後継のMuSig2に取り組んでいるようなので、その発表も期待したい。