CN110166225A - A kind of password has timeliness and authenticates the unrestricted dynamic password authentication method of number - Google Patents

Abstract

The invention relates to a dynamic password authentication method with a time-sensitive password and an unlimited number of authentication times, which belongs to the field of information security. The invention uses the idea of a relay race for elementary school students to generate a short hash chain between two logins of a user, and the user's Each successful login will send the next verification value to the server. Through such a relay process, the number of dynamic password authentications is unlimited; at the same time, each dynamic password has a time limit, no matter whether the user uses the dynamic password or not, the dynamic password is only valid Valid for a very short period of time, which increases the difficulty for attackers to crack passwords; in addition, using N different hash functions to generate dynamic passwords avoids birthday attacks and further improves the security of user accounts. This solution is suitable for users who have high requirements for password security, and is especially suitable for situations where users do not need to re-register and have high requirements for dynamic password security.

Description

A dynamic password authentication method with time-sensitive password and unlimited authentication times

technical field

The invention belongs to the field of information security, and in particular relates to a dynamic password authentication method with time-sensitive password and unlimited authentication times.

Background technique

With the diversification of information and the rapid development of digitalization, information security technology is increasingly showing its important position, and the application level of information security technology directly affects the development of information highway construction. In the traditional identity authentication, the most commonly used method is the static password authentication method, but due to the defects of the static password itself, this method cannot provide sufficient access security. Dynamic passwords not only have the characteristics of low cost and simple deployment of static passwords, but also improve the security of information authentication. It is a one-time-change identity authentication method proposed to address the security weaknesses of traditional static passwords. The basic idea is: in each login process of the user, adding uncertain factors to generate dynamically changing information, thereby improving the security of the login process. Dynamic password authentication is the frontier and hot spot in the field of identity authentication, and it is also a widely used authentication method.

American scientist Lamport first proposed the idea of using a hash function to generate a dynamic password in 1981. Haller proposed the S/KEY scheme on the basis of the Lamport scheme. Although this scheme is widely used in various password mechanisms, it still has There are many areas to be improved, such as: the number of dynamic password authentications is limited by the length of the hash chain, so re-registration is required after the password is used up (re-registration means that the number of dynamic passwords is limited by the length of the hash chain, due to the The chain length is fixed, so the number of dynamic passwords generated is also limited. When these dynamic passwords are used up, the user needs to regenerate a new chain and submit the verification value to the server); it takes a certain amount of time or The storage space is used to calculate or store all OTP values; it cannot resist various attacks such as small number attacks and replay attacks. Later, many researchers optimized the performance of their scheme. In 2017, Kogan proposed "Second-Factor Authentication of Secure Hash Chains" [KoganD, Manohar N, Boneh D.T/Key: Second-Factor Authentication From Secure HashChains[J]. 2017.] and in 2018, Park proposed "Dynamic password based on hash chain without shared secret and re-registration" [Park, Chang-Seop. One-time password based on hash chain without shared secret and re-registration[J]. Computers&Security, 2018: S0167404818301391.] scheme had an extraordinary impact.

Park's contribution is mainly to build a new type of short chain and connect the short chain to the long chain, which realizes the unlimited number of dynamic password authentications and successfully avoids the problem of users needing to re-register; at the same time, it improves the security of the scheme. It can Resists various attacks such as man-in-the-middle attacks and session hijacking attacks. Even if the attacker modifies the OTP value sent by the current user, he cannot forge the next OTP value accepted by the server.

Although Park avoids the problem of re-registration and can resist various attacks, there are still shortcomings in this scheme: he ignores the problem of password timeliness, and the dynamic password is valid until the user's latest successful login and the next successful login. Yes, that is, the dynamic password is valid for an uncertain time. If the time interval between the user's two logins is long, it will give the attacker an opportunity, and if the counter value of each authentication attempt is sent by the server to the client , the vulnerability is amplified, such as the S/KEY scheme.

Kogan's scheme realizes that the dynamic password is valid for a fixed and extremely short time. Before that, most researchers ignored the problem of the valid time of the password; he used N different hash functions to generate the dynamic password, avoiding The "birthday attack" proposed by Hu Jakobsson and Perrig (the so-called birthday attack means that a hash chain with a length of N is generated by iterating the same hash function N times, we obtain the i-th password as x _i , denote As x ₀ , then perform hash iteration on x ₀ , as long as it is the same as any hash value in the hash chain, we say that a collision has occurred, as long as a collision occurs, then a preimage of it has been successfully found , the so-called preimage refers to: if y=h(x), then x is called the preimage of y, that is, the message input into the one-way hash function is also called the preimage, and we call such an attack a birthday attack) The problem.

Of course, the shortcomings of Kogan's scheme are also very obvious: it is still limited by the fixed chain length in the Lamport scheme and the need to re-register.

Contents of the invention

The invention combines the ideas of the Kogan scheme and the Park scheme to achieve the best performance of the two schemes: no re-registration is required and the dynamic password has timeliness, and a dynamic password authentication method with timeliness password and unlimited authentication times is proposed. The present invention can meet without re-registration (re-registration refers to that the number of dynamic passwords is limited by the length of the hash chain, because the length of the hash chain is fixed, so the number of dynamic passwords produced is also limited, when these dynamic When the password is used up, the user needs to regenerate a new chain and submit the verification value to the server), the password is time-sensitive, no matter whether the user logs in or not, the password is valid in a very short time, and it is almost impossible for the attacker Crack the dynamic password in this extremely short time, thereby protecting the security of users; at the same time, use N different hash functions to generate hash chains, avoiding birthday attacks (the so-called birthday attack refers to a hash with a length of N). The Greek chain is generated by iterating the same hash function N times. We obtain the i-th password as x _i , record it as x ₀ , and then perform hash iterations on x ₀ , as long as it is hashed with any one in the hash chain If the Greek values are the same, we say that a collision has occurred. As long as a collision occurs, a preimage of it has been successfully found (if y=h(x), then x is called the preimage of y, that is, the input unidirectional scattering The message of the column function is also called the preimage), and we call such an attack a birthday attack).

The purpose of the present invention is to combine the ideas in the two schemes of Kogan and Park to construct a new type of hash chain to achieve the best performance of the two schemes, realize that the user does not need to re-register and the dynamic password has timeliness, and can resist birthday attacks, Small number attack, replay attack and other attacks. The present invention adds a clock at both ends of the user and the server, and designs a dynamic password scheme related to time. Regardless of whether the user logs in, the password is valid within a short period of time; the number of authentications of the dynamic password is no longer subject to hash The chain length is fixed; at the same time, N different hash functions are used to generate dynamic passwords, which avoids birthday attacks and improves the security of user accounts.

The purpose of the present invention is achieved through the following technical solutions:

A dynamic password authentication method with a time-sensitive password and an unlimited number of authentications, characterized in that the method comprises the following steps:

1. Registration stage:

(1) User: The user submits registration information such as: user name, static password K, mobile phone number, email address, etc.;

(2) User: Generate N different hash functions according to the static password K submitted by the user, the random salt id, the chain length N, and the current node j: h _j (x)=H(<Nj> _c ||id|| k)| _n ;

(3) User: The user randomly generates a seed x ₀ and uses N different hash functions to generate a short chain of length N:

x ₁ =h ₁ (x ₀ ), x ₂ =h ₂ (h ₁ (x ₀ )), x ₃ =h ₃ (h ₂ (h ₁ (x ₀ )))...y ₀ = x _N = h _N (h _N-1 (...h ₁ (x ₀ )));

(4) User: Send the user name, initial verification value y ₀ and N different hash functions to the server (the server obtains the initial verification value y ₀ and records it as y _prev , and stores N different hash functions at the same time ).

2. Login stage (the user logs in for the first time):

(5) User: Calculate the password for the i-th user login as: t=t _now -t _prev (t _now represents the current time, t _prev represents the accumulated value of the previous successful login times), p _t = h _t (h _t-1 (...( _xi ))).

(6) User: Send ( _pt , y _i+1 ) (y _i+1 is the next verification value, generated by the user between two logins) to the server.

(7) Server: Calculation: t=t _now -t _prev , y _i =h _N (h _N-1 (...h _N-t+1 (p _t ))), if y _i =y _prev then the server If the verification is successful, go to (8); otherwise, go to (10) if the verification fails.

(8) Server: Judging that t _now > N, if t _now > N, we think that the cumulative value of t _now is too large, in order to improve operating efficiency, we reassign the time t _now , t _now = t _prev = t; otherwise, We only update t _prev : t _prev =t _prev +t.

(9) Server: update the verification value y _prev : y _prev =y _i+1 .

(10) User: judge whether the login is successful, if the login fails, return failure information, otherwise update the value of t: judge t _now > N, if t _now > N, we think the cumulative value of t _now is too large, in order to improve the operation Efficiency, we reassign the time t _now , t _now =t _prev =t; otherwise, we update t _prev : t _prev =t _prev +t, and generate the next hash chain at the same time.

The static password K submitted by the user in the step (1) is used to generate N different hash functions.

In the step (2), K refers to the static password submitted by the user, id is the salt generated at random, N refers to the chain length of the generated hash chain, j refers to currently generating the jth hash function, and c is Refers to generating a c-bit binary number, m||n refers to the concatenation of m and n.

In the step (3), x ₀ is the seed of the initial hash chain randomly selected by the user, y ₀ is the value of x ₀ after N times of hash operations, x ₁ =h ₁ (x ₀ ), x ₂ =h ₂ (h ₁ (x ₀ )), x ₃ =h ₃ (h ₂ (h ₁ (x ₀ )))...y ₀ =x _N =h _N (h _N-1 (...h ₁ (x ₀ ))).

In the step (4), the user sends the user name and the initial verification value y to the server, and the server obtains the first verification value, and stores N different hash functions _at the same time, and the verification of N different hash functions in the later stage used in calculations.

In the step (5), i means that the user has successfully logged in (i-1) times, and x _i is the user's random time interval between the (i-2) and (i-1) logins. The seed of the selected i-th hash short chain, t _now represents the current time, t _prev represents the cumulative value of the previous successful login times, and the dynamic password for user login at time t _now is p _t .

In the step (6), y _i+1 is the chain tail of the (i+1)th hash short chain generated by the user during the time interval between the (i-1)th and i-th two logins, It is also the verification value of the next user login, and the user sends the dynamic password p _t logged in at t _now and the verification value y _i+1 of the next login to the server.

In the step (7), the server calculates y _i , if y _i =y _prev , the authentication is successful, and the authentication is successful, then go to (8); otherwise, the authentication fails, and then go to (10).

The judgment of t _now in the step (8) is to detect whether the value of t _now is too large, because the value of t _now is dynamically accumulated in a very short time, if the value of t _now is too large, it will affect our operating efficiency , when t _now > N, we think that the value of t is too large, and we need to do a process similar to clearing t _now . Since the value of t _now is related to our current dynamic password acquisition, we make the following adjustments: t _now =t _prev =t; otherwise, we update the time accumulation value t _prev : t _prev =t _prev +t.

In the step (9), the server verification value y _prev is updated: y _prev =y _i+1 .

In the step (10), the user first judges the return information of the server, if the login fails, then log in again, otherwise it is necessary to perform the operation similar to the t _now in the step (8) to t _now , and generate the (i+ 2) Hash chains.

The specific setting environment for the problem to be solved in the purpose of the present invention can be: the user wishes to use the dynamic password to improve the security of the account, but is tired of the cumbersome process that several dynamic passwords that exist at present need to re-register every once in a while. To meet the user's requirements for improving account security, the dynamic password can be changed in a very short time regardless of whether the user uses it or not, and at the same time avoids the user's re-registration operation, which is simple and easy to use.

The advantages of the present invention are:

The outstanding substantive features and remarkable progress of the present invention are mainly reflected in the following points:

1. The user does not need to re-register. Since the chain length of the hash chain is fixed, the number of dynamic passwords generated is also limited. When these dynamic passwords are used up, the user needs to regenerate a new chain and submit the verification value to Server, we call this process re-registration. We adopt the idea of elementary school students' relay race to generate short hash chains between user logins. For example, to generate a short chain that users can use for half a year, it only takes A few seconds, in such a short period of time, it is impossible for the user to make two login attempts, and each successful login of the user will send the next verification value to the server. Through such a relay process, we have successfully implemented The number of dynamic password authentications is unlimited;

2. Each dynamic password has a time limit, no matter whether the user uses the dynamic password or not, the dynamic password is only valid for a very short period of time, which increases the difficulty for attackers to crack the password and further improves the security of the user account;

3. Can resist birthday attacks, and proposes that if the same hash function is used at each step of the hash chain, it is actually k times easier to reverse the kth iteration than to reverse a single instance of the hash function, also Jakobsson and Perrig point out that N times As long as the results of any two hash iteration calculations are the same in the iteration, then we have found a preimage. The so-called preimage means: if y=h(x), then x is called the preimage of y, that is The message input to a one-way hash function is called a preimage, and this method is called a birthday attack, and we can successfully resist this attack by using N different hash functions.

4. The purpose, advantages and characteristics of the present invention will be explained by the non-limiting description of the following preferred embodiments. These embodiments are only typical examples of applying the technical solutions of the present invention, and all technical solutions formed by adopting equivalent replacements or equivalent transformations fall within the protection scope of the present invention.

Description of drawings

The present invention will be further described below in conjunction with accompanying drawing and embodiment:

Fig. 1 is the flow chart of registration stage of the present invention

Fig. 2 is the flow chart of authentication stage of the present invention

Detailed ways

The above solution will be further described below in conjunction with specific embodiments. It should be understood that these examples are used to illustrate the present invention and not to limit the scope of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

The implementation steps of a dynamic password authentication method with a time-sensitive password and an unlimited number of authentication times in this embodiment are as follows:

Registration phase:

Step 1: When the user registers, submit the registration information, such as user name, static password K, email address, mobile phone number, etc., and generate N according to the static password K submitted by the user, random salt id, chain length N, current node i, etc. Different hash functions: h _j (x)=H(<Nj> _c ||id||k)| _n , where K refers to the static password submitted by the user, id is the randomly generated salt, and N refers to the generated The chain length of the hash chain, j means that the jth hash function is currently being generated, c means generating a c-digit binary number, and m||n means the concatenation of m and n. The user selects a random number x ₀ as the seed of the hash short chain, and then uses N different hash functions to generate a hash short chain of length N, x ₁ =h ₁ (x ₀ ), x ₂ =h ₂ (h ₁ (x ₀ )), x ₃ =h ₃ (h ₂ (h ₁ (x ₀ )))...y ₀ =x _N =h _N (h _N-1 (...h ₁ (x ₀ ))), and send the user name, initial verification value y ₀ , and N different hash functions to the server. The initial verification value y ₀ is used as verification information when the user logs in next time, and N different hash functions The hash function is stored in the service and is used in every verification calculation of the server.

Step 2: The server receives the registration information sent by the user, records the initial verification value y ₀ as y _prev , and stores N different hash functions locally.

The mobile APP will generate the next short link within the time gap of the user's login. If the user has successfully logged in for i-1 times and now tries to log in for the i-th time, the mobile phone will generate the next short link between the user's i-1 and i-th login times. Generate a short chain with a length of N and record it as the i+1th short chain. There is no need to worry about the problem that the time interval between the user's two logins is too short to generate a new short hash chain. We use the user for half a year. Take the registration time required for the chain length of the hash chain as an example, assuming that the dynamic password is changed every 30 seconds, the number of OTPs required for that half year is: 5*10 ⁵ , that is, N=5*10 ⁴ , and The time required to generate such a short hash chain is about 4 seconds. Kogan also mentioned in the article "Second Factor Authentication of Secure Hash Chain" that the time required to generate a two-year hash chain is less than 15 seconds, it is almost impossible for a user to make two consecutive login attempts in such a short time of 4 seconds, so we have enough time to generate the next hash chain.

Authentication phase:

Step 3: Log in for the i-th time, the dynamic password of the user at t _now is p _t , the user will (p _t , y _i+1 ) (y _i+1 is the user's two times at the i-1 and i-th time The next hash chain generated by the login gap) is sent to the server; the server receives the information sent by the user, and calculates: t=t _now -t _pre v, y _i =h _N (h _N-1 (...h _{N -t+1} (p _t ))), then check whether y _i is equal to y _prev , if the value of yi is equal to p _rev , the server authentication is successful, and the verification information is updated to y _i+1 , and at the same time judge the time counter t _now value, if t _now > N, we think that the value of the time counter t _now is too large, which has affected our operating efficiency, the value of t _now is dynamically accumulated in a very short time, if the value of t _now is not added If the value is too large, it will definitely affect the operating efficiency, and when the value of t _now is accumulated to a certain extent, there will be a problem of value overflow. Therefore, if t _now > N, we will perform an operation similar to zeroing on t _now : t _now =t _preb =t, otherwise we consider the value of t _now acceptable, and update the time accumulative value t _prev : t _prev =t _prev +t.

Step 4: The user judges the information sent by the server. If the server authentication is successful, the user also needs to judge whether the value of t _now is too large. If the value of t _now is too large, that is, t _now > N, we do something similar to clearing Operation: t _now ＝t _prev ＝t, otherwise we think that the value of t _now is still within the acceptable range, update the cumulative value t _prev of time: t _prev ＝t _prev +t; generate the next hash chain at the same time. If the server returns login failure, log in again.

Claims (7)

1. A kind of dynamic password authentication method that password has timeliness and authentication number of times is not limited, it is characterized in that, described method comprises the following steps: Registration phase: (1) User: The user submits registration information such as: user name, static password K, mobile phone number, email address, etc.; (2) User: Generate N different hash functions according to the static password K submitted by the user, the random salt id, the chain length N, and the current node j: h _j (x)=H(<Nj> _c ||id|| k)| _n ; (3) User: The user randomly generates a seed x ₀ , and uses N different hash functions to generate a short chain of length N: x ₁ =h ₁ (x ₀ ), x ₂ =h ₂ (h ₁ (x ₀ )), x ₃ =h ₃ (h ₂ (h ₁ (x ₀ )))...y ₀ =x _N ＝h _N (h _N-1 (...h ₁ (x ₀ ) )); (4) User: Send the user name, initial verification value y ₀ and N different hash functions to the server (the server obtains the initial verification value y ₀ and records it as y _prev , and stores N different hash functions at the same time ). Login phase (the user logs in for the ith time): (5) User: Calculate the password for the i-th user login as: t=t _now -t _prev (t _now represents the current time, t _prev represents the accumulated value of the previous successful login times), p _t = h _t (h _t-1 (...( _xi ))). (6) User: Send ( _pt , y _i+1 ) (y _i+1 is the next verification value, generated by the user between two logins) to the server. (7) Server: Calculation: t=t _now -t _prev , y _i =h _N (h _N-1 (...h _N-t+1 (p _t ))), if y _i =y _prev then the server If the verification is successful, go to (8); otherwise, go to (10) if the verification fails. (8) Server: Judging that t _now > N, if t _now > N, we think that the cumulative value of t _now is too large, in order to improve operating efficiency, we reassign the time t _now , t _now = t _prev = t; otherwise, We only update t _prev : t _prev =t _prev +t. (9) Server: update the verification value y _prev : y _prev =y _i+1 . (10) User: judge whether the login is successful, if the login fails, return failure information, otherwise update the value of t: judge t _now > N, if t _now > N, we think the cumulative value of t _now is too large, in order to improve the operation Efficiency, we reassign the time t _now , t _now =t _prev =t; otherwise, we update t _prev : t _prev =t _prev +t, and generate the next hash chain at the same time. 2. password according to claim 1 has timeliness and the dynamic password authentication method that authentication number of times is not limited, it is characterized in that, In the step (2), K refers to the static password submitted by the user, id is the salt generated at random, N refers to the chain length of the generated hash chain, j refers to currently generating the jth hash function, and c is Refers to generating a c-bit binary number, m||n refers to the concatenation of m and n. 3. The dynamic password authentication method that does not need to re-register and supports offline authentication according to claim 1, wherein, In the step (3), x ₀ is the seed of the initial hash chain randomly selected by the user, y ₀ is the value of x ₀ after N times of hash operations, x ₁ =h ₁ (x ₀ ), x ₂ =h ₂ (h ₁ (x ₀ )), x ₃ =h ₃ (h ₂ (h ₁ (x ₀ )))...y ₀ =x _N =h _N (h _N-1 (...h ₁ (x ₀ ))). 4. password according to claim 1 has timeliness and the dynamic password authentication method that authentication number of times is not limited, it is characterized in that, In the step (4), the user sends the user name and the initial verification value y to the server, and the server obtains the first verification value, and stores N different hash functions _at the same time, and the verification of N different hash functions in the later stage used in calculations. 5. password according to claim 1 has timeliness and the dynamic password authentication method that authentication number of times is not limited, it is characterized in that, In the step (5), i means that the user has successfully logged in (i-1) times, and x _i is the user's random time interval between the (i-2) and (i-1) logins. The seed of the selected i-th hash short chain, t _now represents the current time, t _prev represents the cumulative value of the previous successful login times, and the dynamic password for user login at time t _now is p _t . 6. password according to claim 1 has timeliness and the dynamic password authentication method that authentication number of times is not limited, it is characterized in that, In the step (6), y _i+1 is the chain tail of the (i+1)th hash short chain generated by the user during the time interval between the (i-1)th and i-th two logins, It is also the verification value of the next user login, and the user sends the dynamic password p _t logged in at t _now and the verification value y _i+1 of the next login to the server. 7. password according to claim 1 has timeliness and the dynamic password authentication method that authentication number of times is not limited, it is characterized in that, The judgment of t _now in the step (8) is to detect whether the value of t _now is too large, because the value of t _now is dynamically accumulated in a very short time, if the value of t _now is too large, it will affect our operating efficiency , when t _now > N, we think that the value of t is too large, and we need to do a process similar to clearing t _now . Since the value of t _now is related to our current dynamic password acquisition, we make the following adjustments: t _now =t _prev =t; otherwise, we update the time accumulation value t _prev : t _prev =t _prev +t.