# Distinguishing 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 XXX 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://facebook.com" or choose a common reasonable protocol. Thanks!

-
 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.

-
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^{*}$.
 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