Fwd: Crypto review?

[Martin Duke <[e-mail]>]

Hello all, it occurred to me that I did not CC the group about the QUIC-LB
crypto review. I'll forward a handful of messages so that others can
reconstruct the thread.

---------- Forwarded message ---------
From: Christian Huitema <[e-mail]>
Date: Tue, Nov 9, 2021 at 8:40 AM
Subject: Re: Crypto review?
To: Ilari Liusvaara <[e-mail]>, Martin Duke <
[e-mail]>
Cc: Benjamin Kaduk <[e-mail]>, Roman Danyliw <[e-mail]>


Thanks, Ilari. Comments in line.

On 11/9/2021 4:31 AM, Ilari Liusvaara wrote:
> On Mon, Nov 08, 2021 at 01:08:16PM -0800, Martin Duke wrote:
>> Christian and I have been working on a crypto design in the QUIC WG that
>> could use some expert review. Ben Kaduk suggested I ask you two directly.
>> Specifically, section 5.2 here:
>>
>>
https://quicwg.org/load-balancers/draft-ietf-quic-load-balancers.html#name-stream-cipher-cid-algorithm
>>
>> Briefly, this draft encodes a server ID for load balancing purposes
inside
>> a QUIC connection ID. The encryption is meant to conceal this mapping to
>> observers.
>>
>> Christian proposed the algorithm in Section 5.2 to allow shorter
connection
>> IDs than the very straightforward block cipher CID in Section 5.3. It's
>> three-pass algorithm with some similarities to FFX.
>>
>> We are moving in the direction of WGLC for this draft. So beyond the
>> general suitability of the design in question, if it provides equivalent
>> levels of confidentiality to the block cipher design, we're inclined to
get
>> rid of the latter to simplify things.
>
> I have some concerns (might be me misunderstanding things) about this
> (both cryptographic and other):
>
> - There are no round constants, so slide attacks might apply (at least I
>    think symmetric ciphers have round constants due to slide attacks).
>    Looking at FFX, it does have round constants (using FFX-A2 directly
>    would not work, because it has 128-bit limit, and cid can be 152).

How would you go about adding that?

> - This uses three rounds even with non-even split. That might not be
>    enough. Firstly, non-even split might increase the rounds needed, and
>    even with even split, fourth round seems to be needed in order to
>    withstand some attacks (those attacks might not be relevant here
>    however). FFX-A2 seems to use a lot more rounds. I do not know why,
>    it does even split and AES should be pretty close to ideal (tho AES
>    is already known not to be quite indistinguishable from ideal, e.g.,
>    one can not use usual cipher-to-hash constructs with it), so I would
>    think four rounds would suffice.

There is a discussion in one of the FFX appendices. From what I
understand, the 12 rounds recommendation in FFX is based on entropy
considerations, and I am not sure I understand that correctly. Each
round merges entropy from input and key into the rather short target of
the round -- say 24 bits for example. Thus, although there might be 64 +
128 bits of input, only 24 buts of entropy are injected, and one would
need about (64+128)/24 = 8 rounds to fully inject the entropy. Add the
minimum number 3, rounded to 4, and you get 12. As I said, I am not sure
I understand that correctly, and I am sure that if we did request 12
rounds developers will just not use this scheme.

That said, yes, 4 rounds might well provide more margin than the bare
minimum of 3. I am actually concerned of one misuse pattern in which
servers use a counter for the nonce, and reset the counter at the
beginning of an epoch. The epoch rollover is visible in clear text.
Adversaries could collect CIDs generated just after a rollover, and use
the knowledge that the nonces will be very small numbers to mount an
attack. Same sort of abuse might happen if the server identifiers are
taken from a small range of integers. I think that the extra round might
provide protection against that.

Another protection might be to add some entropy to the nonce. For
example, if implementations use a counter, ask them to construct the
nonce by xoring the counter with a per-epoch and per-server random number.

> - Does this need sharing a key between load balancer and all backend
>    servers? While sharing keys between LB and an individual backend is
>    not a big problem, sharing a key with all of them is whole another
>    thing.
Yes, that's an obvious issue, but it is not specific to this scheme --
the straightforward use of AES in 17 bytes CID has the same issue.
> - How does reverse routing work? QUICv1 does not support server
>    migration (due to attacks), so presumably the server part of five-
>    tuple has to match (unless preferred address is used, but that has
>    its own serious deployability issues). That part is held by the LB,
>    so servers would somehow need to send on behalf of the LB.

The CID are created by the server, and then passed to the clients. The
clients put them in their packets. The LB reads the CID from the
incoming packet, decrypts it to retrieve the server-id, and routes the
packet to that server ID. LB might cache the CID that have been seen
recently to reduce decryption load.

We are worried that adversaries find a way to retrieve the server ID
associated with a CID, and use that knowledge to attack individual
servers in the pool.

> - If LB routes on SNI (I expect this to be pretty common), any
>    connection with unknown version is unrouteable. It seems the only
>    way to handle that without causing hard failures is for LB to enage
>    in version negotiation on behalf of sever. This presumably requires
>    knowledge of all QUIC versions enabled on the server, and support for
>    all of those.

The CID encryption scheme is not used in that scenario. The encrypted
CID will only be used in later packets, after the initial handshake and
the selection of a server.

-- Christian Huitema