Simmons Subliminal channels and more...

[Peter Wayner <pcw@access.digex.net>]

I too received a copy of Gus Simmons paper in the mail and I
called him on the phone to discuss it with him. He sent me 
a copy of his latest version of the paper. 

The significance of the paper is that it is possible to use
the DSS algorithm to send messages disguised as signatures. 
The specs for the DSS used by NIST required that it could not be used
to hold secrets. This would make it more exportable and this was
one of the reasons why RSA was not chosen as the DSS. 

On a more philosophical level, it shows that the DSS and 
the El Gamal system really aren't signature systems. They
convey extra information. That means that they really aren't
that different from RSA on a functional level.

The easiest way to understand how the message passing system 
works is notice that the DSS uses a random number to compute
the signature. If we could somehow recover this number, then
we could have the information. What's the simplest hidden
way to send a message? Let's say that you want to send a bit.
Just keep rerunning the algorithm with different random numbers
until the right parity appears. The real approach is more 
sophisticated than this. 

My personal feeling is that this shows how utterly impossible
it is to keep secret bits from hiding in the noise of the world.
If the NSA can't do it, then there is a good chance that no one
can. 

-Peter