Difference between a nonce and IV 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?
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.