21
$\begingroup$

I am wondering whether there is a bulletproof way to know if one is successful in decrypting a file.

As an example, say I encrypt a text file and protect it with a 3 letter password. I use brute force to decrypt it, but two different passwords lead to a file that contains English intelligible text. Is there a way for me to know which one is the original one? In other words, is there an infallible way to know I've entered the password correctly?

$\endgroup$
  • 20
    $\begingroup$ You check the authentication tag. You did use authenticated encryption, right? $\endgroup$ – Maeher Nov 12 at 18:47
  • 3
    $\begingroup$ related Can I determine if a user has the wrong symmetric encryption key? $\endgroup$ – kelalaka Nov 12 at 19:30
  • 12
    $\begingroup$ There are (arguably) forms of encryption that rely on indistinguishibility of successfully and unsuccessfully decrypted data. See: en.wikipedia.org/wiki/Deniable_encryption . $\endgroup$ – Yonatan N Nov 13 at 6:51
  • 2
    $\begingroup$ @Gloweye That's not necessarily true. It may hold for English prose, but machine data all looks the same. E.g. financial transaction information, temperatures, etc. There's a large band of candidate data that would all look convincing but be wrong. It also depends on the signal to noise ratio as you can transmit below the noise floor. $\endgroup$ – Paul Uszak Nov 13 at 12:24
  • 1
    $\begingroup$ @PaulUszak, not all machine data. many file formats have magic numbers, even checksums, and some structure that can be somewhat validated (sensible lengths for objects, not using undefined values for any type fields etc.) $\endgroup$ – ilkkachu Nov 13 at 15:10
33
$\begingroup$

From the application designer's perspective: Yes, by using an authenticated cipher like AES-GCM or crypto_secretbox_xsalsa20poly1305, which you should do anyway. See the scrypt tool for an example of an application that does just that: encrypts a single file using a key derived from a password using an authenticated cipher—specifically, the tool uses AES-CTR and HMAC-SHA256 in encrypt-then-MAC composition, but these days it is almost always simpler to reach for AES-GCM or crypto_secretbox_xsalsa20poly1305.


From the adversary's perspective: Can't say without more information about the plaintext in your particular case.

In most applications in practice, the plaintext has some identifiable pattern even if the application foolishly didn't use authenticated encryption. For example, an HTML document will usually begin with <html> or <!DOCTYPE; an email will usually have a header and be limited to 7-bit US-ASCII.

In general, we consider a cipher to be secure for confidentiality (in the formal sense of IND-CPA) only if an adversary can't distinguish patterns in the plaintext given ciphertext even when the adversary can choose the pattern. Of course, a 3-letter password admits a very short brute force attack, so we don't consider that to provide any meaningful security.


I use brute force to decrypt it, but two different passwords lead to a file that contains English intelligible text. Is there a way for me to know which one is the original one?

Again from the adversary's perspective, let's suppose there's no authenticator to verify a decryption, and the pattern you're looking for is that the text is all 7-bit US-ASCII. Actually you're probably looking for a pattern that is much sparser in the set of all bit strings, but this one is easy to quantify.

We can reasonably model each byte of a wrong decryption as independent uniform random, so there's a $1/2$ chance each byte in a wrong decryption is 7-bit US-ASCII independently, and if your file is $n$ bytes long, there's a $1/2^n$ chance that all bytes in a wrong decryption are 7-bit US-ASCII.

In cryptography we generally consider an event ‘not gonna happen’ when its probability is well below $1/2^{100}$. If there are $2^t$ keys chosen uniformly at random (say, $2^{256}$ for AES-256 or Salsa20), all it takes is a bit more than $100 + t$ bytes in this model before you stop worrying about any false positives from wrong decryptions—that is, when the probability of a false positive from this pattern is at most the probability of a false positive from a cryptographic authenticator like Poly1305.

But if you do somehow find yourself confronted with two candidate plaintexts that both meet all your criteria, well, there's nothing in cryptography to help discriminate between them, and you'll have to use outside information to help you decide.


This model assumes that the key is substantially smaller than the message and the cryptosystem is not hopelessly broken by related-key attacks; for example, it breaks down when the key is a one-time pad, but it is a reasonable model for, say, AES-CTR or Salsa20. Specifically, let $K$ be the event of guessing the key correctly, and let $A$ be the event that the ciphertext decrypts under the candidate key to US-ASCII. The hypothesis is that that $P(A \mid K) = 1$ meaning that the true plaintext is known to be US-ASCII. By Bayes' rule,

\begin{align*} P(K \mid A) &= P(K) \frac{P(A \mid K)}{P(A)} \\ &= P(K) \frac{P(A \mid K)} {P(A \mid K) P(K) + P(A \mid \lnot K) P(\lnot K)} \\ &= \frac{P(K)}{P(K) + P(A \mid \lnot K) (1 - P(K))} \\ &= \frac{1}{1 + P(A \mid \lnot K) (1/P(K) - 1)}. \end{align*}

The additional modeling assumption about the cipher is that $P(A \mid \lnot K) = 1/2^n$. If we suppose the key is uniformly distributed among $2^t$ possibilities (e.g., $t = 256$ for Salsa20 or AES256-CTR) so that $P(K) = 1/2^t$, then this reduces to

\begin{equation*} P(K \mid A) = \frac{1}{1 + 2^{-n} (2^t - 1)}. \end{equation*}

When $n < t$, meaning the key is underdetermined, this is about $2^n\!/2^t$. For example, if you have a 100-byte text and a 256-bit key, $P(K \mid A) \approx 1/2^{156}$. However, when $n > t$ so that $2^n \gg 2^t - 1$, this is about $1 - 2^{-n}$ and rapidly converges to 1 as $n$ increases and overdetermines the key with more bytes of plaintext that must match the pattern.

$\endgroup$
  • 4
    $\begingroup$ Would the downvoter care to explain what you disagreed with in this answer? $\endgroup$ – Squeamish Ossifrage Nov 13 at 2:57
  • $\begingroup$ Let's not forget that someone could exploit the two different seemingly valid results. For example, if the message could decrypt to either "launch" or "secure", then by using the correct key at the correct time could be an exploit. To your adversary you display "secure" to show that your message is benign, but to your compatriots you show "launch" to attack the adversaries. So while the probability is small, the potential for exploit is there. $\endgroup$ – longneck Nov 13 at 21:51
  • 2
    $\begingroup$ File signatures won't work, as you can equally incorrectly decrypt into another file with the same signature. The extreme case is OTP, when all plaintexts of the same length have a corresponding key that will produce them from any ciphertext of that length. $\endgroup$ – Stop Harming Monica Nov 14 at 16:43
  • 1
    $\begingroup$ @StopHarmingMonica Oops—you're right, I oversimplified the analysis. Fixed and elaborated now, and clarified the modeling assumption. $\endgroup$ – Squeamish Ossifrage Nov 14 at 18:04
11
$\begingroup$

No, there is no bulletproof way, however, there are some ways to achieve this.

First, look at the problem; consider $\operatorname{AES}:\{0,1\}^{k} \times \{0,1\}^{128} \to \{0,1\}^{128}$ where the $k$* can be 128,192,and 256 bits.

Each key represents (selects) a permutation and decrypting with each possible key will result in all possible texts, meaningful or not. Therefore you will have some false-positive results. To eliminate this you may need additional blocks. A longer message from one block will reduce the possible candidate keys. Since the probability of having all is an intelligible block will be reduced.

In history, we had a nice challenge by the RSA system; the DES challenges in which the attacker had some initial information about the plaintext and padding information to see that they found the correct key.

The easiest way is using a fixed text in the file so that you can know that the key can be correct. A similar method used in VeraCrypt that test all possible combinations of PRF and Encryption algorithms with the key so that if the decryption of the first 4 bytes contains the ASCII string VERA than it is considered successful.

Another common approach for this is using an Authenticated Encryption (AE) mode like AES-GCM, you can check the tag for the correction of the decryption. With negligible probability, the tag can be correct with the wrong key but with the further negligible change that will result in meaningful text.

It is possible to combine AE with fixed text. Also, the fixed text can be used as the associated data in AEAD that is not encrypted but authenticated. With the correct key, the tag will be correct. With the incorrect key, there is a negligible chance that you will end up with the correct tag.

* I've assumed that actually you have a good password with a good KDF like Argon2. A good KDF using different passwords will result in different keys up to the pigeon-hole principle. Deriving the same key with two different password is hard and finding one is an article.

$\endgroup$
  • $\begingroup$ "With a good KDF using different password will result in different keys." violates the pigeonhole principle. $\endgroup$ – Ben Voigt Nov 14 at 20:47
  • $\begingroup$ @BenVoigt you are right, it needed more explainations. Thanks. $\endgroup$ – kelalaka Nov 14 at 20:54
7
$\begingroup$

I am wondering whether there is a bulletproof way to know if one is successful in decrypting a file. I use brute force to decrypt it [...] is there an infallible way to know I've entered the password correctly?

Given a decent text file length, this is bulletproof.

For a somewhat oversimplified explanation:

The fraction of plaintexts that are intelligible English text decreases (roughly) exponentially with plaintext length.

To a zeroth approximation: you need ~1.3 bits / letter to encode English text (As to if this encodes intelligible English text... well, that's another matter. But again, first approximation.). So you can fit ~4 letters / 5 bits, or ~32 letters / 40 bits. That is, in 5 bytes you can store ~32 letters.

Meanwhile, ASCII is 8 bits / character. (Or 7, but again, first approximation.) So in those 5 bytes, you can store... 5 letters. Which means that, to a zeroth approximation, every time you add 5 bytes to your message length, you've got a chance of ~5/32 that it remains intelligible English text.

Or, to put it another way. If I have, say, 1KiB of random data. The probability that it's intelligible English text is, to a zeroth approximation, something like 1 in 10^160.

If I have a 256 bit key, that's ~10^77 possible keys. So to a first approximation, the probability that there is a second key that generates intelligible English plaintext from your encrypted copy of 1KiB of text is ~1 in 10^83. (Each other key generates "random"-ish output, and you have ~10^77 tries at getting a 1-in-10^160 chance.)

This is somewhere around "successfully guessing which particle in the universe I picked" levels of probability that a collision exists. Not going to happen.


But let's say that by some absurdity it did happen, and that there are two keys that produce intelligible English text from your data.

We're starting to hit exascale computing. (Still amazes me sometimes.) Let's say we had a computer that could do 1 exa-decrypt / second and check if the result was English text. That's ~10^18 decryptions / second. Let's say it's trying random keys. How long before it hits a decryption key? The math is fairly simple... Inconceivably longer than the age of the universe.

Ok, so that's not enough. What if we turned the Earth into computronium? Bremermann's limit gives ~10^75 operations / second maximum for the Earth. This is actually somewhat sane - a minute or two.

Again, assuming a 256 bit key.


Let's assume a larger key for a moment. One large enough that there's likely more than one key that maps to English decrypted text.

How long before we find any key that maps to English decrypted text, given our exascale computer? Inconceivably longer than the age of the universe.

Our computronium Earth? Still inconceivably longer than the age of the universe.

...the observable universe? Still not enough. Unless you're willing to wait 10^40 years at least.

So even if the key was long enough that there were multiple keys that produced English text as output, it still wouldn't matter even if the adversary had the entire observable universe at their disposal. And if the adversary has more than the observable universe at their disposal, you likely have other problems.


All told, it's pretty safe to assume for any decent-sized file that if you decrypt it with a decent encryption algorithm and get English text you've got the right decryption key.

Longer files would produce even sillier results.


Note, there are several assumptions here:

  1. The encryption algorithm that is used is actually secure.
  2. The size of the plaintext is "long enough".
  3. Your plaintext has a low enough entropy/bit. This ties into 2 somewhat.
    1. If your plaintext is compressed, this may cause problems (a perfect compression algorithm's output is effectively indistinguishable from random data almost by definition.)
    2. This also implies e.g. Raw: followed by unencoded raw bytes is not allowed
      1. If you do, then your probability of random data looking like valid plaintext can become nontrivial.
$\endgroup$
5
$\begingroup$

I don't know why none of the previous answers mentioned deniable encryption, which was mentioned by Yonatan in a comment. It is an intrinsic feature of deniable encryption that one cannot determine whether the ciphertext has been decrypted with the correct key! In fact, deniable encryption is the best way to actually secure very sensitive information.

Here is a simple instructive example: Given a string $x$ of length $n$, we use any strong encryption to encrypt it to get a string $y$ of length $n$, and embed it at certain positions in a string $s$ of length $1000n$ with its other characters being random, where the positions are of the form $1000k+c$ where $c$ is a constant that is determined by the password. It should be clear that we can use the same method to embed multiple encrypted strings into the same final string $s$, using one password for each string, as long as we choose the passwords so that each string has a different offset $c$. Of course, we do not reveal how many encrypted strings are embedded, and there is obviously no way for an attacker to know how many there are from the ciphertext $s$, even if we reveal some of the passwords, because the rest of the string in $s$ will still appear random. (But if you are a spy, then deniable encryption may also work against you because the enemy might never stop ill-treating you even if you reveal all the passwords, because they really cannot know whether you have...)

If on the other hand, you are talking about a specific file encryption method, then of course it may not be deniable, but then your question was unclear and lacking important context.

$\endgroup$
  • $\begingroup$ There is a related concept of honey encryption. $\endgroup$ – Mikero Nov 14 at 21:00
  • $\begingroup$ @Mikero: That is an interesting idea, though it seems to me impractical for ordinarily sized files. The problem is simply that the password space is too small to cover the entire space of "legitimate plaintexts", even if the latter is known and easily indexed. For instance, suppose we want to encrypt a 1 MB English book stored in text format. That is about 1 million bits of entropy, so one would need to use random passwords that have about 1 million bits each, in order to be able to cover the plaintext space uniformly. Thus it seems that deniable encryption is better for long plaintexts. $\endgroup$ – user21820 Nov 15 at 2:40
2
$\begingroup$

As a fundamental (read: mathy) generalization, I believe not. The same proofs that apply to the one-time pad encryption method seem to extend to this concept as well.

e.g. Say you encrypt a short text. You use the one-time pad method. Then you throw away the key, and suddenly develop amnesia about the whole thing.

TL;DR ... the starting information is lost forever.

Everyone (including you) are now at some random gibberish with the same length as the plaintext. We call this the ciphertext, and, as per proofs for OTP, it leaks nothing about the key, or the plaintext.

We now use a sufficiently powerful computer to brute force the ciphertext. We WILL of course, arrive at the true plaintext... but that is only a byproduct of getting all possible plaintext, including any other English.

Now, as per the cipher proofs, it seems also proven we are ONLY left with ways at comparing one candidate plaintext to others. This is because all of our brute forced text leaks nothing about the key or true plaintext, just as with the ciphertext.

As we start adding information (say knowing that the plaintext was English) we can refine our methods of identifying and comparing candidate plaintext. And, in actual practice, this is how it would be done. (see other answers) However, and most critically, it seems we MUST add more external information to do this. Q.E.D

$\endgroup$

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.