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

[Karthikeyan Bhargavan]

Dear Trevor, All,

Nadim and I have been looking at some Noise patterns that are not in the specification and analyzing them with Noise Explorer.
Unless we misunderstand something, we may have found a forgery attack on one of these patterns.
Essentially, we can compose well-known attack vectors (invalid DH keys, repeated AEAD nonces) to attack patterns 
that rely only on static-static DH (“ss”) for authentication.

====

Consider the pattern KXS below:

KXS(s,rs):
      -> s
      ...
      -> e
      <- e, ee, s, ss

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).

However, there is an attack if the responder does not validate ephemeral public values.
Suppose a malicious initiator were to send an invalid ephemeral public key “e”, say e = 0 (zero)
Then, the responder would compute “ee” as 0 and the resulting key would depend only on the static key “ss”.
(Note that the responder could detect and reject the invalid public key but the noise spec explicitly discourages this behavior.)

Why is this bad? Since the responder will encrypt messages with a key determined only by “ss" (with nonce set to 0), 
the malicious initiator can cause it to encrypt two messages with the same key and nonce, which allows for forgery attacks.

A concrete man-in-the-middle attack on this pattern is as follows:
(For simplicity, we use Hash to represent the more complex key derivation and mixing functions for Noise, but we hope the ideas are clear)

=====
Pre-Messages
=====

0. Before the session begins, A sends s = sA to B

====
Session 1
====

1. Malicious M initiates a session with B (pretending to be A).
    It sends e = Z (zero) such that Z^x would evaluate to Z for any x.

2. B receives e = Z and accepts a new session with:
  	hB_0 = Hash(pattern_name)
  	ckB_1 = hB0
  	hB_1 = Hash(hB0, sA, e=Z)

3. B generates re1, computes ee = Z, and sends back (re1,ee=Z,sB,ssAB,msg1)
    where sB is encrypted with 
         key = ckB_2 = Hash(ckB_1, ee = Z)
         nonce = 0
         additional_data = hB_2 = Hash(hB_1, re1, ee=Z)
    and msg1 is encrypted with
         key = ckB_3 = Hash(ckB_2, ssAB)
         nonce = 0
         using additional_data = hB_3 = Hash(hB_2, sB)

4. M discards this session but remembers the encrypted message 

====
Session 2
====

5. A initiates a new session with B by sending e:
    So at A:
	hA_0 = Hash(pattern_name)
 	ckA_1 = hA0
 	hA_1 = Hash(hA0, sA, e)

6. M intercepts this message and replaces it with the invalid public key Z (zero).

7. B receives e = Z and accepts a new session with:
	  hB_0 = Hash(pattern_name)
	  ckB_1 = hB0
	  hB_1 = Hash(hB0, sA, e=Z)

8. B generates re2, computes ee = Z, and sends back (re2,ee=Z,sB,ssAB,msg2)
    where sB is encrypted with 
         key = ckB_2 = Hash(ckB_1, ee = Z)
         nonce = 0
         additional_data = hB_2 = Hash(hB_1, re)
    and msg2 is encrypted with
         key = ckB_3 = Hash(ckB_2, ssAB)
         nonce = 0
         using additional_data = hB_3 = Hash(hB_2, sB)

9. M intercepts this response. 
    Notably, the encryption keys (ckB_3) and the nonces (0) used for msg1 in session 1 and msg2 in session 2 are the same.
    Hence, if the underlying AEAD scheme is vulnerable to the repeated nonces attack, M can compute the AEAD 
    authentication key for ckB_3 and tamper with msg1 and msg2 to produce a new message msg3 that is validly encrypted under this key.
    Importantly, M can also tamper with the additional data hB_3 to make it match any other hash value.

    M replaces the message with (re=Z, ee=Z, sB, ssAB, msg3) and sends it to A.
    where sB is re-encrypted by M using ckB_2 which it knows
    and msg3 is forged by M using the AEAD authentication key for ckB_3 

10. A receives this message (re=Z,ee=Z,sB,ssAB,msg3) and computes:
         ckA_2 = Hash(ckA_1, ee = Z)
	 hA_2 = Hash(hA_1, re = Z)
      and decrypts sB with ckA_2, nonce = 0, AD = hA_2
      It then computes
        ckA_3 = Hash(ckA_2, ssAB)
     	hA_3 = Hash(hA_2, sAB)
      and decrypts msg3 with ckA_3, nonce = 0, AD= hA_3
      This decryption succeeds since ckA_3 = ckB_3 and the attacker has forged the AD and the msg.

======

Result: A accepts the forged message msg3 as coming from B, even though the pattern had the maximum authenticity level 2.

======

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 

Feedback welcome,
Karthik and Nadim
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20180621/b66f71be/attachment.html>