Re: attacks on steganography?

From: Ben Mord (benmord@earthlink.net)
Date: 01/14/03 

From: "Ben Mord" <benmord@earthlink.net>
Date: Tue, 14 Jan 2003 14:28:08 -0500

"Nick Hopper" <hopper@cs.cmu.edu> wrote in message
news:3E235A75.30906@cs.cmu.edu...
[...]
> Nope, sorry, you are still misunderstanding the way we model a channel.
> Suppose I give you a partial sentence:
> "Will provably secure steganography be useful in"
>
> There exists some distribution on what the next word/trigram/etc. will be
> following this sentence fragment. You might guess the next word is
> "practice," you might guess it is "the," etc...
>
> Our paper describes a way that, given some source that can guess two
> possible next fragments independently and according to these
> distributions,

A source that can *guess* by virtue of a perfect channel model, or that
*knows* precisely by samples channel history, basically using real channel
history in place of a perfect model? My understanding is that your paper
intends the latter, in which case you will eventually construct an exact
verbatim copy of a previous message. If instead you mean the former, then
David still wins his beer.

> like you would, we can construct a sequence which is drawn
> from the proper distribution over sentences. You can extend this concept
> to sequences which are as long as you wish.

...except if you are truely sampling real message history, and you are
sampling based on *all* preceding draws from history which you ended up
using (and the proof does not permit you to ignore your draw history), then
fairly soon your collection of previous draws will uniquely identify a
particular communication from the channel's history. Once this happens, you
have hit a dead end and could only proceed by drawing again without regards
to your own previous history - but this would deviate from your construction
and therefore no longer be provably secure. Once you hit this point, channel
history can not tell you what message could reasonably come next, because
once you hit this point you are blazing new ground that the channel's
history has never before seen.

With your construction, channel history provides you with a keyable covert
vocabulary. But you do not have control over allowable message length, and
this vocabulary is quickly exhausted. If your message is too short, then it
will appear as an incomplete repitition and your last bit of covert
communication will be suspicious not in the context of what came before, but
rather will be conspicous in the context of what failed to follow. If on the
other hand your message is too long, then your sampling of channel history
will prematurely uniquely identify one particular messsage from that
channel's history, at which point you can go no farther because you have no
history to inform your judgement of what cover text could reasonably come
next.

In other words, I think I *do* understand your constructions. However, in my
previous post I did not explain myself clearly. Hopefully I'm doing a better
job of that in this post...

> Our constructions will on
> average (or at worst, depending on the construction) draw two words to
> extend each sentence fragment. You will always end up with sequences that
> look reasonable - assuming you are making draws in the manner I described.

...and so long as your message is a particular length. That particular
length can not be determined until after the coded message has been formed,
so in retrospect you would know which length was permissible for that
particular combination of covert message and channel history - sort of a
catch 22. Or do you have a way of resolving this dilemma?

>
> > Forgive my digression into real-world examples of a framework that is
> > explicitly theoretical, but I now imagine a web server run by the
American
> > CIA hosting verbatim a copy of the top-level frameset of a webpage in
Polish
> > about the care and feeding of elephants. That might seem a bit odd. But
> > perhaps here I have incorrectly defined the cover channel as the whole
of
> > the WWW, when a much more narrow definition is needed? But perhaps this
> > points to another source of complexity - precisely defining the cover
> > channel. This example highlights that with this technique a cover
channel
> > that is defined too broadly or incorrectly will quickly defeat the
> > steganography, and so the mechanisms for precisely identifying
acceptable
> > subsets of the channel must be considered a key part of the
steganography
> > itself, which must be carefully analyzed.
>
> I agree that recognizing and defining the channel from which we wish our
> communications to be indistinguishable is a hard problem, that our paper
> does not address. But this problem exists in practice, for other models
> as well. How do you know, when you choose an image to send to your buddy,
> whether that image will look suspicious? It is because you have
> implicitly assumed that you have the ability to make a single draw from
> the channel distribution.

Yes! This makes your explicit discussion of this point valuable, and
relevant to all of steganography. However, your construction greatly
exacerbates this dilemma because it determines what cover messages may be
used. If your algorithm produced no such constraint, then you could choose
your current communications as a medium for your covert communications so
long as your covert traffic patterns were happily a subset of your regular
communication patterns.

Ben

Relevant Pages