attacks on steganography?

60 views
Skip to first unread message

niko vinken

unread,
Jan 1, 2003, 10:47:58 AM1/1/03
to
Can you make a statistical attack on audio- or video-files?

Are there other attacks possible on those files, similar to visual
attacks you can do on pictures?
For instance : By filtering certain frequencies out off an audio-file
and listening to it?

Mok-Kong Shen

unread,
Jan 1, 2003, 11:42:13 AM1/1/03
to

I can't answer but your question doesn't seem to be
entirely clear. Do you mean the possibility of removing
'watermarks' or something else?

M. K. Shen

niko vinken

unread,
Jan 2, 2003, 6:21:40 AM1/2/03
to
Not removing something, just detecting if there is stegano in such a file?

Ben Mord

unread,
Jan 2, 2003, 3:08:40 PM1/2/03
to
"niko vinken" <niko....@kh.khbo.be> wrote in message
news:747d752e.0301...@posting.google.com...

Sure, why not? You can always try. Whether you can succeed depends on how
good the steganography is, and the ratio of carrier bandwidth versus covert
channel bandwidth. My impression is that this is a very immature field, and
current techniques are not very good. In other words, I would guess that you
can break today's steganography to fairly high reliability, unless they are
accepting a very small covert channel bandwidth. It would be impossible to
discover well designed, very low bandwidth covert channels in a high
bandwidth signal. "Ciphertext only" attacks are of course the hardest, and
onces where you have a copy of the steganography algorithm used (just not
the key) are much more likely to succeed.

There are papers on some fairly generic techniques for attacking stego,
which you can probably find using google. That might give you a sense for
some types of attacks. Most of the papers I've seen focus on attacks where
you know the algorithm that was used - probably because these are the only
attacks where you can quantify the confidence yielded by the attack, and
these numbers lend credibility to the paper. I find the concept of
"ciphertext only" attacks against steganography more interesting, although
this is certainly more difficult. The study of ciphertext only attacks
against steganography would probably be less formal because of the
difficulty in objectively measuring the success of a particular attack
against the space of steganographic techniques that could be designed with
knowledge of the attack in question.

Not knowing much about steganography or audio, my first inclination would be
to take the Fourier transform of a dubious audio file. Hidden data might
involve frequencies outside the human hearing range, so I would focus first
on infrasonic and ultrasonic signals. I think a good audio engineer first
filters certain frequencies in the analogue signal before digitizing it, in
order to preclude bad interactions between the sampling frequency and
frequencies that might be present in the original analogue signal. I think
music is often sampled first at one frequency and then recoded at a lower
sampling frequency after mixing and mastering, so I would learn more about
this process and the inaudible artifacts that it should produce. I would
learn more about this and then look for frequencies that shouldn't be there.
Phase information is mostly inaudible to the human ear so in uncompressed
files I would also look for unusual patterns there. If the music was
synthesized and you can study the synthesizers in use, this should give you
a very precise idea of what their signals should look like and you should be
able to subtract them from the original signal, again yielding less
distraction from potential covert signals.

If you're examining compressed files, then of course you would want to study
the compression algorithm in detail to learn what types of redundancy these
are supposed to eliminate. If it is a lossy format, then I would learn what
information should be eliminated, and to what degree and in what order as
the compression ratio is turned up. Then I would look for anomalies there.

If the steganography is in a widely distributed piece of music, then you
could also compare the suspected file against an original copy and examine
the differences. If the "error" rate seems very high and yet the music
sounds as good as the original, that would be very suspicious.

Maybe good audio steganography would look like white noise, and perhaps it
would be louder where the music (or legitimate frequencies) are louder, and
quieter where the recording is quieter (so as to be less audible.) Or maybe
it would be constant. I would then study sources of white noise in recording
and try to understand what it looks like, how it should (or shouldn't) be
correlated in amplitude to the amplitude of the true signals, etc so that I
can recognize suspicious white noise. As for video signals, this is just a
different medium with different patterns to learn and then scrutinize.

Just some thoughts... If you know the steganographic algorithms that might
be used, then it would be much easier to attain a given level of assurance.
The intuitively simplest technique is exhaustive search of the key space. If
this is too slow, then you need to study the artifacts produced by the
algorithm in question and hope the designers didn't do a good job of
emulating natural noise.

Ben


Ben Mord

unread,
Jan 2, 2003, 9:11:39 PM1/2/03
to
Ben Mord wrote:
> "niko vinken" <niko....@kh.khbo.be> wrote in message
> news:747d752e.0301...@posting.google.com...
>
>>Can you make a statistical attack on audio- or video-files?
>>
>>Are there other attacks possible on those files, similar to visual
>>attacks you can do on pictures?
>>For instance : By filtering certain frequencies out off an audio-file
>>and listening to it?
>
>
> Sure, why not? You can always try.

[...]

[I then went on to speculate about how you could do this.]

Lest I confuse someone, I should emphasize that my previous post is just
some brain storming based on very little real information. My real point
is that, in its most general form, I think thwarting steganography is a
matter of scrutinizing the signal closely, getting to know what a
"natural" signal should look like, and comparing that to what you
actually see. Or you can attack it from the other direction - you can
study common steganographic algorithms, learn the patterns that they
produce, and look for those. If you change the carrier data, the
fundamentals stay the same and at from an abstract level, you attack it
the same way.

Ben

DSCOTT

unread,
Jan 2, 2003, 9:25:37 PM1/2/03
to
ben...@earthlink.net (Ben Mord) wrote in <av2r54$b5ueh$1@ID-
101018.news.dfncis.de>:

>
>[I then went on to speculate about how you could do this.]
>
>Lest I confuse someone, I should emphasize that my previous post is just
>some brain storming based on very little real information. My real point
>is that, in its most general form, I think thwarting steganography is a
>matter of scrutinizing the signal closely, getting to know what a
>"natural" signal should look like, and comparing that to what you
>actually see. Or you can attack it from the other direction - you can
>study common steganographic algorithms, learn the patterns that they
>produce, and look for those. If you change the carrier data, the
>fundamentals stay the same and at from an abstract level, you attack it
>the same way.
>
>

I don't belive you can detect a proper steganographic signal.
You could make it look like background noise of whatever frequencies
you want. The only way one could detect it with out having the
original files before data added is to have a copy if code
desinged to read it and the key. You could stop the spread of
the message only if you change the file.

David A. Scott
--
My Crypto code
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott16u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"

Ben Mord

unread,
Jan 3, 2003, 11:52:06 AM1/3/03
to

"DSCOTT" <daVvid_...@email.com> wrote in message
news:92F7CD685H110W...@130.133.1.4...

> ben...@earthlink.net (Ben Mord) wrote in <av2r54$b5ueh$1@ID-
> 101018.news.dfncis.de>:
>
> >
> >[I then went on to speculate about how you could do this.]
> >
> >Lest I confuse someone, I should emphasize that my previous post is just
> >some brain storming based on very little real information. My real point
> >is that, in its most general form, I think thwarting steganography is a
> >matter of scrutinizing the signal closely, getting to know what a
> >"natural" signal should look like, and comparing that to what you
> >actually see. Or you can attack it from the other direction - you can
> >study common steganographic algorithms, learn the patterns that they
> >produce, and look for those. If you change the carrier data, the
> >fundamentals stay the same and at from an abstract level, you attack it
> >the same way.
> >
> >
>
> I don't belive you can detect a proper steganographic signal.
> You could make it look like background noise of whatever frequencies
> you want. The only way one could detect it with out having the
> original files before data added is to have a copy if code
> desinged to read it and the key. You could stop the spread of
> the message only if you change the file.
>
> David A. Scott

If you define "proper" as "unbreakable", then by that definition I suppose
you are right. The problem is that we don't yet know how to decide if an
algorithm is "proper," by this definition.

For an example of people claiming to break real-world steganography with a
real tool (just the first listed by google):
http://www.outguess.org/detection.php

I'm sure you can find many steganographic algorithms for which there has not
yet been a tool written that can break it (and for which there have not yet
been papers published that highlight their weaknesses) but this is not a
guarantee of security. And of course if you want to hide one bit of data in
a 1 MB jpeg, I think few would argue that you can't do this discretely. If
you want to hide 500 kilobytes in this same file, I think few would argue
that this can be done discretely. So the question more precisely is what
bandwidth ratio is achievable for a given level of assurance that it can not
be discovered, and what steganographic techniques maximize assurance for a
given bandwidth ratio. I don't think anyone can yet answer that question
with confidence. (But maybe someone on this group will correct me?)

Ben


DSCOTT

unread,
Jan 3, 2003, 12:52:12 PM1/3/03
to
ben...@earthlink.net (Ben Mord) wrote in
<av4f4p$bqgi0$1...@ID-101018.news.dfncis.de>:

>
>If you define "proper" as "unbreakable", then by that definition I
>suppose you are right. The problem is that we don't yet know how to
>decide if an algorithm is "proper," by this definition.
>

No I didn't mean unbrakeable. I meant that I think it could be
almost impossible to prove that there is encrypted data in it. As
an extreme example suspise I send you a GIF where the data part
looks like snow. The resutling picture is pure snow garbage. You
might suspect its really encrypted data. You might run several
statisticaly tests on it and it could truely appear random. How would
you know if its encrypted.


I think bad stego code might be easy to spot. If you take the
last bits from each word and it spells out an ascii message or
is the image of a missle or object you can be pretty certain its
hidden there on purpose. I have played with writting message based
on the sorting of color palletes. I suspose I would suspect any
pallets that are not in some standard order as maybe haveing a secret
message. Or if I found on a hard drive two pictures that look
identical but the files are different it could be the differences
imply encrypted data. But its possible he changed formats a few
times and when brought back to same format it caused the differences.
Or even such things as noise level looking constant for first
part of picture file then abrutlly changing. Might imply person
who write the stego wasn't smart enough to change whole data set.
Then again could be a defect in camera that took picture.

Now if you had my code that created it and if you had a key that
creats readable text from this data part of the file you could be
reasonably certain that it was encrypted short of that I don' think
you could prove anything.

>For an example of people claiming to break real-world steganography with
>a real tool (just the first listed by google):
>http://www.outguess.org/detection.php

I did a quick look. I would not be surprised that it could find
and detect several common methods where the intent was to do modest
setgo to hide from casual observations. You have to realize commerical
code is mostly hype. Look at the DVD crap some 15 year broke it. Like
the special Adobe crap. I read there adverstising made it sound good
it sucked shit and when the russian exposed how piss poor it was he
was arrested. Commerial setgo programs have more money spent on
the hype then actaully trying to do secure stego. The code at
this organization will not dectect steg with just a little thought
in it. It might have some noise level detection where it flags
a file as to noisy but how does one prove it stego and not the
camera. You can't.

Ben Mord

unread,
Jan 3, 2003, 2:46:10 PM1/3/03
to

"DSCOTT" <daVvid_...@email.com> wrote in message
news:92F862EDCH110W...@130.133.1.4...

> ben...@earthlink.net (Ben Mord) wrote in
> <av4f4p$bqgi0$1...@ID-101018.news.dfncis.de>:
>
> >
> >If you define "proper" as "unbreakable", then by that definition I
> >suppose you are right. The problem is that we don't yet know how to
> >decide if an algorithm is "proper," by this definition.
> >
>
> No I didn't mean unbrakeable. I meant that I think it could be
> almost impossible to prove that there is encrypted data in it.

That's exactly what I mean by "breaking steganography." Actually retrieving
the information is a matter of breaking the encryption. The latter is much
more heavily researched and better understood.

[...]


> I think bad stego code might be easy to spot. If you take the
> last bits from each word and it spells out an ascii message or
> is the image of a missle or object you can be pretty certain its
> hidden there on purpose.

Yes, that would be a tad suspicious.

[...]


> Now if you had my code that created it and if you had a key that
> creats readable text from this data part of the file you could be
> reasonably certain that it was encrypted short of that I don' think
> you could prove anything.

I can't speak about that particular tool. But are you familiar with the
technique described in this paper, as well as the techniques proposed by the
other papers that it cites in its introduction?
http://citeseer.nj.nec.com/536589.html

[...]


> I did a quick look. I would not be surprised that it could find
> and detect several common methods where the intent was to do modest
> setgo to hide from casual observations. You have to realize commerical

> Look at the DVD crap some 15 year broke it.

[...]

That is an example of copy protection that requires you to put the hardware
containing the decryption key in the hands of your very adversary. This is
understandably a hard system to secure. If you know a way to do this
securely and cheaply, then you might consider an early retirement.

Ben


Douglas A. Gwyn

unread,
Jan 3, 2003, 1:38:50 PM1/3/03
to
Ben Mord wrote:
> If you define "proper" as "unbreakable", then by that definition I suppose
> you are right. The problem is that we don't yet know how to decide if an
> algorithm is "proper," by this definition.

Actually our researchers have devised steganographic methods
that are asymptotically as secure as their underlying encryption.
The basic idea is to modify the existing noise component in a
crypto-keyed manner.

Douglas A. Gwyn

unread,
Jan 3, 2003, 1:40:15 PM1/3/03
to
DSCOTT wrote:
> I think bad stego code might be easy to spot. If you take the
> last bits from each word and it spells out an ascii message ...

Indeed weak stego *is* relatviely easy to detect, and being
stego, detecting it is a form of break even if the embedded
message is never deciphered.

Ben Mord

unread,
Jan 3, 2003, 4:15:10 PM1/3/03
to

"Douglas A. Gwyn" <DAG...@null.net> wrote in message
news:3E15D8BA...@null.net...

Very interesting. This has been proven?

Asymptotic with respect to... carrier data to hidden data ratio? (For a
sufficiently large ratio, surely the defender's job becomes easy.)

Do you have a link to any papers about this work? I just found (but have not
yet read) this one, which looks promising:
http://citeseer.nj.nec.com/hopper02provably.html

Ben


DSCOTT

unread,
Jan 3, 2003, 5:59:04 PM1/3/03
to
ben...@earthlink.net (Ben Mord) wrote in
<av4pb6$bqlao$1...@ID-101018.news.dfncis.de>:

>
>I can't speak about that particular tool. But are you familiar with the
>technique described in this paper, as well as the techniques proposed by
>the other papers that it cites in its introduction?
>http://citeseer.nj.nec.com/536589.html
>

I did a quick look at paper. I notice this in section 4.
"the estimated message length was within a few percent of
the actual message" This to me implies its dectecting poorly
implemented crypto. If one is serious about stego in an image
you should always apply it to the total data section not just
the message length. Example I have an OTP of 2000 bytes.
I take a short message and transform it to a finfitely odd file
( a file if infinite length but last one a finite distance from
start) I then XOR this with the transformed message. I then say
I change the LSB data of the image in a GIF file. Maybe only
1000 bytes of data modified. But lets say the message ends in first
900 bytes. I change all the data in file. So no end of message
can be detected. The data has the same noise characteristics
throughout whole file. When data is recovered I only need to
XOR this random data stream till the data ends. to recover the message
which is assumed to be shorter than the stream of lsb bits from
the data.

No program can prove there is hidden data in this file. They can prove
that the LSB is noisy but so what. How can one prove noise versus
added data especially if they don't have the original file or have the
camera or device that made the picture. One could even go a step farther
and exaime the character of pictures from some camera itself and make
the changes fit other normal characteristics of that particular camera.
There are many ways.

In short you maybe able to prove data is noisy but I doubt you can prove
it was added if you don't have the device that made the picture.


>That is an example of copy protection that requires you to put the
>hardware containing the decryption key in the hands of your very
>adversary. This is understandably a hard system to secure. If you know a
>way to do this securely and cheaply, then you might consider an early
>retirement.
>

Actaully I already am early retired. Second as many small companies
found out even when they are better than say Micoshaft they still lose.
I once saw a show on patents that big corporation stole from others
and as Bill Gates proved its not quaility or honesty that wins it lawyers
and money that makes the difference. Writting a good protection scheme
is not really that hard its that the companys really don't care. Thats
what lawyers are for. Second I think it trival to protect the original data
but if one plays it on a TV you could always record it something else
sure it would lose some quality but this always can be done no method
is going to stop this mode of copying.

Douglas A. Gwyn

unread,
Jan 3, 2003, 5:22:52 PM1/3/03
to
Ben Mord wrote:
> Very interesting. This has been proven?

To my satisfaction, at any rate.

Ben Mord

unread,
Jan 3, 2003, 6:27:49 PM1/3/03
to

"Ben Mord" <ben...@earthlink.net> wrote in message
news:av4uhr$bsooc$1...@ID-101018.news.dfncis.de...
[...]

> Do you have a link to any papers about this work? I just found (but have
not
> yet read) this one, which looks promising:
> http://citeseer.nj.nec.com/hopper02provably.html
>

Actually, I'm having a very hard time penetrating this paper, and I'm having
some doubts.

One thing I find confusing is the emphasis placed on time, "partial draws",
"channel distribution", etc when their analysis is sufficiently abstracted
from the specific channel structure that they could dispense with the time
dimension (accept for the concept of sequential dialogue) without losing any
generality or useful conclusions. I worry that this arbitrary complexity is
masking an unstated assumption. (Namely, that unusual selection of messages
would not be suspicious in the way that unusual selection of bytes within a
message could be. More on that in a sec...)

I also don't understand how one can reach the dramatic conclusions they
reach about steganography while remaining at the impressive level of
abstraction from which this paper speaks to us. Somehow they define (and
prove the security of?) an algorithm without discussing the details of a
specific cover channel. I *think* the algorithm they describe works by
repeating earlier messages verbatim, and by the selection of which messages
to repeat they thus establish a covert channel. It is hard to imagine how
else you could attempt steganography without digging into the dirty details
of a specific choice of cover channel, although even here some implicit
assumptions are being made. This presumes that repeated messages are not in
themselves considered suspicious in the particular cover channel being used.

So, I suggest the following attack. Ward deems there to be covert
communication if messages are repeated verbatim when such repetition would
not naturally occur in the cover channel.

Or alternatively, Ward deems there to be covert communication if message
exchange doesn't make sense when considered as a conversation. For example,
the following dialogue would look a little odd: "They say my dog died
today", "Isn't it great you went to the gym?", "But sometimes the sky *is*
blue. Hey - seen Sam lately?", "I really like split-pea soup!". Not to say
that this couldn't be encoded better, but I'm just illustrating that this
"implementation detail" of how you discretely encode the data in a
particular channel is really the whole of steganography - you can't abstract
it away. Messy details like whether messages can be repeated, and how often,
whether there are restrictions on sensible ordering, and how large the space
of messages are would all be critical to deciding if this algorithm can be
used securely, and any attempt to analyze its security must consider such
issues that are specific to a particular cover channel.

Or am I misreading the algorithm description?

Douglas - did you have another paper? I think you were hinting that you
might...

Ben


Douglas A. Gwyn

unread,
Jan 3, 2003, 11:17:05 PM1/3/03
to
Ben Mord wrote:
> Douglas - did you have another paper?

There are several, the best known apparently being:
"Spread Spectrum Image Steganography" by Lisa M. Marvel,
Charles G. Boncelet, Jr. and Charles T. Retter in
IEEE Transaction on Image Processing, Vol. 8, No. 8
(August 1999), pp. 1075-1083.
Of course there has been more work since then..

Richard Clayton

unread,
Jan 5, 2003, 9:20:00 AM1/5/03
to
In article <av4pb6$bqlao$1...@ID-101018.news.dfncis.de>, Ben Mord
<ben...@earthlink.net> writes

>I can't speak about that particular tool. But are you familiar with the
>technique described in this paper, as well as the techniques proposed by the
>other papers that it cites in its introduction?
>http://citeseer.nj.nec.com/536589.html

I would suggest also looking at Jessica Fridrich's later work... and in
particular at the 5th Info Hiding Workshop last October where she
presented "Steganalysis of JPEG Images: Breaking the F5 Algorithm" which
also breaks OutGuess as well as F5.

It was only one amongst several other papers - for example from Westfeld
[author of F5] attacking low embedding rates.

In particular, "Detecting Hidden Messages Using Higher-Order Statistics
and Support Vector Machines" (Lyu & Farid) showed how very hard it is to
make stego look like "noise" when more and more statistical measures are
being calculated and checked :-(

The conclusion I drew was that there is so much regularity in cover
images that we're going to have to expect to add far less stego signal
than has been attempted up to now if it is to remain undetected.

--
richard Richard Clayton

They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety. Benjamin Franklin

David Wagner

unread,
Jan 6, 2003, 10:11:13 PM1/6/03
to
Douglas A. Gwyn wrote:
>Actually our researchers have devised steganographic methods
>that are asymptotically as secure as their underlying encryption.
>The basic idea is to modify the existing noise component in a
>crypto-keyed manner.

The real crux of the issue is "How good does your model of the covertext
have to be?" Getting good models is very hard. As a result, the bad
guy's model is likely to be much better than the good good's model,
if the bad guy has more resources to spend on this. And as a result,
the bad guy can usually win in practice.

I betcha that any provable security results assume that the model of the
covertext is perfectly known to the good guys. If not, I'd love to be
proven wrong. Do I win the bet?

Ben Mord

unread,
Jan 7, 2003, 3:37:40 PM1/7/03
to

"DSCOTT" <daVvid_...@email.com> wrote in message
news:92F8AA9A4H110W...@130.133.1.4...

> ben...@earthlink.net (Ben Mord) wrote in
> <av4pb6$bqlao$1...@ID-101018.news.dfncis.de>:
>
[...]

>
> In short you maybe able to prove data is noisy but I doubt you can prove
> it was added if you don't have the device that made the picture.
>
[...]

I think David Wagner just summarized the fundamental issue very well, and I
won't restate it here to avoid forking discussion on that particular point.
(Is there a conventional way to reference or "link" to other posts? There
must be...)

But I think there is confusion over the concept of "proof" and what this
really means that might be adding confusion.

Suppose I make a magic black box which when fed a jpeg returns true if it
thinks it contains stego, and false otherwise. Suppose I test this box by
running a zillion jpegs through it made from a zillion makes and models of
cameras, scanners, etc, including images which have been heavily edited in
photoshop, gimp, and other popular tools. Suppose it returned false for all
of them. (Very low rate of false positives.) In fact, suppose this testing
was done by a third party. Suppose I now use a steganographic program to add
hidden data, and I do this to a zillion different photos of different types,
and this magic black box returns true with every test I can think of with a
jpeg containing stego. (Very low rate of false negatives.)

Now suppose you are an agent that has infiltrated some area of organized
crime, but now you are suspected of spying against your peers in the gang.
Suppose it just so happens that you've been emailing images of cats, dogs,
etc to the local FBI office and it just so happens that my magic black box
returns true when fed these images. Hmm... By the standards of a
mathematician proving a theorem, you're right - this doesn't prove a thing,
but who is really going to care? And notice that this pragmatic proof
doesn't care how the black box works - its inventor is free to employ
whatever statistical methods seem to work, because as long as it
demonstrates sufficiently low false positives in the field, that's good
enough. Similar reasoning is used with fingerprint matching, and other
traditional forms of "proof" where at a microscopic technical level there is
a pinch of the subjective.

Now suppose you are a law abiding entity who is attempting to subvert
criminal traffic analysis being employed against you. Or suppose you are a
legitimate user of cryptography who seeks to hedge against possible
weaknesses yet to be discovered in your cryptography by hiding your
encrypted data with steganographic techniques. Or suppose you are attacking
a one-way data pump in a multi-level security system. The standard of proof
to which your enemies hold themselves might be fairly minimal, if they're
only concerned with, say, directing their cryptanalytic efforts towards data
that is probably ciphertext and not just noise, or if they're just concerned
with shutting down possible covert channels rather than pursuing legal
action.

In any case, the goal of the steganographer should be to make it impossible
to design a black box like I describe that has both a false positive and a
false negative rate significantly below 50%. If a potential covert channel
is monitored over time and continuously appears suspicious, this consistency
could also be used to steadily increase confidence that there is indeed
covert communication, and as shown earlier this can also be combined with
other more circumstantial evidence. In unusual situations such as times of
war or under a tyrannical dictator, or when the response is sufficiently
moderate to require little justification, standards of proof may be
significantly lowered. For any of these reasons, this requirement may become
very strict. It depends on the context, and it is poor practice to assume
too much about context when designing cryptographic primitives.

Ben


DSCOTT

unread,
Jan 7, 2003, 3:55:15 PM1/7/03
to
ben...@earthlink.net (Ben Mord) wrote in
<avfds9$f2fej$1...@ID-101018.news.dfncis.de>:

>
>Suppose I make a magic black box which when fed a jpeg returns true if
>it thinks it contains stego, and false otherwise. Suppose I test this
>box by running a zillion jpegs through it made from a zillion makes and
>models of cameras, scanners, etc, including images which have been
>heavily edited in photoshop, gimp, and other popular tools. Suppose it
>returned false for all of them. (Very low rate of false positives.) In
>fact, suppose this testing was done by a third party. Suppose I now use
>a steganographic program to add hidden data, and I do this to a zillion
>different photos of different types, and this magic black box returns
>true with every test I can think of with a jpeg containing stego. (Very
>low rate of false negatives.)
>
>

But supose no such box exits. Which is more likely?

Douglas A. Gwyn

unread,
Jan 7, 2003, 4:52:27 PM1/7/03
to
DSCOTT wrote:
> But supose no such box exits. Which is more likely?

Ben did say:

> > In any case, the goal of the steganographer should be to make

> > it impossible to design a black box like I describe ...

Ben Mord

unread,
Jan 7, 2003, 6:31:46 PM1/7/03
to

"David Wagner" <d...@mozart.cs.berkeley.edu> wrote in message
news:avdggh$th0$3...@agate.berkeley.edu...

Well said!

You describe this as a race between two adversaries to develop the more
accurate cover channel model.

That advantage in such a race also belongs to the one who moves last,
because they can leverage more evolved technology than the one who moves
first. In this game, the defender moves first (composes hidden message), and
the attacker moves last (looks for said message.) The more time separates
these two moves, the more advantage belongs to the attacker. This is why we
must hold any defensive technique to higher standards - because it must
remain secure against the attacks of tomorrow. The faster the pace of
evolution, the more advantage belongs to the attacker. Symmetric
cryptography has settled down enough that this is (hopefully) less of a
concern. Steganography (Steganology?) however is still evolving quickly, so
future proofness remains a huge concern.

I also wonder how steganography could ever settle down. After all, the range
and nature of ubiquitous, benign-looking cover channels available changes as
technology evolves, is adopted, and is retired. It seems likely that these
models will always be playing catch-up, and some plateau of stability
therefore could never be reached.

Ironically, the job of cryptographers is to make their own field as stable
(aka uneventful, boring) as possible. But I guess that's true of most
professions. I suppose the next career jump once this is achieved is to
extend these extreme high-assurance levels to progressively more abstract
layers of the information system.

Ben


Benjamin Goldberg

unread,
Jan 7, 2003, 7:58:25 PM1/7/03
to
Ben Mord wrote:

> David Wagner wrote:
> > Douglas A. Gwyn wrote:
> > >Actually our researchers have devised steganographic methods
> > >that are asymptotically as secure as their underlying encryption.
> > >The basic idea is to modify the existing noise component in a
> > >crypto-keyed manner.
> >
> > The real crux of the issue is "How good does your model of the
> > covertext have to be?" Getting good models is very hard. As a
> > result, the bad guy's model is likely to be much better than the
> > good good's model, if the bad guy has more resources to spend on
> > this. And as a result, the bad guy can usually win in practice.
> >
> > I betcha that any provable security results assume that the model of
> > the covertext is perfectly known to the good guys. If not, I'd love
> > to be proven wrong. Do I win the bet?
>
> Well said!
>
> You describe this as a race between two adversaries to develop the
> more accurate cover channel model.
>
> That advantage in such a race also belongs to the one who moves last,
> because they can leverage more evolved technology than the one who
> moves first. In this game, the defender moves first (composes hidden
> message), and the attacker moves last (looks for said message.)

Actually, *some* attackers have an even greater advantage -- they're not
looking for a hidden message, they're just assuming one is there and
trying to remove it without significantly altering the cover message.

Specifically, removing a watermark from an image or sound file, while
keeping the image the same to a human eye, and keeping the sounds the
same to a human ear.

> The more time separates these two moves, the more advantage belongs to
> the attacker. This is why we must hold any defensive technique to
> higher standards - because it must remain secure against the attacks
> of tomorrow. The faster the pace of evolution, the more advantage
> belongs to the attacker. Symmetric cryptography has settled down
> enough that this is (hopefully) less of a concern. Steganography
> (Steganology?) however is still evolving quickly, so future proofness
> remains a huge concern.

Steganography is latin for 'secret writing,' and I suppose that
'steganology' would be 'the study of secrets.'

I think that the word you want is 'steganographology,' which would be
'the study of secret writing.'

> I also wonder how steganography could ever settle down. After all, the
> range and nature of ubiquitous, benign-looking cover channels
> available changes as technology evolves, is adopted, and is retired.
> It seems likely that these models will always be playing catch-up, and
> some plateau of stability therefore could never be reached.

Well, for a single given cover chanel, one will eventually develop a
model which will be as good as it possibly can be.

Given that there's always *some* randomness present in the model (unless
the cover channel is the transmission of files whose precise binary
representation is already known to the attacker), a 'good guy' who
merely needs to avoid being detected can merely reduce the number of
bits injected to a really tiny number, with a really large cover file.

Suppose I need to transmit a single bit, and I've got a really huge
digital photo I want to use to hide it in. All I need is to tell my
friend before hand "The one-bit message will be the total number of
'one' bits in the message, mod 2". I would then (if necessary) flip a
single bit of the image, and send it. Whether or not there's a message
present will be completely and utterly undetectable to any enemy.

It's also easy to *remove* this stegano, but I might not be converned
about that.

> Ironically, the job of cryptographers is to make their own field as
> stable (aka uneventful, boring) as possible. But I guess that's true
> of most professions. I suppose the next career jump once this is
> achieved is to extend these extreme high-assurance levels to
> progressively more abstract layers of the information system.

--
$..='(?:(?{local$^C=$^C|'.(1<<$_).'})|)'for+a..4;
$..='(?{print+substr"\n !,$^C,1 if $^C<26})(?!)';
$.=~s'!'haktrsreltanPJ,r coeueh"';BEGIN{${"\cH"}
|=(1<<21)}""=~$.;qw(Just another Perl hacker,\n);

Richard Clayton

unread,
Jan 7, 2003, 8:05:27 PM1/7/03
to
In article <3E1B77B1...@earthlink.net>, Benjamin Goldberg
<gol...@earthlink.net> writes

>Actually, *some* attackers have an even greater advantage -- they're not
>looking for a hidden message, they're just assuming one is there and
>trying to remove it without significantly altering the cover message.
>
>Specifically, removing a watermark from an image or sound file, while
>keeping the image the same to a human eye, and keeping the sounds the
>same to a human ear.

there's a similar aim in the "active warden" community ... where they're
trying to develop filtering systems to sit at the border of Los Alamos
(or wherever) that will pass out legitimate messages but will not allow
embedded secrets to escape (as stego material within the legitimate
material)

[snip]

>Suppose I need to transmit a single bit, and I've got a really huge
>digital photo I want to use to hide it in. All I need is to tell my
>friend before hand "The one-bit message will be the total number of
>'one' bits in the message, mod 2". I would then (if necessary) flip a
>single bit of the image, and send it. Whether or not there's a message
>present will be completely and utterly undetectable to any enemy.

actually, if it's a JPEG then Jessica would claim to spot the one
altered bit :)

Ben Mord

unread,
Jan 7, 2003, 9:16:22 PM1/7/03
to
Benjamin Goldberg wrote:
[...]

>
> Actually, *some* attackers have an even greater advantage -- they're not
> looking for a hidden message, they're just assuming one is there and
> trying to remove it without significantly altering the cover message.
>
> Specifically, removing a watermark from an image or sound file, while
> keeping the image the same to a human eye, and keeping the sounds the
> same to a human ear.
[...]

The security goals of digital watermarks seem very different than the
goals of data hiding. Are both refered to as steganography? I always
reserved that term for data hiding.

> I think that the word you want is 'steganographology,' which would be
> 'the study of secret writing.'

[...]

Oh, right. Graph = writing. I guess steganographology is what I was
looking for, but it is longer than I hoped. What do you call someone who
breaks steganographic algorithms?

Ben

Benjamin Goldberg

unread,
Jan 7, 2003, 11:29:20 PM1/7/03
to
Ben Mord wrote:
>
> Benjamin Goldberg wrote:
> [...]
> >
> > Actually, *some* attackers have an even greater advantage -- they're
> > not looking for a hidden message, they're just assuming one is there
> > and trying to remove it without significantly altering the cover
> > message.
> >
> > Specifically, removing a watermark from an image or sound file,
> > while keeping the image the same to a human eye, and keeping the
> > sounds the same to a human ear.
> [...]
>
> The security goals of digital watermarks seem very different than the
> goals of data hiding. Are both refered to as steganography? I always
> reserved that term for data hiding.

Although they have very different goals, the technologies used are
nearly the same; like public key encryption and public key signatures.

I'm not sure whether or not you might call watermarking stego, but I
expect that anything usable for one is usable for the other.

> > I think that the word you want is 'steganographology,' which would
> > be 'the study of secret writing.'
> [...]
>
> Oh, right. Graph = writing. I guess steganographology is what I was
> looking for, but it is longer than I hoped. What do you call someone
> who breaks steganographic algorithms?

I suspect that the word "cryptographer" would adequately cover the
field.

Corners

unread,
Jan 8, 2003, 1:39:23 AM1/8/03
to

"David Wagner" <d...@mozart.cs.berkeley.edu> wrote in message
news:avdggh$th0$3...@agate.berkeley.edu...
> Douglas A. Gwyn wrote:
> >Actually our researchers have devised steganographic methods
> >that are asymptotically as secure as their underlying encryption.
> >The basic idea is to modify the existing noise component in a
> >crypto-keyed manner.
>
> The real crux of the issue is "How good does your model of the covertext
> have to be?" Getting good models is very hard. As a result, the bad
> guy's model is likely to be much better than the good good's model,
> if the bad guy has more resources to spend on this. And as a result,
> the bad guy can usually win in practice.

The "bad guys" (steganography detectors) have another advantage. They
don't actually need a better model, they only need a discriminator function.
For the the "good guys" (steganography users) having a better overall model
than the bad guys is not sufficient. It has to be better than the bad
guys' in every measurable way.

>
> I betcha that any provable security results assume that the model of the

> covertext is perfectly known to the good guys...

Douglas A. Gwyn

unread,
Jan 8, 2003, 1:47:19 AM1/8/03
to
Ben Mord wrote:
> Well said!

But wrong. The reason we're working solely in the noise
channel is that there are inherent variations in the
amount of noise, so provided that the stego signal power
is appreciably lower than the natural noise power, the
signal is not detectable (assuming crypto keying etc. as
is normal for spread-spectrum stealth communications).

Bryan Olson

unread,
Jan 8, 2003, 7:08:52 AM1/8/03
to

Ignoring the real problem isn't going to make it go away. Hiding
ciphertext in random noise is the easy part. How do you what in
the covertext really is random? You can either assume the model
of the covertext captures everything known to the attacker
(which is what David Wagner was talking about) or make extremely
conservative assumptions (which is what I was talking about with
hiding a three-bit message in a JPEG).

Wagner was correct. Covertext modeling is *the* problem in
steganography. Papers that assume it away may be able to prove
theorems, but they will not provide secure and efficient stego
systems.


--
--Bryan

Michael Sierchio

unread,
Jan 8, 2003, 11:42:43 AM1/8/03
to
Our friends in MD, at that place named after a Union general in the
Civil War, are rumored to have a very sophisticated apparatus for
uncovering steganographic messages. They've even demonstrated it
to members of the press.

DSCOTT

unread,
Jan 8, 2003, 11:47:54 AM1/8/03
to
ku...@tenebras.com (Michael Sierchio) wrote in
<V8WcneuPXfy...@speakeasy.net>:

Yeah demonstrate to group that would not only not be able to
question but would not be able to understand it. Question is why
would they show it at all. Makes one wonder if its like a lie dectector
hype in that you would want to create the myth that it works.

Michael Sierchio

unread,
Jan 8, 2003, 1:28:17 PM1/8/03
to
DSCOTT wrote:

> Yeah demonstrate to group that would not only not be able to

> question but would not be able to understand it. ...

On that you're mistaken. Some staff writers for the NY Times, to
name one example, have more than a rudimentary understanding of
SIGINT, COMINT, cryptography, etc.

DSCOTT

unread,
Jan 8, 2003, 1:57:00 PM1/8/03
to
ku...@tenebras.com (Michael Sierchio) wrote in
<pdqcnTn9urN...@speakeasy.net>:

>
>On that you're mistaken. Some staff writers for the NY Times, to
>name one example, have more than a rudimentary understanding of
>SIGINT, COMINT, cryptography, etc.
>
>
>

I have not met such reporters those that I have seem to
have an inflated opionion that they know everything. I think
Katie on NBC is what I would call a typtical over pampered
know it all that knows very little. Howver I haven't meet
most of them so maybe the NY times has same that uderstand
somthing on the subject. I also am not sure just what a
staff writer is. Do they only write. It was mentioned about
a demo. Are staff writers the ones who go to the demos?

Mok-Kong Shen

unread,
Jan 8, 2003, 5:07:07 PM1/8/03
to

For stego with images, there is the practical
difficulty, as far as I am aware, that the stego bits
wouldn't be intact thru a lossy compression that
is normally applied to such materials. Could someone
tell how that problem is solved? Thanks.

M. K. Shen

Ben Mord

unread,
Jan 8, 2003, 6:29:27 PM1/8/03
to

"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:3E1CA10B...@t-online.de...

I would guess you do this by applying the steganography after compression.
If you want to make it very robust and resistant to deliberate tampering
e.g. similar to a digital watermark, then I would guess you would employ a
great deal of error correction coding.

Hmm, but what if the data coding algorithm used to simulate the natural
noise of the cover channel introduced ugly error propogation
characteristics? I suppose that could severely limit the benifit of error
correction codes. I imagine that limited error propogation must be a desired
quality of steganographic algorithms where digital watermarking is
concerned. After all, if you applied the error correction coding *after* the
"noise simulation encoding" (whatever its called) then the introduced
redundancy would defeat the stego by reintroducing detectable patterns into
the fake noise, so it could only be applied prior to the "noise simulation
encoding". But then these considerations are part of why I would expect
steganography and digital watermarking to be considered two very distinct
fields of study whose technologies overlap in only limited areas, and only
through happy coincidence. It seems like their disperate goals would tend to
conflict with each other. My voice trails off... and I now understand why
you ask this question. This must be the subject of several long papers.

Ben


Mok-Kong Shen

unread,
Jan 8, 2003, 7:31:50 PM1/8/03
to

Ben Mord wrote:
>
> "Mok-Kong Shen" <mok-ko...@t-online.de> wrote:

> > For stego with images, there is the practical
> > difficulty, as far as I am aware, that the stego bits
> > wouldn't be intact thru a lossy compression that
> > is normally applied to such materials. Could someone
> > tell how that problem is solved? Thanks.
>

> I would guess you do this by applying the steganography after compression.
> If you want to make it very robust and resistant to deliberate tampering
> e.g. similar to a digital watermark, then I would guess you would employ a
> great deal of error correction coding.

Most descriptions of image stego say doing some
modification of the LSB of certain chosen pixels.
That operation is clearly before compression, not
after. The compressions for images commonly employ
fourier transforms, if I don't err. Any modification
after compression would thus have quite different
effects on the decompressed images in comparison to
(direct) modifications of the LSB of the pixels,
I suppose.

M. K. Shen

Richard Clayton

unread,
Jan 8, 2003, 8:12:08 PM1/8/03
to
In article <3E1CA10B...@t-online.de>, Mok-Kong Shen <mok-
kong...@t-online.de> writes

>For stego with images, there is the practical
>difficulty, as far as I am aware, that the stego bits
>wouldn't be intact thru a lossy compression that
>is normally applied to such materials. Could someone
>tell how that problem is solved? Thanks.

waving ones hands wildly, one would reply:

this is usually seen as a problem for watermarks rather than stego per
se. A typical approach is to do a Fourier transform, add the signal in
that domain and then transform back again.... leaving the signal spread
all over the image in a rather unobvious way

... the result is (if you do it right) that the signal is rather more
resistant to alterations applied directly to the image

Bryan Olson

unread,
Jan 8, 2003, 9:18:56 PM1/8/03
to
Mok-Kong Shen wrote:
>
> Ben Mord wrote:
>
>>"Mok-Kong Shen" wrote:
>
>>>For stego with images, there is the practical
>>>difficulty, as far as I am aware, that the stego bits
>>>wouldn't be intact thru a lossy compression that
>>>is normally applied to such materials. Could someone
>>>tell how that problem is solved? Thanks.
>>
>>I would guess you do this by applying the steganography after
compression.

Ben guesses correctly.

> Most descriptions of image stego say doing some
> modification of the LSB of certain chosen pixels.

Then they're either not talking about using lossy compression,
or perhaps have not thought it through.


--
--Bryan

bob

unread,
Jan 8, 2003, 9:19:33 PM1/8/03
to
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:3E1CC2F6...@t-online.de...
...

> Most descriptions of image stego say doing some
> modification of the LSB of certain chosen pixels.
> That operation is clearly before compression, not
> after. The compressions for images commonly employ
> fourier transforms, if I don't err. Any modification
> after compression would thus have quite different
> effects on the decompressed images in comparison to
> (direct) modifications of the LSB of the pixels,
> I suppose.
>
> M. K. Shen

I would think that, realistically, when doing stego, one would have to
simply use lossless compression on the images. I do a bit of photography,
and I scan my images into my computer. I do not use lossy compression (I've
never understood why anyone would spend $$$ on premium film and premium
lenses and a high res scanner and then use a lossy compression algorithm).
Heck, bandwidths are getting good enough that one ***MIGHT*** consider
simply transmitting uncompressed images. Maybe not yet.

The concept of modifying the compressed file would require a very detailed
knowledge of the compression algorithm. Changing random bits of a
compressed file would almost certainly destroy the integrity of the picture,
making it blindingly obvious that the picture contained stego. More than
likely, to be effective, one would have to write/modify the compression
program to incorporate stego. Not impossible, but a serious challenge. Hey
Tom, are you busy? 8^)


Paul Crowley

unread,
Jan 8, 2003, 10:25:08 PM1/8/03
to
Richard Clayton <ric...@highwayman.com> writes:
> this is usually seen as a problem for watermarks rather than stego per
> se. A typical approach is to do a Fourier transform, add the signal in
> that domain and then transform back again.... leaving the signal spread
> all over the image in a rather unobvious way
>
> ... the result is (if you do it right) that the signal is rather more
> resistant to alterations applied directly to the image

though Markus Kuhn's webpage includes a very effective algorithm
called StirMark for destroying the message in this kind of stego
without visibly altering the image. It may be of course that stego
has caught up with StirMark since I last looked - reading the paper on
it is about the limit of my knowledge on the subject...
--
__ Paul Crowley
\/ o\ s...@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/

Richard Clayton

unread,
Jan 9, 2003, 3:35:14 AM1/9/03
to
In article <87n0mbg...@saltationism.subnet.hedonism.cluefactory.org.
uk>, Paul Crowley <pa...@JUNKCATCHER.ciphergoth.org> writes

some watermarking algorithms now do well against Stirmark ... but there
are new attacks as well. Stirmark Mark II is Checkmark:

http://watermarking.unige.ch/Checkmark/

Mok-Kong Shen

unread,
Jan 9, 2003, 1:38:40 PM1/9/03
to

The problem seems to be that, if one doesn't use the
common (lossy) compression, then one is being suspected
of employing stego. If one uses lossy compression but
embeds stego in the compressed stuff, then the effect
of modification could presumably effect the quality of
the image to such an extent that presence of stego would
more easily be evident. See also the follow-up of bob.

M. K. Shen

David Wagner

unread,
Jan 13, 2003, 2:36:50 AM1/13/03
to
"David Wagner" <d...@mozart.cs.berkeley.edu> wrote:
> The real crux of the issue is "How good does your model of the covertext
> have to be?" Getting good models is very hard. As a result, the bad
> guy's model is likely to be much better than the good good's model,
> if the bad guy has more resources to spend on this. And as a result,
> the bad guy can usually win in practice.
>
> I betcha that any provable security results assume that the model of the
> covertext is perfectly known to the good guys. If not, I'd love to be
> proven wrong. Do I win the bet?

Nick Hopper has gently pointed out to me in private email that I lose
the bet. (Good thing I didn't specify the stakes -- phew, that was a
close one!)

Anyway, I was in error. The following paper gives a counterexample.
N.J. Hopper, J. Langford, L. von Ahn, "Provably Secure Steganography",
CRYPTO 2002. http://eprint.iacr.org/2002/137/
The authors describe a protocol that is secure as long as the good guys
can sample from the distribution. The good guys do *not* need a perfect
model of the distribution of the covertext in their scheme.

In retrospect, I should have known this. A standard scheme that has
been proposed many times in the past for sending one bit B secretly is
the following:
Let F be a PRF with one-bit output and K be the shared key. Compose a
cover message M. Send it if F_K(M) = B, else re-generate another
message (independent of the previous one!) and repeat.
If I understand correctly, one of things the CRYPTO 2002 paper does is
to make this rough idea precise, work out a reasonable threat model,
and analyze the resulting scheme formally.

Sampling from the covertext distribution ought to be considerably easier
than building a perfect model of the covertext distribution. Of course,
the independence assumption requires some care in implementation, but
it is not a priori unreasonable.

Anyway, I apologize profusely for my error, and I hope the authors of
the CRYPTO 2002 paper will forgive me for my oversight. Please let me
know if I've made any further errors in this post. And my gratitude
to Nick Hopper for pointing out my error.

Stefan Katzenbeisser

unread,
Jan 13, 2003, 3:10:13 AM1/13/03
to
In article <avtqai$p1$1...@agate.berkeley.edu>, David Wagner wrote:

> Nick Hopper has gently pointed out to me in private email that I lose
> the bet. (Good thing I didn't specify the stakes -- phew, that was a
> close one!)
>
> Anyway, I was in error. The following paper gives a counterexample.
> N.J. Hopper, J. Langford, L. von Ahn, "Provably Secure Steganography",
> CRYPTO 2002. http://eprint.iacr.org/2002/137/
> The authors describe a protocol that is secure as long as the good guys
> can sample from the distribution. The good guys do *not* need a perfect
> model of the distribution of the covertext in their scheme.

Be careful: to my knowledge, the paper is flawed. At least there was
an interesting presentation at IHW2002 by Ivo Desmedt who discovered some
errors in their construction and proofs...


-S

Nick Hopper

unread,
Jan 13, 2003, 12:00:13 PM1/13/03
to kat...@dbai.tuwien.ac.at

To my knowledge, there are no flaws in the paper indexed at the IACR
eprint server. I have not seen Yvo Desmedt's presentation, nor (despite a
google search) have I read a paper describing this work. However, Desmedt
made a presentation at the CRYPTO 2002 rump session in which he claimed
that our paper was flawed because construction 2 in our paper requires a
function which is unbiased over the covertext distribution. This was
clearly stated in our paper, and we point out that it is not always justified.

Furthermore, any channel which does not admit a balanced function can be
"compiled" into a meta-channel (the product distribution of \omega(\log k)
independent draws from the original channel) which admits an efficient
negligibly-biased function, which satisfies the conditions for that protocol.

In addition, our construction 1, as presented in the IACR eprint version,
has security reducible to the assumption that a certain function ensemble
is pseudorandom, and that the sender can draw two independent samples from
the covertext distribution. The proof is simple, and uses only standard
notions from complexity theory and probability theory. The construction is
not of much practical interest, on the other hand, because it achieves
very low bandwidth. It is useful mainly as a proof of concept, which was
the intent of the paper in the first place.

I would be very interested to see any written summary of this presentation.

-Nick

Paul Rubin

unread,
Jan 13, 2003, 12:16:14 PM1/13/03
to
d...@mozart.cs.berkeley.edu (David Wagner) writes:
> In retrospect, I should have known this. A standard scheme that has
> been proposed many times in the past for sending one bit B secretly is
> the following:
> Let F be a PRF with one-bit output and K be the shared key. Compose a
> cover message M. Send it if F_K(M) = B, else re-generate another
> message (independent of the previous one!) and repeat.
> If I understand correctly, one of things the CRYPTO 2002 paper does is
> to make this rough idea precise, work out a reasonable threat model,
> and analyze the resulting scheme formally.

The amount of covertext you need to process (though not transmit) in
that scheme is exponential in the size of the hidden message you want
to send in a given cover message. I wonder if there's a proof that
you can't do any better.

Ben Mord

unread,
Jan 13, 2003, 3:05:58 PM1/13/03
to

"David Wagner" <d...@mozart.cs.berkeley.edu> wrote in message
news:avtqai$p1$1...@agate.berkeley.edu...

> "David Wagner" <d...@mozart.cs.berkeley.edu> wrote:
> > The real crux of the issue is "How good does your model of the covertext
> > have to be?" Getting good models is very hard. As a result, the bad
> > guy's model is likely to be much better than the good good's model,
> > if the bad guy has more resources to spend on this. And as a result,
> > the bad guy can usually win in practice.
> >
> > I betcha that any provable security results assume that the model of the
> > covertext is perfectly known to the good guys. If not, I'd love to be
> > proven wrong. Do I win the bet?
>
> Nick Hopper has gently pointed out to me in private email that I lose
> the bet. (Good thing I didn't specify the stakes -- phew, that was a
> close one!)

I think you still win the beer - see below.

> Anyway, I was in error. The following paper gives a counterexample.
> N.J. Hopper, J. Langford, L. von Ahn, "Provably Secure Steganography",
> CRYPTO 2002. http://eprint.iacr.org/2002/137/
> The authors describe a protocol that is secure as long as the good guys
> can sample from the distribution. The good guys do *not* need a perfect
> model of the distribution of the covertext in their scheme.

*and* as long as each cover message does not change that distribution from
which subsequent cover messages must be drawn! I assert (without proof) that
this latter (and I think unstated?) assumption fails on most real-world
cover channels. In an attempt to prove that it fails on at least one choice
of cover channel, I now offer a counter example of construction 2. (I
believe analogous counter examples exist for construction 1 as well, but
lets first see how this one flies.)

As an admittedly extreme example to illustrate that this assumption can
fail, consider this naive attempt at implementing construction 2. I request
an html page from a server via HTTP, and it responds with data. However,
this is the cover story - it is actually sending covert data. In its
response, each byte represents a bit. Each byte is chosen as described by
Construction 2. The bytes of other natural web pages have been carefully
sampled, so that the odds of any particular byte value occurring in a
particular position of my cover web page matches that of your typical web
page. Let's look at that more closely. What I did is I decomposed other
natural web pages byte by byte, I counted the number of times that each byte
value appeared, drew a distribution curve, and then I sample this same
distribution for every byte in my page. Clearly, I am assuming that the
probability distribution for byte 2 should be identical to that for byte 1,
and I am also assuming that the selection of byte 1 does not affect the
probability distribution for byte 2. Ditto with bytes 3, 4, 5, etc...

Will this fool anybody? No. It *looks* like random ciphertext, and it
certainly isn't valid HTML. Granted, "<" will show up more often than, say,
")", but a typical portion of my cover "web page" source might look like
<H@><ShRi<A<AiF>AOeu>, rather than, say, <T1>GNU Fan Page</T1>. I believe
this is an example of Construction 2 in that paper, and yet it is provably
insecure. (Apologies if I violate an *explicit* assumption in the paper,
please tell me which one I missed. Further apologies if it in fact deviates
from construction 2, but I don't think it does.) Assuming no rebuttal to
this counter-example, then what went wrong?

For starters, it is not just the variance of each byte value that we care
about. It is also the covariance of that byte value with its neighbors - and
that's just the next level of complexity. To take a step back, get our heads
out of the statistics, and really embrace the complexity that we have to
deal with, we can also state that this cover page has to be valid html, has
to have coherent English (or French or whatever) text, has to have a subject
that is topical to the websites served by that server, have to have
hyperlinks that point to other pages, has to have a topic that is likely to
be of interest to me, have a writing style consistent with other pages,
etc... What am I doing right now? I am modeling the cover channel. There is
just no getting around that.

Ben

Nick Hopper

unread,
Jan 13, 2003, 4:02:32 PM1/13/03
to
Ben Mord wrote:
> Will this fool anybody? No. It *looks* like random ciphertext, and it
> certainly isn't valid HTML. Granted, "<" will show up more often than, say,
> ")", but a typical portion of my cover "web page" source might look like
> <H@><ShRi<A<AiF>AOeu>, rather than, say, <T1>GNU Fan Page</T1>. I believe
> this is an example of Construction 2 in that paper, and yet it is provably
> insecure. (Apologies if I violate an *explicit* assumption in the paper,
> please tell me which one I missed. Further apologies if it in fact deviates
> from construction 2, but I don't think it does.) Assuming no rebuttal to
> this counter-example, then what went wrong?
>
> For starters, it is not just the variance of each byte value that we care
> about. It is also the covariance of that byte value with its neighbors - and
> that's just the next level of complexity. To take a step back, get our heads
> out of the statistics, and really embrace the complexity that we have to
> deal with, we can also state that this cover page has to be valid html, has
> to have coherent English (or French or whatever) text, has to have a subject
> that is topical to the websites served by that server, have to have
> hyperlinks that point to other pages, has to have a topic that is likely to
> be of interest to me, have a writing style consistent with other pages,
> etc... What am I doing right now? I am modeling the cover channel. There is
> just no getting around that.

You have missed the fact that we explicitly model this dependence in our
paper via our definition of a channel. It is nonstandard, so we devote a
page to explaining this model.

Constructions 1,2, and 4 in our paper require the ability to make (on
average 2) independent draws from the distribution on covertexts which is
conditioned on the history of symbols/documents/messages already
transmitted. We also explicitly require that every one of these
conditional distributions has 1 bit of minimum entropy. So the choice of
what constitutes a symbol must be a long enough string that no history of
symbols results in a distribution on the next symbol where one symbol has
probability greater than 1/2. This can be weakened to requiring non-zero
minimum entropy... but if your channel distribution has low minimum
entropy in this sense (conditioned on previous symbols) then it is
unlikely that an unbiased function will exist, which makes Construction 2
useless.

Note that anyone who can send innocent messages over a channel can already
make one draw from any of these conditional distributions. The major
obstacle is in going from one draw to two independent draws. Regardless,
there is no efficient way to extract a complete covertext distribution
from a "black box" which has this ability.

As I've already stated, I do not advocate the use of our constructions in
most real-world situations. They are not practical. They only serve as a
proof that provably secure stegosystems are possible in principle.

-Nick

Paul Crowley

unread,
Jan 13, 2003, 4:25:06 PM1/13/03
to
"Ben Mord" <ben...@earthlink.net> writes:
> *and* as long as each cover message does not change that distribution from
> which subsequent cover messages must be drawn!

I'm pretty sure the paper does *not* make this assumption. At all
points it refers to the distribution given what has gone before.

David Wagner

unread,
Jan 13, 2003, 6:01:46 PM1/13/03
to

Well, not really. You can send each bit separately, and then the
complexity is only linear. Of course, it may not be very practical.

By the way, I should also mention that Nick Hopper pointed out in private
email that the exact scheme I mentioned above is not necessarily secure,
depending on the properties of the covertexts (though this may be a
mostly theoretical weakness in practice). The variation they formalize
in their paper is secure.

Ben Mord

unread,
Jan 13, 2003, 6:39:16 PM1/13/03
to

"Nick Hopper" <hop...@cs.cmu.edu> wrote in message
news:3E232968...@cs.cmu.edu...

You are right on that! Perhaps the main feature of your paper is to make
explicit that very assumption which I wrongly thought you were making
implicitly. (Sorry.) The act of making that assumption explicit sounds like
an important contribution of your paper, because (in my very novice opinion)
that sounds like the essence of what makes steganography hard.

Now that I think I understand your paper, would you agree that these
constructions assume that verbatim repetition is not suspicious for the
given channel? Granted, there are very many examples where this would be
fine.

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.

An algorithm which does not impact the choice of message but only alters the
natural noise within it is less vulnerable to improper channel selection,
because the algorithm itself does not influence the choice of message. For
example, that CIA website could put messages within images that they would
host anyhow, so that the choice of image itself does not become a potential
vulnerability of the algorithm.

I understand that the issue of properly defining the subset of channel
history that may be sampled would be considered an implementation detail by
your paper, rather than a part of the algorithm being analyzed. But I humbly
(and perhaps incorrectly?) suggest that for an algorithm where message
choice is the primary means of communication, this issue of selecting
plausible subsets of history for sampling becomes so critical to overall
security that it must be considered a part of the algorithm needing careful
analysis. Without its inclusion, the algorithm can not be considered
complete. (Perhaps.)

Ben

> Constructions 1,2, and 4 in our paper require the ability to make (on 1

Nick Hopper

unread,
Jan 13, 2003, 7:31:49 PM1/13/03
to
Ben Mord wrote:
>>You have missed the fact that we explicitly model this dependence in our
>>paper via our definition of a channel. It is nonstandard, so we devote a
>>page to explaining this model.
>>
>
> You are right on that! Perhaps the main feature of your paper is to make
> explicit that very assumption which I wrongly thought you were making
> implicitly. (Sorry.) The act of making that assumption explicit sounds like
> an important contribution of your paper, because (in my very novice opinion)
> that sounds like the essence of what makes steganography hard.
>
> Now that I think I understand your paper, would you agree that these
> constructions assume that verbatim repetition is not suspicious for the
> given channel? Granted, there are very many examples where this would be
> fine.

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

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

-Nick

Nick Hopper

unread,
Jan 13, 2003, 7:42:14 PM1/13/03
to
David Wagner wrote:
> Paul Rubin wrote:
>
>>d...@mozart.cs.berkeley.edu (David Wagner) writes:
>>
>>>In retrospect, I should have known this. A standard scheme that has
>>>been proposed many times in the past for sending one bit B secretly is
>>>the following:
>>> Let F be a PRF with one-bit output and K be the shared key. Compose a
>>> cover message M. Send it if F_K(M) = B, else re-generate another
>>> message (independent of the previous one!) and repeat.
>>>If I understand correctly, one of things the CRYPTO 2002 paper does is
>>>to make this rough idea precise, work out a reasonable threat model,
>>>and analyze the resulting scheme formally.
>>>
>>The amount of covertext you need to process (though not transmit) in
>>that scheme is exponential in the size of the hidden message you want
>>to send in a given cover message. I wonder if there's a proof that
>>you can't do any better.
>>
>
> Well, not really. You can send each bit separately, and then the
> complexity is only linear. Of course, it may not be very practical.

Still, the complexity to embed a single bit is 2^1. I think it is
possible to prove Rubin's hypothesis that a "universal" stegosystem must
make 2^k draws to embed k bits in a single message, but I haven't taken
the time to fully consider it.

> By the way, I should also mention that Nick Hopper pointed out in private
> email that the exact scheme I mentioned above is not necessarily secure,
> depending on the properties of the covertexts (though this may be a
> mostly theoretical weakness in practice). The variation they formalize
> in their paper is secure.

It is not hard to show that the bias induced by the procedure outlined by
David is at worst proportional to:
(recursion depth)^2 * (collision probability of the cover distribution)
Which is exponentially small in the minimum entropy of the distribution.
Thus David is correct that this error does not effect channels which are
draws on things like e-mail messages, pictures, etc., which have large
minimum entropy.

-Nick

David Wagner

unread,
Jan 13, 2003, 9:00:34 PM1/13/03
to
Ben Mord wrote:

>"David Wagner" <d...@mozart.cs.berkeley.edu> wrote:
>> N.J. Hopper, J. Langford, L. von Ahn, "Provably Secure Steganography",
>> CRYPTO 2002. http://eprint.iacr.org/2002/137/
>> The authors describe a protocol that is secure as long as the good guys
>> can sample from the distribution.
>
>*and* as long as each cover message does not change that distribution from
>which subsequent cover messages must be drawn!

Actually, the authors address this. It is only my brief (and
oversimplified) summary that suffers from a problem.

They talk about stateful cover channels, where we are assumed to be able
to draw from the channel the next symbol according to the conditional
distribution on the string of previously observed symbols. (This
assumption is sure to hold for anyone who can send innocent messages.)
One also has to be able to "back up" and re-draw conditioned on the same
history if necessary. (It is this second assumption that we can back
up and draw a second time that is the non-trivial assumption, but the
paper discusses this carefully and clearly.)

Ben Mord

unread,
Jan 14, 2003, 2:28:08 PM1/14/03
to

"Nick Hopper" <hop...@cs.cmu.edu> wrote in message
news:3E235A7...@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?

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


Ben Mord

unread,
Jan 14, 2003, 2:44:18 PM1/14/03
to
and besides, all of these constructions use channel history as a substitute
for a channel model. The proof then assumes that the channel history is, by
definition, a perfect model, and the proof therefore does not need to
consider the validity of this model.

But is this true? As we compose new cover messages we must strive to predict
what *future* message would not be suspicious. Why must channel history
always be a perfect model of channel future? For example, a cover message
which has an old date stamp, or which refers to old events as though they
were current, might be highly conspicuous. The most extreme example would be
the attempt to use a UDP-based time synchronization protocol as a cover
channel with these constructions, but more subtle versions of this dilemma
could pop up in email, web pages, jpegs, and other possible choice of cover
channel.

So the assertion that channel history is a predictor of channel future is
itself a model. QED. And David is still owed a drink. (Although its not
clear who owes him that drink. Perhaps some good samaritan will pay him this
debt on society's behalf. I would offer but I'm in New York.)

Ben


Ben Mord

unread,
Jan 14, 2003, 4:47:19 PM1/14/03
to

"David Wagner" <d...@mozart.cs.berkeley.edu> wrote in message
news:avvggq$dp0$1...@agate.berkeley.edu...

> Paul Rubin wrote:
> >d...@mozart.cs.berkeley.edu (David Wagner) writes:
> >> In retrospect, I should have known this. A standard scheme that has
> >> been proposed many times in the past for sending one bit B secretly is
> >> the following:
> >> Let F be a PRF with one-bit output and K be the shared key. Compose
a
> >> cover message M. Send it if F_K(M) = B, else re-generate another
> >> message (independent of the previous one!) and repeat.
> >> If I understand correctly, one of things the CRYPTO 2002 paper does is
> >> to make this rough idea precise, work out a reasonable threat model,
> >> and analyze the resulting scheme formally.
> >
> >The amount of covertext you need to process (though not transmit) in
> >that scheme is exponential in the size of the hidden message you want
> >to send in a given cover message. I wonder if there's a proof that
> >you can't do any better.
>
> Well, not really. You can send each bit separately, and then the
> complexity is only linear. Of course, it may not be very practical.

But by sending each bit "separately", don't you really mean sending them
together, while pretending you don't have to worry about the bits that you
already sent? Doesn't this deveat from the constructions in the paper and
thus break the proof? Otherwise the attacker can analyze the correlation (or
lack there of) between the "separately sent" bits? Or by "separately", do
you mean "in such a way that an attacker who can view one cover message can
not view the others?"

Ben


Ben Mord

unread,
Jan 14, 2003, 5:03:43 PM1/14/03
to

"David Wagner" <d...@mozart.cs.berkeley.edu> wrote in message
news:avvggq$dp0$1...@agate.berkeley.edu...
[...]

> By the way, I should also mention that Nick Hopper pointed out in private
> email that the exact scheme I mentioned above is not necessarily secure,
> depending on the properties of the covertexts (though this may be a
> mostly theoretical weakness in practice). The variation they formalize
> in their paper is secure.

What is that weakness? Does the weakness you refer to really apply to the
one bit case that you outlined, or are you referring to the importance of
considering previous messages when extending the one bit covert channel into
multiple bits?

Ben


David Wagner

unread,
Jan 14, 2003, 7:59:30 PM1/14/03
to
Ben Mord wrote:
>But by sending each bit "separately", don't you really mean sending them
>together, while pretending you don't have to worry about the bits that you
>already sent? Doesn't this deveat from the constructions in the paper and
>thus break the proof?

No. I think this is covered in the paper. Channels are stateful;
they require the ability to sample from the distribution on the next
message a channel would output, conditioned on some given previous
output from the channel. It's this stateful aspect + conditioning
that defends against your concern, I believe.

David Wagner

unread,
Jan 14, 2003, 11:13:46 PM1/14/03