14
$\begingroup$

Say I have a bunch of data encrypted with a secure block cipher (such as AES). An attacker has unlimited access to this encrypted data. The attacker doesn't know whether the data is encrypted or if it's just purely random bits. Is it possible (even theoretically) for the attacker to distinguish the encrypted data from purely random bits?

There seems to be many questions asking whether or not it's possible to identify a particular encryption scheme from the ciphertext, but what I want to know is if it's even possible to determine that the data is encrypted in the first place (as opposed to being random bits).

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

It... depends.

AES is a block cipher. It works over 128-bit blocks. For a given key, AES is a permutation of the $2^{128}$ possible values that 128-bit blocks may assume. As a purportedly secure block cipher, AES is supposed to be indistinguishable from a random permutation, i.e. a permutation selected randomly and uniformly among the $2^{128}!$ possible permutations of the space of 128-bit blocks.

If you consider AES used in counter mode (CTR): some piece of hardware encrypts the successive values of a counter with AES, and spews out the concatenation of the encrypted blocks. You challenge the attacker to distinguish between such a stream, and a purely random stream of equal length. Since AES is a permutation, the AES-CTR stream will never include twice the same block value (by encrypting two distinct counter values, you necessarily obtain two distinct block values). However, the purely random stream is also expected not to repeat the same 128-bit value, until you reach a length of about $2^{64}$ blocks, i.e. quite a lot.

In that sense, AES-CTR is supposed to be indistinguishable from random noise: if AES-CTR was distinguishable, then this would imply that AES (the block cipher) is not indistinguishable from a random permutation, and that would be viewed as a structural weakness in AES. With a $k$-bit key, the cost of distinguishing AES from a random permutation should be $2^{k-1}$, no less (that's the average cost of brute-forcing the key). No such structural weakness is known yet for AES (for AES-192 and AES-256 there are some related-key attacks, but they imply using several AES instances with specific keys which are linked to each other algebraically).

Now, although indistinguishability is academically important (a cipher is deemed weak if it cannot achieve it), it is rarely relevant to practical situations. Most protocols which use encryption very straightforwardly admit to using a specific encryption protocol. For instance, if you use SSL/TLS, the client and server announce in the initial handshake message what kind of encryption algorithm is used, and this is not a problem for practical security. If security crumbles when the algorithm is known, then this is also considered as a structural weakness of the algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ AES-CTR might (with a very small probability) encrypt two distinct blocks to the same cryptotext. I hope that the probability is about the safe as two equal blocks in a completely random stream. $\endgroup$
    – v6ak
    Jan 25, 2014 at 12:55
  • $\begingroup$ @v6ak: You cannot avoid this. If you don't want same blocks to encrypt to the same ciphertext (ECB mode), then it must encrypt to some other ciphertext. With a probability of $2^{-128}$, this other ciphertext is the one from the block before. But this isn't problematic, because this probability is so low. $\endgroup$
    – Marian
    Mar 25, 2019 at 15:56
5
$\begingroup$

Yes and no.

The only cipher that provably has no such distinguisher is the one-time pad.

For practical symmetric ciphers (e.g., AES), we have no proof that no such distinguisher exists or does not exist. The best we can do is say "A bunch of really smart folks have been trying to find such a distinguisher in order to gain fame (and possibly fortune) for a long enough time and haven't found one." This leads us to believe that no such distinguisher will be found for decades to come, so we use the cipher. Could someone release a distinguisher like this for AES tomorrow? Sure.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Assuming a randomly chosen key and a randomly chosen plaintext why is it impossible to prove that no distinguisher exists? Has this been proved? $\endgroup$
    – Ethan Heilman
    Jan 12, 2012 at 14:48
  • 1
    $\begingroup$ @EthanHeilman, I should have said "we have no proof that...". My fault. Also, I think this question (crypto.stackexchange.com/questions/1331/aes-and-perfect-ciphers) and Paulo's answer are related. $\endgroup$
    – mikeazo
    Jan 12, 2012 at 15:05
4
$\begingroup$

In theory, there is a simple distinguisher for encrypted data: Try all the possible keys, decrypt the stream and look if the result is something which makes sense.

Of course, this will not work if you encrypted garbage (and one could say that encrypted random data is really indistinguishable from random data itself, ignoring block sizes).

And practically, the key space of all modern block ciphers is large enough that trying all (or even a large part of all) keys is impossible.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Brilliant, it provably exists but it is as hard as cracking the key, because it is the key. Of course, that does not rule out better distinquishers, but I guess proving that would be about the same as cracking the cipher anyway - the one given by Thomas Pornin for CTR seems to be better than testing the entire key size anyway. $\endgroup$
    – Maarten Bodewes ♦
    Jan 13, 2012 at 0:57
  • $\begingroup$ I don't think it is a given that an AES message can be brute forced. OTP is a perfect cypher because it cannot be brute forced. As brute forcing it would generate all plausible decryptions. Would brute forcing a short AES encrypted message also produce many/most plausible decryptions? $\endgroup$
    – deft_code
    Dec 28, 2012 at 0:53
  • 1
    $\begingroup$ @deft_code This depends on the length of the message. There are (for AES-128) $2^{128}$ possible keys, which means almost as many possible plaintexts for a given ciphertext. If the plaintext size is in a similar order of the key size, we'll get most of the possible plaintexts. But with increasing plaintext size, the probability of a false match shrinks. (And of course, this still depends on what is a "plausible" plaintext.) And in practice, there is no way to brute-force $2^{128}$ keys. $\endgroup$
    – Paŭlo Ebermann
    Jan 4, 2013 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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