Weak steganography

-----BEGIN PGP SIGNED MESSAGE-----

Responding to Mike Diehl's ideas about weak steganography: (Speaking of
which, did anyone notice that there weren't any stegosaurs in Jurassic
Park?  Just another sign of the government crackdown on crypto?)

There are a couple of problems with the idea of sticking encrypted
files onto the end of executable files.  The first is, to make this
easy, you need a program to do it (and to "undo" it).  Well, if someone
steals your computer and gets access to these files, they will probably
also get access to this program.  This will tip them off to what you have
done.

This is an example of the general principle that you need to assume that
your attackers know or can discover the methods you are using, but they
don't know the keys.

Another problem is that encrypted files look different from executable
files.  Encrypted files have a uniform histogram (that is, all 256 different
possible byte values are equally frequent), but exe files do not.  The
appending of an encrypted file to an executable file will be very obvious.
The exact boundary may not be immediately apparent, but it can probably
be narrowed down to ten or twenty words without much effort at all.  In
any case, exe files which have had this treatment will stick out like a
sore thumb.

Last, XOR'ing a PGP file with a repeated string is probably not a very
good method.  PGP has a header at the front whose structure is known and
which has some fixed bytes.  These can be used to immediately recover some
letters of your string.  Given that the string is mnemonic (memorable) it
may be possible to guess more of it.  Again, this is basically effortless
and it narrows down the search space considerably before they even start
to try to break it.

Of course, even if they recover the original PGP file they would then need
your pass phrase to decrypt it.  If you are assuming that they already had
that then they didn't need to go through the rigamarole of deducing the
repeated string which cloaked the PGP file; once they found an executable
with a uniform histogram at the end, along with your program which creates
such files, that should be enough evidence to force you to reveal the string
just as you were forced to reveal your pass phrase.

In sum, I don't think this approach will help much.

Hal Finney
74076.1041@compuserve.com

-----BEGIN PGP SIGNATURE-----
Version: 2.2

iQCVAgUBLCBm8agTA69YIUw3AQFbMAQAqsZE3Zs3oC1RcTqZ+yGDv0uf0avWUI9N
l7Lr+XlOxryu7m7zo7S2knZIjUMa6a0v0EolnpPw/tK0SUkqGwOBrdfkn8BNPIM6
uZe9kzhJJYbc+w+TQqPB8PoVc3ZQ78OAOwyvhdu28KwG6kXLO4mCiX9n6faIDK1I
3G4Ez8v+6Xg=
=F8de
-----END PGP SIGNATURE-----

Hal Finney writes:

> Responding to Mike Diehl's ideas about weak steganography: (Speaking of
> which, did anyone notice that there weren't any stegosaurs in Jurassic
> Park?  Just another sign of the government crackdown on crypto?)

No, the stegosaurs were not in the Jurassic Era...they were in the
*Cryptozoic* Era. At least according to my copy of PGP ("Pretty Good
Paleontology").
 

-Tim

(P.S. I wonder what kind of DNA they'll get from the "Nine Princes in
Amber"?)


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^756839 | Public Key: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.

According to nobody@soda.berkeley.edu:
> There are a couple of problems with the idea of sticking encrypted
> files onto the end of executable files.  The first is, to make this
> easy, you need a program to do it (and to "undo" it).  Well, if someone
> steals your computer and gets access to these files, they will probably
> also get access to this program.  This will tip them off to what you have
> done.

The technique I advocated was so simple, I could code it on my lunch hour at 
work.  I did.  If you didn't want to have such a thing on your machine, you 
could store it remotely, either on an ftp site or a local bbs.  Clean up 
your hard disk and there is no sign of anything.

> This is an example of the general principle that you need to assume that
> your attackers know or can discover the methods you are using, but they
> don't know the keys.

If steganography is to work, we must find ways to make this "principle" invalid.
Strong encryption will protect our "plain-sight-text."  It falls to Data-hiding
to protect our cyphertext.

> Another problem is that encrypted files look different from executable
> files.  Encrypted files have a uniform histogram (that is, all 256 different
> possible byte values are equally frequent), but exe files do not.  The
> appending of an encrypted file to an executable file will be very obvious.
> The exact boundary may not be immediately apparent, but it can probably
> be narrowed down to ten or twenty words without much effort at all.  In
> any case, exe files which have had this treatment will stick out like a
> sore thumb.

I was going to suggest, but Phil beet me to it, that we compress our executables

> Last, XOR'ing a PGP file with a repeated string is probably not a very
> good method.  PGP has a header at the front whose structure is known and
> which has some fixed bytes.  These can be used to immediately recover some

Well, we could do a lot of things here.  We could have the option of xor'ing,
adding, or subtracting....  We could add random bytes to the cyphertext, at 
offsets we specify and memorize....  I still think this could be done, and that
it would work.  If anyone else shares my enthusiasm, I'll try to get it coded up

+-----------------------+-----------------------------+---------+
| J. Michael Diehl ;-)  | I thought I was wrong once. | PGP KEY |
| mdiehl@triton.unm.edu |   But, I was mistaken.      |available|
| mike.diehl@fido.org   |                             | Ask Me! |
| (505) 299-2282        +-----------------------------+---------+
|                                                               |
+------"I'm just looking for the opportunity to be -------------+
|            Politically Incorrect!"   <Me>                     |
+-----If codes are outlawed, only criminals wil have codes.-----+
+----Is Big Brother in your phone?  If you don't know, ask me---+