General Crypto Question

[Ryan Malayter]

[Nicholas Paul Johnson]
...
>B could then verify the signature by generating the signature 
>from the M and S in the same manner as above, and then 
>comparing that signature to the one sent by A.
> 
>As the one-way hash function is "perfect", nobody could 
>determine S if he has a (message, signature) pair.
> 
>Am I thinking this out right, or am I missing something critical?

You have it basically right. In fact, this is the way most secure
password authentication systems work. Both the user and the server have
a shared secret, which is the password. The server sends a random
message over the wire to the client, which then concatenates the secret
password, and hashes the result. This hash is then sent over the wire
back to the server. Presuming the hash function is secure, an
eavesdropper cannot figure out the password, nor can they "replay" the
attack, since the random message used only once.

Sometimes the details change; in most modern systems only a hash of the
user password is stored on the server, so an "extra" hashing step is
required before concatenation at the client. Also, in systems like
Kerberos, a timestamp is part of the hashed authentication string, so
that a particular authentication session is "valid" for only a certain
amount of time. But the basic underlying idea of authentication as the
validation of a "signature" of a random message as you describe remains.

Of course, finding a secure way to share the secret (password) in the
first place can be difficult. But _Applied Cryptography_ illustrates
several protocols for this as well.

Regards,
Ryan Malayter
Bank Administration Institute
Chicago, Illinois, USA
PGP Key: http://www.malayter.com/pgp-public.txt
=========================
All problems can be solved by diplomacy, but violence and treachery are
equally effective, and more fun.