[prev in list] [next in list] [prev in thread] [next in thread] 

List:       oss-security
Subject:    Re: [oss-security] big ints in python: CVE-2020-10735
From:       Demi Marie Obenour <demi () invisiblethingslab ! com>
Date:       2022-09-21 12:41:16
Message-ID: YysGcZi/hcw7bPNs () itl-email
[Download RAW message or body]


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

["signature.asc" (application/pgp-signature)]

[prev in list] [next in list] [prev in thread] [next in thread]