Cryptology 1.1 General Discussion of Bitstream Ciphers

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

XOR

As a first example of a bitstream cipher we encountered XOR in Part I of these lectures. In the twenties of the 20th century XOR ciphers were invented to encrypt teleprinter messages. These messages were written on five-hole punched tapes:

each column representing a five-bit-block. Another punched tape provided the key stream. VERNAM filed this procedure as a U. S. patent in 1918. He used a key tape whose ends were glued together, resulting in a periodic key stream. MAUBORGNE immediately recognized that a nonperiodic key is obligatory for security.

In its strongest form, the one-time pad, XOR encryption is an example of perfect security in the sense of SHANNON. As algorithm A5 or E₀ XOR helps to secure mobile phones or the Bluetooth protocol for wireless data transmission. As RC4 it is part of the TLS/SSL protocol that (often) encrypts client-server communication in the World Wide Web, and of the PKZIP compression software. There are many other current applications, not all of them satisfying the expected security requirements.

The scope of XOR encryption ranges from simple ciphers that are trivially broken to unbreakable ciphers.

Advantages of XOR Ciphers

• Encryption and decryption are done by the same algorithm. Decryption is also done by adding key stream and ciphertext (bitwise binary).
• The method is extremely simple to understand and to implement ...
• ... and very fast—provided that the key stream is available. For high transfer rates one may precompute the key stream at both ends of the line.
• If the key stream is properly chosen the security is high.

Pitfalls

• XOR ciphers are vulnerable under known plaintext attacks: each correctly guessed plaintext bit reveals a key bit.
• If the attacker knows a piece of plaintext she also knows the corresponding piece of the key stream, and then is able to exchange this plaintext at will. For example she might replace »I love you« by »I hate you«, or replace an amount of 1000 $ by 9999 $. In other words the integrity of the message is poorly protected. (To protect message integrity the sender has to implement an extended procedure.)
• XOR ciphers provide no diffusion in the sense of SHANNON's criteria since each plaintext bit affects the one corresponding plaintext bit only.
• Each reuse of a part of the key sequence (also in form of a periodic repetition) opens the door for an attack. The historical successes in breaking stream ciphers almost always used this effect, for example the attacks on encrypted teleprinters in World War II, or the project VENONA during the Cold War.

A remark on the first item, the vulnerability for attacks with known plaintext: The common ISO character set for texts has a systematic weakness. The 8-bit codes of the lower-case letters a..z all start with 011, of the upper-case letters A..Z, with 010. A supposed sequence of six lower-case letters (no matter which) reveals 6*3 = 18 key bits.

[By the way the appearance of many zeroes in the leading bits of the bytes is an important identifying feature of texts in many European languages.]

In other words: We cannot prevent the attacker from getting or guessing a good portion of the plaintext. Thus the security against an attack with known plaintext is a fundamental requirement for an XOR cipher, even more than for any other cryptographic procedure.

Cryptographic Security of Random Generators

This being said the crucial question for a pseudorandom sequence, or for the pseudorandom generator producing it, is:

Is it possible to determine some more bits from a (maybe fragmented) chunk of the sequence?

The answer for the »classic« pseudorandom generators used in statistical applications or simulations will be YES. But we'll also learn about pseudorandom generators that—supposedly—are cryptographically secure in this sense.