CN101938491A - A Three-Party Key Exchange Method Based on Password - Google Patents

Abstract

The three parts cipher key that the invention discloses a kind of based on password exchanges method, comprising: S verifies the VAS that A is sent: if h (gax, A, B, S) with

Latter half it is equal, and S verifying B send VBS: if h (gby, A, B, S) with

Latter half it is equal, gx in h (gax, A, B, S) and h (gby, A, B, S), gy are respectively adopted

With

First half, then VSA is sent to A, VSB and is sent to B; A verifies the VSA that S is sent: if

Comprising gx, and B verifies the VSA that S is sent: if

Comprising gy, then A, B is calculated separately establishes the unified session key gxy of both sides jointly. This key exchange method can not only effectively resist various attacks, provide perfect forward security, and all improve to some extent on exchange wheel number and call duration time.

Description

A Three-Party Key Exchange Method Based on Password

technical field

The invention relates to the field of communication security, in particular to a password-based tripartite key exchange protocol.

Background technique

When the communication parties need to communicate securely on the open channel, in order to ensure the confidentiality of the communication content, they need to negotiate a session key before the communication to encrypt the data to be transmitted. Because the password-based key exchange protocol only requires the communication parties to share a simple and easy-to-remember password, this protocol has been more widely used. However, due to the low entropy of passwords, this protocol is more prone to dictionary attacks. Dictionary attacks can be divided into the following three categories:

1. Online detectable dictionary attack: The attacker tries to guess the customer's password and communicates online to verify the correctness of the password he guessed. Once the attacker fails to guess the password, it is easy to be found.

2. Online undetectable dictionary attack: The attacker tries to guess the customer's password and communicates online to verify the correctness of the password he guessed, and the attacker will not be found if the password guess fails. Therefore, in this case, the attacker can implement multiple guessing attacks.

3. Offline dictionary attack: The attacker guesses the customer's password and verifies the correctness of the guessed password offline.

A secure password-based key exchange protocol should be able to effectively resist online undetectable dictionary attacks and offline dictionary attacks.

In 1992, the inventors Bellovin and Merritt first proposed a password-based two-party key exchange (2PAKE) protocol. Through the password shared by the communication parties, the protocol successfully realized mutual authentication and key exchange between the communication parties. Since then, a large number of 2PAKEs have been proposed.

However, because the key exchange protocol between the two parties is suitable for the "client-server" system, it is not suitable for a system like P2P where a large number of clients need to communicate with each other. In 1995, the inventor Steiner proposed a password-based three-party key exchange (3PAKE) protocol, but engineers and technicians Ding and Horster pointed out that the protocol cannot resist online undetectable dictionary attacks, and engineers and technicians Lin pointed out that the protocol is also unable to resist offline dictionary attack, and an improved protocol based on public key technology is proposed. In 2001, the inventor Lin proposed a new 3PAKE protocol that does not require public key technology, but this protocol requires two more rounds of execution than the improved protocol based on the public key he proposed earlier. In 2003, the inventor Sun proposed a new 3PAKE, but the engineer Nam quickly pointed out that the protocol was vulnerable to man-in-the-middle attacks. In 2004, the inventor Lee proposed a new 3PAKE protocol and claimed that the protocol can resist various attacks and provide perfect forward security. In 2007, the inventors Lu and Cao proposed a simple and efficient 3PAKE protocol based on the assumption of CCDH, and claimed that the protocol can resist various attacks. But then people analyzed and found that the protocol cannot resist man-in-the-middle attacks, online undetectable dictionary attacks, impersonation attacks, and offline dictionary attacks.

Contents of the invention

The problem to be solved by the present invention is: how to provide a method for establishing a three-party key exchange based on passwords. This new 3PAKE protocol can resist various existing attacks, and is different from existing protocols in the number of rounds of exchange and communication time. improved compared to

The technical problem proposed by the present invention is solved like this: provide a kind of three-party key exchange method based on password, it is characterized in that, comprises the following steps:

的后半部分相等，且S验证B发送的V_BS：若h(g^bx，A，B，S)与

的后半部分相等，h(g^ax，A，B，S)和h(g^by，A，B，S)中g^x，g^y分别采用

和

的前半部分，则将V_SA发送给A、V_SB发送给B；S verifies the V _AS sent by A: if h(g ^ax , A, B, S) and

The second half of is equal, and S verifies the V _BS sent by B: if h(g ^bx , A, B, S) and

The second half of is equal, g x and ^{g y} in h(g ^ax , A, B, S) and h(g ^by , A, B, S) respectively adopt

and

In the first half of , send V _SA to A and V _SB to B;

包含g^x，且B验证S发送的V_SA：若包含g^y，则A，B分别计算共同建立双方统一的会话钥匙g^xy＝(g^y)^x＝(g^x)^y；A verifies the V _SA sent by S: if

contains g ^x , and B verifies the V _SA sent by S: if Including g ^y , then A and B respectively calculate and jointly establish a unified session key g ^xy =(g ^y ) ^x =(g ^x ) ^y ;

函数EK(M)是表示用密钥K对M进行对称加密，pw_A是A与S共享的口令，pw_B是B与S共享的口令，Z_p是模p剩余类集合，g是Z_p的生成元，p是一个大素数，函数h()是一个{0，1}^*→Z_p-1的哈希函数；函数D_K(M)是表示用密钥K对M进行对称解密；算式n∈_RZ_p ^*是表示n从模p乘法群中随机选取，a，b∈_RZ_p ^*是S产生的随机数，x∈_RZ_p ^*是A产生的随机数，y∈_RZ_p ^*是B产生的随机数。Among them: A and B are the two parties in the conversation, and S is the third-party server;

The function EK(M) means to encrypt M symmetrically with the key K, pw _A is the password shared by A and S, pw _B is the password shared by B and S, Z _p is the remainder class set modulo p, and g is Z _p The generator of , p is a large prime number, the function h() is a hash function of {0, 1} ^* → Z _p-1 ; the function D _K (M) means to use the key K to decrypt M symmetrically; The formula n∈ _R Z _p ^* means that n is randomly selected from the multiplication group of modulo p, a, b∈ _R Z _p ^* is a random number generated by S, x∈ _R Z _p ^* is a random number generated by A, y∈ _R Z _p ^* is a random number generated by B.

According to the tripartite key exchange method provided by the present invention, it is characterized in that it also includes:

发送给A，并产生随机数b计算

发送给B；S generates a random number a calculation

Send to A, and generate a random number b to calculate

send to B;

A receives S _A , generates a random number x and then calculates and sends V _AS , B receives S _B , generates a random number y and then calculates and sends V _BS .

According to the three-party key exchange establishment method provided by the present invention, it is characterized in that S acquires A and B in this way, including the following four ways:

(1) A sends A and B to S;

(2) B sends A and B to S;

(3) A sends B to S, and S identifies sender A;

(4) B sends A to S, and S identifies the sender B.

The beneficial effects of the present invention are: based on Sun's protocol and Lee's protocol, a new 3PAKE protocol is proposed. improved in time. Compared with the existing technology, it mainly has the following characteristics: 1. It realizes the mutual authentication between each client A, B and the third-party server S; 2. The protocol can resist various existing attacks; Compared with existing protocols, the communication time is improved.

Description of drawings

Fig. 1 is a schematic flow chart of the password-based tripartite key exchange method of the present invention.

Detailed ways

Below, in conjunction with accompanying drawing, the method of the present invention is described in detail, wherein adopt symbol:

A, B represent the two clients who need to negotiate keys in the agreement

S stands for trusted third-party server

pw _A indicates the password shared by A and S

pw _B indicates the password shared by B and S

Z _p represents the set of residual classes modulo p

a ∈ _R Z _p ^* means that a is randomly selected from the multiplicative group modulo p

(G, g, p) represents the finite cyclic group G, g is the generator of Z _p , and p is a large prime number

h() is a hash function of {0, 1} ^* → Z _p-1

E _K (M), D _K (M) respectively represent the symmetric encryption and symmetric decryption of M with the key K

For brevity, "mod p" is omitted from the protocol description

The password-based three-party key exchange method of the present invention is based on the 3PAKE protocol of Sun and Lee, and combined with symmetric encryption, a new three-party key exchange protocol is proposed. Before the protocol starts, A and B share passwords pw _A and pw _B with S respectively. The specific steps of the new protocol are shown in Figure 1 and include the following steps:

101) A sends A, B to S, indicating that A wants to negotiate a session key with B through S.

然后将S_A，S_B分别发送给A，B。102) After S receives A and B, S first generates random numbers a, b∈ _R Z _p ^* and calculates

Then S _A and S _B are sent to A and B respectively.

然后A，B分别产生随机数x，y∈_RZ_p ^*，并计算

最后分别将V_AS，V_BS发送103) After receiving _SA and S _B respectively, A and B use their own passwords pw _A and pw _B to decrypt _SA and S _B to obtain

Then A and B generate random numbers x, y∈ _R Z _p ^* respectively, and calculate

Finally, send V _AS and V _BS respectively

to S.

得到解密后的前半部分g^x，g^y，然后利用自己保存的a，b计算h(g^ax，A，B，S)，h(g^by，A，B，S)，并验证是否与解密后的后半部分相等，若相等，S分别计算

然后分别将V_SA，V_SB发送给A，B。104) After receiving the V _AS and V _BS sent by A and B, S calculates them respectively

Get the first half of the decrypted g ^x , g ^y , then use the saved a, b to calculate h(g ^ax , A, B, S), h(g ^by , A, B, S), and verify whether it is consistent with the decryption The second half of the last part is equal, if they are equal, S is calculated separately

Then send V _SA and V _SB to A and B respectively.

A验证解密后的消息中是否含有g^x，B验证解密后的消息中是否含有g^y。若验证都含有，则A，B计算K_AB＝(g^y)^x，K_AB＝(g^x)^y。A，B双方的会话密钥K＝K_AB＝K_BA＝g^xy。105) After receiving V _SA and V _SB , A and B use the saved g ^ax and g ^by to decrypt them respectively, and calculate

A verifies whether the decrypted message contains g ^x , and B verifies whether the decrypted message contains g ^y . If the verification contains both, then A and B calculate K _AB =(g ^y ) ^x , K _AB =(g ^x ) ^y . A and B's session key K=K _AB =K _BA =g ^xy .

Further, safety and efficiency analysis are carried out to the inventive method:

(1) Safety analysis

Assume that the attacker has eavesdropping, replay, impersonation, forgery and other means to attack the protocol. We analyze the security of the new protocol from several attacks that the existing protocols often suffer.

(1) Assuming that the attacker intercepts A, B, S _A , S _B , V _AS , V _BS , V _SA , V _SB , all messages except the identity are encrypted symmetrically, and the attacker cannot any other useful information.

(2) Assume that the attacker tries to impersonate A and B, but in the second step of the protocol execution, S encrypts g ^a with pw _A and pw _B respectively, and g ^b generates S _A and S _B , the attacker does not know the password In this case, S _A and S _B cannot be decrypted, so g ^a and g ^b cannot be obtained, so the attacker cannot generate fake messages V _AS and V _BS .

(3) Suppose the attacker tries to impersonate S, but in the third step of the protocol execution, A and B use pw _A and pw _B to encrypt g ^x respectively, and g ^y generates S _AS and S _BS , the attacker does not know the password In the case of V _AS , V _BS cannot be decrypted, so g ^x , g ^y cannot be obtained, so the attacker cannot generate fake messages V _SA , V _SB .

(4) Assume that the attacker tries to conduct an online undetectable guessing attack. The attacker can choose possible passwords pw′ _A , pw′ _B , but A and B can discover this password guessing attack when verifying V _SA , V _SB , S This kind of password guessing attack can be found when verifying V _AS and V _BS .

(5) Assuming that the attacker has obtained the password pw _A or pw _B , the attacker cannot calculate the previous session key K, because the attacker must solve a discrete logarithm problem if he wants to obtain the previous session key, and this problem It is now recognized as a difficult problem. So the protocol has perfect forward security.

(2) Efficiency analysis

The efficiency is compared with the Sun protocol and the Lee protocol, and the comparison results are shown in Table 1. The comparison includes the number of random numbers, the number of exponential operations, the number of asymmetric encryption/decryption, the number of exchange rounds and the execution time. Because the calculation of symmetric encryption and hash function is very small, compared with asymmetric encryption/decryption and exponential operation, it is negligible, so we will not consider it here. Usually we think that the amount of computation of asymmetric encryption/decryption and exponent operation is the same. By comparing them, it can be seen that the amount of computation of the new protocol is equivalent to that of the Lee protocol and the Sun protocol, but the number of random numbers is less than that of the Sun protocol. In the new protocol, S _A , S _B , g ^x , g ^y can be calculated in advance (the other two protocols also do the same), so only 3 times of exponential operations are needed when implementing the new protocol (indicated by 3E, and E represents not Symmetric encryption/decryption times and exponential operation times) can be completed, which is better than Sun protocol and Lee protocol. And the new protocol only needs to execute 4 information exchanges, which is better than the Sun protocol and the Lee protocol in terms of the number of exchange rounds.

Table 1

Finally, the protocol of the present invention can be realized by using software and hardware, and the random number selected by each user during the protocol execution process must be safely deleted after the protocol ends to avoid the possibility of leakage.

Claims (4)

1. A three-party key exchange method based on password, is characterized in that, comprises the following steps: S verifies the V _AS sent by A: if h(g ^ax , A, B, S) and

The second half of is equal, and S verifies the V _BS sent by B: if h(g ^bx , A, B, S) and

The second half of is equal, and gx in h(g ^ax , A, B, S) adopts

In the first half, g ^y in h(g ^by , A, B, S) adopts

In the first half of , send V _SA to A and V _SB to B; A verifies the VSA sent by S: if

contains g ^x , and B verifies the V _SA sent by S: if

Including g ^y , then A and B respectively calculate and jointly establish a unified session key g ^xy =(g ^y ) ^x =(g ^x ) ^y ; Among them: A and B are the two parties in the conversation, and S is the third-party server;

The function E _K (M) means to use the key K to encrypt M symmetrically, pw _A is the password shared by A and S, pw _B is the password shared by B and S, Z _p is the set of residual classes modulo p, and g is Z The generator of _p , p is a large prime number, the function h() is a hash function of {0, 1} ^* → Z _p-1 ; the function D _K (M) means that the key K is used to decrypt M symmetrically ;The formula n∈ _R Z _p ^* means that n is randomly selected from the modulo p multiplication group, a, b∈ _R Z _p ^* is a random number generated by S, x∈ _R Z _p ^* is a random number generated by A, y∈ _R Z _p ^* is a random number generated by B. 2. The key exchange method according to claim 1, further comprising: S generates a random number a calculation

Send to A, and generate a random number b to calculate

send to B; A receives S _A , generates a random number x and then calculates and sends V _AS , B receives S _B , generates a random number y and then calculates and sends V _BS . 3. The key exchange method according to claim 1 or 2, further comprising A sending A and B to S, or B sending A and B to S. 4. The key exchange method according to claim 1 or 2, further comprising A sending B to S, or B sending A to S.

Images