Stream Ciphers Part One (Boneh)
As presented in Cryptography: Week One
Ciphers
A cipher is defined over a triple:
The keyspace, the set of all possible keys \(K\)
The set of all possible messages \(M\)
The set of all possible cipher texts \(C\)
The cipher itself is a pair of efficient algorithms (E,D) where:
\[E: K \times M \rightarrow C\]
\[D: K \times C \rightarrow M\]
The requirement is that they satisfy the correctness property:
\[\forall m \in M, k \in K: D(k, E(k,m)) = m\]
\(E\) is often a randomized algorithm, \(D\) is always deterministic.
The One Time Pad
Designed by Vernam in 1917. First example of a secure cipher.
\[M = C = \{0,1\}^n\]
The keyspace is the same as the message space.
The key is a random bit string as long as the message.
The cipher text is the XOR of the key and the message:
\[ c := E(k,m) = k \oplus m\]
To decrypt, I take the XOR of the cipher text and the same key.
Note that if you have the message and the cipher text you can recover the key, since \(k = m \xor c\)
This is very fast from a performance perspective - it’s just an xor operation.
But long keys (as long as plain text), which makes it difficult to use in practice.
If Alice has to send a key to Bob that’s as long as the message, and has a way to do that securely, she might as well send the message instead.
Is One Time Pad secure? To understand this we need to get into information theory. Shannon was the first to analyse this rigorously.
If all you get to see is the cipher text, it should reveal no information about the plain text.
A cipher has perfect secrecy if:
\(\forall m_0, m_1 \in M\) where the messages have the same length
and \(\forall c \in C\) \(Pr[E(k,m_o) = c] = Pr[E(k,m_1) = c]\).
Where k is uniform in the keyspace.
So if I’m an attacker and I intercept the cypher text, the probability that it encrypts any two messages is the same.
Most powerful adversary learns nothing about the plain text from the cypher text. No cyphertext only attack on a cipher with perfect secrecy (other attacks may be possible).
Does OTP have perfect secrecy? Yes.
\[\forall m,c: Pr[E(k,m) = c] = \frac{|\{k \in K | E(k,m)=C\}|}{|K|}\]
If the numerator is a constant (ie any constant value) then the cipher has perfect secrecy.
For OTP there is only one key that can map a message to a given cipher text. So OTP has perfect secrecy.
But there are other attacks possible, even though it has perfect secrecy.
Shannon unfortunately proved that to have perfect secrecy the length of the key must be at least as long as the message.
But given the issues with key length being as long as the message, it means practical ciphers can’t have perfect secrecy.
Stream Ciphers and Pseudo-Random Generators
A stream cipher makes a OTP more practical.
The main idea - take an OTP and replace the random key with a pseudorandom one.
What is a pseudo-random generator (PRG)?
A PRG is a function \(G\) which takes a seed from the seed space \(\{0,1\}^s\) and maps it into a larger string \(\{0,1\}^n\) with the property that n must be much larger than s.
The function \(G\) should be efficiently computable by a deterministic algorithm. The output should look random.
How do we build a stream cipher? We use the generator to take a seed (the key) and expand it into a larger sequence, the length of the message. We then XOR that generated sequence with the message, and that gives us the cipher text.
So:
\[C = E(k,m) := m \oplus G(k)\]
\[ D(k,c) := c \oplus G(k)\]
Note that this doesn’t have perfect secrecy, so a definition of security can’t be perfect secrecy.
The PRG must be unpredictable. What does that mean? Well if the PRG is predictable there exists some i where we can take the first i bits of the output of \(G(k)\) and compute the rest of the stream, given the key.
If the PRG is predictable in this way it is not secure. For example if the attacker is trying to decode HTTP requests, it knows the first bits that must be present. If the attacker could then decode the first bits of the sequence, and the PRG is predictable, it could decrypt the rest of the message.
a PRG is unpredictable if it is not predictable so for any i there is no efficient adversarial algorithm that can predict i+1.
So for example let’s say we have a PRG that maps a key to \(\{0,1\}^n\), such that the XOR of the output is always 1. Now we have a predictable PRG, since if i = n-1 we can predict with confidence the final bit - whatever makes the XOR 1.
Here are some weak PRGs that should not be used for crypto:
A linear congruential generator has three parameters \(a\) and \(b\), both integers, and \(p\), a prime.
\(r[0]\) is the seed of the generator. You then generate \(r[i] \leftarrow a \cdot r[i-1] + b \mod p\)
This has good statistical properties, but it is a very easy generator to predict, so should never be used.
A closely related generator is glibc random() Where \(r[i] \leftarrow \left( r[i-3] + r[i-31]\right) % 2^{32}\) output \(r[i] » 1\)
Never use built glibc function for crypto - doesn’t produce cryptographically secure random numbers.
Attacks on Stream Ciphers and the One Time Pad
Never use stream cipher key more than once - there is a two time pad attack.
If the same pad is used to encrypt more than one message it is insecure.
Let’s say two messages are encrypted by the same \(PRG(k)\) and the attacker gets both cipher texts.
The attacker then does the xor of the two cipher texts, which gives them \(m_1 \oplus m_2\).
English has enough redundancy that if you have the XOR of two messages, you can recover the two messages completely.
ASCII encoding has enough redundancy that it has the same property.
So if you use the same key twice, there is no security at all.
This is a very common mistake. EG in Project Venona - US intel broke Russian use of a stream cipher because they re-used the same pad.
More recent example - a client-server protocol that encrypted both client messages and server messages with the same key.
This is broken - for the reasons given above. Never use the same key to encrypt client and server messages. Have one key for C->S and another key for S->C.
The shared key k is a pair of keys \(k= \left(k_{s\rightarrow c}, k_{c\rightarrow s}\right)\)
Another example of the two time pad occurs with the 802.11b WEP protocol. WEP is the encryption layer in the protocol.
There are many mistakes in WEP. One is a two time pad vulnerability.
WEP took the shared key and prepended a value \(IV\) on each frame before XOR. The value of IV was incremented every frame so it changed.
But the space of IV was only 24 bits, which means it cycled every 16M frames.
And when it cycled, you have a 2 time pad.
Also on many 802.11 cards, if you power cycle the card, IV resets to 0.
They also didn’t randomize IV, it’s 1, 2, 3 etc. So the resulting keys are closely related to each other. The majority of the bits are the same.
The pseudorandom generator is not secure with so many bits shared. After a million frames you could recover the secret key. Now WEP offers no security at all, you can recover the key in just 40k frames.
A better construction - feed the seed through a PRG and use that stream to encrypt the frames.
Final example: disk encryption.
Let’s say we use a stream cypher to encode blocks of a file on disk. If a small portion of the file is modified, and the same pad is used then the attacker can see which part of the file was changed. The attacker should’t see that information. So we need a different way of encrypting data on disk. You want it so that a small change in the file will completely change the encoded form.
So don’t use stream ciphers for disk encryption.
So to defend against two time pad attack:
Never use stream cipher key more than once.
Network traffic - negotiate new key for every session (eg TLS)
Disk encryption - don’t use a stream cipher.
No Integrity attack
The other issue with stream ciphers is that they provide no integrity at all. All they do is provide confidentiality, but no integrity.
And it’s easy to modify cipher texts and have known impact on the plain text. OTP is malleable
Let’s say that the attacker modifies the cipher text by XOR ing it with a value \(p\)
Now when it’s decrypted we get \(m \oplus p\). We have a very specific effect. The modifications are undetected and have predictable effect.
This allows eg, modifying an email from header.
We’ll have to add something to the stream cipher to get us integrity.