Behavior of integrity with packet hashes with losses

louisna commented 9 months ago

What is the dependency between packets when carrying hashes on the multicast channel? If I understand correctly, this creates a dependency between all subsequent packets. Packet x is needed to authenticate packet x+1, and so on. If packet x is lost, packet x+1 cannot be authenticated yet, and we need a retransmission to authenticate x+1. But what is retransmitted? Because the content of packet x will be retransmitted in packet x+y, which must be authenticated using packets x, x+1, ..., x+y-1, which is dependent on packet x that is lost. Maybe there is something that I did not get.

Additionally, I can write some text for the authentication methods discussed in my Arxiv paper (https://arxiv.org/pdf/2309.06633.pdf). This uses asymmetric signatures (at the packet level and stream level).

IMHO, providing per-packet or per-stream authentication, even if more costly due to the asymmetric signatures, can be more beneficial since it does not introduce head-of-line blocking between packets (again, if I understood correctly Section 7 of the draft).

MaxF12 commented 9 months ago

The question about how to do integrity for multicast has been open for quite a while now. The concept of integrity frames originally started with AMBI and was mostly carried over to Multicast QUIC from there. IIRC, the conclusion was that even if you transmit all integrity frames over unicast and guarantee reliability that way you would still be more efficient than to use asymmetric signatures, even for large numbers of subscribers. I think Jake had some numbers on that as well.

Personally, I think in the end having it be done with integrity frames just offers more flexibility to the server as to how exactly achieve integrity, depending on current network conditions and the use case. It can either choose to transmit all integrity frames over unicast, include one integrity frame in each multicast packet to authenticate the next one like you mentioned, or send one packet that consistent exclusively of integrity frames to authenticate the next x packets. In case that packet then gets lost, it can be easily be retransmitted over unicast. We even had considerations about having a second multicast channel used for authentication separate from the one used for data. Also see #48 for more discussion on this.

I think this might also be one of the points that will be guided by some implementation/ deployment experience further down the line.

GrumpyOldTroll commented 9 months ago

IIRC when I checked there weren't any asymmetric algorithms that can verify a signature per packet on e.g. an android phone for a 10mbps stream. I can't recall exactly how far off it was, but it wasn't close--if you use all the processing on the device you could do something like a quarter or a half that, with nothing left over for rendering video.

I think https://datatracker.ietf.org/doc/draft-pardue-quic-http-mcast/ took an approach closer to per-stream authentication (it was per http object, but I think that's a similar idea). While that's ok when everything is going well, it made me uncomfortable because a single corrupt packet would require a retransmit of the entire stream, meaning an attacker injecting corrupt packets can DOS with a high amplification since the entire stream is corrupted because of one malicious packet. This is often an amplification of >1000x, and imo it's not a viable protection scheme, though opinions do differ here.

The scheme with integrity frames allows for retransmit of the integrity frames. If you've buffered some packets as possibly to be accepted, there's not a strict ordering requirement on which packets you depend on, and integrity frames can be retransmitted (either over unicast or multicast). Each integrity frame can authenticate multiple packets, and they're ack-eliciting so the sender knows they must be retransmitted.

It's also permissible to send hashes multiple times in different integrity frames, so that the receiver's ability to authenticate a packet depends on receiving any of several different packets containing an integrity frame with that packet's hash. I think it makes good sense to send each hash multiple times if we're sending them on a multicast channel, though the exact redunancy tuning is left to the deployment.

Not sure if that answers your question? I don't think there's a strict dependency of packet x+1 on packet x nor necessarily a blocker for later packets, and if a packets containing integrity frames are lost the acks should tell the sender about it and the hashes should get retransmitted, either by unicast or multicast.

louisna commented 9 months ago

Thanks for the quick responses.

I think https://datatracker.ietf.org/doc/draft-pardue-quic-http-mcast/ took an approach closer to per-stream authentication (it was per http object, but I think that's a similar idea). While that's ok when everything is going well, it made me uncomfortable because a single corrupt packet would require a retransmit of the entire stream, meaning an attacker injecting corrupt packets can DOS with a high amplification since the entire stream is corrupted because of one malicious packet. This is often an amplification of >1000x, and imo it's not a viable protection scheme, though opinions do differ here.

I agree that, as defined in the paper, stream-level authentication can bring DOS issues. I think that we should define a threat model for Multicast QUIC. For example, a conservative approach would be to leave the multicast channel if the client notices a wrong authentication of a stream, and fall back on unicast. (TLS closes the connection when it sees corruption, for example).

It's also permissible to send hashes multiple times in different integrity frames, so that the receiver's ability to authenticate a packet depends on receiving any of several different packets containing an integrity frame with that packet's hash. I think it makes good sense to send each hash multiple times if we're sending them on a multicast channel, though the exact redunancy tuning is left to the deployment.

Indeed, adding multiple times the same packet hash in subsequent (or preceding) packets can alleviate losses and still provide per-packet authentication. Thanks for the clarification. However, I still have an interrogation on the frequency of unicast-transmitted MC_INTEGRITY frames.

Not sure if that answers your question? I don't think there's a strict dependency of packet x+1 on packet x nor necessarily a blocker for later packets, and if a packets containing integrity frames are lost the acks should tell the sender about it and the hashes should get retransmitted, either by unicast or multicast.

For example, let us consider the case of a video streaming application at W images per second. The application sends new frames every 1/W seconds. Moreover, let us consider that every application frame holds in 3 QUIC packets.

It means that the video frame will span packets x, x+1 and x+2. If I understand correctly, packet x+2 will hold an MC_INTEGRITY frame with packet hashes for hash(x) and hash(x); x+1 for hash(x).

At this point, we need to make sure that packet x is authenticated, so we need to send an MC_INTEGRITY frame using the unicast connections to all clients. Without loss, each client receives hash(x) on the unicast connection, as well as packets x, x+1 and x+2, and can correctly authenticate the three packets. That's fine.

Now we wait for 1/W seconds to get the following video frame. At this point, packets x, x+1 and x+2 have already been sent on the wire. This video frame will span packets x+3, x+4 and x+5. Packets x, x+1 and x+2 are authenticated, but I don't know how we can benefit from them to authenticate x+3, x+4 and x+5. The only way I see it is to send (again) hash(x+5) on the unicast connections to all clients to authenticate x+3, x+4 and x+5.

For a delay-sensitive application, we may buffer some Multicast QUIC packets (e.g., x and x+1 when generating x+2), but it can become a problem if we buffer packets for multiple video frames (e.g., buffering x -> x+5) to send fewer hashes through the unicast connections. Without buffering, I don't understand how we could leverage previously authenticated packets through packet hashes for new data that was not available at that time. Please let me know if my understanding is wrong. The only way I see it is to send hashes through the unicast connections for each video frames (or maybe by group of 2-3 of them, if we tolerate small buffering), which is (in my opinion) against the "pure multicast philosophy".

The concept of integrity frames originally started with AMBI and was mostly carried over to Multicast QUIC from there. IIRC, the conclusion was that even if you transmit all integrity frames over unicast and guarantee reliability that way you would still be more efficient than to use asymmetric signatures, even for large numbers of subscribers

I took a look at the AMBI draft, and also at ALTA. I think the best methodology lies in-between. Having packet hashes to authenticate bunch of packets is a smart way to go, thanks to computational efficiency. However, only relying on unicast transmission of the "root of trust" may not be the only way to go. ALTA's point of view is to use digital signatures to create this root of trust. Even if this is more computationally intensive, it releases resources on the network, as fewer packets are sent - and its scalability is independent of the number of receivers.

What I mean by "in-between" is that we could suggest both approaches for clients. For example, the default authentication approach could use the ALTA-based method, where a single stream is authenticated using packet hashes + a digital signature at the end of the stream. For resource-constrainted devices, the AMBI-based method may be an alternative as it is less costly for these end-users. At the end of the day, both approaches are quite similar, with the difference being how to distribute the root of trust.

Do you think that it may be worth writing some text about this somewhere?

MaxF12 commented 8 months ago

I agree that, as defined in the paper, stream-level authentication can bring DOS issues. I think that we should define a threat model for Multicast QUIC. For example, a conservative approach would be to leave the multicast channel if the client notices a wrong authentication of a stream, and fall back on unicast. (TLS closes the connection when it sees corruption, for example).

I think this is a good idea, maybe we it could be generalized and added to the Multicast thread model ID?: https://datatracker.ietf.org/doc/draft-krose-multicast-security/

I'll see if Kyle has any thoughts on this if we get the chance to catch up in Prague.

Now we wait for 1/W seconds to get the following video frame. At this point, packets x, x+1 and x+2 have already been sent on the wire. This video frame will span packets x+3, x+4 and x+5. Packets x, x+1 and x+2 are authenticated, but I don't know how we can benefit from them to authenticate x+3, x+4 and x+5. The only way I see it is to send (again) hash(x+5) on the unicast connections to all clients to authenticate x+3, x+4 and x+5.

I think the idea here would be to include the Hashes for x+3, x+4, x+5 in packets x, x+1 and x+2. In your concrete use case it would for example to make a lot of sense to include all the hashes for the next frame in all the packets of the previous frame. So concretely, x1..3 each hold hashes for x4...6. The hashes for all three packets of the first frame are send over unicast to act as an anchor. So if at least one packet of that frame gets through the packets of the next frame can be decoded without a need for retransmissions over unicast in case of a single lost packet.

What I mean by "in-between" is that we could suggest both approaches for clients. For example, the default authentication approach could use the ALTA-based method, where a single stream is authenticated using packet hashes + a digital signature at the end of the stream. For resource-constrainted devices, the AMBI-based method may be an alternative as it is less costly for these end-users. At the end of the day, both approaches are quite similar, with the difference being how to distribute the root of trust.

Do you think that it may be worth writing some text about this somewhere?

I think at least it would be a good discussion to have and if there is a way to offer even more flexibility on how to achieve integrity without making the draft too complicated and complex is good as well. Offering two alternative methods might be a good way to achieve this, either by tying them directly into the ID or maybe even have a separate one for mechanisms to guarantee integrity.

GrumpyOldTroll commented 8 months ago

Hi Louis, and sorry for the slow response.

I agree that asymmetric signatures based on a securely transmitted public key can also provide a root for authentication.

My calculations suggested it’s not necessary, so I was in favor of keeping the first version simpler, since we’d still have the option to add more frames in a later spec if we have operational troubles. My math was like this:

If we have 2k packets per second at 10k bits per packet providing a 20mbps video stream transported over multicast, the unicast requirements to support that via hashes in integrity frames on the unicast stream with 32-byte SHA-256 hashes would be (256 bits/hash * 2k pps) = 512kbps + <2% overhead, which can just be sustainably sent as unicast in support of the 20mbps stream (over a 35x gain).

Optimizing that further is an option (either with smaller 160-bit SHA-1 or 224-bit SHA-224 hashes or by doing something more complicated with new frame extensions) and would likely reduce the unicast costs, but would not be a necessary blocker for deployment, and could be extended and fine-tuned later, after getting the basics functional.

I do think we’d need a buffer for unauthenticated packets, and in the case of loss and delay that gets sufficiently desynchronized, video artifacts could be visible. Of course there’s more failure modes when the unicast performance is needed to have success in the multicast stream, but my expectation was that if we did well enough with the server’s unicast fanout, it wouldn’t be substantially worse than running a unicast 20mbps stream. I also thought this would be something that could be improved with ALTA-based extensions in the future, if we needed to get the latency budget tighter, but that doing a simpler job on the earlier versions and accepting a latency penalty of ~half a second would be preferable, so I had tried for language that would allow future extensions to the ways to provide authentication.

I think extensions like an asymmetric signature that let you avoid some of the unicast would be a fine idea and good to implement at some point, I just thought it a complicating distraction from getting the first version operational, especially considering I was expecting we’d need to support some significant proportion of receivers not accepting multicast for a while, so we’d need the capability to have the senders scaling in an elastic fleet anyway.

I hope that’s helpful and that it clarifies my thoughts on the matter.

From: Louis Navarre @.> Reply-To: GrumpyOldTroll/draft-jholland-quic-multicast @.> Date: Monday, October 9, 2023 at 5:43 AM To: GrumpyOldTroll/draft-jholland-quic-multicast @.> Cc: "Holland, Jake" @.>, Comment @.***> Subject: Re: [GrumpyOldTroll/draft-jholland-quic-multicast] Behavior of integrity with packet hashes with losses (Issue #131)

Thanks for the quick responses.

I think https://datatracker.ietf.org/doc/draft-pardue-quic-http-mcast/https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-pardue-quic-http-mcast/__;!!GjvTz_vk!XMJxVxpVyzL_qCyffPSToeIDSgVybnojuR8M_j2e82VOzF0YnGDJD40pEGxWDMkpJlTIL9_aGAlLe-C9m1sjwAu6$ took an approach closer to per-stream authentication (it was per http object, but I think that's a similar idea). While that's ok when everything is going well, it made me uncomfortable because a single corrupt packet would require a retransmit of the entire stream, meaning an attacker injecting corrupt packets can DOS with a high amplification since the entire stream is corrupted because of one malicious packet. This is often an amplification of >1000x, and imo it's not a viable protection scheme, though opinions do differ here.