Thu Apr 18 01:23:46 BST 2013

```On 17/04/13 21:44, Ben Liddicott wrote:
>
> Firstly, I don't think anyone is suggesting that Facebook are actually
> trying to prevent people sending secret messages. They just want to
> optimise bandwidth away from meaningless chatter and towards
> advertising, and compressing the images is purely incidentally
> preventing some steganographic techniques from working. I am pretty sure
> you could send quite long messages purely as variations in the use and
> misspelling of non-words like Lollzr! and how many exclamation marks are
> used.
>
> A technique which is hidden only from casual inspection is one thing,
> and I don't think really qualifies as steganography, it's more like a
> dead drop - if you look for it you will find it. Such techniques can be
> erased simply by looking for the message and then deleting it purposely.
> So the discussion is about techniques which are not detectable even if
> you suspect they are there and if you know the algorithm.

There is a well-studied warden problem - the warden has two prisoners in
seperate cells, and he wants them to exchange messages without any
hidden content. Turns out it's impossible.

Entropy (in the Shannon sense) is not the same as meaning. Entropy
refers only to the probability of a particular selection being made from
a set of possible selections. The selection which is actually made, the
fact that a selection is made at all, the channel by which it is sent,
the time it is made - all are information in the message which are not
the entropy of the selection.

You can do much the same analysis with Kolmogorov-Chaitin complexity as
a measure of information, and come to the same conclusion - preventing
hidden transfer of meaning is impossible, especially where the
participants can prearrange a codebook between anything which is passed
in the message.

That said, imagine a "standard" Facebook picture has 360,000 bits of
information (200 pixels by 100 pixels by 18 bits per pixel). That's
2^360k posible pictures. Now let's suppose 2^360 of those possible
pictures are non-redundant.

Alice posts one of those 2^360 non-redundant pictures - Bob now has 360
bits of information from Alice, the choice of which picture she posted.
Also Bob knows when she posted it, and so on.

In practice it is, of course, impossible to tell exactly whether a
picture is non-redundant.

I don't know who Oscar is in the rest your post - seems to be Facebook
sometimes, Alice other times - but I will say that Facebook could change
images so that they were detectably changed without that being
steganography, only Alice can't introduce detectable changes

Oh, and it's impossible for facebook to know every stego technique.

-- Peter Fairbrother

>
>
> On 14/04/2013 08:16, Ian Batten wrote:
>>
>> On 12 Apr 2013, at 00:01, Ben Liddicott <ben at liddicott.com
>> <mailto:ben at liddicott.com>> wrote:
>>
>>> That isn't possible, up to a limit. Proof is that any such
>>> transformation can carry only a limited number of bits of data.
>>> Therefore any steganographic message can be destroyed by a
>>> transformation using the same stego technique
>>>
>>>
>> That would rely on Facebook knowing the stego technique and any
>> associated keys.
>
> Indeed, it's assumed that Oscar knows the library of available techniques.
>> If it's keyed (ie, Alice and Bob share a key from which they can
>> derive a small subset of the pixels in the image which contain the
>> message), then how can the attacker overwrite that message?   The key
>> would denote some small number of bits, drawn from potentially all the
>> bits in the image.  The attacker can choose some random key and insert
>> a message using that, but if a key identifies some fraction F of the
>> image, adding another message with an independent key would overwrite
>> F of the first message.  As F will typically be small, simple error
>> correction will suffice.
>
> In the presence of a given level of redundancy, the number of bits Oscar
> would have to store in any given image in order to erase the message is
> left as an exercise to the reader.
>
>>
>> Facebook could attack this technique by dithering the whole image.
>>  But I suspect that you can perturb a small number of pixels more than
>> all the bits, so the degradation caused by dithering all the bits
>> sufficiently to extinguish information encoded in any subset of those
>> bits would be visually unacceptable.
>>
> Do you think you can perturb a small number of pixels enough to
> withstand an erasure attack, without those pixels becoming detectable as
> a hidden message, and thereby defeating the purpose of steganography?
>
> Oscar can perturb the image as much as he likes provided it isn't
> noticeable to a human - and if it's noticeable to a human it isn't
> steganography.

```