Int/str conversions broken in latest Python bugfix releases

Maybe “10^1000000” then, computation takes me 0.4 seconds and conversion to str takes me 15 seconds.

I didn’t think anything about it other than to show a counterexample to the “there is no way for them to apply the “int->str is quadratic” part of the attack” that I replied to.

I haven’t seen a DoS-mitigation rationale quite like the current one - like you, I was looking for some reason to believe that an individual conversion near the limit was waaay slow, but that’s not the issue here. On the currently released CPyhon, on my pretty capable desktop box:

$ py -m timeit -s "s = '9' * 50000" "int(s)"
20 loops, best of 5: 10.6 msec per loop

So even now it appears instantaneous to a human eye, with an input string more than 10x longer than the new limit.

But they don’t care about that. Instead there’s some argument about “well, what if they have megabytes worth of strings of this size, and go through all of them as fast as possible? No matter the speed of an individual conversion, the lower the limit on an individual string, the smaller the aggregate time they can consume for going through all of a fixed overall total size of input strings, because conversion per string takes worse than time linear in the length of the string”.

If this is to be consistently applied, then essentially any operation a server farm can be talked into doing, that can consume a few milliseconds given an input of no more than several thousand bytes,. is equally a “DoS vulnerability”.

For example, this takes more than twice as long as the conversion above despite that the input string is 10 times shorter:

$ py -m timeit -s "import re; s = 'x' * 5000" "re.search('x*y$', s)"
10 loops, best of 5: 24 msec per loop

How can that not be a DoS vulnerability if converting a merely 5,000-digit string to int (which goes a couple hundred times faster) is?

I understand that users generally don’t get to supply the regexps an app uses for parsing. But they do supply the strings, and genuine expertise in writing regexps for an re engine like Python’s is rare. I’ve generally been the one to fix stdlib regexps that display exponential-time behavior in bad cases, but best I know nobody has ever even tried to probe for quadratic-time cases. Like converting a 50,000 digit string to int, one instance goes so fast nobody cares. Well, until now :wink:.

14 Likes

None of these operate in isolation, though. If an attacker is forced to send 100x the requests, that will be detected (and possibly handled) by other parts of the system, whereas one request that’s 100x the size will likely pass through as “normal” traffic.

Individual requests are also the granularity. With 100 x 10ms requests, other users get an opportunity every 10ms to get a request in. With 1 x 1000ms request, users have to wait over a second. So at least for this kind of DoS attack, we can make a big difference to those who are doing a fixed number of parses per request (e.g. Sebastian’s example above)

Those who allow an unlimited amount of data to be received and processed synchronously are in just as much trouble as they were before :wink:

2 Likes

Steve, I should have spelled this out: the regexp example I gave takes time quadratic in the length of the user-supplied string. The same O() behavior as int(user_supplied_str), although the regexp spelling has a much higher constant factor. There is no DoS argument you can make about one that can’t be made about the other, because they’re both ways of applying standard Python operations to user-supplied strings, with the same asymptotic behavior in the length of the strings.

# try at 5,000
$ py -m timeit -s "s = '9' * 5000" "int(s)"
2000 loops, best of 5: 112 usec per loop

$ py -m timeit -s "import re; s = '9' * 5000" "re.search('9*8$', s)"
10 loops, best of 5: 24 msec per loop

# try at 50,000 - about 10**2 = 100 times slower
$ py -m timeit -s "s = '9' * 50000" "int(s)"
20 loops, best of 5: 10.1 msec per loop

$ py -m timeit -s "import re; s = '9' * 50000" "re.search('9*8$', s)"
1 loop, best of 5: 2.39 sec per loop

A difference is that a hostile user has to find a vulnerable regexp in the stdlib, and contrive a bad-case input for it. Which I expect they’ll do, now that I’ve mentioned it :wink:.

9 Likes

I’ve opened a PR to refactor the PyLong_FromString function here:

3 Likes

What is the argument for limiting str(x) for integers? I understand the argument that int(s) can be used for DOS attack, but that does not explain why str(x) should be limited. If a program doesn’t allow big integers in its input, then it generally won’t try to output big integers either, unless it actually intends to print a big int.

Another problem that arises from limiting str(x) is that this kind of program

x = int(input())
print(x + 1)

will now get a very unexpected error on the print line by being given the input '9' * 4300. So the limit on str(x) essentially introduces overflow errors to Python. This wouldn’t have been the case if the limit was only introduced to int(s).

2 Likes

The CVE fix does not disable big integer support. It only prevents inefficient conversion from decimal text representation to integer and vice versa. Built-in Types — Python 3.12.1 documentation has a complete list of APIs that are limited. Octal, hexadecimal, and int from/to bytes conversions are not limited because they have linear complexity.

A possible attack vector is YAML as YAML supports hexadecimal integer notation. An attacker could send you a malicious YAML file with a very large hexadecimal number. If your application uses e.g. logging to log the value, then your application would be affected.

If you need to deal with very, very large numbers, then use hexadecimal notation. It’s much faster and unlimited. A decimal string with 1,000,000 digits takes about 4 seconds to convert on my system. A hexadecimal number string with 1,000,000 digits takes about 1.3 millisecond to convert.

2 Likes

As someone who’s still actively working on “Trojan Source” mitigations, I disagree. The main difference there is that the researchers were unwilling to wait for mitigations before making big announcements and trying to claim credit for it, but even despite this many of the biggest editors and renderers (the tools that need fixes, not the languages) had basic mitigations in place. Once Unicode publish more concrete guidance on how code renderers should handle Unicode, they’ll be able to move toward more targeted mitigations, but for now they’re using a similarly heavy hammer.

This doesn’t address the ability of libraries to use it and support their users who don’t want to upgrade. You can’t have an optional keyword argument that is ignored in older versions, and so every library that wants to use it ends up with a version-selected helper method anyway, likely until the end of time.

It also doesn’t address the fact that one user’s DoS is another user’s intentional calculation, but that is the user’s decision, not the library’s. Libraries that know users will commonly end up converting very large integers to/from strings to the point where they would consider adding a utility function to do it unsafely can equally just inform their users that some/many/all will need to modify how their app is run.

But most importantly, nothing will solve all the issues brought up in this thread, other than going back in time to having an implicit limit on the size of int again. Just like one day when we get rid of the recursion limit, then likely decide to bring it back because it’s useful for catching runaway bugs, this is likely something that we will come to appreciate as a reasonable check that prevents runaway work from being done.

Since my more exhaustive post was flagged[1], the only point I’d like to reiterate is that the SC eminently has the power to allow backporting a keyword to int() back to stable releases, which would solve this situation in a much less broken fashion.


  1. I’d be interested to hear how it can be considered off-topic or even discourteous… Relatedly, lack of transparency is not helped by hiding (even gentle) criticism. ↩︎

4 Likes

Because the conversion takes a very long time, and if you have a way to induce someone else’s app to generate a very large integer, then you may have a way to force it to freeze up while it converts that number to a string (e.g. it lies about the length of some content that an app tries to put into a Content-Length header).

I agree this is the less exploitable side, compared to parsing an arbitrarily long string, but it’s still possible. It’s also a bit weird for int(repr(x)) on an integer to fail on one side but not the other (though that is what used to happen in the past anyway, so maybe not so weird).

You just typed an entire screen’s worth of numbers into a prompt, is it really that unexpected? :wink:

You were also about to get an entire screen’s worth of numbers in response. Is that really helpful?

The default length limit is pretty arbitrary, yes, but it’s also well beyond the length of a number that humans can comprehend. They are valuable as intermediate results in a calculation, but we as people can’t do anything useful with numbers that big. Rendering it as “<4300 digits>” is probably much more useful, even without the leading ‘9’.

FWIW, I didn’t flag it and don’t agree with it being flagged.

Yes, and I’m sure they considered it and decided against it. Likely for the reasons I mentioned above, which they’ve used before for not backporting certain changes.

The SC is our new BDFL - they can, but don’t have to post justifications of their decisions. And the rest of us have agreed to accept them. Anyone who disagrees is more than welcome to run for the next SC to have more influence over it, but by definition, their decision is final.

@steve.dower I was talking about malicious user input. I wonder how many Python codes will crash unexpectedly from being given the input '9' * 4300.

The default length limit is pretty arbitrary,

What the exact limit is doesn’t matter. This “overflow” problem I’m describing would be happen even if the limit was 200 or 2000000.

From the testing we did to determine the initial default, not very much will crash unexpectedly. That’s how we landed on that number.

From the testing we did to determine the initial default, not very much will crash unexpectedly. That’s how we landed on that number.

I don’t see how you could possibly run tests on this. What kind of tests existed that checked if maliciously giving '9' * 4300 unexpectedly crashes the program before this new limit was introduced?

1 Like

I think you’re missing the point. We test for how much code is going to break on regular inputs, not malicious inputs. Code that was not being attacked and did not break continues to not break when it’s not being attacked.

Code that is being attacked will now break, whereas before it would simply eat up all your CPU time.

Code that previously worked and now breaks even though it’s not under attack is what we want to avoid. And we had the opportunity to build Python with various limits and run a huge range of code (public and private) through its paces to see if it was impacted.

Virtually nobody was testing for malicious inputs before, and because the mitigation is global, they don’t have to. If we pushed every library to implement their own mitigations, then everyone would be adding tests now to make sure that their own protections work, and users would have basically no idea whether the code they were using was protected or not.

3 Likes

Thanks for your responses!

Let me say first off that I have huge appreciation for the work of the security team. It’s a task with insane amount of responsibility/pressure, and not a lot of reward besides people complaining one way or another. All that said, your disagreement is unsurprising, because you’re so very close to the fire (which, OTOH makes you uniquely more qualified to comment than 99.9% of others here).

Let me rephrase my point thusly:

  • the impact of a given security-relevant topic is perceived greatly amplified within security circles, which – not least due to disclosure concerns – tends to operate in a sort of bubble where this perception can further feed back on itself.
  • people outside the security sphere have a different set of priorities (partially because the blood, sweat & tears of the security folks allows them to remain ignorant of problems), where not every security issue makes the world tumble from its axis and accepting breakage for a somewhat theoretical security concern is a tough pill to swallow[1].

I don’t propose to have an answer that’s obviously better than the others in balancing these very divergent needs, but I wanted to point out that the SC is not bound by “we cannot backport a feature to stable” – it’s a choice they have (and one that should have been discussed more publicly IMO), all the more so if they can at the same time decide to backport the security mitigation (and breakage that implies) to all stable releases.

With the caveat that this comes from the luxury of being only in the peanut gallery, I still think the reaction was overblown, not transparent enough, and breaking lots of people’s codes, projects, teaching examples, etc. was not worth it, or would have deserved way more public discourse, as well as advance communication.


  1. all the more so since DoS attacks aren’t nearly as critical as divulging sensitive information or remote privilege escalation / code execution. ↩︎

6 Likes

I wonder if decimal is affected by this change? And if not, could one not simply use decimal initially but return an int?

Other security issues with YAML aren’t relevant to the discussion about int/str conversion. It was used as an example of what is affected, not as an example of something that is completely secure in other ways.

3 Likes

No, it’s not. decimal_str <-> decimal.Decimal conversion are linear-time (in both directions).

You could do that - but it wouldn’t help :frowning_face:. It’s not the “string” part that’s the real problem, but instead converting between any representations whatsoever based on a power-of-2 base and a power-of-10 base. Your last int(decimal.Decimal) part becomes the quadratic-time part:

$ py -m timeit -s "import decimal; s = '9' * 10_000" "decimal.Decimal(s)"
1000 loops, best of 5: 283 usec per loop

# make input 10x longer, conversion takes about 10x longer (linear time)
$ py -m timeit -s "import decimal; s = '9' * 100_000" "decimal.Decimal(s)"
100 loops, best of 5: 2.82 msec per loop

# but if we go on to convert to int, about 100x longer (quadratic time)
$ py -m timeit -s "import decimal; s = '9' * 10_000" "int(decimal.Decimal(s))"
50 loops, best of 5: 8.84 msec per loop

$ py -m timeit -s "import decimal; s = '9' * 100_000" "int(decimal.Decimal(s))"
1 loop, best of 5: 854 msec per loop

If there’s an app out there that converts strings to decimal.Decimal first, and then to int, the current mitigation gimmick can’t stop a “DoS attack” based on that.

By far the most efficient way to convert a decimal string to a CPython int today is to install the gmpy2 extension (Python bindings for GMP), and use the latter to convert to GMP’s power-of-2 based internal representation first.

$ py -m timeit -s "import gmpy2; s = '9' * 10_000" "int(gmpy2.mpz(s))"
5000 loops, best of 5: 77.9 usec per loop

# Way sub-quadratic, but also super-linear.
# No linear time algorithm is known (or expected).
$ py -m timeit -s "import gmpy2; s = '9' * 100_000" "int(gmpy2.mpz(s))"
200 loops, best of 5: 1.84 msec per loop
3 Likes

Is this class of attacks (targeting intstr conversions) common enough and severe enough to justify a breaking change in such a core part of the Python API?

Was it also considered that this change enables a new class of attacks? For example, if the very large value is being logged on other users’ requests with logging.info(f"Value: {value}"), the application is now unusable instead of just slow.

intstr conversions are not mentioned in CVE-2020-10735 at all. I feel it’s unusual that a security fix goes this far beyond the scope of the associated CVE, so I would greatly appreciate if you could go into more detail about the reasoning behind this change. intstr conversions are mentioned on the PR, so I trust there was plenty of discussion around this. I do recognize that this was a hard situation with no easy answers for the Python Security Response Team, and I may be missing something here.

5 Likes