From aj at erisian.com.au  Tue Sep 22 01:22:57 2015
From: aj at erisian.com.au (Anthony Towns)
Date: Tue, 22 Sep 2015 11:22:57 +1000
Subject: [Lightning-dev] Onion routing design.
In-Reply-To: <87r3lshkcp.fsf@rustcorp.com.au>
References: <8737ybi9fj.fsf@rustcorp.com.au>
	<AC2281B8-9EA0-42F2-8A3D-3FDF257300C0@erisian.com.au>
	<87r3lshkcp.fsf@rustcorp.com.au>
Message-ID: <20150922012257.GA22782@navy>

On Mon, Sep 21, 2015 at 06:35:58AM +0930, Rusty Russell wrote:
> Anthony Towns <aj at erisian.com.au> writes:
> > On 19 September 2015 9:39:44 am AEST, Rusty Russell <rusty at rustcorp.com.au> wrote:
> >>        // Sum of this whole thing after decryption.
> >>        required sha256_hash sum = 1;

> > Just adding random bytes on to the end should
> > work I think - they'll just be treated as extra padding and ignored.
> My original plan.  But it enables a probing attack where you corrupt the
> packet and if it succeeds anyway you know those bytes weren't used.

Actually, any random bytes on the end would be included (after decryption)
when calculating the sha256_hash sum by the next node, no? Otherwise
you'd at least need a length field to tell how much of the packet needs
verifying.

Hmm, I'm not sure it's possible to have the hash actually work at the
same time as letting nodes add padding?

You could have the hash only verify the current message and the following
(encrypted) message. None of the hashes would ever then verify the added
padding; but you'd still be vulnerable to probing attacks.

Probing attacks only reveal the length of the chain, of course. AFAICS
tor is vulnerable to this sort of probing attack? Weird.

> Hmm, what if we include a pubkey, and you use that to encrypt 0 padding?
> The last hop gets the privkey (and boundary information), and she can
> verify the padding.

Actually, this is missing a step isn't it? Don't we have to generate
symmetric keys for each step in an onion route, transmitting to Bob:

  E_B( KB ) E_KB( forward $20 to Carol; E_C( KC ) E_KC( ... ) )

In which case, I think Bob can append E_KB(00000..) as padding, which
we can predict, and eg, the final message to Dave will look like:

  E_D( KD ) E_KD( H; here's $15 )
    E_KD( grbg grbg ... grbg )
    D_KC( D_KB( E_KA( 0000 ) ) )
    D_KC( E_KB( 0000 ) )
    E_KC( 0000 )

If you use OFB or CTR mode for the symmetric cypher, you can calculate
D_KD() of all the padding and use that to work out the hash H of the
plaintex message:

  here's $15
  grbg grbg ... grbg
  D_KD(
        D_KC( D_KB( E_KA( 0000 ) ) )
        ...
      )

I don't think you can use CBC mode, because you'd need to know E_KD(grbg)
in order to know D_KD( padding ), but you need to know grbg in order
to know H, and you need to know E_KD(H + ...) in order to work out
E_KD(grbg).

You can't use sum for Kx because you need to know Kx before working out
the sum...

I think that means that:

>>> The format of a route looks like so:
>>>        required bytes route;

should actually be something like:

       required bytes hop_key; // encrypted with public key
       required bytes route;   // encrypted with hop_key

(possibly with an IV as well, if the block cypher mode doesn't just
include that in the cyphertext)

> But I've not had coffee yet, plus jetlag.  Could be missing a flaw or
> simplification!

It's crypto protocols; it's almost always safe to assume you're missing
a flaw...

Cheers,
aj