No work limit on normalize() in any released version (RDFC-1.0 §4.4.3), and data for choosing the 4.0.0 maxPermutations default

オープン
  • 何か問題がありますか？
#368 コメント 2 件 リアクション 0 件 担当者 1 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

@mielvds がすでに取り組んでいます。

2026年11月9日 から。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
35/100
issue の種類
機能追加
明瞭さ
おおむね明確
活発さ
活発
技術スタック
python
領域
security

調査の方向性

Start by reviewing the unreleased 4.0.0 maxPermutations implementation and the RDFC-1.0 §4.4.3 requirement. Compare candidate defaults against the specification test suite and the poison-graph and acyclic-control measurements linked in the issue; done means the default is supported by evidence that it stops the cyclic attacks without rejecting legitimate inputs, with a release decision addressed.

索引モデルが issue の本文から書いたものです。

説明

Hello — we benchmarked RDFC-1.0 canonicalization across several implementations
for a paper we are about to post to arXiv, and we would rather give you the
numbers before it goes out than after.

What we measured

In PyLD 3.3.0 — the current PyPI release — jsonld.normalize() places no bound
on the Hash N-Degree Quads recursion. RDFC-1.0 §4.4.3 states that implementations
MUST defend against denial-of-service by raising an exception and terminating
early, and the note there suggests a call limit derived from the blank node count.

The cost of not having one is small to trigger. A complete graph K_5 — five
mutually referencing blank nodes in 527 bytes of JSON-LD — costs about
278x a plain credential. K_8, at 1,196 bytes, runs for seconds. The cost
follows the symmetry of the blank-node references rather than the document size,
so a request-size cap is not a defence: the attack fits inside any limit a
verifier would plausibly set.

We also measured what a caller can do about it today. A timeout imposed from
outside the call returns to the caller on schedule but does not stop the work —
canonicalization keeps a core busy afterwards. In Python, the only control we
found that actually interrupts the computation is a SIGALRM delivered to the
main thread, which is not available to a library consumer running in a worker
thread or under an async framework.

What we found in master

While writing this up we found that the unreleased 4.0.0 already adds
maxPermutations (default 10000) and raises
maximum canonicalization work exceeded. That addresses the issue, and we have
corrected our paper to say that no released version exposes a limit rather
than that PyLD exposes none.

Two things we think are still worth raising:

  1. There is no release that has it. pip install pyld today gives 3.3.0.
    If 4.0.0 is close, cutting it would do more for users than anything we could
    suggest here.

  2. Choosing the default is the harder half, and we have data on it. On the
    JavaScript side, rdf-canonize 5.0.0 ships maxWorkFactor=1, which stops
    every cyclic family we tried — but it also aborts acyclic inputs with 16
    and 20 blank nodes, and 18 cases of the RDFC-1.0 specification test suite.
    The clean separation we measured — every cyclic attack family stopped, every
    legitimate input admitted — appears one step looser than that. In other words
    a default tight enough to feel safe can reject well-formed credentials that
    merely have many structurally similar blank nodes, and the threshold deserves
    to be picked against measurements rather than intuition. We are happy to run
    a sweep of maxPermutations over your own corpus or test suite if that would
    be useful.

Reproducing

The poison-graph generators and the measurement harness are at
https://github.com/fujie/vcbench — the families are complete graphs K_n, rings
C_n, cubic circulants, and an acyclic forest control, so false positives are
visible as well as true positives.

On disclosure

We are not reporting this as an embargoed vulnerability and are not asking for
one. RDFC-1.0 documents dataset poisoning in §7.1 and requires a defence in
§4.4.3, so there is nothing here an attacker could not derive from the
specification; what the paper contributes is the price of the missing default,
in bytes and milliseconds on commodity hardware. We expect to post it in the
coming weeks and are glad to cite a 4.0.0 release if one lands first.

Thank you for PyLD — and for FrozenDocumentLoader, which is the other half of
what we end up recommending to verifiers.

Naohiro Fujie and Shigeya Suzuki

主要言語
Python
スター
689
フォーク
140
平均マージ
2日 16時間
マージ済み PR（30日）
11

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

digitalbazaar/pyld のほかの issue

digitalbazaar/pyld の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。