authentication without public keys

[ted at nmsu.edu]

Chris Torek writes:

    The trick is to encrypt the trial password with a different key.
    The authentication server sends the client a new key, which has
    been encrypted with the client's private key; the client decrypts
    the string using its private key to obtain the temporary key.  The
    client then uses the temporary key to encrypt the trial password,
    and sends that to the server; the server decrypts using the
    temporary key, encrypts using the user's private key, and
    compares.  If those match, the authentication server believes that
    the client is acting on behalf of the user.

This requires the use of public key cryptography.  Given recent
results in factoring (300 bit numbers are kind of factorable,
complexity growth rate is considerably less than n^0.1 so we need a
considerable increase in key size to be safe for a limited time), it
might be wiser not to trust this sort of option.

It is possible, however, to use one-way encryption to accomplish the
same goal.  One-way encryption can arguably be made more secure
because even the no-one has to be able decrypt the message.
	
In order for to build an authentication server, we can have the
untrusted host use the plain text password as a key to one-way encrypt
a random test string passed to it from the authentication server.
This result is passed back to the authentication server as proof that
the untrusted host has access to the plain-text password.  If this
matches what the authentication server computes by the same process,
then it is known by the authentication server that the untrusted host
had access to the plain text password and can now be trusted.  Some
function of this plain text password can then be used as an initial
key in an invertable system for passing an initial key to encrypt
time-stamps on communications to prevent impersonation after
authentication.

This way, untrusted hosts only have a known plain-text attack on some
function of the plain-text password.  It should be possible to make
this attack much harder than normal plain-text attack by adding a
considerable amount of salt to the key.  The authentication server
must then search through all possible salts to verify the result
returned by the untrusted host, but it can make searching a list of
common passwords much less appetizing.

The use of the test string precludes the construction of an encrypted
list of passwords.

If we have the authentication server to validate user/machine pairs
instead of just users, then we can incorporate a secret password in
hardware on each machine.  A trusted user must provide a password to
the new hardware which is authenticated by the server as above, after
which the server is given an encryption of the new machine's hardware
password.  Since this step is only done once, the trusted user's
password can be much more difficult to guess than a normal password.
This hardware password is subsequently appended to the user password
and salt in the system outlined above.  To break this system, the
complete eavesdropper must either guess the initial difficult
password, or must guess the machine password.  An eavesdropper not
privy to the inital setup conversation must guess the machine
password.  On the other hand, the authentication server merely has to
do two verifications since the purported identity of the machine
asking for authentication is known.