2017年2月に発覚したMonero（正確にはCryptoNoteのプロトコルを採用している暗号通貨）でコインを無限生成できる脆弱性について、原因が曲線の特性に起因するもので興味深かったので調べてみた。
この脆弱性自体は実際にMoneroでは悪用されることなく、表向き別の目的でパッチが当てられ、問題は回避されている。
脆弱性の内容
MoneroのベースとなっているCryptoNoteは匿名通貨を実装するプロトコルの1種で、中でも特徴的な技術がリング署名。トランザクションを作成する際に、自身が所有するUTXOの他に、そのUTXOと同じ量のコインを持つ他人のTXO*1をブロックチェーンから複数選択し（現在は最低10個）、それを実際に使用する自分のUTXOと一緒にインプットにセットする。この時点でインプットにセットしたTXOの内、自分が秘密鍵を知っているのは1つだけで、その秘密鍵とインプットにセットしたTXOの公開鍵のセットを使ってリング署名を生成する。こうすることで、インプット内のいずれかのTXOが使用されたのは分かるが、実際にどのTXOが使用されたのかは分からず、これによって送信元の匿名化を図る。
ただ、このままだとどのインプットが使われたか分からず、UTXOの二重使用が発生する可能性がある。そのため、インプットには実際に使用するUTXOに紐づく秘密鍵から生成したキーイメージがセットされ、リング署名のインプットの１つにもなる。トランザクションインプット内のキーイメージがこれまで使用されていないかどうかチェックをすることで、二重使用を防ぐ仕組みになっている。
キーイメージは、秘密鍵をx、対応する公開鍵をP = xGとした場合、I = x * hashp(P)で計算される。hashp()は公開鍵から決定論的にランダムな公開鍵を生成するハッシュ関数。
今回の脆弱性では、このキーイメージが特別な方法で変更することができたため、それによって二重使用が可能な状態だった模様。
では具体的にどうやってキーイメージを変更するのか？という点だが、これは↓のサイトが詳しい。
曲線Ed25519の特性
CryptoNoteはEd25519の曲線を使用している。Ed25519の特性の１つは、曲線上の点の数（曲線の位数）がベースポイントGによって生成された群内の点（群の位数）より多いという点。群の位数は素数ｌ = 2^252 + 27742317777372353535851937790883648493で、曲線の位数は8*lとなる。曲線の位数と群の位数の比はcofactorとして知られており、Ed25519の場合は8。ちなみにBitcoinで使われている曲線secp256k1のcofactorは1なので、群の位数と曲線の位数は等しい。
- cofactor == 1の場合、部分群は曲線全体で、任意のゼロ以外の点が生成点となる。曲線の方程式を満たす点はすべて部分群の一部。
- cofactor != 1の場合、素数位数の部分群は曲線の厳密なサブセットで、点を考慮すると、曲線の座標が方程式と一致するか検証するだけでは、点が適切な部分群にあることを保証するには不十分。さらに位数がrの倍数でない点が存在する。cofactor = 8の曲線25519で起こり、その場合それを使用するプロトコルでいくつかの注意が必要になる。例えば曲線25519でDiffie-Hellman鍵交換をする場合、Diffie-Hellmanの秘密鍵は8の倍数を選択する必要がある。これにより点が確実に部分群に格納される。
cofactorは曲線上に低位の群が存在すること示している。例えばPを26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05で表される点とし、Pから8*P = 0を意味する位数8の（ユニークな）群を生成する。低位数の曲線上にはわずかな点しか存在しない。その点を見つける１つの方法は、a*lの位数で曲線上にランダムな点を生成し、その点にIを乗算して位数1 <= a <= 8の点を得る。一方、CryptNoteでキーイメージを生成する際に使用するハッシュ関数hashpは結果を出力する前に8を乗算して、結果の点が素数位数群にあることを保証する。
攻撃と解決
攻撃者がコインを持っており、キーイメージI = x*hashp(P)を使ってそのコインを使用するための通常のワンタイムリング署名を作成できると仮定する。普通にIを使えば攻撃者が持っているコインを使用できるが、コインを使用後さらにIとは別のキーイメージI' = I + Lを生成して同じコインを使用できる。ここで、Lは位数oの下位の点である（曲線上には存在するが群の点ではない）。
キーイメージの検証は元々s*hashp(P) + e*Iを評価するようになっている。
なので細工するとしたらIの部分。oがeで割れる場合（e = e'*o）、e*I' = e*I + e'*o*L = e*Iとなり、Iと同じ方法でI'を使って有効な署名を作成することができる（ただしメッセージmは今度はI'にコミットする必要がある）。つまり、曲線の方程式を満たす点は存在するが、Ed25519で指定された群には含まれない（部分群内にある）点を使用する。これらの点のいくつかは8で割り切れる位数の群にある。これらの点の１つがキーイメージとして選択されていて、ランダムオラクル値eが部分群の位数の倍数である場合、キーイメージの検証は約分のため正しい点に戻すようマップされるようになる。そのため有効なキーイメージに、群の位数が8で割り切れる点を加算すると1/8の確率で本当のキーイメージと同じ点に写像されるeを入手できる。
ちなみにByteCoinではこれをはるかに効果的な方法で悪用された模様。攻撃者は低位キーイメージIを生成するのに低位公開鍵Pを使用した。曲線上には8個の低位点しかないので（CryptoNoteでは同じ点の複数の表現を禁止しているため）、この攻撃は１つのブロックチェーン上で8回実行できる。
Moneroで実装された修正は、キーイメージが素数位数群内に存在する点であることを保証するためにl*I = 0をチェックすることで、各キーイメージIが素数位数l群を生成することを検証する。実際に、l' != lを持ちl*I = 0ならば、lはl'で割り切れなければならいが、これはlが素数であるため矛盾する。この修正による追加コストは、トランザクションインプット毎に1回のスカラー演算ですむ。
というのが2017年の無限コイン生成の脆弱性の内容。
Bitcoinのsecp256k1と違い、cofactor > 1の場合、群の位数と曲線の位数が異なり、曲線上に低位の群が存在して↑のような考慮事項が発生すると。問題はEd25519自体の脆弱性とかではなく、キーイメージを生成する際にEd25519の場合は必要な位数の検証が抜けていたという点で、そういう安全性の評価までちゃんとする必要があるんだろうけど、中々難しいものもあるので、secp256k1のようなcofactor1の曲線を使用するの方が無難な気もする。
*1:TXOと記載しているのは、未使用でも使用済みでも良いため。参加ノードからは実際に使用済みかどうかは分からない（但し、今は不可能だがmixinするインプットが0の場合は使用されたインプットが明確になる）。
