[noise] Invalid point attacks

[Trevor Perrin]

On Thu, Mar 30, 2017 at 6:06 AM, Jason A. Donenfeld <Jason at zx2c4.com> wrote:
>
> I suggest that the Noise spec explicitly mandate erroring out early in
> the case that DH() returns the null string.
>
> Noise already had an abort path when an AEAD calculation fails, which
> means adding in more abort points doesn't introduce a fundamentally
> new oracle. Rather, explicitly aborting on null DH() output strictly
> adds desirable security properties.

Let's work through these.

The IETF has decided to promote the idea of post-DH zero checks for
the 25519 and 448 curves.  I think that was a mistake, since this was
not part of 25519 as DJB defined it, it adds complexity (const-time
code, error-handling, and implementation variance), and is not needed
in good protocols.

It also creates a dangerous situation where protocols requiring this
check are going to get used with widespread existing code that doesn't
do it!

But it also means we'll have to fend off these arguments, in future.

> 1. It prevents accidents in which a peer might shoot himself in the
> foot with a bad RNG for ephemerals and/or bad static key.

It doesn't prevent that.  A low-entropy private key multiplied by the
base point is still a valid public key.


> 2. In NoiseIK, there is an invalid point attack from the initiator to
> the responder, wherein the initiator sends a bad ephemeral for message
> 1. The responder then encrypts his payload in message 2 with {DH(Sr,
> Si), DH(Sr, Ei) = NULL, DH(Er, Ei) = NULL, DH(Er, Si)} = {DH(Sr, Si),
> DH(Er, Si)}, which may not be desirable.
> 3. In NoiseIK, there is an invalid point attack from the initiator to
> the responder, wherein the initiator sends a bad ephemeral and also
> announces his static key out of band to be an invalid point, for
> message 1. The responder then encrypts his payload in message 2 with
> {DH(Sr, Si) = NULL, DH(Sr, Ei) = NULL, DH(Er, Ei) = NULL, DH(Er, Si) =
> NULL} = NULL. While you might claim the attacker has brought this upon
> himself and so we shouldn't be sympathetic, one could imagine complex
> interactions or sophisticated adversaries who are in a position to
> weaken utilized keys like this, with the goal of having weaker crypto
> later on that is passively recorded.

You don't spell out why you think either of these are attacks.

These cases are no different than the initiator choosing a "bad
ephemeral" and/or "bad static" whose private key is known to the
attacker (or known publicly), right?

It's impossible to prevent someone from choosing bad keys and
weakening their own security.


> 4. Allowing for DH to "maybe return null" significantly complicates
> the security analysis and formal verification.

Typically formal models idealize DH as working in a prime-order group.
Doing zero checks rules out small-order inputs, but does *not*
guarantee working in a prime-order group, which would require a more
expensive scalar multiplication to validate the input point.

So unless we do a full point validation (scalar multiplication) we're
not going to match a simplified idealization of DH.


Anyways, existing Noise code doesn't perform these checks.  This
simplifies implementation, and also enables null public keys to be
used to skip authentication, which is a nice feature, since a pattern
like XX can be used with/without authentication from either party.

I don't think any of the reasons you mention are compelling, but maybe
you (or Kevin) could add more detail if you feel strongly about some
of them?

Trevor