5

I am not sure if it is pre-mature to ask such a question. The question is largely inspired by pondering over the question and discussions in the following link (In his answer, @Dad also raises similiar question there):
Can we still provide confidentiality when cryptography is outlawed?

Question: Are there any theoretical models of undetectable encryption system or any elementary work done on the same?

Most modern encryption systems are detected because it is easier to know that they are encrypted. For example: 

 /*a basic working of an encryption function*/
 char* a = encrypt("Hello World");
 printf("%s", a);

We get something like, a = #$%HGFGYTU@724. Most security experts who intercept the exchange of 'a' will realise that it is an encryption and proceed with whatever further action. But on the contrary if 'a' was encrypted something like "I am fine" then, at first place, it would be difficult for the eavesdropper to even detect a presence of encryption. Thus, 'making sense' of encrypted text probably may be important.

By using the phrase "undetectable encryption system" I am explicitly ruling out mechanisms like steganography, for they often work on the probabilistic models of information being located or decoded.

I am talking of a deterministic model of encryption where if C eavesdrop on a message from A to B then C receives an interpretation, which though completely sensible to him/her, is not the same as the the interpretation shared by A & B.

Community
  • 1
check123
  • 534
  • 1
  • 5
  • 14

4 Answers4

9

Steganography is an answer to your question. Namely, you find a medium which normally contains a bit of "noise" which should be random looking (e.g. in the least significant bits of pixels in a photograph). Then, you replace that noise with your encrypted message: if the encryption system is any good, then the encrypted message will be indistinguishable from a sequence of random bits, except by using the encryption key. This is not very easy to build and somehow prevents using public-key cryptography (too much structure...). Properly applied, you get innocent-looking data with steganographic contents which cannot be detected through statistical analysis.

Without a "random noise" channel, things become much more difficult. You can "hide" information in text through some conventions; e.g. you decide that the first word of every sentence in an email will encode a 0 if it consists of an even number of characters, a 1 otherwise. You then can write your text around that convention, and it will be innocent-looking, but the data bandwidth will be very low; if you want to increase bandwidth, then this adds constraints and will make it more difficult to make text which has some meaning and does not look contrived. There again, encryption should be applied to the data which is to be hidden, so that it is externally "random" and thus does not show up in statistical analyses.

(Proper encryption would use, e.g., AES in CTR mode, with a random IV which is included in the message.)

Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
  • But I have explicitly excluded steganography. I believe they are stochastic in nature and there fore, even with a very small probability, they are vulnerable. – check123 Apr 26 '11 at 12:01
  • 1
    Every single security algorithm is "vulnerable with a very small probability", if only because they run on hardware which may fail and give erroneous answers. This is no issue as long as the probability is billions of times smaller than the chances that, for instance, China's government spontaneously converts _en masse_ to Buddhism and declares itself subordinate to the Dalaï Lama. – Thomas Pornin Apr 26 '11 at 13:13
  • Agreed on hardware failures and other errors owing to 'noise'. But I am talking about a mathematical proof of security. Even the RSA relies on the inability of current knowledge to factorize very large numbers in feasible time, but things can change very fast. – check123 Apr 26 '11 at 14:09
  • BTW, nice analogy with the Chinese Government. Lol! who knows it may happen one day ;) ask quant-finance fellows about possibility of tail events. – check123 Apr 26 '11 at 14:11
  • @check123: stereography isn't a substitute for encryption. It's a transmission mechanism, not an encoding mechanism. You can encrypt your data, then HIDE the cipher-text in something noisy and innocent-looking, like the least significant bits of the pixels of an image. Ciphertext looks like noise, so if you want to hide it, put it somewhere noise is expected. – tylerl Apr 29 '11 at 08:07
  • @check123: we do not know whether factorization is really a hard problem (well, 2500 years of research could not achieve it, so it is probably not very easy, at least); moreover, there is no proof that RSA is equivalent to factorization (i.e. it is not proven that one _must_ factorize the modulus to break RSA; this is just the best currently known way to break RSA). The Rabin-Williams scheme is equivalent to factorization. – Thomas Pornin Apr 29 '11 at 13:23
  • @tyler: this is precisely what I am saying that steganography is not an encryption and therefore excluded from the scope of the situation. – check123 Apr 29 '11 at 14:02
  • @Thomas: Interesting... _one must factorize.._ do you know of any other techniques prevalent (to attack an RSA)? – check123 Apr 29 '11 at 14:08
  • @check123 off topic I know, but the world's financial system is in its current mess because quants are _bad_ at dealing with tail/black swan events. –  Aug 08 '11 at 08:21
3

Thomas is correct. In case you need other approaches, I have added this link for Winnowing and Chaffing https://people.csail.mit.edu/rivest/Chaffing.txt in my answer to the original question

Phoenician-Eagle
  • 2,237
  • 17
  • 21
2

Richard Clayton has a PDF about Chaffinch, a Winnowing and Chaffing implementation

http://www.cl.cam.ac.uk/~rnc1/Chaffinch.pdf

You are incorrect about correctly done steganography, although many popular steganography products produce results that are trivial to detect.

Some systems are provably secure

http://www.cs.cmu.edu/~biglou/PSS.pdf

Also relevant to your answer would be things like RubberHose or TrueCrypt's plausible deniability mode. People know there's some random data there, and that random data might be encrypted, but there's no way to know if they have all the layers.

http://en.wikipedia.org/wiki/Rubberhose_(file_system) http://www.truecrypt.org/docs/?s=plausible-deniability

DanBeale
  • 2,074
  • 3
  • 18
  • 27
2

There are many solutions to "outlawed encryption" (such as steganography as already discussed), but what you specify in your example at the end of your question is rather close to deniable encryption. In deniable encryption, the message is encrypted, but rather can be "revealed" to contain other plaintexts than the one originally sent.

It is currently somewhat of an active research subject, so if you are interested in investigating the issue further, I would suggest reading through all papers mentioning deniable encryption in:

http://eprint.iacr.org/curr/

I found Bi-Deniable Public-Key Encryption as a particularily concrete example as to what people are trying to achieve right now. (Note: I don't pretend to understand a half of it properly, but I think it explains the goals in a nice way.)

Nakedible
  • 4,531
  • 4
  • 26
  • 22