[noise] Raw RNG over the Wire [was: Re: Rev30 branch]

[Jason A. Donenfeld]

Hey,

These are interesting points you make. In WireGuard, there's a session
index that ties several UDP messages together into one session. At the
beginning of a session, it's randomly generated from the equivalent of
/dev/urandom. It's 4 bytes, and is included in every message of the
session.

Perhaps this isn't such a good idea to transmit it raw? One potential
mitigation would be as follows:

1. At the beginning of the program's lifetime, generate a 16 byte
secret (using the same RNG).
2. Everytime a new session index is created (at the start of a
session), rather than simply use 4 bytes of /dev/urandom as the
session index, I pass 8 bytes of /dev/urandom to SipHash24, using the
secret generated in step (1).
3. 4 bytes of this siphash'd random data is then used as the session
index and sent over the wire.

RNG backdoor designers would then have to account for RNG outputs at
two separate points going through SipHash. I think this hurdle would
defeat the backdoor attempt.

But is this overkill? Is 4 bytes of raw RNG being transmitted even a problem?

What are your opinions on this approach?

Thanks,
Jason

PS: in case you're curious, code wise, that would look something like this:

diff --git a/src/hashtables.c b/src/hashtables.c
index 8911625..06754d2 100644
--- a/src/hashtables.c
+++ b/src/hashtables.c
@@ -60,6 +60,7 @@ static inline struct hlist_head *index_bucket(struct
index_hashtable *table, con

 void index_hashtable_init(struct index_hashtable *table)
 {
+ get_random_bytes(table->key, SIPHASH24_KEY_LEN);
  hash_init(table->hashtable);
  spin_lock_init(&table->lock);
 }
@@ -67,6 +68,7 @@ void index_hashtable_init(struct index_hashtable *table)
 __le32 index_hashtable_insert(struct index_hashtable *table, struct
index_hashtable_entry *entry)
 {
  struct index_hashtable_entry *existing_entry;
+ uint8_t raw_rng_bytes[sizeof(uint64_t)];

  spin_lock(&table->lock);
  hlist_del_init_rcu(&entry->index_hash);
@@ -76,7 +78,9 @@ __le32 index_hashtable_insert(struct index_hashtable
*table, struct index_hashta

 search_unused_slot:
  /* First we try to find an unused slot, randomly, while unlocked. */
- get_random_bytes(&entry->index, sizeof(entry->index));
+ get_random_bytes(raw_rng_bytes, sizeof(raw_rng_bytes));
+ /* We run the random bytes through siphash, to prevent against
potential RNG backdooring. */
+ entry->index = (__force __le32)siphash24(raw_rng_bytes,
sizeof(raw_rng_bytes), table->key);
  hlist_for_each_entry_rcu(existing_entry, index_bucket(table,
entry->index), index_hash) {
  if (existing_entry->index == entry->index)
  goto search_unused_slot; /* If it's already in use, we continue searching. */
diff --git a/src/hashtables.h b/src/hashtables.h
index 495a6f0..f5d856a 100644
--- a/src/hashtables.h
+++ b/src/hashtables.h
@@ -20,6 +20,7 @@ struct wireguard_peer
*pubkey_hashtable_lookup(struct pubkey_hashtable *table, c

 struct index_hashtable {
  DECLARE_HASHTABLE(hashtable, 10);
+ uint8_t key[SIPHASH24_KEY_LEN];
  spinlock_t lock;
 };
 struct index_hashtable_entry;




On Thu, Jun 30, 2016 at 8:44 PM, Trevor Perrin <trevp at trevp.net> wrote:
> On Wed, Jun 29, 2016 at 6:21 PM, Rhys Weatherley
> <rhys.weatherley at gmail.com> wrote:
>> On Thu, Jun 30, 2016 at 10:53 AM, Jason A. Donenfeld <Jason at zx2c4.com>
>> wrote:
>>>
>>> > * Explicit nonces make it easier to "backdoor" crypto implementations.
>>>
>>> That's an interesting point. Do you mean simply in the sense that a
>>> backdoored RNG would result in more catastrophic effects than
>>> otherwise? Or do you have something else in mind?
>>
>>
>> I interpret that as a reference to Dual_EC_DRBG and similar constructions
>> where the output of the RNG contains information that can be used to derive
>> the internal state.
>
> That's right, and a good summary.  And this isn't theoretical, RSA
> BSAFE and Juniper Netscreen (and who knows what else) were backdoored
> via RNG + explicit nonces, and NSA tried to lobby the IETF for larger
> TLS nonces, to make it easier to exfiltrate the Dual_EC state.
>
> OTOH, I don't want to exaggerate this.
>
> There's arguments in favor of explicit nonces (it enables ephemeral
> key reuse, which lets your amortize key-generation costs).  And if
> someone is in position to backdoor the RNG, avoiding explicit nonces
> won't necessarily stop them (they could always make the RNG
> low-entropy, though that's perhaps more detectable and doesn't achieve
> the Nobody-but-Us "NOBUS" property of a good backdoor).
>
> So I've edited the rationale to be more nuanced:
>
> Explicit random nonces (like TLS "Random" fields) are not used because:
>
>  * One-time ephemeral public keys make explicit nonces unnecessary.
>  * Explicit nonces allow reuse of ephemeral public keys. However
> reusing ephemerals (with periodic replacement) is more complicated,
> requires a secure time source, is less secure in case of ephemeral
> compromise, and only provides a small optimization, since key
> generation can be done for a fraction of the cost of a DH operation.
>  * Explicit nonces increase message size.
>  * Explicit nonces make it easier to "backdoor" crypto
> implementations, e.g. by modifying the RNG so that key recovery data
> is leaked through the nonce fields.
>
> https://github.com/noiseprotocol/noise_spec/blob/rev30/noise.md
>
>
> Trevor