Score:1

Crypto

decrypting full ciphertext of (AES CTR/GCM) based on partial knowledge of the cleartext

Tito

4/27/24, 9:38 AM

I have found myself in a position where I need to encrypt multiple objects (vCards) with AES Counter mode or Galois/Counter Mode using the same key. Now here is the problem the structure of the vCard always starts with predefined values i.e. here is an example from wikipedia

 BEGIN:VCARD
 VERSION:4.0
 FN:Simon Perreault
 N:Perreault;Simon;;;ing. jr,M.Sc.
 BDAY:--0203
 GENDER:M
 EMAIL;TYPE=work:[email protected]
 END:VCARD

basically, we always have the following data that is in the beginning of the object i.e.

BEGIN:VCARD
 VERSION:4.0
 FN:

and in the end, we always have

 END:VCARD

Now the problem is that the attacker will also know this information. That means he will definitely be able to partially decrypt those vCards. Imagine I need to encrypt hundreds of thousands of such vCards with one key. How to do this at all? Since it is assumed that the attacker will have access to the encrypted version but also he will also be able to know the type of the object i.e. that the ciphertext represents vCard.

My question is will the attacker be able to.

decrypt the full cipher text to plain/clear text
reverse engineer the encryption key

assuming the attacker has access to hundreds of thousands of such encrypted records(vCards) each one of them is encrypted with separate Nonce and counter and assuming that entropy used during the process was correct.

What are the risks in such a situation and what can be done here in order to protect the data. Does encryption makes sense in such a situation at all or is this idea doomed from the beginning?

I have done some research here in regard to what people are writing i.e

How to attack a classical cipher using known partial plaintext?

But those examples are referring only to one instance of the ciphertext. what happens when the attacker has access to hundred thousands of such instances all encrypted with separate Nonce/Coutners. The information about

a) what block cipher has been used
b) mode of information of that block cipher
c) nonce
d) counter

is public that means that the attacker has access to it. the only thing that is private in this situation is the key.

Addition 1 (27.04.23) , after the answer of Kodlu which answer i consider correct. It is not possible to do what Kodlu suggested since we have many more objects types i.e. messages, todos, calendar, etc. etc and doing that for each one of them is not feasible.

2 + 0

cryptanalysis

aes-gcm

Score:1

Crypto

kodlu

4/27/24, 10:37 AM

This is a high-level conceptual answer, addressing the common text between plaintexts issue arguing it can be managed

By Kerchoff's principles, a well designed cipher's security rests only with the key.

If the beginning and end are known and constant just don't encrypt those. They can be transmitted in the clear. Then you remove the ability of the attackers to make use of it.

So instead of encrypting

 BEGIN:VCARD
 VERSION:4.0
 FN:Simon Perreault
 N:Perreault;Simon;;;ing. jr,M.Sc.
 BDAY:--0203
 GENDER:M
 EMAIL;TYPE=work:[email protected]
 END:VCARD

Encrypt

 Simon Perreault
 N:Perreault;Simon;;;ing. jr,M.Sc.
 BDAY:--0203
 GENDER:M
 EMAIL;TYPE=work:[email protected]

with AES-GCM. Remove the constant prefix

 BEGIN:VCARD
 VERSION:4.0
 FN:

and suffix

 END:VCARD

After decryption you include the prefix and suffix to reconstruct the vcard.

As far as hundreds of thousands of plaintexts, that's of the order of $2^{20}$ (for a million) to $2^{24}$ for tens of millions so that should not be enough to give any attacker an advantage to extract the key. If it did, AES-GCM would be broken.

Note: The plaintexts are short, so have a look at some other answers discussing that aspect. One keyword to look for is "format preserving encryption", such as this one.

+ 2

Tito

4/27/24, 11:30 AM

kodlu, i will accept you answer , in fact i thought if that myself , and it is my fault that i did not mentioned what i am mentioning here that that i have multiple objects of different types it is not just the vcard there many more types including messages, calendar , todos, etc. etc. that always start with the same characters and end with those. Unfortunately it is not possible to remove the beginning and the end. I am more curious what an attacker can do if i can not remove the beginning and the end. What are your ideas on that topic ?

Tito

4/27/24, 11:43 AM

so will that mean that if i leave it like it is without removing the beginning and the end of the encryption hundreds of thousands of plaintext which are encrypted like that will still not reveal the private key ? Will the attacker be able to decrypt the rest of the objects ?

Score:1

Crypto

honzaik

4/27/24, 12:29 PM

AES-GCM is considered practically AEAD secure. AEAD security implies CCA2 security which implies CPA security. That means AES-GCM considered CCA2 (and CPA) secure.

If a cipher is CPA secure, that roughly means that even if attacker has access to large (NIST recommends to change key for AES-GCM after $2^{64}$ blocks https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf, page 26)

Moreover, as with most block cipher modes of operation, the security assurance of GCM degrades as more data is processed with a single key. Therefore, the total number of blocks of plaintext and AAD that are protected by invocations of the authenticated encryption function during the lifetime of the key should be limited. A reasonable limit for most applications would be $2^{64}$, consistent with the requirement on the number of invocations in Sec. 8.3.

number of pairs of (plaintext,ciphertext) encrypted under same key (but unique nonces!), then he still is not able to learn a single bit about the content. Note that this definition also includes your case. The attacker can have millions of encryptions of "AAAAA-{x}-CCCCC" where {x} is some changing variable but he would still not be able to learn anything about my variable {y} if he knowns the ciphertext of "AAAAA-{y}-CCCCC". Even if one of the million encryptions is an encryption of "AAAAA-{y}-CCCCC" the ciphertext is different (nonce is unique for every encryption) therefore he cannot detect it.

AES-CTR should be also resistant to this sort of attack. Attacker won't learn anything about the encrypted data just from the pairs but can alter encrypted data by simply flipping bits which can lead to potential decryption attacks (AEAD secure ciphers are immune to this). AES-CTR does not provide integrity/authenticity of the ciphertexts. If you are not space/speed constrained, it is always better to use authenticated encryption such as AES-GCM.

TLDR; what you are referring to is basic IND-CPA security - in a vacuum, an attacker having access to encryption oracle (he can get encryption of any plaintext he wants) is still unable to learn anything about a ciphertext he wants to decrypt. AES-CTR/GCM is practically (if you can bruteforce all AES keys you can decrypt obviously, but thats not practical) CPA secure. Problem is that CPA security assumes an attacker with limited capabilities (he only has plaintext/ciphertext pairs to work with). CCA2/AEAD-secure ciphers consider more advanced (not advanced in terms of computing power, in terms of what he has access to) attackers and are still secure -> use AES-GCM.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: decrypting full ciphertext of (AES CTR/GCM) based on partial knowledge of the cleartext

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.