Bit by Bit: Streaming Ciphers and Wireless Security

Streaming algorithms were designed to avoid speed and throughput penalties due to the implementation of block symmetric ciphers in CFB and OFB modes when bit-by-bit data encryption is required. Streaming ciphers are based on generating identical keystreams on both encrypting and decrypting sides. The plaintext is XORed with these keystreams to encrypt and decrypt data. To generate the keystream, pseudo-random generators (PRNGs) are used, thus placing stream algorithms somewhere between easy-to-break simple XORing with a predefined key and unbreakable, but rather impractical, one-time pads. PRNG is based on algorithms that produce seemingly random but reproducible numbers. Because they can be reproduced, they aren't truly random. However, PRNG output should be able to pass a battery of specially designed randomness tests. A decent source on PRNGs, including open source PRNG software to download and detailed descriptions of randomness tests, is available at http://random.mat.sbg.ac.at/. U.S. government suggestions, standards, and regulations on randomness generators and their evaluation criteria are published at http://csrc.nist.gov/encryption/tkrng.html. PRNG digests a pool of data (called a seed) and uses it to generate numbers that look random. However, if you feed a different seed, the results of a PRNG run would be different. Using the same seed always gives you the same results. If the same seed repeats over and over, the cryptosystem becomes predictable and can be broken. Thus, a large seed is frequently used to maximize the amount of ciphertext a would-be attacker has to collect to catch the repeating strings. This explains why seeds of streaming ciphers are not used as keys (do you really want a 65,535-bit key?).

Of course, keystreams on both sizes must be synchronized to make such a cryptosystem work. This synchronization can be provided by the cipher operation itself. Such streaming ciphers are called self-synchronized. In self-synchronized ciphers, each keystream bit is dependent on a fixed amount of previous ciphertext bits. Thus, self-synchronized ciphers operate in a manner very similar to the way block algorithms work in CFB mode. Alternatively, the synchronization can be independent of the ciphertext stream, in which case it has to be done via external means. This streaming cipher type is known as the synchronous stream cipher, and you probably guessed that block ciphers in the OFB or CCM mode (802.11i AES) operate in a similar manner.

The most commonly encountered stream cipher of today is a synchronous stream cipher, RC4, which we already mentioned when discussing Kerckhoff's principle. RC4 is a default cipher used by the SSL protocol and WEP. RC4 uses a variable 0- to 256-bit key size. It employs 8x8 S-box entries that include permutations of numbers from 0 to 255. Permutations are a function of the key supplied. RC4 is very fast, approximately 10 times faster than DES. For maximum performance, RC4 should be run in hardware, as it done in Cisco Aironet and many other wireless client cards' WEP RC4 implementations. Its speed is one of the main reasons RC4 is so widely implemented by the networking security protocols we have mentioned. So how about that infamous WEP cracking story we outlined in Chapter 8?

One should distinguish between flaws in ciphers and their practical implementation. The weakness of WEP is not a flaw in RC4, per se. RC4 is a PRNG. A seed for this PRNG is made up of the combination of a secret key (does not change and is similar for all hosts on the WLAN) and the IV, which makes the seed unique. The IV implemented in WEP is only 24 bits—a very small number in cryptographic terms. No wonder it starts repeating itself after a sufficient amount of data on a busy WLAN passes through. However, selecting a seed of insufficient size is not the PRNG's problem. In fact, in the SSL protocol, RC4 keys are produced for each session and not permanently, as in the "classical" static use of WEP. Thus, a would-be SSL cracker cannot accumulate the amount of data necessary for a successful attack against RC4, at least theoretically. In a rather obscure and now nearly extinct HomeRF technology (FHSS alternative to 802.11b), the size of IV is 32 bits, which significantly enhances its security in comparison to 802.11b-based LANs. As an alternative to increasing the IV size, one can go the SSL way and implement per-session or even per-packet keys and automatically rotate the keys after a short period of time. Per-session and rotating keys were the heart of the initial Cisco SAFE wireless security blueprints, and 802.11i/WPA implement both larger 48-bit IV and dynamic key rotation, as we have already reviewed. Finally, RSA Labs has suggested a rather simple but elegant solution for the weak WEP IV problem (more details are available at http://www.rsasecurity.com/rsalabs/technotes/wep.html). RSA cryptographers calculated that if WEP could discard the first 256 bytes produced by the keystream generator before the keystream is XORed with plaintext, there would be no weak IVs on the wireless network. Unfortunately this technique, as well as the RSA fast-packet rekeying fix mentioned earlier, is not compatible with the still common implementation of WEP. Nevertheless, the IEEE, along with wireless equipment, firmware, and software vendors, are slowly catching up, as 802.11i/WPA, Cisco SAFE, and Agere/Proxim WEPPlus development shows.