Encryption algorithm that produces dummy output on incorrect passwords

Question

Background: I've been thinking about using encryption in the context of backing up files to untrusted locations (to the point of making the file publicly and widely distributed for practically failsafe backup).

The problem is, once a file is publicly available, it will forever remain so. And in 20 years, when computing power is unpredictably faster, AES256 bit encryption might be practically useless - and my private backup file readable to all.

I was thinking, as a deterrent to brute force attacks on encryption, what if when the wrong password was tried the algorithm returned dummy data that would require human examination to assert that the data is not what the attacker is looking for.

Example:

I encrypt the plain text (say, an account number) '123456789' with the password 'pass'.

Attacker attempts to brute force the encryption and tries the password 'a'.

The result is '987654321'.

Now, how is the attacker to know that this is not the value I encrypted, and that the password I used was 'a'? Additionally, even if the attacker guesses the password 'pass', how are they to know that '123456789' is the correct value?

This of course is a simple example and most people encrypt somewhat recognizable artifacts; human language text, files recognizable by headers, etc. So this idea could be expanded to not just scramble data upon output, but also to include a variety of generated 'dummy' artifacts (common file formats, samples of language text, etc) not necessarily included in the core algorithm (the dummy data could be user defined). The dummy data output on incorrect passwords could then possibly include valid JPEG files, WORD files, PNG files, and samples of valid text from a variety of languages.

The result would make the encrypted file very hard to brute force without either a huge amount of computing and human power, or specific knowledge of what is encrypted.

Are there any algorithms out there that work like this? Are there any flaws in the idea itself?

Answer 1

Yes, this is possible (conditionally). It sounds like you want Format Preserving Encryption. FPE works by encrypting from an arbitrary domain $X$ onto $X$. Consequentially, if plaintext $M \in X$ is encrypted to ciphertext $C \in X$, any decryption of $C$ - even with the wrong key - will yield a decrypted message inside of $X$. Thus an attacker doesn't know anything from a decrypted ciphertext if he only knows the original format of the valid plaintexts. All decrypted ciphertexts look like valid plaintexts to him.

For example, your domain might be "all ASCII strings of length 7", or "a NULL-terminated string of numbers with length less than 10", or some credit-card number format. All plaintexts, ciphertexts, and wrong-key decrypted ciphertexts will be in that domain. From your example, you might have a domain of 9 ASCII numeral digits.

(In case it's not obvious: The way an attack typically works is that the attackers are decrypting a ciphertext onto a plaintext message space $Y$, but they know something about the original plaintext that limits the potential domain to some set $Z$ strictly contained within $Y$ (that is, $Z \subset Y$). On a typical cipher we encrypt $\{0,1\}^n \rightarrow \{0,1\}^m$ (one binary string to another), but it's rare that all plaintexts could actually be any binary value, generally they are only a strict subset of the input domain. So we assume the attacker knows which plaintext formats are valid, and they just check decrypted plaintexts against this smaller domain. FPE addresses that issue by only allowing encryption and decryption from and to domains that are valid plaintexts. The attacker will never be able to look at a decrypted value and conclude that it is an invalid plaintext. Eg, if they are decrypting a credit-card number, they have an idea of what a valid decrypted CC will look like, but with an FPE algorithm all decrypted messages will look like a valid CC.)

Note that this won't mitigate the problem if the attacker knows some part of the original plaintext that does not apply to all valid plaintexts. FPE mitigates attacks where the attacker just knows the original message space for all valid messges, but it's possible they know something about the specific message on hand that doesn't apply to other messages. (For example, they may know that the 3rd digit is an 8 for the plaintext in question, but not necessarily an 8 for all plaintexts.) In this case they would have a smaller domain to check decrypted messages against and their original attack will still help them to some extent.

An FPE algorithm can be implemented from an existing block cipher. There are different schemes for turning a block cipher into an FPE, depending on your domain size and such. Some of the constructions are relatively simple given the block cipher and a function that decides whether a raw block cipher output is inside of the desired domain. The Wikipedia page linked to above contains descriptions of some.

As for your example: I think that it's rare to see FPE applied to very large domains, like image files. It's usually only applied to small domains, things like credit-card numbers in databases. I don't think I've seen it used in a case where the domain was larger than a couple block cipher blocks. (But whether you can use FPE efficiently on very large domains is a different question.)

Answer 2

Your problem, the way I read it, could be described as follows: You are currently using password encryption for protecting the confidentiality of files on a known format. You have concerns regarding the long term confidentiality of those files, given that you don't know what computers will be able to do in the future. Ideally, you want the confidentiality to be preserved even if the encryption scheme is broken.

• I wouldn't bet it would be very problematic for a futuristic computer that is able to crack AES, to also tell invalid WORD or PNG files from valid ones. If you fear that human inspection would possibly be sufficient to tell a valid one from an invalid one, you obviously can't rule out that advances in both hardware and software will make it possible for the computer to do anything a human could do.
• If you are using password based encryption, it is possible that the weakest link is the password and not the cipher you use for bulk encryption.
• If you require indefinite confidentiality, using a stronger symmetric block cipher (such as triple-AES or whatever) won't help, unless it is provably secure even if the adversary has unlimited resources. If the assumption is that any symmetric block cipher will be broken eventually, and that this is no good, only provable security will do.

There are ways to hide one alternative plain text in the cipher text, which are intended for situations where you yourself might be coerced into revealing the password, and in such case might reveal the password that decrypts the cipher text into the alternative plain text. The common denominator for such schemes is however that the length of the cipher text is doubled if you want to include one alternative plain text, tripled if you want to include two, etc. Clearly, this makes such schemes infeasible if you want to include an arbitrarily large number of alternative plain text.

That said, there are two things you possibly could do:

1. Use an One Time Pad. If you do that, your main problem would be how to generate the One Time Pad and where to store it. If all the adversary has is OTP encrypted cipher text, the plain text could be anything (up to the length of the cipher text), because the pad could be anything.
2. Use a dedicated perfect compression function that effectively removes all redundancy from the plain text before encryption. The idea in such case would be that any automated test of the validity of the decrypted text would look for certain patterns that would have to be present if it were valid plain text, and a compression function could theoretically remove any such pattern (because such patterns consist in redundant information, and that's what a compression function is supposed to remove).

Answer 3

It’s of course doable. Please be referred to the paper “Honey Encryption: Security Beyond the Brute-Force Bound” by Ari Juels and Thomas Ristenpart (PDF) for more details.

Answer 4

It's certainly possible to design an encryption algorithm so it's possible to identify a "correct" decryption. For example the algorithm could append a hash to each block before the actual encryption, and check the hash after decryption.

However, I think this would actually make the overall system less secure. One of the problems a brute force attack has is to determine if the decrypted text is correct (and therefore it's task is done). Adding a categorical check makes this trivial.