論文解説: SABRE: Protecting Bitcoin against Routing Attacks

Table of Contents

今回は以下の論文について解説する。
https://vanbever.eu/pdfs/vanbever_sabre_ndss_2019.pdf

概要

BGP ハイジャックなどを利用したネットワークルーティング攻撃が現実的になっている今日において、ブロックチェーンはこの攻撃に対して脆弱な存在である。この論文では SABRE というセキュアで拡張可能なBitcoinリレーネットワークを提案する。SABRE はネットワークルーティング攻撃に耐性があり通常の P2P ネットワークの隣で実行されており、容易に展開が可能である。

SABREは、2つの重要な技術的見識に基づいて構築した。まず、ドメイン間ルーティング（BGP）ポリシーの基本的な性質を利用して、リレーノードをホストする。リレーノードは以下の条件を満たしている。

ルーティング攻撃から本質的に保護されているネットワークにある
ビットコインクライアントの大多数が経済的に好むパスにいる

次に、ブロックの中継は計算量ではなく通信量が多いという事実を利用する。これにより、ほとんどのリレー操作をプログラム可能なネットワークハードウェアにオフロード可能である（P4プログラミング言語を使用）。これらの２つの技術的見識について詳しく見ていく。

見識１：リレーノードを本質的に安全な位置でホスティングすること

1つ目の見識は SABRE リレーノードを以下の条件を満たす位置にホストすることである。

内部接続を安全にするためにリレーノード間の接続を攻撃者が分断することから防ぐ
リレーネットワークへのクライアント接続を守るために、ルーティングの観点から多くの Bitcoin クライアントから惹きつけられる

そうするために BGP ポリシーの基本特性を活用した。つまり、互いに直接ピアリングしており、顧客がいない2つのAS間で確立した接続はルーティング攻撃によって迂回させることができないと言うことである。SABRE ではそのようなASのみリレー位置として見なしている。著者らはSABREノードを６つ展開するだけでASレベル攻撃者の96%からクライアントの80%を守ることができると示している。

見識２：ソフトウェア/ハードウェアの共同設計による回復力

リレーが毎回伝播する必要のあるコンテンツ（ブロック）は予測可能であり、サイズが小さい。これらの性質により、プログラム可能なネットワークデバイスを使用して、ほとんどのSABRE操作をハードウェアにオフロードできる。このソフトウェアとハードウェアの共同設計のおかげで、SABREリレーノードは最大Tbpsの負荷に耐えることができる。

背景

BGP ポリシー

経路の選択と広告処理は各ASとその近隣ASとのビジネス関係によって決められる。

customer-provider
カスタマーASがプロバイダASに、インターネットの接続性を得るためにお金を払う関係。プロバイダASはカスタマーに最善の経路を広告し、カスタマーから広告された経路を近隣ASに広告する機能を提供する。
peer-peer
各カスタマーと内部ユーザ間でのトラフィックを転送するためだけに接続している関係。それぞれは自身のプレフィックスとカスタマーから広告されたプレフィックスのみを互いに広告する。

経路選択に関しては、ASはカスタマーから広告された経路を最も優先し次いでピアから広告された経路、最後にプロバイダから広告された経路を好む。もし、同等の優先度を持つ経路が複数ある場合、ASは最短パスの方を支持する。

攻撃者AS（ASM）が標的AS（ASV）からリレーAS（ASR）へのトラフィックを迂回させることができるかどうかを確認するために観察する。（ASVからASRへの経路とASVからASMへの経路を比較するだけで良い）ASMへの経路が優先されるとASMはASVからASRへのトラフィックをハイジャックすることに成功する。

図４はビジネス関係を示したASトポロジーである。プロバイダはそのカスタマーの上部へ書かれておりピアは横に書かれている。影の違いはどの広告をASVが好むかを示している（白が最も優先）。例えば、リレーがASHにホストされていた場合、ASVがカスタマーリンクを通じて到達できる全てのAS（ASA - ASG）は攻撃者の可能性がある。同様に、リレーがASMにホストされている場合、他のAS（ASA - ASL）のいずれかはASVからの対応するトラフィックを迂回できる。

SABRE: ネットワークのための安全なリレーネットワーク

攻撃モデル

前提

SABRE ノードの IP アドレスとソースコードを知っている
攻撃者はリレーノードがホスティングしているプレフィックスをハイジャックすることができる
攻撃者は効果的に（D）DoS攻撃を実行するためにリレーノードに複数のリクエストを発行できる

SABRE の安全なネットワーク設計

relay-to-relay 接続の保護
SABRE はカスタマーがいない、直接ピアリングしており、k-接続グラフのASに属した /24 プレフィックスにホストされているリレーで構成される。これらの制約は3つの理由から relay-to-relay 接続をルーティング攻撃から守る。1つ目は、これらの制約により攻撃者がより詳細なプレフィックスを広告することによってリレー間のトラフィックを迂回させる攻撃を防ぐことができ、既存のプレフィックスを広告することを強制して正当な広告と競うことになる。2つ目に、攻撃者は経済的に好ましいルートを広告することによりリレーノードをホストしているASからリレートラフィックを迂回させることができなくなる（カスタマーがいないから）。つまり、同等の経路を広告できる悪意のあるASの数は、リレーをホストしているASの直接のピアに限られる。3つ目は、これらの制約が k の値が大きくなるに連れて、攻撃者がリレー接続を迂回させる機会が指数関数的に減少するからである。
client-to-relay 接続の保護
どのASにリレーをホストするかは選択できるが、どのASがBitcoinクライアントをホストしているかは選択できない。つまり、BGPハイジャックによってBitcoinクライアントからリレーへのトラフィックは迂回させることが可能である。そこで、Bitcoinクライアントを持つASにより好まれる傾向にある /24 のプレフィックスを広告するASにリレーをホストするように制限している。
relay-to-client 接続の保護
攻撃者がBitcoinクライアントのプレフィックスをハイジャックして、リレーのIPアドレスと一致するトラフィックをドロップする攻撃があるだろう。SABREはクライアント間で交換するトラフィックを難解にすることで防ぐことができる。これは攻撃者に迂回させた大量のトラフィックからL4レベルでの完全な監査を実行することを強いるため、攻撃者にとっては非現実的である。
SABREはリレートラフィックを難解にするために2つの技術に依存している。1つ目は、リレーはクライアントと通信を行う時にソースIPアドレスを修正できる。これは、SABREがリレーとクライアント間でコネクションレス型通信を使用し、クライアントがトラフィックの送信先とは異なる送信元IPを持つパケットを受け入れることができるために可能である。2つ目は、クライアントはリレーとVPN/proxyサービスを通じて接続できる。これによって、攻撃者はプロキシーIPアドレスと対応するクライアントのマッピングを見つける必要がある。

SABRE の安全なネットワーク設計

課題

SABRE が提供するセキュリティは以下の２点に依存する。

内部とリレーの相互通信能力がどれだけセキュアか（攻撃者がネットワークを分断するためにいくつのハイジャックが必要になるのか）
Bitcoinネットワークのどの程度がカバーされているか（攻撃者が、クライアントがすべてのリレーノードに接続するのを防ぐことができる可能性がどの程度あるか）

ネットワークアーキテクチャの評価

この章では、SABREがルーティング攻撃に対してどれだけ効果的なのか述べる。

6つの単接続SABREノードの展開でさえ、94%のASが10％以上のBitcoinクライアントを隔離することを防ぐことがわかった。一方で、5接続の30リレーノードを使った大規模な展開では99%のASが20％以上のBitcoinクライアントを隔離することを防ぐ。加えて、既存のリレーネットワーク（Falcon, FIBRE）はルーティング攻撃から守ることはできないことがわかった。

図8は、SABREネットワークのサイズNと内部接続kに応じて、Bitcoinネットワークがどのように保護されているかを示している。グラフは、Bitcoinノードの特定の割合yごとに、SABREから独立して切断できるASの割合を示している。 N = 20、k = 1の場合、ASの3％未満が、Bitcoinクライアントのかなりの部分（15％）がリレーネットワークに接続するのを防ぐことができる。対照的に、クライアントの90％以上は、現在のネットワーク内の任意のASによって分離できる。

攻撃者の可能性のある数とパーティションサイズの間のマッピングは、SABREのサイズと接続性によって異なる。特に、展開されるノードの数を増やすと、攻撃者がトラフィックを正常に迂回できる可能性が低くなる。一方、接続内の要件（つまり、kの値）を減らすと、アルゴリズムがより多くのリレーのセットから選択できるようになり、より効果的なSABREが形成される。これにより、リレー内接続の安全性とリレーノードが既存のBitcoinネットワークをどの程度カバーするかという興味深いトレードオフが生じる。

たとえば、フルメッシュ（5接続グラフ）で接続された6つのリレーのSABREは分割が非常に困難だが、より多くのASレベルの攻撃者がBitcoinクライアントの大部分をSABREから切断できるようになる。

たとえば、ASの3％は、Bitcoinノードの22％を含むパーティションを作成する可能性がある。対照的に、1接続のSABREでは、攻撃者が深刻な攻撃を実行することは少なくなる（ASの1％のみが12％のパーティションを作成できる）が、リレーネットワーク自体は、単一のリンク障害または直接ピアからのハイジャックの成功によってパーティション化できる。

SABREが個々のクライアントをどの程度効果的に保護するかを評価するために、ランダムなASレベルの攻撃者によってBitcoinクライアントがすべてのリレーノードに到達するのを防ぐ可能性がどの程度あるかを調べた。

図９は、インターネット内のASの特定の割合ごとに、Bitcoinクライアントの割合が、この割合のASによって攻撃され、SABREから切断される可能性があることを示している。 5接続されたノードが6つしかないSABREネットワークでも、クライアントの80％がASレベルの敵の96％から保護されていることがわかった。安全な内部接続性とBitcoinクライアントのカバレッジの間には、やはりトレードオフがある。

たとえば、6つの1接続ノードのSABREはBitcoinクライアントの90％を92.5％のASから保護するが、完全に接続された6ノードのSABREはわずか89.5％のASから保護する。興味深いことに、接続性をk = 3からk = 5に増やしても、保護されたクライアントが大幅に減少することはないが、リレーネットワークの切断はほとんど不可能になる。