Develop with pleasure!

福岡でCloudとかBlockchainとか。

Repairable Threshold Scheme

Cryptography 秘密分散

最近、Schnorrベースの閾値署名スキームFROSTをベースにして、暗号技術だけでt-of-nのマルチシグの設定を動的に調整可能にする提案が行われている。その中で、母数nの数を増やす際に利用されているのが、RTS（Repairable Threshold Scheme）。

RTSは、シャミアの秘密分散法などを使って、複数のパーティでシェアを分散して保持するスキームにおいて、後から参加者のシェアを復元できるようにするスキーム。↑の提案では、既存のシェアの復元ではなく、新しい参加者用に新しいシェアを作るのにRTSを利用することで、母数を増やす。

今回は、↓サーベイ論文に掲載されている内の１つEnrollementスキームについて調べてみた。

https://eprint.iacr.org/2017/1155.pdf

RTS

論文は、ディーラーがいるモデルで書かれており、参加者の母数をn、閾値をtとした場合、ディーラーはシークレット値を含むt-1次の多項式f(x)を生成し、n人の参加者に対して、割り当てられたインデックス {ID_i}で多項式を評価した結果 {(ID_i, f(ID_i))}をシェアとして配布する。

この場合、多項式を知っているディーラーがいればシェアの復元は可能だが、ディーラーが利用できない場合でも、閾値数分の参加者がいればシェアを復元できるようにするのがこのスキームの目標。

※ RTSをt - 1人で実行できると追加のシェアが作成され閾値tを超えるシェアを入手できてしまうため、必ずt人以上で実行しないと再構築できないようなプロトコルになっている必要がある。

※ また、閾値分のシェアが集まれば多項式補間で多項式が復元できシェアを計算できるようになるが、シェアを集める参加者が登場することになり実質ディーラーとなれるので、そういうアプローチではない。

シェアの復元

シェアを復元したい参加者を {P_r}、復元を支援するt人の参加者を {P_1, ..., P_t}とする。各参加者が保持しているシェアを {\phi_i = f(ID_i)}とした場合、 {\phi_r = f(ID_r)}を求めるのが目標。

ラグランジュ補間公式を利用すると {f(ID_r)}は以下を計算することで入手できる。

{f(ID_r) = \lambda_1(ID_r)\phi_1 + ... + \lambda_t(ID_r)\phi_t}

ここで、各ラグランジュ係数 {\lambda_j(ID_r)}（1≦ j ≦ t）は、

{\displaystyle \lambda_j(ID_r) = \Pi_{0 \leq m \leq t, (m \neq j)} \frac{ID_r - ID_m}{ID_j - ID_m} = \frac{(ID_r - ID_1) \cdot \cdot \cdot (ID_r - ID_t)}{(ID_j - ID_1)\cdot \cdot \cdot (ID_j - ID_t)}}

であり、各参加者の識別子（ {ID_1, ..., ID_t}）が分かっていれば計算できる。

Enrollementプロトコルでは以下の手順で、 {P_r}が {\phi_r}の値を計算できるようにする。

  1. t人の各参加者 {P_i}は、 {\lambda_i(ID_r)\phi_i = \sum_{j=1}^{t}\delta_{i, j}}となるようなt個のランダム値 {\delta_{i, j}}（1≦ j ≦t ）を生成する。各参加者は自分のシェアと上記のラグランジュ係数から {\lambda_i(ID_r)\phi_i}を計算できるので、t - 1個の {\delta_{i, j}}をランダムに生成して、最後の値は {\lambda_i(ID_r)\phi_i - \sum_{j=1}^{t-1}\delta_{i, j}}で計算すればいい。
  2. 各参加者 {P_i}は、計算した {\delta_{i, j}}を他の支援者 {P_j}に送信する。
  3. 各参加者 {P_j}は、 {\sigma_{j} = \sum_{i=1}^{t}\delta_{i, j}}を計算し、 {\sigma_{j}}を新しい参加者 {P_r}に送信する。
  4. {P_r}は、 {\phi_r = \sum_{j=1}^{t}\sigma_j}を計算し、シェア {\phi_r}を入手する。

1〜4の計算結果は、求めたかった最初の {\displaystyle \phi_r = \sum_{i=1}^{t}\lambda_i(ID_r) \phi_i}と同じになる。

各参加者は自分のシェア（正確にはラグランジュ係数を掛けた {\lambda_i(ID_r)\phi_i}）をt個分割して、他の参加者に配布し、それを全参加者分集めたら {P_r}が自身のシェアを計算できるようにしてるっぽい。

btcdで発見された相対的タイムロックのコンセンサスバグ

btcd vulnerability Bitcoin

先日、Delving Bitcoinで開示された、btcdで発見された相対的タイムロックのコンセンサスバグについて↓

https://delvingbitcoin.org/t/disclosure-btcd-consensus-bugs-due-to-usage-of-signed-transaction-version/455

相対的タイムロック

トランザクションの相対的なタイムロック機能は以下の2つのBIPで定義されている。

これらの仕様はソフトフォークとして2016年6月にBitcoinに導入された。

今では、ライトニングネットワークなどさまざまなコントラクトプロトコルの構成要素の1つとして利用されている。

BIPにも記載されているように、この機能をトランザクションで有効にするためには、トランザクションのバージョンを2以上に設定する必要がある（ソフトフォーク前に事前署名したトランザクションが無効にならないようにするための措置）。

バグの内容

問題はトランザクションのバージョンの型。元々Bitcoinの実装では、このバージョンは符号付き整数で管理されている。バージョンを負の値として解釈することができる。

ただ、BIP-68の参照実装のセクションのコード内には、

tx.nVersion is signed integer so requires cast to unsigned otherwise we would be doing a signed comparison and half the range of nVersion wouldn't support BIP 68.

と、符号付き整数（int32）から符号なし整数（uint32）へのキャストするよう記載されている。符号付き整数のまま比較すると、バージョンのとり得る値の半分がBIP 68をサポートできなくなるため。

Bitcoin Coreではこのキャストを行っているが、btcdではこのキャストが行われていなかったというのがバグの内容。

バグの影響

btcdでは上記のキャストが行われないため、符号付き整数として解釈した場合に、負の値のバージョンを持つトランザクションを構築することが可能になる。

そのようなトランザクションがあると、

  • Bitcoin Coreでは相対的タイムロックのルールを強制する。
  • btcdから見ると負の値で2未満なので相対的タイムロックの適用対象外とみなされる。
    たとえば、OP_CSVロックされているUTXOを使用するトランザクションを構成し、事前署名していても、OP_CSVの評価時にTxのバージョンが2未満であると解釈され無効なトランザクションとして判定される。

ただ、負の値にするためには最上位bitが1になる必要があるので、符号なし整数としては、2147483648以上の値をバージョンとして指定する必要があるけど、

  • そういったバージョンを設定したトランザクションを作成する一般的なウォレットは無いだろうし、
  • Bitcoin Coreのリレーポリシーで現在許可されているバージョンは最小値が1、最大値が2なので、負の値のバージョンを持つトランザクションは拒否される（マイナーの協力でもない限りそういったトランザクションをブロックに含めるのもハードル高い）。

ただ、実際に発生するとチェーン分岐が発生する可能性があり、

  • btcdを使用しているライトニングノードは、正しいチェーンの更新を受信できず、資金を失うリスク
  • 悪意あるマイナーが（実質競合がいない）btcdチェーンでマイニングを続け、ユーザーに無効な支払いを受け入れさせる可能性
  • マイナー自体がbtcdを使用している場合、無効なチェーンのマイニングを継続してリソースを無駄に消費する

といった影響が考えられるので、btcd使っている場合はv0.24.0へのアップグレードは必須。

バグの修正

修正はシンプルで、上記のキャストをするようにするというもの。修正のPR自体は、gofmtを適用するPRで、その中にuint32へのキャスト処理を入れ込んだみたい。

また、btcd以外にbitcoin-sでも修正が行われている↓

https://github.com/bitcoin-s/bitcoin-s/pull/5346

今回影響なかった、Bitcoin Coreにも符号付き整数として解釈した場合に負の値になるバージョン（0xffffffff）のテストデータが新しく追加されてる↓

https://github.com/bitcoin/bitcoin/pull/29291

タイムライン

開示までのタイムラインは↓

  • 2023-05-22 Lightning Labsへの最初の開示
  • 2023-06-21 修正PRがbtcdにマージ
  • 2023-12-31 btcd v0.24.0リリース
  • 2024-01-22 開示

修正からリリースまでは結構あいてる。標準のリリースサイクルに含めたということなのかな？

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

Lightning network vulnerability CLN Bitcoin

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

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

競合を発生させる攻撃

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

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

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

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

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

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

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

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

BIP Bitcoin

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

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

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

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_L、responder_L）と、コンテンツ自体を暗号化する暗号鍵（initiator_P、responder_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だとこれらのフラグ無いの何故だろう？

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

BitcoinのP2Pメッセージは、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つの脆弱性

LND Lightning network Bitcoin vulnerability

最近、過去（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は、チャネルの各方向毎に１つずつ作成されるので、合計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で修正された。

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