5
$\begingroup$

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".

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?

And in this example (https://tools.ietf.org/html/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"?)

Also can the nonce be stored in plaintext alongside the ciphertext, or is it normally stored in some secured fashion, and if so how? Thanks

$\endgroup$
  • $\begingroup$ Your question is missing a description of what "IV"'d means. $\;$ $\endgroup$ – user991 Jul 18 '15 at 7:36
  • $\begingroup$ Ricky: "IV'd" as in given an IV... eg not set to zero $\endgroup$ – David Jul 18 '15 at 8:00
  • 2
    $\begingroup$ As a trivial example, if you use an incrementing counter for your IV, and that counter is further incremented for each "block" (as defined by CTR mode), the second block of your first plaintext and the first block of your second plaintext will use the same effective IV. Likewise with the third block of your first plaintext, the second block of your second plaintext, and the first block of your third plaintext (and so on). $\endgroup$ – Stephen Touset Jul 18 '15 at 20:29
3
$\begingroup$

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://tools.ietf.org/html/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).
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.