5 ms·

Can anyone TL;DR why? Why wouldn't it just return that long integer of all 1s?

sp332 4y ago
Yeah it's right at the top of the linked page?
schoen 4y ago
It's stated to be CVE-2020-10735, which is apparently about a denial of service by forcing Python to inefficiently convert a very large string to an integer, using a potentially ridiculous amount of CPU time. The CVE hasn't been published, but for example there's an explanation at https://bugzilla.redhat.com/show_bug.cgi?id=1834423 https://bugzilla.redhat.com/show_bug.cgi?id=1834423
- adgjlsfhk1 4y ago
  this seems like a dumb fix to the cve to me. why not just use a faster algorithm?
  - lifthrasiir 4y ago
    Because there is no linear-time algorithm for decimal-to-binary conversion. If we are to expose the bignum-aware `int` function to untrusted input there should be some limit anyway. I do think the current limit of 4301 digits seem too low though---if it were something like 1 million digits I would be okay.
    - schoen 4y ago
      It looks like there is some discussion of the algorithmic options at https://github.com/python/cpython/issues/95778 https://github.com/python/cpython/issues/95778 https://github.com/python/cpython/issues/90716 https://github.com/python/cpython/issues/90716 Is there something bad going on with Python's internal representation of big integers, too? I thought I might have understood Tim Peters to be saying that in the latter thread. It does look like gmpy2.mpz() is like 100 times faster than int() or something. Is this just because it's doing it all in assembly rather than in Python bytecodes, or are the Python data structures here also not so hot?
      - klodolph 4y ago
        > It does look like gmpy2.mpz() is like 100 times faster than int() or something. Is this just because it's doing it all in assembly rather than in Python bytecodes, or are the Python data structures here also not so hot? It's not the data structures. The data structures are really more or less the same: you have some array of words, with a length and a sign. The only real differences are in the particular length of word that you choose, which is not a very interesting difference. Assembly language optimizations do tend to matter here, because you're working with the carry bit for lots of these operations, and each architecture also has some different way of multiplying numbers. Multiplying numbers is "funny" because it produces two words of output for one word of input. There are also sometimes some different algorithms in use, and GMP uses some different algorithms depending on the size. Here's a page describing the algorithms used by GMP: https://gmplib.org/manual/Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms Here's a description of how carries are propagated: https://gmplib.org/manual/Assembly-Carry-Propagation https://gmplib.org/manual/Assembly-Carry-Propagation IMO, I wouldn't expect my language's built-in bigint type to use the best, most cutting-edge algorithms and lots of hand-tuned assembly. GMP is a specialized library for doing special things.
      - thehappypm 4y ago
        One of the comments showed the incredibly naive approach of just building the integer digit-by-digit: ‘1234’ => 1x1000 + 2x100 + 3x10 + 4x1 Is faster and has room to improve
        tylerhou 4y ago
        This takes (worse than) quadratic time.
        thehappypm 4y ago
        I’m not sure it does, in the best case. There are d additions, so the addition is linear time. Each multiplication is potentially quadratic, but it seems optimizable since it’s never multiplication of two large numbers—always one large and one small number.
    - adgjlsfhk1 4y ago
      there isn't a linear time algorithm, but there is an algorithm in O(n*log(n)^2) http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf which is pretty close. it also seems weird to have a CVE for "some algorithms don't run in linear time". should there be a 4000 element maximum for the size of list passed to sort?
      - lifthrasiir 4y ago
        > should there be a 4000 element maximum for the size of list passed to sort? Technically speaking, yes, there should be some limit if you are accepting an untrusted input. But there is a good argument for making this limit built-in for integers but not lists: integers are expected to be atomic while lists are wildly understood as aggregates, therefore large integers can more easily propagate throughout unsuspecting code base than large lists. (Or, if you are just saying that once you have sub-quadratic algorithms you don't need language-imposed limits anymore, maybe you are right.)
    - bjourne 4y ago
      But why convert it to binary? If you store the number as an array of digits the parsing process should be O(n).
      - lifthrasiir 4y ago
        That means every limb operation should be done modulo 10^k, which would be pretty expensive and only makes sense if you don't do much computation with them so the base conversion will dominate the computation.
      - thehappypm 4y ago
        Are you asking why computers store numbers in binary?
        bjourne 4y ago
        No. Many bignum libraries store numbers as sequences (or linked lists) of "digits", where each digit is an 8 to 256-bit binary number. Which is why I'm skeptical of lifthrasiir's claim that a bignum cannot be parsed in O(n) since it is analogous to initializing a list.
    - tylerhou 4y ago
      There is no practical linear time algorithm for multiplication; should Python disable multiplication for numbers greater than 10^4301? Even a naive divide and conquer decimal to binary algorithm is only logarithmically slower than multiplication.
  - wyldfire 4y ago
    But the multiplier is unbound, though. Faster wouldn't help in that case.
    - klyrs 4y ago
      Maybe we should limit the lengths of strings altogether. 512k should be enough for anybody.
- klyrs 4y ago
  Looks to me like the actual problem is in string.__mul__ -- that one's got arbitrary memory usage. Better limit those arguments...
  - masklinn 4y ago
    str.__mul__ is just a conveniently short way to demonstrate the issue, the target is pretty much any parsing routine exposed to outside users e.g. any JSON API.
    - klyrs 4y ago
      Apologies, my comment is snark. The algorithm in question is soft-linear, faster implementations exist, this seems like an incredibly myopic fix. Just make a bigger JSON blob and it will take longer to parse.
- deleted 4y ago
  [deleted]

Yeah it's right at the top of the linked page?

It's stated to be CVE-2020-10735, which is apparently about a denial of service by forcing Python to inefficiently convert a very large string to an integer, using a potentially ridiculous amount of CPU time. The CVE hasn't been published, but for example there's an explanation at https://bugzilla.redhat.com/show_bug.cgi?id=1834423 https://bugzilla.redhat.com/show_bug.cgi?id=1834423

adgjlsfhk1 4y ago
this seems like a dumb fix to the cve to me. why not just use a faster algorithm?
- lifthrasiir 4y ago
  Because there is no linear-time algorithm for decimal-to-binary conversion. If we are to expose the bignum-aware `int` function to untrusted input there should be some limit anyway. I do think the current limit of 4301 digits seem too low though---if it were something like 1 million digits I would be okay.
  - schoen 4y ago
    It looks like there is some discussion of the algorithmic options at https://github.com/python/cpython/issues/95778 https://github.com/python/cpython/issues/95778 https://github.com/python/cpython/issues/90716 https://github.com/python/cpython/issues/90716 Is there something bad going on with Python's internal representation of big integers, too? I thought I might have understood Tim Peters to be saying that in the latter thread. It does look like gmpy2.mpz() is like 100 times faster than int() or something. Is this just because it's doing it all in assembly rather than in Python bytecodes, or are the Python data structures here also not so hot?
    - klodolph 4y ago
      > It does look like gmpy2.mpz() is like 100 times faster than int() or something. Is this just because it's doing it all in assembly rather than in Python bytecodes, or are the Python data structures here also not so hot? It's not the data structures. The data structures are really more or less the same: you have some array of words, with a length and a sign. The only real differences are in the particular length of word that you choose, which is not a very interesting difference. Assembly language optimizations do tend to matter here, because you're working with the carry bit for lots of these operations, and each architecture also has some different way of multiplying numbers. Multiplying numbers is "funny" because it produces two words of output for one word of input. There are also sometimes some different algorithms in use, and GMP uses some different algorithms depending on the size. Here's a page describing the algorithms used by GMP: https://gmplib.org/manual/Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms Here's a description of how carries are propagated: https://gmplib.org/manual/Assembly-Carry-Propagation https://gmplib.org/manual/Assembly-Carry-Propagation IMO, I wouldn't expect my language's built-in bigint type to use the best, most cutting-edge algorithms and lots of hand-tuned assembly. GMP is a specialized library for doing special things.
    - thehappypm 4y ago
      One of the comments showed the incredibly naive approach of just building the integer digit-by-digit: ‘1234’ => 1x1000 + 2x100 + 3x10 + 4x1 Is faster and has room to improve
      - tylerhou 4y ago
        This takes (worse than) quadratic time.
        thehappypm 4y ago
        I’m not sure it does, in the best case. There are d additions, so the addition is linear time. Each multiplication is potentially quadratic, but it seems optimizable since it’s never multiplication of two large numbers—always one large and one small number.
  - adgjlsfhk1 4y ago
    there isn't a linear time algorithm, but there is an algorithm in O(n*log(n)^2) http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf which is pretty close. it also seems weird to have a CVE for "some algorithms don't run in linear time". should there be a 4000 element maximum for the size of list passed to sort?
    - lifthrasiir 4y ago
      > should there be a 4000 element maximum for the size of list passed to sort? Technically speaking, yes, there should be some limit if you are accepting an untrusted input. But there is a good argument for making this limit built-in for integers but not lists: integers are expected to be atomic while lists are wildly understood as aggregates, therefore large integers can more easily propagate throughout unsuspecting code base than large lists. (Or, if you are just saying that once you have sub-quadratic algorithms you don't need language-imposed limits anymore, maybe you are right.)
  - bjourne 4y ago
    But why convert it to binary? If you store the number as an array of digits the parsing process should be O(n).
    - lifthrasiir 4y ago
      That means every limb operation should be done modulo 10^k, which would be pretty expensive and only makes sense if you don't do much computation with them so the base conversion will dominate the computation.
    - thehappypm 4y ago
      Are you asking why computers store numbers in binary?
      - bjourne 4y ago
        No. Many bignum libraries store numbers as sequences (or linked lists) of "digits", where each digit is an 8 to 256-bit binary number. Which is why I'm skeptical of lifthrasiir's claim that a bignum cannot be parsed in O(n) since it is analogous to initializing a list.
  - tylerhou 4y ago
    There is no practical linear time algorithm for multiplication; should Python disable multiplication for numbers greater than 10^4301? Even a naive divide and conquer decimal to binary algorithm is only logarithmically slower than multiplication.
- wyldfire 4y ago
  But the multiplier is unbound, though. Faster wouldn't help in that case.
  - klyrs 4y ago
    Maybe we should limit the lengths of strings altogether. 512k should be enough for anybody.
klyrs 4y ago
Looks to me like the actual problem is in string.__mul__ -- that one's got arbitrary memory usage. Better limit those arguments...
- masklinn 4y ago
  str.__mul__ is just a conveniently short way to demonstrate the issue, the target is pretty much any parsing routine exposed to outside users e.g. any JSON API.
  - klyrs 4y ago
    Apologies, my comment is snark. The algorithm in question is soft-linear, faster implementations exist, this seems like an incredibly myopic fix. Just make a bigger JSON blob and it will take longer to parse.
deleted 4y ago
[deleted]