new authentication protocol, possible SRP alternative

From: Steven Alexander (fbi66_at_hotmail.com)
Date: 08/01/04 

Date: 1 Aug 2004 00:04:20 -0700

I've been studying authentication protocols lately and am interested
in verifier-based protocols that provide perfect forward secrecy.
I've designed a protocol that appears to me to provide the same
security as Wu's Secure Remote Password Protocol while requiring one
less modular exponentiation on both the client and server sides.
Additional symmetric encryption and hash operations are required on
both sides but should require less computation time than modular
exponentiation.

Obviously, protocol design is complicated and I'm interested in
hearing any opinions or analyses that people might come up with. My
own analysis is included at the end. I would also be interested to
hear any mistakes in my own analysis. Responses indicating that the
design appears strong are always welcome as well :) I hope I haven't
missed anything obvious but am prepared to find out that I have.

Thanks in advance to everyone who takes the time to look at this.

-steven alexander
alexander dot s _at_ mccd dot edu

Please send any replies directly to me as well as to the list. Use
the address above, the hotmail address I registered with is a
throwaway.

Notation:

H(x) = Hash of x
K[x] = Encryption of x with key K
K^-1[x] = Decryption of x with key K
g^x = shorthand for g^x mod p

Alice = client
Bob = server

P = Password
M = key derived from P, H(P)
r = random number generated by client(Alice)
s = another random number generated by client(Alice)
challengeX = randomly generated challenge

Bob stores:
X = M[r,s]
Y1 = hash(r)
Y2 = hash(s)

 Alice <------------------------------------------------------>Bob

1. "Alice" -------------------------->
2. <------------------------------------ g^b, X
 
        Alice computes <r,s> = P^-1(X)
        Alice computes Y1 = hash(r)
        Alice computes Y2 = hash(s)
        Alice computes (a * Y1 mod p) while Bob computes (b * Y1 mod p)
            Both sides compute K = g^(a * b * Y1)
        [using Y1 in the calculation of K ensures that Alice is talking with
someone who is Bob or has compromised Bob]

3. g^a, challengeA ------------------------------------------>

4. <---------------------------------------------- K[challengeA],
challengeB
                [ use challengeA to prevent Man in the Middle attacks ]

        Alice generates new r and s values (newR, newS) and calculates newX,
newY1, newY2

5. K[[Y2[r, newX,newY1,newY2], challengeB]
        Bob stores newX, newY1 and newY2
        Alice's knowledge of r ensures that Alice knows P and was able to
compute P^-1[X]. Bob computes H(r) to verify.
        r can be used to calculate Y1 which could be used to exact a
dictionary attack if K were compromised so it is doubly encrypted with
Y2

[ K can be used to encrypt further data or a new DH exchange can be
performed with those message encrypted with K].

My analysis (with a little bit of redundancy):

I am considering combining message 1 and 3. As it stands, Alice can
verify that Bob has provided a good value of X before sending g^a and
a challenge but this is probably not necessary. Alice initiates the
authentication attempt so denial of service is not an issue.

The server stores a verifier (Y1) rather than a plaintext equivalent.
Therefore, this information cannot be used directly to impersonate
Alice. A dictionary attack could be executed to find a P such that K
= H(P), <r,s> = P^-1(X) and H(r) = Y1 and H(s) = Y2.

X is a reminder to Alice as to the value r which is used for
authentication and the values s which is used to produce a key that
can be used for encryption of the new reminder, verifier and s values.

A salt is not necessary since a new random r and s are generated to
complete each authentication. Both of r and s should be as large as
the output of the hash function.

The return of challengeA by Bob proves that Bob knows Y1. An
attacker, Trudy, should not be able to generate a new message X such
that <r,s> = P^-1[X] and H(r) = Y1 without knowledge of P.

Alice encrypts challengeB with K to prove she knows K and thus was
able to compute Y1 using r derived from X with her password.

An attacker who discovers K (through psychic ability perhaps) should
not be able to find Y1 without solving the discrete log problem.

r, newX, newY1 and newY2 are random. Thus, an attacker who discovers
K should not be able to perform a dictionary attack on X to produce a
candidate s value that will allow computation of Y2 and trial
decryptions of r, newX, newY1 or newY2 since they do not have a
recognizable format.

An attacker who has control of Bob throughout an authentication
process will know K, X, Y1 and Y2. He will thus be able to recover
newX, newY1 and newY2 (trivial) but will not know the newR and newS
used to produce these values.

An attacker who recovers K will not be able to recover the values
newX, newY1 and newY2.

An attacker will not be able to substitute his own values for newX,
newY1 and newY2 provided CBC-mode encryption is used. If he tries,
challengeB will not decrypt correctly.

The server has no awareness of password changes. Because of this, the
protocol extends well to smart card usage. A smart card can generate
and save a random value that will be used as part of the key material
for the next authentication, this value will be used at the end of
this authentication to compute newX.

Replay attacks should not be a factor since a new verifier is
generated with every authentication.

Relevant Pages

  • Re: OTP Secure Authentication
    ... I've now revised my method of OTP authentication to prevent the type of bit-flipping attack ... Alice and Bob now use stored values for Y, which they each OTP encrypt and exchange. ... If an attacker flips bits, the sent value for Y will not match the stored value and Alice and Bob ...
    (sci.crypt)
  • Re: Voice encryption (Stream vs CBC mode)
    ... Peter Fairbrother writes: ... An attacker ... There are all sorts of security failures when the protocol doesn't ... include any authentication. ...
    (sci.crypt)
  • Re: How secure is Digest Mode compared to Integrated Authenticatio
    ... Secure authentication protocols like Integrated does not support ... Because the protocol never passes username/ ... document which delineates the weaknesses of Digest mode. ... password integrity is. ...
    (microsoft.public.inetserver.iis.security)
  • Re: Signatures and encryption headers
    ... breached when an attacker can modify the message received? ... But I see how the lack of authentication can cause the receiver to act ... not for the iv or other encryption ... A create a payload, S signs it with public key crypto (most likely ...
    (sci.crypt)
  • RE: Passwords with Lan Manager (LM) under Windows
    ... A device's security associations are contained in its Security Association Database ... Internet Protocol Security (IPSec) provides application-transparent encryption services for IP network traffic as well as other network access protections for the Windows 2000 operating system. ... As for "article you reference does indeed use the phrase "IPSec Authentication," but as any who reads it ...
    (Pen-Test)