Notes - Computer Security MT24, RC4

Formally, a stream cipher is defined like so:

• Definitions
  • A hidden state from a set of possible states $s \in \mathcal S$
  • An initialisation function $I: \mathcal K \to \mathcal S$ which constructs an initial state from a key
  • An update function $U : \mathcal S \to \mathcal S$ which updates the state
  • An output function $f : \mathcal S \to \Sigma$ where $\Sigma$ is the alphabet for the stream cipher
• Operation
  • Every time the output function is called to request a new symbol from the stream, the state is updated

In this context, @define how RC4 works.

Formally, a stream cipher is defined like so:

• Definitions
  • A hidden state from a set of possible states $s \in \mathcal S$
  • An initialisation function $I: \mathcal K \to \mathcal S$ which constructs an initial state from a key
  • An update function $U : \mathcal S \to \mathcal S$ which updates the state
  • An output function $f : \mathcal S \to \Sigma$ where $\Sigma$ is the alphabet for the stream cipher
• Operation
  • Every time the output function is called to request a new symbol from the stream, the state is updated

In this context, RC4 works like so:

• States $\mathcal S$: Tuples $\langle \pi, x, y \rangle$ where $\pi \in S _ {256}$, a permutation of $0, \ldots, 255$.
• Initialisation $I : \mathcal K \to \mathcal S$: Converts a 256 byte key into an initial permutation
• Update $U : \mathcal S \to \mathcal S$: $\langle \pi, x, y \rangle \mapsto \langle \pi’, x’, y’ \rangle$ where $x’ = x+1$, $y’ = y + \pi(x)$ and $\pi’$ is obtained by swapping $\pi(x’)$ and $\pi(y’)$ (i.e. $\pi’(x’) = \pi(y’)$, and vice versa)
• Output $f : \mathcal S \to \Sigma$: $f(\pi, x, y) = \pi(\pi(x) + \pi(y))$.

where all addition is done modulo 256.

What is the biggest problem with RC4?