Length-extension glitch

BIP32Node.verify() allows longer signatures than it should.

This is the sort of thing that isn't immediately exploitable but could be chained with other exploits to shim in unexpected data in places it's not meant for.

Here's setting up a key for basic usage:

>>> import pycoin
>>> pycoin.version
'0.90a'
>>> from pycoin.symbols.btc import network as btc
>>> key = "xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U"
>>> key = btc.ui.parse(key)
>>> print(f"key = {key}")
key = private_for <xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB>
>>> h = b"aofdjsoifjsdioufjdsoifjdsoifjdij"
>>> h
b'aofdjsoifjsdioufjdsoifjdsoifjdij'
>>> len(h)
32
>>> s = key.sign(b"aofdjsoifjsdioufjdsoifjdsoifjdij")
>>> s
b'0E\x02!\x00\x87\x10\x1c\x8d\x8b\xba\xa8o\x03\x8c\x8a|j\x93\xcc,\xd9\x9f\xf7\xa6\xe5;\x02\xa6\xfd\x8e\x16\xc86m\x13\xf7\x02 7\xe2H\xbd\xf3\xd3\x8d\xb8\x9f\x97;\xf4\xbcjTE0bQ\xde=\xdd\xc3\xe9F\x1cXq\x93\xb4.|'
>>>
>>> key.verify(h, s)    # good
True

But this is weird:

>>> key.verify(h, s+s) # BUG
True
>>> key.verify(h, s*23) # 22 TIMES THE BUG
True
>>> key.verify(h, s+b"sdfds") # :/
True

Trying to extend the message hash instead of the signature fails (as expected) but it doesn't fail in the way I expect:

>>> key.verify(h+b"1"*100, s)
False
>>> key.verify(h+b"1"*1000, s)
False

because doing the same extension at signing time gives

>>> key.sign(h+b"1"*100)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "./pycoin/pycoin/key/Key.py", line 214, in sign
    r, s = self._generator.sign(self.secret_exponent(), val)
  File "./pycoin/pycoin/ecdsa/Generator.py", line 152, in sign
    return self.sign_with_recid(secret_exponent, val, gen_k)[0:2]
  File "./pycoin/pycoin/ecdsa/Generator.py", line 134, in sign_with_recid
    k = gen_k(n, secret_exponent, val)
  File "./pycoin/pycoin/ecdsa/rfc6979.py", line 66, in deterministic_generate_k
    h1 = intstream.to_bytes(val, length=order_size)
  File "./pycoin/pycoin/ecdsa/intstream.py", line 7, in _to_bytes
    return v.to_bytes(length, byteorder=byteorder)
OverflowError: int too big to convert

Requests

Strongly-type the inputs to sign() and verify(). They should be fixed length bytestrings.

Make the exception sign() and verify() give on extending h consistent.

Do something sensible in the case of underflow. Is key.sign(b"") legal or illegal? What about key.sign(b"abcde")?

richardkiss / pycoin

Length-extension glitch #317

Requests