Ed25519の3ラウンドN-of-N集約署名アルゴリズムの解説

Table of Contents

はじめに

本稿は主にドキュメント[1]の紹介です。

単純な Ed25519署名

鍵生成

RFC8032に従った単純なEd25519署名アルゴリズムは以下の通り。

公開パラメータ $(\mathbb{G}, q, B)$ とする。ここで $\mathbb{G}$ は楕円曲線によって定義される群、qはその群の位数、Bは群の生成元とする。
鍵ペアを生成するために、アリスはランダムなシークレット $\text{sk}$ を有限体上から選び、SHA-512を通してハッシュし、拡張秘密鍵を入手する。

拡張秘密鍵は以下のように32バイトずつの x' と prefixに分けられる。以下(3)でx'の方はさらにバイナリで256ビットにて表現している。

(1) h = SHA-512(sk) = h[0], h[1], ..., h[63] = x' || prefix
(2) prefix = h[32], h[33], ..., h[63]
(3) x' = h[0], h[1], ..., h[31] = $b_{255} b_{254} ... b_2 b_1 b_0$

秘密鍵 xは x' のうち上位2ビットを $b_{255} = 0, b_{254} = 1$ とし、下位3ビットを $b_2 = b_1 = b_0 = 0$ としてセットしたものになる。すなわち、秘密鍵が必ず255ビットかつ8の倍数になるようにしている。

ここで、この秘密鍵 xに対応する公開鍵A は生成元Bに対して A = xB で表される。

署名

アリスがメッセージMに対して署名するときには、まず以下のようにプレフィクスを用いてrの値を計算する。

(4) r = SHA-512(prefix || M)

この rに対して楕円曲線上の点Rを R = (r mod q) Bとする。

さらに k = SHA-512(R || A || M) としてアリスは以下を計算する。

(5) s = r + kx

最終的にアリスは署名 (s, R) を出力する。

検証

署名を (s, R)を公開鍵AとメッセージMに対して検証するためには、以下が成立するかどうかを確認する。

(6) 8sB = 8R + 8kA

ここで、kは検証者も R, A, M から導出することができることに注意する。

なおここで8を掛ける理由については[4]を参照。

Ed25519 集約署名

[2]のセクション5.1.の手法を使って構成する。
元の構成ではシュノア署名と非特異楕円曲線を使っている。Ed25519署名アルゴリズムはcurve25519という楕円曲線を使ったシュノア署名の一種であることから、元のアルゴリズムを適切に調整する。

Ed25519集約署名スキームはn人の参加者が共同でメッセージに署名を行うプロトコルである。このプロトコルでは3つのハッシュ関数 $H_0, H_1, H_2 : \{0, 1\}^* \rightarrow \mathbb{Z}_q$ を使う。これらのハッシュ関数は、単一のSHA-512ハッシュ関数に対して（適当なプレフィクスを追加するなどして）定義域を分離することで構成できる。

公開パラメータに関しては単純なEd25519署名と同様に $(\mathbb{G}, q, B)$ とする。

鍵生成

それぞれの参加者は skを選び、秘密鍵xと公開鍵Aを、単純なEd25519署名のケース(1)(2)(3)と同様に計算する。

鍵集約

集約公開鍵 apk は以下のように計算される。

$\text{apk} = \sum_{j=1}^{n} H_1 (A_j, \{A_1, ..., A_n\}) \cdot A_j$

署名

署名は対話型の3ラウンドプロトコルになる。

ラウンド1

ラウンド1はコミットメントラウンドになる。参加者iは256ビットの乱数zを署名のプロトコル実行ごとに生成し（プロトコル実行をまたいでの共有はできない）、 $r_i$ を以下のようにして計算する。この手順は単純なEd25519署名の手順(4)とは異なりzが追加されていることに注意する。

(7) r = SHA-512(h[32], h[33], .., h[63] || M || z) = SHA-512(prefix || M || z)

楕円曲線上の点 $R_i$ を $R_i = (r_i \ \text{mod}\ q) B$ とする。

$t_i = H_2(R_i)$ とし、 $t_i$ を $A_1, ..., A_n$ に対応する他の参加者に送信し、他の全ての $j \neq i$ なる参加者から $t_j = H_2(R_j)$ が送信されてくるのを待つ。

ラウンド2

$R_i$ を $A_1, ..., A_n$ に対応する他の参加者に送信し、他の全ての $j \neq i$ なる参加者から $R_j$ が送信されてくるのを待つ。 $j = 1, ..., n$ に対して $t_j = H_2(R_j)$ が成り立つことを確認する。

ラウンド3

全ての参加者i (i = 1,...,n)が以下を実行する。

$A_1, ..., A_n$ を使ってapkを計算する。
$a_i = H_1 (A_i, \{A_1, ..., A_n\})$ を計算する。
$\hat{R} = \sum_{j=1}^{n} R_j$ と $k = H_0(\hat{R}, \text{apk}, M)$ を計算する。
$s_i = r_i + k \cdot x_i \cdot a_i \ \text{mod} \ q$ を計算する。
$s_i$ をその他全ての参加者に送信し、その他全ての参加者から $s_j (j \neq i)$ が送信されてくるのを待つ。
$s = \sum_{j=1}^{n} s_j$ を計算し、 $(\hat{R}, s)$ を最終的な署名として出力する。

検証

検証は単純なEd25519署名の(6)と同様である。

考察

ハッシュ関数を3種類別のものにしているのは他のラウンドで使われた値が使い回されることによる攻撃ベクトルを防ぐためと理解しました。
また、(7)でzという乱数（ナンス値）を新たに導入しているのは以下の理由です。

もしもこの署名プロトコルにおいて、同一のメッセージに対する署名プロトコルを複数回実行させることができるのであれば（例えば、最後に攻撃者が他の参加者に渡すsの値を無効なものとすることで最初の署名プロトコルを意図的に失敗させ、次の、同一のメッセージに対する署名プロトコルを同じパラメータで再試行させることが可能ならば）、攻撃者は2回目のプロトコルにおいてナンス再利用を行わせる攻撃が可能になり、結果的に全体の鍵を盗むことができてしまう。

2-of-2 の署名の場合の、具体的な攻撃手順は以下のとおりです。

攻撃手順

参加者2を攻撃者、参加者1を被害者とする。

被害者と攻撃者が協力してラウンド3まで進み、被害者は $s_1 = r_1 + H_0(R_1 + R_2, \text{apk}, M) \cdot x_1 \cdot a_1$ となる署名値を送信する。攻撃者は無効な署名値 $s_2$ を送信して署名ラウンドを失敗させる。
攻撃者は被害者に再度の署名プロトコルを要求する。攻撃者は意図的に前回のプロトコルと異なる適当な乱数 $R_2' \neq R_2$ を使う。正直にプロトコルに従う被害者は前回と同じ乱数 $R_1$ を生成してしまう。結果として、被害者は $s_1' = r_1 + H_0(R_1 + R_2', \text{apk}, M) \cdot x_1 \cdot a_1$ となる署名値を送信してしまう。
攻撃者は $s_1, s_1'$ に関する上記の式を $r_1, x_1$ に関する二元連立方程式として解き（他の値は全て公開されている）、被害者の秘密鍵を入手する。

当初はナンス値rをメッセージと固定シークレット値に依存した値にしていたため、このナンス再利用攻撃が可能になっていました。現在はrをプロトコルの実行ごとに異なる値zを加えて変化させることでこの脆弱性を回避する設計になっています。

このように単純なプロトコルの拡張であっても、複数参加者がいる環境では新たな攻撃ベクトルが発生することがあるため注意が必要です。

EdDSA (Ed25519)の応用については過去にも [3] などで解説しているので、興味があればそちらも見てみてください。
本プロトコルを2ラウンドで行う方法については[5]を参照してください。