GHSA-3q6v-r5mr-hxv8 [高] league/commonmark: GitHubで利用されるMarkdownのテーブル拡張機能において、ブロック開始の解析処理に二次時間オーダーの脆弱性があり、サービス拒否攻撃につながる可能性がある。

league/commonmark: GitHub Flavored Markdown のテーブル拡張機能における、二次時間計算のDoS（サービス拒否）脆弱性

## 概要

`league/commonmark` の GitHub Flavored Markdown テーブル拡張機能は、`TableStartParser` をブロック開始パーサーとして登録します。段落がアクティブなブロックである間、コアのブロックパーサーは、空白でないすべての行に対して `TableStartParser::tryStart()` を呼び出します。この処理の最初の段階として、`getParagraphContent()` を使用して、現在構築中の段落全体を読み込み、`strpos($paragraph, '|')` を使用して、そのすべての部分に対して検索を行います。パイプ記号を含まない M 行からなる段落の場合、k 行目は約 k 行のバッファを再スキャンするため、全体の処理量は 1 + 2 + ... + M となり、これは O(M^2) の計算量となります。認証されていないユーザーが、アルファベットで始まらないパイプ記号を含まない、非常に長い段落を、`GithubFlavoredMarkdownConverter` (または `TableExtension` が有効になっている環境) を使用して、信頼できない Markdown を変換するサービスに送信すると、シングルコアの CPU が数秒から数十秒間、ボディサイズに応じて二次的に増加する負荷がかかり、ワーカープロセスを枯渇させ、サービスを拒否する可能性があります。

## 根本原因

GFM テーブル検出器は、テーブルヘッダーを形成する可能性のある部分だけでなく、累積された段落全体に対して、行ごとの「簡易チェック」を行います。段落は、空白でない行が継続的に受信される限り閉じられず、そのバッファは無制限に増加します。そのため、簡易チェックは、各行に対してバッファ全体を再スキャンします。段落の最後の行だけがテーブルヘッダーになり得ます（これは `strrpos`/`substr` を使用して個別に抽出されます）。したがって、すべての行に対して、複数行のバッファ全体をパイプ記号の有無を調べるスキャンを行うことは、不要な処理であり、二次時間計算量を引き起こします。入力サイズに制限はなく、デフォルトのネスト制限にも達しないため、スキャンを制限する要素はありません。

影響を受ける関数: League\CommonMark\Extension\Table\TableStartParser::tryStart
場所: src/Extension/Table/TableStartParser.php:35-38
$paragraph = $parserState->getParagraphContent(); // フルサイズのバッファを返す
if ($paragraph === null || \strpos($paragraph, '|') === false) {
return BlockStart::none(); // strpos は各行に対してバッファ全体をスキャンする
}
バッファの増加: src/Reference/ReferenceParser.php:89-95 ($this->paragraph .= "\n"; $this->paragraph .= $line;)
行ごとの処理: src/Parser/MarkdownParser.php:135-147 および :224-236

## 影響

認証されていない攻撃者が、GitHub Flavored Markdown コンバータを使用している、または Table 拡張機能を有効にしているアプリケーションに対して、ユーザーの操作なしでサービス拒否攻撃を引き起こす可能性があります（デフォルトの GFM バンドルでは有効になっています）。パイプ記号を含まず、空白行を含まず、文字で始まらない多数の行を含む単一のリクエストは、入力サイズの二乗に比例する CPU を消費します。測定結果では、入力サイズが2倍になると CPU 使用量は約4倍になることが示されています。数メガバイトのデータを含むリクエストは、PHP 処理プロセスを数秒から数十秒間占有し、繰り返されるリクエストや同時リクエストは、利用可能なすべての PHP 処理プロセスを枯渇させ、正当なユーザーへのサービスを拒否します。影響は可用性に限定され、機密性や完全性への影響はありません。

## 実証

`league/commonmark 2.x がインストールされた PHP が必要です。テストツールは、実際の MarkdownParser と実際のブロック開始パーサーを使用して、パイプ記号を含まない段落を徐々に大きくし、GFM と Table 拡張機能を有効にした構成と、コア機能のみの構成を比較して、Table パーサーの貢献度を特定します。`

1. `league/commonmark` (2.10.1 または 2.x の任意のバージョン) をインストールします。
2. `GithubFlavoredMarkdownConverter` を使用して、パイプ記号を含まず、空白行を含まず、文字で始まらない多数の行を含む単一の大きな段落を変換します。
3. 段落のサイズが2倍になるにつれて、経過時間を測定します。

```php
<?php
require 'vendor/autoload.php';
use League\CommonMark\GithubFlavoredMarkdownConverter;

$converter = new GithubFlavoredMarkdownConverter();
foreach ([25000, 50000, 100000, 200000] as $lines) {
$md = str_repeat("12345678\n", $lines); // 一つの段落、空白行なし、'|'なし、アルファベットで始まらない行
$t = microtime(true);
$converter->convert($md);
printf("%7d lines %6.3fs\n", $lines, microtime(true) - $t);
}
```

```text
lines input アルファベットで始まるアルファベットで始まらない
("aaaaaaaa") ("12345678")
25000 0.23MB 0.27s 0.75s
50000 0.45MB 0.50s 2.36s
100000 0.90MB 1.07s 7.70s
200000 1.80MB 2.26s 27.81s
```

アルファベットで始まる入力は、線形に増加します（入力が2倍になると、時間が2倍になる）。これは、`SkipLinesStartingWithLettersParser` が、Table パーサーに到達する前に処理を停止するためです。一方、アルファベットで始まらない入力は、入力が2倍になると4倍の時間がかかります（0.75, 2.36, 7.70, 27.81）。これは、Table の開始を解析する部分が O(M^2) の計算量を持つことを示しています。

## 攻撃の連鎖

1. **脆弱性:** 攻撃者は、`GithubFlavoredMarkdownConverter`を使用して信頼できないMarkdownを変換するエンドポイント、または`TableExtension`を追加する環境に、Markdownの内容を送信します。デフォルトのGFMバンドルには、`TableExtension`が登録されています。`GithubFlavoredMarkdownExtension`は`TableExtension`を追加します（src/Extension/GithubFlavoredMarkdownExtension.php:30）、そして`TableExtension`は`TableStartParser`を登録します（src/Extension/Table/TableExtension.php:56）。
2. **制御:** 攻撃者は、Markdownの内容を完全に制御できます。エクスプロイトの入力は、空白行がなく、`|`文字が含まれておらず、文字で始まらない行で構成された1つの段落です（例：`str_repeat("12345678\n", 200000)`）。
3. **処理の流れ:** `MarkdownParser::parseLine()`は、段落がアクティブな間、すべての空白行に対してブロック開始パーサーを繰り返し処理します（src/Parser/MarkdownParser.php:135-147）。`ParagraphParser::tryContinue()`は、すべての空白行に対して段落を開いたままにし、バッファを拡張し続けます（src/Parser/Block/ParagraphParser.php:46-53）。各行は`ReferenceParser::parse()`によって1行ずつ追加されます（src/Reference/ReferenceParser.php:89-95）。バージョン2.0.2以降、最優先の`SkipLinesStartingWithLettersParser`は、先頭の空白以外の文字が文字である行に対して`BlockStart::abort()`を返し、`TableStartParser`の前に`findBlockStart()`を中断します。行が文字以外の文字（例えば数字）で始まる場合、そのパーサーは何も返さず、残りのコアパーサーもすべてnullを返すため、すべての行で`TableStartParser`が実行されます（src/Parser/MarkdownParser.php:224-236）。
4. **防御:** `MarkdownInput`には入力サイズの制限がなく、`max_nesting_level`はデフォルトで`PHP_INT_MAX`に設定されており、これは深さ1の段落では到達しません。バッファ全体の検索には、制限がありません。
5. **根本原因:** `TableStartParser::tryStart()`は、`getParagraphContent()`によって返されるバッファ全体に対して`strpos($paragraph, '|')`を実行します（src/Extension/Table/TableStartParser.php:35-38）。パイプ文字が含まれていない場合、`strpos`はすべての行でバッファの末尾までスキャンします。
6. **結果:**

累積的なスキャン処理はO(M^2)です。小さなリクエストでも、CPUの使用量が不均衡に、そして二次関数的に増加し、ワーカープロセスを枯渇させ、サービスを停止させる可能性があります。

## 脆弱性の詳細

このコードパスに対する以前の修正は存在しないため、これは不完全な修正やリグレッションの問題ではなく、これまで明らかにされていなかった、別の二次関数的な動作をする箇所です。最も強力な反証の試みがなされましたが、すべて失敗しました。

- 試行: 観測された二次関数的な動作は、コアパーサーやPHPの文字列処理のオーバーヘッドによるものであり、Tableパーサーによるものではない。反証: 2つの測定構成の唯一の違いは`TableStartParser`です。コアのみのベースラインは線形ですが、Tableのみの構成では、入力が2倍になると4倍になります。
- 試行: `strpos`が早期に終了するか、バッファが実際に増加しない。ソースコードのトレースによって反証: `ReferenceParser::parse()`は、状態遷移の前に、すべての行を無条件に追記します。パイプ文字を含まないテキストの場合、`strpos`は`|`を見つけられず、各行でバッファ全体をスキャンします。
- 試行: `TableStartParser`の前に、別のパーサーが早期に終了する。部分的に正しい: 2.0.2以降、`SkipLinesStartingWithLettersParser`は、アルファベットで始まる行について、ブロックの開始スキャンを中止します。したがって、アルファベットで始まる入力（元の`aaaaaaaa`のPoCを含む）は、Tableパーサーに到達せず、線形時間で処理されます。アルファベット以外の文字で始まる行は、すべてのコアパーサーを通過し、各行で`TableStartParser`に到達するため、二次関数的な動作を示します。
- 試行: 入力サイズまたはネストの制限によって、この問題が緩和される。反証: サイズ制限はなく、デフォルトのネスト制限に到達することはありません。
- 試行: これは既存の二次関数的なDoS脆弱性に関するアドバイザリーの重複であるか、すでに修正されている。反証: 公開されている二次関数的な脆弱性に関するアドバイザリーは、行ごとの位置変換や、他のファイルにある別のメカニズムを対象としています。`src/Extension/Table/TableStartParser.php`の`git log`を確認した結果、セキュリティに関する修正がこのリスキャン部分に適用されたことは一度もありません。このコードは、最新リリースでも変更されていません。

## 対象バージョン

- `Ecosystem: composer`
- `Package: league/commonmark`
- `影響を受けるバージョン: >= 2.0.0, <= 2.10.1`
- `確認された最新バージョン: 2.10.1 (Packagist, repo.packagist.org/p2/league/commonmark.json)`
- `修正状況: 未修正`

注: `SkipLinesStartingWithLettersParser` は 2.0.2 で導入されました。2.0.0 および 2.0.1 では、先頭に文字がある行でも問題が発生する可能性があります。いずれにしても、問題の根本原因である二次スキャンは、>= 2.0.0, <= 2.10.1 の範囲全体で存在します。

脆弱な再スキャンは、バージョン 2.8.0 および 2.10.1 (最新の公開バージョン) で確認されています。下限の 2.0.0 は、`getParagraphContent()` に基づくアーキテクチャを導入した 2.x ブロックパーサーの書き換えから推測されます。確認対象にはバージョン 2.8.0 から 2.10.1 までのタグのみが含まれているため、2.8.0 未満のバージョンについては検証されていません。公開されているどのバージョンでも、バッファ全体のスキャンが削除されたり、制限されたりすることはありません。

## 推奨される修正方法

各行のクイックチェックで、段落の最後の行のみを検査するようにします。これは、表のヘッダーを形成できる唯一の行だからです。`strrpos($paragraph, "\n")` を使用して最後の改行位置を計算し、最後の行を取得し、`strpos($lastLine, '|')` を使用して検査します。これにより、各行のチェックは最後の行の長さに制限され、二次的な動作を解消しつつ、表の検出の動作を変更しません。コードの変更なしの一時的な対策として、オペレーターは変換に使用される信頼できない Markdown のサイズを制限するか、信頼できない入力に対してテーブル拡張機能を無効にすることができます。これにより、影響を軽減できますが、根本的な二次的な処理を解消するわけではありません。

報告者: zx (GitHub: @manus-pi)。

影響を受けるパッケージ:
- Composer (PHP) league/commonmark: 影響を受けるバージョン >= 2.0.0, <= 2.10.1、2.10.2 で修正済み。