閾値ECDSA署名プロトコルGG18 - Develop with pleasure!

GG18/GG20の脆弱性CVE-2023-33241が今年の夏くらいに公開されていた模様↓

www.fireblocks.com

GG18/GG20は閾値ECDSA署名をサポートするMPCプロトコルで、ブロックチェーン界隈のMPC系のウォレット実装でよく利用されているらしい。CVE-2023-33241は、この2つのプロトコルにおいて、秘密鍵を抽出することができてしまうという脆弱性。この2つ以外に、Lindellの2P-ECDSAも対象っぽい。

脆弱性を確認する前にGG18の中身をまず簡単に調べてみた。Lindellの2P-ECDSAについては、以前書いた記事がある。

GG18

脆弱性の内容の前にまずGG18がt-of-nの閾値ECDSA署名を生成するプロトコルについて簡単にみておく（簡略化してるので詳細はペーパー参照）。

鍵生成

まず最初に参加者全員で鍵生成プロトコルを実行して、各参加者がそれぞれ鍵のシェアを持ち閾値署名が可能になるようFeldmanのVSS（検証可能な秘密分散法）を使用して鍵生成を行う*1。この辺りの仕組みは他のプロトコルでもよく使われる手法。Paillier暗号*2の鍵が登場するのが少し異なるポイントだけど、これを利用するのは署名フェーズ。

参加者の鍵ペアを ${P_i = u_iG}$ とすると、具体的な手順は↓

各参加者は自身の公開鍵 ${P_i}$ のコミットメントと、Paillier暗号の公開鍵 ${E_i}$ をそれぞれ交換する。
全参加者は、コミットメントの交換後に、コミットされた公開鍵でデコミットし、公開鍵 ${ P = \sum P_i}$ を計算する。つまり、Pは全参加者の公開鍵をすべて加算したもの。対応する秘密鍵は全参加者の秘密鍵を合算した値（ ${sk = \sum u_i}$ ）
続いて、各参加者は、FeldmanのVSS（検証可能な秘密分散法）を使って、自身の秘密鍵と新たに選択したt − 1個のシークレット値 ${a_{i, j}}$ から、t - 1次の多項式 ${p_i(x) = u_i + a_{i, 1}x + a_{i, 2}x^{2} + ... + a_{i, t - 1}x^{t-1} \mod q}$ を構築する*3。ここで、tは閾値。
続いて、各参加者のIDでその多項式を評価し、対象のIDのユーザーにその評価値 ${p_i(ID)}$ をシェアとして共有する。
次に自分が選択した ${a_{i, j}}$ について、 ${A_{i,j } = a_{i, j}G}$ を計算し、他の参加者に送信する。
自分が受け取ったシェアが正しいか、 ${p_i(ID)G = P_{i} + \sum_{j=1}^{n} ID^{j} A_{i, j}}$ が成立するか検証する。

ここまでの計算で、各参加者は以下の秘密鍵のシェアと公開鍵のシェアを持っていることになる。

${x_i = \sum p_i(ID) = sk + \sum ID^{j} a_{i, j}}$
${X_i = P + \sum ID^{j} A_{i, j}}$

つまり、ラグランジュ補間を利用すれば、公開鍵とそれに対応する秘密鍵を復元することができる。

最後に、秘密鍵のシェアとPaillier暗号の公開鍵 ${E_i}$ に対応する秘密鍵を持っていることを証明する。

署名プロトコル

鍵生成フェーズで鍵のシェアが生成できたら、実際に閾値数のメンバーが協力すれば有効な署名データを作成することができる。具体的にはラグランジュ係数を使用して、閾値分集まれば多項式の秘密鍵のデータを用いた計算が可能になる。現在IETFで標準化が進められているSchnorr署名の閾値署名プロトコル FROSTでも同様のアプローチを採っている。

メッセージをm、ハッシュ関数をH、署名に使用する秘密鍵をx、署名に使用するプライベートnonceをkとすると、Schnorr署名は ${s = k + H(m) \cdot x}$ という計算になるが、ECDSAの場合 ${s = k^{-1}(H(m) + r.x \cdot x)}$ という計算式になり（r.xはR = kGのx座標）、単純に部分署名を加算して集約するということはできないので、工夫が必要になる*4。

Multiplicative to Additive

署名プロトコルの中で実行されるプリミティブの１つがMtA（Multiplicative to Additive）という計算。これは、乗法シェアを加法シェアに変換するためのプロトコル。例えば2人の参加者アリスとボブがそれぞれ秘密の値a, bを持っていると仮定すると、これはx = a * b mod qと考えると、aとbはxに対する乗法シェアをそれぞれ持っていると考えることができる。それをα + β = xとなるような加法シェアα、βをそれぞれアリスとボブが保持する形に変換する。

アリスはPaillier暗号の公開鍵 ${E_A}$ を持っており、aを暗号化し ${c_A = Enc_{E_A}(a)}$ と、aの範囲証明を生成し、ボブに送信。
ボブはランダムな数値β'を選択し、 ${c_B = b \otimes c_A \oplus β' = Enc_{E_A}(ab + β')}$ を計算し、bとβ'の範囲証明を生成し、アリスに送信。そして ${\beta = - \beta' \mod q}$ とする。
アリスは ${c_B}$ を復号することで ${\alpha = ab + β' \mod q}$ を入手する。

この結果、 ${\alpha + \beta = ab + \beta' - \beta' = x}$ となる加法シェアα、βをアリスとボブがそれぞれ保持した状態になる。

署名生成

署名はt人いれば完成できる。ここで、各参加者が保持している秘密鍵のシェア ${x_i}$ とラグランジュ係数 ${\lambda_i}$ を乗算した値を ${w_i = x_i \cdot \lambda_i}$ とする。署名生成のプロトコルは↓

t人の参加者はランダムな値 ${k_i, \gamma_i}$ を選択し、そのコミットメントを送信する。そしてこれらの値と↑のwを使用して計算される値を ${k \cdot \gamma = \sum_{i,j \in t} k_i \gamma_j \mod q}$ および ${k\cdot sk = \sum_{i,j \in t} k_iw_j \mod q}$ とする。
続いて、参加者iとjのペアは、↑のおよびについて、それぞれMtAのシェア変換プロトコルを実行することで、シェアはおよびのような加法シェアに変換される。各参加者は、以下をセットする。
- ${\delta_i = k_i \gamma_i + \sum_{j \neq} \alpha_{i,j} + \sum_{j \neq i} \beta_{i, j}}$
- ${\sigma_i = k_i w_i + \sum_{j \neq} \mu_{i,j} + \sum_{j \neq i} v_{i, j}}$
各参加者は、 ${\delta_i}$ を共有し、 ${\delta = \sum \delta_i = k \gamma}$ を得る。
1で送信したコミットメントをデコミットして ${\Gamma_i = \gamma_iG}$ を入手する。 ${\Gamma = \sum \Gamma_i}$ であるため、 ${\delta^{-1} \Gamma = (\gamma \cdot \gamma^{-1} \cdot k^{-1} )G = k^{-1}G = R}$ を計算することでECDSA署名に用いるPublic nonce Rを得ることができる。ここでRのx座標をrとする。
各参加者は、 ${s_i = H(m)k_i + r\sigma_i}$ を計算し、コミット、開示、検証のプロセスを経て共有する*5。これを全部加算すると ${\sum s_i = k(H(m) + r\cdot sk)}$ という値になり、(r, s)がPKとmに対して有効なECDSA署名となる。

Paillier暗号を用いたシェアの変換を利用して、最終的に有効なECDSA署名を生成できるようにしている。

GG20

GG20は、

署名プロセスが不正などを含み中断した場合に、対象者を識別できるようにし、
事前処理フェーズを設けてほとんどの計算、通信を行うことでメッセージ署名時の通信ラウンドを削減

するといった改良が加えられているみたい。ただ、MtAの実行やPaillier暗号を使った処理はGG18と同じなので、同様に今回の脆弱性の影響を受けるということみたい。

*1:全参加者が並行してFeldmanのVSSを行い結果を集約するのがPedersenのDKG。FeldmanのVSS単体だと共有シークレットを知るディーラーが存在するが、PedersenのDKGの場合は誰も共有シークレットを知らない

*2:Paillier暗号は、加法準同型性のある暗号化方式で、例えばメッセージ ${m_1, m_2}$ を暗号化したデータ ${c_1 = Enc(m_1), c_2 = Enc(m_2)}$ から、暗号化したまま ${c_1 \oplus c_2 = Enc(m_1 + m_2)}$ を計算でき、メッセージ ${m}$ を暗号化したデータ ${c = Enc(m)}$ に対して任意のスカラー値sを暗号化したまま乗算し、 ${s \otimes c = Enc(s * m)}$ の暗号データを計算することができる。以前書いたLindellの2P-ECDSAなどでも使用されている。