Potential Oracle Access to he peer's randomness

[Florentin Rochet <[e-mail]>]

Dear QUIC designers,

I've been recently following the discussion on PATH_CHALLENGE/PATH_RESPONSE
attack scenarios, and for what it matters, I am also working on QUIC-like
capabilities above TCP. In my design, upon thinking on connection 
migration attack vectors,
I've been worried about another type of exploit. It is more critical in 
my opinion than
bandwidth amplification, and it also affects QUIC.

So, regarding QUIC, when a connection migration is initiated, from the 
current
specification[0], "An endpoint can migrate a connection to a new local 
address
by sending packets containing non-probing frames from that address." Sending
a non-probing packet would trigger a PATH_CHALLENGE message from the other
peer in an implementation following those specs to enter in path validation.

Essentially, it means that a client can, on-demand, trigger a PATH_CHALLENGE
from the server. In the specification[1], the PATH_CHALLENGE is 
containing an
unpredictable payload. More formally, it is meant to be 
indistinguishable from the output
of a random function. In practice, there are different ways to compute this
"unpredictable" payload, with critical differences.

The naive approach is to use unsecure randomness random(), and then 
putting it
in the PATH_CHALLENGE.

Another approach would be to use secure randomness to satisfy the current
specifications. That is, putting the output of SecureRandom() to the
PATH_CHALLENGE.

Ironically, the second approach is worrying me. That is, the current 
protocol
specifications may provide incentives to implement a protocol channel to 
allow
any client to query the server's PRNG output on-demand, and with probably a
consequent amount of randomness bandwidth.

We know from history that this is not a great idea, especially is the 
presence
of potential weaknesses within the PRNG (intentional or not). The most 
appealing
example is the backdoored Dual EC PRNG, for which the "backdoor holder" 
would
only need to bruteforce 16 bits to recover the internal state and 
predict any
new outcome. This is possible as soon as enough of the Duac EC output is
observed. In the case of Dual EC, and assuming that the PATH_CHALLENGE 
contains
16 bytes of randomness, the attacker would only need to trigger 3 
PATH_CHALLENGE
to predict the PRNG's next outcomes (assuming P256 base points).

Of course, Dual EC is an extreme case, for which the randomness could 
still be
available from other protocol materials (e.g., ConnIDs or keys), but we 
should
anyway avoid specifying a protocol that would offer Secure Randomness 
easily,
and not under the peer's control.

I suggest to specify what "unpredictability" means and how to compute it
and iterate over multiple "unpredictable" payloads. A goal would be to make
clear that we want as few as possible outputs from SecureRandom() to 
avoid for
e.g., a client to have an oracle access to the Server's PRNG. A solution 
could
be to use a simple Hash function and R, 16 bytes of randomness only 
known by the
server and global to all sessions. Then a PATH_CHALLENGE could contain, with
SESSION_SERCRET the shared derived secret of the session:

Challenge_1 = H(SESSION_SECRET || R)

Then, the next one:

Challenge_2 = H(Challenge_1 || R)
...
Challenge_i = H(Challenge_i-1 || R)

This maintains unpredictability, assuming a cryptographic hash function 
and R
secret. I guess that other constructions are possible as well, using 
HKDF for
example.

I would also suggest looking into other places for which "unpredictability"
is needed, and evaluate whether it could provide good oracle access to the
other peer, and if we can be more exigent into the specifications to 
make sure
to avoid those issues.

I have opened a issue to github to further discuss appropriate changes, 
if any are decided.

https://github.com/quicwg/base-drafts/issues/4314


Best regards,

Florentin

[0] 
https://github.com/quicwg/base-drafts/blob/master/draft-ietf-quic-transport.md#initiating-connection-migration-initiating-migration

[1] 
https://github.com/quicwg/base-drafts/blob/master/draft-ietf-quic-transport.md#initiating-path-validation