Property that prevents determining key from ciphertext and plaintext

What is the property (if it is not Forward Secrecy) that prevents (good) symmetrical encryption algorithms from being vulnerable to an attack vector that requires only decrypted data, and the corresponding encrypted data, and allows the attacker to either:

1. Obtain the encryption key OR
2. Obtain some data that is useful to determine some information about the plaintext of a future intercepted ciphertext.

This is a follow-up question to Tom Leek's answer saying that the property mentioned is not Forward Secrecy, that asks, "Then what is it?"

Note that this is not about hashes, or asymmetric encryption (or any other session-token-based method), as those questions can be found at the corresponding links.

(Note, this question was moved from security.SE, which is why most of the links above lead there)

• would this just be resistance to "known plaintext" attacks? Oct 6 '17 at 17:19
• Or, "semantic security" Oct 6 '17 at 17:51

As mentioned in the comments, it appears that you are seeking to understand what provides a cipher with resistance to known plaintext attack. "Diffusion" and "Confusion" I think are the answer here.

Diffusion

"Diffusion" means that the terms/bits of the algebraic expression of the cipher are inter-dependent. Without diffusion, different subsections of the state will act independently, and so can be attacked independently. With diffusion, different subsections of the state will be dependent on the values of other subsections of the state. More diffusion leads to a greater number of terms in the expressions that represent the cipher.

Confusion

"Confusion" means that the algebraic expressions of the cipher are non-linear, which makes them difficult to work with. Non-linearity increases the degree of the ciphers equations. Ideally, the non-linear expressions are not even approximately similar to any linear expressions.

A linear cipher can often times be easily broken with negligible time/space complexity, regardless of how many rounds or how much key material is applied. The linearity means that we can view the ciphertext as a simple equation of key + message bits, which can be easily solved if you know the message bits.

• For 2. Does changing the key come into it? Can a known plain text attack work on a good symmetric encryption if you don't eventually rekey (after 100mb, 64 gb?) Oct 6 '17 at 23:35

Ella's answer is excellent when it comes down to how things work practically, but I think a theoretical overview would be appropriate as well. This one is based off the idea to model block ciphers as pseudo-random permutations (PRPs).

Let's first focus on the primitives, ie on block ciphers.
Imagine the space of all functions from $\{0,1\}^n$ to $\{0,1\}^n$. There are $(2^n)!$ such functions. Now if we pick $n=128$ (the standard modern block size), there are $(2^{128})!\approx2^{2^{135}}$ such functions. That is an insane number of functions. Now what any modern cipher does is to pick $2^k$ of these functions, with $k\in\{128,192,256\}$ being common.

So you have $2^k$ possible functions. Most of which have never been used by humanity because the corresponding key didn't get picked. All you have is a few in- and outputs of the function you look for and you want to identify the function (essentially "find the key") or predict some other (particular?) in- and output pair. Technically you could do that by brute-forcing the key, but this is physically out of reach. Theoretically however this is even harder. As an illustration, imagine a set of 32 numbers. Now mentally draw arrows from 8 elements to 8 other elements. Now try to limit the possibilities for the connections among the last sixteen elements. You can't. Now scale this up by a factor of $2^{123}$ to get a taste of how this is for real block ciphers.

So this is how this works for block ciphers. Now to the encryption of real data. In that case we use less sophisticated constructions but involve randomness / state as well. If we were to re-use our previous picture, you'd pick a new function after each evaluation of the function. So doing evaluations allows you to learn just about nothing about the function.

• I think you meant $2^{128}$?
– NH.
Oct 6 '17 at 18:31
• @NH. I don't see where you mean I should use $2^{128}$ instead of the current number?
– SEJPM
Oct 6 '17 at 18:32
• you have $2^{123}$
– NH.
Oct 6 '17 at 18:32
• @NH. ahh, that one is "imagine a small example of $2^5=32$ [...] and now scale this up by a factor of $2^{128}/2^5=2^{123}$" so 123 is correct
– SEJPM
Oct 6 '17 at 18:40