# An Authentication Scheme Based on Novel Construction of Hash Chains for Smart Mobile Devices

Authors: Qinglong Huang; Haiping Huang; Wenming Wang; Qi Li; Yuhan Wu
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

With the increasing number of smart mobile devices, applications based on mobile network take an indispensable role in the Internet of Things. Due to the limited computing power and restricted storage capacity of mobile devices, it is very necessary to design a secure and lightweight authentication scheme for mobile devices. As a lightweight cryptographic primitive, the hash chain is widely used in various cryptographic protocols and one-time password systems. However, most of the existing research work focuses on solving its inherent limitations and deficiencies, while ignoring its security issues. We propose a novel construction of hash chain that consists of multiple different hash functions of different output lengths and employ it in a time-based one-time password (TOTP) system for mobile device authentication. The security foundation of our construction is that the order of the hash functions is confidential and the security analysis demonstrates that it is more secure than other constructions. Moreover, we discuss the degeneration of our construction and implement the scheme in a mobile device. The simulation experiments show that the attacker cannot increase the probability of guessing the order by eavesdropping on the invalid passwords.


---

## Body

## 1. Introduction

The Internet of Things (IoT) is becoming more and more closely connected with people’s daily lives, due to the popularity of mobile devices which takes a central role in IoT. Users can use applications installed on mobile devices to obtain and transfer sensitive data, so the user authentication is a necessary process to ensure the security and privacy. For instance, SMS-based (Short Message Service) authentication is widely employed in many applications, such as Gmail. However, in the latest draft of the Digital Authentication Guideline, NIST (National Institute of Standards and Technology) has announced that the SMS-based authentication is deprecated and may no longer be allowed in the future releases of the guideline [1]. Furthermore, unlike traditional personal computers and laptops, mobile devices have limited energy, computing power, and storage capacity. Thus, it is not practical for the authentication schemes to employ expensive cryptographic primitives.Hash chain used in Lamport’s one-time password (OTP) [2] has become an important lightweight cryptographic primitive since it was proposed, which greatly improves the security of the simple password system. It also has been widely adopted to design key management and authentication mechanisms. The time-based one-time password (TOTP) system based on the hash chain is the most widely applied authentication system in which each password is valid only for a fixed time interval. TOTP system is more secure than SMS-based authentication, and the user can be authenticated implicitly. For example, some multifactor key management and authentication schemes [3–5] adopt the hash chain to ensure forward security, because the security foundation of the hash chain is guaranteed by its unidirectional nature. Hash chain is also employed by some broadcast authentication protocols [6] as one of the building blocks. And in many countries, the TOTP system has been chosen as a major security component of Internet banking to authenticate account holders. Thus, the TOTP system can be an alternative to replace SMS-based authentication [7, 8].Hash chain is a very important tool to design the TOTP system. However, the hash chain still has some limitations and disadvantages that are issued by many literatures. First, one hash chain can only perform one-way authentication for two parties. The mutual authentication implemented by the hash chain requires both parties to store a secret value that is known as “seed,” which cannot be implemented or may cause huge security issues in many scenarios. Second, due to the limited length of the hash chain, a new hash chain must be generated and both parties have to reregister when the last hash chain has been consumed. Park [9] proposed an endless hash chain composed of many short chains in which each authentication message contains the commitment of the next short hash chain. The studies of [8, 9] designed a multilevel hash chain to avoid its exhaustion. And [10–15] presented a self-renewal hash chain in which a new hash chain will be established if the old one is consumed. Third, the computational burden is much higher when the sender generates a new one-time password in which multiple hash operations are required. [16–18] proposed construction methods to store and recover an intermediate value of a hash chain. [18, 19] further discussed the optimal time-memory tradeoff for the traversal of sequence hash chain. Hu et al. [10] gave two construction methods enabling faster verification.Although most of the existing researches have addressed the issues caused by the above limitations and disadvantages, there is little related literature on the security research of the hash chain itself. Given the complex mobile environment and the open nature of channels (wireless channels) connected to mobile devices, the Lamport’s hash chain is easier to be inverted than a single hash function if the attacker can eavesdrop on lots of values of hash chains. Thus, Kogan et al. [20] improves the safety of Lamport’s hash chain by domain separation.


### 1.1. Our Work

In this paper, we introduce a novel construction of the hash chain and design a TOTP scheme for authentication of mobile devices. In our scheme, the hash chain is composed ofk different hash functions with different output length. Compared to Lamport’s hash chain, our construction can address the issue that the invalid password may help the attacker to invert the hash chain. Therefore, keeping the order of these hash functions confidential can effectively prevent the attacker from inverting the hash chain. And meanwhile, this design presents a challenge whether an attacker can easily find the order, which will come through a simulation. Besides, our scheme can be easily adopted by multifactor authentication scheme because of the simplified structure, especially adaptive to mobile devices.The remainder of this paper is organized as follows. Section2 illustrates the overview of hash chains. Our construction of hash chain and a TOTP system is given in Section 3. In Section 4, we analyse the security of our construction. We discuss the degeneration of our construction and run simulation experiments in Section 5. Section 6 concludes this paper.


## 1.1. Our Work

In this paper, we introduce a novel construction of the hash chain and design a TOTP scheme for authentication of mobile devices. In our scheme, the hash chain is composed ofk different hash functions with different output length. Compared to Lamport’s hash chain, our construction can address the issue that the invalid password may help the attacker to invert the hash chain. Therefore, keeping the order of these hash functions confidential can effectively prevent the attacker from inverting the hash chain. And meanwhile, this design presents a challenge whether an attacker can easily find the order, which will come through a simulation. Besides, our scheme can be easily adopted by multifactor authentication scheme because of the simplified structure, especially adaptive to mobile devices.The remainder of this paper is organized as follows. Section2 illustrates the overview of hash chains. Our construction of hash chain and a TOTP system is given in Section 3. In Section 4, we analyse the security of our construction. We discuss the degeneration of our construction and run simulation experiments in Section 5. Section 6 concludes this paper.


## 2. Overview of Hash Chains

In this section, we briefly review the Lanport’s and Kogan et al.’s hash chains and their security.


### 2.1. Lamport’s Hash Chain

The hash chainxi=hxi−1,i=1,⋯,N proposed by Lamport is the continuous iteration of a secret value x0 with the same hash function, as shown in Figure 1.Figure 1
Lamport’s hash chain.The secret value is generated by the user and the root of the hash chainxN, which is called commitment, should be registered on the server in advance. Whenever the server receives a password xi from the user, the server verifies whether it equals the commitment xi+1 by a hash operation, namely, hxi?=xi+1. If the verification is passed, the server stores xi as a new commitment for the next authentication.A classic attack on the hash function is the birthday attack. The Lamport’s hash chain is generated by iterating the same hash function, so birthday attack is still an effective attack to the hash chain. Hu et al. [10] has discussed the susceptibility of iterating the hash function to birthday attack. Furthermore, Håstad and Näslund [21] got a conclusion that inverting the k-th iteration is k times easier than a single hash function if the same hash function is used in each step of the hash chain. Nevertheless, this research still works on the hash chain based on the same hash function.


### 2.2. Kogan et al.’s Construction

Kogan et al. [20] proposed a TOTP system called T/Key that is designed as a second-factor authentication scheme, which can be used in mobile devices. The hash chain used in T/Key is composed of independent hash functions hk in every step, as shown in Figure 2.Figure 2
The structure of T/Key’s hash chain.x0∈0,1n is a uniformly random secret key.These hash functionshi:0,1n⟶0,1n,i=1,2,⋯,Nare obtained from a certain hash function H:0,1m⟶0,1m by domain separation.
(1)hix=H<tinit+n−i>c∣id∣xn,where tinit is the initialization time and id∈0,1s is a random salt. For a numeral t, <t>c denotes the c-bit binary representation of t, and tn denotes the n-bit prefix of t. And these functions have the same domain so that it can withstand length extension attack.In T/Key, each password is valid for a specific time intervalI. The user computes
(2)xN=hNhN−1⋯h1x0⋯,at first and sends it along with random salt id to the server as a commitment. At a later time t, the user sends a password xi to the server. When the server receives it, the server verifies whether it equals the stored commitment xi+j by j hash operations, namely,
(3)hi+j⋯hi−1xi⋯?=xi+j.If the verification passes, the server stores thexi as a new commitment for the next authentication.Kogan et al. also demonstrate that the difficulty of inverting this construction is almost the same as inverting a single hash function. However, as the length of the hash chain increases, a larger domain ofH is integrant.


## 2.1. Lamport’s Hash Chain

The hash chainxi=hxi−1,i=1,⋯,N proposed by Lamport is the continuous iteration of a secret value x0 with the same hash function, as shown in Figure 1.Figure 1
Lamport’s hash chain.The secret value is generated by the user and the root of the hash chainxN, which is called commitment, should be registered on the server in advance. Whenever the server receives a password xi from the user, the server verifies whether it equals the commitment xi+1 by a hash operation, namely, hxi?=xi+1. If the verification is passed, the server stores xi as a new commitment for the next authentication.A classic attack on the hash function is the birthday attack. The Lamport’s hash chain is generated by iterating the same hash function, so birthday attack is still an effective attack to the hash chain. Hu et al. [10] has discussed the susceptibility of iterating the hash function to birthday attack. Furthermore, Håstad and Näslund [21] got a conclusion that inverting the k-th iteration is k times easier than a single hash function if the same hash function is used in each step of the hash chain. Nevertheless, this research still works on the hash chain based on the same hash function.


## 2.2. Kogan et al.’s Construction

Kogan et al. [20] proposed a TOTP system called T/Key that is designed as a second-factor authentication scheme, which can be used in mobile devices. The hash chain used in T/Key is composed of independent hash functions hk in every step, as shown in Figure 2.Figure 2
The structure of T/Key’s hash chain.x0∈0,1n is a uniformly random secret key.These hash functionshi:0,1n⟶0,1n,i=1,2,⋯,Nare obtained from a certain hash function H:0,1m⟶0,1m by domain separation.
(1)hix=H<tinit+n−i>c∣id∣xn,where tinit is the initialization time and id∈0,1s is a random salt. For a numeral t, <t>c denotes the c-bit binary representation of t, and tn denotes the n-bit prefix of t. And these functions have the same domain so that it can withstand length extension attack.In T/Key, each password is valid for a specific time intervalI. The user computes
(2)xN=hNhN−1⋯h1x0⋯,at first and sends it along with random salt id to the server as a commitment. At a later time t, the user sends a password xi to the server. When the server receives it, the server verifies whether it equals the stored commitment xi+j by j hash operations, namely,
(3)hi+j⋯hi−1xi⋯?=xi+j.If the verification passes, the server stores thexi as a new commitment for the next authentication.Kogan et al. also demonstrate that the difficulty of inverting this construction is almost the same as inverting a single hash function. However, as the length of the hash chain increases, a larger domain ofH is integrant.


## 3. Our Construction

The hash chain used in T/Key has a limitation that the domain should be larger as the length of the hash chain increases, and the independent hash functions are actually generated by the same hash function. Therefore, the basic ideal of our construction is that multiple hash functions, e.g., SHA-2 and MD5, are selected to build the hash chain, and these hash functions have different output length. The order of these hash functionsord is confidential. We denote these hash functions as h0,⋯,hk−1, and their output lengths are nii=0,⋯,k−1. For example, if two hash functions (k=2), SHA-2 and MD5, have been chosen, there are two orders, ord=h0=SHA−2,h1=MD5 or ord=h0=MD5,h1=SHA−2. These hash functions are used cyclically in the hash chain, namely,
(4)Hx=hk−1m⋯hk−12k⋯h0k+1hk−1k⋯h12h01x⋯⋯⋯,where hij is one of the k hash functions, and i=j−1modk represents the index of hash function hii=0,⋯,k−1 used in j-th iteration and m is the hash chain length. Since the hash function used in j-th iteration can be inferred from its index, hij will be simplified as hj, and ha,bb>a is equivalent to hb∘hb−1∘⋯∘ha. The secret information x=sk‖ord consists of two parts: the secret key sk and the order of these hash functions ord.The hash chain we constructed is used as a time-based one-time password scheme to authenticate the mobile device where each password is valid for a short time interval. The scheme consists of only two phases so that it can be easily integrated into many multifactor authentication schemes or used as a separate auxiliary authentication method for mobile devices. Since that, a hash chain can only be used for authentication by two parties; the roles in our scheme are simplified to two. The party requesting authentication is a mobile deviceM (or a mobile application), and the verifier who verifies the password sent by a mobile device or application is a server S. Figure 3 shows the design of our proposal.Figure 3
The design of our proposal.x=sk‖ord is the secret information and tend is the moment that the hash chain is consumed.


### 3.1. Setup

The mobile deviceM selects k hash functions h0,⋯,hk−1 with different output length ni and then chooses and stores the order ord, the hash chain length m, and a random secret key sk. The mobile device M (or the sever S) notes the time interval I (in seconds), which represents the valid time of each password and the initial time of the hash chain tinit (measured in I). The public parameters h0,⋯,hk−1,n0,⋯,nk−1,I,tinit,m can be sent to both two parties through an insecure channel. The order of hash functions ord should be sent to the server in a secure channel.Moreover,M computes
(5)mesroot=h1,mx,and sends it to the server S. Then, S stores it as mesv for the next verification and records tinitastv.


### 3.2. Authentication

At some timet>tinit, M wants to access the server. The mobile device M and the server S proceed as follows:
(i)
M generates the password mest using the secret key sk and the order ord. And M sends it to the server(6)mest=h1,m−txParticularly, ift=m, then mest=x.
(ii)
Upon receiving themest, S firstly checks whether the password lenmest is valid. If lenmest=nm−t−1modk, S accepts it, otherwise, refuses it(iii)
S then verifies the password according to ord and computes(7)mest′=hm−t+1,m−tvmest(iv)
Ifmest′=mesv, then S sets mesv=mest and tv=t, and the authentication successes, otherwise, the authentication fails


### 3.3. Clock Synchronization

In the TOTP system, a synchronized clock is necessary to ensure the authentication process. However, time skew or network natural delay is unavoidable, which may cause authentication failure. If time skew can be quickly repaired, then no additional mechanism is needed, as this only causes one authentication failure when it happens. Otherwise, when the time skew or network natural delay continues, a solution is that each password is valid for serval time intervals (related toI), instead of only valid for a time interval. In this case, the server S needs to verify the password in each valid time, and tv should be updated to the time of successful verification.


## 3.1. Setup

The mobile deviceM selects k hash functions h0,⋯,hk−1 with different output length ni and then chooses and stores the order ord, the hash chain length m, and a random secret key sk. The mobile device M (or the sever S) notes the time interval I (in seconds), which represents the valid time of each password and the initial time of the hash chain tinit (measured in I). The public parameters h0,⋯,hk−1,n0,⋯,nk−1,I,tinit,m can be sent to both two parties through an insecure channel. The order of hash functions ord should be sent to the server in a secure channel.Moreover,M computes
(5)mesroot=h1,mx,and sends it to the server S. Then, S stores it as mesv for the next verification and records tinitastv.


## 3.2. Authentication

At some timet>tinit, M wants to access the server. The mobile device M and the server S proceed as follows:
(i)
M generates the password mest using the secret key sk and the order ord. And M sends it to the server(6)mest=h1,m−txParticularly, ift=m, then mest=x.
(ii)
Upon receiving themest, S firstly checks whether the password lenmest is valid. If lenmest=nm−t−1modk, S accepts it, otherwise, refuses it(iii)
S then verifies the password according to ord and computes(7)mest′=hm−t+1,m−tvmest(iv)
Ifmest′=mesv, then S sets mesv=mest and tv=t, and the authentication successes, otherwise, the authentication fails


## 3.3. Clock Synchronization

In the TOTP system, a synchronized clock is necessary to ensure the authentication process. However, time skew or network natural delay is unavoidable, which may cause authentication failure. If time skew can be quickly repaired, then no additional mechanism is needed, as this only causes one authentication failure when it happens. Otherwise, when the time skew or network natural delay continues, a solution is that each password is valid for serval time intervals (related toI), instead of only valid for a time interval. In this case, the server S needs to verify the password in each valid time, and tv should be updated to the time of successful verification.


## 4. Security Analysis

### 4.1. Forward Security

Our protocol can provide forward security, which means that if one key of the hash chainmest is leaked at a certain time, the previous authentication process will not be affected. In our construction, the order of hash functions is securely stored in both mobile devices and servers. The adversary has no way to compute the key mesii<t. In the worse situation where ord is no longer a secret, the mesi computed by the adversary is expired, so the adversary cannot pass the verification. Thus, our protocol achieves the forward security.


### 4.2. A Lower Bound of Inverting Hash Chain

Our construction is hard to invert because it is composed of multiple different hash functions that have different lengths. However, this is vulnerable to length extension attacks, especially when some hash functions are MD-based hash functions. To prevent this kind of attack, the server has to verify the length of the password first after receiving it.The next crucial question is how difficult is it to invert our construction in our TOTP system. For clarity and completeness, we review some key theories before analysing the security of our scheme.


#### 4.2.1. Lamport’s Construction

In the Lamport’s hash function, the attacker can utilize invalid passwords which have been authenticated in the past to invert the hash chain. As more and more passwords are collected, attackers will have a greater chance of obtaining a legitimate preimage by oracle query.Furthermore, Håstad and Näslund show that, in a hash chain composed of the same hash function, the adversary inverts thek-th iteration is actually k times easier than inverting a single hash function. The representation is rearranged here for completeness and better understanding.Theorem 1 (Inverting the original hash chain) (see [21]).
LetA be an algorithm that tries to invert a hash function h:0,1n⟶0,1n which makes T oracle queries at most. Given y=fkx for a randomly chosen x, then
(8)PrhAy=y=ΩTk2n.
Moreover,A succeeds with the probability at most OTk/2n.


#### 4.2.2. T/Key’s Construction

Kogan et al. give a further analysis of the inverting hash chain which usesk independent hash functions defined by a certain hash function H through domain separation, which shows as Theorem 2.Theorem 2 (Inverting the T/Key’s hash chain) (see [20]).
Let functionsh1,⋯,hk:0,1n⟶0,1n be chosen independently and uniformly at random. Let A be an algorithm that can get oracle queries to all of the functions h1,⋯,hk which makes T oracle queries at most overall. Thus,
(9)PrhkAh1,kx0=h1,kx0≤2T+32n,where h1,k=hk∘hk−1∘⋯∘h1.Proof.
We briefly prove this theorem which will prepare for the following proof of other theorems. LetP=p0,p1,⋯,pk be the values of the hash chain, i.e., p0=x, pi=hipi−1, and i=1,⋯,k. The algorithm A also needs to maintain a list L=i,x,y,hix=y, which records the oracle queries x and their answers y. For any query i,x, if x=pi−1, A responds with y=pi and adds i,pi−1,pi to the list. Else if i,x∈L, A replies with y. Otherwise, A chooses y=0,1n randomly. Thus, to invert the hash chain, at least one query result should collide with P. It follows that
(10)PrH,x0Aloses=PrH,x0⋂j=1T+1yj≠pij=∏j=1T+1PrH,x0yj≠pij∣⋂l=1j−1yl≠pil≥∏j=1T+11−22n−j+1≥22n−2T+32n22n.
Therefore,(11)PrH,x0Awins≤2T+32n.Theorem2 demonstrates that inverting a hash chain using independent hash function results in a loss of security by a factor of 2, but by a factor of Ok if the same hash function is used in the entire chain. Inverting this construction is as hard as a single hash function. Moreover, in the proof, algorithm A is designed to get oracle access to all the functions h1,⋯,hk. In fact, these functions have the same domain as well as the function H, which means that algorithm A actually only gets oracle access to one hash function H.


#### 4.2.3. Our Construction

In our proposal, the hash chain is composed ofk different hash functions, and the attacker is hard to invert the chain due to the secrecy of the order of these functions. For an attacker who does not know ord, the entire hash chain can be regarded as consisting of multiple independent hash functions.When the attacker wants to invert the chain, he has two choices. The attacker either “guesses” a hash function that may be the right one and queries (see Theorem3), or averages T oracle queries to all hash functions (see Theorem 4). These two choices are both analysed.Theorem 3.
Let functionsh0,⋯,hk−1:0,1∗⟶0,1ni be different hash functions with distinct output length ni. Let A be an algorithm that can get oracle queries to a certain hash function which can make T oracle queries at most overall. Thus,
(12)PrhmAh1,mx=h1,mx≤2T+3k2nm−1modk.Proof.
We say the attacker successfully inverts the hash chain when he finds a preimage that meets the length requirement. LetA be an algorithm as in the statement of Theorem 2, and we used it to construct another algorithm A1 for finding the preimage of the last iteration. The first step of A1 is to select a hash function H which is used in hm−1 and
(13)PrH=hm−1=1k,(14)PrH≠hm−1=k−1k.
Then, algorithmA1 runs algorithm A to get oracle access to hash function H and query T times at most and inputs the result to hm. It follows that
(15)PrH,xA1loses=PrH,xH≠hm−1+PrH,x⋂j=1T+1yj≠pij,H=hm−1=k−1k+PrH,xH≠hm−1∙PrH,x⋂j=1T+1yj≠pij∣H=hm−1.
According to Theorem2, we know
(16)PrH,x⋂j=1T+1yj≠pij∣H=hm−1≥22nm−1modk−2T+3∙22nm−1modk22nm−1modk.
Overall,(17)PrH,xA1loses≥nm−1modk2−2T+3∙2nm−1modk22nm−1modk.
Therefore,(18)PrH,xA1wins≤2T+3k2nm−1modk.Theorem 4.
Let functionsh0,⋯,hk−1:0,1∗⟶0,1ni be different hash functions with distinct output length ni. Let A be an algorithm that can get oracle queries to all of the functions h0,⋯,hk−1 which makes T oracle queries at most overall. Thus,
(19)PrhmAh1,mx=h1,mx≤2T+3kk22nm−1modk.Proof.
LetA be an algorithm as in the statement of Theorem 2. We use it to construct another algorithm A2 which finds the preimage of the last iteration of the hash chain. The algorithm A2 runs algorithm A first, which queries T times at most to all k hash functions, scilicet T/k oracle queries for each function. The legal preimage could be got only from the query results which returned by the oracle access to hm−1, and the algorithm A makes T/k oracle queries to it.
Therefore, according to Theorem3,
(20)PrH,xA2wins≤2T/k+3k2nm−1modk=2T+3kk22nm−1modk.The above two theorems establish the difficulty of finding a preimage of the last iteration of the hash chain in the authentication scheme. And the difficulty of inverting the hash chain which is composed ofk different hash functions with different output length is further reduced to OT/k2n, where n is the average length of these functions.


### 4.3. Formal Security Analysis

In the following, we show our protocol is provably secure in the random oracle model since the hash function behaves closely like a random oracle [22–24]. We first present a formal description of the proposed protocol before defining the security game, which is a tuple P=s,k,p,v.In the setup phase, the polynomial time algorithmsk,m⟶ni takes as input the number of hash functions k and the length of hash chain m and outputs the password length ni. Next, the algorithm kni,m⟶sm,vs takes as input the password length ni and hash chain length m and outputs the secret message sm and the verifier state vs. In the authentication phase, the prover psm,t⟶pwd outputs a one-time password pwd by taking as input the secret message sm and a time t. While the verifier vvs,pwd,t⟶ACCEPT/REJECT,vs′ takes as input the verifier state vs, one-time password pwd and a time t outputs a state that the password is accepted or rejected and a new verifier state vs′. Afterwards, we are ready to define the attack game.Attack Game 5.
LetP be a one-time password protocol and let R be a random oracle. Given a challenger C and an adversary A, the attack game acts as follows:
(i)
Setup. The challenger generates password lengths ni⟵sCk,m(ii)
KeyGen. The challenger generates sm,vs⟵kCni,m by random oracle(iii)
Password Query. The adversary sends a time t to the challenger. The challenger generates a password pwd⟵pCsm,t, which is fed to the verifier ACCEPT/REJECT,vs′⟵vCvs,pwd,t(iv)
Test. The adversary submits a password tA,pwdA
The attacker will win the game if the verifier outputACCEPT by vCvs,pwd,t. We denote AdvPTestA as the probability that A successfully impersonates as a legal user in the execution of protocol P.Theorem 6.
LetP be the proposed protocol in the Section 3. Let A be a probabilistic polynomial-time adversary attacking the protocol that makes at most T oracle queries with the length m and the number of hash function k.
(21)AdvPTest≤2T+2m+3k2nm−1modk.Proof.
LetA be an algorithm stated before. We, using algorithm A, construct algorithm A3 that makes the oracle query of the last iteration of the hash chain. The adversary wins the game if and only if the verifier outputs ACCEPT by taking as input the password tA,pwdA, i.e., hm−tA+1,kpwdA=vs. Without loss of generality, we assume that the verifier state vs=h1,msm. With the input ni⟵sCk,m, the algorithm A3 runs A to get a point y and computes y′=h1,m−1y. If hmy′=h1,msm, then h1,my=h1,msm. Thus, the algorithm makes at most T+m−1 oracle queries. According to Theorem 3,
(22)AdvPTest≤2T+m−1+3k2nm−1modk≤2T+2m+1k2nm−1modk.


## 4.1. Forward Security

Our protocol can provide forward security, which means that if one key of the hash chainmest is leaked at a certain time, the previous authentication process will not be affected. In our construction, the order of hash functions is securely stored in both mobile devices and servers. The adversary has no way to compute the key mesii<t. In the worse situation where ord is no longer a secret, the mesi computed by the adversary is expired, so the adversary cannot pass the verification. Thus, our protocol achieves the forward security.


## 4.2. A Lower Bound of Inverting Hash Chain

Our construction is hard to invert because it is composed of multiple different hash functions that have different lengths. However, this is vulnerable to length extension attacks, especially when some hash functions are MD-based hash functions. To prevent this kind of attack, the server has to verify the length of the password first after receiving it.The next crucial question is how difficult is it to invert our construction in our TOTP system. For clarity and completeness, we review some key theories before analysing the security of our scheme.


### 4.2.1. Lamport’s Construction

In the Lamport’s hash function, the attacker can utilize invalid passwords which have been authenticated in the past to invert the hash chain. As more and more passwords are collected, attackers will have a greater chance of obtaining a legitimate preimage by oracle query.Furthermore, Håstad and Näslund show that, in a hash chain composed of the same hash function, the adversary inverts thek-th iteration is actually k times easier than inverting a single hash function. The representation is rearranged here for completeness and better understanding.Theorem 1 (Inverting the original hash chain) (see [21]).
LetA be an algorithm that tries to invert a hash function h:0,1n⟶0,1n which makes T oracle queries at most. Given y=fkx for a randomly chosen x, then
(8)PrhAy=y=ΩTk2n.
Moreover,A succeeds with the probability at most OTk/2n.


### 4.2.2. T/Key’s Construction

Kogan et al. give a further analysis of the inverting hash chain which usesk independent hash functions defined by a certain hash function H through domain separation, which shows as Theorem 2.Theorem 2 (Inverting the T/Key’s hash chain) (see [20]).
Let functionsh1,⋯,hk:0,1n⟶0,1n be chosen independently and uniformly at random. Let A be an algorithm that can get oracle queries to all of the functions h1,⋯,hk which makes T oracle queries at most overall. Thus,
(9)PrhkAh1,kx0=h1,kx0≤2T+32n,where h1,k=hk∘hk−1∘⋯∘h1.Proof.
We briefly prove this theorem which will prepare for the following proof of other theorems. LetP=p0,p1,⋯,pk be the values of the hash chain, i.e., p0=x, pi=hipi−1, and i=1,⋯,k. The algorithm A also needs to maintain a list L=i,x,y,hix=y, which records the oracle queries x and their answers y. For any query i,x, if x=pi−1, A responds with y=pi and adds i,pi−1,pi to the list. Else if i,x∈L, A replies with y. Otherwise, A chooses y=0,1n randomly. Thus, to invert the hash chain, at least one query result should collide with P. It follows that
(10)PrH,x0Aloses=PrH,x0⋂j=1T+1yj≠pij=∏j=1T+1PrH,x0yj≠pij∣⋂l=1j−1yl≠pil≥∏j=1T+11−22n−j+1≥22n−2T+32n22n.
Therefore,(11)PrH,x0Awins≤2T+32n.Theorem2 demonstrates that inverting a hash chain using independent hash function results in a loss of security by a factor of 2, but by a factor of Ok if the same hash function is used in the entire chain. Inverting this construction is as hard as a single hash function. Moreover, in the proof, algorithm A is designed to get oracle access to all the functions h1,⋯,hk. In fact, these functions have the same domain as well as the function H, which means that algorithm A actually only gets oracle access to one hash function H.


### 4.2.3. Our Construction

In our proposal, the hash chain is composed ofk different hash functions, and the attacker is hard to invert the chain due to the secrecy of the order of these functions. For an attacker who does not know ord, the entire hash chain can be regarded as consisting of multiple independent hash functions.When the attacker wants to invert the chain, he has two choices. The attacker either “guesses” a hash function that may be the right one and queries (see Theorem3), or averages T oracle queries to all hash functions (see Theorem 4). These two choices are both analysed.Theorem 3.
Let functionsh0,⋯,hk−1:0,1∗⟶0,1ni be different hash functions with distinct output length ni. Let A be an algorithm that can get oracle queries to a certain hash function which can make T oracle queries at most overall. Thus,
(12)PrhmAh1,mx=h1,mx≤2T+3k2nm−1modk.Proof.
We say the attacker successfully inverts the hash chain when he finds a preimage that meets the length requirement. LetA be an algorithm as in the statement of Theorem 2, and we used it to construct another algorithm A1 for finding the preimage of the last iteration. The first step of A1 is to select a hash function H which is used in hm−1 and
(13)PrH=hm−1=1k,(14)PrH≠hm−1=k−1k.
Then, algorithmA1 runs algorithm A to get oracle access to hash function H and query T times at most and inputs the result to hm. It follows that
(15)PrH,xA1loses=PrH,xH≠hm−1+PrH,x⋂j=1T+1yj≠pij,H=hm−1=k−1k+PrH,xH≠hm−1∙PrH,x⋂j=1T+1yj≠pij∣H=hm−1.
According to Theorem2, we know
(16)PrH,x⋂j=1T+1yj≠pij∣H=hm−1≥22nm−1modk−2T+3∙22nm−1modk22nm−1modk.
Overall,(17)PrH,xA1loses≥nm−1modk2−2T+3∙2nm−1modk22nm−1modk.
Therefore,(18)PrH,xA1wins≤2T+3k2nm−1modk.Theorem 4.
Let functionsh0,⋯,hk−1:0,1∗⟶0,1ni be different hash functions with distinct output length ni. Let A be an algorithm that can get oracle queries to all of the functions h0,⋯,hk−1 which makes T oracle queries at most overall. Thus,
(19)PrhmAh1,mx=h1,mx≤2T+3kk22nm−1modk.Proof.
LetA be an algorithm as in the statement of Theorem 2. We use it to construct another algorithm A2 which finds the preimage of the last iteration of the hash chain. The algorithm A2 runs algorithm A first, which queries T times at most to all k hash functions, scilicet T/k oracle queries for each function. The legal preimage could be got only from the query results which returned by the oracle access to hm−1, and the algorithm A makes T/k oracle queries to it.
Therefore, according to Theorem3,
(20)PrH,xA2wins≤2T/k+3k2nm−1modk=2T+3kk22nm−1modk.The above two theorems establish the difficulty of finding a preimage of the last iteration of the hash chain in the authentication scheme. And the difficulty of inverting the hash chain which is composed ofk different hash functions with different output length is further reduced to OT/k2n, where n is the average length of these functions.


## 4.2.1. Lamport’s Construction

In the Lamport’s hash function, the attacker can utilize invalid passwords which have been authenticated in the past to invert the hash chain. As more and more passwords are collected, attackers will have a greater chance of obtaining a legitimate preimage by oracle query.Furthermore, Håstad and Näslund show that, in a hash chain composed of the same hash function, the adversary inverts thek-th iteration is actually k times easier than inverting a single hash function. The representation is rearranged here for completeness and better understanding.Theorem 1 (Inverting the original hash chain) (see [21]).
LetA be an algorithm that tries to invert a hash function h:0,1n⟶0,1n which makes T oracle queries at most. Given y=fkx for a randomly chosen x, then
(8)PrhAy=y=ΩTk2n.
Moreover,A succeeds with the probability at most OTk/2n.


## 4.2.2. T/Key’s Construction

Kogan et al. give a further analysis of the inverting hash chain which usesk independent hash functions defined by a certain hash function H through domain separation, which shows as Theorem 2.Theorem 2 (Inverting the T/Key’s hash chain) (see [20]).
Let functionsh1,⋯,hk:0,1n⟶0,1n be chosen independently and uniformly at random. Let A be an algorithm that can get oracle queries to all of the functions h1,⋯,hk which makes T oracle queries at most overall. Thus,
(9)PrhkAh1,kx0=h1,kx0≤2T+32n,where h1,k=hk∘hk−1∘⋯∘h1.Proof.
We briefly prove this theorem which will prepare for the following proof of other theorems. LetP=p0,p1,⋯,pk be the values of the hash chain, i.e., p0=x, pi=hipi−1, and i=1,⋯,k. The algorithm A also needs to maintain a list L=i,x,y,hix=y, which records the oracle queries x and their answers y. For any query i,x, if x=pi−1, A responds with y=pi and adds i,pi−1,pi to the list. Else if i,x∈L, A replies with y. Otherwise, A chooses y=0,1n randomly. Thus, to invert the hash chain, at least one query result should collide with P. It follows that
(10)PrH,x0Aloses=PrH,x0⋂j=1T+1yj≠pij=∏j=1T+1PrH,x0yj≠pij∣⋂l=1j−1yl≠pil≥∏j=1T+11−22n−j+1≥22n−2T+32n22n.
Therefore,(11)PrH,x0Awins≤2T+32n.Theorem2 demonstrates that inverting a hash chain using independent hash function results in a loss of security by a factor of 2, but by a factor of Ok if the same hash function is used in the entire chain. Inverting this construction is as hard as a single hash function. Moreover, in the proof, algorithm A is designed to get oracle access to all the functions h1,⋯,hk. In fact, these functions have the same domain as well as the function H, which means that algorithm A actually only gets oracle access to one hash function H.


## 4.2.3. Our Construction

In our proposal, the hash chain is composed ofk different hash functions, and the attacker is hard to invert the chain due to the secrecy of the order of these functions. For an attacker who does not know ord, the entire hash chain can be regarded as consisting of multiple independent hash functions.When the attacker wants to invert the chain, he has two choices. The attacker either “guesses” a hash function that may be the right one and queries (see Theorem3), or averages T oracle queries to all hash functions (see Theorem 4). These two choices are both analysed.Theorem 3.
Let functionsh0,⋯,hk−1:0,1∗⟶0,1ni be different hash functions with distinct output length ni. Let A be an algorithm that can get oracle queries to a certain hash function which can make T oracle queries at most overall. Thus,
(12)PrhmAh1,mx=h1,mx≤2T+3k2nm−1modk.Proof.
We say the attacker successfully inverts the hash chain when he finds a preimage that meets the length requirement. LetA be an algorithm as in the statement of Theorem 2, and we used it to construct another algorithm A1 for finding the preimage of the last iteration. The first step of A1 is to select a hash function H which is used in hm−1 and
(13)PrH=hm−1=1k,(14)PrH≠hm−1=k−1k.
Then, algorithmA1 runs algorithm A to get oracle access to hash function H and query T times at most and inputs the result to hm. It follows that
(15)PrH,xA1loses=PrH,xH≠hm−1+PrH,x⋂j=1T+1yj≠pij,H=hm−1=k−1k+PrH,xH≠hm−1∙PrH,x⋂j=1T+1yj≠pij∣H=hm−1.
According to Theorem2, we know
(16)PrH,x⋂j=1T+1yj≠pij∣H=hm−1≥22nm−1modk−2T+3∙22nm−1modk22nm−1modk.
Overall,(17)PrH,xA1loses≥nm−1modk2−2T+3∙2nm−1modk22nm−1modk.
Therefore,(18)PrH,xA1wins≤2T+3k2nm−1modk.Theorem 4.
Let functionsh0,⋯,hk−1:0,1∗⟶0,1ni be different hash functions with distinct output length ni. Let A be an algorithm that can get oracle queries to all of the functions h0,⋯,hk−1 which makes T oracle queries at most overall. Thus,
(19)PrhmAh1,mx=h1,mx≤2T+3kk22nm−1modk.Proof.
LetA be an algorithm as in the statement of Theorem 2. We use it to construct another algorithm A2 which finds the preimage of the last iteration of the hash chain. The algorithm A2 runs algorithm A first, which queries T times at most to all k hash functions, scilicet T/k oracle queries for each function. The legal preimage could be got only from the query results which returned by the oracle access to hm−1, and the algorithm A makes T/k oracle queries to it.
Therefore, according to Theorem3,
(20)PrH,xA2wins≤2T/k+3k2nm−1modk=2T+3kk22nm−1modk.The above two theorems establish the difficulty of finding a preimage of the last iteration of the hash chain in the authentication scheme. And the difficulty of inverting the hash chain which is composed ofk different hash functions with different output length is further reduced to OT/k2n, where n is the average length of these functions.


## 4.3. Formal Security Analysis

In the following, we show our protocol is provably secure in the random oracle model since the hash function behaves closely like a random oracle [22–24]. We first present a formal description of the proposed protocol before defining the security game, which is a tuple P=s,k,p,v.In the setup phase, the polynomial time algorithmsk,m⟶ni takes as input the number of hash functions k and the length of hash chain m and outputs the password length ni. Next, the algorithm kni,m⟶sm,vs takes as input the password length ni and hash chain length m and outputs the secret message sm and the verifier state vs. In the authentication phase, the prover psm,t⟶pwd outputs a one-time password pwd by taking as input the secret message sm and a time t. While the verifier vvs,pwd,t⟶ACCEPT/REJECT,vs′ takes as input the verifier state vs, one-time password pwd and a time t outputs a state that the password is accepted or rejected and a new verifier state vs′. Afterwards, we are ready to define the attack game.Attack Game 5.
LetP be a one-time password protocol and let R be a random oracle. Given a challenger C and an adversary A, the attack game acts as follows:
(i)
Setup. The challenger generates password lengths ni⟵sCk,m(ii)
KeyGen. The challenger generates sm,vs⟵kCni,m by random oracle(iii)
Password Query. The adversary sends a time t to the challenger. The challenger generates a password pwd⟵pCsm,t, which is fed to the verifier ACCEPT/REJECT,vs′⟵vCvs,pwd,t(iv)
Test. The adversary submits a password tA,pwdA
The attacker will win the game if the verifier outputACCEPT by vCvs,pwd,t. We denote AdvPTestA as the probability that A successfully impersonates as a legal user in the execution of protocol P.Theorem 6.
LetP be the proposed protocol in the Section 3. Let A be a probabilistic polynomial-time adversary attacking the protocol that makes at most T oracle queries with the length m and the number of hash function k.
(21)AdvPTest≤2T+2m+3k2nm−1modk.Proof.
LetA be an algorithm stated before. We, using algorithm A, construct algorithm A3 that makes the oracle query of the last iteration of the hash chain. The adversary wins the game if and only if the verifier outputs ACCEPT by taking as input the password tA,pwdA, i.e., hm−tA+1,kpwdA=vs. Without loss of generality, we assume that the verifier state vs=h1,msm. With the input ni⟵sCk,m, the algorithm A3 runs A to get a point y and computes y′=h1,m−1y. If hmy′=h1,msm, then h1,my=h1,msm. Thus, the algorithm makes at most T+m−1 oracle queries. According to Theorem 3,
(22)AdvPTest≤2T+m−1+3k2nm−1modk≤2T+2m+1k2nm−1modk.


## 5. Discussions and Experiment

### 5.1. Degeneration

The hash chain constructed by us consists ofk different hash functions with different output length that can be freely selected by the mobile device or the server. This freedom of choice has caused more changes in our construction that needs to be discussed.First and foremost, as shown in security analysis, the length of the hash chain is no longer a key factor affecting the difficulty of inverting the hash chain, but the quantity of hash function selected is a key factor. Obviously, the larger the value ofk, the more difficult to invert the hash chain. Furthermore, when there is only one hash function k=1 in the hash chain, our construction will degenerate to Lamport’s hash chain.Second, the quantity of hash function with different output length is not unlimited. So, what happens if there are several functions that have the same output length, or the same hash function is used twice or more in the hash chain? At a macro level, it would be easier for an attacker to forge a password with this length because there is a greater probability of “guessing” the preimage correctly. If all the hash functions used in the hash chain have the same output length but the hash functions are different, it will degenerate into a special instance of T/Key’s construction. The chain is equivalent to connecting T/Key’s construction multiple times, and they have a similar difficulty for inverting the hash chain.Last but most importantly, the security of our construction is guaranteed by the confidentiality of the order of these hash functionsord. If the ord is leaked, the difficulty of breaking our solution will be reduced to OT/n which is the same as the difficulty of inverting a single hash function, because the invalid password only provides a limited effect to the attacker. In theory, the probability that an attacker finds the order without any prior knowledge is 1/k!. However, in practice, the mobile device (or application) authenticates to the server as a Poisson process. We will show how difficult it is for an attacker to guess ord if the attacker can eavesdrop on the authentication message through simulation in the next subsection.


### 5.2. Experimental Evaluation

As we analysed above, in our scheme, the order of hash functionsord is one part of the secret information x. Once it is leaked, the security of our mechanism will be greatly affected. In this section, we run a simulation to compute the difficulty of the attacker finding ord and then implement our construction in a real smart mobile device.Before starting the simulation, two crucial issues, the login pattern of the mobile device and the attacker’ behaviour, have to be discussed.In the real world, it is reasonable that the login behaviour of a mobile device (or application) follows the Poisson Process, which means that the time interval between consecutive logins can be modelled using the exponential distribution. Thus, the probability density function that the next authentication of mobile device at timet is
(23)pt=λe−λt,where λ is the average login rate.Then, we need to know how the attacker guesses theord which actually has k! possible permutations ordi,i=1,2,⋯,k!. The authentication message intercepted by the attacker can help him/her to guess ord. Since the lengths of these authentication messages are totally random, it is hard for an attacker to guess ord based on the context between them. But, for ord=h0,⋯,hk−1, in the sequence of attacker owned, hj only appear after hij<i before h0 appears. Thus, the attacker can count the number that ordi appears through the sequence. We define that the attacker finds the real ord by the probability
(24)Prattackerwins=numord∑iordi.Figure4 shows how the probability of an attacker’s guesses the ord changes over time (per month). If the attacker can eavesdrop on every authentication message, as the number of chain value held by the attacker increases, the probability of the attacker’s success decreases. This is because when the attacker has fewer chain values, the higher probability of correct ord appearing makes the attacker more likely to succeed.Figure 4
Probability of attacker wins whenp=1.The conclusion still holds when we change the eavesdropping probability of the attacker. Figure5 compares the probability that the attacker finds ord in the following eavesdropping probability: 0.2, 0.5, and 0.8, respectively. When p≤0.5, the probability peaks at third and fifth months, respectively. Meanwhile, due to the increasing number of hash chain values captured by attackers, the probability of attackers’ success is still decreasing. According to the law of large numbers, the probability that the attacker observes the correct ord approaches the theoretical value when the attacker has a large amount of hash chain values.Figure 5
Probability of attacker wins whenp=0.2,0.5,0.8.Theoretically, the probability that an attacker finds the correctord is 1/4!=1/24≈0.0417. While in our simulation, even if the attacker can intercept every authentication message, the probability does not exceed 0.0400. Therefore, an attacker eavesdropping on a channel does not increase the probability of finding the correct ord.The experiment environment is set up as follows: The smart device is a HUAWEI Mate 30 smartphone with 2.86 GHz CPU and 6 GB RAM running Android 10, and the server is executed on a 2-core CPU and 1024 MB memory running Ubuntu 18.04.We use 4 hash functions to instantiate our scheme discussed in Section3, which are MD5, SHA-1, SHA-2, and BLACK2b, and the output length is 128 bits, 160 bits, 256 bits, and 512 bits, respectively. The time interval I when each password is valid uses time slots of 30 seconds. We generate a hash chain with the length 1.05×106 that would be valid in one year. We assume that mobile device login once a day on average (λ=1/86400). Furthermore, an attacker eavesdrops on authentication message with a certain probability p. These parameters used in simulation experiments are shown in Table 1.Table 1
Experiment parameters.
ParameterValueDescriptionλ1/86400Average authentication ratem1.05×106Length of hash chainI30 secInterval timek4Number of hash functionsp0,1The probability of an attacker eavesdrops on passwordsAs a comparison, we also implement Lamport’s hash chain with 4 kinds of hash functions, respectively. We evaluate the following time: mobile device setup time, average password generation time (mobile device), and average verification time (server). Table2 shows the results.Table 2
Experiment result.
Setup time (seconds)Average password generation time (seconds)Average verification time (milliseconds)MD50.960.511.30SHA-12.211.082.40SHA-28.343.369.02BLAKE2b8.723.594.80Ours7.742.995.1As shown in Table2, the MD5 and SHA-1 hash functions have better performance, while it is not a good choice to construct the Lamport’s hash chain because both of them are not secure enough [20, 21]. Our solution has the best computational performance on a mobile device while ensuring security. And the server only takes several milliseconds to verify the password which is acceptable in general. More experimental results can be obtained through online resources (https://github.com/qinglong-huang/hash_chains_experiments).Both theoretical analyses in Section4 and simulation experiments that we performed demonstrate that the hash chain scheme proposed in this paper is still harder to invert. Therefore, our scheme has better performance on computation and security.


## 5.1. Degeneration

The hash chain constructed by us consists ofk different hash functions with different output length that can be freely selected by the mobile device or the server. This freedom of choice has caused more changes in our construction that needs to be discussed.First and foremost, as shown in security analysis, the length of the hash chain is no longer a key factor affecting the difficulty of inverting the hash chain, but the quantity of hash function selected is a key factor. Obviously, the larger the value ofk, the more difficult to invert the hash chain. Furthermore, when there is only one hash function k=1 in the hash chain, our construction will degenerate to Lamport’s hash chain.Second, the quantity of hash function with different output length is not unlimited. So, what happens if there are several functions that have the same output length, or the same hash function is used twice or more in the hash chain? At a macro level, it would be easier for an attacker to forge a password with this length because there is a greater probability of “guessing” the preimage correctly. If all the hash functions used in the hash chain have the same output length but the hash functions are different, it will degenerate into a special instance of T/Key’s construction. The chain is equivalent to connecting T/Key’s construction multiple times, and they have a similar difficulty for inverting the hash chain.Last but most importantly, the security of our construction is guaranteed by the confidentiality of the order of these hash functionsord. If the ord is leaked, the difficulty of breaking our solution will be reduced to OT/n which is the same as the difficulty of inverting a single hash function, because the invalid password only provides a limited effect to the attacker. In theory, the probability that an attacker finds the order without any prior knowledge is 1/k!. However, in practice, the mobile device (or application) authenticates to the server as a Poisson process. We will show how difficult it is for an attacker to guess ord if the attacker can eavesdrop on the authentication message through simulation in the next subsection.


## 5.2. Experimental Evaluation

As we analysed above, in our scheme, the order of hash functionsord is one part of the secret information x. Once it is leaked, the security of our mechanism will be greatly affected. In this section, we run a simulation to compute the difficulty of the attacker finding ord and then implement our construction in a real smart mobile device.Before starting the simulation, two crucial issues, the login pattern of the mobile device and the attacker’ behaviour, have to be discussed.In the real world, it is reasonable that the login behaviour of a mobile device (or application) follows the Poisson Process, which means that the time interval between consecutive logins can be modelled using the exponential distribution. Thus, the probability density function that the next authentication of mobile device at timet is
(23)pt=λe−λt,where λ is the average login rate.Then, we need to know how the attacker guesses theord which actually has k! possible permutations ordi,i=1,2,⋯,k!. The authentication message intercepted by the attacker can help him/her to guess ord. Since the lengths of these authentication messages are totally random, it is hard for an attacker to guess ord based on the context between them. But, for ord=h0,⋯,hk−1, in the sequence of attacker owned, hj only appear after hij<i before h0 appears. Thus, the attacker can count the number that ordi appears through the sequence. We define that the attacker finds the real ord by the probability
(24)Prattackerwins=numord∑iordi.Figure4 shows how the probability of an attacker’s guesses the ord changes over time (per month). If the attacker can eavesdrop on every authentication message, as the number of chain value held by the attacker increases, the probability of the attacker’s success decreases. This is because when the attacker has fewer chain values, the higher probability of correct ord appearing makes the attacker more likely to succeed.Figure 4
Probability of attacker wins whenp=1.The conclusion still holds when we change the eavesdropping probability of the attacker. Figure5 compares the probability that the attacker finds ord in the following eavesdropping probability: 0.2, 0.5, and 0.8, respectively. When p≤0.5, the probability peaks at third and fifth months, respectively. Meanwhile, due to the increasing number of hash chain values captured by attackers, the probability of attackers’ success is still decreasing. According to the law of large numbers, the probability that the attacker observes the correct ord approaches the theoretical value when the attacker has a large amount of hash chain values.Figure 5
Probability of attacker wins whenp=0.2,0.5,0.8.Theoretically, the probability that an attacker finds the correctord is 1/4!=1/24≈0.0417. While in our simulation, even if the attacker can intercept every authentication message, the probability does not exceed 0.0400. Therefore, an attacker eavesdropping on a channel does not increase the probability of finding the correct ord.The experiment environment is set up as follows: The smart device is a HUAWEI Mate 30 smartphone with 2.86 GHz CPU and 6 GB RAM running Android 10, and the server is executed on a 2-core CPU and 1024 MB memory running Ubuntu 18.04.We use 4 hash functions to instantiate our scheme discussed in Section3, which are MD5, SHA-1, SHA-2, and BLACK2b, and the output length is 128 bits, 160 bits, 256 bits, and 512 bits, respectively. The time interval I when each password is valid uses time slots of 30 seconds. We generate a hash chain with the length 1.05×106 that would be valid in one year. We assume that mobile device login once a day on average (λ=1/86400). Furthermore, an attacker eavesdrops on authentication message with a certain probability p. These parameters used in simulation experiments are shown in Table 1.Table 1
Experiment parameters.
ParameterValueDescriptionλ1/86400Average authentication ratem1.05×106Length of hash chainI30 secInterval timek4Number of hash functionsp0,1The probability of an attacker eavesdrops on passwordsAs a comparison, we also implement Lamport’s hash chain with 4 kinds of hash functions, respectively. We evaluate the following time: mobile device setup time, average password generation time (mobile device), and average verification time (server). Table2 shows the results.Table 2
Experiment result.
Setup time (seconds)Average password generation time (seconds)Average verification time (milliseconds)MD50.960.511.30SHA-12.211.082.40SHA-28.343.369.02BLAKE2b8.723.594.80Ours7.742.995.1As shown in Table2, the MD5 and SHA-1 hash functions have better performance, while it is not a good choice to construct the Lamport’s hash chain because both of them are not secure enough [20, 21]. Our solution has the best computational performance on a mobile device while ensuring security. And the server only takes several milliseconds to verify the password which is acceptable in general. More experimental results can be obtained through online resources (https://github.com/qinglong-huang/hash_chains_experiments).Both theoretical analyses in Section4 and simulation experiments that we performed demonstrate that the hash chain scheme proposed in this paper is still harder to invert. Therefore, our scheme has better performance on computation and security.


## 6. Conclusion

In this paper, a novel construction of hash chain was presented, and a TOTP system based on this construction was designed for mobile device authentication. This system could be easily employed by some lightweight authentication schemes to ensure forward security or be applied as a second-factor authentication method replacing SMS-based authentication for mobile devices. We gave a formal security analysis regarding the difficulty of inverting the hash chain and demonstrate that the attacker inverting the hash chain inT queries is OT/kn at most. Besides, we discussed several situations that may reduce its security when the selection of hash function changes. Finally, we implemented the scheme on a smartphone, and the simulation result showed that even if an attacker can eavesdrop on every password; the probability that she/he uses these invalid passwords to guess ord successfully is not higher than the theoretical value. Therefore, our scheme met the higher security requirement in mobile device authentication.



---

*Source: 8888679-2020-12-18.xml*