Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 6 down vote accepted

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.)

share|improve this answer
    
Very interesting! It's not exactly what I had in mind, but has very similar properties. Will accept if nothing closer comes up. Thanks. –  Jack Singleton Apr 4 '12 at 22:40
1  
FPE is typically used when you already have a database structure, but later discover that some of the fields need to be kept confidential. In order not to have to restructure the database and change the type of those fields, you use a scheme such that the cipher text has the same format as the plain text, with respect to the definitions of the database. However, the question was how to produce cipher text such that it decrypts to seemingly valid plain text using any key (or at least any key derived from plausible passwords), and it's a future computer that determines if it does or not. –  Henrick Hellström Apr 5 '12 at 7:29
    
FPE ensures that all keys will always decrypt to plaintext that was considered valid at encryption time, which is what the question asked. The future attacker is assumed to know the PT domain, but FPE negates that advantage. They may also know more about the PT than just the domain, as I outlined, but the OP's question seems about the PT domain, not message-specific knowledge (see the account number example). For very complicated domains, defining it carefully and using FPE efficiently would be very difficult. But it's still a theoretical construction that closely matches the OP's question. –  B-Con Apr 5 '12 at 16:24

Its of course doable. Please be referred to this paper for more details.

share|improve this answer

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.

share|improve this answer

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).
share|improve this answer
    
2. sounds a lot like performing double encryption to me - and doing double encryption using two known good ciphers that use different techniques might be an answer (as CPU power is not the problem, finding a vulnerability in the cipher might be more dangerous) –  owlstead Apr 4 '12 at 20:26
3  
No, compression is not encryption. Compression will just remove redundancies in such way that it is possible to deterministically restore them. However, if you have an ideal compression function, it will be such that it the corresponding decompression function will output plain text that "looks OK" from any random bit string. –  Henrick Hellström Apr 4 '12 at 21:17
    
"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." - I don't see how computing power would help with this... if the attacker does not know what is in the file they are decrypting, how can they know what is an 'invalid' WORD file and what is a 'valid' one? –  Jack Singleton Apr 4 '12 at 22:05
1  
@JackSingleton: A computer can fairly easily spot a WORD file that contains random characters, just by running a spell check. If your decryption algorithm outputs random but correctly spelled words, it can run a grammar check. Etc. –  Henrick Hellström Apr 4 '12 at 22:42
1  
@owlstead: If by a perfect cipher you mean one that is IND-CPA, IND-CCA and IND-CCA2 given contemporary security parameters, it does in no way require the plain text to look fully random. –  Henrick Hellström Apr 5 '12 at 7:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.