3
$\begingroup$

Suppose that $t_1, t_2, \ldots, t_n$ are my clear texts. Suppose that for any $(i,j) \in \{1,2,\ldots,n\}^2$, $t_i$ and $t_j$ only differ in, say, the 1st $m$-many characters. Finally, suppose that I got an encryption function $\texttt{enc} : t_i \mapsto c_i$. By function I mean a programming function, not necessarily mathematically.

To make it clearer, from the point of the adversary, the following is known:

  • The encryption algorithm is $\texttt{enc}$.
  • He knows all ciphers $c_1, c_2, \ldots, c_n$. E.g. he sniffed them over the network.
  • While he does not know the clear texts $t_1, t_2, \ldots, t_n$, he does know the fact that they only differ in their 1st $m$-many characters (without actually knowing the 1st $m$-many characters, nor the other $m+1, m+2, \ldots$ characters).

My question is: how much information would the adversary gain, given that he learned that the original clear texts are mostly identical and only vary in their 1st $m$-many characters, for these algorithms:

  • AES for various modes of operation,
  • RSA and its variations,
  • and scrypt?

Just to rephrase the question: suppose that $H(\{c_1,c_2,\ldots,c_n\}|\texttt{enc})$ is total number of information bits that the adversary managed to gain about the ciphertexts by simply knowing their encryption algorithm, the question is:

  • How bigger is $H(\{c_1,c_2,\ldots,c_n\}|\texttt{enc}, m)$ (information gain after also knowing that the original clear texts are mostly identical except for their 1st $m$-many letters)?

I don't know much about encryption, and I don't know how easy or hard this question is. Any guidance is also highly appreciated.

The reason I'm concerned about this is due to me having multiple backups of my encrypted files, which their cleartexts have differed only slightly. I'm concerned that I'm leaking information by keeping multiple encrypted copies of my slightly-modified cleartexts.

$\endgroup$
3
  • 2
    $\begingroup$ Is the "encryption function" a function in the mathematical sense? It would imply deterministic encryption, which is not CPA-secure. "AES" is a block cipher, implying that the $t_i$ and $c_i$ are precisely 128-bit; anything else AES-based would be a mode of operation. "RSA" can be a number of things, from deterministic textbook RSA $c_i={t_i}^e\bmod n$ to more secure schemes. "scrypt" is a key derivation function, not encryption. Are adversaries computationally bounded? $\endgroup$
    – fgrieu
    Aug 15 '20 at 7:58
  • $\begingroup$ Updated my question. (1) I mean a programming function. (2) various AES modes of operations. (3) RSA and its variations. (4) the scrypt tool that's used to encrypt files, and updated link to point to the tool. $\endgroup$
    – caveman
    Aug 15 '20 at 8:13
  • $\begingroup$ Does each file is encrypted with the same key? Similar to your question, there was a DES challenge by the RSA group. It is brute-force tough theoretically broken by the linear attack. Since the attacks requires lots of plaintext-ciphertext pairs. $\endgroup$
    – kelalaka
    Aug 15 '20 at 21:30
2
$\begingroup$

The question has opposite answers, depending on if we consider adversaries computationally bounded, or not.


Actual adversaries are computationally bounded, that is have limited computational resources. Against these, any cipher that is secure against Chosen Plaintext Attack has the property that similarities between plaintexts are undetectable and unexploitable¹: the adversary gains no useful information (about the key or the plaintexts) from such similarities. With a properly chosen key, and a correct implementation (no side channel leakage, secure Random Number Generator for Initialization Vector, salt, …), that's believed² to be the case for all modern ciphers, including the ciphers in the question:

  • AES in any of the standard modes of operation except Electronic Code Book.
  • RSA encryption per one of the PKCS#1 mode (RSAES-OAEP and the legacy RSAES-PKCS1-v1_5), or using an otherwise secure hybrid encryption. Textbook RSA $c_i\gets {t_i}^e\bmod n$ is not CPA-secure.
  • The scrypt tool, which really uses AES in counter mode³. For this tool, "properly chosen key" means that the entropy in the password, combined with the workfactor parameters used, must make brute force password search far exceed the computational capabilities of adversaries.

Against computationally unbounded adversaries (theoretical all-powerful things), practical cryptographic schemes including those in the question become insecure no later than when what's known about plaintext exceeds the key entropy. In that case, learning that $k$ original plaintexts are mostly identical in a certain location reveals $k-1$ times the length of the common plaintext, and when that exceeds the key size it becomes theoretically possible to find the key, by enumeration of all keys, decrypting the ciphertexts, and keeping the (probably, single) key that makes all the tentatively decrypted plaintexts match in the stated location.

The situation is even worse for RSA and public-key encryption in general: knowledge of the public key, which is assumed, allows a computationally unbounded adversary to decipher any ciphertext.


¹ Including with any amount of known plaintext.

² Moderns ciphers are believed (without mathematical proof) to be resistant against mathematical attacks; that is, when the key is random and unknown, it is believed there is no attacks much more computationally efficient than trying all keys (brute force), absent side channels. AES is among such modern ciphers, despite two decades of intense analysis.

³ According to this description of the format, the bulk of the ciphertext is data xor AES256-CTR key stream generated with nonce == 0. The later means that a multi-targets attack applies (assuming redundancy in plaintext, it is possible to test if a 256-bit AES key matches any of the ones used in multiple ciphertexts using a single block encryption), but that's unlikely to be a practical weakness.

$\endgroup$
6
  • $\begingroup$ (1) I guess by the "computationally unbounded adversaries" case, you mean specifically with bruteforcing? E.g. since the attacker knows part of the cipher text, he can keep guessing until he gets the correct result? (2) What about non-bruteforcing cases where a person who knows enough of mathematics plugs the cipher, and the known plaintext parts, to obtain the key (or bits of it) without bruteforcing? How possible is this with today's mathematics? Is there any mathematical proofs that our encryptions are crackable only by bruteforce? $\endgroup$
    – caveman
    Aug 15 '20 at 20:00
  • $\begingroup$ (3) And what about the question's case when the clear text itself is unknown. So the attacker cannot just do a simple bruteforce trying keys to see when it matches the known plain text. But —instead— what is known is only the fact that the cipher texts correspond to cleartexts that match in parts $m+1 \ldots$ (only differ in the early $m$ parts). What is state of science on this question? If I understand it correctly, your answer (very helpful still) is about an easier case with plain texts also being known (unlike my Q, only location of similarity among unknown cleartexts is known). $\endgroup$
    – caveman
    Aug 15 '20 at 20:06
  • 2
    $\begingroup$ 1) computationally unbounded mean there is no limit for their computation, Just search all of the keyspace. 2) There is no proof, Just 20 years of extensive search over AES, and it is still safe from computationally bounded adversaries $\endgroup$
    – kelalaka
    Aug 15 '20 at 21:23
  • 1
    $\begingroup$ 3) Even all of the Plaintext is known AES-CBC. CTR is CPA secure that means that the attacker cannot even distinguish the encryption of the messages that they choose. $\endgroup$
    – kelalaka
    Aug 15 '20 at 21:26
  • 1
    $\begingroup$ It's worse than no proof for AES - we don't even have a proof that in theory symmetric encryption is possible, except for the (boring/obvious/useless) One Time Pad. For all we know a sophisticated adversary always breaks anything that moves more data than it uses key bits using some method we've yet to discover regardless of the type of symmetric encryption used. That seems very unlikely, but we have no proof. $\endgroup$
    – tialaramex
    Aug 16 '20 at 1:23

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.