The properties of the encryption method itself may also be a concern, although the primary concern is that the clear-text be random, which simplifies the constraints on the function E_S. Toward this goal, other recommended constraints for DH-EKE are:

SPEKE does not require these constraints, since it does not use symmetric encryption.

4.2.2    SPEKE partition attack

Using a primitive base is not required in SPEKE. If the base f(S) is an arbitrary member of Z_p^*, since the exponentials are not encrypted, an observer can test the result for membership in smaller subgroups. When the result is a primitive root of p, he knows that the base also is primitive. For a safe prime p, this case reveals 1 bit of information about S. When p varies, as has been recommended when using a reduced modulus size (§ 4.6, § 4.7), new information from runs with different p allow a partition attack to reduce a dictionary of possible S_i.

When, for any S, the base f(S) is a generator of a particular large prime subgroup, then no information is leaked through the exponential result. Suitable functions for f(S) create a result of known large order. One example is shown in § 4.13. One important limitation on f is discussed in § 4.12. We assume the use of a large prime-order base in SPEKE for the rest of the discussion.

Because SPEKE does not encrypt the exponentials, a formal analysis of security may be simpler to achieve for SPEKE than for DH-EKE. The prime-order subgroup is the same as that used in the DSA and Schnorr digital signature methods.

4.3    Subgroup confinement

In a subgroup confinement attack on a Diffie-Hellman exchange, the goal is to confine K to a predictable and small set of values, by causing one or both parties to use a number of a small order t as the base of exponentiation. Use of a safe-prime p = 2q+1 reduces, but does not eliminate the presence of small subgroups, as shown in figure 4.3. Even with a safe-prime p, Z_p^* still has the small subgroup G₂. We'll show two versions of the attack.

In the man-in-the-middle version of this attack described in [vOW96], both parties are unaware that Mallory has intercepted and modified the exponentials. Knowing that t is a small prime factor of p-1, Mallory intercepts both Q_A and Q_B and sends Q_A^(p-1)/t to Bob and Q_B^(p-1)/t to Alice. This converts the exponentials into generators of the small subgroup G_t. ^[1]    Both Alice and Bob go on to compute a shared value for K, which is confined to G_t. Mallory then has the easy job of finding K with a brute force attack. [vOW96] recommends the use of a large prime order subgroup to thwart this attack, making confinement to the only small subgroup G₁ trivial to detect. An alternate safeguard when the factorization of p-1 is known is to test K for membership in all small subgroups, and abort if it is confined.

We show that a confinement attack also occurs when Barry masquerades as Bob, and sends a value Q_B of small order t directly to the other. This is feasible in SPEKE, or in DH-EKE when Q_B is unencrypted. This one-side attack also results in K being confined to G_t, which gives Barry a 1/t chance of guessing K. He may get lucky with a tiny t. The middle attack is only a threat for SPEKE, since it requires that both Q_A and Q_B be sent unencrypted.

One path to a solution is to try to eliminate small subgroups in Z_p^*. The closest we can come to this is to select p as a safe prime, which yields the small subgroups G₂ and G₁. An easy solution for SPEKE is to test the value of K. In this case, insuring that K is a member of G₂ prevents the attack. Each side tests K and only proceeds if 1 < K < p-1, since G₂ = {1, p-1}. For DH-EKE, another solution is to always encrypt both exponentials so that an attacker on either side cannot (feasibly) cause Q_x to be of small order.

Another approach to avoiding confinement in SPEKE is to test K for membership in all subgroups other than G_q, where q is a large prime, and f(S) is of order q. If K is found to be a member of any group other than G_q, then the protocol must be aborted. This is conveniently done if each receiving party raises Q_x to the power (p-1)/q before computing K. This forces K to be a member of G_q, so that testing to insure K does not equal 1 prevents any confinement. ^[2]    If Q_x is a member of G_q, then this extra exponentiation is just a one-to-one mapping that shuffles K to somewhere else in the group. The extra exponentiation adds negligible cost, since it can be performed as multiplication in the exponent.

4.4    Omitting encryption in DH-EKE

[STW95] shows that when the party who first receives verification of K from the other omits the step of encrypting the exponential, then DH-EKE is open to a dictionary attack on the password. [BM92] describes this attack as it applies to other public-key variants of EKE. In this description, presume that an attacker Abby is posing as Alice, and that the step of encrypting Q_A is omitted.

D1.	Abby computes:	QA = gRA mod p,	A®B: QA
D2.	Bob computes:	QB = gRB mod p,	B®A: ES(QB)
D3.	Abby yawns.
D4.	Bob computes:	K = h( QARB mod p )
D5.	Alice computes:	Abby chooses a random V,	A®B: V
D6.	Bob computes:	Bob chooses a random CB,	B®A: EK(CB, EK-1(V)))
D7.	Abby leaves the building.

In this case, Abby has temporarily displaced Alice, and it may appear to Bob as an ordinary communication failure. At this point Abby performs the off-line attack:

      For each S_i,
          Decrypt E_S(Q_B) with candidate password S_i to obtain candidate Q_B'.
          Compute K' = Q_B' ^R_A.
          Decrypt V with K' to get C_A'.
          Decrypt E_K(C_B, E_K^-1(V))) with K' to get (X_B, X_A).
          If X_A equals C_A', Abby knows that S_i = S.

The problem is due to the fact that the protocol makes Bob show his knowledge of K before Abby shows hers. This attack will not succeed if the order of verification is changed so that the first to receive proof is not the same party as the sender of the unencrypted exponential.

Encryption is a delicate issue in DH-EKE. Omitting one of the encryptions in DH-EKE raises the possibility of either this protocol attack, or the one-sided small subgroup confinement attack described in § 4.3. On the other hand, the presence of encryption poses the threat of the partition attack that must be dealt with carefully as described in § 4.2.1.

The protocol attack described here is not possible in SPEKE. In SPEKE rather than encrypting Q_x with the password, the password is hidden on each side by raising it to a random exponent. In order to compute K given Q_A and Q_B, one must either derive the value of R_B from Q_B or derive R_A from Q_A. This requires a discrete log computation.

4.5    Using a short modulus

To increase the speed of exponentiation, the modulus size can be reduced. But since the huge size of the modulus is a cornerstone of DH security, we must be extremely careful here. If the modulus size is reduced well below, say, 600 bits, the threat of discrete log attack becomes significant. [BM92] argues both for and against a decreased modulus. We summarize the debate here.

Pro: A decreased modulus size makes the method faster.

Con: A decreased modulus size permits feasible (though expensive) discrete log attack.

Con: Also, for a session established with a modulus vulnerable to log attack, perfect forward secrecy is no longer guaranteed (see § 4.9).

Pro: The log attack can be mitigated by a user-specific or frequently-changing modulus. This is a disincentive for a third-party attacker to spend much time or money computing a discrete log for a particular number.

In order to synchronize a variable modulus for both parties, it has been suggested that one party choose the parameters for the other [BM92, Jas96]. This raises new issues of trust. We must now ask whether an attacking party could maliciously choose parameters so as to gain information about the password from the other, or to make it easier to obtain a key without using the proper password.

4.6    Uncertified ephemeral parameters

We continue the debate, which is now in terms of whether or not one party should choose the ephemeral DH parameters. Presume that Bob chooses p and g randomly from a pre-computed set, and sends them to Alice prior to the exchange. As we maintain our goal of not requiring persistent public keys, these parameters must be uncertified. So, how can Alice trust them?

Con: Barry masquerading as Bob can deliberately send Alice a non-prime or non-safe prime modulus and/or a base with properties that aid in a partition attack against Alice's password (as described in § 4.2).

Pro: Alice can use primality and other tests to insure that the parameters are safe. [BM92]

Con: Practical tests for primality are probabilistic, and are only guaranteed to work for small or randomly chosen huge primes. An attacker might be able to deliberately create a non-prime that can pass Alice's test, and lead to an attack. (Also, [BM92] refers to a communication with Odlyzko about a potential "trap door" modulus, without further explanation.)

A simple way to avoid the debate is to embed fixed safe parameters in the system, where the modulus is large enough to "permanently" preclude the discrete log attack. It has been suggested that 1000 or 2000 bits is adequate for long-term security. The use of a short exponent as is discussed next may make this practical for many situations.

Constraint	Reason	Reference	Applies to
Test that p is prime	non-prime p with calculated log	[BM92]	D S
Test that q is a large prime	non-safe prime p with calculated log	[BM92]	D S
Certified parameters	p has hidden trap door (?)	[BM92]	D S
Certified parameters	chosen false-prime p or q	§ 4.6	D S

If we continue the debate in search of a safe way to use a smaller modulus, the analysis becomes more complex. To end our discussion on a positive note, we ask whether there may be some perfect test that Alice can efficiently perform to guarantee that the parameters are trusted to not leak information in the first stage, at least until Bob proves who he is. Toward this goal we note that SPEKE can operate in a large prime subgroup of order q << p, and that perfect primality tests for non-huge q are possible.

It may also be interesting to consider the case where p and q are also kept secret, possibly within a tamper-proof hand-held device. Though this violates our characteristic 5, it might be useful if the modulus size must be imprudently small. Considering a normal SPEKE exchange with p, q, and S kept secret may also be of interest.

4.6.1    A user-to-station protocol

If despite the warnings in the preceding section, we still desire to let Bob choose the DH parameters for Alice, we may want to omit our desired characteristic 5b of § 2. Bob can sign the parameters with his private key, and require all users to have a certified copy of his public key to verify the signature. Note that this may impose less of a key management problem than the dual-signature approach used in the Station-to-Station protocol [DvOW92] (also see § 7). If Bob is a relatively secure site compared to Alice, his key may change only rarely. Further, if parameter generation is performed by a trusted authority at a secure central site, we might embed a public key of the trusted authority in read-only memory within all parties' systems. The trusted authority would periodically send out lists of certified safe parameters.

4.7    Using a short exponent

A less radical approach to increasing speed is to decrease the exponent size to be merely large, leaving the modulus huge. [vOW96] discusses this in detail. The number of bits in the exponents must be at least double the number of bits (t) that are required for K, but this is typically much less than the number of bits in p.

Their conclusions suggest two safe approaches, where the exponents can be reduced to size 2t bits:

1. Use a huge safe prime modulus p with a primitive base of 2, or better yet, a prime-order base of 2.
2. Use a huge prime modulus p with a base of large prime order q, where q has at least 2t bits.

The first approach works with either DH-EKE or SPEKE, although DH-EKE needs further protection from the small-subgroup confinement attack. Using a base g = 2 further increases the speed. When g = 2, note that the two methods cannot use the same safe primes. A safe prime p suitable for DH-EKE must have 2 be a primitive root of p (see § 4.2.1), while a safe prime p suitable for SPEKE should ideally have 2 be of order q.

The use of a large prime subgroup where q << p has the advantage of speeding up the generation of the DH parameters. This works with SPEKE, but it cannot be used with DH-EKE which requires a primitive base.

4.8    More desirable characteristics

In [DvOW92] the security of general authenticated key exchanges is discussed, and several desirable protocol characteristics are described. We start numbering these at 6 to add to the five characteristics listed in § 2.

   6. Perfect forward secrecy
   7. Direct authentication
   8. No timestamps
   9. Hidden identity.

Perfect forward secrecy means that disclosure of the password doesn't reveal prior recorded conversations. Direct authentication means that both sides verify the session key before proceeding. No timestamps means that the messages do not contain time-dependent data, which might require time synchronization between the parties. Without further discussion, we note that both DH-EKE and SPEKE meet the first three objectives.

Only the ninth characteristic, hidden identity is problematic. Neither of the methods described here hides the identity of the user from a passive observer. This limitation could be overcome with an additional prior standard DH exchange that establishes an unauthenticated key, to encrypt the user's identity. A man-in-the-middle attack would reveal this hidden identity, perhaps at the expense of being detected. We also note that while the somewhat-related Station-to-Station protocol (§ 7) can hide identity from passive attack, it also reveals identity to a man-in-the-middle at the expense of disrupting the run.

The problem of authenticating with a perfectly-hidden identity seems to be intractable without using a previously established secure session or large public keys. In these methods, the problem is related to the fact that the secret is shared. In order to choose the appropriate secret for a particular party, one needs to know the identity of the party prior to the exchange. However, prior to the exchange we assume that no secure channel exists over which to send the identity. We forgo any further analysis of this chicken-and-egg problem.

These characteristics have been covered in the referenced literature, with respect to key exchanges in general. At least one more desirable characteristic of these password methods is revealed as we consider the next attack.

4.9    Stolen session key attack

In an analysis of several flavors of EKE, [STW95] describes a variation of what they refer to as the Denning-Sacco Attack, where a stolen session key K is used to mount a dictionary attack on the password. The attack on the public-key flavor of EKE is also noted in [GLNS93]. [STW95] correctly points out that DH-EKE resists this attack (as does SPEKE). Resistance to this attack is closely related to perfect forward secrecy, which also isolates one kind of sensitive data from threats to another.

We note that, in DH-EKE, a stolen value of R_A in addition to K permits a dictionary attack against the password S. For each trial password S_i, the attacker computes:

K' = (E_Si^-1(E_S(g^R_B)))^R_A

When K' equals K, he knows that S_i equals S. SPEKE is also vulnerable to an attack using R_A to find S. These concerns highlight the need to promptly destroy ephemeral sensitive data, such as R_A and R_B.

[STW95] also notes a threat when the long-term session key K is used in an extra stage of authentication of the extended A-EKE method [BM94, and § 7], a dictionary attack is possible using the extra messages. To counter this threat, one can use K for the extra stage, set K' = h(K) using a strong one-way function, and promptly discard K.

4.10    Verification stage attacks

The verification stage of either DH-EKE or SPEKE is where both parties prove to each other knowledge of the shared key K. Because K is cryptographically large, the second stage is presumed to be immune to brute-force attack, and thus verifying K can be done by traditional means. However, the order of verification may be important to resist the protocol attack against DH-EKE as was discussed in § 4.4.

4.11    Detecting on-line attack

The threat of repetitive on-line guessing by a masquerading user can be mitigated by a careful logging and accounting of invalid access attempts. The idea is to limit the number of illegal access attempts against any single password, and require that the password be changed before the threshold is exceeded. The threshold should be based on the known (or suspected) size of the password space. It is also advantageous to keep separate per-password and total system counts of invalid attempts to detect both attacks on a single account, and broad-scale attacks that do not exceed any single user's threshold.

It may be tempting to try to distinguish between accidental mistakes and illegal attempts, by noting that most mistakes are followed immediately by a valid access. However, a clever attacker may be able to anticipate or delay a legitimate run, and perform a few quick guesses against the same account before letting the legitimate run succeed. Thus, even apparently accidental mistakes should be counted, by both parties, and viewed with suspicion.

The case of a masquerading host is a little different. Whereas the host usually has long-term storage for logging errors, the user's system may not. It is generally foolish to rely completely on the user himself to enforce security policy dealing with suspicious bad attempts. The user's system should at least keep a short-term count of bad attempts and (securely) update the host with this count the next time access is granted. The host may also alert the user of bad access attempts at this time. These methods greatly deter guessing attacks against both the user and the host.

4.12    The "password-in-exponent" attack

It is generally a good idea for f(S) to create a result of the same known order for all S, so that testing the order of the exponential doesn't reveal information about S. When considering suitable functions, it may be tempting to choose f(S) = g_c^h(S) for some fixed prime-order g_c and some well-known hash function h. Unfortunately, while this is a convenient way to convert an arbitrary number into a generator of a prime-order group, it creates an opening for attack. ^[3]

To show the attack, let's assume that g_c = 2, and h(S) = S, so that f(S) = 2^S. Alice's protocol can be rewritten as:

    Choose a random R_A.
    Compute Q_A = 2^{(S R_A)} mod p.
    Send Q_A to Bob.
    Receive Q_B from Bob.
    Compute K = Q_B^R_A mod p.

Bob should perform his part, sending Q_B to Alice. The problem is that an attacker Barry can perform a dictionary attack off-line after performing a single failed exchange. His initial steps are:

    Choose a random X.
    Compute Q_B = 2^X.
    Receive Q_A from Alice
    Send Q_B to Alice.
    Receive verification data for K from Alice.

Barry then goes off-line to perform the attack as follows:

    For each candidate password S':
      Compute K' = (Q_B^X)^1/S' mod p.
      Compare Alice's verification message for K to K',
      when they match he knows that S' = S.

This attack works because:
      K' = Q_A^(X/S') mod p
            = 2^{(S R_A)(X/S')} mod p
            = 2^{(X R_A S/S')} mod p
            = Q_B^{(R_A S/S')} mod p
            = K^(S/S') mod p

Thus, when S' = S, K' = K. More generally, the attack works because the dictionary of passwords {S₁, S₂, ..., S_n} is equivalent to a dictionary of exponents E = {e₁, e₂, ..., e_n}, such that for a given fixed generator g_c, the value of f(S_i) for each candidate can be computed as g_c^e_i. This allows the password to be effectively removed from the DH computation.

In general, we must insure that no such dictionary E is available to an attacker. We should note that while it is true that for any function f there will always be some fixed g_c and hypothetical dictionary E that corresponds to f(S), for most functions f, computing the value of each e_i requires a discrete log computation. This makes the dictionary E generally unknowable to anyone. As a specific example, for the function f(S) = S, the attack is infeasible.

The password-in-exponent attack is possible only when f(S) is equivalent to exponentiation (within the group) of some fixed gc to a power which is a known function of S.

The attack is also a problem for DH-EKE, when E_S(x) = x^S and E_S^-1(x) = x^1/S. Although [BM92] doesn't discuss this case, they describe how this class of attack affects the PK-EKE protocol, attributing discovery of the problem to Li Gong.

4.13    Choosing f(S)

As discussed earlier, a preferred choice of f(S) in SPEKE creates a generator of prime order. An easy way to avoid the attack in §4.12 is to use f(S) = S^(p-1)/q mod p. For safe prime p, f(S) = S².

4.14    Application to Kerberos

[Jas96] applies the DH-EKE method to Kerberos authentication between a client and the Key Distribution Center (KDC). The goal is to simultaneously solve three long-standing limitations in the system, related to dictionary attacks, dependence on timestamps, and password chaining. Password chaining is the ability of an attacker to use an old password to determine a new one. The reference describes how DH-EKE prevents this. The proposal uses a mild form for ordinary login, and a strong form for specially protecting the password-change protocol. The proposed protocol (PA-ENC-DH) uses only the first stage of DH-EKE, and omits the verification of K.

By omitting verification of K, there is no direct authentication. One result is that the KDC cannot distinguish valid from invalid access attempts; It can only count the total number of attempts. A tradeoff is being made between the size of the minimally secure password and the total number of allowed uses. Such a system may be impractical for protecting very small passwords. A system that performs direct authentication by verifying K and distinguishing valid from invalid attempts would be friendlier. With this improvement, the frequent user who rarely mistypes his password is not penalized with frequent demands to change the password.

5    A fully constrained SPEKE

Despite the length of the preceding analysis and discussion, a fully constrained SPEKE method is simple in structure. The description here presumes a well-known safe prime p and random numbers R_A and R_B of suitable size. Other formulations are possible.

Stage 1:
      A®B: Q_A = S^{(2 · R_A)} mod p.
      B®A: Q_B = S^{(2 · R_B)} mod p.
      Alice: K = Q_B^{(2 · R_A)} mod p.
      Bob: K = Q_A^{(2 · R_B)} mod p.
      Each aborts if K < 2.

Stage 2:
      B®A: V_B = h(h(h(K))).
      Alice verifies V_B.
      A®B: V_A = h(h(K)).
      Bob verifies V_A.

Both then compute the shared authenticated session key K' = h(K), and both promptly destroy all copies of K, R_A, R_B and, if possible, S.

Our constraints would not be complete without mention of the often controversial subject of bit-lengths. Following the standard sizes used for the DSA [NIST94], using 512 to 1024 bits for p and 160 bits for random exponents, resulting in an 80-bit K, may be sufficient for many uses. Using 1024 bits for p and 336 bits for the exponents has been recommended for DH-EKE in [Jas96] for long-term safety.

6    Other limitations and possibilities

Here are some apparent limitations of any password-only scheme, in light of dictionary attacks:

Without an interactive method, the password verification messages can be used in simplistic dictionary or replay attacks. Both parties must be active participants. We further accept that anyone in a position to verify the password can find it with brute-force. This can be done by simulating the actions of the other party using each candidate password. This limitation is mentioned in [BM92].

Passwords as private-keys in a public-key system would be wonderful, but the holder of the corresponding public-key is then in a position to perform dictionary attack -- which defeats the purpose of a public-key. Further pursuit along these lines leads into the domain of identity schemes, which are quite complex and involve a trusted third-party. [Sch96 p. 115]

Password methods are attractive for their simplicity, convenience, and strength. Where the password can be memorized, it need not be recorded and possibly stolen. The attraction of key-based methods is in the richness and power of public-key and non-interactive techniques. By carefully setting expectations, both classes of methods can be widely promoted. Strong hybrid systems can use independent key-based and password-only methods to complement each other.

Need for a trusted path

One of the limitations of any password method is reflected in the need for a trusted path. In a classical system this refers to the integrity of the entire system from the user's fingers at a keyboard to the final destination where the password is verified. In a network, password-only methods can be used to "shorten" the trusted-path to end at the software on the user's local processor. The path no longer requires a prior secure network channel. However, any risks to the integrity of the local system are still relevant.

Formal verification

Although strong password-only methods based on Diffie-Hellman have been studied for several years, more formal analysis of the security of SPEKE and other methods would be valuable. Due to its simple structure, SPEKE may more easily facilitate such analysis. The ability to use a prime-order subgroup may also be significant in this regard.

7    Other related work

Only a few other password-only methods have been designed that successfully address the goal of preventing off-line dictionary attacks. More complex variations of EKE using public-key encryption are described in [BM92]. DH-EKE and SPEKE have an advantage over these in being extensible to allow the host to store a one-way hashed form of the password, in methods such as A-EKE [BM94]. In these extended methods, Bob uses the one-way hashed password to verify possession of the clear-text password by Alice. When using this type of extension, we make Alice compute the hashed form, and use S to represent the hashed password in the first stage of the exchange.

A few other approaches to strong password-only protocols have also been explored, with varying degrees of success and complexity.

[GLNS93] describes both three-party and two-party protocols based on using secret public keys. The authors express a concern about finding a suitable public-key method for these protocols, which require that any random number of appropriate length be a valid public-key. The paper further describes stored-public-key-assisted protocols, and discusses guessing attacks, Kerberos login, the important concept of verifiable plain-text, which was originally introduced by these authors.

[Gon95] describes an optimal 3-message version of the two-party secret-public-key protocol. [STW95] shows an optimal 3-message form of DH-EKE, which applies equally well to SPEKE. ^[4]

Fortified Key Negotiation [Sch96 p. 522], [And94] is another method which resists dictionary attack, at the expense of reducing the effective size of the password space.

Other variations on the password-only theme are three-party exchanges, where multiple shared secrets are held by a common trusted authentication server who mediates the process of exchange between two parties. [STW95] points out a weakness in some instances of these.

An earlier promising approach was the Shamir and Rivest Interlock Protocol, as used by Davies and Price, of which a brief historical account appears in [Sch96 pp. 54-55]. An attack on the Interlock Protocol for authentication is described in [BM93], and a recent attempt to patch this hole is described in [Ell96].

The Station-to-Station protocol described in [DvOW92] is interesting for the sake of comparison, although it depends on the deployment of private and public keys, in violation of our desired characteristic 5 (§ 2). The protocol uses a DH exchange and encrypts the exponentials in a manner similar to DH-EKE, but using public-key encryption.

Still further away along the spectrum of methods are identity-based schemes, which can use zero-knowledge ideas to prove knowledge of a secret held by another party. These do not provide an authenticated key exchange, and they do not allow the "secret" to be cryptographically small. A brief review of these is also included in [DvOW92].

8    Uses of password-only authenticated exchange

With a strong password-authenticated key exchange, even small passwords can be safely used. The host is presumed to detect and deter on-line attacks, and the protocol itself prevents off-line attacks. These methods are ideal in some applications for several reasons: secure key storage can be problematic, large-key input can be cumbersome, and passwords may need to be better protected. Several applications for strong password-only exchanges are mentioned here.

In § 4.14 we discussed using DH-EKE or SPEKE to correct deficiencies in Kerberos. The same ideas can be used to upgrade many other vulnerable network login systems, which can be essential for new uses such as personal-computer remote banking, and general computer login over the Internet.

In systems where only a numeric keypad is available, such as cellular telephone authentication, a secure, short numeric password is especially convenient. TV remote-controlled set-top boxes might be another area of new applications. These environments may also preclude long-term storage of persistent keys.

Diskless workstations are another class of device where it is inconvenient to have locally stored keys. Password-only methods are ideal for establishing an initial connection to a trusted host, and to obtain the user's safely stored credentials. This concept of remote storage of long-term credentials with a secure download has been used in the SPX authentication system. [TA91]

Any device or system that uses these methods can be generic, in that it is not preprogrammed to speak only for a particular user, or to speak to any particular host. Alternative approaches using a persistent public-key need to embed a key which designates a specific trusted authority. This can be inconvenient. Password-only methods make it easier to deploy a system that has no such embedded prior agreement. This model may better fit the "commodity" market model for software and hardware devices.

The concept of bootstrapping a new secure system is broad, and is best illustrated with a common case. You're installing a new network workstation from a CD-ROM. Somewhere during installation you're prompted to enter a name and password to let you join the secure corporate network. Unless some additional site-specific keys are manually installed on the system, a strong password-only method is needed to allow the new station to make a secure channel to the rest of the network. Once an authenticated channel is established, the station can automatically obtain any further credentials or keys. Similar "bootstrapping" situations arise in almost all secure systems.

Though we've focused so far on user-to-host authentication, password-only methods may be important for direct user-to-user authentication. [Ell96] describes the use of an interactive series of questions and answers to authenticate the identity of an "old friend, out of touch" across a network. The idea is to prove to each other that they know common facts, without revealing those facts. Such situations are actually quite common. Password-only methods solve this general authentication paradox, which is present even in some face-to face situations. For example, you may want to prove that your bank knows your "secret" account numbers, and your bank wants you to prove that you know your "secret" social security number, but neither wants to reveal the information directly to the other. This is solved by these methods. Of course, given that much of this type of shared information is not as secret as we'd like it to be, a series of exchanges may be needed to prove further small amounts of shared knowledge, to build confidence in the authentication.

Multi-factor authentication may be needed when neither a stored key nor a memorized password is strong enough. In a hybrid system, one should strive to make the password an independent factor, so that its security does not depend on persistent stored keys, and vice-versa. Password-only methods can be combined with key-based method to build systems that can tolerate either a stolen password or a stolen key.

9    Summary

We've introduced a new password-only authentication protocol, SPEKE, which appears to be at least as strong as the closely related DH-EKE method. Using only a small password, these methods provide authentication and key establishment over an insecure channel, and are immune to off-line dictionary attack.

A review of the classes of attack against these DH-based methods includes some new observations, and new constraints which are required to keep both methods safe. These constraints are listed as a convenience to implementors. Concerns raised about receiving unauthenticated DH parameters argue for the use of either a fixed huge modulus, or certified parameters, or the need for further research. In any case, it is practical to increase speed by using shorter exponents.

Strong password-only methods have many uses, by themselves, or in multi-factor authentication systems. It is apparent that password-only methods can achieve things that no stored-key method can achieve, and vice-versa. A well-designed system can leverage the power of small, easily-memorized passwords, adding significant strength to the foundation for remote security.

10    References

[And94] R. J. Anderson and T. M. A. Lomas, "Fortifying Key Negotiation Schemes with Poorly Chosen Passwords", Electronics Letters, v. 30, n. 13, June 23, 1994, pp. 1040-1041.

[Bel96] S. M. Bellovin, private communication.

[BM92] S. M. Bellovin and M. Merritt, "Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks", Proceedings of the I.E.E.E. Symposium on Research in Security and Privacy, Oakland, May 1992.

[BM93] S. M. Bellovin and M. Merritt, "An Attack on the Interlock Protocol When Used for Authentication", I.E.E.E. Transactions on Information Theory , v. 40, n. 1, January 1994, pp. 273-275.

[BM94] S. M. Bellovin and M. Merritt, "Augmented Encrypted Key Exchange: a Password-Based Protocol Secure Against Dictionary Attacks and Password File Compromise", AT&T Bell Laboratories (c. 1994).

[DH79] W. Diffie and M. E. Hellman, "Privacy and Authentication: An Introduction to Cryptography," Proceedings of the I.E.E.E., vol. 67, No. 3, pp. 397-427 (Mar. 1979)

[DvOW92] W. Diffie, P.C. van Oorschot, and M. Wiener, "Authentication and Authenticated Key Exchanges", Designs Codes and Cryptography", 2, 107-125, (1992)

[Ell96] C. Ellison, "Establishing Identity Without Certification Authorities", Proceedings of the Sixth Annual USENIX Security Symposium, San Jose, July 1996, pp. 67-76.

[GLSN93] L. Gong, M. Lomas, R. Needham, & J. Saltzer, "Protecting Poorly Chosen Secrets from Guessing Attacks", I.E.E.E. Journal on Selected Areas in Communications, Vol. 11, No. 5, June 1993, pp. 648-656.

[Gon95] L. Gong, "Optimal Authentication Protocols Resistant to Password Guessing Attacks", Proceedings of the 8th IEEE Computer Security Foundations Workshop, County Kerry, Ireland, June 1995, pp. 24-29.

[Jas96] B. Jaspan, "Dual-workfactor Encrypted Key Exchange: Efficiently Preventing Password Chaining and Dictionary Attacks", Proceedings of the Sixth Annual USENIX Security Conference, July 1996, pp. 43-50.

[McC90] K. McCurley, "The Discrete Logarithm Problem", Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, vol. 42, 1990, pp. 49-74.

[NIST94] National Institute of Standards and Technology, NIST FIPS PUB 186, "Digital Signature Standard", U.S. Department of Commerce, May 1994.

[PH78] Pohlig & Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", I.E.E.E. Transactions on Information Theory, pp. 106-110, January 1978.

[Sch96] B. Schneier, "Applied Cryptography Second Edition", John Wiley & Sons, 1996.

[STW95] M. Steiner, G. Tsudik, and M. Waidner, "Refinement and Extension of Encrypted Key Exchange", Operating Systems Review, vol. 29, Iss. 3, pp. 22-30 (July 1995).

[TA91] J. Tardo & K. Alagappan, "SPX: Global authentication using public key certificates", Proceedings of I.E.E.E. Computer Society Symposium on Research in Security and Privacy, Oakland, pp. 232-244, May 1991.

[vOW96] P. C. van Oorschot, M. J. Wiener, "On Diffie-Hellman Key Agreement with Short Exponents", Proceedings of Eurocrypt '96, Springer-Verlag, May 1996.

Appendix A Group theory relevant to Diffie-Hellman methods

Finite groups have interesting properties that are used in Diffie-Hellman and the SPEKE and DH-EKE methods discussed in this paper. Several finite groups can be used in DH, but for simplicity we limit discussion to Z_p^*, the group of integers from 1 to p-1, under multiplication modulo p, where p is a huge prime. Exponentiation modulo p is a one-way function, for suitable p, due to the difficulty of computing discrete logarithms.

Z_p^* is also known as the multiplicative group of the Galois field of integers modulo p, or GF(p)^*. When showing arithmetic within these groups, it is traditional to sometimes omit "mod p". As in any group, for any x and y which are members of Z_p^*, the product of x and y is also a member, and thus exponentiation always remains within the group. In other words:

• For any x,y which are members of Z_p^*, ((x * y) mod p) is a member of Z_p^*.

• For any integer n, and any x which is a member of Z_p^*, (xⁿ mod p) is a member of Z_p^*.

A prime where p-1 has only small factors is called smooth. Smooth primes are avoided in these methods because they allow a much faster discrete log computation [PH78], ruining exponentiation as a useful one-way function. It is easy to select a non-smooth prime by insuring that p-1 has a large prime factor q. Using a safe-prime of the form p = 2q+1, where q is prime, and where the base g is a primitive root of p, is commonly recommended in DH. However, other choices are sometimes preferable. [vOW96] recommends using g as a base of order q to force all results within the large prime subgroup G_q.

Note that a safe prime is somewhat different from strong primes, which refers to a more complex (and debatable) set of constraints for the prime factors of a number n = pq, in methods such as RSA.

Footnotes

[1] Let y = x^(p-1)/t for an arbitrary x. Since y^t = (x^(p-1)/t)^t is congruent to 1 mod p, it can be seen that the order of y is a factor of t. Since t is prime, y is either of order t or of order 1.

[2] From footnote 1 in § 4.3, we know Q_x is a member of G_q. Consider any G_t and G_q, q is prime, and t < q. We can see that the intersection of G_t and G_q = G₁. Since K is a member of G_q, if K is also confined to G_t, then K is a member of G₁, or K = 1.

[3] This attack was not noted in the Oct. '96 ACM CCR version of this paper. The problem was found independently by at least myself, Li Gong, and Susan Langford.

[4] Whether a minimal message protocol is truly "optimal" depends on the desired goal, and on the cost and speed of communication vs. computation. For example, optimizing SPEKE for minimal time to completion may require more than three messages to maximize parallel processing of both parties.

[*] An earlier version of this paper appeared in ACM Computer Communication Review, vol. 26, no. 5, Oct. 1996.

Copyright © 1996-1997 Integrity Sciences, Inc. All rights reserved.