# Can you distinguish encryption methods from the output?

Suppose that you see all IP communication packets between two computers for a day, as they pass through a connecting router, and this amounts to 10MB. You additionally know that all data transmission follows the standard "RSA-1024 plus AES-128" protocol. To be even more specific, suppose you know only one computer is doing RSA decryption, which computer that is, its specific "public key", and that the RSA decryption is only done to re-initiate the AES key after the other computer is (instantly) rebooted.

Could you look at the 10mb and get any information about whether the computer was rebooted?

I wonder if these pseudo-random streams could be "hashed" in some way to help...e.g., maybe 0.03 bits of information is revealed ("Because of this abnormal X-X-X data series in the stream, there is a 60% chance it was rebooted, instead of the normal 50%.").

I know that any revealing (even a tiny part of a single bit as useless as the rebooting of a computer) is against the goal of this encryption, so I ask in a rigorous way for those familiar with these protocols and their outputs. I truly wonder if there isn't some blatant unencrypted "I need to login from scratch, please!" signal in the standard protocols. When a computer loses its AES key, they could be blatant to help the server, or they could rely on the server to use AES first, conclude it's gibberish, and then try RSA. I'm guessing the latter is done, but hoping for confirmation here.

To answer my own question, I do believe that 0.03 bits would be reasonable, mainly due to the timing of the packets. RSA encryption/decryption takes longer, so delayed responses correlate with a reboot (please notice I'm ignoring the actual power-down time and wrote "instantly rebooted" in the problem statement to focus just on the cryptography).

Note: We need more information on the protocol to confidently answer this, but I know nothing beyond the AES and RSA algorithms. This is why I ask the question. So, if you must, please just assume the server URL is "https://whatever.ext" or choose a common reasonable protocol.

-
Cross post: stackoverflow.com/questions/11072921/… –  CodesInChaos Jun 19 '12 at 10:07

Well, with standard protocols (TLS, SSH, IPsec), there really is a blatant unencrypted "I need to login from scratch, please!" message. That's because when they first come up, they don't share keying material with the peer, and so they can't encrypt any messages. Instead, they perform some sort of key exchange process using nonencrypted messages, and those messages are easily distinguishable.

Now, I suppose it would be possible to define a protocol where this initial message would be indistinguishable from an encrypted message. However, the details would appear to be rather finicky (you'd have to worry about message timing and message length), and probably end up being expensive. In addition, reboots are not actually instantaneous, and when you are rebooting, you obviously can't send out any messages. I can't think of any scenario where the effort would be worth the cost.

-
"They can't encrypt any messages", you say. But, the client could use RSA encryption with the server's public key right after reboot, right? In theory, no eavesdropper should know then whether this is truly RSA or a continuation of the previous AES. But, the server could try both options and figure it out. –  bobuhito Jun 18 '12 at 20:29
@bobuhito: typically, no, they can't use the server's public key, because they don't assume that they know it. Instead, when the client attempts to bring up a session, it asks the server for its public key (certificate, actually, so the client can validate it). –  poncho Jun 19 '12 at 22:15
So, the answer is yes, thanks! As Poncho and Maeher have pointed out, it would be possible to change our protocols to conceal this bit. I wonder if anybody would feel insecure knowing that packet sniffers can tell how often they ask for a certificate...but I guess the sniffer gains a lot more information from knowledge of the traffic volume. Are there any protocols in regular use that "pad a lot" to create high volume at all times (thereby concealing more information)? –  bobuhito Jun 19 '12 at 22:33
@bobuhito: As to whether there are standard protocols that "pad a lot", well, the closest thing we have is IPsec (RFC4303) which allows an implementation to both add padding to real packets and add dummy packets, both to disguise this. On the other hand, it doesn't mandate that any implementation do anything effective with it (and, in practice, it'd be nontrivial to generate dummy traffic that would actually fool an intelligent adversary. –  poncho Jun 20 '12 at 13:30

The security of two encryption schemes does not imply that you cannot distinguish their ciphertexts. (In fact, it may be even possible to decide which public key a ciphertext has been encrypted with.)

Consider the following: AES ciphertexts are simply bitstrings of a certain length. RSA ciphertexts on the other hand are elements of $\mathbb{Z}_N^{*}$. In general when you have an AES ciphertext, there will be bistrings that would not decode to valid elements of $\mathbb{Z}_N^{*}$.

As an example consider the RSA modulus $11\cdot13=143_{10}=10001111_2$. Now, if we would see the bitstring $11000000_2=192_{10}$ we would immediately see, that this can not be an RSA ciphertext, because even though, the bitstring has the correct length, it decodes to $192 > 143$ and therefore not to a valid element of $\mathbb{Z}_N^{*}$.

There are ways to get around that, such as Admissible Encodings, but general, it is possible to distinguish two encryption schemes based on their ciphertexts.

-
Note that, with RSA, it is fairly easy to make the output indistinguishable (as long as you control the modulii); simply restrict the modulii used to the range (say) $2^{2048} - 2^{1500} < N < 2^{2048}$. When generating an RSA key, it is easy enough to compute a modulus of this form, and practically speaking, you'll never see a 2048 bit value that cannot be an RSA ciphertext. –  poncho Jun 19 '12 at 16:45
Yes, there are different ways to achieve such behavior. My point was that in general, the security of two encryption schemes does not imply that their ciphertexts are indistinguishable. –  Maeher Jun 19 '12 at 17:01