Date: Wed, 21 Sep 2022 08:41:16 -0400 From: Demi Marie Obenour <demi@...isiblethingslab.com> To: oss-security@...ts.openwall.com 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. > > https://docs.python.org/3.10/whatsnew/changelog.html#security > > === > 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 > ==== > > https://cve.mitre.org/cgi-bin/cvename.cgi?name=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. -- Sincerely, 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.