Int/str conversions broken in latest Python bugfix releases

Core Development
1

The latest bugfix releases of all supported Python versions break printing or parsing large integers e.g.:

>>> import math
>>> math.factorial(1559)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300) for integer string conversion

This follows from issues in Sage and SymPy:
https://trac.sagemath.org/ticket/34506

As of Python versions 3.10.7, 3.9.14, 3.8.14, 3.7.14 (all pushed yesterday) this change applies to all supported versions of Python:
https://mail.python.org/archives/list/python-dev@python.org/message/B25APD6FF27NJWKTEGAFRUDNSVVAFIHQ/

The CPython issue where this change was discussed is here:

The issue and the release notes refer to this CVE:

However when I go that page I see no useful information at all. The only thing I can establish is that the CVE is “reserved”.

Problems with the change were pointed out in the issue but then the discussion was shutdown and it was suggested to “redirect further discussion to discuss.python.org.” so that’s what I’m doing here.

To be clear this is a significant backwards compatibility break. The fact that int(string) and str(integer) work with arbitrarily large integers has been a clearly intended and documented feature of Python for many years. I can’t see any way to reconcile this change or the process around it with the sort of statements in the Python backwards compatibility policy (PEP 387):

The only possibly applicable part I can find is this:

  • The steering council may grant exceptions to this policy. In particular, they may shorten the required deprecation period for a feature. Exceptions are only granted for extreme situations such as dangerously broken or insecure features or features no one could reasonably be depending on (e.g., support for completely obsolete platforms).

Presumably here it is the word “insecure” that justifies a potential SC exception. The OP of the issue suggests that this supposed vulnerability has been known about for over 2 years though. During that time many releases of Python were made and nothing was done to address this. Now when a potential fix arrives how is it so urgent that it should be backported to all release branches and released within days?

From a process perspective I really don’t understand how the decisions were made that lead to breaking changes being committed, dissenting views ignored, and then the changes pushed out two days later to every version of Python simultaneously to fix an issue that apparently was not urgent for the previous two years.

There are also technical problems with the way that this has been done. Consider this from the perspective of SymPy: every call to str or int is now a potential bug that might fail for large integers and there are lots of such calls:

$ git grep 'int(' | wc -l
10003

What exactly can SymPy replace those calls to int or str with?

The documentation says that the limit can be configured with an environment variable, a command line flag or with a setter function but all of these have the effect of setting a global variable somewhere. For Sage that is probably a manageable fix because Sage is mostly an application. SymPy on the other hand is mostly a library. A library should not generally alter global state like this so it isn’t reasonable to have import sympy call sys.set_int_max_str_digits because the library needs to cooperate with other libraries and the application itself. Even worse the premise of this change in Python is that calling sys.set_int_max_str_digits(0) reopens the vulnerability described in the CVE so any library that does that should then presumably be considered a vulnerability in itself. The docs also say that max_str_digits is set on a per interpreter basis but is it threadsafe? What happens if I want to change the limit so that I can call str and then change it back again afterwards?

There should at minimum be alternative functions that can be used in place of int and str for applications that do want to work with large integers. Those alternative functions should just work and not depend in any way on any global flags so that they can function as dropin replacements for the previous functionality that has existed for many years. This is a basic consideration with a compatibility break: what is the replacement code that should be used downstream to achieve the precise equivalent of the previous behaviour?

Of course some things can’t be fixed by providing alternative functions and a clear example of that is int.__str__ which might be called indirectly by any number of other functions. There is no way for SymPy etc to work around the fact that large integers just can’t be printed any more:

>>> print(10**10000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300) for integer string conversion

On the other hand though why am I even talking about making alternative functions to do what the previous functions already did? The alternative functions should be the new functions like safe_int and safe_str that are not susceptible to these problems. The existing functions int and str should just be left as they were and had been for many years.

I find it hard to see this as a real security fix. If code is doing int(gigabyte_long_untrusted_string) then isn’t it obvious that that might be slow? Why are massive untrusted strings being fed into something like int that clearly does nontrivial processing (check the length first?)? Couldn’t there just be an option like int(string, maxdigits=100)? Isn’t this just something to be fixed in parsing libraries?

I can think of many other ways to address the potential security concerns but a global flag that breaks integer/string conversions would never have made it into my shortlist. There is one very simple way to address the security concern while not breaking integer/string conversions: this feature of limiting the size of integers could be optional and disabled by default. The application that actually wants this can enable the limit.

Please reconsider this change and do not allow it to become established as the status quo.

41 Likes
2

Our apologies for the lack of transparency in the process here. The issue was first reported to a number of other security teams, and converged in the Python Security Response Team where we agreed that the correct fix was to modify the runtime.

The delay between report and fix is entirely our fault. The security team is made up of volunteers, our availability isn’t always reliable, and there’s nobody “in charge” to coordinate work. We’ve been discussing how to improve our processes. However, we did agree that the potential for exploitation is high enough that we didn’t want to disclose the issue without a fix available and ready for use.

We did work through a number of alternative approaches, implementing many of them. The code doing int(gigabyte_long_untrusted_string) could be anywhere inside a json.load or HTTP header parser, and can run very deep. Parsing libraries are everywhere, and tend to use int indiscriminately (though they usually handle ValueError already). Expecting every library to add a new argument to every int() call would have led to thousands of vulnerabilities being filed, and made it impossible for users to ever trust that their systems could not be DoS’d.

We agree it’s a heavy hammer to do it in the core, but it’s also the only hammer that has a chance of giving users the confidence to keep running Python at the boundary of their apps.

Now, I’m personally inclined to agree that int->str conversions should do something other than raise. I was outvoted because it would break round-tripping, which is a reasonable argument that I accepted. We can still improve this over time and make it more usable. However, in most cases we saw, rendering an excessively long string isn’t desirable either. That should be the opt-in behaviour.

Raising an exception from str may prove to be too much, and could be reconsidered, but we don’t see a feasible way to push out updates to every user of int, so that will surely remain global.

4 Likes
3

Those who value the ability to see huge values in base 10 can configure a different limit or disable it entirely as documented in Built-in Types — Python 3.10.7 documentation.

For the REPL/Notebook >>> prompt result case being annoying - agreed - that is one major use case that FR: Change `int` repr on huge values to automatically use hexadecimal · Issue #96601 · python/cpython · GitHub could address, though it has its own caveats so no decision has been made there.

4

[quote=“Gregory P. Smith, post:3, topic:18889, username:gpshead”]
Those who value the ability to see huge values in base 10 can configure a different limit or disable it entirely as documented in [Built-in Types — Python 3.10.7 documentation]

I explained why this is insufficient above. How should a library achieve the equivalent of int(string) (as it existed in previous Python versions for many years) without altering or depending on any global state?

8 Likes
5

It is literally “per interpreter” meaning all threads in your interpreter. :frowning: (which should mean sub-interpreters get their own limit… if this causes more use of sub-interpreters, that’ll be an interesting consequence)

Why did we feel we had to do that? The CPython internals do not currently have a fully fleshed out concept of an execution context within which interpreter internals settings can be carried around.

Otherwise we’d very much like this to be something that a context could disable without impacting the broader application. Unfortunately that level of feature extending development is too large for a security fix. It makes for a possible 3.12+ feature request though. I imagine an API resembling this:

with sys.int_max_str_digits_context(allowed_digits_at_least=9_999_999):  # >= N or 0
    ... # something you know may intentionally involve huge base conversions.

Where that would only apply to the current linear code flow execution context inside that with statement block, not other threads or other async context switches (including gc).

Though even that may not be enough because it really comes down to some specific types like Fraction just naturally dealing with unruly integer sizes where you’d like to just label all use of that type as “may consume oodles of CPU” and have calculations related to it always be immune. That’s beyond a mere execution context and is more tied to specific data (an int attribute perhaps?)

1 Like
6

I think there may not be a choice for some applications or libraries. If a project/framework/library decides to say, “we can’t live with this limit”, and include a Warning in their documentation telling users that the limit has been disabled, the consequences, why, how to opt-out of that or re-enable it, and what different limits may be more appropriate for what purposes if they choose to do so, that is entirely up to them. I consider it reasonable even though I fully agree with the philosophy that changing a global setting from a library is an anti-pattern.

Blanket disabling or configuring the limit very high for stated reasons also serves as a good signal back to us as a project of where we need to improve CPython to better serve parts of the community.

(Sorry, your post was long it’s easy for me to lose track of everything in there).

2 Likes
7

This CVE is owned by the RedHat CNA, they are aware of the need to get its text updated, assign CVSS scores, and mark it public with MITRE. There is no good way to do a security release with every little thing happening at the same time across multiple global organizations many of whom are volunteers.

8

ContextVars are designed to be usable for this kind of thing – very cheap to access, opaque namespace so no way for accidental collision or leakage, etc. Decimal and float context settings were two of the major motivating use cases, so this would be right up the same alley.

Obviously the work would still need to be done and I respect not wanting to attempt it in the RC stage; just saying a lot of the infrastructure is already there for when/if someone does take it on.

Having a kwarg to int at least to use an explicit limit for a single call seems like a very reasonable addition too.

8 Likes
9

Honestly I disagree with this whole change and think that it is bad for Python as a language but just putting that aside for a moment and presuming that it is necessary to break ordinary int/str conversion: why can’t pure functions be provided to do what the (also pure) functions previously did? It shouldn’t be necessary to even consider thread-safety etc: there should be functions that simply retain the old behaviour.

It’s disappointing that the core Python team has pushed out breaking (supposedly “bugfix”) releases for all supported versions with no notice and without providing even the basic compatibility functions that would have been demanded in any normal deprecation process. After reading PEP 387 and looking at this the impression I have is that there is a backwards compatibility policy until the SC makes an exception at which point there are no rules and anything can be broken in any kind of release without any requirement for even basic considerations to mitigate any kind of breakage even if it potentially means permanently degrading the language.

(I really hope PEP 387 gets improved after this)

29 Likes
10

As much as I agree with the sentiment, this was a practicality beats purity decision.

I totally get why you and some others dislike this change. We’re really sorry for those who this change causes pain. We tried to pick something that limited the global amount of pain caused. Python’s user base and usage scenarios are quite diverse. We saw no way to satisfy everyone.

Your example showing 10k int( calls in a project also happens to demonstrate why. All of those could need auditing to determine if they might ever handle huge data. Same with str( %s "{}" repr %r %d and so on. Such auditing would need to happen and be redone continually as code evolves, new code is added, new call paths use code transitively throughout the application, etc. So we chose the “secure by default” approach as that flips the story such that only the less common code that actually wants to deal with huge integers in decimal needs to do something simpler in response to this: raise or disable the limit and live life as they always have.

Could this have been done better? Undoubtedly. Was there anyone who was going to do it? No. So we made the decision.

When doing something that is needed as a back-ported security fix our options are restricted to non-invasive changes. Ex: We can’t add a parameter to int() or new intended for heavy use library functions in patch releases. Those are all good ideas for 3.12+ as features where we have a chance to define a happier integer story for everyone using Python. It wouldn’t surprise me if third party PyPI libraries spring up offering things along these lines to existing versions as well.

Similarly if we don’t address something in a particular supported Python release, other distributors of Python who have customers demanding security mitigation may cause them to provide one whether we like what they’ve done or not. If we don’t offer a recommended solution ourselves, they could wind up doing their own thing to their runtime, fragmenting the community compatibility matrix further.

(Steering Council hat:)

We don’t take this kind of change lightly.

We weren’t happy with any of the available options.

But those also included not being happy with continuing to do nothing and sitting on it for longer, or continuing to do nothing and letting it become public directly or via any of the disappointed at our lack of action reporters.

6 Likes
11

How long was this under discussion/consideration?

12

Honestly, I thought this problem was fixed 2 or 3 years ago. It’s not a perfect solution, but the consensus was that it was a necessary evil, and there was nothing better.

If the solution causes issues, just disable it, or set limit to more reasonable value (I do not think that pending several days in parsing or formatting an integer is reasonable in any program). Most programs do not work with such large integers, they will only benefit from adding this guard.

2 Likes
13

This would be about the time that it came to the PSRT with a description and example of how it could be remotely exploited, and how impractical the “obvious” mitigation would be. That remote exploitation is what pushed it past the “acceptable evil” level.

14

I think that the security risk here is probably a bit overblown but leaving that aside there is a real process problem here where security apparently trumps compatibility to the point that even providing a reasonable alternative for a long standing very much core feature can be neglected. The compatibility policy (PEP 387) says:

  • Similarly a feature cannot be removed without notice between any two consecutive releases.

Note that that’s referring to minor releases but here we’re talking about patch releases. I realise that there is also an exception in the policy for things that are “insecure” if granted by the SC but I would expect the consideration of compatibility options for downstream should weigh much more heavily when breaking all the other principles of the compatibility policy and process.

Presumably any codebase that would be happy with the change just pushed out would also be happy to just s/int/safe_int. In fact they would be happier because then they would know that they weren’t depending on some global flag for security. Note that the global flag isn’t even thread-safe so it could be switched out by another thread.

On the other hand a codebase that actually wants to use potentially large integers can’t do s/int/large_int because the large_int function hasn’t been provided. Some codebases or combinations of codebases (i.e. many libraries as part of an application) will want to do both. If you want to sometimes parse large integers and sometimes parse untrusted input it isn’t possible to simply call safe_int in some places and large_int in others because the separate functions are not provided. The behaviour is only controllable by a global flag that isn’t even thread-safe:

def large_int(s: str):
    # This function is not thread-safe.
    # It could fail to parse a large integer.
    # It could also undermine security of other threads
    old_val = sys.get_int_max_str_digits()
    try:
        sys.set_int_max_str_digits(0)
        return int(s)
    finally:
        sys.set_int_max_str_digits(old_val)

By contrast look how easy it is to write the safe_int function in any version of Python:

def safe_int(s: str):
    if len(s) > 5400:
        raise ValueError
    return int(s)

Suppose I provide an implementation of a change of base algorithm that is sub-quadratic and has reasonable performance for the largest strings and integers up to some very large size. Would it then be considered that the security problem (at least at core level) was fixed in a better way? Then what happens to this set/get API that has been introduced and can presumably never be removed again? Will the flag have to be respected forever because some code will come to depend on this as the way of limiting inputs rather than actually writing secure parsing code?

For comparison here is the performance of GMP on a single core of an ageing CPU (Intel(R) Core(TM) i5-3427U CPU @ 1.80GHz):

In [1]: import gmpy2

In [2]: s = '1' * 10**7

In [3]: %time i = gmpy2.mpz(s)
CPU times: user 928 ms, sys: 16 ms, total: 944 ms
Wall time: 942 ms

In [4]: s = '1' * 10**8

In [5]: %time i = gmpy2.mpz(s)
CPU times: user 14.9 s, sys: 88 ms, total: 15 s
Wall time: 14.9 s

In [6]: i.bit_length()
Out[6]: 332192807

Here I really have to get up to gigabyte sized strings before I start to see run times of minutes:

In [10]: s = '1' * 10**9

In [11]: %time i = gmpy2.mpz(s)
CPU times: user 3min 43s, sys: 2.85 s, total: 3min 46s
Wall time: 3min 45s

Any larger than this and my poor little computer will just run out of RAM.

Part of the difference with GMP here is due to asymptotically faster arithmetic but the biggest difference is just using a sub-quadratic algorithm for base conversion. A reference was given in the issue for such an algorithm Richard P. Brent and Paul Zimmermann, Modern Computer Arithmetic. The algorithms given there for base conversion are algorithms 1.25 and 1.26 in section 1.7 (Base conversion). Here is a pure Python implementation of algorithm 1.25 which is not exactly complicated:

def parse_int(S: str, B: int = 10) -> int:
    """parse string S as an integer in base B"""
    m = len(S)
    l = list(map(int, S[::-1]))
    b, k = B, m
    while k > 1:
        last = [l[-1]] if k % 2 == 1 else []
        l = [l1 + b*l2 for l1, l2 in zip(l[::2], l[1::2])]
        l.extend(last)
        b, k = b**2, (k + 1) // 2
    [l0] = l
    return l0

This algorithm has complexity M(n/4)*log(n) where M(m) is the complexity of multiplying two m bit integers. It’s not clear how much faster this would be for large inputs if implemented in C since the runtime will be dominated by the large integer operations any way. On this machine parse_int is faster than int for strings greater than around 1 megabyte e.g. it can do a 10 megabyte string in 1 minute:

In [10]: %time i = parse_int('1' * 10**6)
CPU times: user 1.33 s, sys: 36 ms, total: 1.36 s
Wall time: 1.36 s

In [11]: %time i = parse_int('1' * 10**7)
CPU times: user 58.5 s, sys: 104 ms, total: 58.6 s
Wall time: 58.6 s

Here is int by comparison:

In [13]: %time i = int('1' * 10**6)
CPU times: user 7.24 s, sys: 20 ms, total: 7.26 s
Wall time: 7.26 s

In [14]: %time i = int('1' * 10**7) # killed after 5 minutes
Terminated

This parse_int function is clearly a lot slower than GMP but still asymptotically it will be a lot faster than int. It’s possible it can be improved with micro-optimisations or that a better algorithm could be used or that implementing it in C would make it some amount faster.

22 Likes
15

No, but we’d change the default limit. Potentially back to infinite, if the algorithm was good enough, but the ability to limit would remain.

Ultimately, it’s a user setting (where “user” can be both the developer using the library in their application, and the user of the application). This is why it’s okay for it to be global. Libraries, once installed, are now the responsibility of the user and not the library author. If a library requires larger parsing limits as a normal part of its operation, that will be very obvious to users of that library, who will then be able to adjust the limit they’re using or use a different library.

By analogy, it’s like having a network firewall. Just because a library thinks it deserves to bypass the firewall, it doesn’t get to unless the user approves.[1] Giving this kind of control to the user is a regular feature of Python (e.g. no “private” attributes).

That said, I’m still personally in favour of allowing more focused ways to adjust the limit. A per-context setting would be nice, as would additional int() and str() and format(), etc. arguments. But these are not sufficient to close off the underlying issue (we tried, we really did), so the starting point is more restrictive.

The more examples we can collect of regular behaving apps that are impacted (i.e. not contrived examples, not runaway behaviours, etc.), the better design we can put together for additional features.

But it wasn’t an option to announce to the world that they could easily lock up any Python service remotely so that we could have that discussion. We had to get a viable fix out first.

  1. And to continue the analogy, the user opens up the firewall for the entire application, not just certain code paths, much like what happens here. ↩︎

2 Likes
16

Are you going to s/int/safe_int/ across all your dependencies too, or wait for them to push updates one by one? A global flag means you don’t need to worry about whether it’s your code or someone else’s that actually calls int().

4 Likes
17

I’m very appreciative of that this was a difficult choice and that there was no way to make all groups of users happy. But one group of users I would like to bring up is users practicing number theory in Python using only the Python language and the standard library, not advanced third party libraries like sympy.

Because of the unbounded nature of Python integers and the very easy syntax to learn it has historically been a very low barrier to entry for such users. As this is now a new barrier it would be nice if in the release notes it very clearly stated how to disable this in the easiest possible way for such users, e.g. sys.set_int_max_str_digits(0).

Currently it took me ~15 paragraphs of reading from the release notes to the documentation, to subtopics in the documentation, to correlating the information with sys.int_info.str_digits_check_threshold to sys.set_int_max_str_digits. To me this seems like a much bigger barrier to entry than this group of users has ever faced before.

17 Likes
18

Indeed. That’s why some discussion on the better algorithm feature request - Quadratic time internal base conversions · Issue #90716 · python/cpython · GitHub - favors keeping the fancier algorithms in pure Python.

19

yuck, agreed! Tracking in Reduce user friction: Improve docs on how to work around our integer to/from decimal str length limit · Issue #96722 · python/cpython · GitHub

3 Likes
20

Would it be sensible for IDLE to disable the limit, with 0, in the user-code execution process? Should it make a difference if the code comes from >>> or the editor? (I am not sure how easy the latter would be.)

4 Likes