Why do stream ciphers like A5/1 and ZUC have "frames"?

Question

A5/1 and (I think) ZUC, both stream ciphers used in mobile telecommunications, have "frames" where the, in addition to the key, a frame number is provided to the keystream generator which produces a relatively short pseudorandom sequence called a "frame" (on the order of at most a few kilobytes).

Advancing the stream cipher requires incrementing the counter and running the algorithm again with no state carried over from the generation of the previous frame. This stands in contrast to stream ciphers like RC4, Trivium, and Grain, where the $i$^th keystream bit can only be computed after generating the previous $i-1$ bits, and in contrast to counter mode and stream ciphers like ChaCha20 which are capable of complete random access.

What is the rationale behind these "frames" and why not just go for full random access if they want this?

Answer 1

What is the rationale behind these "frames" and why not just go for full random access if they want this?

That's because they're used in mobile communications. There, packets can easily be dropped in transit (e.g. by a bit of electrical noise that just happens to come in at the wrong time); possibly with the receiver not even knowing that he missed one.

Because of this, it is necessary to design our crypto system to be able to decrypt even if packets are missing; using a system that can decrypt only if it has successfully received the previous packets just doesn't work. One approach to do this is to put in a frame number; by using the frame number, the decryptor can work even if he missed some packets.

Now, you might think that we might also try to make the system reliable, by having the sender retransmit packets that the receiver didn't get (just like TLS does). This really doesn't work out for voice communications; not only does it consume extra bandwidth (which is precious), live voice is time sensitive; if the next audio segment does come in late, the receiver can't do anything with it, and so there's no point in retransmitting it.

As for why they use serial numbers, rather than another approach (e.g. a random nonce), serial numbers are needed to tell the receiver when this segment of the voice should be replayed, and so voice communications have serial numbers in there anyways; using the same thing for two different purposes reduces on the bandwidth used (and, as I said, that's a major concern for wireless).

Answer 2

What is the rationale behind these "frames" and why not just go for full random access if they want this?

First for the name "frame number". In low level communication tech, like with Ethernet or WiFi where you think about "Bits" as opposed to "high level data packets / structures", the individual packets, which don't need to map 1-to-1 to IP packets, are called frames.

Now for why they use it. The role of this frame index for the cipher is the same as with a nonce for fully-fledged modes like GCM: So that different encryptions of the same plaintext yield different plaintexts. For this you need uniqueness of the nonces, which happens to be the case with frame indices.

Finally, why not use random access? It's not needed. You very rarely need random access to plaintexts (rather you decrypt a whole message in one go) and this is one of the cases where the designers decided that having this nonce mechanism is sufficient. Also if you implement the relation between stream cipher block indices like in CTR, this is prone to mis-use because in CTR, if your message is longer than 1 block, you need a bigger offset with your IV than 1, whereas with this an offset of 1 probably is safe.