# Stream Ciphers

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2FDybdSXhtDrRoWUdAnwgQ%2F2023-09-16_11-36.png?alt=media&#x26;token=0dd4ed5a-ad6e-4027-af2c-2ddb02f6390d" alt=""><figcaption></figcaption></figure>

## A mixture of a keystream with the plaintext or ciphertext

* **Random** keystream (Vernam's one-time pad).
* **Pseudo-random** keystream (produced by a generator using a finite key).

### Reversible mixture function

* e.g. bitwise XOR
* C = P ^ ks, P = C ^ ks

### Polyalphabetic cipher

* Each keystream symbol defines an alphabet.

Keystream may be infinite but with a finite period.

* The period depends on the generator.

Practical security issues.

* Each **keystream** should be used only **once**!
  * Otherwise, the sum of cryptograms yields the sum of plaintexts.
    * C1 = P1 ^ Ks, C2 = P2 ^ Ks -> C1 ^ C2 = P1 ^ P2
* **Plaintext length** should be **smaller** than the **keystream period**.
  * Total keystream exposure under know/chosen plaintext attacks.
  * Keystream cycles help the cryptanalysts know plaintext samples.
* Integrity control is mandatory.
  * No diffusion! (only confusion).
  * Chiphertexts can easily be changed deterministically.

## Lorenz (Tunny)

* 12-Rotor stream cipher
  * Used by the German high command during WWII
  * Implements a stream cipher.
    * Each 5-bit character is mixed with 5 keystreams.
* Operation
  * 5 regularly stepped (x) wheels.
  * 5 irregularly stepped (y) wheels.
    * All or no stepping
  * 2 motor wheels.
    * For stepping the y wheels.
  * The number of steps on all wheels is relatively prime.

### Cryptanalysis of Tunny in Bletchley Parl

They didn't know Lorenz's internal structure.

* They observed one only at the end of the war.
* They knew about them because they could get 5-bit encrypted transmissions.
  * Using the 32-symbol Baudot code instead of Morse code.

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2FXjbnLeudwm3PYV6w10QU%2F2023-09-16_11-51.png?alt=media&#x26;token=612aa423-0ea7-435e-81e4-3dd2929757de" alt=""><figcaption></figcaption></figure>

#### The mistake (August 30, 1941)

A german operator had a long message (\~4,000) to send.

* He set up Lorenz and sent a 12-letter indicator (wheel setup) to the receiver.
* After \~4,000 characters had been keyed, by hand, the receiver said "send it again".

The operator resets the machine to the same initial setup.

* Same keystream! Absolutely forbidden!

The sender began to key in the message again (by hand).

* But he typed a slightly different message!

C = M ^ Ks

C'= M' ^ Ks -> M' = C ^ C' ^ M -> text variations.

Know parts of the initial text M reveal the variations, M'.

#### Breakthrough

Messages began with SPRUCHNUMBER - "msg number"

* The first time the operator typed **S P R U C H N U M M E R**.
* The second time he typed **S P R U C H N R**
* Thus, immediately following the **N** the two texts were different!

John Tiltman at Bletchley Park was able to fully decrypt both messages (called _Depths_) using an addictive combination of them.

* The 2nd message was \~500 characters shorter than the first one.
* Tiltman managed to discover the correct message for the 1st ciphertext.

They got for the 1st time in a long stretch of the Lorenz keystream.

* They did not know how the machine did it, but they knew that this was what it was generating!

#### Colossus

The cipher structure was determined from the keystream.

* But deciphering it required knowing the initial position of rotors.

Germans started using numbers for the initial wheels' state.

* Bill Tutte invented the double-delta method for finding that state.
* The Colossus was built to apply the double-data method.

Colossus

* Design started in March 1943.
* The 1,500-valve Colossus Mark 1 was operational in January 1944.
* Colossus reduced the time to break Lorenz from weeks to hours.
