When performing a key search, I've always wondered how you reliably detect a successful decryption once you hit the right key. I assume that you have to analyze the data and look for patterns: words, letter frequency, known file headers, statistical properties and so forth.

Is this a correct assumption and, if so, has anyone exploited this by enabling the introduction of decoy plaintexts in a cipher? Is there any research related to this?


Yes, that's a correct assumption: sometime statistical properties of the plaintext (like, compressibility using standard algorithms, which can be quickly approximated, then refined) are used to check that a correct key was found during brute-force search, when there is no better way, like known plaintext.

By the second Kerckhoffs's principle, if a decoy method is used, that fact is part of the algorithm, and public (the value of the decoy can be an input, considered part of the key, and either secret or public). However modern cryptographic algorithms are designed to resit any amount of known plaintext (and even chosen plaintext), and therefore do not need such decoy method in order to achieve confidentiality; which is why I doubt you'll find (recent) peer-reviewed articles about decoy in order to improve confidentiality, only as a mean to implement plausible deniability, as in TrueCrypt. In this application, decoy is used, but not for improved resistance to exhaustive key search.

Update: Sometime the key is really a passphrase stretched to a key using some password-based key derivation function. When you count brute-force search of such passphrase as key search, which is quite legitimate, a decoy (deciphering to plausible decoy plaintext with a weak decoy passphrase) is an interesting idea. One issue is that, as stated above, the adversary is assumed to know there is potentially a decoy; anyway it seems hard to hide the fact that an encryption system allows the use of decoy passphrases(s) and plaintext(s), when that system is analysed by the adversary to the point necessary to mount an efficient passphrase search. Therefore, the adversary performing passphrase search has the option to continue searching after finding decoy(s), and I do not see that the overall resistance to a given effort of passphrase search is much improved. Towards that goal, it is probably better to use a good key derivation function, using the principles pioneered by scrypt; also, that avoids the ciphertext expansion unavoidably caused by the use of decoy.

  • $\begingroup$ Thank you for your answer. Couldn't the decoy be part of the input instead of the algorithm? And if you could input a large number of decoys, could that not be effective? $\endgroup$ – Alexander Torstling Jan 15 '14 at 21:22
  • $\begingroup$ I mean, it wouldn't help against known plaintext, but it could make it impossibe to know which plaintext was the intended message, couldn't it? Or am I missing something? $\endgroup$ – Alexander Torstling Jan 15 '14 at 21:26
  • $\begingroup$ @Alexander Torstling: you are right, the decoy can be part of the input, and my wording was ambiguous; I hope that's clearer now. Yes, decoy as used for plausible deniability (e.g. as an option in TrueCrypt) is there in order to make it impossibe to know which plaintext was the intended message, but not to prevent exhaustive key search. $\endgroup$ – fgrieu Jan 16 '14 at 2:55
  • $\begingroup$ Yes, it's clearer. Thanks for the update. Good point about the fact that being aware of potential decoys would just drive the attacker to continue. Having a strong crypto is probably better in the general case, but I believe that the plausible deniability of for instance sending two contradictory messages could be useful to guard one self against potential future cracking of the cipher. $\endgroup$ – Alexander Torstling Jan 16 '14 at 5:06

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.