It occurred to me that determining whether a set of random bytes is actually a crypto message could be reduced to the halting problem. Given this, it would be theoretically impossible to prove that an uncrackable message was indeed a crypto message. The revelation here (for me, anyway) is that if arbitrary crypto were made illegal, the burden of proof would be on the prosecution which would have to crack the message (at least partially).
Paul E. Baclace peb@procase.com
I don't see how determining that a particular string is an encrypted message reduces to the halting problem. For an arbitrary cipher, you can't prove anything about any given potential ciphertext, since the cipher could be a one-time pad. (for one time pads, where keylength=message length, any string can encrypt to any other string by selecting the right key). So it's true that you can't prove anything about arbitrary ciphertext, but that doesn't involve the halting problem. If the cipher is known, on the other hand, there are perfectly deterministic methods to determine whether a particular ciphertext may coresponds to some given plaintext, simply by exhaustive search of the keyspace. However, I do agree with your basic conclusion - there is no way to determine, by the bitstream alone, whether something has been encrypted with an arbitrary cipher. -matt