Olaoluwa Osuntokun [ARCHIVE] on Nostr: 📅 Original date posted:2016-08-04 📝 Original message: > I'm going back and ...

📅 Original date posted:2016-08-04
📝 Original message:
> I'm going back and forth about including the payloads in the header HMAC.
I
> think we have three options here:
>
> 1) Include the payload in the header HMAC computation

I'd say personally, I prefer the first option. This results in "fail fast"
behavior w.r.t packet forwarding, and additionally adds the smallest
overhead.

> we also lose the ability to do anonymous rendezvous meetings, where the
final
> recipient provides half of the route in the form of a precompiled header
> (something that Hornet is using).

It doesn't appear that we loose the ability to do rendezvous routing if we
follow through with the first option. The final recipient can still provide
a
precompiled header which is the e2e payload sent from the source to the
rendezvous node. As the source knows the exact nested mix-header when
sending,
it can still be protected under the mix-header wide MAC.

Additionally, in order to hide the next-hop after the rendezvous node from
the
source node, the destination can wrap the nested header in a layer of
encryption, decryptable only by the rendezvous node.

> Both the per-hop checkable schemes, combined with nodes signing the
packets
> they forward, would give us the ability to identify misbehaving nodes and
> denounce them: if we receive a packet we check the integrity and if it
doesn't
> match then we can prove to others that the node forwarded something broken
> with its signature, or it did not check the packet itself.

Great observation. However, it seems like this is currently out of scope
(the
implications of "denouncing" a node") and should be re-visited at a future
time
when we brainstorm some sort of "reputation" scheme.

> There is a tradeoff between small packets and keeping the size uniform. I
think
> we could bucketize sizes, e.g., have multiples of 32 bytes or 64 bytes
for the
> fields, to have packets with similar sized payloads have the same packet
size.
> That would allow us to also drop the e2e payload by setting a size of 0,
and
> still be able to forward it, should we ever find a use for it.

Good point, we may have uses for non-uniform sizes as far as mix-headers in
the
future. So with this, then it appears there may be 3 types of mix-header
formats:
1. Regular. Meaning no e2e payload, weighing in at 1234 bytes.
2. Extended. Meaning bearing the e2e payload with a size of 2468 bytes.
3. Rendezvous. Which nests another mix-header within the end-to-end
payload,
with a size which is double that of the regular.

If we like this taxonomy, then we may want to reserve the first 2 version
bytes
within the draft. A version 0 packet would encompass processing the first
two
types, while a version 1 packet denotes that this is a rendezvous packet.
The
rendezvous case needs to be distinct as it modifies the
processing/forwarding
at the final hop.

Alternatively, we can use solely a version of 0 in the initial spec, with
the
final hop checking if the [1:34] bytes of the payload (if one is present)
are a
point on the curve. If so, this triggers the rendezvous forwarding, with
the
mid-point node processing the packet again as normal, completing the
rendezvous
route.

> We have to be careful when using timestamps in the packet as it makes
individual hops collatable.

Excellent observation. Assuming we roll out a reasonably efficient solution
for
the collatable HTLC R-values across hops, naively selecting timestamps would
present another correlation vector.

> So my proposal would be to include a timestamp rounded up to the closest
hour
> and have a sliding window of accepted timestamps of +/- 1 hour,
remembering the
> secrets for that period and rejecting anything that is too far in the
future or
> too far in the past.

This seems reasonable, also the size of the sliding window can easily be
tuned
in the future should we find it too large or small.

> The more coarse the bigger the less likely an attacker is to guess which
> packets belong to the same route, but the more storage is required on the
> node's side.

Yep, there's a clear trade off between the window size of the accepted
timestamps, and a node's storage overhead. We can tune this value to a
ballpark
estimate of the number of HTLCs/sec a large node with high frequency
bi-directional throughput may forward at peak times.

Let's say a HFB (High-Frequency Bitcoin) node on the network at peak
forwards
5k HTLC's per second: (5000/sec * 32 bytes) * 3600 sec = 576MB, if nodes are
required to wait 1 hour between log prunings, and 288MB if we use a
30-minute
interval. Even with such a high throughput value, that seems reasonable.

> We could just use the announced key, i.e., the one that participated in
the
> channel setup, as a root key for HD key derivation. The derivation path
could
> then be based on floor(blockheight / 144) so that we rotate keys every
day, and
> don't need any additional communication to announce new public keys.

Great suggestion! However, I think instead of directly using the key which
participated in the channel setup, we'd use a new independent key as the
root
for this HD onion derivation. This new independent key would then be
authenticated via a signature of a schnorr multi-sign of the channel
multi-sig
key and the node's identity key (or alternatively two sigs). This safeguards
against the compromise of one of the derived private keys leading to
compromise
of the master root HD priv key which would allow possibly stealing a node's
coins. Additionally, a node can switch keys more easily, avoiding a channel
tear down.

However, the HD Onion Key approach can potentially cancel out the forward
secrecy benefits. If an attacker gains access to the root HD pubkey, along
with
any of the child derived onion keys, then they can compute the root privkey.
This allows the attacker to derive all the child priv keys, giving them the
ability to decrypt all mix-headers encrypted since the HD Onion Key was
published.

I think we can patch this exploit by adding some precomputation for each
node,
and introducing an intermediate onion derivation point. Assuming we rotate
every 144+ (1 day) blocks, then using the HD Onion PrivKey, each node
pre-generates 365 (or a smaller batch size) keys. Then, generates an
independent "onion derivation" key. The OD key then combined with each of
the
child onion keys, produces the final child onion key (C_i = final onion key,
B_i = intermediate child key, A = OD):
* C_i = B_i + A

After the precomputation, the OD key (A) should be *destroyed*. If so, even
if
an attacker gains access to one of the intermediate child onion keys,
they're
unable to derive the final child onion key as the OD key has been destroyed.
This safeguards the forward secrecy of the scheme in the face of the HD
root+child exploit. As before, in the case of a root/child compromise the
original node can simply authenticate a new HD Onion Key.

So perhaps we can combine the two approaches, publishing a blockhash (buried
under a "safe" re-org depth), along with an authenticated HD root pubkey.
With
this new scheme we're able to push key rotation out to the edges in a
non-interactive manner. Having the blockhash as an anchor will reduce the
amount of guessing required by a node to fetch the correct onion key.

> I'm also trying to figure out how to enable intermediate nodes to reply
to a
> packet, e.g., if capacities are insufficient or the next node is
unreachable,
> by recycling the routing info.

Yeah I've also attempted to tackle this issue a bit myself. The inclusion of
onion routing certainly makes certain classes of failures harder to
reconcile.
There has been a bit of discussion of this in the past, at the time called
"unrolling the onion". In a similar vein it's also more difficult to
ascribe blame node's which directly cause a payment to fail.

One of my naive ideas was to include a "backwards" mix-header within each
node's per-hop payload (though I hadn't included the per-hop payload in my
mental model at the time), however this would result in a quadratic blow up
space complexity parametrized by our max-hop limit. Essentially, we'd
include
a SURB within the mix-header for each hop in the route.

> Maybe we could continue blinding the ephemeral key on the return path, and
> have a mechanism to tell the node the total blinding factor along the
path so
> that it can encrypt something in the routing info for the return path?
That
> would neatly combine Hornet and Sphinx, eliminating the initial roundtrip
to
> setup forwarding segments.

Could you elaborate on this a bit more? It seems that this alone is
insufficient to allow "backwards" replies to the source w/o revealing the
source's identity.

It seems the primary question is: how can we re-use the information present
at
a hop, post-processing to reply to the sender without an additional round
trip?
If we can solve this, then we can greatly increase the robustness of onion
routing within the network. I think they may be worth spinning some cycles
on,
although I don't consider it blocking w.r.t the initial specification.

-- Laolu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20160804/30f33520/attachment.html>;