Difference between a nonce and IV

Question

I know the generic difference between a nonce and an IV. I am specifically looking for a clarification on these terms as used in the "Evaluation of Some Blockcipher Modes of Operation" by Phil Rogaway. In that when describing the block cipher modes for e.g. CBC he says the following (table in page 5) --

Confidentiality is not achieved if the IV is merely a nonce, nor if it is a nonce enciphered under the same key used by the scheme, as the standard incorrectly suggests to do.

I don't understand the difference between the IV and nonce in this context. If I choose the nonce randomly won't it be the same as an IV? What am I missing here?

Answer 1

With CBC mode the initialization vector is referred to as IV, because it is not nonce. There are ways to construct nonce so that it does not meet the needs of CBC mode. Random IV is one generation choice which is usually fine. Nonce can also be a counter, which is not ok here.

Definitions

Nonce means number used once. IV means initialization vector.

CBC mode security

For security of CBC mode (SemCPA in this case), it is necessary that the IV is unpredictable, prior use of IV. However, once IV is used, the value does not need to be kept secret.

One way to generate IV is to generate random numbers. For the CBC IV size (128 bits) it is extremely rare to get IV value which is same than one of the previously used *IV*s. In addition, random numbers are by definition unpredictable.

Such IV values are nonce as well, as the numbers are used only once (with high probability unless the number of encryptions with the same key is very large).

However, there are also other ways to generate nonce. Once of common ways to generate nonce is to use increasing numbers (increment with 1 or use linear feedback shift register). Such approach fullfils the necessary requirements for nonce, but fails to meet needs (unpredictability) of IV for CBC mode. (In Rogaway's paper, "Random IV" is used for Random IV generation and "nonce IV" for these other ways of generating nonce.)

The Rogaway's paper is concerned investigating the security provided by AES usual block cipher modes of operation if they have been implemented as defined in papers by NIST. NIST SP 800-38A is concerned with CBC, CFB, OFB and ECB modes. NIST SP 800-38A (Appendix C) suggests two ways to generate IV for CBC mode, Random IV and nonce-based scheme using forward cipher function ($C = E_K^R(P)$) to generate IVs.

This paper by Rogaway points out that the nonce-based scheme using forward cipher function does not provide intended security.

Random IV

When using Random IV's, remember that if you generate $2^{64}$ IV's, there is around 50% possibility that not all IVs are unique. For this reason, you need to make sure that the amount of encryptions with single key is not too large.

And... If the random number generator is not a good one, then unpredictability can be violated. So generally you should make sure that a cryptographically secure RNG is used for IV's.

Answer 2

There is not much difference and in practice the terms are often used to mean the same thing. In this context however the Nonce does not have to keep to the random properties that the IV has. As explained in the paper:

A probabilistic encryption scheme $C = \varepsilon^R_K (P)$ is an IV-based encryption scheme, syntactically, but we are suggesting that, in the security definition, the IV will be regarded as a random value $R$. A nonce-based encryption scheme $C = \varepsilon^N_K (P)$ is an IV-based encryption scheme, syntactically, but we are suggesting that, in the security definition, the IV will be regarded as a nonce $N$ : a value that is used at most once for a given key.

So yes, if you choose the nonce randomly then CBC and the #CBC defined in the paper are identical.

Note that the attack on #CBC in the paper shows that the NIST requirements for #CBC are not met (SemCPA security is not achieved). In practice it may be the case that the cipher is safe within a particular protocol, for instance when CPA (choosen plaintext attacks) don't apply.

Answer 3

An IV is an intial vector, which means it is an initial vector of data used when you start a chaining mode. It has no interesting properties of its own.

If the IV is a nonce, that means it is a number used once (eg CTR mode). This means that (by changing the IV) we ensure that the process is never run on exactly the same input data (even if messages are repeated then the two IVs will be different). The easiest way to implement a nonce is through a counter - just make sure it never overflows and you can be sure the IVs were all different.

Often, we require that the IV is unpredictable (eg CBC mode). This means that an adversary should not be able to predict what the IV would be in advance. This is implemented by choosing the IV at random (or as close to random as we can do in appropriate context).

If we use a random IV when we require a nonce, then (due to the birthday bound) after half the IV length we expect to get a collision. That is, we expect that if we randomly sample an $n$ bit IV, after $n/2$ values it is expect that we will have used two IVs that were identical. Conversely, if we use a nonce when an unpredictable IV is required then something similar occurs. If the nonce is provided by a counter then the IV is trivially predictable, since the adversary can increment the counter himself to find the next IV.