# Replay Attack in Stream Cipher

If E() is a stream cipher and an attacker intercepts the message m that's being transmitted at time t, how can the attacker compose an encryption of the following for any value of t?

E(k,t || m)


context: An Unilateral Authentication using Time-stamp

The way a stream cipher works, traditionally, is that $E_k$ produces a pseudorandom bitstream (the keystream) based solely on the key $k$. The message is then encrypted by XORing the message with the keystream. This has a number of consequences, notably that if you know both the plaintext and ciphertext, it's trivial to compute the keystream (if $C=M\oplus K$, then $K=M\oplus C$). If you know the keystream, you can then encrypt messages of your choice up to the length of that keystream, even without the actual key.
For this method, it's actually far, far, far worse. The attacker doesn't even need m to do his attack; if you know the plaintext corresponding to some part of a ciphertext, you can then modify the ciphertext so that that part decrypts to whatever you want. For instance, if you know the first 32 bits are a timestamp and know the timestamp $t_1$ (so the message is $t_1||M$), you can then XOR the first 32 bits of the ciphertext with $t_2\oplus t_1$ to get a new ciphertext that decrypts to $t_2||M$.
The lesson is that stream ciphers don't hold up to active attack. That's OK; they're not meant to. To ensure that a ciphertext wasn't tampered with, you need a proper message authentication code like HMAC, which does verify that the person making the message had access to the key. The lesson for other uses of stream ciphers is that you want a message-specific initialization vector so that you don't have the same keystream on all messages encrypted with the same key; then the keystream is $E(k,IV)$, and the IV need not be secret (so you can just slap it on the front of the message). This isn't good to rely on for authentication, though; a MAC is what's made for message authentication.