OFB or CTR mode without an IV

Question

I'm reading the SSL specs here.

The interesting thing seems to be that RC4 is not re-keyed with a new IV for each message. The stream cipher state is simply carried over to the next record. Why is this secure? Shouldn't messages be encrypted with different IVs? Honestly, this is one part I don't fully understand about IVs: each message needs a different IV, but what counts as a message? A full stream of records? One record?

The CBC modes do have different IVs for each block.

My question is, how about a stream ciphery mode of operation, like OFB or CTR? Do I need new IVs for each smallish record, or can I do what SSL does with RC4 and just carry over the cipher state? Is that in any way insecure? WEP seems to do the new-IV-per-packet thing, and that seems to have caused its downfall. Why?

Answer 1

The answer from owlstead and its comments covers WEP part quite nicely.

This answer concentrates on CTR and OFB.

Strictly speaking, CBC, CFB, CTR, and OFB modes always use IV or counter. I'm assuming that the question was more like is it possible to use CTR or OFB mode securely without transmitting IV. I.e. for instance, start at all zeroes IV/counter and increment the counter for each message. This appears to be possible and secure. (As long as you're careful enough to never reuse same counter+key combination.)

Details for selecting IV for CTR and OFB modes

The answer for IV(/nonce in CTR and OFB modes is found in document NIST SP 800-38A: Recommendation for Block Cipher Modes of Operation, which describes these modes. This document tells in Appendixes B and C various recommendations by NIST for choosing IV/counter for CBC, CFB, CTR and OFB. Long story short, for CTR and OFB modes, it is sufficient that IV/counter used is always unique for the same key, as long as it is also unique for each invocation of the encryption operation.

In other words, counter is ok for CTR and OFB. In OFB mode, it is not safe to use cipher text from a previous operation as IV, a practice that has been often used with e.g. CBC mode. The language of NIST specification may be misleading. There is evaluation of cipher modes of operation from Rogaway, which you may find easier to read and understand, and containing a lot of additional detail.

Answer 2

There is a number of ways how to generate the initialization vector (IV), and not all of them are secure for a particular mode of operation. The NIST recommendations are sometimes ambiguous and may lead to confusion. A comprehensive story of these issues has been recently told by Rogaway (see also excellent pictures there); let me summarize what should be said about CTR and OFB in the context of the IV generation (Sections 4.6, 4.7, 5.4).

First, by security I mean a rather strong model where the adversary selects a plaintext for the encryption and is then asked to tell apart a random string from the ciphertext. If the IV is random, it can not be chosen by the adversary; if it is a nonce, an adversary can choose it accordingly. If the probability of success is negligible up to huge amount of attempts with a fixed key, the mode is considered secure to chosen-plaintext attacks. This setting covers virtually all attacks that a good mode of operation that provides confidentiality (but not necessarily authenticity) should counteract.

Coming back to IVs, the OFB and CTR mode treat them differently even though they are somewhat stream-based. The IV in the OFB mode undergoes a number of encryptions; it can be easily proved secure if IV is random. However, a nonce-based OFB is generally insecure, as taking any previous ciphertext block as an IV destroys the security while being a good nonce (so the answer to one of your questions is definite "No"). A counter for the IV in OFB is fine and can be proved secure.

The CTR mode generates a keystream by encrypting an arithmetic progression starting with an IV. The best security is achieved when IV is selected such that no repetition in these values ever occurs; the NIST approach is good enough. A random IV is still fine, but not better; any previous ciphertext block should be fine and is likely to be secure, but it is unnecessary complication.

Answer 3

What a message is depends on the protocol. As long as the state within the stream cipher does not repeat, the stream cipher is safe.

The problem with WEP (in this regard) was that it choose a new IV/nonce for each packet, but that it was possible for an attacker to repeat the nonces. This was due to the 24 bit size of the nonce.