more steganography talk
jim at bilbo.suite.com
Fri Mar 4 12:06:36 PST 1994
Stuff that Sergey Goldgaber, Hal, and others wrote induced the
following ideas in my head:
Goal - create a steganography system that hides cyphertext in such a
way that only the true recipient of the message will be able to prove
an encrypted message is hidden within a public message. Nobody else
will be able to determine if the public message also contains an
embedded encrypted message. In Hal's words:
> A test, then, for the success of a steganographic
> technique is this: given some sampling of data items,
> half of which have embedded hidden messages, can the
> opponent guess which ones have such messages with better
> than 50% accuracy? If not, the steganography is fully
> successful. If he can do slightly better than 50%, it may
> still be useful depending on the situation. If he can
> guess with 100% accuracy, the steganography has failed
> and is totally worthless.
If the LSBs of most picture files were truly random, then good
steganography would be trivial. Anyone could just plop an
unremarkable encrypted message (Stealth-PGP) in the LSB's, starting
at the beginning of the file. Since one sequence of truly random
bits statistically looks like any other sequence of truly random
bits, nobody would be able to prove the picture file contained a
hidden encrypted message.
Unfortunately, I doubt that most, or even many, picture files have
truly random LSBs. It would be possible to write frame grabber or
scanner software to purposely place random bits in the LSB of picture
files to generate a source of useful picture files. When this
software became widely used, good steganography would become trivial.
Unfortunately, I don't have much confidence that this could be pulled
off on a large enough scale. If it could be done, great, but I'm not
holding my breath.
Assuming the LSBs of most picture files are not truly random, and
wont be any time soon, the next approach to good steganography would
be to figure out how to transform a sequence of random bits (your
encrypted message) into a sequence of bits that resemble the kinds of
bit patterns you see in typical picture files. If you could do this,
and do it without requiring more secret keys, then good steganography
becomes trivial again.
[Actually, you don't have to transform your random bits into a
*sequence* of typical picture file LSB bits. The steganography
algorithm could deposit the bits anywhere in the picture file, as
long the process was reversible and the result was undetectable.]
"Reversible, undetectable, without requiring additional keys."
Sounds like a good set of requirements for a steganography system.
I have an idea to help with the "reversible" part and the "no
additional secret keys" part, and it suggests a direction for the
The idea: Encrypt a widely known value with the recipient's
public-key and use the result as an initialization vector for a
clever transformation/steganography algorithm. The message recipient
recovers the encrypted message by re-calculating the initialization
vector using the same widely known value and his public-key and
reversing the transformation/steganography step.
The initialization vector will be different for each message
recipient. The "widely known value" could be a large block of bytes.
A large file of random bits could be shipped with the steganography
executable. The intent is to make it more difficult and time
consuming for the opponent to determine if a public message contains
a hidden encrypted message.
It's not fool-proof. The opponent could try to discover a hidden
message by reversing the process using every known public-key.
Worse, an opponent could narrow the search by only trying the
public-keys of suspected recipients. However, I think it is an
improvement over the techniques being used today.
One significant property this technique does *not* possess is
deniability. A perfect steganography system will produce results
that will let a recipient claim that they did not know a message
contained a hidden encrypted message (e.g. most picture files had
truly random LSBs). If somebody sent you a hidden message using your
public-key and the initialization vector technique, your claim of
ignorance might not hold up. Anybody could use your public-key to
recover the random bit sequence. They would not recover the contents
of the hidden message, but they would be able to show that your file
did contain what appears to be a hidden message. It might be enough
to tip the scales of justice against you.
In my mind, the perfect steganography system depends upon either an
environment containing ubiquitous random bit sequences or a
reversible algorithm that can transform non-random bit sequences into
random bit sequences without using encryption (unlikely). However, I
believe a less-than-perfect, but still useful steganography system
could be created using the initialization vector technique described
Jim_Miller at suite.com
More information about the cypherpunks-legacy