Security of AES counter mode vs. CBC mode

Evgeni Vaknin 09/05/2017. 1 answers, 401 views
aes cbc ctr nonce

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

1 Answers


Patrick K 07/31/2017.

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.

5 comments
Evgeni Vaknin 07/31/2017
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?
1 Patrick K 07/31/2017
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}$.
Evgeni Vaknin 07/31/2017
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)
Evgeni Vaknin 07/31/2017
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)
1 Patrick K 08/01/2017
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)

HighResolutionMusic.com - Download Hi-Res Songs

1 (G)I-DLE

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
2 The Chainsmokers

Beach House flac

The Chainsmokers. 2018. Writer: Andrew Taggart.
3 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
4 Nicki Minaj

No Candle No Light flac

Nicki Minaj. 2018. Writer: Denisia “Blu June” Andrews;Kathryn Ostenberg;Brittany "Chi" Coney;Brian Lee;TJ Routon;Tushar Apte;ZAYN;Nicki Minaj.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
7 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
8 BTS

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
9 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
10 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
11 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
12 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.
13 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
14 Anne-Marie

Rewrite The Stars flac

Anne-Marie. 2018. Writer: Benj Pasek;Justin Paul.
15 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
16 Imagine Dragons

Machine flac

Imagine Dragons. 2018. Writer: Wayne Sermon;Daniel Platzman;Dan Reynolds;Ben McKee;Alex Da Kid.
17 Little Mix

The Cure flac

Little Mix. 2018.
18 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
19 Rita Ora

Velvet Rope flac

Rita Ora. 2018.
20 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.

Related questions

Hot questions

Language

Popular Tags