Is there a term for cryptographic attacks where you can verify decryption without assuming any known structure on the plaintext?

Question

The questions https://security.stackexchange.com/questions/1696/if-someone-breaks-encryption-how-do-they-know-theyre-successful and https://security.stackexchange.com/questions/119887/how-to-know-if-a-file-is-decrypted-or-not on Information Security SE both ask how someone can verify whether they've successfully decrypted a ciphertext. The answers to both questions (as well as this old article by Bruce Schneier) all give the following complementary answers:

1. In the overwhelming majority of practical cases where someone's bothering to use encryption, the plaintext has some known structure and recognizing it is easy in practice.
2. If for some reason you encrypt truly random data, then the ciphertext can't be cracked, because the plaintext can't be recognized.

However, both of these answers seem wrong to me. (I think) a simple counterexample to both is given by one of the single most common cryptography protocols in the world today: the key encapsulation part of hybrid cryptosystems, which are extremely common. For example, a common cryptosystem uses RSA to encrypt an AES symmetric key and publicly transmit the encrypted key, which is then decrypted and subsequently used to encrypt and decrypt the data itself.

1. In this case, the "message" in the first stage (the key encapsulation using RSA) is an AES symmetric key, which is indeed a completely random bitstring. Contrary to claim 1 above, people encrypt completely random plaintext all the time.
2. Fortunately for the attacker, claim 2 above is wrong as well. If you manage to factor the RSA public key and then decrypt the message, then you can easily tell that you've obtained the correct plaintext without even looking at it, let alone verifying that it's structured. All you have to do is multiply the two numbers in the private key together and verify that their product is the public key.

My question is twofold:

1. Is my understanding correct? Is there something that I'm missing that makes these answers correct?
2. If my understanding is correct, is there a term for a cryptographic attack (like factoring an RSA public key, but unlike guessing a one-time pad) where there exists some method of checking the attack's success without assuming any known structure on the plaintext?

Answer 1

You're missing that using a KEM for hybrid is not encrypting random garbage. Say you have a chain of ciphertexts $C_1||C_2||\dots|| C_n$, where $C_1 = \mathsf{Enc}_K(k)$, where $k$ is an AES key, and $C_2||\dots||C_n$ is the result of encrypting some stream of plaintexts under the AES key $k$ in some mode of operation.

If we can compute $k = \mathsf{Dec}_K(C_1)$, we can easily check if we decrypted correctly by decrypting $C_2||\dots||C_n$ under the aforementioned mode of operation. Assuming this data has any structure (or any way to distinguish it from random garbage essentially), one can bootstrap that to a method to distinguish $\mathsf{Dec}_K(C_1)$ from random garbage.

If someone did encrypt (using the block cipher mode of operation) some sequence of random data $P_3||\dots||P_n$ (one block is used for the IV in the mode of operation), we could no longer use the aforementioned method to distinguish a correct AES key. Then the linked comments would still be problematic (from the perspective of an attacker) --- there's no way to distinguish a bunch of random garbage from random (provided its distributed the same), so its essentially hopeless to ask.

This is essentially making the point that just because $k$ is (hopefully) uniformly random on some domain by itself, the rest of the ciphertext blocks are highly dependent on it, which can be utilized to develop a "correctness test" for guessing $k$. So $C_1$ satisfies the "random garbage" property, but $C_1||\dots||C_n$ (jointly) doesn't.

Your second question is interesting, but I can only comment on the first question unfortunately.

Answer 2

To answer part 2, RSA private keys do have known structure. They're $e^{-1}(\mod lcm(p-1,q-1))$. Since $e$ is public, and $n$ is public and equal to $pq$, finding two primes whose product is $n$ is a corresponding private key for a given RSA public key. That's the structure you're verifying, not the decapsulated symmetric key. You can also verify the symmetric key's correctness based on attempting to decrypt some ciphertext or verify a MAC with it, as per Mark's answer.