Is an invulnerable code possible (including brute force attack)?

Question

If I double encrypted a text with for example AES wouldn't it be invulnerable to bruteforce attacks due to the computer not knowing when it has reached the plain text?

Plain text->1st layer of encryption->2nd layer->output

Answer 1

I will address the question in the title - double encryption with AES has been addressed in the other answers.

As Squeamish Ossifrage pointed out, you do not want in general to rely on the assumption that the adversary cannot verify if a candidate decryption is correct. However, there are situations where you have to. Typically, this is the case when the message you want to protect is encrypted with a low-entropy key (e.g., a password). In this case, brute-force attacks become computationally feasible, and it is an interesting and well-studied question to understand when we can mitigate that and achieve beyond brute-force security.

The solution to this problem is known as honey encryption (see also this paper). Honey encryption enjoyed quite a number of interesting application, see Google scholar for a list of papers that used it. citing the abstract of the seminal paper that introduced it:

We introduce honey encryption (HE), a simple, general approach to encrypting messages using low min-entropy keys such as passwords. HE is designed to produce a ciphertext which, when decrypted with any of a number of incorrect keys, yields plausible-looking but bogus plaintexts called honey messages. A key benefit of HE is that it provides security in cases where too little entropy is available to withstand brute-force attacks that try every key; in this sense, HE provides security beyond conventional brute-force bounds. HE can also provide a hedge against partial disclosure of high min-entropy keys.

HE significantly improves security in a number of practical settings. To showcase this improvement, we build concrete HE schemes for password-based encryption of RSA secret keys and credit card numbers. The key challenges are development of appropriate instances of a new type of randomized message encoding scheme called a distribution-transforming encoder (DTE), and analyses of the expected maximum loading of bins in various kinds of balls-and-bins games.

Intuitively, honey encryption will protect even against brute-force attack when your message comes from a known distribution. The idea is to design the encryption scheme such that given a ciphertext $C = E_K(m)$ encrypting a message $m$ sampled from a distribution $D$, then any alternative key $K'$ will have the property that $D_{K'}(C)$ looks like a random sample from $D$ - and therefore, brute-force decryption cannot tell appart the right key from the wrong keys.

Honey encryption can be achieved relatively easily for simple distribution. For example, you could want to encrypt your phone number, such that any decryption of the ciphertext with an incorrect key looks like a valid phone number. Or you could want to encrypt a prime (this is an application described in the first paper I referenced).

Answer 2

No, If we assume that the mythical computer can brute force the multiple AES encryptions and there are many ciphertexts available which are encrypted under the same key and their corresponding plaintext are not random.

The brute-force code can keep track of the meaningful plaintexts for each ciphertext and finally can perform an intersection of possible key candidates to find the key.

Yes, If the plaintexts don't contain any meaningful information to distinguish them from random then there will be no possibility. So at least a distinguisher is required.

Answer 3

When you cascade two ciphers with independent keys, $E_{k_1,k_2}\colon x \mapsto \operatorname{AES}_{k_2}(\operatorname{AES}_{k_1}(x))$, the intelligent adversary will use a parallel collision search for a meet-in-the-middle attack at far less than $2^{128}$ or $2^{256}$ times the cost of a search for $k_1$ or $k_2$ alone.

So this technique doesn't improve security nearly as much as you may think it does. It is often not helpful to simply add layers of complexity: the result may turn out worse than you thought if you don't design it to make proving theorems easy, which is a mistake made over and over again in real-world protocols. The additional complexity may distract you from other concerns like preventing forgery or malleability, which can lead to leaking plaintexts.

---

What about the more general question of knowing whether you're looking at plaintext or not?

From the attacker's perspective, yes, you need some pattern to tell whether you've succeeded in breaking the system or not.

But from the defender's perspective, we don't usually consider a cipher secure unless it can conceal any pattern even if the adversary can choose the pattern. Then you don't have to worry about whether the particular patterns of data in your application will thwart an adversary or not.

Answer 4

The assumption that an adversary would be unable to verify a successful decryption is not safe. They may for example isolate a piece of encrypted data that they are certain is part of some constant plaintext data (eg. file header) or cross check legible English etc.

I am unsure what your example of double encryption even has to do with it. Usually it's something you do as a hedge against a potential catastrophic flaw in a cipher (you don't use the same cipher multiple times in this case). Or if you are suffering from a too short key (eg. triple DES).