A Python security fix breaks (some) bignums

Typically, an urgent security release of a project is not for a two-year-old CVE, but such is the case for a recent Python release of four versions of the language. The bug is a denial of service (DoS) that can be caused by converting enormous numbers to strings—or vice versa—but it was not deemed serious enough to fix when it was first reported. Evidently more recent reports, including a remote exploit of the bug, have raised its importance—causing a rushed-out fix. But the fix breaks some existing Python code, and the process of handling the incident has left something to be desired, leading the project to look at ways to improve its processes.

Python integers can have an arbitrary size; once they are larger than can be stored in a native integer, they are stored as arbitrary-length "bignum" values. So Python can generally handle much larger integer values than some other languages. Up until recently, Python would happily output a one followed by 10,000 zeroes for print(10**10000). But as a GitHub issue describes, that behavior has been changed to address CVE-2020-10735, which can be triggered by converting large values to and from strings in bases other than those that are a power of two—the default is base 10, of course.

The fix is to restrict the number of digits in strings that are being converted to integers (or that can result from the conversion of integers) to 4300 digits for those bases. If the limit is exceeded, a ValueError is raised. There are mechanisms that can be used to change the limit, as described in the documentation for the Python standard types. The value for the maximum allowable digits can be set with an environment variable (PYTHONINTMAXSTRDIGITS), a command-line argument (-X int_max_str_digits), or from within code using sys.set_int_max_str_digits(). It can be set to zero, meaning there is no limit, or any number greater than or equal to a lower-limit threshold value, which is set to 640.

Collateral damage

After the release was made on September 7, Oscar Benjamin posted a complaint about it to the Core Development section of the Python discussion forum. He noted that the new limit causes problems for the SageMath mathematics application (bug report) and the SymPy math library (Benjamin's bug report). The fix for the bug is a significant backward-compatibility break, because of 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".

Furthermore, the ways to alter the limit are all global in nature; a library cannot really do much about it, since changing it would affect the rest of the program. Applications like SageMath can probably just set the limit (back) to zero, but not SymPy:

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?

He wondered why the choice was made to switch the longstanding behavior of int() and str(), rather than creating new variants, such as safe_int(), that enforced this limit. Programs that wanted the new behavior could switch to using those functions, but the default would remain unchanged. Benjamin was hoping that the change could be reconsidered before it became "established as the status quo" but that is not going to happen.

Steve Dower apologized for how the bug fix was handled. The problem had been reported to various security teams, which then converged on the Python Security Response Team (PSRT), he said. That group agreed that fixing it in the Python runtime was the right approach, but making that actually happen took too long:

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.

As might be guessed, the problem stems from untrusted input. The PSRT tried a number of different approaches but settled on forcing the limit, he said:

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.

Gregory P. Smith, who opened the GitHub issue and authored the fix, noted that the int_max_str_digits setting is not specific to a particular thread, so changing it in one thread may affect others, as Benjamin suggested. Because the scope of the change was simply a security fix, no new features could be added, Smith said, but he expects that some kind of execution context to contain the setting (and perhaps others) will be added for Python 3.12, which is due in 2023. Meanwhile, he understands that some libraries may need to change the setting even though that has more wide-ranging effects:

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.

Beyond that, Smith is sympathetic to the complaints, but the intent was "to pick something that limited the global amount of pain caused". They saw no way to satisfy all of the different users of Python, 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" to deal with the change.

In addition, it had gotten to the point where the PSRT was concerned that other Python distributors would decide to apply their own fixes, which could lead to fragmentation within the ecosystem. Smith is also a member of the Python steering council; he and the other members felt that this was the only reasonable path:

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.

But Benjamin noted that PEP 387 ("Backwards Compatibility Policy") seems to preclude removing a feature without notice, though it does provide a steering council escape hatch, which was used here. While security is a reasonable concern, he was unhappy that "security apparently trumps compatibility to the point that even providing a reasonable alternative for a long standing very much core feature can be neglected". In particular, he complained that no alternative conversion function (e.g. large_int()) was added for code that wants to be able to convert arbitrarily long strings and integers. He wrote a version of that function to demonstrate that the tools being provided are inadequate to allow libraries like SymPy to write their own:

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)

Since another thread could be changing the limit at the same time, all bets are off for a multi-threaded Python program when calling that function. Benjamin and others also brought up the performance of the current conversion code, better algorithms for conversions, and other plans for the future, all of which may well deserve more coverage down the road. But much of the focus of the discussion was about the process of making a change like this, with no warning, and its effects on other projects in the Python community.

For example, "Damian" pointed out that there is a community using Python for studying number theory; the language has a low barrier to entry "because of the unbounded nature of Python integers and the very easy syntax to learn". But this change has erected a new barrier and the way to restore the previous behavior is buried; "it took me ~15 paragraphs of reading from the release notes to the documentation, to subtopics in the documentation" to find what is needed. Smith agreed ("yuck") and filed a bug to improve the documentation.

Why 4300?

The limit of 4300 digits seems rather arbitrary—why not 4000 or 5000, for example? Tim Peters said that it did not make sense to him; "I haven't been able to find the reasoning behind it". Tests on his system showed that numbers that large could be converted "well over a thousand times per second", which seemed like it would not really create a denial-of-service problem. But Smith said that the limit was chosen for just that reason; he filled in a bit more background on the attack, though the full details of it still have not been disclosed as of this writing:

Picture a CPU core handling N things [per] second, which can include a few megabytes of data which could be something full of a thousand integer strings (ie: JSON). It's still possible to get something to spin an entire CPU core for a second in an application like that even with the 4300 digit limit in place. What isn't possible anymore is getting it to spend infinite time by sending the same amount of data. With mitigation in place an attack now [needs] to scale the data volume linearly with desired cpu wastage just like other existing boring avenues of resource waste.

Steven D'Aprano lamented that secrecy, however, noting that there have been multiple disclosures of similar bugs along the way.

I don't buy the need to push out a fix to this without public discussion. This class of vulnerability was already public, and has been for years.

Even if it turns out that the chosen solution is the best, or only, solution, the secrecy and "trust us, we know best" from the security team was IMO not justified.

Smith said that the vulnerability is not "in any way exciting, new, or novel". The decision was made to keep it private "because it hadn't publicly been associated with the Python ecosystem". That may turn out to be the wrong choice, in truth, but we will not know that until we see the exploit(s) the security team was working with.

Peters asked again about the value of the digit limit. Neil Schemenauer said that it "was chosen to not break a numpy unit test". Ofek Lev called that "extraordinarily arbitrary" and wondered if there was proof that was actually the case. Andre Müller was in favor of the change "because it makes Python safer", but he also wondered about 4300. Christian Heimes filled in the details:

4,300 happens to be small enough to have int(s) in under 100 usec on modern hardware and large enough to pass unit tests of popular projects that were in our internal test [systems]. My initial value was 2,000, which is easier to remember and more than large enough for a 4k RSA key in decimal notation. We later bumped it up to 4,300 because the test suites of some popular Python projects like NumPy were failing with 2,000.

Chris Angelico thought that the limit was "extremely aggressively chosen"; it could be quite a bit higher without causing major problems, he said. Dower agreed that was possible, "but as we've seen from the examples above, the people who are unhappy about the limit won't be happy until it's completely gone". Given that, having a lower limit means those people will encounter and work around the problem that much sooner.

The discussion continues as of this writing and it looks like there are some real efforts toward better fixes down the road, but for now users of lengthy bignums need to make adjustments in their code. It is unfortunate that the community did not get to pitch in on the solution, as there are a few different suggestions in the thread that seem at least plausibly workable—with less impact. We will have to wait and see what the original vulnerability report(s) have to say; no one has said so specifically, but one hopes those will be released at some point soon. The two-year gap between report and fix is worrisome as well, but the security team is aware of that problem and, with luck, working on a fix for that as well.