Subject: Fwd: Crypto review?

From: Martin Duke <[email-masked]>
Date: Tue, 14 Dec 2021 10:52:04 -0800

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 <[email-masked]>
Date: Tue, Nov 9, 2021 at 8:40 AM
Subject: Re: Crypto review?
To: Ilari Liusvaara <[email-masked]>, Martin Duke <
[email-masked]>
Cc: Benjamin Kaduk <[email-masked]>, Roman Danyliw <[email-masked]>

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

---

From: Martin Duke <[email-masked]>
Date: Tue, 14 Dec 2021 10:52:50 -0800

crypto review thread #2

---------- Forwarded message ---------
From: Martin Duke <[email-masked]>
Date: Thu, Nov 18, 2021 at 1:48 PM
Subject: Re: Crypto review?
To: Ilari Liusvaara <[email-masked]>
Cc: Christian Huitema <[email-masked]>, Benjamin Kaduk <[email-masked]>,
Roman Danyliw <[email-masked]>

Regarding the non-crypto parts that Christian asked me to reply to:

On Thu, Nov 18, 2021 at 3:09 AM Ilari Liusvaara <[email-masked]>
wrote:

> On Tue, Nov 09, 2021 at 08:40:10AM -0800, Christian Huitema wrote:
> <snip>

> 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.
>
> Okay, that does not make any sense. If one has 64 bit plaintext, it is
> fundamentially impossible to inject more than 64 bits of entropy per
> plaintext. And if one looks at some sort of multi-output generalization,
> the entropy injections are much greater than 24 bits.
>
> And I would think that if 4 rounds is not enough, then that would call
> entiere AES into serious question.

Christian didn't directly reply to this, but I take this discussion to mean
that we believe 4 rounds is sufficient; I have nothing more to add.

> > 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.
>
> Oh sorry, that was unclear (and not directly related to crypto):
>
> I was talking about routing packets back from the server:
>
> - The client needs to see the return packets to come from the LB. Not
>   just for the client itself: Some NAT boxes will break otherwise.
> - The server can not send on behalf of LB. That breaks in presence
>   of BCP38 filtering, which may be required.
> - So the server need send via the LB. So it needs to put the LB
>   as outer IP in reply packets. But LB needs to put the client as
>   outer IP for reply pakets for those to reach the client.
>
- So LB needs to know the client IP. The packets do contain a CID, but

  it is randomly generated by the client, so LB would have to keep
>   CID to IP mappings.
> - But even that breaks in case of migration (either voluntary or
>   involuntary), as either the address CID points to changes, or a
>   new never before seen CID appears.
>

To my knowledge, Layer 4 LBs are not using inner and outer IP addresses.
Either they are NATing the client IP to its server-facing interface
address, or they preserve the client IP and the server default-routes to
the LB.

QUIC-LB is agnostic as to whether the LB has per-connection state or not.
It is certainly possible to decode every inbound CID and route it
accordingly, or it can just decode the first packet from a 4-tuple and just
use the 4-tuple from there. It's early days, but I've heard of
implementations that make either choice.

If the LB is NATing the client IP, then yes, it will need to keep some
connection state, like any other NAT.

If the server-LB traffic actually encapsulates the QUIC IP packets in an
outer IP, as you suggest, I don't see that there's an issue: the LB simply
decapsulates the packet and sends it on its way.

> > 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.
>
> ... And this is another thing not directly related to the crypto.
>
> What should LB that routes on SNI do if it receives packet with unknown
> QUIC version?
>
> - It can not pass that on, as it has no idea of next-hop.
> - Dropping that packet or returning an error presumably causes QUIC to
>   fail hard.
> - Sending back version negotiation might at least allow forward
>   progress.
> - That version negotiation can not have versions the LB does not know
>   about or versions the backed does not know about. As client picking
>   any such version causes a deadlock.
> - And then one has to disable the LB-unsupported versions on the
>   server, in order to avoid tripping downgrade attack detection.
>

I agree that SNI switching interacts poorly with new versions unless those
versions are deployed in lock step. That is a property of QUIC versioning,
not of migration or QUIC-LB. In the absence of routing based on the packet
payload, QUIC-LB does allow LBs to support migration even if the LB never
upgrades its supported versions.

I have thought about an optional "Suggested CID" frame that would be a
message to the client to use that CID for the next connection, so that it
would be routed correctly. The use case for that is not clear, however, as
you would still need to connect with an earlier version to bootstrap it.

Thanks for this review!
Martin

> -Ilari

---

From: Martin Duke <[email-masked]>
Date: Tue, 14 Dec 2021 10:54:22 -0800

Adding the QUIC WG and removing the Sec ADs.

Ilari, I would like your input on the questions below.

On Wed, Nov 24, 2021 at 3:50 PM Martin Duke <[email-masked]> wrote:

> Hi All,
>
> Thanks for the review. I've made an attempt to capture this conversation
> in a PR:
> https://github.com/quicwg/load-balancers/pull/146
> Please take a look.
>
> Some questions from earlier in the thread:
> (1) Is it alright if the server ID and nonce are of very different
> lengths, so that the "split" is nowhere near even? Or should we just take
> exactly half the octets even though they represent different information?
>
> (2) Does this have similar security properties to a normal block cipher
> with 16 bytes of entropy?
>
> On Thu, Nov 18, 2021 at 2:09 PM Martin Duke <[email-masked]>
> wrote:
>
>> Ilari,
>>
>> One last question about the 4-pass design you describe. With these
>> improvements, do you see any *security* advantages of a technique where
>> we have a full-size AES block via a random nonce (i.e. 16 - sid_length
>> bytes of nonce)? Clearly, it's nice to do only one pass, but if it doesn't
>> confer any additional protection I think the cost in terms of longer CIDs
>> is probably too prohibitive to make it a worthwhile alternative.
>>
>> On Thu, Nov 18, 2021 at 12:54 PM Martin Duke <[email-masked]>
>> wrote:
>>
>>> I received a PR to pad these items in accordance with RFC 2315 (PCKS #7)
>>> sec 10.3, instead of zeros. Is this a valuable improvement? I have very
>>> little intuition here.
>>>
>>> On Thu, Nov 18, 2021 at 10:38 AM Christian Huitema <[email-masked]>
>>> wrote:
>>>
>>>> Ilari,
>>>>
>>>> Thanks for the suggestion. This is very practical, and I will change
>>>> the
>>>> text to follow it. Your message also discusses the exchanges between
>>>> load balancer, servers and clients, and I will let Martin respond to
>>>> that.
>>>>
>>>> On 11/18/2021 3:09 AM, Ilari Liusvaara wrote:
>>>> > One way would be (while also making splitting even):
>>>> >
>>>> > (l,r) <- split_even(server||nonce)
>>>> > l <- l XOR truncate(AES(K,r||zeroes||1))
>>>> > r <- r XOR truncate(AES(K,l||zeroes||2))
>>>> > l <- l XOR truncate(AES(K,r||zeroes||3))
>>>> > r <- r XOR truncate(AES(K,l||zeroes||4))
>>>> > enc_cid <- l||r
>>>> >
>>>> > One issue with this is that if server||nonce is of odd length,
>>>> > split_even would produce something with a half octet, which is a bit
>>>> > annoying.
>>>>
>>>> As you say, a pure "split even" is a bit hard to implement, given octet
>>>> boundaries. Would we lose too much strength by splitting at the octet
>>>> boundary closest to the middle, such "3 bytes left, 4 bytes right"?
>>>>
>>>> I also considered a split_top_bottom, i.e. AND with (0xF0...) for top,
>>>> with (0x0F) for bottom, but that's a bit exotic, and probably wrong in
>>>> some subtle ways. I am worried about degenerate cases in which server <
>>>> 16 and nonce < 16, in which case top might be all zeroes.
>>>>
>>>> -- Christian Huitema
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 14 Dec 2021 22:31:41 +0200

> > https://github.com/quicwg/load-balancers/pull/146

That construction can be pretty unbalenced, and I do not know if 4
rounds is sufficient in that case.

> > exactly half the octets even though they represent different information?

I tried to look at security of unbalanced Feistel ciphers. One paper I
found stated that the general case is open problem. There might be later
paper that solved the case, but I did not see one.

The result that four rounds is sufficient (given good enough PRF) only
hold for balanced case. Unbalanced casese can require more rounds. And
they definitely do once things get highly unbalanced.

And every octet should avalanche to every octet right (that would
certainly happen with block cipher)? So informations being different
does not matter.

One of the issues with always balancing it is that if number of octets
is odd, one of the octets gets split, with 4 bits ending up on one side
and 4 to the other.

> > with 16 bytes of entropy?

Four round balanced Feistel with good enough PRF is normal block cipher.

AES is not a PRF, but I would expect it to behave very close to one if
number of samples available is not huge. E.g., trivial collision-
checking requires on order of 2^64 samples.

-Ilari

---

From: Martin Duke <[email-masked]>
Date: Tue, 14 Dec 2021 12:55:29 -0800

Thank you Ilari,

We'll split the odd octet, if need be. In an hour or two you should see an
updated PR that reflects what I think you're recommending.