Re: more steganography talk

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.

On Sat, 5 Mar 1994, Peter Wayner wrote:

> 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. 

I find it fascinating how complimentary cryptography and AI are!


> is done by translating RSA encryption into
> a context-free grammar.

I wonder if anyone has actually gone to all the trouble of 
developing some kind of binary CFG?  It should be easier to design 
than an equally effective human-language Turing-complete CFG.


> that there could be many practical "incomplete" attacks
> that worked in general cases. 

What kinds of "incomplete" attacks could possibly work against
Mimic functions implementing Turing-complete CFGs?
 

> 4) It is still unclear how to generate RSA-level strength
> with Mimic Functions. 

Can't you simply use a Turing-complete CFG, and meta-CFG?
Do such things exist on computer media?


> Understanding what makes grammars hard and easy to grok is a 
> hard question. 

Why not just ask an AI?  :)


> 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.

Do you know if anyone has ported either of those over to anything
other than the Mac?



Good to have you join the discussion, BTW...

Sergey