Merge pull request #10798 from SomberNight/202608_base43
What the developer wrote
Authored by Felix
Merge pull request #10798 from SomberNight/202608_base43
transaction: cap max tx size we allow for base43
What changed, and why it matters
This commit fixes a performance weakness in Electrum's handling of large Bitcoin transactions encoded in 'base43'. The base43 encoding and decoding functions run in quadratic time, meaning the work grows much faster than the input size. An attacker could send or feed Electrum a very large base43 transaction string and cause the program to freeze or become unresponsive for a noticeable period (a denial-of-service effect). The patch limits how large a base43 string Electrum will try to decode and also makes the encoder slightly faster. It does not fix the underlying quadratic algorithm.
Treat this as a low-to-moderate denial-of-service hardening patch. Users and downstream packagers should apply it. For a stronger fix, replace the base43 implementation with a linear-time algorithm or avoid base43 for large payloads entirely, as the FIXME comments suggest.
Security signals we found
Quadratic-time base43 encode/decode can be triggered on attacker-controlled input
Denial-of-service via CPU exhaustion / UI freeze on large transaction strings
Input-length cap added as a defensive guard, not a full algorithmic fix
Developer comment explicitly calls out the quadratic complexity and the DoS risk
No cryptographic weakness or funds-theft vector is present in the diff
Evidence from the diff
The base_encode/base_decode helpers in electrum/bitcoin.py use Python big-int arithmetic whose time complexity is O(n^2) in the input length. electrum/transaction.py uses base43 for QR-code serialization of transactions and also tries base43 when converting a raw transaction to hex. The patch adds a 30,000-character cap before attempting base43 decoding, with a comment that decoding that length takes ~0.2 s on the developer’s machine. It also reorders the decoding attempts (base64 before base43) and rewrites base_encode to build a bytearray in reverse and then reverse it, which is a modest constant-factor improvement. The quadratic behavior is explicitly acknowledged but not eliminated.
Changed components
electrum/bitcoin.py: base_encode(), base_decode()electrum/transaction.py: to_qr_data(), convert_raw_tx_to_hex()Inspect captured patch +25 / −9
### electrum/bitcoin.py
@@ -539,7 +539,10 @@ class BaseDecodeError(BitcoinException): pass
def base_encode(v: bytes, *, base: int) -> str:
- """ encode v, which is a string of bytes, to base58."""
+ """ encode v, which is a string of bytes, to base58.
+
+ note: time complexity is O(len(v)^2), due to big-int arithmetic.
+ """
assert_bytes(v)
if base not in (58, 43):
raise ValueError('not supported base: {}'.format(base))
@@ -552,10 +555,11 @@ def base_encode(v: bytes, *, base: int) -> str:
newlen = len(v)
num = int.from_bytes(v, byteorder='big')
- string = b""
+ string_rev = bytearray()
while num:
num, idx = divmod(num, base)
- string = chars[idx:idx + 1] + string
+ string_rev += chars[idx:idx + 1]
+ string = string_rev[::-1]
result = chars[0:1] * (origlen - newlen) + string
return result.decode('ascii')
@@ -564,6 +568,8 @@ def base_encode(v: bytes, *, base: int) -> str:
def base_decode(v: Union[bytes, str], *, base: int) -> Optional[bytes]:
""" decode v into a string of len bytes.
+ note: time complexity is O(len(v)^2), due to big-int arithmetic.
+
based on the work of David Keijser in https://github.com/keis/base58
"""
# assert_bytes(v)
### electrum/transaction.py
@@ -1228,7 +1228,8 @@ def to_qr_data(self) -> Tuple[str, bool]:
tx.convert_all_utxos_to_witness_utxos()
is_complete = False
tx_bytes = tx.serialize_as_bytes()
- return base_encode(tx_bytes, base=43), is_complete
+ tx_base43 = base_encode(tx_bytes, base=43) # FIXME this takes quadratic time in len(tx)
+ return tx_base43, is_complete
def txid(self) -> Optional[str]:
if self._cached_txid is None:
@@ -1499,17 +1500,26 @@ def convert_raw_tx_to_hex(raw: Union[str, bytes]) -> str:
return binascii.unhexlify(raw).hex()
except Exception:
pass
- # try base43
- try:
- return base_decode(raw, base=43).hex()
- except Exception:
- pass
# try base64
if raw[0:6] in ('cHNidP', b'cHNidP'): # base64 psbt
try:
return base64.b64decode(raw, validate=True).hex()
except Exception:
pass
+ # try base43
+ try:
+ # FIXME This takes quadratic time in len(tx).
+ # We could prefix all txs we base43-serialize with e.g. "BASE43TX:",
+ # (and break-compat with old versions). Then at least we would not attempt
+ # the expensive deser here if it's not needed.
+ if len(raw) > 30_000:
+ # note: base_decode for this length takes around 0.2 sec on my laptop.
+ # note: We only use/expect base43 inside QR codes. The max data a QR can fit is around 4 KB,
+ # serializing that to b43 results in a length of ~5500. 30k is already over 5x that.
+ raise ValueError("raw tx too large for base43")
+ return base_decode(raw, base=43).hex()
+ except Exception:
+ pass
# raw bytes
if isinstance(raw, (bytes, bytearray)):
return raw.hex()Why this scored 51/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.