From aj at erisian.com.au  Sat Oct  3 16:38:56 2015
From: aj at erisian.com.au (Anthony Towns)
Date: Sun, 4 Oct 2015 02:38:56 +1000
Subject: [Lightning-dev] Onion routing strawman proposal
In-Reply-To: <877fn5om6g.fsf@rustcorp.com.au>
References: <877fn5om6g.fsf@rustcorp.com.au>
Message-ID: <20151003163855.GA22873@navy>

On Fri, Oct 02, 2015 at 03:18:39PM +0930, Rusty Russell wrote:
> So, I've pushed some test onion routing code in an acceptable
> format:
> https://github.com/ElementsProject/lightning/blob/onion/test/test_onion.c

>         struct hop {
>         	unsigned char msg[MESSAGE_SIZE];
>         	struct pubkey pubkey;
>         	struct sha256 hmac;
>         };
> That's a fixed 3840 bytes;

Is the idea to switch that to non-fixed size using protobufs, or?

> then prepends padding.

(prefixes...)

My understandng is it works as follows:

 * random EC key pairs are generated for each hop, known to the
   initiator
 * the public key for each hop is included in plaintext as hop.pubkey
 * ECDH is used to establish a shared secret with each hop
   (initiator uses routing node's pubkey (ie, their lightning node id)
    and the generated privkey; routing node uses their privkey and the
    hop.pubkey value)
 * symmetric AES & HMAC keys are derived based on the secret

When you receive a message (say you're hop 5) what you'll get is:

  P4 P3 P2 P1 H20 H19 ... H5

where P1 is padding added at node 1, and H19 is the hop structure
intended for node 19, etc; all of those in various stages of
encryption/decryption.

You then grab the pubkey from H5.pubkey; which is already plaintext,
and calculate your shared secret, and generate AES key, HMAC key, IV
and padding IV from those. That then lets you run a hmac of everything
you've received, excluding the final hmac (so, P4 ... P1 H20 .. H6 +
msg + pubkey), and compare that to the hmac.

You then decrypt everything (except maybe the hmac and pubkey, but
whatever) using AES in CTR mode with a nonce of IV, giving you:

  P4' P3' P2' P1' H20' H19' .. H4' [M5]

M5 lets you know what to do, and if you need to forward it, you generate
P5 by encrypting 0000's with AES in CTR mode with a nonce of PAD_IV. You
forward:

  P5 P4' P3' .. H4'

and you're done.

Question:

 - I think this means lightning nodes are identified by the
   full 512 bit (or 257 bit?) public key used for routing -- (ie,
   knowing the HASH160 of the pubkey isn't enough, unlike in normal
   bitcoin pay2pubkey transactions).

 - I think you can still use different keys for routing and
   anchors/commitments so far. (Using the anchor transaction to turn
   your routing id into a beacon would probably change that though)

Sigh. I've had a go at reimplementing it in python, but I'm stuck trying
to reproduce the secret info using pyelliptic (which in turn uses
openssl).

...

Ah, it looks like the problem is that libsec256k1 actually goes a step
further and runs SHA256(y||x), where "x" is the value I'm getting and y
is '\x02' is the y value is even and '\x03' if it's odd. If I try both,
one of them turns out right:

 Secret1: d9946724c6bd8d5b58bdd2256a0251816a42f9707c794427a410075e4dbb199c
 Secret2: 105e0c04f0a910d72dcf2683c21903ba08cd8b225e4124afc41bb2341dc40f49

Unfortunately openssl throws away y and just gives us x, so I'm not sure
if I can work out the right secret directly. I guess I can run the HMAC
twice and pick the value that worked?

Okay, we'll see if we can get any further tomorrow.

Cheers,
aj