Develop with pleasure!

福岡でCloudとかBlockchainとか。

GrinのPoWアルゴリズムCuckoo cycleとその実装の脆弱性CVE-2020-15899

Grin Cryptography vulnerability

最近公開されたGrinの脆弱性CVE-2020-15899↓について見てみる。

https://github.com/mimblewimble/grin-security/blob/master/CVEs/CVE-2020-15899.md

Cuckoo cycle

GrinはDual Proof of Workという仕組みを採用している。これは１つはASICフレンドリーなPoWアルゴリズム、もう１つはASIC耐性があるPoWアルゴリズムの２つのアルゴリズムを採用した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部グラフになる。

https://github.com/mimblewimble/grin/raw/master/doc/pow/images/cuckoo_base_numbered_minimal.png

これにランダムにエッジを追加したものが↓

https://github.com/mimblewimble/grin/raw/master/doc/pow/images/cuckoo_base_numbered_few_edges.png

この2部グラフは8個のノードと4個のエッジを持っている。つまりN = 8およびM = 4で、8✕4のグラフ。

サイクル（cycle）というのは、2部グラフにおいてあるノードから始まったエッジを辿っていきそのノードで終了するような循環するノードとエッジの関係で、↑のグラフには存在しない。サイクルが発見できるグラフは以下のようなグラフで、以下では赤線が長さ４のサイクルになる。

https://github.com/mimblewimble/grin/raw/master/doc/pow/images/cuckoo_base_numbered_more_edges_cycle.png

このグラフには以下の特徴がある。

  • ↑のようにノードの数Nに対して、エッジの数Mを調整することで、サイクルを見つける難しさや、グラフにサイクルが存在する確率が変動する。ノード数Nに対してエッジ数Mを増やせば、つまりM/Nの値が大きいほど、サイクルが存在する確率が高くなる。
  • ↑のような小さなグラフであれば、ある長さのサイクルが存在するかどうvか判断するのは簡単だが、グラフが大きくなるにつれて、サイクルの検出は難しくなる。

Cuckoo cycleのパズルは↑の2部グラフを使って長さ42のサイクルを見つけることにある。このサイクルを見つけるためには、2部グラフの要素を全て保持するメモリが必要になるので、これがASIC耐性になっている。マイニングにおいては、具体的に以下の計算を行う↓

  1. 新しいブロックのブロックヘッダーを生成する。
  2. ブロックヘッダーのハッシュ値を計算する。
  3. 以下のパラメータを使って、Cuckoo graphジェネレーターを初期化する。
    • ブロックヘッダーのハッシュ値をSIPHASH関数のキーとして使って、エッジを生成するため、各ノードの位置のペア＝エッジインデックスのペアを生成する。
    • コンセンサスルールで決められているグラフのサイズ（↑のNの数）
    • コンセンサスルールで決められている↑のM / N比（グラフに解が存在する確率）を表す値（この値はM = N/2で固定されている）。
  4. Cuckoo Cycle検出アルゴリズムがグラフ内で長さ42のサイクルを見つける。
    1. サイクルが見つかると、proofのBlake2bハッシュが作成され、現在の難易度のターゲットと比較する。
      1. Blake2bハッシュ値の難易度がターゲットの難易度以上の場合、ブロックはトランザクションプールに送信され、ピア間に伝播され、次のブロックの処理に進む。
      2. Blake2bハッシュ値の難易度がターゲットの難易度より小さい場合、無効なので、別のサイクルを見つける。
    2. サイクルが見つからない場合、ブロックヘッダーのnonceをインクリメントし、タイムスタンプを更新し、新しいブロックヘッダーのハッシュ値を計算し、↑の反復を続ける。
    3. サイクルが見つからず、ループがタイムアウトすると最初からやり直して新しいトランザクションを収集し新しいブロックヘッダーを作り直す。

サイクルを見つける難易度を調整するのに、グラフのサイズNと解の存在確率M / Nはコンセンサスルールにより固定されているので、同じルールで動作している限り、難易度の調整はBlake2bハッシュ値のターゲット難易度を使って行われるだろう。

CVE-2020-15899の内容

Grinはこれまで6ヶ月毎に3回のHFを行っており、都度Cuckoo cycleのパラメータが変更されている。ちなみに3回目のHF3はつい最近2020年7月16日にアクティベートされたばかりだ。

脆弱性はHF2を行った際のCuckaroom29で導入された。Cuckaroom29のグラフは {2^{29}}のノードと {2^{29}}のエッジを持つ。エッジインデックスの生成処理は↑と少し違ってて、ペアを作るのに2回SIPHASH関数を実行するのではなく、エッジインデックスに対してSIPHASH関数を実行し、上位32bitおよび下位32bitのワードをそれぞれマスクして生成している。これを導入したPRが#3136で、問題のソースがcore/src/pow/cuckaroom.rs。

このソースは、実は前のCuckarood29の実装core/src/pow/cuckarood.rsから作られたもの。前のCuckarood29のグラフは2部構成で、 {2^{29}}個のノードを {2^{28}}個の２つのグループに分割しているが、Cuckaroom29のグラフは {2^{29}}個のノードが単一のグループ構成になる。この設定の調整を忘れたため、Cuckaroom29の実装はノード数が {2^{28}}に制限されてしまった。つまりノード数が本来意図した数の半分になり、実質ハーフ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で作成される。
    • この脆弱性は悪用されていないことが確認されている。
    • 展開計画が合意され修正の準備ができる。
    • ネットワークへの攻撃を検出し、keybaseおよびローカルコンソールにアラートを送信するよう構成されたモニターノードがセットアップされる。
    • 現在のCuckarooz verifierにも同じバグがあり、リファクタリング/コード簡略化のPRで直ちに対処する必要があると判断される。
  • 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日：ドキュメントの公開による脆弱性の開示。