Why does not GSM use any stream cipher mode (OFB, CFB)?

Question

If I understand correctly GSM uses A5/1 stream cipher. My question is why doesn't it use a stream cipher mode like OFB or CFB?

Answer 1

Actually, GSM uses "A5", which is not one algorithm, but several. The initial GSM standard dates from the late 1980s, and had to work on hardware available at that time. A mobile device using what was considered the standard secure block cipher algorithm at that time (3DES) would have been too bulky and drawn too much power to be considered "mobile", even in the eighties.

So custom algorithms were designed. The A5 family contained three algorithms:

• A5/0, which is "no encryption at all".
• A5/1, the "strong" algorithm for well-behaved countries.
• A5/2, the "weak" algorithm for other countries.

The distinction between A5/1 and A5/2 makes sense only if envisioning to eavesdrop on phone calls. However, A5/1 was supposed to be strong (presumably, in lawful countries, eavesdropping is done by law enforcement agencies through official judiciary channels, and thus can be done on the network provider side, without needing to break through the on-the-air encryption system).

A5/1 and A5/2 use just a few LFSR; they are remarkably power-efficient. An A5/1 core can use less than 600 transistors, while a 3DES inefficient core (one round, with a loop counter, no pipeline) would need 5 to 10 times as much; and AES even more (AES was invented ten years later anyway). A5/1 still offers an extremely high security-to-power ratio.

Unfortunately, A5/1 was designed with too small an inner state, reflecting the traditions of the industry at that time (in particular the tradition of not allowing academics to come too near of practical applications, lest they break something through their quaint disregard for the mundane world). The A5/1 structure (three LFSR with the special clocking rule using the middle bits) offers, for a total internal state of n bits, a security level of about 2^2n/3 (see section 3 of this article). This means that the 64-bit space of A5/1 brings security to be about the same as a 42-bit block cipher, i.e. not a lot... and quite a few researchers have describes "breaks" which apply various precomputed table methods to this 42-bit strength problem.

A "boosted A5/1", with the same structure but three times larger (three LFSR of total size 192 bits or so) would still be impeccably secure nowadays, and more power-efficient than any more classical alternative.

---

Technology improved, and modern mobile phones are now computers, with CPU which are perfectly able to encrypt and decrypt data at full network bandwidth, with more usual algorithms. Therefore, for 3G, the A5 family was adjoined a fourth member, called "A5/3": this is the block cipher KASUMI turned into a stream cipher by being used in OFB mode. KASUMI is still "optimized for hardware" (its S-boxes are derived from relatively simple boolean expressions) but much closer to what is done in software-oriented block ciphers.

Summary: GSM did not use a block cipher in CTR or OFB mode mainly because of limitations of the available hardware at that time (25 years ago). And nowadays, it does use a block cipher in OFB mode.