bug in Sphinx padding allows for last hop to learn the route length

[david415]

I do not know if your use of the Sphinx packet format is such that variable length routes are used... however you should know that your Sphinx packet implementation does leak the route length to the last hop.

According to the recently submitted paper: Breaking and (Partially) Fixing Provably Secure Onion Routing, ( https://arxiv.org/abs/1910.13772 ) there is a padding bug where a sphinx implementation creates a header and in so doing uses zeros to pad the beta field whereas random data should be used instead because of the use of the stream cipher...

https://github.com/UCL-InfoSec/sphinx/blob/c05b7034eaffd8f98454e0619b0b1548a9fa0f42/SphinxClient.py#L67

# The os.urandom used to be a string of 0x00 bytes, but that's wrong
beta = dest + id + os.urandom(((2 * (p.r - nu) + 2)*p.k - len(dest)))
beta = p.xor(beta,
p.rho(p.hrho(asbtuples[nu-1]['s']))[:(2*(p.r-nu)+3)*p.k]) + phi

This bug, that is, if beta were padded with zeros instead of random bytes would allow an adversary to determine the length of the route. This adversary would have to be the last hop and it could then XOR the beta portion of the header with zero bytes to learn how many skipped hops the Sphinx packet had.

[david415]

here the zero bytes are created: https://github.com/lightningnetwork/lightning-onion/blob/master/sphinx.go#L204

this right shift fills the gap with zero as well: https://github.com/lightningnetwork/lightning-onion/blob/master/sphinx.go#L234

here some data is copied to our mixHeader slice... where the remainder of the slice length is only zero bytes: https://github.com/lightningnetwork/lightning-onion/blob/master/sphinx.go#L241

the entire mixHeader slice is then XOR'ed with a stream cipher: https://github.com/lightningnetwork/lightning-onion/blob/master/sphinx.go#L246

therefore the last hop may in fact XOR the beta portion of the header with zero bytes to learn the number of hops in the route used by the Sphinx packet.

[david415]

oops hi. i just now realized there's already a pull request to fix this: https://github.com/lightningnetwork/lightning-onion/pull/40

[Roasbeef]

Yep, thanks for making this issue in either case!

[david415]

Yep, I had to fix Yawning's Go Sphinx, my Rust Sphinx and one line in our Sphinx spec file :)