Re: more steganography talk

[Peter Wayner <pcw@access.digex.net>]

On Fri, 4 Mar 1994, Jim Miller wrote:
 
> In my mind, the perfect steganography system depends upon either an
> environment containing ubiquitous random bit sequences or a
> reversible algorithm that can transform non-random bit sequences into
> random bit sequences without using encryption (unlikely).
 
Such is the function of Mimic, available at ftp.cs.cornell.edu
in /pub/wayner/Mimic
 
It holds the most promise for steganography, in my oppinion.  Unfortunately,
it may be difficult to implement, initially.
 
 
Sergey


------------------------


Sorry to be so distracted. This is a very interesting topic for
me, but I've been bogged down with more prosaic topics. I think
the Mimic FUnction implementation that I did is a very general
standard for steganography. On the current level, it just deals
with text, but you can make it do bits by just using the alphabet
of just plain {0,1}.

Here are the important points about it:

1) If the grammars are made complex enough, they can simulate
anything you can compute with a computer. I.e. You can encode
data in a Turing-complete way. 

2) Even if you limit yourself to plain old context-free grammars,
you still have a class of encryption functions that can be
as powerful as RSA. I.e. You can show that any general program
that can infer the grammar used in a Mimic function can also 
break RSA. This proof is done by translating RSA encryption into
a context-free grammar.

3) If you use Turing-complete grammars, then the result is
technically "undecidable." I.e. it may be technically 
"unbreakable." I don't put much stock in this claim, but
it is interesting to note that there is _no_ possible 
brute-force attack on these systems. I do believe, though,
that there could be many practical "incomplete" attacks
that worked in general cases. 

4) It is still unclear how to generate RSA-level strength
with Mimic Functions. The simplest way may be just to 
encrypt with RSA first. Understanding what makes grammars
hard and easy to grok is a hard question. 

5) That being said, I think that Mimic grammars are one
of the most natural ways to specify steganography. There
are many other forms that are Turing-complete, but I think
that grammars are one of the most natural ways to specify
what you want to happen. 

6) The process is slightly difficult to implement, but I've
got two running versions (as I've mentioned before on the 
list). One in C and the other in Pascal. Your choice if 
you live in the Continental US. It is not clear to me 
if the software is "exportable". I considered applying
to the commerce department to get a free assessment of the
cryptographic strength, but then I found out that they
were denying licenses to systems that I could break.

So they're not a great oracle for these questions.