attacks on steganography?
niko vinken
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
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
Ben Mord
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
> "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
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
"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
>
>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
> 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
> 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
> I think bad stego code might be easy to spot. If you take the
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
"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
>
>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
> Very interesting. This has been proven?
To my satisfaction, at any rate.
Ben Mord
"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
> 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
<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
>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
>
> 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
>
>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
> 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
"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
> 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
<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
[...]
>
> 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
>
> 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
"David Wagner" <d...@mozart.cs.berkeley.edu> wrote in message
news:avdggh$th0$3...@agate.berkeley.edu...
> >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
> 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
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
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
<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
> 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
>
>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
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
"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
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
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
>
> Ben Mord 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
...
> 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
> 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
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
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
> 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
> 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
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
> 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
> "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
> 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
> *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
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
"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
>>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
> 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
>"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.
>
>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
[...]
> 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
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
> 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
"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
>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
>> email that the exact scheme I mentioned above is not necessarily secure,
>
I better let him respond, since I received the details in private
email and am not sure whether they were intended for public disclosure
at this point.
Ben Mord
Nope. See page 5, definition of channel and description of the Oracle. "This
oracle can draw from the channel in steps and at any point the draw is
conditioned on what has been drawn so far."
The last half of that sentence is very important, because not only do you
care about what messages have been sent on the channel by anyone at anytime,
you also care which of those messages have been sent by *you* as part of
your cover text. Otherwise, there is no way for you to build the
correlations between discrete pieces of cover message in order to form a
convincing cover text. You will see that the definition of channel (top of
page 5) is sufficiently general that it provides no way for you to know
which message in the channel history (top of page 5) has been sent by whom,
and you need to track what you yourself have said so far. For the sake of
your current argument I suppose you could add this requirement to the
channel definition, at the expense of some generality.
Note, by the way, that these constructions deal well with making sure each
unit of covertext has convincing correlations with previously sent
covertext, but it does nothing to deal with the possibly conspicuous failure
of the last piece of covertext to be followed by more convincing covertext
after the covert communication has ended. I suppose this could be fixed
through padding, although you would need some way to determine what length
of padding is required for this channel and history. Its not clear how you
would do that in a way that is forever provably secure.
Ben
Ben Mord
"Ben Mord" <ben...@earthlink.net> wrote in message
news:b041on$kt3q7$1...@ID-101018.news.dfncis.de...
[...]
> Note, by the way, that these constructions deal well with making sure each
> unit of covertext has convincing correlations with previously sent
> covertext, but it does nothing to deal with the possibly conspicuous
failure
> of the last piece of covertext to be followed by more convincing covertext
> after the covert communication has ended. I suppose this could be fixed
> through padding, although you would need some way to determine what length
> of padding is required for this channel and history. Its not clear how you
> would do that in a way that is forever provably secure.
>
> Ben
>
And that just gave me two other ideas.
Some channels may be subject to a traffic analysis that considers message
content in relation to sender and/or receiver identity. Not only might you
be concerned about creating covertext that is well camouflaged in the
context of the channel history taken as a whole, you might also be concerned
about creating covertext that is convincing with respect to the identity of
the sender and recipient. The channel definition does not explicitly declare
the binding of sender/receiver identity to messages, and so such
considerations do not enter the analysis presented by the paper. But the
channel definition also does not prohibit such binding (and almost all
real-world examples do have such a binding) and so this analysis is
required.
Some channels may also be subject to temporal analysis that considers
message content in relation to time. In the most general form used by this
paper, channel history does not suffice to tell you what channel future
should look like - for this a model is needed of how channel content evolves
over time. (Clock synchornization protocols is the most direct example of a
channel whose content changes over time, current events referenced by email
is a slightly more insidious example.) Security then depends in part on the
accuracy of this model.
Ben
David Wagner
>Note, by the way, that these constructions deal well with making sure each
>unit of covertext has convincing correlations with previously sent
>covertext, but it does nothing to deal with the possibly conspicuous failure
>of the last piece of covertext to be followed by more convincing covertext
This is easy to deal with. Just keep sampling from the channel and
output each channel; there's no need to ever "back up" and draw a second
sample.
David Wagner
>Not only might you
>be concerned about creating covertext that is well camouflaged in the
>context of the channel history taken as a whole, you might also be concerned
>about creating covertext that is convincing with respect to the identity of
>the sender and recipient.
This is not a problem for their approach.
Obviously, this should be absorbed in the notion of the channel.
The channel distribution represents the distribution on sequences
messages that might be sent from this sender to this receiver,
conditioned on the sender and receiver's identity and on any other
context that may be known to the attacker.
David Wagner
>Some channels may also be subject to temporal analysis that considers
>message content in relation to time. In the most general form used by this
>paper, channel history does not suffice to tell you what channel future
>should look like - for this a model is needed of how channel content evolves
>over time.
I suppose we could discretize time. At time intervals when there is
nothing to be sent, the channel outputs a special "nothing to send now"
symbol. Then their approach should apply fine.
Paul Crowley
You could, but their approach takes time into account by labelling
each bit sent with a timestamp.
Ben Mord
> Ben Mord wrote:
> >Not only might you
> >be concerned about creating covertext that is well camouflaged in the
> >context of the channel history taken as a whole, you might also be
concerned
> >about creating covertext that is convincing with respect to the identity
of
> >the sender and recipient.
>
> This is not a problem for their approach.
Technically, you're right - if you are saying that this particular point is
not a flaw in the proof.
>
> Obviously, this should be absorbed in the notion of the channel.
> The channel distribution represents the distribution on sequences
> messages that might be sent from this sender to this receiver,
> conditioned on the sender and receiver's identity and on any other
> context that may be known to the attacker.
Yes. This is only a practical limitation - the channel history that may be
used in such channels is only the history between the two parties who intend
to conduct covert communication. As their constructions are stated, this is
the only channel history you would be permitted to use in channels that
encode sender and receiver information. Otherwise, it breaks.
Ben Mord
This fixes nothing. I think what I am saying might be most clearly
communicated by an example.
Suppose you choose email as your cover channel. You are now constructing a
brand new plausible email to send as cover text. What data informs your
decision? The history of previously sent emails. But this history includes,
for example, old email that was written back when people used different
slang, perhaps even the statistical rate of particular characters was a
little different due to the evolution of language, and at a higher level
many of these emails refered to historical events as though these were
breaking news (because at the time, they were.) Now if you use this old data
in constructing your new email, that new email might not look so plausible
in the context of today.
Now you might want to fix this by only sampling from recent email. But try
to define this in detail, in a generic way that does not make any
significant assumptions about your choice of cover channel, and in a way
that is provably secure. My confidence on this particular point has grown to
the point where I would bet many beers you can't do this. A counter example
to many of your first attempts could likely be formed by considering cover
channels where each "message" contains a unique id that is always
incremented. Perhaps usenet has something like this for message ids?
Ben
Ben Mord
"Paul Crowley" <pa...@JUNKCATCHER.ciphergoth.org> wrote in message
news:87k7h52...@saltationism.subnet.hedonism.cluefactory.org.uk...
> d...@mozart.cs.berkeley.edu (David Wagner) writes:
>
> > Ben Mord wrote:
> > >Some channels may also be subject to temporal analysis that considers
> > >message content in relation to time. In the most general form used by
this
> > >paper, channel history does not suffice to tell you what channel future
> > >should look like - for this a model is needed of how channel content
evolves
> > >over time.
> >
> > I suppose we could discretize time. At time intervals when there is
> > nothing to be sent, the channel outputs a special "nothing to send now"
> > symbol. Then their approach should apply fine.
>
> You could, but their approach takes time into account by labelling
> each bit sent with a timestamp.
Yes. But it does not take into account the constant evolution of content
patterns over time. For this, I see no easy fix. What is needed to fix this
is, alas, a channel-specific model so that patterns from the past can be
used to predict what patterns would be plausible as future content.
Ben
Ben Mord
Sure, just keep sampling and spewing out covertext even after you have
finished your covert communication. For how long must you keep this up if
your standards are provable security? Forever! Well, or until the channel
itself ceases to exist.
Ben
David Wagner
>But it does not take into account the constant evolution of content
>patterns over time.
I don't understand. Can you explain?
David Wagner
>Sure, just keep sampling and spewing out covertext even after you have
>finished your covert communication. For how long must you keep this up if
>your standards are provable security? Forever! Well, or until the channel
>itself ceases to exist.
Well, most channels will likely have a special "end transmission"
symbol. Just keep going until you hit that symbol.
For instance, if we're hiding information in an email message, and
our channel outputs one word at a time, at some point the email
message will end. That's when you stop spewing out covertext.
Paul Crowley
> Yes. But it does not take into account the constant evolution of
> content patterns over time. For this, I see no easy fix. What is
> needed to fix this is, alas, a channel-specific model so that
> patterns from the past can be used to predict what patterns would be
> plausible as future content.
But their model does exactly this!
Ben Mord
Sure. The problem I believe I have identified is not at the bit level or in
the Martingale analysis, so if you're thinking at that level and take about
two steps back, then you should be at about the right level of abstraction
for what I'm saying.
What will your covertext look like with these constructions? It will look a
whole lot like the typical message that has been sent previously through
this channel. In fact, that's the whole point.
For the sake of illustration, suppose the channel is email, suppose email
has been in active use since writing was first developed, and suppose you
are sampling from the whole history of this ancient medium when producing
cover text. (Bare with me...) What language will your covertext be in?
Probably not modern English, because that hasn't been around for very long
and will only represent a tiny percentage of the channel's history. So
suppose that right now, in the year 2003, you send out a new email which
appears to be in some dialect of ancient Greek. What odds might an attacker
assign this email (knowing about these constructions) that this is in fact
covertext hiding covert communication, rather than, say, something less
suspicious in the context of modern times such as an interoffice memo about
training for the new HR application?
This is an absurd example, but consider carefully why it works. Then scale
it down. When we say that newly created cover text will look a whole lot
like your "typical" message selected randomly from the channel history,
exactly how much will it look like your typical message? In fact, it will
look identical. For a sufficiently long transmission, the generated
covertext will actually be an exact duplicate of some random message from
the past. Now this can look very suspicious in very many channels, even if
you only use the past day of a channel's history and have no concerns about
accidentally using some Sumarian dialect.
Does this help? I think the hazard with this paper is that it launches
directly into low-level mathematical analysis without spending enough time
at other levels of abstraction. The hardest part with math and with system
design (and certainly with the combination!) is operating at multiple levels
of abstraction simultaneously. But I shouldn't sound too confident yet -
perhaps someone can find a flaw in what I'm saying?
Ben
Ben Mord
> "Ben Mord" <ben...@earthlink.net> writes:
> > Yes. But it does not take into account the constant evolution of
> > content patterns over time. For this, I see no easy fix. What is
> > needed to fix this is, alas, a channel-specific model so that
> > patterns from the past can be used to predict what patterns would be
> > plausible as future content.
>
> But their model does exactly this!
Yes, but only the evolution of past patterns over time, and it is not even
prejudiced towards modern channel history over ancient channel history. (Not
that introducing such a bias in the sampling algorithm would alone fix the
proof, but it would be a step closer...)
Ben
Ben Mord
Not good enough. For example, suppose your covertext happens to be an email
from an employee informing their project manager of their intentions to take
vacation on a particular date. Wouldn't this typically be followed up by an
email, sent a day prior to that date, that the employee will be gone the
next day but will be available for emergencies by cell phone etc? If you
examine channel history, you'll probably find that indeed yes - it is
typically followed up by such a reply. (Of course the particulars will vary,
but one such scenario should probably be selected.) But what if you ran out
of covert data before finishing the first message? This is why you must
continue padding, otherwise you will never send the follow up email. To
remain provably secure in the most general case, for how long must you
continue padding? Forever. In the particular case of this example, you could
do something much more reasonable.
Yes, you might intuitively be able to define logical break points where a
transmission would probably never be suspect so long as it terminated at one
of these break points. But this would be channel-specific, and subjective.
How could you do this in the general case in a way that is provably secure?
Ben
David Wagner
>Yes, but only the evolution of past patterns over time, and it is not even
>prejudiced towards modern channel history over ancient channel history.
Huh?
David Wagner
>> symbol. Just keep going until you hit that symbol.
>>
>> For instance, if we're hiding information in an email message, and
>> our channel outputs one word at a time, at some point the email
>> message will end. That's when you stop spewing out covertext.
>
>Not good enough. For example, suppose your covertext happens to be an email
>from an employee informing their project manager of their intentions to take
>vacation on a particular date. Wouldn't this typically be followed up by an
>email, sent a day prior to that date, that the employee will be gone the
>next day but will be available for emergencies by cell phone etc?
Ok! Good point.
David Wagner
>For the sake of illustration, suppose the channel is email, suppose email
>has been in active use since writing was first developed, and suppose you
>are sampling from the whole history of this ancient medium when producing
>cover text.
Let's not suppose that -- that's not how Hopper et al's scheme works.
I'm getting the suspicion that you may have the wrong idea about how
the construction works. Keep in mind there is a difference between (1)
a priori probabilities and (2) observed frequencies. We sometimes use
(2) as an estimate of (1), but they are not the same. In Hopper et
al's scheme, they use (1), not (2). In other words, they don't sample
randomly among the set of previously observed channel outputs. Rather,
they sample from the a priori distribution on the next channel output.
Let me give an example. Suppose our channel outputs one word at a time,
according to the distribution on conversational English. Suppose that,
up till now, this is the first time we've ever used stego or had a
conversation in English, and suppose our channel has output the words
My favorite color is
What is the conditional distribution on the next word to appear from
this channel, given that our conversation began with the words "My
favorite color is"? Well, presumably words like "giraffe" have very
small probability, and words like "blue", "green", "red" have some
reasonably large probability. Hopper et al communicate information by
choosing between words like "blue", "green", "red" (usually) or "giraffe"
(rarely), according to those previously mentioned probabilities.
I'm worried you might have a misconception. Your misconception seems
to be that we are forced to choose from the words "My", "favorite",
"color", and "is", since they are the only ones that have been observed
in the past. This would be incorrect.
If this wasn't what was going on, I hope you can explain further.
I must admit I'm having a hard time understanding your concerns; my
apologies for being slow to catch on.
David Wagner
>Suppose you choose email as your cover channel. You are now constructing a
>brand new plausible email to send as cover text. What data informs your
>decision? The history of previously sent emails.
Now I see the problem. Hopper et al assume that we have an oracle that
can sample from plausible emails. They don't say how to build such an
oracle; they simply assume that one exists. Their scheme only applies
if we believe we have such an oracle.
You seem to have in mind one particular method of instantiating such an
oracle: namely, sampling from the history of all previously sent emails.
Then you note that, if we use your method of constructing the oracle
along with Hopper et al's scheme, the result might be insecure.
But the problem is with your instantiation of the oracle, not with Hopper
et al's scheme. Your oracle doesn't satisfy the required conditions.
Hopper et al only make any promises if the oracle has certain properties,
and your instantiation of the oracle doesn't have those properties.
So it is no great surprise that their construction becomes insecure with
your instantiation of the oracle.
Now, maybe we could critique Hopper et al's method by arguing that their
assumption (about the existence of such an oracle) is unreasonable.
Maybe we could argue that it is too hard to construct an oracle that
satisfies all their conditions. This could well be. I agree that this
sounds like a real concern, and one we should think about carefully.
But let's not jump to conclusions too quickly. To really make this
case, it's not enough to just consider one possible instantiation of
the oracle and show that this one instantiation is no good; we have
to argue more broadly somehow. And even if we can make this argument
successfully, it doesn't prove that their scheme is insecure -- rather,
it demonstrates that it is not applicable in practice. I think it
is plausible that this issue might be a showstopper for their method,
but it is also plausible that this issue might not be a big problem.
I'd like to see more evidence before being convinced either way.
Paul Rubin
> Now I see the problem. Hopper et al assume that we have an oracle that
> can sample from plausible emails. They don't say how to build such an
> oracle; they simply assume that one exists. Their scheme only applies
> if we believe we have such an oracle.
Actually, if the covertext is email, then steganography at such low
bit rates is very simple. The webmail client that I use, for example,
generates random strings (20 chars long or so) to use as MIME
attachment separators. If it instead put ciphertext into those
strings, no one would know.
Mok-Kong Shen
One could even embed a few bits in the modified (invalid,
normally to prevent spam e-mail) address of posts to
internet groups, etc. etc. BTW, I may be biased by my
own stuff, but I think that what I proposed in the thread
'Steganography with ASCII text files' of 11 Feb 2001
utilizing word/character counts of chosen lines of
e-mails/documents to be practically useful.
M. K. Shen
Ben Mord
> Ben Mord wrote:
> >Suppose you choose email as your cover channel. You are now constructing
a
> >brand new plausible email to send as cover text. What data informs your
> >decision? The history of previously sent emails.
>
> Now I see the problem. Hopper et al assume that we have an oracle that
> can sample from plausible emails. They don't say how to build such an
> oracle; they simply assume that one exists. Their scheme only applies
> if we believe we have such an oracle.
>
> You seem to have in mind one particular method of instantiating such an
> oracle: namely, sampling from the history of all previously sent emails.
> Then you note that, if we use your method of constructing the oracle
> along with Hopper et al's scheme, the result might be insecure.
>
> But the problem is with your instantiation of the oracle, not with Hopper
> et al's scheme. Your oracle doesn't satisfy the required conditions.
> Hopper et al only make any promises if the oracle has certain properties,
> and your instantiation of the oracle doesn't have those properties.
> So it is no great surprise that their construction becomes insecure with
> your instantiation of the oracle.
So you are telling me that when, on page 5, there is reference to an Oracle
that "draws from the channel," what they mean is both the past *and* future
of the channel? I assumed they only meant that it draws from the channel
past, because otherwise you have an oracle whose actions are determined in
part by the future, and yet whose actions are also part of what defines that
future. Wow, that gets very complicated, very quickly! Is this construction
coherent? Can its coherence be proven without placing additional constraints
upfront? Or I suppose all that needs to be proven is the existence of a
coherent implementation - this would suffice to demonstrate that the
construction does not contradict itself. That would be important part of the
proof itself, because you can prove (and disprove) all kinds of things in an
incoherent framework! (I'm still not convinced this is what the authors
meant, but obviously they can answer that question.)
Isn't there reason to suspect that this is incoherent? After all, you look
at one channel distribution, then publish a message that necessarily alters
that channel distribution! So either it is incoherent, or you say that this
is what you meant by a perfect Oracle, in which case the proof breaks. You
can't have it both ways. (But I just thought of this argument so my
confidence level in it is only about 1/4 of a beer.)
Ok. If that's true, then there is the presumed perfect model that you were
looking for - its the Oracle. If that's true, then this paper does presume
the existence of a perfect model, and then asserts that provably secure
steganography is possible if you presume a perfect model. That's not very
surprising - the modeling is the hard part, making a signal conform to a
model is much easier. But if this in fact proves that you can make a signal
conform exactly to a model, then that is interesting.
>
> Now, maybe we could critique Hopper et al's method by arguing that their
> assumption (about the existence of such an oracle) is unreasonable.
...or maybe incoherent when combined with their algorithms? (not sure...)
> Maybe we could argue that it is too hard to construct an oracle that
> satisfies all their conditions. This could well be. I agree that this
> sounds like a real concern, and one we should think about carefully.
>
> But let's not jump to conclusions too quickly. To really make this
> case, it's not enough to just consider one possible instantiation of
> the oracle and show that this one instantiation is no good; we have
> to argue more broadly somehow. And even if we can make this argument
> successfully, it doesn't prove that their scheme is insecure -- rather,
> it demonstrates that it is not applicable in practice. I think it
> is plausible that this issue might be a showstopper for their method,
> but it is also plausible that this issue might not be a big problem.
> I'd like to see more evidence before being convinced either way.
Ben
David Wagner
>Actually, if the covertext is email, then steganography at such low
>bit rates is very simple. The webmail client that I use, for example,
>generates random strings (20 chars long or so) to use as MIME
>attachment separators. If it instead put ciphertext into those
>strings, no one would know.
How do you know those strings are truly random?
Maybe they're generated with rand(), or with a PRNG that's seed
with the time of day -- in which case, your stego proposal wouldn't
work.
But yes, I agree, there may be many useful low-bit-rate subliminal
channels available for this sort of purpose.
David Wagner
>So you are telling me that when, on page 5, there is reference to an Oracle
>that "draws from the channel," what they mean is both the past *and* future
>of the channel?
No, no, not at all. I think you're confusing the channel's *outputs*
with the *distribution* on the channel's output. You're making this too
complicated. When we say "draw from the channel", we mean to sample from
the *distribution* on the channel's output. We don't mean to randomly
select one of the previous (or even future) *outputs* of the channel.
Again, there is a crucial distinction between the *a priori* distribution
and the *observed* outputs. Improperly conflating these two will lead
you astray, and this is what seems to be the source of the confusion here,
if I'm following correctly. Do you agree?
Mok-Kong Shen
David Wagner wrote:
>
[snip]
> But yes, I agree, there may be many useful low-bit-rate subliminal
> channels available for this sort of purpose.
I would think that the bit rate is necessarily low,
if one desires substantial security in stego in
practice.
M. K. Shen
Ben Mord
No - my apologies for being slow. Yes, I did not understand that this is
what was intended.
But there is only one future. (I mean, we're not delving into quantum
mechanics, are we?) So where does this distribution come from? I would think
the distribution would be probability 0 for everything, except that which is
going to happen, which would have probability 1. But then you are deciding
that the bit that should come next is the bit that should come next - which
isn't a decision. So, I'm still confused. What defines this distribution?
Ben
Ben Mord
"Ben Mord" <ben...@earthlink.net> wrote in message
news:b07asd$md9vb$1...@ID-101018.news.dfncis.de...
outputs one word at a time, according to the distribution on conversational
what you mean by channel. In this example, your channel is conversational
English. I grok. Thank you! Yes, that is simple.
The hard part, then, is figuring out exactly what channel you're using. It
is not enough to say that you are using email. It is not enough to say that
you are using email with English. It is not enough to say that you are using
email with the style of English found in 2003. It is not enough to say you
are using the American English of 2003 as used by professors. All of these
are too aproximate for an absolute proof of security.
You must instead say that you are using the American English of 2003 as
would be used by a professor named David Wagner at this time on January 16
shortly after receiving messages from a confused guy about a paper which
said a, b, and c and who has also received messages from other people saying
x, y, and z and whose life history is h and with personality p and writing
style s etc...
In short, the channel is uniquely identified by the sum of all information
which could conceivably be used to validate your cover text. If you know the
distribution uniquely defined by all information that could be used to
attack your stego (including many variables other than time, I might add,
e.g. your life history and personality traits) then, using this construct,
you can conduct provably secure steganography.
You know what - I believe that assertion full heartedly. If you add infinite
padding, then I also believe that these constructs, assuming you know this
distribution as identified by a nearly infinite amount of information, are
examples of provably secure steganography. I buy that. Anyhow, you still win
your bet - I think that distribution qualifies as a perfect model. Actually,
it is a model that is defined as being as perfect as the best model that
could be constructed by the attacker, so if you want to get technical it
need not be perfect.
If you assume an omniscient attacker and a deterministic universe, then your
Oracle would predict the future. In this case it would not be a record of
the past - it would only be a perfect record of the future. So I got that
backwards. (That's a handy Oracle.) Do you agree?
Ben
Jan Panteltje
<mok-ko...@t-online.de> wrote in <3E271A54...@t-online.de>:
>One could even embed a few bits in the modified (invalid,
>normally to prevent spam e-mail) address of posts to
>internet groups, etc. etc. BTW, I may be biased by my
>own stuff, but I think that what I proposed in the thread
>'Steganography with ASCII text files' of 11 Feb 2001
>utilizing word/character counts of chosen lines of
>e-mails/documents to be practically useful.
>
>M. K. Shen
>
You can expand on that a bit to make a deal with the receiver like this:
XOR my secret codes with the morning news on digital satellite channel
ZDF, at (such and such time).
(You did XOR it with that too), starting at the first 0xff byte after 7:30h.
Of cause, since on one transponder there are also many hidden channels,
like ECM channels, you could XOR again with those too.
And of cause, to prevent long 00 sequences to show things 'as they are'
not a simple XOR.....
I have been thinking to implement this in my news reader (NewsFleX),
I did read the Navy (US) had some project involving Usenet long time ago.
For sure the enormous amount of data transmitted over Usenet would make
any hidden stuff more difficult to find.
Have had no need for it yet, but for a fee ..... I could work it out.
Maybe this idea is flawed, I am not really a crypto man, but if you added some
good encryption, making use of public available digital data channels for
'key' (as in the XOR) would that not make the chances of detection remote?
It could be some ID in some article header in some newsgroup that needed
to be combined with the email ID for example.
JP
Ben Mord
Huh is right. This is me flaunting my confusion. Thanks again for setting me
straight regarding their definition of channel and oracle.
David Wagner
>So where does this distribution come from?
Where does any distribution come from?
For instance, I say that I will have a 1/6 probability of getting a
3 if I roll this die. What does this mean?
(This is a serious question. Once you understand this, enlightenment
may follow.)
David Wagner
>In short, the channel is uniquely identified by the sum of all information
>which could conceivably be used to validate your cover text. If you know the
>distribution uniquely defined by all information that could be used to
>attack your stego (including many variables other than time, I might add,
>e.g. your life history and personality traits) then, using this construct,
>you can conduct provably secure steganography.
Close, but the assumption is not quite that strong. Remember that their
scheme only requires that you be able to sample from this distribution,
not that you know it. The former might be easier than the latter.
Ben Mord
What it means is that you have a well defined set of possible outcomes
with probability that is equal if you ignore details such as wind
current, exact movement of your hand while shaking, physics of how they
bounce around, etc. Instead of modeling this stuff, you just ignore
these nearly intractable details and are left with a very well-defined
set of knowledge about what could happen. In this case, the probability
distribution is an expression of your ignorance about the myriad
variables and their interaction, rather than some fundamental source of
randomness (e.g. like the uncertainty principle in quantum mechanics.)
But that's not where this distribution in the paper comes from.
Actually, the paper doesn't say where it comes from, just that it exists
and has certain properties, in terms of which a definition of security
is established and then checked against several constructions.
The intention, of course, is that this distribution can be mapped to
something in the real world, and the name "channel" is used to suggest
vaguely what that might be. But the exact nature of this mapping is not
really defined or explored, and therefore the true origin of this
distribution is not defined. Hopefully, this is left as the subject of
another paper.
But like the dice, the uncertainty that results in a distribution
(instead of a certain prediction) is an expression of certain things
which someone does not know. Who is that someone? I think it must be the
attacker, for the proof to work. But this must be clearly defined before
a real-world implementation could be considered provably secure.
There are two currently known origins of randomness. Ignorance, and the
uncertainty principle. A probability distribution which finds its
origins in ignorance is, in a sense, a model of that which is or is not
known. Randomness is usually a placeholder that we use to represent our
ignorance.
Ben
Ben Mord
I think you can sample a specific history as many times as you like.
That means you can reconstruct the distribution to arbitrary accuracy,
so I don't think the assumption is weaker. Right?
By the way, it seems to me that these constructions do increase entropy
*slightly* above what you would naturally see. This happens because,
e.g., half the time the most probable block will be unacceptable because
it hashes to the wrong bit. But the paper probably discusses this, and
that might be part of why there is a minimum block entropy requirement.
There are some parts I still don't grok - its probably in there
somewhere. You could look for this increase in entropy, so they probably
discuss measurable bounds to the security as a result?
Ben Mord
Yes. Thanks.
Ben Mord
> 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
Just cleaning up loose ends. This post of mine was not refuted directly,
so lest it confuse someone else let me point out that I was deeply
confused. David Wagner explains my confusion in other posts in
neighboring threads.
I still maintain that what this paper calls the "channel" is in fact a
perfect model, so David is still owed a beer. But this particular
explanation of mine was drastically misinterpreting the paper and should
be ignored.
Ben
Mok-Kong Shen
Jan Panteltje word:
My said proposal concerns only how the stego bits
are realized in the messages. These bits may and
preferably should themselves be the result of
an encryption of the plaintexts, employing any
algorithms of one's choice. (I didn't suggest
one in the thread mentioned.)
BTW, the use of public available texts and xor-ing
them to get some random sequences in the sense
you wrote was discussed in a couple of threads quite
a time ago. Whether the result is considered good
for practical use must of course be a subjective
decision, since no rigorous analysis could be done.
M. K. Shen
David Wagner
>I think you can sample a specific history as many times as you like.
>That means you can reconstruct the distribution to arbitrary accuracy,
>so I don't think the assumption is weaker. Right?
It depends. Not necessarily, I think.
For instance, if the distribution is uniform on the set of pairs
(x,y) such that AES_k(x)=y, where k is secret, then sampling from
this distribution doesn't suffice to reconstruct a description of the
distribution (unless you're willing to sample exponentially many times).
David Wagner
>By the way, it seems to me that these constructions do increase entropy
>*slightly* above what you would naturally see. This happens because,
>e.g., half the time the most probable block will be unacceptable because
>it hashes to the wrong bit. But the paper probably discusses this, and
>that might be part of why there is a minimum block entropy requirement.
Note also the presence of the counter in the input to the PRF.
Paul Crowley
Or if the distribution is the set of y such that there exists a k such
that AES_k(0)=y, we can easily sample it, but finding the probability
of a given y is hard.
--
__ Paul Crowley
\/ o\ s...@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/