Remove backtracking from parsing tarfile members and headers

[sethmlarson]

Bug description:

Today the tarfile module parsing of header values allows for backtracking when parsing header values. Headers have a well-known format that doesn't require backtracking to parse reliably, the new method of parsing will only require a single pass over a byte stream.

CPython versions tested on:

CPython main branch

Operating systems tested on:

No response

Linked PRs

• gh-121285: Remove backtracking when parsing tarfile headers #121286
• [3.13] gh-121285: Remove backtracking when parsing tarfile headers (GH-121286) #123542
• [3.12] gh-121285: Remove backtracking when parsing tarfile headers (GH-121286) #123543
• [3.11] gh-121285: Remove backtracking when parsing tarfile headers (GH-121286) #123639
• [3.10] gh-121285: Remove backtracking when parsing tarfile headers (GH-121286) #123640
• [3.9] gh-121285: Remove backtracking when parsing tarfile headers (GH-121286) #123641
• [3.8] gh-121285: Remove backtracking when parsing tarfile headers (GH-121286) #123642

[gpshead]

main version merged. I'll let you work out any non-automatic backports.

[picnixz]

(I just added the labels that still require the backports and you could remove them one by one when you're done)

[frenzymadness]

The CVE description contains:

Regular expressions that allowed excessive backtracking during tarfile.TarFile header parsing are vulnerable to ReDoS via specifically-crafted tar archives.

but the test added to verify the fix does not cause/test the ReDoS. I mean, when you run the test with unpatched Python, it raises tarfile.ReadError as well just with a different message, for example:

tarfile.ReadError: file could not be opened successfully:
- method gz: ReadError('not a gzip file')
- method bz2: ReadError('not a bzip2 file')
- method xz: ReadError('not an lzma file')
- method tar: ReadError('bad checksum')

Could you please help me understand how one of the regexes (fox example: br"(\d+) ([^=]+)=") can cause a regex backtracking? There is no combination of greedy nested quatifiers, greedy quantifiers are limited by the character class and I don't see a need for the regex algorithm to go back and consider another path if the match is not found.

[sethmlarson]

@frenzymadness Apologies for the confusion, not all of the regular expressions in the PR have issues with backtracking. The regex you mention was replaced to process the entire tar header block in one pass rather than multiple passes.

[mcepl]

Patch for Python 3.8 applies more or less painlessly on the 3.6 branch as well.