GHSA-r4xh-jqrq-34v2 json
smol-toml: Quadratic-time parse() from parseKey rescanning to end of document on each key line
published last mo. modified last mo.
- cvss
- 5.3
- version 3.1, GitHub
- cisa kev
- Not listed
- not in CISA's catalog
- epss
- —
- no score, EPSS covers CVEs only
- public exploits
- 0
- none known
Summary
### Summary
`parse()` has a quadratic-time path in `parseKey`, reachable on default options with ordinary valid input. For every key line and table-header line, `parseKey` (dist/struct.js, lines 58 and 86) finds the dotted-key separator with `ctx.s.indexOf('.', ctx.p)`, where `ctx.s` is the whole document. When a key has no `.` ahead of it, that search runs all the way to the end of the input, and the result is then clamped back to the line terminator `endPtr` - so everything scanned past the current line is wasted. `parseKey` runs once per line, so a document of N dot-free keys costs O(n^2).
The most ordinary TOML shape triggers it: a flat list of `key = value` lines, or a repeated `[[a]]` table. No dotted keys, no special options, valid input throughout.
### Proof of concept
```js import { parse } from 'smol-toml'
let doc = '' for (let i = 0; i < 256000; i++) doc += 'k' + i + ' = 1\n'
console.time('parse') parse(doc) // ~2.8 MB of valid TOML, default options console.timeEnd('parse') ```
Doubling the line count roughly quadruples the time:
| lines | size | parse() | |---|---|---| | 32k | 0.3 MB | 0.3 s | | 64k | 0.7 MB | 1.0 s | | 128k | 1.4 MB | 3.5 s | | 256k | 2.8 MB | 14 s |
### Impact Any service that runs `parse()` on attacker-supplied TOML can be stalled. The work is synchronous, so it blocks the whole event loop, and the quadratic is unbounded: a ~7 MB body pins a core for about a minute, larger bodies for several.
### Patches Version 1.9.0 uses a different implementation for parsing keys which is strictly linear.
### Workarounds Limit the maximum document size accepted when parsing arbitrary documents.
Patch / fix
- npm smol-toml 1.9.0
Is GHSA-r4xh-jqrq-34v2 in your dependencies? Fencer shows which of your repositories are affected as soon as an advisory lands, and opens the fix as a pull request.
Check with FencerCVSS scores
| assigned by | version | score | vector |
|---|---|---|---|
| GitHub | 3.1 | 5.3 | CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L |
Affected packages
| ecosystem | package | affected | fixed in |
|---|---|---|---|
| npm | smol-toml | <1.9.0 |
1.9.0 |
Classification
- Weakness
-
- CWE-407 Inefficient Algorithmic Complexity
References
Sources
- GitHub Advisory GHSA-r4xh-jqrq-34v2
- Maintainer advisory GHSA-r4xh-jqrq-34v2
Fencer Intel keeps one entry per vulnerability: the CVE id wins, then GHSA, and records that alias each other are merged, except that two CVEs always keep separate entries. The same data is available as JSON.
The maintainers of squirrelchat/smol-toml published their own advisory on GitHub. Reviewed sources take precedence over it.