Add bounds checks before base58 decoding #17511

sipa commented at 11:28 PM on November 18, 2019: member

DrahtBot added the label Tests on Nov 19, 2019

DrahtBot added the label Utils/log/libs on Nov 19, 2019

in src/base58.cpp:50 in 1dfd33b4ad outdated

  44 | +        zeroes++;
  45 | +        psz++;
  46 | +    }
  47 | +    size_t len = strlen(psz);
  48 | +    if (len > 1000000) return std::numeric_limits<size_t>::max();
  49 | +    return (len - 1) * 732 / 1000 + 1 + zeroes;

MarcoFalke commented at 2:28 AM on November 19, 2019:

Test cases order is shuffled using seed: 911766883

Entering test module "Bitcoin Core Test Suite"

test/key_io_tests.cpp(20): Entering test suite "key_io_tests"

test/key_io_tests.cpp(122): Entering test case "key_io_invalid"

base58.cpp:49:17: runtime error: unsigned integer overflow: 0 - 1 cannot be represented in type 'unsigned long'

    [#0](/bitcoin-bitcoin/0/) 0x55bab4eefc6d in DecodeBase58Size(char const*) /home/travis/build/bitcoin/bitcoin/build/bitcoin-x86_64-pc-linux-gnu/src/base58.cpp:49:17

    [#1](/bitcoin-bitcoin/1/) 0x55bab4eefa12 in DecodeBase58CheckSize(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) /home/travis/build/bitcoin/bitcoin/build/bitcoin-x86_64-pc-linux-gnu/src/base58.cpp:187:18

    [#2](/bitcoin-bitcoin/2/) 0x55bab4f4a6fc in (anonymous namespace)::DecodeDestination(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, CChainParams const&) /home/travis/build/bitcoin/bitcoin/build/bitcoin-x86_64-pc-linux-gnu/src/key_io.cpp:76:9

    [#3](/bitcoin-bitcoin/3/) 0x55bab4f4a4f5 in DecodeDestination(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) /home/travis/build/bitcoin/bitcoin/build/bitcoin-x86_64-pc-linux-gnu/src/key_io.cpp:217:12

    [#4](/bitcoin-bitcoin/4/) 0x55bab3a4be21 in key_io_tests::key_io_invalid::test_method() /home/travis/build/bitcoin/bitcoin/build/bitcoin-x86_64-pc-linux-gnu/src/test/key_io_tests.cpp:141:27

    [#5](/bitcoin-bitcoin/5/) 0x55bab3a4a529 in key_io_tests::key_io_invalid_invoker() /home/travis/build/bitcoin/bitcoin/build/bitcoin-x86_64-pc-linux-gnu/src/test/key_io_tests.cpp:122:1

    [#6](/bitcoin-bitcoin/6/) 0x55bab36fd3d5 in boost::detail::function::void_function_invoker0<void (*)(), void>::invoke(boost::detail::function::function_buffer&) /usr/include/boost/function/function_template.hpp:118:11

    [#7](/bitcoin-bitcoin/7/) 0x7f865d6212cd in boost::detail::function::function_obj_invoker0<boost::detail::forward, int>::invoke(boost::detail::function::function_buffer&) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x4b2cd)

    [#8](/bitcoin-bitcoin/8/) 0x7f865d62077c in boost::execution_monitor::catch_signals(boost::function<int ()> const&) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x4a77c)

    [#9](/bitcoin-bitcoin/9/) 0x7f865d620860 in boost::execution_monitor::execute(boost::function<int ()> const&) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x4a860)

    [#10](/bitcoin-bitcoin/10/) 0x7f865d620fdc in boost::execution_monitor::vexecute(boost::function<void ()> const&) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x4afdc)

    [#11](/bitcoin-bitcoin/11/) 0x7f865d64f8d0 in boost::unit_test::unit_test_monitor_t::execute_and_translate(boost::function<void ()> const&, unsigned int) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x798d0)

    [#12](/bitcoin-bitcoin/12/) 0x7f865d62bc6a in boost::unit_test::framework::state::execute_test_tree(unsigned long, unsigned int, boost::unit_test::framework::state::random_generator_helper const*) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x55c6a)

    [#13](/bitcoin-bitcoin/13/) 0x7f865d62c12d in boost::unit_test::framework::state::execute_test_tree(unsigned long, unsigned int, boost::unit_test::framework::state::random_generator_helper const*) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x5612d)

    [#14](/bitcoin-bitcoin/14/) 0x7f865d62c12d in boost::unit_test::framework::state::execute_test_tree(unsigned long, unsigned int, boost::unit_test::framework::state::random_generator_helper const*) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x5612d)

    [#15](/bitcoin-bitcoin/15/) 0x7f865d624cc7 in boost::unit_test::framework::run(unsigned long, bool) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x4ecc7)

    [#16](/bitcoin-bitcoin/16/) 0x7f865d64d13e in boost::unit_test::unit_test_main(bool (*)(), int, char**) (/usr/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.65.1+0x7713e)

    [#17](/bitcoin-bitcoin/17/) 0x55bab35f5d8b in main /usr/include/boost/test/unit_test.hpp:63:12

    [#18](/bitcoin-bitcoin/18/) 0x7f865b3afb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)

    [#19](/bitcoin-bitcoin/19/) 0x55bab34d9129 in _start (/home/travis/build/bitcoin/bitcoin/build/bitcoin-x86_64-pc-linux-gnu/src/test/test_bitcoin+0x2a40129)

practicalswift commented at 6:39 AM on November 19, 2019: contributor

Concept ACK

Thanks for fixing this!

sipa force-pushed on Nov 19, 2019

laanwj commented at 7:53 AM on November 19, 2019: member

~~I still stand by what I said in #17501 (comment)~~

I would say it's not the encoder/decoder responsibility to check input sizes. Good generic code works for any input size. But of course, the application side (e.g. address parsing routines) could have a check to see if inputs are reasonable. They have that knowledge.

~~Checking input sizes is not the responsibility of the decoding code, but of application specific code.~~

Never mind, you're doing this. I was surprised at the complexity of the DecodeBase58Size function, that it ignores a potentially infinite amount of spaces and ones. Don't we have tighter constraints on address lengths and such? I guess apparently not!

Concept ACK.

sipa commented at 8:30 AM on November 19, 2019: member

@laanwj Hmm, I think there is a better solution than this. We do have upper bounds on the encoded data as well, which would be fine. Alternatively, we could just make DecodeBase58(Check) take an additional argument for the max size on the encoded data.

laanwj commented at 8:36 AM on November 19, 2019: member

Ah yes, the number of '0' is not really unbounded, because they are counted and signify the padding. It basically just ignores an infinite amount of spaces around it. That's fine.

I think this solution is OK!

Alternatively, we could just make DecodeBase58(Check) take an additional argument for the max size on the encoded data.

I kind of like having a separate function to estimate the size. However, this would make it easier to ensure consistency between the functions, I guess.

in src/base58.cpp:67 in bfa56d844f outdated

  61 | @@ -44,8 +62,11 @@ bool DecodeBase58(const char* psz, std::vector<unsigned char>& vch)
  62 |          zeroes++;
  63 |          psz++;
  64 |      }
  65 | +    // Decoding a megabyte of Base58 takes minutes, seems like a reasonable upper limit.
  66 | +    size_t len = strlen(psz);
  67 | +    if (len > 1000000) return false;

laanwj commented at 8:36 AM on November 19, 2019:

Let's make 1000000 a constant, like BASE58_LIMIT.

sipa commented at 11:40 PM on November 19, 2019:

I've rewritten it, this constant is no longer necessary.

in src/base58.h:66 in bfa56d844f outdated

  59 | @@ -60,4 +60,15 @@ NODISCARD bool DecodeBase58Check(const char* psz, std::vector<unsigned char>& vc
  60 |   */
  61 |  NODISCARD bool DecodeBase58Check(const std::string& str, std::vector<unsigned char>& vchRet);
  62 |  
  63 | +/**
  64 | + * Compute a lower bound on the vchRet result from DecodeBase58Check.
  65 | + *
  66 | + * It will never overshoot, and will never undershoot by more than 0.25% plus 2.

laanwj commented at 8:40 AM on November 19, 2019:

"and will never undershoot by more than 0.25% plus 2" is not true in the case of trailing spaces, I think :smile:

sipa commented at 11:41 PM on November 19, 2019:

You're right, and that makes this whole approach wrong, as it will reject inputs that are too long just due to spaces at the end. I've changed the approach.

Pass a maximum output length to DecodeBase58 and DecodeBase58Check

Also remove a needless loop in DecodeBase58 to prune zeroes in the base256
output of the conversion. The number of zeroes is implied by keeping track
explicitly of the length during the loop.

2bcf1fc444

sipa force-pushed on Nov 19, 2019

Sjors commented at 10:46 AM on November 20, 2019: member

Note that there are various places, e.g. PSBT parsing, that call DecodeBase64 in strencodings directly, bypassing these new bounds checks.

laanwj commented at 10:48 AM on November 20, 2019: member

@Sjors DecodeBase64 doesn't have this problem, its runtime is linear on the input size.

practicalswift commented at 10:17 AM on November 25, 2019: contributor

@sipa

I think we should drop the default for max_ret_len since the default of std::numeric_limits<int>::max() is not a good or "natural" choice for most callers.

I think it would be preferable to not have a default for max_ret_len to make sure callers make an informed decision regarding max_ret_len.

Makes sense?

Add bounds checks in key_io before DecodeBase58Check 5909bcd3bf

sipa force-pushed on Dec 6, 2019

sipa commented at 12:32 AM on December 6, 2019: member

@practicalswift Done.

laanwj commented at 7:33 AM on December 6, 2019: member

code review ACK 5909bcd3bf3c3502355e89fd0b76bb8e93d8a95b (definitely agree that this is easier to review than the size estimation as separate function)

practicalswift commented at 8:47 AM on December 6, 2019: contributor

ACK 5909bcd3bf3c3502355e89fd0b76bb8e93d8a95b -- code looks correct

FWIW there is a base58 fuzzer in #17229 (currently at zero concept ACKs :)) which would be nice to have in the tree in addition to the unit tests to get further testing.

DrahtBot commented at 6:41 PM on December 11, 2019: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#17721 (util: Don't allow Base58 decoding of non-Base58 strings. Add Base58 tests. by practicalswift)
#17229 (tests: Add fuzzing harnesses for various Base{32,58,64} and hex related functions by practicalswift)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

laanwj referenced this in commit 3914e877c4 on Dec 12, 2019

laanwj merged this on Dec 12, 2019

laanwj closed this on Dec 12, 2019

sidhujag referenced this in commit 16c91db6c7 on Dec 12, 2019

jasonbcox referenced this in commit cf70ca7acc on Oct 28, 2020

sidhujag referenced this in commit 5a7c40f692 on Nov 10, 2020

furszy referenced this in commit 170beab56c on Jul 1, 2021

random-zebra referenced this in commit b4751e10ce on Aug 11, 2021

DrahtBot locked this on Dec 16, 2021