Questions
I'm just a bit confused about the nonce/IV in AES-CTR ... it seems the suggested way to go is have a 64bit random nonce, and use the last 64bits as the counter, "starting at 0".
No, that's just one way of creating a counter block.
Due to the birthday bound you would have about $2^{16}$ messages to have a chance of $1 \over 2^{48}$ that the nonce repeats. Or $2^{32}$ messages with a chance of $1 \over 2^{32}$. Your message size would be $2^{64}$ blocks.
I'm just wondering why not PRNG initialize all 128bits? Still using a 'static' 64bit nonce and still with the least significant 64bits as the counter, but "IV"'d (set to a non-zero value). Am i missing something?
You're not missing something, that's just another way of doing things.
But this requires the user to generate 128 bits of randomness, and random numbers may not come that cheap - depending on the random number generator used. It would however be tricky to exactly define how many messages at what size (no known bounds), and you'd have to store the initial counter value to detect an overflow (to regenerate keys go into an error condition).
Your scheme could be useful to send many smaller messages in a system that cannot keep state such as a counter for the nonce.
And in this example (https://www.rfc-editor.org/rfc/rfc3686) they clearly have a distinction with 1) a 32bit nonce, 2) a 64bit IV, and 3) a 32bit counter. In essence don't the nonce and IV essentially combine to form just one random use-only-once value? (ie. couldn't they just say "a 96bit nonce"?)
No, if you look at the definition you see that:
The encryptor can generate the IV in any manner that ensures uniqueness.
Common approaches to IV generation include incrementing a counter for
each packet and linear feedback shift registers (LFSRs).
So the IV in the IPsec protocol is there for a different reason than the nonce, which is just there to prevent precomputation attacks (see below).
The IV does not need to be random, which allows for efficient calculation of the counter and a larger message space of $2^{64}$ messages if a counter is used.
Also can the nonce be stored in plaintext alongside the ciphertext, or is it normally stored in some secured fashion, and if so how?
The nonce in IPsec is a random nonce, so it must be stored alongside the ciphertext (or at least linked to the ciphertext somehow, keeping it with the ciphertext is the most common method). It can be kept in plaintext and does not need to be secured.
IPsec case study
In the case of IPsec, the example in the question, the full counter block is defined using a specific scheme:
Each PT block is XORed with a block of the key stream to generate the
ciphertext, CT. The AES encryption of each counter block results in
128 bits of key stream. The most significant 96 bits of the counter
block are set to the nonce value, which is 32 bits, followed by the
per-packet IV value, which is 64 bits. The least significant 32 bits
of the counter block are initially set to one. This counter value is
incremented by one to generate subsequent counter blocks, each
resulting in another 128 bits of key stream. The encryption of n
plaintext blocks can be summarized as:
CTRBLK := NONCE || IV || ONE
FOR i := 1 to n-1 DO
CT[i] := PT[i] XOR AES(CTRBLK)
CTRBLK := CTRBLK + 1
END
CT[n] := PT[n] XOR TRUNC(AES(CTRBLK))
So IPSec allows $2^{64}$ packets to be encrypted if the sequence number is used for the IV, and it allows $2^{32} - 1$ counter for a maximum packet size of over 68GB (1 GB = 10 ^ 9 bytes). Fresh keys are required to be generated whenever the IPsec is restarted or after the encryption of $2^{64}$ packets. It is important to notice that these sizes are not influenced by the nonce.
The nonce is just there to prevent precomputation attacks against the key. This can be found in the security rationale, chapter 7:
There are fairly generic precomputation attacks against all block
cipher modes that allow a meet-in-the-middle attack against the key.
These attacks require the creation and searching of huge tables of
ciphertext associated with known plaintext and known keys. Assuming
that the memory and processor resources are available for a
precomputation attack, then the theoretical strength of AES-CTR (and
any other block cipher mode) is limited to 2^(n/2) bits, where n is
the number of bits in the key. The use of long keys is the best
countermeasure to precomputation attacks. Therefore, implementations
that employ 128-bit AES keys should take precautions to make the
precomputation attacks more difficult. The unpredictable nonce value
in the counter block significantly increases the size of the table
that the attacker must compute to mount a successful attack.
So the IPsec has been defined in such a way that it requires a relatively small amount of randomness.
It provides clear bounds on the number of packets (messages) and packet size.
Finally it allows easy detection of overflow so that implementations can go into an error condition rather than to repeat a nonce, destroying confidentiality of the data in the packets.
Although the inclusion of a nonce to prevent precomputation attacks is probably superfluous (due to the large key sizes offered by AES) it may also offer some protection against implementations for which the generation of the IV is faulty.
Note that the CTR spec of IPsec does have its faults:
- The name IV is generally used to indicate the initial counter block within cryptographic API's, which is confusing.
- It says that "The same IV and key combination MUST NOT be used more than once.", but it should specify that this is specific to the IPsec packets, not the counter blocks.
- It doesn't give any security hints in case the IV is generated by an LFSR (pseudo random value).
"IV"'dmeans. $\;$ $\endgroup$