最近公開されたGrinの脆弱性CVE-2020-15899↓について見てみる。
https://github.com/mimblewimble/grin-security/blob/master/CVEs/CVE-2020-15899.md
Cuckoo cycle
GrinはDual Proof of Workという仕組みを採用している。これは1つはASICフレンドリーなPoWアルゴリズム、もう1つはASIC耐性があるPoWアルゴリズムの2つのアルゴリズムを採用したPoW。後者のASIC耐性のあるPoWアルゴリズムとしてGrinが採用しているのがCuckoo cycleで、今回その実装に脆弱性が発見された。※ ちなみにCuckoo cycle自体に脆弱性があるという訳ではない。現に、C++のGrinの実装であるGrin++にはこの脆弱性は無い。
https://github.com/mimblewimble/grin/blob/master/doc/pow/pow.md
折角なのでまずCuckoo cycleがどんなアルゴリズムなのか↑見てみよう。
Cuckoo cycleは与えられたメッセージに対して、ランダムな2部グラフを生成する。2つの部分集合の中にはそれぞれN個のノードがあり、一方のノードからもう一方のノードを結ぶ線をM個のエッジで構成される(同じ部分集合内のノード間を結ぶエッジは存在しない)。
例えば以下のグラフは上半分の偶数を持つ部分集合と、下半分の奇数を持つ分集合の2部グラフになる。
これにランダムにエッジを追加したものが↓
この2部グラフは8個のノードと4個のエッジを持っている。つまりN = 8
およびM = 4
で、8✕4
のグラフ。
サイクル(cycle)というのは、2部グラフにおいてあるノードから始まったエッジを辿っていきそのノードで終了するような循環するノードとエッジの関係で、↑のグラフには存在しない。サイクルが発見できるグラフは以下のようなグラフで、以下では赤線が長さ4のサイクルになる。
このグラフには以下の特徴がある。
- ↑のようにノードの数
N
に対して、エッジの数M
を調整することで、サイクルを見つける難しさや、グラフにサイクルが存在する確率が変動する。ノード数N
に対してエッジ数M
を増やせば、つまりM/N
の値が大きいほど、サイクルが存在する確率が高くなる。 - ↑のような小さなグラフであれば、ある長さのサイクルが存在するかどうvか判断するのは簡単だが、グラフが大きくなるにつれて、サイクルの検出は難しくなる。
Cuckoo cycleのパズルは↑の2部グラフを使って長さ42のサイクルを見つけることにある。このサイクルを見つけるためには、2部グラフの要素を全て保持するメモリが必要になるので、これがASIC耐性になっている。マイニングにおいては、具体的に以下の計算を行う↓
- 新しいブロックのブロックヘッダーを生成する。
- ブロックヘッダーのハッシュ値を計算する。
- 以下のパラメータを使って、Cuckoo graphジェネレーターを初期化する。
- ブロックヘッダーのハッシュ値をSIPHASH関数のキーとして使って、エッジを生成するため、各ノードの位置のペア=エッジインデックスのペアを生成する。
- コンセンサスルールで決められているグラフのサイズ(↑の
N
の数) - コンセンサスルールで決められている↑の
M / N
比(グラフに解が存在する確率)を表す値(この値はM = N/2で固定されている)。
- Cuckoo Cycle検出アルゴリズムがグラフ内で長さ42のサイクルを見つける。
サイクルを見つける難易度を調整するのに、グラフのサイズN
と解の存在確率M / N
はコンセンサスルールにより固定されているので、同じルールで動作している限り、難易度の調整はBlake2bハッシュ値のターゲット難易度を使って行われるだろう。
CVE-2020-15899の内容
Grinはこれまで6ヶ月毎に3回のHFを行っており、都度Cuckoo cycleのパラメータが変更されている。ちなみに3回目のHF3はつい最近2020年7月16日にアクティベートされたばかりだ。
脆弱性はHF2を行った際のCuckaroom29で導入された。Cuckaroom29のグラフはのノードとのエッジを持つ。エッジインデックスの生成処理は↑と少し違ってて、ペアを作るのに2回SIPHASH関数を実行するのではなく、エッジインデックスに対してSIPHASH関数を実行し、上位32bitおよび下位32bitのワードをそれぞれマスクして生成している。これを導入したPRが#3136で、問題のソースがcore/src/pow/cuckaroom.rs
。
このソースは、実は前のCuckarood29の実装core/src/pow/cuckarood.rs
から作られたもの。前のCuckarood29のグラフは2部構成で、個のノードを個の2つのグループに分割しているが、Cuckaroom29のグラフは個のノードが単一のグループ構成になる。この設定の調整を忘れたため、Cuckaroom29の実装はノード数がに制限されてしまった。つまりノード数が本来意図した数の半分になり、実質ハーフCuckaroom29パズルになる。そしてこれに気付いたのが、HF3の準備で新しい実装Cuckarooz29を用意してたタイミング。
ノード数が半分ではあるが、一応動作はする。28番目のビットが存在するかしないかで。このため、おそらく28番目のノードへのエッジが作られるプルーフを持つブロックは、これまで作られてなかったんだろう。マイナーはちゃんとCuckaroom29として計算していたんだろうけど、Cuckaroom28のグラフとして計算すれば2倍のスピードで計算が可能になる。さらに、上記の下、1,000倍を超える大幅な高速化手法も提案されている。
修正
気付いたのがHF3を控えたタイミングであったため、HF3で新しいCuckarooz29に切り替われば問題無いように思われたが、攻撃者が効率的なHalfCuckaroom29パズルのソルバーを開発し、HF2がアクティベートされたタイミングからのチェーンの履歴を書き換え、HF2〜HF3がアクティベートされるまでの間の累積の難易度が既存のチェーンより高いチェーンを構成すると、期間6ヶ月という大規模なチェーンの再編成が発生する可能性があるため修正された。
修正はHF3のリリースまでの間に、PoWコードの大規模なリファクタリングに紛れるよう偽装されて行われた。以下発見から修正、展開までの流れ。
- 2020年6月6日:Grinセキュリティチームに脆弱性が通知され、暗号化されたチャットグループがJohn Trompで作成される。
- 2020年6月7日:Cuckaroozのバグ修正がPR https://github.com/mimblewimble/grin/pull/3343 で導入された。これによりCuckaroomのバグはプロダクションでもそのまま残っている。
- 2020年6月10日:監視ノードによってプロダクション環境で悪用が検出された場合の緊急行動計画に合意。
- 2020年6月17日:プランAとしてどのアプローチを取るか合意。修正はHF3を対象とする。@tromp は最終的な4.0.0バイナリがリリースされる少し前に、全ての検証コードのリファクタリングに修正を組み込む。
- 2020年6月24日:全ての検証コードの大幅なリファクタリングで偽装されたバグ修正がPR https://github.com/mimblewimble/grin/pull/3365 で導入される。
- 2020年6月26日:@antiochpと@quentinlesceller はPRとそのタイミングについてプライベートで質問し、PRの背景にセキュリティ関連の課題があることを認識するが、詳細は知らせられない。PRがマージされ、修正は同日リリースされたv4.0.0-rc1に含まれる。
- 2020年7月16日:ブロック高786,240で、ネットワークがv4.0.0に正常にアップグレードされCuckaroomの脆弱性を修正するコンセンサスルールが適用される。
- 2020年7月24日:Grinコアチームは、修正されたGrinのPoWの重大な脆弱性が間もなく公開されることを通知する。
- 2020年7月27日:ドキュメントの公開による脆弱性の開示。