GG18/20で発見された脆弱性CVE-2023-33241

GG18のプロトコルについて、ざっと確認したので↓

techmedia-think.hatenablog.com

秘密鍵を抽出できるという脆弱性 CVE-2023-33241の内容について見ていく。ペーパーは↓

https://eprint.iacr.org/2023/1234.pdf

攻撃を成功するためには、攻撃者は署名プロセスに関与できる必要がある（自分が署名者の1人となっているか、署名者の1人を制御可能な状態にあるか）。

Paillier暗号

まず最初にPaillier（ペイエ）暗号について簡単に触れておく。Paillier暗号は加法準同型性のある暗号方式で、暗号化したデータ同士の加算、暗号化したデータへのスカラー値の乗算などが可能。

鍵生成

鍵生成は以下の手順で行われる。

2つの素数p, qをランダムに選択し、N = pqとする
p - 1とq - 1の最小公倍数λ = lcm(p-1, q-1)を計算する（λはカーマイケル関数）
1〜N²の範囲内のランダムな整数gを選択する。
関数L(x)を ${L(x) = \frac{x - 1}{N}}$ とし、 ${\mu = (L(g^{\lambda} \mod N^{2}))^{-1} \mod N}$ を計算する（逆元が存在しない場合はgを再選択）
結果、公開鍵が（N, g）で対応する秘密鍵が（λ, μ）

暗号化

メッセージmの暗号化は以下の手順で行われる（mは0≦ m < nの範囲）

0〜Nの範囲でランダムな整数rを選択する。
暗号文 ${c = g^{m} \cdot r^{N} \mod N^{2}}$ を計算する

復号

暗号文cからメッセージmを復号する手順は、

${m = L(c^{\lambda} \mod N^{2}) \cdot \mu \mod N}$ を計算する

GG18/20での攻撃

GG18/20については、2021年に悪意ある攻撃者により一時的なシークレット値のランダム性の漏洩を可能にする攻撃が報告され（ただ、実際に攻撃を仕掛けるのには役に立たなかった模様）、それによりプロトコルのパラメータが変更されている。変更されたのはMtAを実行する際のβのサイズで、1〜Nの範囲内で選択したものが1〜q⁵内*1で選択されるよう変更されている（元のペーパー、更新されたペーパー）。

これに伴い、以下の2つの攻撃手法が報告されている。

攻撃手法	対象	βの範囲	必要な署名の数
6ix1een	新	1〜q⁵（約1024 bit）	16個
Death by 1M Cuts	旧	1〜N（約2048 bit）	約 ${(参加者数 - 1)\cdot 10^{6}}$

更新されたβのサイズの方が攻撃リソースが低いみたい。

攻撃はいずれも参加者の各ペア間で実行されるMtAの実行をターゲットにしている。

MtAで使用するPaillier公開鍵Nの値を1つの大きな素数qと16個の16 bit長の小さな素数 ${p_1, p_2, ..., p_{16}}$ を乗算した値にする。つまり、

${N = p_1 \cdot p_2 \cdot ... \cdot p_{16} \cdot q}$

↑のPaillier暗号の鍵生成時の素数pを16個の素数で構成するようにしている。

攻撃者はMtAでPaillier暗号を用いる際に、 ${k = N/p_i}$ としこれを暗号化して送信する。

ここまでは↑の2つの攻撃において共通。

6ix1een

6ix1een攻撃では、合計16回の署名を試行する。つまり暗号化した ${N/p_i}$ を16回（ ${p_i}$ は16個あるので、毎回異なる ${p_i}$ を）送る。

↑のブログの説明に合わせて書くとaの代わりに ${c_A = Enc_{E_A}(N/p_i)}$ を計算し、相手に送信する。相手から受け取ったデータを復号した値は ${\alpha = b \cdot N/p_i + \beta'}$ ととなる。さらに、 ${\beta' \lt N/p_i}$ であるため、 ${b \mod p_i \approx \alpha / (N / p_i) }$ 、つまりαの値に最も近い ${N / p_i}$ の倍数が ${b \mod p_i}$ の値を漏洩する。

これを16回繰り返すと、異なる小さな素数を法とした16個の ${b \mod p_i}$ が得られ、中国の剰余定理を使ってシークレット値を再構築できるということみたい。

↑の手順により入手できるのは参加者1人のシークレット値になるので、参加者の数分この攻撃を行う。

厄介なのが、細工したデータによって生じたオフセットを使ってデータを修正することで、署名プロセスを正常に続けることができるステルス性があるということ。

Death by 1M Cuts

この攻撃は、βパラメータが1〜Nから選択される旧バージョンのGG18/20を対象にした攻撃。この場合（βパラメーターがPaillier公開鍵とほぼ同じサイズになる）パラメーターのサイズ的に6ix1een攻撃は機能しないため、署名プロセスが成功したか失敗したかの情報を元に情報を漏洩させる手法を使用している。

攻撃者は復号して ${\alpha = b \cdot N/p_i + \beta'}$ を入手すると、 ${b \mod p_i}$ のランダムな推測値をyとして、 ${\alpha = \alpha - y\cdot N/p_i \mod N}$ とαの値を更新して、プロトコルを継続する。

つまり、6ix1een攻撃のように ${b \mod p_i}$ の値を推測できないので、代わりにランダムな推測値 ${y \in \mathbb Z_{p_j}}$ を使って、署名プロセスを継続し、生成された署名が有効であれば、 ${y = b \mod p_i}$ であると判断するというもの。

この攻撃を繰り返し、異なる小さな素数を法とした16個の ${b \mod p_i}$ が得られれば、6ix1een攻撃と同様、中国の剰余定理を使用してシークレット値を再構築する。

ただ、攻撃に必要な署名の数が多く（ ${(参加者数 - 1)\cdot 10^{6}}$ ）ハードルは高め。また、攻撃の性質上6ix1een攻撃のようなステルス性はない。

範囲証明の細工

もともとMtAプロトコルでは、最初にアリスが選択したaを暗号化した ${Enc_{E_A}(a)}$ を送信する際に、この値が ${a \lt q^{3}}$ であることを証明する範囲証明を提供する必要がある。ところが、上記の攻撃の場合、暗号化するデータ ${N/p_i}$ は、q³よりも巨大なデータであるため、当然この範囲証明でエラーになる。GG18/20を実装していたライブラリの中には、当初この範囲証明を実装していなかったものもあるようで、その場合、当然上記の攻撃がそのまま可能になる。

範囲証明が実装されている場合は、これをすり抜ける必要がある。脆弱性を報告しているペーパーでは、Protocol 4.7が該当する範囲証明のプロトコルになってて、プロトコル内のチャレンジの値がNの約数になるよう総当りの計算をすることで不正行為を可能にするとのこと。

ただ、GG18のペーパーの範囲証明のプロトコル（Appendix A.1）とはプロトコルの内容が違うのが何故だろう？見てるところが違う？

対応

↑の攻撃は、Paillier暗号の鍵生成において、pとqが半素数で構成されていないことに起因する。そのため、Fireblocksのレポートでは、この攻撃への緩和策として、鍵生成プロセスで適切なゼロ知識証明を使用して、悪意ある鍵生成を検知できるようにすることを推奨としている。

具体的にどういう証明を作るんだろう？

*1:qは楕円曲線のサイズ

Develop with pleasure!

福岡でCloudとかBlockchainとか。