Base58 decoding is done without checking that the input size is reasonable #17501

issue practicalswift openend this issue on November 17, 2019

practicalswift commented at 9:46 pm on November 17, 2019: contributor

Base58 decoding is currently done without checking that the input size is reasonable.

This can lead to excessive decoding run time if an attacker can control the base58 input being decoded.

DecodeBase58/DecodeBase58Check(…) run time sampled with varying input sizes:

1 000 bytes: 1 ms
10 000 bytes: 97 ms
100 000 bytes: 8 865 ms (9 seconds)
1 000 000 bytes: 857 440 ms (14 minutes)
10 000 000 bytes: too long :)

DecodeBase58/DecodeBase58Check(…) is reachable via the RPC interface using the following code paths:

 0addmultisigaddress(JSONRPCRequest const&) → AddrToPubKey(CKeyStore*, std::string const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 1createpsbt(JSONRPCRequest const&) → ConstructTransaction(UniValue const&, UniValue const&, UniValue const&, UniValue const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 2createrawtransaction(JSONRPCRequest const&) → ConstructTransaction(UniValue const&, UniValue const&, UniValue const&, UniValue const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 3createwallet(JSONRPCRequest const&) → CWallet::CreateWalletFromFile(interfaces::Chain&, WalletLocation const&, unsigned long) → CWallet::LoadWallet(bool&) → WalletBatch::LoadWallet(CWallet*) → ReadKeyValue(CWallet*, CDataStream&, CDataStream&, CWalletScanState&, std::string&, std::string&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 4deriveaddresses(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeExtKey(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 5deriveaddresses(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeExtPubKey(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 6deriveaddresses(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 7deriveaddresses(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 8dumpprivkey(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
 9fundrawtransaction(JSONRPCRequest const&) → FundTransaction(CWallet*, CMutableTransaction&, long&, int&, UniValue) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
10generatetoaddress(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
11getaddressinfo(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
12getdescriptorinfo(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeExtKey(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
13getdescriptorinfo(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeExtPubKey(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
14getdescriptorinfo(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
15getdescriptorinfo(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
16getreceivedbyaddress(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
17importaddress(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
18importmulti(JSONRPCRequest const&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
19importmulti(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeExtKey(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
20importmulti(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeExtPubKey(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
21importmulti(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
22importmulti(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
23importmulti(JSONRPCRequest const&) → ProcessImportLegacy(ImportData&, std::map<CKeyID, CPubKey, std::less<CKeyID>, std::allocator<std::pair<CKeyID const, CPubKey> > >&, std::map<CKeyID, CKey, std::less<CKeyID>, std::allocator<std::pair<CKeyID const, CKey> > >&, std::set<CScript, std::less<CScript>, std::allocator<CScript> >&, bool&, UniValue const&, std::vector<CKeyID>&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
24importmulti(JSONRPCRequest const&) → ProcessImportLegacy(ImportData&, std::map<CKeyID, CPubKey, std::less<CKeyID>, std::allocator<std::pair<CKeyID const, CPubKey> > >&, std::map<CKeyID, CKey, std::less<CKeyID>, std::allocator<std::pair<CKeyID const, CKey> > >&, std::set<CScript, std::less<CScript>, std::allocator<CScript> >&, bool&, UniValue const&, std::vector<CKeyID>&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
25importprivkey(JSONRPCRequest const&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
26importwallet(JSONRPCRequest const&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
27listreceivedbyaddress(JSONRPCRequest const&) → ListReceived(interfaces::Chain::Lock&, CWallet*, UniValue const&, bool) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
28listreceivedbylabel(JSONRPCRequest const&) → ListReceived(interfaces::Chain::Lock&, CWallet*, UniValue const&, bool) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
29listunspent(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
30loadwallet(JSONRPCRequest const&) → LoadWallet(interfaces::Chain&, WalletLocation const&, std::string&, std::string&) → CWallet::CreateWalletFromFile(interfaces::Chain&, WalletLocation const&, unsigned long) → CWallet::LoadWallet(bool&) → WalletBatch::LoadWallet(CWallet*) → ReadKeyValue(CWallet*, CDataStream&, CDataStream&, CWalletScanState&, std::string&, std::string&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
31scantxoutset(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeExtKey(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
32scantxoutset(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeExtPubKey(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
33scantxoutset(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → (anonymous namespace)::ParsePubkey(Span<char const> const&, bool, FlatSigningProvider&) → (anonymous namespace)::ParsePubkeyInner(Span<char const> const&, bool, FlatSigningProvider&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
34scantxoutset(JSONRPCRequest const&) → Parse(std::string const&, FlatSigningProvider&, bool) → (anonymous namespace)::ParseScript(Span<char const>&, (anonymous namespace)::ParseScriptContext, FlatSigningProvider&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
35sendmany(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
36sendtoaddress(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
37sethdseed(JSONRPCRequest const&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
38setlabel(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
39signmessage(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
40signmessagewithprivkey(JSONRPCRequest const&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
41signrawtransactionwithkey(JSONRPCRequest const&) → DecodeSecret(std::string const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
42validateaddress(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
43verifymessage(JSONRPCRequest const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
44walletcreatefundedpsbt(JSONRPCRequest const&) → ConstructTransaction(UniValue const&, UniValue const&, UniValue const&, UniValue const&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
45walletcreatefundedpsbt(JSONRPCRequest const&) → FundTransaction(CWallet*, CMutableTransaction&, long&, int&, UniValue) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)

Other code paths involving base58-decoding:

0IsValidDestinationString(std::string const&, CChainParams const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
1LoadWallet(interfaces::Chain&, std::string const&, std::string&, std::string&) → LoadWallet(interfaces::Chain&, WalletLocation const&, std::string&, std::string&) → CWallet::CreateWalletFromFile(interfaces::Chain&, WalletLocation const&, unsigned long) → CWallet::LoadWallet(bool&) → WalletBatch::LoadWallet(CWallet*) → ReadKeyValue(CWallet*, CDataStream&, CDataStream&, CWalletScanState&, std::string&, std::string&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
2LoadWallets(interfaces::Chain&, std::vector<std::string, std::allocator<std::string > > const&) → CWallet::CreateWalletFromFile(interfaces::Chain&, WalletLocation const&, unsigned long) → CWallet::LoadWallet(bool&) → WalletBatch::LoadWallet(CWallet*) → ReadKeyValue(CWallet*, CDataStream&, CDataStream&, CWalletScanState&, std::string&, std::string&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)
3WalletBatch::RecoverKeysOnlyFilter(void*, CDataStream, CDataStream) → ReadKeyValue(CWallet*, CDataStream&, CDataStream&, CWalletScanState&, std::string&, std::string&) → DecodeDestination(std::string const&) → (anonymous namespace)::DecodeDestination(std::string const&, CChainParams const&) → DecodeBase58Check(std::string const&, std::vector<unsigned char>&)

laanwj commented at 8:38 am on November 18, 2019: member

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.
practicalswift commented at 8:58 am on November 18, 2019: contributor

@laanwj Yes, that information would need to be either a.) provided by the caller for enforcement in DecodeBase58, or b.) enforced by the caller itself. As you say DecodeBase58 as it works today has no concept of “reasonable size” obviously :)

Also the documentation of DecodeBase58 should probably be updated to reflect this obligation of the caller.
laanwj commented at 9:56 am on November 18, 2019: member

In any case, I think the surprising thing here, for most users of strings encodings such as Base64, is that decode time doesn’t scale linearly with size. It would make sense to document that. (this is because it’s implemented with bigint arithmetic, and bigint arithmetic is not linear time in operations)
laanwj added the label Resource usage on Nov 18, 2019
laanwj closed this on Dec 12, 2019
sidhujag referenced this in commit 16c91db6c7 on Dec 12, 2019
sidhujag referenced this in commit 5a7c40f692 on Nov 10, 2020
DrahtBot locked this on Dec 16, 2021
knst referenced this in commit 1809f27599 on Jun 7, 2022
knst referenced this in commit 85c28b4b1f on Jun 8, 2022

Contributors
practicalswift laanwj

Labels
Resource usage