Repository navigation
CVE-2020-10735: Prevent DoS by large int<->str conversions #95778
Description
Activity
- changed the title
[-]Placeholder issue for a specific security fix[/-][+]CVE-2020-10735: Prevent DoS by large int<->str conversions[/+]on Sep 2, 2022 28 remaining items
But if some version of Tim's suggestions in #90716 went in, billion digit conversions might become feasible. :-) But at that point, maybe we'd be able to drop these limits entirely?
Removing the limit might not be feasible as after this feature some code could come to depend on its existence indirectly to protect other things in whole systems from large values, knowingly or not. That doesn't mean we couldn't, just that it'd need consideration.
We also need to consider the worst case performance of any fancier algorithm before removing the ability to limit it. Untrusted data seeking a DoS would target that. Ex: If a faster conversion algorithm is typically
$O(n * log_2(n))$ but devolves into$O(n^2)$ on some values, we need to handle the worst case unexpected computation.A notebook could even be designed to avoid half the problem by having their REPL repr and storage code auto-switch to hex for large values.
This is appalling.
Situation: people pass untrusted data to slow built-in functions. Reasonable solution: a) patch vulnerable programs, b) optimize said functions. CPython's solution: just limit stuff.
Your rationale is founded on the fact that developers constantly add bugs and fixing them is not an option. Fixing bugs is like, more than half of what developers normally do.
When ReDoS was discovered, did we limit the number of iterations of the matching algorithm? No. Then why should we do the same here? There are dangerous tools, but they are often much more useful due to lack of artificial limits. When did we drop "Special cases aren't special enough to break the rules."
To add insult to injury, people seem to be talking about limiting
reprtoo. How many bugs that will cause, I can't tell: I saw people userepr(...)to generate non-Python code as a universal solution that works with both integers and strings, and I foresee problems when it starts generating non-digit strings.You're limiting integer to string conversions. How soon are you going to limit
repr(list)because of the billion laughs attack?Why is
_PY_LONG_MAX_STR_DIGITS_THRESHOLDeven a constant? No one's going to recompile Python, and if people actually start using this security "feature", chances are it'll be enabled everywhere, and then programs that use big arithmetic and parse numbers from the user input will silently stop working. It's not even big arithmetic, really: the discussed limit toreprseems to be only 512 bit, which is much less than thousands-of-bits numbers used in cryptography right now, in Python. In fact, the problem doesn't go away if it's variable: the problem is that it's global, affecting the whole application rather than the user-facing part. When did we drop "Explicit is better than implicit?"And then, has anyone actually researched how much trusted code parses integers from untrusted sources directly? To me it seems that even ReDoS should be more popular than this. I think people seldom call
inton user input directly: they either use parsing libraries likejsonandyaml, or (hear me out) use (web) frameworks that parse the data themselves. Either way, there's a finite number of places where checks should be added, and even if it's tens of places, it's so much better than limiting every single program, including those that don't even face the outer world, because it'll be actually configurable.I don't think I even understand why a limit is added in the first place. If Python used a quadratic algorithm for multiplication instead of FFT, that would not be considered a vulnerability but an inefficiency. There are much faster algorithms than the one used by CPython, I literally found one by googling "subquadratic base conversion". There: Richard P. Brent and Paul Zimmermann, Modern Computer Arithmetic. #90716, the issue that was tracking this, was dropped because what, developers tried to invent stuff themselves instead of comparing with state of art, and just chose the simplest option after an inevitable failure?
Reacted by Oleksandr Kulkov, Magnus Hokland Hegdahl, dorijanko, Kent, akcube, dnialh, Anson Hu, Lyrical, Radoslav Dimitrov, Andrew Yuan and 20 moreReacted by Gregory P. Smith and Łukasz LangaReacted by Magnus Hokland Hegdahl, Kent, akcube, Anson Hu, Cheran, Riley, Áron Noszály and JanAs a reminder to everybody the Python Community Code Of Conduct applies here.
Closing. This is fixed. We'll open new issues for any follow up work necessary.
Reacted by Magnus Hokland Hegdahl, akcube, Anson Hu, Radoslav Dimitrov, Golovanov399, Alex, Thien Udomsrirungruang, Riley, Alisa Sireneva, Oskar Haarklou Veileborg and 3 moreEveryone auditing all existing code for this, adding length guards, and maintaining that practice everywhere is not feasible nor is it what we deem the vast majority of our users want to do.
If applications don't validate their data before running str <-> int conversions, I'm not entirely sure that having an exploit that allows attackers to crash the application with an unexpected ValueError instead of merely slowing it down for a few seconds is a great improvement.
I'm only a naive developer but this kinda feels like the fix is worse than the problem its solving. What I am missing?
Please redirect further discussion to discuss.python.org.
- locked as resolved and limited conversation to collaborators
on Sep 6, 2022 Further Discussion
... is taking place in discuss.python.org threads
- linked a pull request that will close this issuegh-95778: add doc missing in some places #100627
on Dec 30, 2022
Problem
A Denial Of Service (DoS) issue was identified in CPython because we use binary bignum’s for our
intimplementation. A huge integer will always consume a near-quadratic amount of CPU time in conversion to or from a base 10 (decimal) string with a large number of digits. No efficient algorithm exists to do otherwise.It is quite common for Python code implementing network protocols and data serialization to do
int(untrusted_string_or_bytes_value)on input to get a numeric value, without having limited the input length or to dolog("processing thing id %s", unknowingly_huge_integer)or any similar concept to convert anintto a string without first checking its magnitude. (http,json,xmlrpc,logging, loading large values into integer via linear-time conversions such as hexadecimal stored inyaml, or anything computing larger values based on user controlled inputs… which then wind up attempting to output as decimal later on). All of these can suffer a CPU consuming DoS in the face of untrusted data.Everyone auditing all existing code for this, adding length guards, and maintaining that practice everywhere is not feasible nor is it what we deem the vast majority of our users want to do.
This issue has been reported to the Python Security Response Team multiple times by a few different people since early 2020, most recently a few weeks ago while I was in the middle of polishing up the PR so it’d be ready before 3.11.0rc2.
Mitigation
After discussion on the Python Security Response Team mailing list the conclusion was that we needed to limit the size of integer to string conversions for non-linear time conversions (anything not a power-of-2 base) by default. And offer the ability to configure or disable this limit.
The Python Steering Council is aware of this change and accepts it as necessary.
Linked PRs