notes/docs/lectures/cryptography/02_randomness.md

Stream Ciphers

Stream ciphers encrypt bits one at a time, for as long as necessary.

Stream ciphers using modulo 2 addition

Let x, y, s \in \{0,1\}

Encryption: e_{s_i} (x_i) = y_i \equiv x_i + s_i \space (mod\space 2)

Decryption: d_{s_i} (y_i) = x_i \equiv y_i + s_i \space (mod\space 2)

Why does mod 2 work for both encryption and decryption?

d_{s_i} (y_i) \equiv y_i + s_i \space (mod\space 2) \\
d_{s_i} (y_i) \equiv (x_i + s_i)+s_i \space (mod\space 2) \\
d_{s_i} (y_i) \equiv (x_i + 2s_i) \space (mod\space 2) \\
d_{s_i} (y_i) \equiv (x_i + 0\cdot s_i \space (mod\space 2) \\
d_{s_i} (y_i) \equiv x_i

Note: 2 % 2 is 0; it's like xor-ing twice.

Security of XOR

x_i	s_i	y_i
0	0	0
0	1	1
1	0	1
1	1	0

When y_i is 1, it could’ve been from the message or the key.

Randomness

The security of a stream cipher depends entirely on the nature of the key stream

• If the stream is truly random, the output is truly random.

True Randomness

• True randomness is impossible to recreate except by chance
  • coin flips
• Computer systems often use hardware sources for randomness
  • Thermal or other noise
  • Radioactive decay
  • Clock drift
  • Random timings of interrupts

Pseudo Randomness

• Generate a sequence of values based on a seed
• Usually the only requirement is statistical randomness

Linear Congruential Generator

C's rand() function is a PRNG

s_0 = 12345 \\
s_{i+1} \equiv 1103515245 \cdot s_i + 12345 \space (mod \space 2^{32})

Cryptographically Secure Pseudo Randomness

• Is a PRNG whose output is unpredictable
• Given n bits of key stream, can we predict the next bit x?

Pr[x=s_{n+1}] < 0.5 + \epsilon

Unconditional Security

A cryptosystem has unconditional security: it is unconditionally or information-theoretically secure if it cannot be broken, even with infinite computational resources.

Perfect Secrecy: The cipher-text should reveal no information about the plain text

\forall_{m_0, m_1} \in M where |m_0| = |m_1| and \forall_c \in C

Pr[E(k,m_0) = c] = Pr[E(k,m_1) = c]

The probability that m_0 encrypts to c is the same as the probability of m_1 also being encrypted to c

One Time Pad

• Key stream generated by a TRNG
• The key stream is known only to the communicating parties
• Every key stream but s_i is used only once

OTP has perfect Secrecy

Proof

\forall m, c : Pr[E(k,m)=c] = \frac{\{k\in K|E(k,m)=c\}}{|K|}

For every message, that encrypts to cipher text, the probability of m encrypting to c, is all the keys over all the messages

For OTP:

#\{k\in K| E(k, m) = c\} = 1

Because a key is only used once

because if E(k,m)=c then k=m \oplus c

\therefore Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c]

• Any plaintext is equally likely depending on the key
• This is an example where M = C-K\space (mod\space 26)

OTP is not practical:

• A 1GB file would need a 1GB key
• How are we transporting these keys & storing them
• If you ever reuse a key, the entire cipher is broken

Modern Stream Ciphers

• Modern stream ciphers use an initial seed key to generate an infinite pseudo-random keystream
• Reusing keys catastrophically breaks the encryption

M_1 \oplus K = C_1 \quad\quad M_2 \oplus K = C_2 \\
C_1 \oplus C_2 = (M_1 \oplus K) \oplus (M_2 \oplus K) \\
= (K \oplus K) \oplus M_1 \oplus M_2 \\
= 0 \oplus M_1 \oplus M_2 \\
= M_1 \oplus M_2 \\

Crib Dragging

This involves guessing M_1; this can be a common message such as an HTTP request.

This can be automated by checking M_1 over different parts of M_2.

• Stream ciphers use a nonce value to alter the keystream for a given key
• This allows us to create different key-streams for a given key

Number Used Once

• Numbers used once or nonces are vital for stream cipher security
• Instead of always using a unique key, the security requirement is you always use a unique (key + nonce) pair
• Nonces are not secret; they are public random seeds for a key stream

Could we use an LCG?

• LCG - Linear congruential generators
• Seed using some key, then
  • s_{i+1} \equiv A \cdot s_i + B \space (mod \space 2)
  • s_i, A, B are log_2m bits long
• This is trivial to break
  • Given known plaintext x_1, x_2, x_3
  • Calculate corresponding key s_1, s_2, s_3