How does one know when a message is successfully decrypted?

Question

How do people who decrypt encrypted messages know they have decrypted to the correct message? Do they just keep decrypting until the message is in English (or any other language), or is there a standard, proven method that says that when a certain algorithm is applied to an encrypted message, the original message is reproduced?

I was just thinking about this today and it struck me that it is quite possible to hide a message inside what seems to be the actual message, which could be intended to throw off anyone who might be trying to decrypt the encrypted message without knowing the encryption technique. So with this new insight, it sort of makes it impossible to decide if the message decoded is the original, or another puzzle. Is this a thing, or am I missing something?

Edit:

I feel I should narrow this down to a specific instance, so that answers are less broad. In the case of a war, when the one side intercepts an encrypted message/transmission, is it always guaranteed that the decrypted message is the original intended message [before encryption]? Say you have a job of decrypting intercepted messages, and are given an intercepted encrypted message intended for the enemy, how would you even start decrypting it or choosing an algorithm that could do it? Is there like a step by step process that the entire process from A-Z depends on and is proven to work?

Also as one of the answers pointed out, how would you know the enemy is sending encrypted coordinates or a message? Or is the same decrypting technique used universally? In essence, are humans so predictable that any encryption technique developed is following some predefined pattern (answer with pattern or link)? I hope this is enough to set some new answers on the right track.

Answer 1

I'm sure the real -not so useful- answer is "it depends", but I think you're on the right track here:

A good way to start is to detect ASCII characters (assuming, it's a text message in ASCII), or a file header (if the file type is known), or a "known" sample, being a sequence of characters (think TCP/IP headers, XML tags, ...).

In weak cyphers (such as XOR or any Caesar-alike thing), you can detect patterns, which if you substitute with another value, you can try to derive the key, or parts thereof.

This is of course a simplified version, Cryptanalysis is a very broad field and by no stretch am I an expert in it.

Answer 2

I think you are asking two very different questions:

1. How do I know that a specific sequence of bytes carries a message (i.e. that it is syntactically correct)?
2. How do I know that such sequence carries a meaningful message (i.e. that it is semantically correct)?

For example, suppose a cleartext message can only contain the symbols a and b (to keep things simple). You successfully decrypt two encrypted message and end up with the sequences aba and abbbba.

They are, strictly speaking, "successfully decrypted". However, this tells you nothing about their meaning.

In other words: the syntax of your decrypted string is correct (contains the symbols a and b), but their semantics is what makes the difference. In our particular case abbbba is a palindrome string, i.e. a string that can be read both ways. This adds one more bit of information that's not embedded in the syntax.

Back to your original question:

I was just thinking about this today and it struck me that it is quite possible to hide a message inside what seems to be the actual message,

What you are talking about is steganography and in a similar fashion plausible deniability.

In particular, if we ground your question in the domain of disk encryption and filesystems, a nice implementation is the Truecrypt's Hidden Volumes:

The principle is that a TrueCrypt volume is created within another TrueCrypt volume (within the free space on the volume). Even when the outer volume is mounted, it should be impossible to prove whether there is a hidden volume within it or not*, because free space on any TrueCrypt volume is always filled with random data when the volume is created** and no part of the (dismounted) hidden volume can be distinguished from random data. Note that TrueCrypt does not modify the file system (information about free space, etc.) within the outer volume in any way.

Answer 3

This reminds me of a challenge I had a week ago where I had to find an AES key of a ciphertext. One of the problems was when would I know that the key is correct when I hit it?

What I did is I figure out a word that was for sure in that message: "Congratulations" or "the" or " a " .. you get the idea.

There was another interesting fact in AES: The padding bytes. AES CBC system will add 0xff as its first byte, followed by 15 bytes of 0x0f padding (this is probably not only AES but other encryption systems)

Another way: would be look for the plaintext with most of printable ASCII (chars from 32 (space) to 126 (tilde ~)) in it since other candidates will be just garbage data.

So again if you look for these it will also indicate a possibility of having the original message.

Answer 4

Only using encryption you cannot know if your ciphertext has been correctly decrypted or not. What you require is some provision of integrity.

Integrity can be provided against accidental errors or deliberate attacks with checksums or MAC functions respectively.

Another aspect to know is that not all encryptions are in a 'languages'. Lets say, if you expect a random value (a cryptographic key for example)... How would you know if you decrypted the correct one?

Answer 5

I wouldn't think it's possible without ensuring an integrity check, sadly the only way I can think of is the popular PKI offerings. I'm assuming checksums are out because you'll still need the original file to compare it to or find a way to communicate the checksum value.

Establish a secure session communication using the asymmetric key method and by generating a master secret (like SSL for e.g.) - then go the symmetric key way to communicate. Sender encrypts data with key, sends the encrypted data over the secure channel. Receiver decrypts data. That's it, receiver will know that the decrypted message is accurate because of the provisions PKI offers - integrity, non repudiation etc.