[noise] Potential forgery attack on "ee, ss" patterns

[Trevor Perrin]

On Thu, Jun 21, 2018 at 8:18 PM, Karthikeyan Bhargavan
<karthik.bhargavan at gmail.com> wrote:
>
> Consider the pattern KXS below:
>
> KXS(s,rs):
> -> s
>
>       ...
>       -> e
>       <- e, ee, s, ss


Hi Karthik, Nadim,

That pattern is invalid per bullet 3 of 7.1:

http://noiseprotocol.org/noise.html
"""
After performing a DH between a remote public key and any local
private key that is not the ephemeral private key, the local party
must not call ENCRYPT() unless it has also performed a DH between the
ephemeral private key and the remote public key.
"""

In this case, both parties are performing a DH between a remote s and
their local s, so they also have to perform an ephemeral-static DH
with the remote s before encrypting data.  To make that a valid
handshake you could add "es" and "se" tokens to the last message.

This would prevent the replay attack you describe, since "se" would be
a DH between honestly-chosen key pairs, thus would randomize the
encryption of the response.


> This is a variation of KX that uses ss instead of se, and es, so it is a
> little more efficient, but essentially satisfies the same confidentiality
> and authentication goals. In particular, the responder can start sending
> messages immediately after the second message (with a auth=2, conf=3
> guarantee).

I don't think it's accurate to say this KXS pattern "essentially
satisfies the same confidentiality and authentication goals" as KX,
even if the attack you describe was prevented some other way.

First, you're claiming (2,3) properties, but the "2" requires
authentication to be secure even if static keys are compromised (KCI
resistance), which the KXS pattern doesn't have.  For a similar
reason, KX achieves a "5" property instead of "3".

So this is another reason for the validity rule:  Noise forces people
to to use ephemeral-static DH for authentication, not static-static,
because ephemeral-static DH provides better security in case the
static keys are compromised.  The "ss" token is used in current
patterns when there's no other option for authentication (e.g. 0-RTT),
and could also be used for resistance to ephemeral-key compromise, but
we've otherwise taken an opinionated stance against relying on "ss".


> At a high-level, the above analysis  can be read in one of three ways:
> 1) We need to be careful about uses of “ss” in Noise patterns
> 2) We need to validate DH public values, including for Curve25519
> 3) We need to ensure that independent sessions cannot have the same AEAD
> keys
>
> Consequently, a simple countermeasure would be any of the following:
> 1) Forbid the use of “ss” unless accompanied by se or es
> 2) Require implementations to validate incoming DH public values
> 3) Mix ephemeral+static public DH values into the encryption key

The (1) bullets are the approach taken by Noise, in validity rule #3.

You mention a couple alternatives:  One was "validating" public keys.
It's not clear what you mean, validating EC public keys has
historically meant different things, some of them expensive, and this
ambiguity has caused problems [1].  In particular, Noise is most
commonly used with X25519 (previously Curve25519), for which
widespread software and specs exist that don't apply any of the checks
you might ask for, and which advertise the simplicity of this API as a
virtue.

So if we were to rely on some set of validation checks while allowing
patterns like KXS, people would likely use these patterns with
libraries for which it was unsafe (e.g. versions of NaCl, libsodium,
donna, etc).

Your (3) proposal was to randomize the calculation by using ephemeral
public keys as nonces.  We do this if PSKs are involved, since we want
PSK protocols to be secure even if all the DHs are bad.  But since
we've already decided to force people to do ephemeral-static DH, this
would just add unnecessary calculation to pure-DH protocols.

Trevor

[1] https://moderncrypto.org/mail-archive/curves/2017/000896.html