How difficult is it to practically detect a forgery in a cryptosystem?

Question

If the encryption key that you use doesn't correspond to the decryption key used by the crypto system, it is assumed that it will not be possible to decrypt the message or you'll know that there has been some mischief.
I wanted to know how will one know that the decrypted text is not correct? My point is that whether the decryption was successful or not can be checked by seeing if the either the decrypted text is same as what we expected it to be or follows the syntax of the language in which it was expected. Otherwise you will defintiely get SOME decrypted string. So how does a computer know that the decrypted string was not correct? Is it left to the programmer to check the correctness of the output?

Answer 1

Confidentiality does not imply authenticity. Many common ciphers are trivially malleable—an attacker that doesn't know the key can nevertheless modify ciphertexts in ways that cause predictable changes to the plaintext. Authenticated encryption solves this problem.

I wanted to know how will one know that the decrypted text is not correct? My point is that whether the decryption was successful or not can be checked by seeing if the either the decrypted text is same as what we expected it to be or follows the syntax of the language in which it was expected.

There is no general criterion to be had here. If the attacker has partial information about the plaintext (e.g., the language or protocol, the application that sends the message, the context in which the message was sent, etc.), they may be able to leverage this to produce an undetectable forgery.

Keep in mind that most encrypted data is not read by humans, but rather processed by computers, or as I like to call them, "error multiplication machines." Attackers don't have to fool a human, only a computer—a fairly stupid machine that may act in very literal and potentially catastrophic manners when given unanticipated input, and which will happily do the wrong thing over and over and over.

Answer 2

There are several standard methods for cryptographically detecting forged messages:

• A cryptographic message authentication code (MAC) can be applied to the message, preferably after it has been encrypted. Such MACs can be built e.g. from block ciphers or from hash functions. Such codes are computed using a key shared by the sender and the recipient (which might be the same as their shared encryption key, or derived from the same master key); the recipient can simply recompute the code and verify that it matches the code included with the message.

• Alternatively, an authenticated encryption (AE) scheme that both encrypts and authenticates the message can be used. The combination of any conventional encryption scheme and a MAC can be considered one type of AE scheme, but there are various other types of AE schemes as well.

• In public-key cryptography, message authentication can be achieved using digital signatures, which allow the sender to sign the message using their private signing key, and for the recipient to verify the signature using the corresponding public key.

MACs and symmetric AE schemes generally come with conditional security proofs, showing that as long as the underlying cryptographic primitive (e.g. block cipher or hash function) remains unbroken, an attacker who does not know the key used to compute the authentication code cannot forge it with a probability significantly higher than e.g. 1/2¹²⁸ or 1/2²⁵⁶ (depending on the scheme and its parameters). Some low-security schemes with short authentication tokens might allow forgery probabilities as high as 1/2⁶⁴.

Digital signatures, like public-key encryption schemes, are generally based on hard mathematical problems like integer factorization or discrete logarithms, and also come with proofs showing that, provided that this problem cannot be solved more efficiently than some assumed lower bound, an attacker cannot forge a signature with a non-trivial probability using any feasible amount of computational power. Again, cryptographers tend to choose such bounds pretty conservatively, considering e.g. a 1/2¹²⁸ success probability after 2¹²⁸ attempted signature computations to be reasonably acceptable.

---

The upshot of all this is that, yes, there are ways to easily and practically detect forged messages. Of course, having a way to detect forgeries only helps if it is actually used (and used correctly!). This is one reason why the trend over recent years has been towards integrated AE systems that combine message authentication and encryption into a single package, so that any message encrypted using such a scheme is automatically also protected against forgeries.

My personal favorite, in terms of misuse resistance, is SIV mode (or other modes using the same construction, like GCM-SIV), which not only provides strong guarantees of message integrity and confidentiality, but also retains most of its security in the face of common user errors, such as failing to provide unique nonces for each message.

One relatively common attack type that no AE mode (not even SIV) automatically protects against are replay attacks, where the attacker captures a valid authenticated message (e.g. a command to unlock a door) and simply resends it verbatim, with the original authentication tag still in place. Such attacks can be thwarted by including a timestamp and/or a sequential message number with each message (and ensuring that it also gets authenticated as part of the message!), and verifying that arriving messages are not too old and do not repeat a previously used message number. However, as such countermeasures are not part of the message authentication scheme itself, implementing them correctly remains the user's responsibility, and thus they are often forgotten or implemented poorly.

Answer 3

One tool we can use to check whether decryption succeeded is called N-gram analysis.

The plaintext is likely to contain many of the common letters or "1-grams" e, t, a, o, i, and n, and unlikely to contain many copies of z, x, j, and q. A random decryption is equally likely to contain all of these letters, so statistical analysis can tell us whether we succeeded. Of course, decrypting a message to "passetao" will score higher in this statistical analysis than "password", but you can eliminate a lot of obviously incorrect decryptions. (note that spaces, numbers, and punctuation can also be considered).

To extend this concept, we can consider bigrams, trigrams, quadgrams, and so on. We're likely to see letter pairs like "th", "es", "in", and "ed", triplets like "the", "ing", and "ion", and quadgrams like "tion" and "ther". If you're decrypting something with partially known contents, you may also be able to look for larger or unusual N-grams. When decrypting a Shakespearean script, you could look for "Romeo" and "Lear", or when decrypting a database of emails, you could look for "gmail" and "yahoo". Other statistical calculations on the distribution of letters, whole words, word lengths, and so on can also be used in addition to N-gram analysis.

Here's an example of this technique applied to the Enigma cipher:

http://practicalcryptography.com/cryptanalysis/breaking-machine-ciphers/cryptanalysis-enigma/

Note that the Enigma cipher, while good for its use, had several phases. Early phases leaked plaintext through which can aid in decryption. This is not necessarily a part of modern cryptosystems.