I will write this question using a database example, but please note this detail may be irrelevant.

Let's say I have data belonging to N clients stored in a single column of a database table. Each client has their own AES key used to encrypt/decrypt their own data.

In this setting, I have the understanding that if someone gets a copy of all values in the database, then brute-force attacks would actually become easier than if I had used just one single key to encrypt the entire column instead of this one-key-per-client approach.

If I had used just a single key for the entire data, the attacker would need to find that one key that would correctly decrypt all of the data. However, if one different key has been used to encrypt each of those N partitions, then time for finding at least one key that would decrypt at least one of these partitions would be reduced by a factor of N, since each candidate key being tested during a brute-force attack could match any of the N keys instead of having to match just one.

In this situation, it seems all that I have done was to reduce the search surface for finding a valid key from X to X/N.

Edited for clarification - All the above mentioned, my question is: Is having a single column with data encrypted according to different keys could possibly make brute-forcing the data easier?

If yes, what would be a suitable approach to overcome this, i.e., for encrypting different groups of data using separate keys without reducing the difficulty of brute-forcing individual keys?

  • $\begingroup$ It makes no sense. 1) For smb. who gets a copy of the data it will be impossible to brute-force even a single key, thus your approach makes no sense. 2) For smb. who attacks your software that works with decrypted data (database application itself or client application), there will be no difference because the data at that moment are already decrypted, thus your approach again makes no sense. $\endgroup$
    – mentallurg
    Dec 27 '20 at 15:03
  • $\begingroup$ You mean, the approach of having separate keys per client does not make sense, or the impression that this will make brute-forcing easier doesn't make sense? Sorry I think I badly worded the question $\endgroup$ Dec 27 '20 at 15:18
  • $\begingroup$ Think what attack are you going to protect your data from. A) From brute-forcing? If you trust AES, then you know that it would need 2^128 ~= 10^38 = 100 000 000 000 000 000 000 000 000 000 000 000 000 operations. Even the computer power of the whole planet during millions of years will not be sufficient for single key. Thus having more than one key adds complexity but does not add security. $\endgroup$
    – mentallurg
    Dec 27 '20 at 15:55
  • $\begingroup$ B) Don't you trust AES? Then it makes no sense to use it at all. If you believe AES is broken, then you should accept that for an attacker there is no difference to break 1 key or to break 1 000 000 keys. C) If you trust AES, but you want to protect from stealing the keys? For an attacker there would be no difference between stealing 1 key or 1 000 000 keys. Thus in any scenario I see no reason in having more than one key. $\endgroup$
    – mentallurg
    Dec 27 '20 at 15:55
  • $\begingroup$ Thanks, I see, brute-forcing would not be the concern here. But talking about attacks, what about D) Certain fields need to be equality-searchable within a client (but not across clients), so some fields would be using deterministic encryption. If an attacker hacks/impersonates one of the clients, enters arbitrary values in the database through the application, then obtains a copy of the database data, even though the database data would be encrypted, wouldn't he/she be able to know where those values also happen in the data of other clients? Wouldn't separate keys help mitigate this issue? $\endgroup$ Dec 27 '20 at 16:39

Your Answer

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

Browse other questions tagged or ask your own question.