Vernam ciphers are easy to break


2a. Basic cryptographic techniques

Bitstream encryption


The principle of bitstream encryption

(XOR with (quasi) aperiodic keystream.)

example

S ore --------- --------- --------- --------- --------- b: 0101 0011 0110 0101 0110 1000 0111 0010 0010 0000 ... k: 1001 1000 1101 1101 0010 1111 1000 1001 1001 0101 ... ----------------------- ---------------------------------- c: 1100 1011 1011 1000 0100 0111 1111 1011 1011 0101 ...

Bitstream encryption: advantages and disadvantages

+Very fast, suitable for large amounts of data (e.g. image transmission) [provided the key is already available].
+Easy to implement, decryption and encryption are the same function.
-The quality of the key sequence is very critical (see below).
-Exchange of known plain text is trivial.

Creative use to bypass the key deposit:Every ciphertext can be decrypted to any plain text (of the same length) with a suitable key.


The security of bitstream encryption

  • In theory absolutely certain if the keystream is "real" random (One time pad [OTP FAQ]).
  • Completely unsure when the keystream consists of a short, repeated sequence.
  • Unsure when the keystream is used multiple times.
  • Unsureif the keystream is generated by a standard random number generator.
  • For sure, if the keystream is generated by a cryptographically secure ("perfect") random generator.

The one-time pad (»endless worm«)

  • The keystream consists of a genuinely random, never repeated bit sequence [Vernam 1917].
    • The key is as long as the actual message (!)
    • Must be stored in two places.
    • So key exchange and safekeeping is difficult.
  • Only suitable for two-way communication, not for multi-party communication.
  • Security only in terms of confidentiality, not in terms of integrity.
Overall usefulness very narrowly limited.

The picture shows a "real" one-time pad that was used by Soviet spies in the Cold War. This encryption was occasionally broken by the NSA in the "Venona Project" because key parts were repeatedly used.


Bitstream encryption - multiple use of the key

Plain textXORkey=Ciphertext

mXORk=c
m 'XORk=c '

m XOR m '=c XOR c '

The attacker sees c and c ', so can c XOR c ' and thus also m XOR m ' to calculate. This is the sum of two plain texts and can easily be broken using methods of classic cryptanalysis (albeit not entirely trivial).


Current examples of bitstream ciphers

  • Bit block ciphers in CFB, OFB or CTR mode.
  • RC4 in the SSL protocol, which (occasionally) encrypts the client-server communication in the WWW.
  • AES-CTR in WinZip.
  • Algorithm A5 for mobile telephony (between mobile phone and base station).
  • Algorithm E0 seemingly secure in the Bluetooth protocol for wireless data transmission.

Lecture on data protection and data security
Author: Klaus Pommerening, March 31, 1999; last change: June 8, 2004
email to
.