Isn't it difficult to recognize a successful decryption?

Question

When I hear about methods for breaking encryption algorithms, I notice there is often focused on how to decrypt very rapidly and how to reduce the search space. However, I always wonder how you can recognize a successful decryption, and why this doesn't form a bottleneck. Or is it often assumed that a encrypted/decrypted pair is known?

Knickers

especially in Bletchly park with Turings "Bombs"... How did those machines know when they had cracked the code? – Ovoid

The Bombes worked by looking for solutions that were internally consistent: many of the hypotheses for the day's key were incompatible with the generated ciphertexts, and the bombes eliminated those, leaving only the consistent ones for manual analysis. See en.wikipedia.org/wiki/Bombe – Supinate

Answer 1

From Cryptonomicon:

There is a compromise between the two extremes of, on the one hand, not knowing any of the plaintext at all, and, on the other, knowing all of it. In the Cryptonomicon that falls under the heading of cribs. A crib is an educated guess as to what words or phrases might be present in the message. For example if you were decrypting German messages from World War II, you might guess that the plaintext included the phrase "HElL HITLER" or "SIEG HElL." You might pick out a sequence of ten characters at random and say, "Let's assume that this represented HEIL HITLER. If that is the case, then what would it imply about the remainder of the message?"

...

Sitting down in his office with the fresh Arethusa intercepts, he went to work, using FUNERAL as a crib: if this group of seven letters decrypts to FUNERAL, then what does the rest of the message look like? Gibberish? Okay, how about this group of seven letters?

Jerrodjerrol

Answer 2

Generally, you have some idea of the format of the file you expect to result from the decryption, and most formats provide an easy way to identify them. For example, nearly all binary formats such as images, documents, zipfiles, etc, have easily identifiable headers, while text files will contain only ASCII, or only valid UTF-8 sequences.

Supinate

Answer 3

In assymetric cryptography you usually have access to the public key. Therefore, any decryption of an encrypted ciphertext can be re-encrypted using the public key and compared to the original ciphertext, thus revealing if the decryption was succesful.

The same is true for symmetric encryption. If you think you have decrypted a cipher, you must also think that you have found the key. Therefore, you can use that key to encrypt your, presumably correct, decrypted text and see if the encrypted result is identical to the original ciphertext.

Basir

Your observation isn't really useful for symmetric encryption, as you used your key to generate the decrypted text: of course it's going to match when you use it to encrypt again. Consider the extreme case of a one-time pad; for a given ciphertext you can guess keys that will give you any plaintext of the correct length and all will successfully re-encrypt to the right ciphertext :). – Thayer

The two previous comments show that this is answer is incorrect, unfortunately. – Diageotropism

Answer 4

For symmetric encryption where the key length is shorter than the cipher-text length, you're guaranteed to not be able to produce every possible plain-text. You can probably guess what form your plain--text will take, to some degree -- you probably know whether it's an image, or XML, or if you don't even know that much then you can assume you'll be able to run file on it and not get 'data'. You have to hope that there are only a few keys which would give you even a vaguely sensible decryption and only one which matches the form you are looking for.

If you have a sample plain-text (or partial plain-text) then this gets a lot easier.

Thayer