How do people know decryption is successful?

Question

Decryption is simply a process of transforming one byte string into another with an input argument private_key. However, if people have no knowledge about the plaintext, how do they know the decryption is successful?

For example, suppose the plaintext is a byte string abcd, and transformed into ciphertext whatever in the encryption process. Then let's assume the decryption process transforms whatever into abcd with one private key, and wxyz with another private key, how do people know which result is the original plaintext?

Answer 1

It depends on the encryption scheme if the correctness of the result is verified or not.

For instance, the output of an asymmetric scheme such as raw RSA decryption (just modular exponentiation) is just a number; you cannot directly distinguish between a correct and incorrect answer.

However a secure padding scheme such as OAEP then a possible output of OAEP can be "decoding error". Decoding error shows that something went wrong when removing the padding, which would happen if the resulting (padded) plaintext message contains is not encoded correctly. And that situation would arise (with high certainty) if either the ciphertext or the private key was incorrect.

---

The same goes for symmetric decryption. Decryption with AES-CTR always succeeds, the result is just a bit string. AES-GCM is however an authenticated cipher and will result in an error if the key is incorrect.

---

There are schemes in which the result does sometimes result in an error and sometimes it doesn't. A perfect example of this is AES in CBC mode with PKCS#7 padding and PKCS#1 v1.5 padding for RSA encryption. In that case the scheme sometimes results in an error and sometimes it doesn't. This leaks information about the plaintext which can be exploited by a padding oracle attack.

---

If your scheme doesn't return an error (with high certainty) then you can protect it with a signature (for asymmetric crypto) or MAC (for symmetric crypto). Usually sign-then-encrypt is used for asymmetric crypto and encrypt-then-MAC for symmetric crypto.

---

As an attacker you can use any information about the (padded) plaintext to see if the result is (partially) correct. This could include information about padding, formats of data structures (and therefore files), frequency analyzes of text etc. etc. etc.

An attacker may also use errors returned from the decrypting party to obtain information. This is called a plaintext oracle attack (a padding oracle attack is usually seen as a specific plaintext oracle attack).

---

Notes:

• an error is often indicated as $\bot$ in scientific papers on cryptography (falsum)

Answer 2

Typically there is a certain amount of structure in the plaintext. For modern crypto algorithms (AES, etc.) a wrong key will almost certainly produce nonsense output.

Even if I take something as simple as a Caesar cipher, encrypting with a shift of four letters and decrypting using a shift of three letters, the first sentence becomes: UZQJDBMMZ UIFSF JT B DFSUBJO BNPVOU PG TUSVDUVSF JO UIF QMBJOUFYU. I doubt that anyone would mistake this for the intended message.

The main reason for adding the hash (Authenticated Encryption) is to prevent a malicious attacker from changing the message, not the risk of decoding it with the wrong key.

Answer 3

A way to offer the option to know if the message is the same is using a hash function to create a resume of the original text.

When you encrypt the original text you have to use a hash function to create a summary of this original text and attached that summary in the message. When the addressee receives your message, he will have to decrypt the message to obtain the supposed original message and after, he will use the same hash function that you had used but with the supposed original message that he has obtained to get a summary. If the summary that you send him and the summary that he obtains are the same, then the message that he decrypts is exactly the same message that you send him.

Here you have more information about hash functions.

If you want to create a secure message then, you (the sender) have to encrypt this summary with sender's private key (in the public cryptography). In this way, you obtain more security because the addressee will have to decrypt the summary with the sender's public key. When you encrypt using your private key you give to the message the security that you, and only you, were the real sender of this message. Besides, as you encrypt the summary with your private key, you créate a summary that cannot be modified for anyone. The reason is simply: you are the only with that private key and then, if the attacker want to modify the message, he has to modify the summary, but as you (the sender) have signed the message with your private key and this signature includes the summary, then the attacker will not be able to sign with the sender's private key the summary that he has to do to avoid that the addressee sees that he has not modified the original message.

Here you have more information about the digital signature because the digital signature is based on this explanation.

Answer 4

There is no way, out of the box, to know that what you got is exactly the original plaintext; that's why it's common to encrypt and sign the original plaintext, so that the recipient can verify that what she got is exactly what the sender encrypted.