NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/sci/crypt/4519

Internet Message Format | 1992-11-09 | 3.5 KB

Path: sparky!uunet!utcsri!newsflash.concordia.ca!sifon!thunder.mcrcim.mcgill.edu!sobeco!rcorco!elevia!alain
From: [e-mail] (W.A.Simon)
Newsgroups: sci.crypt
Subject: A new encryption problem?
Message-ID: <[e-mail]>
Date: 10 Nov 92 04:20:53 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <1
Lines: 71

In <[e-mail]>
[e-mail] (Eric Silber)
gives us a problem to solve:

> create a secure encryption algorithm which has the following
> characteristics:
> Let 'p' be the plain text.
> Let 'E' be the encryption transformation.
>    Let 'c' be the cipher text.
> Require that for-all p
> (c=E(p)) is a text which appears to be a plaintext)

This has been answered, in a way,
by Peter Wayner ([e-mail]).
Ask him about Mimic.  It is a dry read, but intellectually well
worth the effort (Peter, this one will cost you).

There may be others, but I am not aware of them.
However, there are easier ways, if one doesn't mind wasting
bandwidth, and if one accepts to step out of the constraints you
have placed on the resolution of the problem.  What you ask for
is hard to do; but if your intent is practical rather than
academic, then you will have to count the ways to skin a cat.

So far, steganography's best ally is digitized material.  There
is room for dithering and noising.  As demonstrated by other
writers in this forum, borrowing a less significant bit within a
digitized product, although slightly less than efficient, is a
very secure way to hide information.  This can be done without
giving yourself away.

The danger here is that once we know this, so do "they".  So we
have to encrypt this borrowed one-bit wide channel in some
manner.  We are back to square one.

On the other hand, if the "borrowed" bits are taken at random
(the random source being the key to a spectrum spreading
algorithm) among the bits of the digitizing word size, our
message is not only safely encrypted, but there is no way to a)
say where it is, b) say what it contains, c) know for sure that
it is indeed there.

On the down side, we will get the equivalent of white noise in
the digitized piece.  If your hiding place is a digitized
picture, it will look like a case small-pox and if it is music
you'll think we are back in the age of cheap vinyl.  This is
enough to weaken points a) and c), above.  So why not bias the
random key so it tends to favor low order bits?  The picture will
just gain a bit of romantic haze, and the music will pick up a
touch of tape hiss, elegantly disposed off with a Dolby NR machine...

If you are interested, I suggest you consider [trumpet triumphal]
The Braid [drum roll] yes, my own baby! Look it up for details on
how it is done (just add low bias).

The Braid (donated to PD (yet another drum roll)) will distribute
hidden information in such a way that even a known plaintext
attack will fail, first because any plaintext at all can be found
in the final product if one looks hard enough, second because it
is not possible to prove that a message is indeed hidden there,
third because even if you know that it is there you can't find it
without the key.  And the Braid, if you so wish, borrows another
bit to manage key distribution.

Can you imagine the outlawing of digitized material?



--
 Alain
 [ ... usual disclaimer... ]