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?

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.

  • $\begingroup$ Right, but you could certainly imagine a situation where the attacker doesn't have access to the encrypted data $C_2||\dots||C_n$. For example, if it hasn't actually been generated yet - suppose that Bob sends Alice his public key well before Alice actually needs to send him any data. If Eve has the computational ability to factor it, but still at significant cost, then she'd certainly want to get a jump start on factoring before she intercepts any actual encrypted data. $\endgroup$
    – tparker
    Mar 20 '20 at 3:14
  • $\begingroup$ Or simply consider that it's often a lot easier to get your hands on someone's RSA public key than the encrypted data stream. The former is often literally posted publicly, while the later is still somewhat protected even if sent over a not-perfectly secure channel. There are different levels of security. $\endgroup$
    – tparker
    Mar 20 '20 at 3:17

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.