Re: big ints in python: CVE-2020-10735

[Demi Marie Obenour <demi () invisiblethingslab com>]

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

Attachment: signature.asc
Description: