Subject: Potential Oracle Access to he peer's randomness

From: Florentin Rochet <[email-masked]>
Date: Thu, 29 Oct 2020 13:04:23 +0100

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

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 29 Oct 2020 05:18:14 -0700

I think you make a good point. But there are other areas of equal concern
that I no longer recall. The general QUIC consensus was that QUIC relies on
a quality PRNG and if it is compromised, all bets are off anyway.

Even so, I don’t think it is a good idea to expose more PRNG state than
necessary. Implementations are of course free to use their own discretion
in this case. I believe the wording on appearing random is carefully chosen
to allow so leeway here.  QUIC could at most provide some additional
recommendations. But then you could recommend a lot of things outside the
core area of QUIC.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 29 October 2020 at 13.04.49, Florentin Rochet (
[email-masked]) wrote:

Dear QUIC designers,

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

server and global to all sessions. Then a PATH_CHALLENGE could contain,
with

Then, the next one:

Best regards,

Florentin

[0]

[1]

---

From: Marten Seemann <[email-masked]>
Date: Thu, 29 Oct 2020 19:27:27 +0700

How is this attack different from initiating a new TLS handshake, as the
server will also use secure random in that case?

---

From: Florentin Rochet <[email-masked]>
Date: Thu, 29 Oct 2020 15:28:58 +0100

Right, preventing the PATH_CHALLENGE to output the PRNG's state does not
preclude to get it from other places within the protocol. As you 
mention, the
TLS handshake also produce secure randomness on-demand, since one can 
send many
ClientHello.

There are small differences between them that can yield the 
PATH_CHALLENGE to
offer a higher bandwidth of secure randomness to the attacker, but that 
should
not be game-changing.

make sure
 >to avoid those issues.

It is somewhat a shy call to reconsider putting the output of the PRNG 
at every
places in the protocol in which we can get it on-demand. In the TLS 
handshake,
we may also use a second construction to reduce the output of the 
"trusted" PRNG.
Intuitively, what I suggest is to build a protocol-level PRNG that is 
minimalist
in the secure randomness it requests from the OS, but built its
"unpredictability" based on the same cryptographic assumptions already 
in use in
other places of the protocols, such as the ones of HKDF.

That might be more a research question than something directly to bring 
to the
IETF, though. Intuitively, it is like reducing the surface of attack, and it
should not be too difficult to prove that it makes sense, if it does :)

Best regards,

Florentin

Le 29/10/20 à 13:27, Marten Seemann a écrit :
> How is this attack different from initiating a new TLS handshake, as 
> the server will also use secure random in that case?
>
> On Thu, Oct 29, 2020 at 19:04 Florentin Rochet 
> <[email-masked] <mailto:[email-masked]>> 
> wrote:
>
>     Dear QUIC designers,
>

---

From: Lucas Pardue <[email-masked]>
Date: Thu, 29 Oct 2020 14:33:05 +0000

Thanks Florentin,

This seems like an excellent topic for the CFRG.

Cheers
Lucas

---

From: Christian Huitema <[email-masked]>
Date: Thu, 29 Oct 2020 08:39:17 -0700

Florentin,

The code in the picoquic implementation is:

path_x->challenge[ichal] = picoquic_public_random_64();

That is, the implementation reserves the use of the crypto random
generator for the actual crypto operations, and uses a separate PRNG for
"mondane" use of random number generation. That design was very much
motivated by the considerations in your original email. There are a
variety of use of random numbers in QUIC, and I thought of those as
risks of leaking the state of the crypto random generator, and thus
enabling attacks on that generator and eventually risking exposing the
cryptographic state.

-- Christian Huitema

On 10/29/2020 7:28 AM, Florentin Rochet wrote:
> offer a higher bandwidth of secure randomness to the attacker, but
> that should
> not be game-changing.
>
> In my fist email:
>
> That might be more a research question than something directly to
> bring to the
>> <[email-masked]
>> <mailto:[email-masked]>> wrote:
>>
>>     Dear QUIC designers,
>>

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 29 Oct 2020 16:02:27 +0000

> There are a variety of use of random numbers in QUIC, and I thought of those as risks of leaking the state of the crypto random generator, and thus enabling attacks on that generator and eventually risking exposing the cryptographic state.

FWIW, OpenSSL does the same thing with an API for random bytes (RAND_bytes), and a separate one for when they’re going to be used in key material (RAND_priv_bytes)

---

From: Roberto Peon <[email-masked]>
Date: Thu, 29 Oct 2020 18:17:53 +0000

Also interesting to note that the server can ignore anything it wishes to ignore and pretend it never received it.
(Not to say the crypto/RNG elements are perfect or anything, just reminding that accepting and replying to the data is ultimately optional!)
-=R

From: QUIC <[email-masked]> on behalf of "Salz, Rich" <rsalz=[email-masked]>
Date: Thursday, October 29, 2020 at 9:03 AM
To: Christian Huitema <[email-masked]>, Florentin Rochet <[email-masked]>, Marten Seemann <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: Potential Oracle Access to he peer's randomness

---

From: Christian Huitema <[email-masked]>
Date: Thu, 29 Oct 2020 11:23:40 -0700

On 10/29/2020 11:17 AM, Roberto Peon wrote:
> Also interesting to note that the server can ignore anything it wishes
> to ignore and pretend it never received it.
> (Not to say the crypto/RNG elements are perfect or anything, just
> reminding that accepting and replying to the data is ultimately optional!)

And it is indeed a good idea to apply a rate limit of some kind to NAT
rebinding events. Somewhere in my test suite is a NAT rebinding attack,
in which every packet from the client arrives from a different IP
address. That stresses the handling of NAT rebinding, and verifies that
the server code is not getting itself tied up in knots trying to handle
a whole bunch of rebindings in parallel.

-- Christian Huitema