[noise] secp256k1 (was Re: Notes and thoughts from RWC2017)

[Trevor Perrin]

On Tue, Jan 17, 2017 at 2:38 PM, Olaoluwa Osuntokun <laolu32 at gmail.com> wrote:
> Hi Y'all,
>
> I've read bits of the archive of this mailing list, but never subscribed
> until now when it was brought to to my attention that y'all were discussing
> the new Noise variant we're using for Lightning. My name is Laolu Osuntokun,
> I'm one of the co-authors of the Lightning Network specifications and the
> lead developer for lnd[1].

Hi Olaoluwa,

Thanks for joining in!

The Lightning work points out some areas for improvement in the Noise
spec, it'll be great to get your perspective as we work this out.


> Our choice of secp256k1 and SHA-256 are to better align ourselves with the
> existing cryptographic software implementations in the Bitcoin space. There
> exist some libraries highly optimized for the choice of curve parameters
> such as libsecp256k1[2] (which is very widely used within the ecosystem)
> that we're able to take advantage of by sticking with "bitcoin crypto".

Makes sense, I'm glad to see Noise's flexibility is useful here.  I
didn't see any security problems with how secp256k1 is used.


> Jason wrote:
>> so we decided that it was up to the implementer as to what to do
>> in this case -- keep processing, so that the whole noise handshake
>> message would receive constant time treatment, or abort early, so as
>> to not waste cycles
>
> Implicitly, we've gone with the "abort early" route. It isn't precisely
> spelled out in the Lightning specification atm, but I'll remedy that with an
> amendment.  My implementation (brontide) along with the other
> implementations [3][4] will _reject_ a point not on the secp256k1 curve
> during deserialization.

Ah, there's Scala and C code in-progress, nice!


> As implemented now, the invalid point will
> essentially be rejected by the DH functions. Therefore, the spec currently
> doesn't outline the usage of null points.
[...]
>
> I don't think we require the specification of a null value since we use
> point-compression everywhere (thereby rejecting invalid points). However,
> there may be some other benefits of doing so that I haven't thought of yet.


That makes sense.  Stepping back, I think there's 2 design questions for Noise:
 (1) Handling invalid public keys
 (2) Allowing "null public keys" to skip an authentication/DH step

Noise was designed around an X25519-style DH function that is
"nonstrict" (doesn't return errors), and has a natural "null" value
(zeros input -> zeros output).

But many DH/ECDH functions are a "strict" style where the public value
is validated, and off-curve or small-subgroup values (like a "null"
value) are rejected.  This includes both older curves like
P-256/P-384, and newer ones like FourQ and Mike Hamburg's Decaf
encoding.

So for invalid public keys we have a few options:
 * Allow strict or nonstrict behavior as implementation decision
 * Force all DH functions to be strict (reject off-curve and/or small subgroups)
 * Force all DH functions to be nonstrict (turn errors into zero outputs)
 * Allow strict or nonstrict handling that is fixed for the DH
function (ie "25519" is always nonstrict, "secp256k1" is strict)

The last seems best to me (and I think Laolu), since it allows the
natural style for each DH function, and doesn't require extra work to
map errors to values or vice versa.  Also, it leaves the possibility
of defining "25519strict" etc if a need arises to be consistent.


Null public keys are useful for a couple reasons:
 * To signal that a party is not authenticating itself.  For example,
in the XK handshake, the client can send a null public key to say that
it is skipping client authentication, and effectively turn the
handshake into NK, but without needing conditional logic, parsing, or
transmitting extra bytes
 * To skip the DH computation when a party is skipping authentication.

A nonstrict DH function probably has an implicit null value, which is
convenient.

We could ask DH functions without an implicit null to specify an
explicit null input/output (e.g. zeros -> zeros).  Then we could leave
it to the implementer of such a DH function whether to support the
explicit null (if you never expect to use it then support isn't
mandatory).

We've tried to avoid implementation-variance within a single Noise
protocol.  However I'm doubtful we could force all users of strict DH
to implement explicit nulls in cases where they don't need them, so
maybe we have to tolerate it here?


Trevor