Potential PRNG attack via Stateless Reset

[mikkelfj]

The editors draft on stateless reset states that

7.9.4. Stateless Reset: ... The Packet Number field is set to a randomized value.

This may already have been discussed as I have not followed the stateless reset discussion closely, but here is my concern regardless:

The concern is that any unqualified peer can elicit stateless reset packets in order to get more entropi information about the PRNG being used to generate random packet numbers. If this PRNG is also being used for key material and the PRNG is not fully protected against such attacks, it might be possible to guess future keys for an adversary with sufficient resources.

There are other places in QUIC where random numbers are exposed, but stateless reset may be particularly easy to trigger in high volumes. A stateless reset might also be easier to trigger without attracting unwanted attention compared to proper connection establishment.

What is the motivation behind adding a random packet number ?

[ekr]

The server's first flight includes the ServerHello, which has a random value. How is this easier to elicit?

…

On Thu, Oct 19, 2017 at 5:29 AM, MikkelFJ ***@***.***> wrote: The editors draft on stateless reset states that 7.9.4. Stateless Reset: ... The Packet Number field is set to a randomized value. This may already have been discussed as I have not followed the stateless reset discussion closely, but here is my concern regardless: The concern is that any unqualified peer can elicit stateless reset packets in order to get more entropi information about the PRNG being used to generate random packet numbers. If this PRNG is also being used for key material and the PRNG is not fully protected against such attacks, it might be possible to guess future keys for an adversary with sufficient resources. There are other places in QUIC where random numbers are exposed, but stateless reset may be particularly easy to trigger in high volumes. A stateless reset might also be easier to trigger without attracting unwanted attention compared to proper connection establishment. What is the motivation behind adding a random packet number ? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#892>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABD1oTkI-BZtbBBxrw3-CcCa3zOdJEsHks5st0CWgaJpZM4P_Jlr> .

[mikkelfj]

The server's first flight includes the ServerHello, which has a random value. How is this easier to elicit?

It may be the same problem there, but it seems more necessary, and it is more difficult to hide spurious connection attempts than sending data on nonexisting connections. And, if random data isn't strictly needed, it should be avoided. Perhaps there need to be some guidelines on how ServerHello produces random - isn't it via a HKDF which somewhat protects the PRNG - I haven't looked hard at that.

[ekr]

No, it's not. It's up to the implementation. Anyway, this does need to be random in some way because it needs to be indistinguishable from non reset.

[mikkelfj]

I'm a bit torn on this - I belive I have previously claimed that QUIC ought to be able to trust the PRNG, but then I'm not sure that is a safe thing to do.

[martinthomson]

The general advice regarding randomness that is exposed like this is to use a separate CSPRNG instance to the one that is used for generating private keying material. That said, I don't believe that there is much value to the paranoia around safeguarding against a bad PRNG. A PRNG that reveals its state as a result of its output being seen isn't worthy of being called CS, and the method for ensuring that this doesn't happen is pretty simple to implement.

You will note also that the text does not require cryptographically secure randomness here.

[mikkelfj]

I mostly agree here. Regarding paranoia, I'm not sure you can have enough:

https://www.alexhudson.com/2017/10/15/wpa2-broken-krack-now/

I guess my point is, how can we reduce the attack surface without overengineering. E.g. being more paranoid about offpath attacks.

[huitema]

The recommended implementation is to set the stateless reset secret to something like hash(some local secret, connection ID). The typical implementation will be:

1. At initialization of the server, get N bytes from the PRNG;

2. When bad connection arrive, compute a hash of that and connection ID.

Yes, attackers can use the packets as an oracle: guess a local secret value, send a bogus packet with a chosen ID, observe the hash in the stateless reset. If they can break the HASH, they might be able to get back to the secret. But that's a big IF -- the typical implementation would use SHA256, and being able to reverse the values mean that SHA256 is really broken. There might be other attacks available at this point than reversing a hash to find 16 bytes of PRNG output from some unspecified time in the past.

[mikkelfj]

My concern here is not the token, assuming it is hashed properly. It is the other random data that might expose the internal state of the underlying PRNG. Sometimes crypto libraries default to OS PRNg and it might be broken, or deliberately flawed:
https://en.wikipedia.org/wiki/Random_number_generator_attack

Some claim large tables exists to attack PRNGs:
https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1676224

Some PRNG's may be good, but only when the entropy is not exhausted. Better PRNG's use something like a CTR mode encrypted to derive values from a short entropy source.
https://www.schneier.com/academic/fortuna/

Again, I don't really think it is QUIC's concern to fix PRNG's, but still, a conservative approach to exposure should be taken when feasible.

[huitema]

So, you are concerned with the large number of random padding bytes? OK. Do you have a suggestion on a practical algorithm that would not rely so much on the PRNG, and yet meet the goal of not being detectable by a observers?

[mikkelfj]

The Stateless reset could use AEAD encryption, and include the connection ID in the encrypted content. Then padding and connection ID can be set to zero and encrypted, but the AEAD key for the packet is then derived from a random value instead of using the (previously random) connection ID.

This is roughly what a good PRNG already does, but thinking AEAD into all packets this way is consistent and significantly safer.

In a broader context, the cleartext AEAD on other handshake packets also helps protect againts PRNG attacks, except as already pointed out, one could attempt to create a lot of connections.

[mikkelfj]

Alternatively the connection ID could be hashed with a hmac using a random key, and padding would use a counter as input.

[ekr]

As these bytes are not examined by the client, this doesn't seem like it needs to be specified in the protocol.

[martinthomson]

I'm going to close this one. It's clear that there are many ways in which the random bits you need might be obtained without exposing the state of the PRNG that you use for key generation. How an implementation safeguards itself is up to that implementation.

(FWIW, if you care about this specific issue, I would encourage you to pursue a more general solution, perhaps by revising RFC 4086. Then everyone benefits, not just QUIC.)