Slashdot Mirror
Distinguishing Encrypted Data From Random Data?
gust5av writes "I'm working on a little script to provide very simple and easy to use steganography. I'm using bash together with cryptsetup (without LUKS), and the plausible deniability lies in writing to different parts of a container file. On decryption you specify the offset of the hidden data. Together with a dynamically expanding filesystem, this makes it possible to have an arbitrary number of hidden volumes in a file. It is implausible to reveal the encrypted data without the password, but is it possible to prove there is encrypted data where you claim there's not? If I give someone one file containing random data and another containing data encrypted with AES, will he be able to tell which is which?"
Doesn't compressed data look random?
As an ideal, yes. But compressed data is still pretty distinguishable from random data. In particular, many compression formats have small markers in various places so that the decompressor can attempt to recover a corrupted file. Also, no compression technique is perfect, so even without these the data is still distinguishable.
Need a Python, C++, Unix, Linux develop
AES is designed to be a pseudo-random function (meaning it's evaluated against that criteria). What this means is that /when used properly/ AES encrypted data should be indistinguishable from random data, at least for a distinguisher running in bounded time. If anyone discovers an efficient algorithm that can distinguish this, it'll be a big nail in AES's coffin (and yes, at the very theoretical level I realize that there already are some known weaknesses in AES, but for the moment you're in good shape).
Hard to say from your question, but if you haven't done already, get yourself some crypto knowledge. Crypto is hard, there is a reason that you are laughed out of the room if you say you've invented a new crypto algorithm and you don't already have strong credentials.
Randomness is one of the harder computer problems. Especially in steganography, many implementations have been defeated by creating not enough or too much randomness. If you want to hide your message in something, it doesn't matter if your output is distinguishable from randomness, it matters if it is distinguishable from what should be there. Simple approaches like LSB tricks have often fallen because those happen to be not random in many input data.
Assorted stuff I do sometimes: Lemuria.org
If you use AES in ECB mode, then the answer is that it's usually painfully obvious that the original data was structured.
If you do use chaining (CBC, or something similar), then it will look quite random.
Excellent example here: http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation#Electronic_codebook_.28ECB.29
Am I part of the core demographic for Swedish Fish?
Rubberhose (Pronounced Marutukku) is transparently deniable encryption, developed by (among others) Julian Assange.
This seems to do exactly what you're trying to do, so even if you want to go ahead and implement it yourself from scratch, it's worth reading up on what they've done to get some ideas and avoid some potential pitfalls.
Specialist Mac support for creative pros, Melbourne
Not true. You are subject to the jurisdiction of the nation of registry of your craft.
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.
DES is nowadays considered a weaker algorithm
DES is considered too weak for many uses due to its small key size.
Nonetheless, if you can find a way to reliably distinguish DES output from random bits, without knowledge of the key and with remotely-practical efficiency, you can publish a paper that will gain you substantial name recognition among the world's cryptographic elite.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
You (and the submitter) might want to have a look at http://eprint.iacr.org/2009/531 which talks about "known-key attacks" on "AES-like permutations". The goal of these types of attacks is to distinguish AES-encrypted data from random noise. Right now, all they can do is break 8 rounds of AES-128, so the answer to OP's question is "right now, AES-encrypted data is indistinguishable from noise".
---linuxrocks123
vi ~/.emacs # I'm probably going to Hell for this.
There is no question is is computationally difficult, just not computationally impossible. The reason for that lies in computational complexity theory. You can get a basic summary of the theory here.
In summary, if the data being encrypted is compressible by practically any algorithm whatsoever, it has computational complexity less than its bit length, i.e. a smaller bit string can be used to recover the larger one. Likewise, the computational complexity of any encryption key is at most the length of the key in bits.
Suppose you are encrypting a 256K bit string that can be compressed by a factor of two by an _ideal_ compressor. And then you have a maximally random 1K bit key. The maximum Kolmogorov complexity of any finite deterministic function of those two inputs that is known to the attacker is 129 Kbits. Where the maximum computational complexity of a truly random string of the same length as the input is 256 Kbits.
The difference between those figures opens the door to a statistical attack, because the data is not _really_ random. It just looks that way, sort of like the output of a pseudo random number generator, which isn't really random at all. If you encrypt a string of zeroes with a significantly shorter key, the output of a pseudo random number generator is exactly what you will get, a pattern that is maximally vulnerable to attack.
The lesson to be learned here is if you want to minimize the risk of attacks from folks with far more computer power than you have available, compress it using the best available compression algorithm first. Then the computational complexity of the input string will approach the theoretical maximum for a string of that length, depending on how good the compressor is. Throughout I mean complexity relative to what the attacker knows (such as the encryption algorithm) of course.
"Secure Empty Trash overwrites your data with digital gibberish"
From apple's site about Secure Empty Trash feature @ http://www.apple.com/pro/tips/empty_trash.html
I suggest you read up on cryptography.
Encryption, in general, is attempting exactly what you're attempting: make plaintext look random.
What you're trying to defend against is known as a "known-plaintext attack".
You can use any standard cryptographic approach such as AES-CBC as suggested above.
For a password-based approach, there are also standard key generation algorithms such as PKCS #5.
Note that your claim that your approach gives "as random as it gets" data is not true; once you've fixed for all time a set of random numbers, they're no longer "random".
As for generating random-like numbers deterministically, that's what stream ciphers (e.g. RC4) do.