Password-Based Protocols
7.1 Introduction
Cryptographic authentication relies on possession of a key by the party to be authenticated. Such a key is usually chosen randomly within its domain and can be of lengths from around 100 bits up to many thousands of bits, depending on the algorithm used and security level desired. Experience has shown [109, 333] that humans find it difficult to remember secrets in the form of passwords of even seven or eight characters. But if all upper and lower case letters are used together with the digits 0 to 9 then a random eight- character password represents less than 48 bits of randomness. Therefore we can conclude that even short random keys for cryptographic algorithms cannot be reliably remembered by humans. Another way to express this is that it can be assumed that a computer is able to search through all possible passwords in a short time.
Cryptographic keys are often stored in secure memory in computers or us- ing special devices such as tamper-resistant cryptographic servers or in smart cards. However, there are situations where this is inconvenient or expensive. Not all devices are tamper resistant, and the memory required for public keys can be scarce. Therefore it is desirable to be able to set up secure communi- cations relying only on a short secret that can be remembered by humans.
Copyright By PowCoder代写 加微信 powcoder
This chapter examines a number of key establishment protocols that have been designed to be secure in the situation that the principals share only a password of small entropy. At first thought it might seem impossible to achieve key establishment using only a short secret in such a way that brute force searching to find the secret is not possible. This intuition may account for why it was not until 1989 that the first password-based protocols appeared in the literature. These first protocols, due to Lomas et al. [210]’ used the additional assumption that the client (in a client-server application) has knowledge of the server’s public key, in addition to sharing the password with the server. Later Bellovin and Merritt [38] introduced a class of protocols that does not require this assumption.
C. Boyd et al., Protocols for Authentication and Key Establishment © Springer-Verlag Berlin Heidelberg 2003
248 7 Password-Based Protocols
The idea of Bellovin and Merritt’s Encrypted Key Exchange (EKE) pro- tocols is that the protocol initiator will choose an ephemeral public key and use the shared password to encrypt this key. The responder can decrypt the public key and use it to send the session key securely back to the initiator. On the assumption (not always reasonable) that public keys are random strings, an adversary who tries a brute force search of passwords will not be able to distinguish which ephemeral public key was used; furthermore even when the correct public key has been found it cannot be used to discover the session key since it is not possible to obtain the private key from the public key. It is interesting to compare password-based protocols with protocols providing forward secrecy. Both seem to be possible only through use of ephemeral pub- lic keys! and, for both, a typical approach is to use long-term keys (which may be passwords) only for authentication of the message exchanges. Many password-based protocols do provide forward secrecy.
We may summarise the special properties and requirements for password- based key establishment protocols as follows. Additional properties, such as forward secrecy, are often seen as desirable.
• Users only possess a secret of small entropy. Specifically, it is possible for the adversary to search through all possible secrets in a reasonable time.
• Off-line dictionary attacks should not be feasible. This means that a passive eavesdropper who records the transcript of one or more sessions cannot eliminate a significant number of possible passwords.
• On-line dictionary attacks should not be feasible. This means that an active adversary cannot abuse the protocol so as to eliminate a significant number of possible passwords. An active adversary can always eliminate at least one password per protocol run by attempting to masquerade using that password. Ideally this should be all that the adversary can gain.
There have been many variants of Bellovin and Merritt’s EKE protocol, as well as many alternative protocols. Recently these have included some with proven security properties. The original EKE protocol does not specify the encryption algorithm to be used or how to transform the password to a rel- evant key. Some later protocols have used specific algorithms which typically require a means to map the shared password to an element of the group in which a Diffie-Hellman exchange takes place. Most protocols have variants in which the server stores only an image of the client password rather than the password itself. This means that compromise of the server does not automat- ically compromise the password; however, it will allow a brute force searching attack so this is not necessarily a significant advantage. Some authors have explored further the situation in which the client has access to a public key of the server and there are now protocols with provable security in this situation too.
1 Halevi and Krawczyk [140] provide formal arguments in support of this view.
7.1 Introduction 249
The majority of the proposed protocols use Diffie-Hellman-based key agreement with the shared password used for authentication purposes. We therefore require notation similar to that used in Chap. 5. The notation used in this chapter is shown in Table 7.1. Many of the protocols examined in this chapter are client-server protocols for which the actions of the client are dif- ferent from those of the server. Specifically, the client always possesses the plain password 7r while the server sometimes stores only an image of 7r under some one-way function. In order to avoid confusion we always assume that principal A is the client and principal B is the server.
Table 7.1. Notation for password-based protocols
A key of short length, such as a password, owned by A.
A large prime (usually at least 1024 bits).
A prime with qlp – 1.
A subgroup of Z;. G is often a subgroup of order q, but sometimes is equal to Z;.
A generator of G.
Random integers, typically of the same size as the order of G, chosen
by A and B respectively.
tA, tB grA and grB respectively. All computations take place in Zp,
XA, XB YA, YB
KAB SAB Hi(.}
The private long-term keys of A and B respectively.
The public keys of A and B, gXA and gXB respectively. These public keys will have to be certified in some standard way which we do not consider here.
The shared secret calculated by the principals. The derived session key.
The static Diffie-Hellman key of A and B.
One-way hash functions. Functions Hl, H2 , ••• are often assumed to be independent random functions. Certain protocols may require specific properties and may specify particular functions.
In the next section we examine in some detail the version of EKE based on Diffie-Hellman key exchange and later protocols derived from it. Section 7.3 is concerned with EKE variants in which the server stores only an image of the password; these are often called augmented password-based protocols. Then in Sect. 7.4 we look at protocols in which a server shares passwords with two users and establishes a key between them. Most protocols in this chapter are based on Diffie-Hellman, but in Sect. 7.5 some protocols based on RSA are described. Section 7.6 is concerned with protocols that make use of a server public key and we also look at some protocols that do not fit into
250 7 Password-Based Protocols
any of the above sections. In the final section we make a comparison of the properties achieved and resources used in a selection of the protocols.
7.2 Encrypted Key Exchange Using Diffie- this section we examine the Encrypted Key Exchange (EKE) protocol of Bellovin and Merritt [38] as applied to Diffie-Hellman key exchange. Although the original protocol has potential weaknesses and lacks a proof of security, it is instructive to understand what may go wrong with such protocols: com- pletely different attacks are possible from those applicable to protocols with strong keys. We later examine the many variants and extensions that have subsequently been developed from the original idea. Steiner et al. [306] give a specification of how to integrate EKE into the TLS protocol including details of how to use the symmetric encryption algorithm.
7.2.1 Bellovin-Merritt’s Original EKE
The general idea of EKE is to transmit ephemeral public keys encrypted using the password as a shared key. Only parties that know the password should be able to complete the protocol. This idea can be applied to ephemeral keys from different public key schemes. Here we consider only Diffie-Hellman key exchange in which both principals choose an ephemeral public key; the password is used to encrypt the ephemeral keys as shown in Protocol 7.1.
Shared information: Shared password 7r. Security parameter L. AB
nA ER {l,…,2L}
TB ER Zp ZAB =t~B
nB ER {l,…,2L}
Protocol 7.1: Diffie-Hellman-based EKE protocol
7.2 Encrypted Key Exchange Using Diffie-Hellman 251
As in basic Diffie-Hellman key agreement, the shared secret is ZAB = gTATB although the key derivation function to obtain the session key KAB from ZAB is not specified. Protocol 7.1 requires two exponentiations by each party, which is the same as ordinary Diffie-Hellman. We will see below that there are versions with fewer message passes.
Symmetric Encryption Algorithm
The choice of symmetric encryption algorithm using 7rwas left flexible by Bellovin and Merritt. They suggested that many choices are acceptable, even ones that are ‘quite weak’. However, it now seems clear that use of encryption functions without special properties prevents security proofs being obtained and allows attacks in certain cases.
Bellovin and Merritt introduced the notion of partition attacks against EKE. The idea is that an adversary guessing the password can attempt to decrypt {tA}11″ and {tB}11″ and examine whether the resulting plaintext is a valid Diffie-Hellman ephemeral value. If not then the guessed password is in- correct and can be discarded. Given several runs of the protocol, successive ‘partitions’ of the passwords into valid and invalid sets may be obtained. The success of partition attacks can depend on two factors: the symmetric encryp- tion used, and the parameters defining the group G in which the protocol works.
Consider an example in which the symmetric encryption algorithm is a conventional block cipher (the key can be derived from the password using a suitable hash function). If G = Z; then decryption of {tA}1I” using a candidate password can be assumed to be a random string of the appropriate block length. This string must be interpreted as an element of Z;. During encryption any padding that must be included due to the algorithm block length can be chosen randomly (as suggested by Bellovin and Merritt). Even so, there will be some bit-strings that cannot occur as plaintexts and these allow some passwords to be discarded. This is because if decryption with a candidate password results in a string whose value is greater than p then that candidate is invalid.
In order to make partition attacks harder, Bellovin and Merritt suggest to choose p to be slightly less than a power of 2. In this way very few candidate passwords will be invalid. Jaspan [170] conducted an analysis which concludes that it is adequate in practice to ensure that 1 – (P/2n ) < 10-4 , where 2n is the smallest power of 2 greater than p. However, it seems preferable to choose the symmetric encryption algorithm to be matched to the group so as to completely eliminate such attacks; we will explain below how this may be done.
Omitting Symmetric Encryption
Bellovin and Merritt suggested that either of the two encryptions using 7r in Protocol 7.1 could be omitted. Subsequent authors have shown that this can
252 7 Password-Based Protocols
result in weaknesses depending on the precise format of the messages used for authentication.
First suppose that the encryption using 7r is omitted from the first message so that this message becomes: A, t change does not appear to help a passive adversary and still prevents K A B from being found without knowledge of 7r. However, Patel [262] shows how an active adversary masquerading as A may be able to exploit this change. The adversary can send the first message by choosing Te and setting tA =grc. Now if the authenticator {nB}KAB returned in the second message contains redundancy then the adversary can use it to eliminate any potential password 1T by decrypting {tB}11" with 1T to obtain tB, finding the corresponding value of the session key KAB from ZAB = (tBYc, and checking for the redundancy after decrypting {nB}KAB with KAB. Jablon [164] noted that small subgroup attacks (see Sect. 5.2.1) may also become possible in this situation; the adversary can move tA into any small subgroup and use the authenticator in the third message to identify the correct KAB in a brute force attack. Standard precautions against small subgroup attacks can prevent this.
If encryption using 7r is omitted from the second message then the ad- versary can attempt to masquerade as B. Steiner et al. [307] showed that this allows an attack if the authenticators do not contain redundancy. The adversary chooses a random X and Te, sets tB = grc, and sends tB, X as the second message, which will be accepted by A. Now the adversary can de- crypt {tA}1I" with a candidate password 1T to obtain tA and the corresponding session key KAB = (tAYc. The adversary can then decrypt message 3 using KAB and check whether the second field equals the decryption of X using KAB, in order to confirm whether 1T is the correct password. Patel [262] also noted an attack here when there is limited redundancy in the authenticator, but this time it is necessary for the adversary to wait to see if a random au- thenticator is accepted by A: the adversary sends tB, X as the second message for a random value X. If this message is accepted then the adversary knows that the redundancy is present, but if it is not then all passwords that result in the desired redundancy can be eliminated.
It may seem reasonable to conclude that it is safest not to omit either of the symmetric encryptions using 7r. However, a better solution is to be more careful in the use of authenticators. We now examine variants in which this is done; not only is the result a protocol with fewer rounds, but also a proof of security becomes feasible.
7.2.2 The P AK Protocol
Bellare et al. [29] have provided proofs that the exchange of the password- encrypted Diffie-Hellman messages at the core of EKE is a secure protocol using the Bellare-Rogaway mod~l discussed in Chap. 2. Although they specify the key derivation function to find the session key the symmetric encryption algorithm used in the protocol is not concretely defined; it is assumed to be
7.2 Encrypted Key Exchange Using Diffie-Hellman 253
an 'ideal cipher' that can be regarded as a random function (analogous to the functions used in the random oracle model). Furthermore, the decryption function must take strings of a fixed size and map them to elements of G. This may leave the implementer in some difficulty in choosing an appropriate concrete algorithm. Later MacKenzie [218) proposed concrete ways to achieve a suitable algorithm along with complete proofs.
In parallel work, Boyko et al. [65) specified a slightly different version of Diffie-HeIlman-based EKE called PAK (Password Authenticated Key ex- change). They provided a proof of security in Shoup's simulation model, and later MacKenzie provided proofs in the Bellare-Rogaway model too. The en- cryption function used is simply multiplication in the Diffie-Hellman group.
PAK uses a prime p of the form p = rq +1, with rand q relatively prime. The Diffie-Hellman key exchange takes place in the subgroup G of order q. The original PAK protocol uses four hash functions. It is important that these functions are different and the formal proof assumes they are independent random functions. In practice we may define the different hash functions by prepending a different fixed string to the input and then using a standard hash function. For example, we may define Hi(x) = H(ASCII(i),x), where H is SHA-1 [245) and ASCII(i) is the ASCII representation of i. Protocol 7.2 shows the basic version of PAK. Output from Hl is treated as an element of Z; and is used to map 7r to an element of G which is an important part of defining the symmetric encryption algorithm.
A key feature of Protocol 7.2 is that the element P in the group G is
derived from the password 7r using the formula P = H l (A, B, 7r
applications the computing device of A will not have the value 7r available beforehand and so this calculation is part of the computational requirements for A. (In contrast we may assume that B is a server which can store the derived value of P.) Since typical lengths of q and r may be 160 bits and 864 bits respectively, this calculation is more expensive than the subsequent Diffie-Hellman exchange. The computational requirements may be optimised for different applications by choosing a larger size for q so that the size of r becomes smaller.
The PAK protocol was proven by Boyko et al. [65) to be secure in Shoup's simulation model assuming the hash functions act as random oracles. Origi- nally this result relied on the Decision Diffie-Hellman assumption but later MacKenzie [218) showed that the ordinary (computational) Diffie-Hellman assumption is sufficient. We may regard the PAK protocol as a variant of the original Diffie-HeIlman-based EKE protocol with the following instantiations and modifications:
• the key derivation function is specified;
• symmetric encryption is defined as multiplication in G by the image P of
• symmetric encryption of the ephemeral Diffie-Hellman key in the second
message is omitted;
y. In typical
254 7 Password-Based Protocols
Shared information: Generator 9 of G where p - 1 qr. Hash functions H 1 ,H2,H3,H4.
Information held by A: Password 1r.
Information held by B: Derived password image P = H1 (A,B,1rY.
P =H1 (A,B,1r)' rA ER Zq
m modp -I 0
tA =m/P rB ER Zq tB =gTB ZAB = t~B
Protocol 7.2: PAK protocol
• a simplified authentication mechanism is used which allows a more efficient
It is interesting to consider how these changes ensure that the potential weaknesses in Diffie- KE are avoided. The choice of symmetric en- cryption is very simple and matched to the group G. (Although a modular multiplication may be computationally more expensive than encryption with a block cipher, in practice the additional effort over the required exponenti- ations is very small.) In the partition attack described above the adversary attempts decryption with candidate passwords 'Tr'. With this natural choice of encryption, every 'Tr' maps to an image P' E G and attempted decryption of tAP results in tAP/P' which will always lie in G. Therefore the partition attack cannot even discount a single candidate 'Tr'. If the adversary tries to ex- ploit the omission of the symmetric encryption with 'Tr in the second message by sending tB, X for a random X then with overwhelming probability A will reject the message. Instead the adversary can calculate a correct value k for any candidate password and this would allow checking of that one password.
Boyko et al. [65] also specify a variant protocol of PAK without explicit authentication. The result is shown as Protocol 7.3 and is known as PPK (Password Protected Key exchange). Apart from omitting the authenticators
k == H 2 ( A , B , m , t B , Z A B , P )
k' = H3(A, B, m, tB, ZAB, P)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com