Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Wed, 21 Sep 2022 08:41:16 -0400
From: Demi Marie Obenour <>
Subject: Re: big ints in python: CVE-2020-10735

On Wed, Sep 21, 2022 at 09:17:21AM +0300, Georgi Guninski wrote:
> There was recent discussion of big ints in python and libgmp.
> ===
> gh-95778: Converting between int and str in bases other than 2
> (binary), 4, 8 (octal), 16 (hexadecimal), or 32 such as base 10
> (decimal) now raises a ValueError if the number of digits in string
> form is above a limit to avoid potential denial of service attacks due
> to the algorithmic complexity. This is a mitigation for CVE-2020-10735
> ====
> ===
> In algorithms with quadratic time complexity using non-binary bases ...
> The highest threat from this vulnerability is to system availability.
> ===
> AFAICT the quadratic complexity is quadratic in the size of the int,
> that is its logarithm.

This is correct, and IMO it is just a bug in Python.  Python should
either provide better algorithms itself, or use an external library that
does so.  Using GMP would be a good choice where available, but would
require using GMP’s non-allocating functions, as the allocating ones
abort in out-of-memory situations.
Demi Marie Obenour (she/her/hers)
Invisible Things Lab

Download attachment "signature.asc" of type "application/pgp-signature" (834 bytes)

Powered by blists - more mailing lists

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.