Stream Ciphers
Last updated
Last updated
Random keystream (Vernam's one-time pad).
Pseudo-random keystream (produced by a generator using a finite key).
e.g. bitwise XOR
C = P ^ ks, P = C ^ ks
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.
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.
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.
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'.
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!
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.
