Prev: Draft paper submission deadline is extended: ISP-10, Orlando, USA
Next: Request to review OWASP ESAPI crypto
From: Mok-Kong Shen on 15 Feb 2010 19:02

I am attempting to find some perhaps non-conventional ways of embedding
numbers as stego information in drawings. I should be grateful of
getting critiques/comments on the following very preliminary thought of
mine and, even more desirable, of eventually learning from the group
some better schemes.

My humble idea is to have in the drawing a number of selected objects,
identical or different (in kind, size, colour), positioned in a certain
discernable order agreed upon with the communication partner. These
objects represent thus a permutation of them, which has in the
lexicographical ordering of permutations a unique index to serve as the
number to be transmitted.

Thanks,

M. K. Shen
From: Globemaker on 16 Feb 2010 14:39
On Feb 15, 2:02 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:

> My humble idea is to have in the drawing a number of selected objects,
> identical or different (in kind, size, colour), positioned in a certain
> discernable order agreed upon with the communication partner. These
> objects represent thus a permutation of them, which has in the
> lexicographical ordering of permutations a unique index to serve as the
> number to be transmitted.

The "order agreed upon with the communication partner" is important.
Imagine the two people studying the reference drawings eight hours per
day for three days. The drawings are ink on paper. The ten possible
colors of the stego drawing is one number. The style of the drawing is
planned to be one of ten styles defines on this link:
http://www.artyfactory.com/pen_and_ink_drawing/pen_and_ink_drawing.htm
Also, information is passed according to: perspective is used or not
used, one vanishing point or two or three vanishing points in
perspective. Thin lines or thick lines. Straight-edge lines or jittery
hand-drawn lines.

Comment: your idea is useful, but only for people who need to pass
secrets (not me, I have no secrets to pass, even to my best friends).
After two years of inactivity, the training may fade from memory, so
practice is needed periodically.

From: bmearns on 18 Feb 2010 15:20
On Feb 15, 7:02 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> I am attempting to find some perhaps non-conventional ways of embedding
> numbers as stego information in drawings. I should be grateful of
> getting critiques/comments on the following very preliminary thought of
> mine and, even more desirable, of eventually learning from the group
> some better schemes.
>
> My humble idea is to have in the drawing a number of selected objects,
> identical or different (in kind, size, colour), positioned in a certain
> discernable order agreed upon with the communication partner. These
> objects represent thus a permutation of them, which has in the
> lexicographical ordering of permutations a unique index to serve as the
> number to be transmitted.
>
> Thanks,
>
> M. K. Shen

Just with regards to using permutations to convey a numerical value:
myself and a few others have done a bit of work using the factoradic
number system for exactly this purpose. All you need to do is
establish a way to unambiguously sort your different objects and then
the factoradic number system can readily be used to assign a unique
integer in the range [0, n!-1] to each permutation of n objects.
Wikipedia has a reasonable article on it, but if you'd like any
additional help I may be of some assistance.

Hope that helps a little.
-Brian
From: Mok-Kong Shen on 18 Feb 2010 18:00
bmearns wrote:

> Just with regards to using permutations to convey a numerical value:
> myself and a few others have done a bit of work using the factoradic
> number system for exactly this purpose. All you need to do is
> establish a way to unambiguously sort your different objects and then
> the factoradic number system can readily be used to assign a unique
> integer in the range [0, n!-1] to each permutation of n objects.
> Wikipedia has a reasonable article on it, but if you'd like any
> additional help I may be of some assistance.
>
> Hope that helps a little.

Interesting. I know how to utilize the lexicographical ordering,
which is based on combinatorics, but don't know how to exploit the
factoradic number system in the present context. My point is that
I need to be able to express all numbers in a certain range, i.e.
without exceptions. The reason is that one can without sacrificing
generality assume that what one needs to transmit is information
of m bits. Now, if there are G different permutations (G >= 2^m)
in lexicographical ordering, the sender can order the objects in such
a way that any arbitrily given m bit information can be expressed.
Conversely, the recipient can compute the index of the received
permutation in the lexicographical ordering of all permutations,
thus obtaining the m bit information. C codes of doing such tasks are
rather simple, as far as I am aware. As an example, let's consider
employing 4 objects, with 2 of them the same, and denote them by
A, A, B, and C. How does the correspondence between the permutations
of them, namely AABC, ABAC, ..... and the numbers in the factoradic
system look like? (I surmise that there would be gaps.) What is the
advantage of employing the factoradic number system in the present
oontext? Does it perhaps have the merit of reducing the computing cost
for achieving the intended purpose of transmitting m bit information?
Could you please kindly explain a little bit?

Thanks,

M. K. Shen
From: bmearns on 19 Feb 2010 09:39
On Feb 18, 6:00 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> Interesting. I know how to utilize the lexicographical ordering,
> which is based on combinatorics, but don't know how to exploit the
> factoradic number system in the present context. My point is that
> I need to be able to express all numbers in a certain range, i.e.
> without exceptions. The reason is that one can without sacrificing
> generality assume that what one needs to transmit is information
> of m bits. Now, if there are G different permutations (G >= 2^m)
> in lexicographical ordering, the sender can order the objects in such
> a way that any arbitrily given m bit information can be expressed.
> Conversely, the recipient can compute the index of the received
> permutation in the lexicographical ordering of all permutations,
> thus obtaining the m bit information. C codes of doing such tasks are
> rather simple, as far as I am aware. As an example, let's consider
> employing 4 objects, with 2 of them the same, and denote them by
> A, A, B, and C. How does the correspondence between the permutations
> of them, namely AABC, ABAC, ..... and the numbers in the factoradic
> system look like? (I surmise that there would be gaps.) What is the
> advantage of employing the factoradic number system in the present
> oontext? Does it perhaps have the merit of reducing the computing cost
> for achieving the intended purpose of transmitting m bit information?
> Could you please kindly explain a little bit?
>
> Thanks,
>
> M. K. Shen

Factoradic does not have any gaps: with N unique elements you can
represent all the integers in the closed range [0, N!-1]. So for
instance, if you need to convey 8 bits, you need to be able to
represent all the numbers in [0, 255], which you can do in factoradic
with N = 6 (because 6!-1 = 719 which is of course greater than 255).

Now if you're set on using repetition, as in you're previous examples
A appeared twice, I'm not sure off hand whether factoradic will work
or not. Generally, you would use N /unique/ elements. As I mentioned,
Wikipedia has a decent introduction to factoradic, specifically in the
"Permutations" section which shows a little about how permutations
(without repetition) are mapped to factoradic.

Factoradic isn't really distinct from lexicographical ordering. All it
really does is give you a standard way to /compute/ the index of a
given permutation within the list of all possible permutations. (It so
happens that the ordering of permutations thus produced does matches
lexicographic ordering). If you already have code that does this, then
it's entirely possible that you're already using factoradic, or some
variation of it, without realizing that it had a name. If you're
method is not related to factoradic but still works, then there might
not be any good reason for you to switch to a different method, except
that factoradic is a fairly standard method for numbering permutations
so it might be easier to get support for your technique.

Looking at your examples where repetition is allowed, I might point
out that what you've really done is create a base-N number, where N is
the number of different elements (3 in your example: A, B, and C), and
each item is a digit. So for instance, if we assign logical digit
values of A=0, B=1, and C=2, then you have AABC is simply (0,0,1,2) =
1*3 + 2*1 = 5, and ABAC is (0,1,0,2) = 1*9 + 0*3 + 2*1 = 11. Is this
what you were going for? If you're allowing repetition and using
combinatorics, I think you're probably over working it. With
repetition, it's simply a base-N number and is probably most easily
dealt with in that manner, which doesn't require any combinatorics and
is a bit easier and less computationally intensive.

Just in terms of steganography, your description raises some concerns,
but I'm not sure I fully understand your concept. What I got from your
description is an image of various shapes or objects from some agreed
upon set (so they can be assigned a sorting value) arranged in some
order. Again, I may be missing something but this doesn't seem very
transparent. In other words, the image itself seems like it would be
fairly suspicious. For limited use, of course, you can get away with
just about any obscure encoding mechanism you want, but if this had
widespread use, would there be believable cover stories for sending
such images back and forth without anyone suspecting ulterior motives?
Remember, with steganography, your opponent doesn't generally need to
prove that you're up to anything: all they need to do is sense
something fishy in what you're doing and then start digging to see if
they were right.

It also doesn't seem to provide all that much capacity. In order to
encode a useful amount of information, you need to have a lot of items
in the picture (if you're not using repetition) or at least a very
large set of items to choose from (if you're allowing repetition,
i.e., using base-N numbers you would want N to be quite large so each
item/digit encodes a large amount of information).

Finally, would this be encoded and decoded by computers or done
manually? If it's done by computers, you would need either very simple
items (which probably means a small N) or some pretty sophisticated
image processing code. You could do it manually or semi-manually (have
a human identify each item, and then let the computer compute the
encoded value) but then of course you need to rely on the humans not
to make mistakes, and it might be a pretty slow process.

I hope this isn't too dismissive. You're thinking along good lines and
I certainly don't mean to discourage you. When I started working on
permutation based stego, I thought I had come up with something
entirely new, and I was quite disappointed when I learned it was
already known, so I hope you're not too disappointed if that happens
here.

Cheers,
-Brian
 |  Next  |  Last
Pages: 1 2 3 4
Prev: Draft paper submission deadline is extended: ISP-10, Orlando, USA
Next: Request to review OWASP ESAPI crypto