Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
