For AES-CBC to be CPA secure the IV that is used has to be randomly selected for each packet. If the IV is predictable than the encryption is not CPA secure. Is the same true for AES-CTR mode? that is, for AES-CTR mode the first counter must be random or it can be a nonce? Thanks
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
The requirement for the AES-CTR input blocks is, that they should be unique during the lifetime of a key. In most of the cases a random 96bit nonce is used with a 32bit counter that starts from 0. If the same input block for AES-CTR occurs twice, AES-CTR is not CPA secure any more. In this case, this can be due to a counter-overflow after $2^{32}$ blocks or due to colliding randomly chosen 96bit nonces (birthday paradox: 50% chance after $\sqrt{2^{96}}$ messages. Consider the following case:
Two distinct 1-Block messages $P$ and $P'$ are sent under the same key $K$ (that might be negotiated beforehand) and with the same nonce $N$. The attacker knows that the related cipher texts $C$ and $C'$ where calculated by XORing them with the keystream (which is based on the nonce and the counter):
$C = P \oplus E_K(N,0)$
$C' = P' \oplus E_K(N,0)$
Then the attacker can simply xor the cipher texts
$C\oplus C' = P \oplus E_K(N,0) \oplus P' \oplus E_K(N,0) = P \oplus P'$
and he obtains the ''distance'' between the two plain texts. Due to redundancies in the English language, he might be able to determine $P$ and $P'$.
This problem is also known as the "two-time-pad". Once the same keystream is XORed with the plaintext, we get into trouble. Therefore, it is important, that the input for the AES encryption is unique during the lifetime of a key. It does not have to be unpredictable, just unique.
-
$\begingroup$ by the statement "2^32 messages"I think you mean 2^32 blocks of 16 byte each in AES? if so, than 2^32 blocks time is 2^32*128 bits, which is in 10Gbps, about 1 minute...so each 1 minute a key exchange algorithm has to be executed in order to set up a new key and nonce? $\endgroup$ Commented Jul 31, 2017 at 8:25
-
1$\begingroup$ Yes you're right. I have edited the answer. If you have a static nonce, then you would need to do a key exchange every minute in this case. But since the nonce is usually changed with every message, you are limited to messages of a max length of $2^{32}\cdot128$ bits. The maximum number of messages that can be sent under a given key is limited by the birthday paradox. If the 96bit nonce is chosen uniformly at random for every message, the probability of a nonce collision is $\approx 0.5q^2/2^{96}$ for q messages. If you want this term to be at most 1%, your $q_{max} = 4\cdot10^{13}$. $\endgroup$ Commented Jul 31, 2017 at 10:48
-
$\begingroup$ What happens if I do not use random nonce, rather I use a random value for the nonce initial value and than increment it each packet? For instance, lets say each packets contains less than 256 AES blocks (128 bit each), and the counter for the AES-CTR is composed of nonce of 120 bits, that initialized randomly when key is exchanged, and than within the packet 8 bits counter is used to counts the 128 bit blocks. And each new packet, (continue in next comment) $\endgroup$ Commented Jul 31, 2017 at 16:27
-
$\begingroup$ I increment the nonce by 1, and clear the 8 bit counter. In this case, the birthday paradox is not relevant, as collision is impossible (assuming I'm replacing the key before the 120 bit counter of the nonce expired) $\endgroup$ Commented Jul 31, 2017 at 16:27
-
1$\begingroup$ Yes, if you somehow make sure that you never reuse the same (input-block, key) pair for the keystream-generation, then everything is fine. (of course assuming that the key is kept secret and is chosen uniformly from random) $\endgroup$ Commented Aug 1, 2017 at 7:03