Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Lets say there is a piece of software that uses AES CTR to encrypt different messages using the same key but with slightly different IVs

So for example, a 16 byte IV, the 2nd 8 bytes are always the same, but the 1st 8 bytes are random.

How insecure is this?

I know that you shouldn't use the same IV and key. But do similar IVs have the same vulnerability or a different way to attack them?

share|improve this question

3 Answers 3

up vote 10 down vote accepted

As the name suggests, CTR mode works by encrypting a counter (that gets incremented with each 16-byte block) to generate a stream of random bits. That bit stream is then XOR'ed with the plaintext to create the ciphertext. The IV provides the initial value for the counter.

CTR mode is secure as long as the probability of a counter value repeating is negligible. Therefore the scheme you describe is secure under two conditions:

  1. No message is longer 2^32 sixteen-byte blocks long. Since this works out to be 64GB, this assumption is probably safe. (I'm assuming the 32 IV bits that are the same each time are the bits that get incremented with each block.)
  2. The number of messages encrypted under a single key is small.

How small is small? Well, the birthday paradox says that if you encrypt 2^m messages, the probability that the random, 64-bit portion of the IV will repeat is at most $2^{2m}/2^{64}$. So if you encrypted 2^16 = 65536 messages, the probability of having a repeated counter is less than one in 2^32; i.e., less than 1 in roughly four billion. In most cases, this is an acceptable risk (although some may consider it high by cryptographic standards).

share|improve this answer

The answer above is good but I would suggest that a non equal split between the Random IV size and the size of the counter would be safer. An 8 byte counter enough for $2^{64}$ 16 byte blocks, which, to be very precise, is huge. Using a 5 byte counter, for example, would still allow you to encrypt files up to $2^{40} \times 16$ bytes or about 17,592 Gigabytes. This should be plenty for most applications.

Thus 11 bytes could be used to initialize the random IV. Using the same assumption as above of up to $2^{16}$ messages under one long term key, the probability of a collision is then 1 in 144,000,000,000,000,000 as opposed to one in 4 billion.

You could adjust the relative sizes of the counter and the random IV as per your requirements. E.g. for lots of small messages (<268 MB) a 3 byte counter and a 13 byte IV could work well. For a one in a trillion risk of a collision you could encrypt $4\times 10^{19}$ small messages.

The equation for finding the probability of a collision is:

$$P = 1 - \exp( -n^2 / 2m )$$

where

  • $P$ = probability of collision,
  • $n$ = number of messages,
  • $m$ = size of the IV space, e.g. $2^{64}$ if the IV is 8 bytes long,
  • $\exp$ = exponential,
  • $\ln$ = natural log

The equation below finds the maximum number of messages for a given value of P the risk of a collision:

$$n = \sqrt{ - 2m \ln(1 - P) }$$

share|improve this answer

CTR mode turns a block cipher into a synchronizable/seekable stream cipher. The IV in this case is a nonce (number used once), and in general practice for a 128-bit block cipher is 96-bits (12 bytes), leaving 32-bits (4 bytes) for the block counter.

How insecure is this?

Not at all, given the following VERY important considerations:

  1. The 2nd 8 bytes are also used for the block counter
  2. The first 8 bytes are never repeated under the same key

Therefore, if you are choosing the first 8 bytes randomly, you would need to keep track of them, as randomly being identical is possible. The best way is to increment the first 8 bytes on a per message basis, modulo 2^64

But do similar IVs have the same vulnerability or a different way to attack them?

As long as the underlying block cipher (in this case AES) behaves like a random permutation, then there is not a practical attack against CTR mode. The best attack is a known plaintext attack, where the output of the cipher can be recovered, and compared with the nonce/counter to recover the key. The workload of this attack for AES in the best case is over 2^96, with massive plaintext requirements, so it is not practical. Changing keys well before 2^64 blocks is common practice.

If you are especially concerned, you can split the nonce in half, and choose half randomly. This will assure that the input to the cipher is more dissimilar, while also preventing nonce reuse. The other option is to change the key more frequently, say after 2^16 blocks, which may be very practical or very impractical depending on application.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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