Develop with pleasure!

福岡でCloudとかBlockchainとか。

CLN v23.02〜v23.05.2に影響したDoS脆弱性

Core Lightnig v23.02〜v23.05.2に影響した脆弱性について、最近内容が開示された↓

DoS disclosure: Channel open race in CLN - Implementation - Delving Bitcoin

ので、内容を確認してみる。詳細は報告者のブログ記事で説明されている↓

morehouse.github.io

発見された脆弱性は、元々別のフェイクチャネルの脆弱性の修正についてテストをしていたところ新たに発見されたものらしい。折角なのでまずフェイクチャネルの脆弱性についても調べてみた↓

フェイクチャネルによるDoS

こちらも同じ報告者のブログ記事が詳しい↓

morehouse.github.io

この脆弱性は、偽のチャネル開設リクエストを多数発行する攻撃により発生する。

新しくチャネルを開く際、↑の記事にあるように二者間で以下のメッセージがやりとりされる。

https://morehouse.github.io/images/channel_funding.png

1〜4のステップで、FunderとFundeeはチャネル開設用のコミットメントトランザクションを構築し、その署名を交換する。そしてステップ5でFunderがファンディングトランザクションBitcoinネットワークにブロードキャストして、そのトランザクションが指定数承認されたらチャネルが開設される。

このとき、Funderがファンディングトランザクションをブロードキャストしなければ、Fundeeは2016ブロック(約2週間)の間その保留中のチャネルがオンチェーンで承認されないかオンチェーンを監視する必要がある。そのため、ストレージやRAM、CPUリソースが消費される。

これを悪用して、攻撃者は大量の偽のチャネルの開設要求を被害ノードに送信し、被害ノードのマシンリソースを消費させるというのがフェイクチャネルのDoS攻撃。この攻撃では、攻撃者はランダムに生成したIDをトランザクションIDとして偽のファンディングアウトポイントを作成すれば良いので、攻撃者が資金をオンチェーンに保持している必要もない。

脆弱性の影響

主要なライトニングノード実装の影響は以下のとおり:

実装 影響
LND 数日でパフォーマンスが大幅に低下し、ピアやCLIからのリクエストに応答しなくなる。DoS攻撃が終わっても、パフォーマンスの低下は継続する。
CLN 攻撃から1日後、CLNのconnectdデーモンがブロックされ他のノードからの接続要求に応答できなくなる。ただ、他の機能は引き続き動作し(別のデーモンで動作してるので)、タイムロックなどの反応で資金が危険にさらされることはなかった。
Eclair OOMによりクラッシュ。DoS攻撃が終わった後も再起動しても30分以内にOOMでクラッシュする。
LDK ルノード実装ではないため、ldk-sampleノードで実験。DoS攻撃から数時間後にパフォーマンスが大幅に低下し、ブロックチェーンが同期できなくなる。

いずれのノードも攻撃の影響を受け、CLN以外は、資金が危険にされされる可能性があった模様。対応としては、チャネル開設がペンディング中の場合、その上限を設けるようにしたみたい。

競合状態の発生によるDoS

上記のフェイクチャネルの修正のフォローアップのテスト中に発見された新たな脆弱性が今回開示された内容。

この脆弱性は、CLNのチャネル開設フローとピア接続フローの2つの異なるフローが重なった場合に競合状態が発生し、その結果CLNがchanneldデーモンを2回起動しようとしてクラッシュを引き起こすというものみたい。

チャネル開設フロー

通常、CLNに対して新たなチャネル開設をリクエストするとCLNの各デーモンでは以下のフローが実行される(CLNは各機能がそれぞれ別のプロセスで実行されるように構成されている。このような構成のため、フェイクチャネルのDoS攻撃の場合、一部のデーモンのみがダウンして他は機能し続けた模様)。

https://morehouse.github.io/images/cln_channel_open_no_race1.png

  • connectdは、ピアとの接続を管理するデーモン
  • lightningdは、サブデーモンを制御するマスターデーモン
  • opendは、1つのピアとのチャネル開設をネゴシエーションするデーモン
  • channeldは、1つのピアとの開設したチャネルを管理するデーモン

ピア接続フロー

ピアがチャネルをセットアップした後、接続が切断して再接続が発生すると、以下のフローが実行される。

https://morehouse.github.io/images/cln_channel_open_no_race2.png

いずれのフローも最終的に、lightnigdchanneldデーモンを起動する構成になっている。

競合を発生させる攻撃

問題となるは、上記の2つのフローが重なるような実行が発生した場合↓

https://morehouse.github.io/images/cln_channel_open_race.png

chanbackupプラグインの処理に時間がかかるとこのような競合状態が発生する。その結果、ピアに対して2回channeldの起動が行われ、アサーションに失敗し、CLNがクラッシュする。

この攻撃を成功させれるためには、多くのピア接続やチャネルステートの変更などによってchanbackupプラグインの処理を遅くする必要がある。上記のフェイクチャネル攻撃もそういった攻撃の方法の1つ。

↑の記事では、インターネット上で約30秒の作業でCLNをクラッシュさせることができたらい。

フェイクチャネルの脆弱性の修正中にこの競合が発見されなかったのは、単に、chanbackupプラグインが導入されたのがそれより後だったからということみたい。

その後、ピア接続時のフックによるプラグインの処理が終わった後、すでにそのピアとのchanneldが実行されている場合は、再度channeldを起動しようとしないという修正が行われたCLN 23.08がリリースされている。

BitcoinのP2P層の通信を暗号化するBIP-324

これまでBitcoinP2Pレイヤーの通信は暗号化されておらず平文でメッセージがやりとりされている。基本的にBitcoinの場合、ブロックやトランザクションなどのデータは誰もが共有する台帳データで機密性のあるデータではないから。

ただ、リレーされるデータ自体は公開データであるものの、平文の通信には以下のような課題もある:

  • ノードのP2P接続を観察可能なプレーヤー(ISPなど)に対して、トランザクションソースやタイミングに関する情報を与えることになる。
  • 平文なので途中でデータの改ざんリスクがあり、その検出も難しい。
  • 接続時に固有のマジックバイトで通信が始まるのでBitcoinP2P接続であることを簡単に識別することができる。

BIP-324では、これらに対処するためトランスポート層の通信を暗号化するv2トランスポートプロトコルを定義している。v2トランスポートプロトコルを利用すると、ネットワーク上のデータは一様にランダムなデータと見分けがつかなくなる*1

Bitcoin Coreもv26.0からこのv2トランスポートプロトコルの実験的なサポートを開始している(デフォルトでは無効、また当然接続相手もv2をサポートしている必要がある)。

v2トランスポート

従来のv1トランスポートプロトコルでは、接続先のノードとのTCP接続を行うとすぐに、version/verackメッセージの交換を始めるけど、v2トランスポートプロトコルでは、最初にハンドシェイクを実行して鍵交換を行う。

ハンドシェイク

v2トランスポートを使用する場合、2つのノードは接続時に以下のハンドシェイクを実行する。

1.5往復の通信でハンドシェイクは完了する。

ElligatorSwift公開鍵

ハンドシェイク時にお互いに送信する公開鍵は、Bitcoinでよく使われるsecp256k1鍵のエンコード方式ではなく、ElligatorSwiftという方式でエンコードされている。

鍵交換の際に送信する公開鍵は当然暗号化されていないのと、公開鍵自体は楕円曲線上の点で、その座標は曲線の方程式を満たす必要がありランダムなデータにはならないため、ネットワーク上の通信を見ればそれが公開鍵であるか分析できる可能性がある。そのため、この公開鍵をランダムなバイトストリームにしかみえないようにするために、ElligatorSwiftというエンコード方式を採用している。

Elligator/Elligator 2と同じように、二種類の写像を利用する。

  • 直接写像
    楕円曲線の有限体上の値rを入力として、その楕円曲線上の点P = (u, t)を出力する。
  • 写像
    点Pを入力として、有限体上の値rを出力する関数。

BIP-324ではハンドシェイク時に生成したsecp256k1の一時鍵の公開鍵のx座標を入力として、↑のElligatorSwiftエンコードした公開鍵(64バイト)を取得するようになってる。この公開鍵を受け取った側は、逆写像を使って、元のx座標の値を入手する。

ガベージの役割

ガベージは、最初のメッセージが少なくとも64バイトであるという認識可能なパターンを回避するために付与される任意のデータで、最大4095バイト。

x-only ECDH

共有シークレットの導出に書いているx-only ECDHは、以下の手順で共有シークレットを導出する。

  1. 相手のElligatorSwift公開鍵からx座標を入手し、y座標を計算し、楕円曲線上の点として復元する。
  2. 1の点に自分の秘密鍵を乗算した楕円曲線上の点を導出する。この点のx座標をecdh_point_x32とする。
  3. 2のecdh_point_x32と両者のElligatorSwift公開鍵を使って以下のタグ付きハッシュを計算し、その結果が共有シークレットになる。
secret = sha256_tagged("bip324_ellswift_xonly_ecdh", イニシエーターのElligatorSwift公開鍵 || レスポンダーのElligatorSwift公開鍵 || ecdh_point_x32)
共有シークレットから導出するデータ

ハンドシェイクにより、両者は共有シークレットから以下のデータを導出する。

  • 暗号鍵(32バイト)
    各方向毎に、コンテンツの長さを暗号化するための暗号鍵(initiator_Lresponder_L)と、コンテンツ自体を暗号化する暗号鍵(initiator_Presponder_P
  • セッションID(32バイト)
  • 双方のガベージターミネーター(各16バイト)
    ガベージデータの終端を表すデータ。※ ハンドシェイク後に、ガベージターミネーターを送信したらすぐにversionパケットを送信することができる。受信した4,111バイト以内(ガベージ+ガベージターミネーターの最大値)にガベージターミネーターに合致するデータが存在しない場合は、接続は無視される。

各データは、以下のデータを使ってHKDF-SHA256を使って導出される。

  • ikm(入力のキーマテリアル)= 共有シークレット
  • salt = "bitcoin_v2_shared_secret" + <P2Pメッセージのマジックバイト>
  • info(コンテキスト情報):
    • initiator_L
    • initiator_P
    • responder_L
    • responder_P
    • session_id
    • garbage_terminators

パケットの暗号化

ハンドシェイクで双方ガベージターミネーターを受信したら、それ以降のデータはすべて暗号化される。この暗号化には、以下の2つの暗号プリミティブが使用される。各暗号化パケットは以下のデータで構成される

  • 暗号化データのデータ長を示すデータで、ChaCha20ブロック関数を使って暗号化される。
  • コンテンツの認証付き暗号データでChaCha20-Poly1305 を使って暗号化される。以下の2つのデータで構成される。
    • トランスポート層プロトコルのフラグで構成される1バイトのヘッダー。現在は、ignore bitとして最上位ビットのみが定義されている。他のbitは無視されるが、これは将来のバージョンで変更される可能性あり。
    • 可変長のコンテンツ

各平文は、それぞれ異なるnonceを持つ個別のAEADメッセージとして扱われる。

また、暗号化に使用される鍵は、224個のメッセージ毎に更新され新しい鍵が使用される。

バージョンネゴシエーション

ハンドシェイク後は、両者それぞれ空のバージョンパケットを送信する。将来v2トランスポートプロトコルを拡張する場合、適切なペイロードを持つようになるものと思われる。

ガベージターミネーターを送信後に送られる最初の暗号パケットはこのバージョンパケットか、オプションのデコイパケットになる。

v1だとversionメッセージのサービスフラグでノードのサポート機能をネゴシエーションしてたけど、v2だとこれらのフラグ無いの何故だろう?

アプリケーションメッセージ

BitcoinP2Pメッセージは、v1の場合は、

マジックバイト + 12バイトのASCIIメッセージタイプ(12バイトに満たない場合はゼロ埋め) + メッセージペイロード

という形式で送信されるが、v2の場合メッセージタイプはASCIIデータではなく1〜255の範囲内の数値で指定する(そのため、v1に比べて11バイト分メッセージのデータは小さくなる)。既存の各メッセージに割り当てられるメッセージタイプの値は以下のとおり:

  0 1 2 3
+0 従来のASCIIメッセージタイプ ADDR BLOCK BLOCKTXN
+4 CMPCTBLOCK FEEFILTER FILTERADD FILTERCLEAR
+8 FILTERLOAD GETBLOCK GETBLOCKTXN GETDATA
+12 GETHEADERS HEADERS INV MEMPOOL
+16 MERKLEBLOCK NOTFOUND PING PONG
+20 SENDCMPCT TX GETFILTERS CFILTER
+24 GETCFHEADERS CFHEADERS GETCFCHECKPT CFCHECKPT
+28 ADDRV2

29以降は現状未定義。

v2サポートのシグナリング

v2トランスポートプロトコルをサポートするノードは、addrメッセージのサービスフラグにNODE_P2P_V2 = (1 << 11)をセットすることで、v2トランスポートプロトコルをサポートしていることを通知できる。

*1:パケット長やタイミング分析、能動的な攻撃により、Bitcoinのv2トランスポートが使われていることが分かる可能性はまだ残る

LND v0.14.0とv0.15.0で修正された2つの脆弱性

最近、過去(2021年)のLND実装のサービス拒否の脆弱性が公開されてたので見てみる↓

Denial-of-service bugs in LND's channel update gossip handling - Implementation - Delving Bitcoin

(最近は、Delving Bitcoinフォーラムでの議論も増えてるっぽい。)

2つともchannel_updateメッセージのハンドリングに起因する脆弱性

メモリ不足によるクラッシュ

新しくチャネルを開設するとノードは以下のメッセージをネットワークにブロードキャストする。

  • channel_announcement
    新しいチャネルをネットワークに通知するために利用。チェーン上でチャネルを一意に識別する情報(ショートチャネルID)や、両ノードの公開鍵、ファンディングアウトプットのマルチシグの鍵、各鍵に対する署名などが含まれる。
  • channel_update
    主に、ルーティング手数料やタイムロックの期待値を更新するために利用。

channel_updateは、チャネルの各方向毎に1つずつ作成されるので、合計3つのメッセージがブロードキャストされる。channel_updateにも、そのメッセージがチャネル参加者によって作成されたものであることを検証できるようにするため、ノードの公開鍵に対して有効なデジタル署名が付与されている。

ここで、これらメッセージを受け取るピアにおいては、必ずしもchannel_announcement -> channel_updateの順にメッセージが届く保証はない。そのため、channel_updateの方が先に届いた場合、このメッセージが正しいか検証するためのノードの公開鍵はchannel_announcementメッセージに含まれているため、channel_announcementが届くまで検証が行えない。

この状況に対処するため、LNDではそのようなchannel_updateを一時的にメモリのバッファに保持するようなっていた。ただ、このバッファにはサイズ制限がなく、攻撃者が無効なchannel_updateを大量に送りつけてバッファを埋めることで、メモリ不足に陥らせるという攻撃が可能だった。

この脆弱性は、バッファーを上限付きのキャッシュに置き換えるようにする形で、LND v0.14.0で修正されている。

レート制限による検閲

チャネルの手数料やタイムロックの値を変更する場合、ノードはchannel_updateメッセージをブロードキャストする。このメッセージの作成にかかるコストは、せいぜい署名の生成くらいなので、何もしなければこのメッセージを大量に送りつけるスパムが可能になる。

そのため、各ライトニング実装では、このようなスパムを防ぐために、所定の時間内にリレーするchannel_updateの数をレート制限するようになっている。

LNDでは、このレート制限を行った後で、channel_updateメッセージの署名を検証していた。そのため、攻撃者は無効なchannel_updateメッセージを作成/送信し、無効なメッセージでレート制限されるようにし、他のチャネルの有効なchannel_updateの伝播が無視されるような攻撃をすることが可能になる。

この脆弱性は、レート制限の適用の前に署名検証が確実に行われるようにするようv0.15.0で修正された。

というのが、今回公開された脆弱性の内容。尚、これらの脆弱性を悪用した攻撃は、いずれも確認されていない。

現在のBitcoinのUTXOセットの内訳

現状のBitcoinのUTXOセットについて、その内訳を調べてみた。

UTXOセットのダンプ

Bitcoin Coreを実行すると、chainstateディレクトリ以下のLevelDBのファイルにUTXOセットのデータが格納される。LevelDBは基本的に1つのプロセスしかDBファイルを開けないのと、LevelDBで操作するのも難儀なので、調査しやすいようにまずUTXOセットをファイルにダンプする。これは、Bitcoin Coreのdumptxoutset RPCを実行することでできる(2〜3分かかる)*1

$ bitcoin-cli dumptxoutset <生成先のパス>
{
  "coins_written": 146009905,
  "base_hash": "000000000000000000042303364e5e50144b3d77362842354fb7992af10a80af",
  "base_height": 821628,
  "path": "<生成先のパス>",
  "txoutset_hash": "647a5f9f0e6427b999d633e981674d0af1ed5eddd4b9f8f3a7f1c59eae08146c",
  "nchaintx": 937337142
}

レスポンスのJSONの各値は、

  • coins_written:スナップショットに書かれているコインの量
  • base_hash:スナップショットのベースとなったブロックのハッシュ
  • base_height:スナップショットのベースとなったブロックの高さ
  • path:スナップショットファイルのパス
  • txoutset_hash:UTXOセットのコンテンツのハッシュ
  • nchaintx:ベースとなったブロックを含むチェーン内のトランザクション

出力されたのは、mainnetのブロック821,628時点のUTXOのスナップショットで、約9.1GB。

UTXOセットのデータフォーマット

ダンプしたファイルは以下の形式のデータで構成されている。

まず、先頭に

  • 32バイトのbase_hash
  • 8バイトのcoins_written

が記録されていて、以降、UTXOの各エントリーが続く。このエントリーのデータ構造は↓

UTXOセットの内訳

ダンプファイルをパースしたタイプ別の内訳が↓

ブロック821,628におけるUTXOセットの内訳

タイプ 個数
P2PK 45,537
P2PKH 50,789,846
P2SH 19,190,365
P2WPKH 47,532,135
P2WSH 1,325,019
P2TR 26,183,277
Bare Multisig*4 934,122
Other 9,604

Ordinalsの影響だろうけど、2021年11月にアクティベートされたP2TRが結構多い(UTXOセットなので、インプットのwitnessにデータが格納されるInscriptionの画像系のデータはここには含まれない)。そして、現状のLNチャネルで使われるP2WSHは全体から見ればまだ少数(Simple Taproot Channelとかに移行すると、これもP2TRベースになる)。

ちなみに、UTXOにセットされているsatoshiの量が0のアウトプットのタイプ別の内訳は↓

タイプ 個数
P2PK 2
P2PKH 6,031
P2SH 68
P2WPKH 3
Other 8,846

Otherに分類されるUTXOの9割ちょっとが、0 sat UTXOになってるのが分かる。そして、その大半は、

OP_2 OP_3 <38バイトのデータ>

という形式のスクリプトになってる。これもデータの埋め込みに使われてるみたいだけど、OP_RETUNと違ってUTXOセットに残るのが難。ただこのスクリプトは、データがプッシュされているだけなので、マイナーであれば回収可能なUTXO。まぁ、0 satなので回収するメリットはないけど、その分の手数料収入放棄すれば、1ブロックで掃除できるボリュームではある。

*1:将来的には、ダンプされたUTXOセットのデータをロードして、スナップショットベースの同期をサポートするみたい

*2:通常のTxのシリアライゼーション形式ではなく、データスペースを節約するために独自の圧縮形式が採用されている

*3:6加算しているのは、P2PKH、P2SH、P2PKの各スクリプトプレフィックスと被らないようにするため

*4:P2SHになっていない素のマルチシグスクリプト

IPAを利用した多項式コミットメントスキーム

Inner Product Argument(IPA)は、内積の関係を証明するプリミティブで、いくつかの証明システムに組み込まれて使用されている。IPAの解説については、GBEC動画 or 過去記事参照↓

goblockchain.network

techmedia-think.hatenablog.com

IPAは、多項式コミットメントスキームとしても機能するため、今回はそのプロトコルについて見ていく↓

blog.lambdaclass.com

IPAベースの多項式コミットメント

ここでは、n次の任意の多項式 {p(x) = a_0 + a_1x + a_2x^{2} + ... + a_{n}x^{n}}を想定する。

この多項式をx = zで評価した場合、つまりp(z)は、 {A = (a_0, ..., a_{n})} {B = (1, z, z^{2}, ..., z^{n})}内積値p(z) = <A, B>となる。

コミットメント方式のセットアップフェーズとして、可換群 {\mathbb G}が与えられ、以下を決める。

  • n個のベースポイント {G_0, G_1, ..., G_{n} \in \mathbb G}
  • ブラインドファクター用のベースポイント {H \in \mathbb H}

コミット

多項式のコミットメントは、ランダムな値r(ブラインドファクター)を選択し、以下を計算することで得られる。

 {C = a_0G_0 + ... + a_{n}G_{n} + rH}

これは楕円曲線上の点で、証明者はこれを多項式p(x)のコミットメントとして検証者に送信する。

オープン

検証者がx = zの場合の評価値p(z)を知りたいのに対して、証明者はy = p(z)がその値であることを検証者に納得させる。yは2つのベクトル {A = (a_0, ..., a_{n})} {B = (1, z, z^{2}, ..., z^{n})}内積であるため、Inner Product Argumentを利用してこれを証明する。

証明者、 {A = (a_0, ..., a_{n})} {B = (1, z, z^{2}, ..., z^{n})}および {G_0, G_1, ..., G_{n} \in \mathbb G}について、それぞれ前半部と後半部に分割し、それを {A_{lo}, A_{hi}, B_{lo}, B_{hi}, G_{lo}, G_{hi}}とする。

検証者は、ランダムな要素 {U \in \mathbb G}を選択し、証明者に送信。

証明者は、ランダムな要素s, s'を選択し、以下のベクトルを計算し、検証者に送信。

  •  {L = \langle A_{lo}, G_{hi} \rangle + sH + \langle A_{lo}, B_{hi} \rangle U}
  •  {R = \langle A_{hi},G_{lo} \rangle + s'H + \langle A_{hi}, B_{lo} \rangle U}

検証者はランダムな数値xを選択し、証明者に送信。

証明者は、

  •  {A' = xA_{lo} + x^{-1}A_{hi}}
  •  {B' = x^{-1}B_{lo} + xB_{hi}}
  •  {G' = x^{-1}G_{lo} + xG_{hi}}

を計算し、これらを新しいAおよびB、Gとして各ベクトルの長さが2になるまで繰り返す。

証明者は、最終的に得られたA'、B'と、ブラインドファクターについて {r' = sx^{2} + r + s'x^{-2}}を計算し、検証者に送信する。

検証者は、

 {x^{2}L + C + x^{-2}R + yU = x^{-1}A'G_0 + xA'G_1 + r'H + A'B'U}

が成立するか検証する。

元のコミットメント {C = a_0G_0 + ... + a_{n}G_{n} + rH}の各係数部分、つまり {A = (a_0, ..., a_{n})} {G_0, G_1, ..., G_{n} \in \mathbb G}内積は、IPAの折りたたみプロセスにより、検証式の {x^{-1}A'G_0 + xA'G_1}に含まれる。

実際に利用する際は、証明者と検証者間の対話はFiat-Shamir変換により非対話型で構成される。

というのが、IPA多項式コミットメントとして使用する方法。冒頭の解説動画/記事の内容との違いは、多項式コミットメントの場合、コミットするのは多項式の各係数とブラインドファクターのみなので、Hのベースポイントはベクトルではなく1つだけ。多項式を評価する値zは、後で検証者から証明者に送られるため、検証者はBのベクトルについては既知になる。