From laolu32 at gmail.com Wed Jul 27 18:13:55 2016 From: laolu32 at gmail.com (Olaoluwa Osuntokun) Date: Wed, 27 Jul 2016 18:13:55 +0000 Subject: [Lightning-dev] [BOLT Draft] Onion Routing Spec In-Reply-To: References: Message-ID: Hi Christian, welcome to the mailing list! Excellent work! I've been meaning to re-visit my implementation since I finished it last October but have been busy tending to other lnd related items. Thanks for the cleanups and optimizations you've added to my initial Sphinx implementation. Once we've finished fleshing out the initial specification, I'd be happy to get those changes merged! I've taken a look at the diff against the existing implementation, plus the current spec draft. I'd say the current spec draft is the *clearest* description of Sphinx I've encountered, especially the padding bits. IMO, the notation within the paper describing how to construct+process the mix-header is rather opaque. I see you've modified the encryption scheme of the end-to-end payload, switching from the arbitrary block-size block cipher (LIONESS) to purely a stream cipher (ChaCha20). Initially I was under the impression that this might compromise one of the security arguments of the scheme, but on closer inspection this is perfectly fine if one extends the header MAC to the entire payload as you've done. If one was staying true to the original construction, then this would eliminate the possibility of Single-Use Reply Blocks (SURB's) since the sender would be unable to construct the reply mix-header as she would be unaware of they responder's message. It's clear to me now that a MAC covering the end-to-end payload was omitted in the original version since the proof of computational indistinguishability of replies vs responses depends on the structure+processing being identical for both messages types. However I don't see us having any use for SURB's so this is an excellent change. Additionally, modifications to the end-to-end payload will instantly cause packet corruption, stopping invalid packets from propagating through the network. I really like the addition of the per-hop payload! It's a change to the original construction that I've seriously considered proposing. Such a payload should prove to be very useful in the future for information such as: limits on the per-hop absolute timeout, fee information, etc. The addition of a version byte is also very welcome. This'll streamline future modifications we may make to the mix-header format in the future, such as increasing the size of the per-hop payload, or switching to an alternative format to encoding the "next hop" address. The current draft doesn't specify the processor's action in the scenario that they're unable to locate the next hop node within their local routing table. Just to be explicit, I think a final paragraph should be inserted under the "Packet Forwarding" section detailing the abort procedure. > However, they could easily be made variable should we decide that sending > mostly empty messages is wasteful. I strongly think we should maintain the size uniformity of the packet throughout processing, changes in payload size between hop can give away information w.r.t a node's position within the route. We might want to consider dropping the end-to-end payload altogether though. I can't really think of a clear use case for the e2e payload within our specific application. That would save us 1k bytes, reducing the size of the full mix-header to 1234 bytes. Accounting for the additional fields within an HTLC "add" message, plus some additional overhead, this should keep us below typical MTU sizes, avoiding fragmentation of HTLC "add" messages. > This specification is limited to version 0 packets and the structure of > future version may change. The receiving node then splits the packet into its > fields. Packets with a non-zero version byte should be immediately rejected, as well as packets which aren't *exactly* 2258 bytes (or 1234 bytes if we drop the e2e payload). > The resulting HMAC is compared with the HMAC from the packet. Should the > computed HMAC and the HMAC from the packet differ then the node MUST abort > processing and report a route failure. Perhaps we should explicitly specify that the HMAC equality check MUST be performed without leaking timing information (constant time comparison)? I can't think of a precise potential vulnerability otherwise since the scheme uses an encrypt-then-MAC construction with a semantically secure encryption scheme. I don't see any clear downsides in specifying that the comparison be made in constant. > The sender computes a route {n_1, ..., n_{r-1}, n_r}, where n_1 is a peer of > the sender and n_r is the recipient. In order to eliminate ambiguity, I think this should be more explicit, specifying that "n_1" is a *direct neighbor* of the sender > A special HMAC value of 20 0x00 bytes indicates that the currently > processing hop is the intended recipient and that the packet should not be > forwarded. At this point the end-to-end payload is fully decrypted and the > route has terminated. It seems that with the current construction, then the "next hop" address will also be zero bytes if a packet processor is the last hop in the route. Alternatively, if the sender is aware that the receiver is actually a "virtual channel", then an additional address could be used instead of the zero-address to facilitate de-multiplexing at the last hop to the destination virtual channel. > In the pocessing phase the secret is the node's private key... Typo here, it should read "In the processing phase..." I think two key onion-routing related aspects are under specified within the current draft: replay protection, and key rotation. Although we might want to place details concerning key rotation in a separate document covering the initial routing protocol as the two are closely related. First, lets talk replay protection. The current draft specifies that: > The node MUST keep a log of previously used shared secrets. Should the shared > secret already be in the log it MUST abort processing the packet and report a > route failure, since this is likely a replay attack, otherwise the shared > secret is added to the log This is definitely necessary, however as dictated this would require nodes to allocate a potentially *unbounded* amount of storage to the shared secret "seen" log. I think we can allow nodes to periodically truncate this log by adding an additional session time stamp to the mix-header, either placed directly after the version byte, or within the per-hop payload. With this absolute timestamp, each entry within the "seen" log becomes a two-tuple: the shared secret itself, and the corresponding timestamp specified within the mix-header. Before the absolute timestamp has passed, the entry within the log remains, and mix-headers received with duplicated shared secret are rejected. If we enforce an upper bound on the "session lifetime", then nodes can periodically prune this log, discarding obsolete shared secrets. Once an entry has been pruned, although a node may not know if a shared secret is being duplicated, they can reject expired sessions according to the timestamp achieving a similar affect. Reasonable session times may be something around 30-minutes to an hour or two. With this scheme, I think that we can achieve near perfect replay protection without unbounded storage. On to the second aspect: key rotation. Ignoring the possible time-stamped log solution, the (possibly) only other way to allow nodes to prune their shared secret log is to periodically rotate keys. Once a node rotates a key, it can safely delete its *entire* previous shared secret log, as replay attacks will fail on the HMAC check. Independent of replay attack prevention, key rotation is useful in order to provide a degree of forward secrecy. Without key rotation, when a node is compromised by the adversary (assuming the node keeps *all* prior mix-headers), the adversary learns of the next-node within the route, and also the per-hop payload for the compromised node. With key rotation, assuming the prior keys are deleted, then the adversary is only able to decrypt partially ciphertexts from the current epoch. So then a question arises: how do we perform key rotation within the network globally with loose synchronization? I say loose synchronization since if rotations aren't synchronized to a degree, then the payments of source nodes may fail as an intermediate hop is unable to process the packet since it used an obsolete onion key. Therefore published onion keys should come in pairs (with overlapping lifetimes), and also be authenticated by a node's identity key. A key rotation scheme might look something like the following: * A node publishes two keys, along with a block hash of a block beyond a "safe" re-org distance, and a signature (under the identity pubkey) covering the advertisement. * The first key is intended for use until N blocks after the specified block hash, with nodes switching to the second key afterwards. * At the N/2 point, the original node publishes a new advertisement with the second key from the original advertisement listed as the "first" key, and a new fresh quasi-ephemeral onion key. The original node performs this rotation at intervals at the mid-point of expiration of the oldest key. * Nodes who receive this new advertisement (aware of the previous) record this as the node's next rotation key. Nodes who receive this advertisement, unaware of the previous treat this as the node's initial pair of quasi-ephemeral onion keys. With this scheme, rotations are synchronized very loosely, perhaps in the timespan of half-days, days, etc. There is a new cost however, when processing packets, a node must attempt to derive the shared secret with both active onion keys. Alternatively, instead of block hashes, we can use some other time based beacon as a switch over point in order to accommodate peers on multiple blockchains. I'll take a few more passes through the current draft spec, as well are your commits in your fork of my original implementation, following up with any other questions/comments. -- Laolu On Mon, Jul 25, 2016 at 9:23 AM Christian Decker wrote: > Hi all, > > I took the liberty of taking apart Olaoluwa's Sphinx implementation and I > came up with a spec draft that I'd like to propose [1]. It should roughly > be Sphinx, pinning down the various key-generation and stream generation > algorithms, and adding a per-hop payload. > > The per-hop payload is used to give instructions to individual hops, i.e., > how many coins to forward to the next hop. This means that the end-to-end > payload, i.e., the message in the Sphinx protocol, is currently unused and > could be omitted. > > The payloads are currently fixed size (20 bytes per-hop and 1024 bytes for > end-to-end payload) to avoid making messages collatable by their size. > However, they could easily be made variable should we decide that sending > mostly empty messages is wasteful. > > The spec is implemented in Go [2] and in C [3]. The Go version is an > adaptation of Olaoluwa's implementation, with some minor speedups, removing > some duplicate information, stripping the header, and switching to ChaCha20 > for stream generation and encryption. I also added a small commandline tool > that allows you to write packets to stdout so that we can feed an onion > generated by the C version to the Go implementation and vice-versa :-) > > Feedback is very welcome. If people like the draft I'll create > pull-requests for the spec and the implementations, but I'd like to keep > the discussion on the mailing list :-) > > Cheers, > Christian > > [1] > https://github.com/cdecker/lightning-rfc/blob/master/bolts/onion-protocol.md > [2] https://github.com/cdecker/lightning-onion/tree/chacha20 > [3] https://github.com/cdecker/lightning/tree/chacha20 > _______________________________________________ > Lightning-dev mailing list > Lightning-dev at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > -------------- next part -------------- An HTML attachment was scrubbed... URL: