2
$\begingroup$

Is using zero IVs with AES-CBC safe, if chosen-plaintext attack (CPA) is not possible and ciphertext indistinguishability is not an issue?

Practical example:

Alice operates an online service that stores user data on a cloud-based database. Alice is worried about the possibility of someone making off with the database, so wants to encrypt certain data to ensure recovery in that eventuality is impossible.

Alice is mainly concerned about data that are sensitive in their own right, such as those that identify an individual, or are tokens such as CC numbers.

Examples are:

  • Social security numbers
  • Addresses of residence
  • Phone numbers
  • Credit card numbers

Alice knows chosen-plaintext attacks are a concern, so uses a per-user key to prevent an attacker from loading the database with known-plaintexts.

However, Alice thinks ciphertext indistinguishability is a non-issue because knowing two ciphertexts equal doesn't usually lead to knowing the actual plaintext.


Is Alice safe in assuming data benefits from this kind of encryption and is secure from cryptography? (i.e. Wholesale data breach.)

One problem I can think of is:

  • If a user's phone number and credit card number are coincidentally identical, attacker can gleam this information from the encrypted database. They then only need to obtain the former to also get the latter.
  • If the first 16 bytes of the user's address is somehow identical to their social security number, again, the attacker can determine this from the encrypted database.

Are there any other problems?

Furthermore, is using AES-CBC this way any safer than using AES-ECB?

$\endgroup$
  • $\begingroup$ What is the performance constraint that prevents you from just using a full AEAD without such sharp edges? What are you trying to optimize by cutting these corners? $\endgroup$ – Squeamish Ossifrage Apr 5 '18 at 1:51
  • $\begingroup$ @SqueamishOssifrage Yeah, customizing basic security constructs never end well, is your point I guess. One rationale for someone seeking an answer if there's an existing system already implemented in the manner described with loads of data in the database. The constraint then is migration cost versus need. Another motivation could be pure implementation simplicity by doing away with IV storage / MAC calculation+storage and/or nonce (i.e. CTR) management. If theory permitting, less seems to be a good thing. $\endgroup$ – antak Apr 5 '18 at 2:31
  • $\begingroup$ Upon re-use of a (IV,key) pair, CBC leaks how long the common prefix between messages is (at block-level granularity). This is the best guarantee you'll get from a "classical" mode. There are more modern modes (all of which are authenticated and thus need tag storage) which only leak equality of messages upon a (IV,Key) re-use. $\endgroup$ – SEJPM Apr 5 '18 at 8:09
  • $\begingroup$ @antak Here's another cost: Spending the time to navigate and analyze the space of variants on standard authenticated encryption choices. If you haven't yet even identified what your operational costs are, you should consider whether that research and development cost on your part is worth them—and whether you spending time prematurely optimizing an application that you have yet to deliver! $\endgroup$ – Squeamish Ossifrage Apr 7 '18 at 4:50
  • $\begingroup$ @SEJPM There are more modern modes (which are authenticated) which only leak equality of messages upon a (IV,Key) re-use: That's kinda what I'm looking for. Which modes are those? $\endgroup$ – antak Apr 19 '18 at 0:16
2
$\begingroup$

Furthermore, is using AES-CBC this way any safer than using AES-ECB?

Yes, using CBC mode is (almost?) always safer than using ECB mode.

Is using zero IVs with AES-CBC safe[...]?

No it is not safe, because if you re-use a key with that construction you will leak the common prefix between messages, at block granularity. That is if you have three messages encrypted with CBC with the same IV and key $m=A\parallel B\parallel C\parallel G$ and $m'=A\parallel B\parallel D\parallel G$ and $m''=A\parallel E\parallel F$, with $A,B,C,D,E,F,G$ being 16-byte blocks, you can tell that $m'',m'$ and $m$ share the first block in common and you can tell that $m'$ and $m$ share the first two blocks in common, of course you don't actually directly learn the value of these shared blocks.

Note that either changing the key or the IV for each message fixes the above problem.

There are more modern modes (which are authenticated) which only leak equality of messages upon a (IV,Key) re-use: That's kinda what I'm looking for. Which modes are those?

These modes are called nonce-misuse resistant authenticated encryption modes (nmrAE). The two standard suggestions for this are AES-SIV and AES-GCM-SIV or AES-PMAC-SIV, both of which will offer standard authenticated encryption security if you use different (IV,Key) pairs with each message and will both offer (some) security if such a pair is re-used and of course they offer authentication as well and only leak equality of the underlying messages upon a re-use.

$\endgroup$
  • $\begingroup$ Interesting.. Just to note, these modes work by calculating a MAC of the plaintext and using that as the IV in AES-CTR so one needs two keys (or a longer key, if it may), one for the encryption itself and one for MAC. Also, the resulting IV ends up being the tag from MAC so storing that single item along with the ciphertext serves both the IV and authentication tag needed during decryption. (I found this site easy to follow: github.com/miscreant/miscreant/wiki/AES-SIV) $\endgroup$ – antak Apr 23 '18 at 4:29

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.