Affected: Kludex python-multipart

Python-Multipart is a streaming multipart parser for Python. Prior to 0.0.30, when parsing application/x-www-form-urlencoded bodies, QuerystringParser located the field separator with a two step lookup: it first scanned the entire remaining buffer for &, and only when no & existed anywhere ahead did it fall back to scanning for ;. For a body that uses ; as the separator and contains no &, every field iteration performed a full failed & scan over the entire remaining buffer before locating the nearby ;. With N semicolon separated fields in a chunk of size B, this yields O(B^2) byte comparisons per chunk. An attacker can submit a small crafted body of the form a;a;a;... and cause the parser to spend seconds of CPU per request. A handful of concurrent requests can exhaust worker processes. This vulnerability is fixed in 0.0.30.

Affected: PyPI: python-multipart

### Summary

When parsing `application/x-www-form-urlencoded` bodies, `QuerystringParser` located the field separator with a two step lookup: it first scanned the entire remaining buffer for `&`, and only when no `&` existed anywhere ahead did it fall back to scanning for `;`. For a body that uses `;` as the separator and contains no `&`, every field iteration performed a full failed `&` scan over the entire remaining buffer before locating the nearby `;`. With N semicolon separated fields in a chunk of size B, this yields O(B^2) byte comparisons per chunk.

An attacker can submit a small crafted body of the form `a;a;a;...` and cause the parser to spend seconds of CPU per request. A handful of concurrent requests can exhaust worker processes.

### Details

In `python_multipart/multipart.py`, both the `FIELD_NAME` and `FIELD_DATA` states located the next separator like this:

```python sep_pos = data.find(b"&", i) if sep_pos == -1: sep_pos = data.find(b";", i) ```

`data.find(b"&", i)` scans from `i` to the end of the buffer and returns `-1` only when there is no `&` anywhere in the remainder. For a `;` separated body with no `&`, this failed full buffer scan repeats once per field, making parsing quadratic in the body length.

For example, a 1 MiB url encoded body consisting of `a;` repeated ~500,000 times, submitted with `Content-Type: application/x-www-form-urlencoded`, causes the parser to perform on the order of 10^11 byte comparisons, consuming several seconds of C…

Affected: PyPI: python-multipart

### Summary

When parsing `application/x-www-form-urlencoded` bodies, `QuerystringParser` located the field separator with a two step lookup: it first scanned the entire remaining buffer for `&`, and only when no `&` existed anywhere ahead did it fall back to scanning for `;`. For a body that uses `;` as the separator and contains no `&`, every field iteration performed a full failed `&` scan over the entire remaining buffer before locating the nearby `;`. With N semicolon separated fields in a chunk of size B, this yields O(B^2) byte comparisons per chunk.

An attacker can submit a small crafted body of the form `a;a;a;...` and cause the parser to spend seconds of CPU per request. A handful of concurrent requests can exhaust worker processes.

### Details

In `python_multipart/multipart.py`, both the `FIELD_NAME` and `FIELD_DATA` states located the next separator like this:

```python sep_pos = data.find(b"&", i) if sep_pos == -1: sep_pos = data.find(b";", i) ```

`data.find(b"&", i)` scans from `i` to the end of the buffer and returns `-1` only when there is no `&` anywhere in the remainder. For a `;` separated body with no `&`, this failed full buffer scan repeats once per field, making parsing quadratic in the body length.

For example, a 1 MiB url encoded body consisting of `a;` repeated ~500,000 times, submitted with `Content-Type: application/x-www-form-urlencoded`, causes the parser to perform on the order of 10^11 byte comparisons, consuming several seconds of C…