# Polynomial-Based Google Map Graphical Password System against Shoulder-Surfing Attacks in Cloud Environment

Authors: Zhili Zhou; Ching-Nung Yang; Yimin Yang; Xingming Sun
Journal: Complexity
 (2019)

---

## Abstract

Text password systems are commonly used for identity authentication to access different kinds of data resources or services in cloud environment. However, in the text password systems, the main issue is that it is very hard for users to remember long random alphanumeric strings due to the long-term memory limitation of the human brain. To address this issue, graphical passwords are accordingly proposed based on the fact that humans have better memory for images than alphanumeric strings. Recently, a Google map graphical password (GMGP) system is proposed, in which a specific location of Google Map is preset as a password for authentication. Unfortunately, the use of graphical passwords increases the risk of exposing passwords under shoulder-surfing attacks. A snooper can easily look over someone’s shoulder to get the information of a location on map than a text password from a distance, and thus the shoulder-surfing attacks are more serious for graphical passwords than for text passwords. To overcome this issue, we design a polynomial-based Google map graphical password (P-GMGP) system. The proposed P-GMGP system can not only resist the shoulder-surfing attacks effectively, but also need much fewer challenge-response rounds than the GMGP system for authentication. Moreover, the P-GMGP system is extended to allow a user to be authenticated in cloud environment effectively and efficiently.


---

## Body

## 1. Introduction

In modern digital life, people cannot avoid to use passwords for identity authentication. Recently, the emerging technologies such as cloud computing [1–3] and big data processing [4–12] develop very rapidly. Under this background, the password systems play more and more important roles to allow legal users to access different kinds of data resource or service in cloud environment. Most traditional password authentication systems use the combination of alphanumeric strings such as numbers, symbols, and mixed-case letters as passwords, i.e., text passwords. To resist brute force or random guessing attacks, users usually adopt long random alphanumeric strings as strong text passwords, but these strong passwords are hard to remember due to the long-term memory limitations of the human brain. Thus, many users tend to choose simple passwords that are easy to remember, but they will be easily cracked by malicious attackers. Therefore, it is quite difficult to achieve a good trade-off between passwords’ strength and memorability in text password authentication systems.Due to the fact that humans have better memory for images over alphanumeric strings, the graphical password systems have been proposed accordingly to address the issues of text password systems. In the literature, there are two well-known kinds of graphical password systems, i.e., pass-points graphical password (PPGP) systems [13, 15–18] and cued click-points graphical password (CCPGP) systems [19–25]. In the PPGP systems, users click a sequence of preset points on a picture as password for the registration and login processes, as shown in Figure 1. Actually, it is harder to remember a set of points than a single point on a picture. Therefore, instead of using only one picture, the CCPGP systems have been proposed to use a series of pictures and users only need to click one point on each picture. After clicking a point on a picture, the next picture will appear according to the point clicked on the previous picture, as shown in Figure 2. However, CCPGP systems need to store a large number of pictures in the database. Recently, Spitzer et al. [26] integrated application programming interface (API) of Google Map into CCPGP to propose a Google map graphical password (GMGP) system. Because Spitzer et al.’s GMGP system uses online Google Map services, it does not need additional storage space for storing a large number of pictures.Figure 1
Selection of a sequence of points on a single picture in the PPGP system [13]. The numbers shown on the image mean the orders of clicks.Figure 2
Selection of a sequence of points on a picture set in the CCPGP system [14].However, both text passwords and graphical passwords are compromised by shoulder-surfing attacks. The shoulder-surfing attacks will be more serious for graphical passwords than for text passwords since a snooper can easily get the information of a location of map than a text password from a distance. In this work, we design a polynomial-based Google map graphical password (P-GMGP) system against shoulder-surfing attacks. The proposed P-GMGP system not only resists the shoulder-surfing attacks effectively, but also significantly reduces time complexity of authentication compared to Spitzer et al.’s GMGP system.In cloud environment, a user usually needs to access different kinds of services or data resources from multiple servers. The proposed P-GMGP system can be easily extended to allow a user to be authenticated byM servers simultaneously. Thus, the extended P-GMGP system can be applied successfully in cloud environment.The rest of this paper is organized as follows. Section2 introduces the previous work. The motivation and contributions are introduced in Section 3. The proposed P-GMGP system and the extended P-GMGP system are described in Section 4. Conclusions are drawn in Section 5.


## 2. Previous Work

Spitzer et al.’s GMGP [26] adopted Google Map API into CCPGP, so that it does not require a huge storage space for storing pictures. Instead of receiving a natural picture, users will receive a Google Map from the server in each layer. Consider a seven-layer Spitzer et al.’s GMGP, where a Google Map in each layer is subdivided into 256 grids. Seven layers provide 2567 = 256 possible choices, and thus the GMGP system has the same security strength as a DES algorithm with a 56-bit key. To pass authentication, users should correctly click a set of grids on Google Maps. Because a user has the knowledge of the password point, he can easily select a specific grid that includes this password point. After clicking the selected grid on the map, Spitzer et al.’s GMGP will zoom out (enlarge) this grid and display this enlarged Google Map on next layer. By selecting the correct grids in all seven layers (note: every grid in each layer should include the password point), users can pass the authentication successfully. Figure 3 illustrates the login/authentication process of the GMGP system.Figure 3
The login process by selecting a grid on each layer of Google Map in the GMGP system [26].Denote the longitude and latitude of password pointP as xP,yP and the longitude and latitude of response point Ri as xi,yi in the ith layer, where 1≤i≤n and xi,yi belong to the grid Gi∈1,256. The following briefly describes registration and login/authentication phases for an n-layer Spitzer et al.’s GMGP system.


### 2.1. Registration Phase

In this phase, a user (U) with their identifier IDU applies for a login account to the verification server (V). To achieve secure communication, the password points and the response points are sent via a Hypertext Transfer Protocol Secure (HTTPS) channel.Step (1). U chooses a password point P=xP,yP which is easy to rememberStep (2). U sends the registration request IDU,P to V via a secure channelStep (3). V stores the user’s ID and the longitude and latitude of the password point IDU,P in the database


### 2.2. Login/Authentication Phase

In this phase,U tries to login to V and V verifies U.Step (1). U starts login by sending his identifier IDU to V.Step (2). After receiving IDU, V generates an arbitrarily large Google Map Mi including P, where 1≤i≤n, and then sends Mi to U. If 1≤i≤n−1, repeat steps (3-1)∼(3-3).Step (3-1). After receiving the map Mi, by the knowledge about P, U chooses a response point Ri=xi,yi in the grid Gi where the point P is located. Then, the user sends Ri to V.Step (3-2). After receiving Ri, V determines Gi by Ri and Mi.Step (3-3). V zooms out the map in grid Gi to generate the next map Mi+1, and then sends Mi+1 to U.Step (3-4). For the last layer (i.e., i=n), U chooses a response point Rn=xn,yn in the grid Gn where the point P is located, and then sends Rn to V.Step (4). V verifies whether every grid in the corresponding layer includes the password point, i.e., P∈?Gi for 1≤i≤n.Step (5). If all the verifications pass, the login/authentication is successful.


## 2.1. Registration Phase

In this phase, a user (U) with their identifier IDU applies for a login account to the verification server (V). To achieve secure communication, the password points and the response points are sent via a Hypertext Transfer Protocol Secure (HTTPS) channel.Step (1). U chooses a password point P=xP,yP which is easy to rememberStep (2). U sends the registration request IDU,P to V via a secure channelStep (3). V stores the user’s ID and the longitude and latitude of the password point IDU,P in the database


## 2.2. Login/Authentication Phase

In this phase,U tries to login to V and V verifies U.Step (1). U starts login by sending his identifier IDU to V.Step (2). After receiving IDU, V generates an arbitrarily large Google Map Mi including P, where 1≤i≤n, and then sends Mi to U. If 1≤i≤n−1, repeat steps (3-1)∼(3-3).Step (3-1). After receiving the map Mi, by the knowledge about P, U chooses a response point Ri=xi,yi in the grid Gi where the point P is located. Then, the user sends Ri to V.Step (3-2). After receiving Ri, V determines Gi by Ri and Mi.Step (3-3). V zooms out the map in grid Gi to generate the next map Mi+1, and then sends Mi+1 to U.Step (3-4). For the last layer (i.e., i=n), U chooses a response point Rn=xn,yn in the grid Gn where the point P is located, and then sends Rn to V.Step (4). V verifies whether every grid in the corresponding layer includes the password point, i.e., P∈?Gi for 1≤i≤n.Step (5). If all the verifications pass, the login/authentication is successful.


## 3. Motivation and Contributions

In Spitzer et al.’s GMGP, the response point is sent by the plaintext type via a secure channel, i.e., a HTTPS channel. Generally, HTTPS can be resistant to replay attacks. Thus, users can use the same password point in each login/authentication phase and do not need to consider the replay attacks.However, using the same password point may lead to the increase of risk of exposing password under shoulder-surfing attacks. In fact, the shoulder-surfing attacks are usually more serious for graphical password than for text password since a snooper can look over someone’s shoulder to get the information of a location on map more easily than a text password from a distance. Although then-layer Spitzer et al.’s GMGP system needs n challenge-response rounds in login/authentication phase, there is an easy way to steal login information just from the last round. The reasons are given below.Because the mapMi+1 is enlarged from the grid Gi in the previous map Mi and thus Mi+1=Gi, the grids have the following property, i.e., Gi+1⊂Gi, 1≤i≤n−1, as shown in the following equation:(1)Gi+1⊂Mi+1⟶Gi+1⊂Gi∵Mi+1=Gi,1≤i≤n−1.Consequently, a snooper could capture the last response pointRn=xn,yn by a direct observation, and thus he knows the grid Gn. By the property Gi+1⊂Gi and the knowledge of Gn, 1≤i≤n−1, attackers can know the correct grids to send the corresponding response points in all layers to pass the authentication.To resist the shoulder-surfing attacks, the user should not directly expose any knowledge of the password point when they try to login to the server. To this end, motivated by the theory of zero-knowledge proof, we propose a polynomial-based Google map graphical one-time password (P-GMGP) system. In this system, instead of directly clicking the password point, the user clicks a point on the straight line (i.e., one-degree polynomial) generated by connecting the password point and a challenge point to pass the authentication. Since the attackers hardly know any information of the password point from the clicked point in the user’s login phase, it is possible for the proposed system to resist the shoulder-surfing attacks. Moreover, the password point used in the proposed system is a one-time password, which can further improve the security.In addition, another flaw of Spitzer et al.’s GMGP is that then-layer Spitzer et al.’s GMGP system needs n challenge-response rounds for authentication since the user needs to click a correct point on each of n maps in different levels. Thus, the authentication process is time-consuming especially for large n. On the contrary, in the proposed P-GMGP system, the user only needs to click one point on a line, and thus the system can reduce n challenge-response rounds to a single round to speed up the authentication.We also consider the application scenarios of cloud environment. Suppose that a cloud service provider builds a multiserver system, and these servers may collaborate to provide various services or data resources to the clients. When a user needs to login to multiple servers (sayM servers) to get services or data resources, the user should login M times in Spitzer et al.’s GMGP system. On the contrary, the proposed P-GMGP system can be easily extended to allow the user to be authenticated by M servers, simultaneously, which will significantly reduce the authentication cost compared to Spitzer et al.’s GMGP system. Therefore, the extended P-GMGP system is suitable for cloud environment.


## 4. The Proposed P-GMGP and Extended P-GMGP Systems

### 4.1. P-GMGP

Our design concept is based on one-degree polynomial (i.e., a straight line). The proposed P-GMGP system can resist shoulder-surfing attacks effectively. The registration phase of the P-GMGP system is the same as that of Spitzer et al.’s GMGP system. Thus, we only show the login/authentication phase. The operation byU and the operation with the help of computing device (say smartphone S) are separated to more clearly understand the process.


#### 4.1.1. Login/Authentication Phase

In this phase,V sends a challenge point C=xC,yC and U responds a response point R for login.Step (1). U starts login by sending his identifier IDU to V.Step (2). After receiving IDU, V randomly selects a challenge point C and uses current timestamp T, and then sends {C, T} to U.Step (3). By receiving {C, T}, S determines a straight line L from two points, C and the shifted password point P′=xP′,yP′, where xP′=HxP,T and yP′=HyP,T, and shows this line L on screen.Step (4). U randomly selects a response point R=xR,yR on the line L and sends R to V.Step (5). V verifies whether R is on L or not (note: because V has the information of C, P, and T, it can determine the line L). If the verification passes, the authentication is successful.As we know, any two points will determine a straight line (i.e., one-degree polynomial), while a straight line contains infinite points theoretically. The proposed P-GMGP is based on the following Lemma.Lemma 1.
Suppose that any three distinct pointsP1, P2, and P3 in a plane are on a straight line (one-degree polynomial). For the straight line drawn by connecting P1 and P2, one knowing the point P3 can verify whether P3 is on the line. If others do not have information of P3, they cannot know P3 from the line.Proof.
The two pointsP1 and P2 can determine a line represented by a one-degree polynomial fx=a0+a1x. One can use the coordinates of P3=x3,y3 to determine whether P3 is on the line by checking y∈?a0+a1x3. On the other hand, because a straight line contains an infinite set of points theoretically, others cannot know the point P3 from the straight line fx=a0+a1x.Theorem 1.
The proposed P-GMGP is a one-time password scheme. Also, attackers cannot get the password point from the intercepted point, challenge point, and response point.Proof.
Denote the challenge point, the response point, the shifted password point, and the line asCi, Ri, Pi′, and Li for the current timestamp Ti, respectively. For the different timestamps TiandTj, where Ti≠Tj, we have different lines.
(i.e.,Li≠Lj). Thus, the response points are not static. From Step (2)∼Step (4), the points Ci, Ri, and Pi′ are on the straight line Li. From Lemma 1, we can conclude that V can verify whether Ri is on the line, and meanwhile attackers cannot obtain information about Pi′ from the line. As shown in Figure 4, the intercepted point of Li and Lj is just a normal point on Li and Lj rather than the password point Pi′. Moreover, because a straight line theoretically has an infinite set of points, we cannot reveal any information of Pi′ and Pi′ from the intercepted point. Even though attackers obtain Ci and Ri, where 1≤i≤n, from the above description, they have no information of Pi′=xPi′,yPi′. Also, the coordinates of password point are protected by hash function, i.e., xPi′=HxP,Ti and yPi′=HyP,Ti, attackers cannot get the original password point P=xP,yP.
Basically, the security of our P-GMGP is based on two factors: (i) infinite points theoretically contained in a line, which does not expose the shifted password points and (ii) the one-way property of cryptographic hash functionsH(·), which could resist severe collision attacks and preimage attacks [27]. By factor (i), attackers cannot guess the shifted password points from the lines. Even though attackers have the shifted password points (note: it is impossible), they still have no information of the original password point due to the one-way hash function in factor (ii).
It is worth noting that, since it is hard for some users to exactly click points on a line in practice, we set a tolerant distanceTD=100m to improve the usability of the proposed P-GMGP system, so that the user can easily pass the authentication by clicking any point within the tolerant distance TD=100m to the line. Moreover, although an infinite number of points are contained in a line theoretically, that is not true in a line drawn on Google Map. Therefore, in practice, the probability that attackers can successfully guess the shifted password points from the line can be computed by(2)PG≈AreaRAreaP=π×TD2L×2TD,where AreaR means the area of the region on which the user can click any point to successfully pass the authentication and AreaP means the area of the possible region in which the response points are located in Google Map. As the tolerant distance TD=100m is used in the proposed P-GMGP system and the length of line drawn on the whole Google Map is usually very large, by equation (2), the probability PG is equal to a very small value. That means it is still very hard for attackers to successfully guess the shifted password points from the line.
Another advantage of P-GMGP is to speed up the authentication process. When using ann-layer GMGP system, a user should select n response points in n challenge-response rounds in the login/authentication phase. As shown in Step (4) in the proposed P-GMGP system, the user only needs to send one response point in a single round.Figure 4
Diagrammatical representation of password point, shifted password points, and challenge and response points for different timestamps in the P-GMGP system.


### 4.2. Extended P-GMGP

Also, we consider how to efficiently login toM servers (say V1, V2, …, VM) to get services or data resources in cloud environment. By using M-degree polynomial instead of one-degree polynomial, we can easily extend the P-GMGP system to allow a user to be authenticated by M servers, simultaneously. The registration process of the extended P-GMGP system is the same as that of the P-GMGP system. After registration, users have M password points PVm=xPVm,yPVm for the M servers Vm, 1≤m≤M, respectively. The modified login/authentication phase is described below.


#### 4.2.1. Login/Authentication Phase

In this phase, a representative server of theseM servers sends a challenge point C and U selects a response point R for the login.Step (1). U starts login process by sending the login request IDU,IDV1,IDV2,…, IDVM to a representative server (say V1). Note that V1 has to collect all shifted password points from the other verification server PVm′=HxPVm,T,HyPVm,T, 2≤m≤M.Step (2). After receiving IDU,IDV1,IDV2,…,IDVM, V1 randomly selects a challenge point C=xC,yC and uses the current timestamp T, and then sends {C, T} to U.Step (3). By receiving {C, T}, S determines a curve line Ω (M-degree polynomial) from (M + 1) points, C and M shifted password points PVm′=HxPVm,T,HyPVm,T, 1≤m≤M. Then, it shows this curve line Ω on screen.Step (4). U selects a response point R=xR,yR on Ω and sends R to V1.Step (5). V1 verifies whether R is on Ω or not (Note: because V1 has C and all shifted password points, it can determine Ω). If the verification passes, the authentication is successful.The following lemma and theorem for the extended P-GMGP are similar to Lemma 1 and Theorem 1 for P-GMGP, respectively. By using the same argument, they can be easily proved.Lemma 2.
Suppose that any (M + 2) distinct points P1, P2,…, and PM+2 in a plane are on a curve line Ω (M-degree polynomial). By public (M + 1) points (say P1∼PM+1), one knowing the point PM+2 can easily verify whether PM+2 is on the curve line Ω. If one does not have the information of PM+2, they cannot know the point PM+2 from the curve line Ω.Theorem 2.
The extended P-GMGP is a one-time password scheme. Attackers cannot get the password point from intercepted points and challenge and response points. Also, servers can verify whether the user hasM passwords simultaneously PVm=xPVm,yPVm, 1≤m≤M.For the caseM=2, Figure 5 shows the password points, shifted password points, and challenge and response points for different timestamps in the extended P-GMGP system. Like the P-GMGP system, the security is also based on the two factors mentioned above. The password points PV1 and PV2 are not on the parabolic curves Ωi and Ωj; according to factor (ii), the password points are shifted and protected by hash function. Also, attackers cannot know the information of the shifted password points Pi,V1′, Pi,V2′, Pj,V1′, and Pj,V2′; according to factor (i), infinite points are theoretically contained in a line. Thus, the extended P-GMGP system has high security. Additionally, the servers can verify whether the user has M passwords PVm=xPVm,yPVm, 1≤m≤M, simultaneously, by checking if R is on Ω or not.Figure 5
Diagrammatical representation of password point and challenge and response points for different timestamps in the extended P-GMGP whenM = 2.


### 4.3. Discussion

#### 4.3.1. Entering Response Point with the Help of Smartphone

In Spitzer et al.’s GMGP system, with the help of Google Map functions (locating, sizing, zooming, and panning via Google Maps API), users can personally select a response point according to the knowledge about password point. In the proposed P-GMGP system, after receiving the challenge point, we need the smartphoneS to generate the M-degree curve (note: users can check whether the curve generated by smartphone is correct or not because he knows the password points). Then, he chooses any one point on the line as a response point.


#### 4.3.2. Compatibility of the P-GMGP System and the Extended P-GMGP System

Actually, the two password schemes are compatible. Users can login to multiple servers one by one. Also, they can login to any set of multiple servers, simultaneously. The login/authentication processes of the two systems are very similar, and the only difference is that users choose a response point on a straight line (forM = 1) and a curve line (for M ≥ 2).


#### 4.3.3. Single-Round Authentication

Ann-layer Spitzer et al.’s GMGP system needs n challenge-response rounds for authentication. The proposed P-GMGP system only sends a response point on a straight line in a single round, and this will speed up the authentication process. By the extended P-GMGP system, even authenticating by M servers, the user still needs to send one point on a curve line in one round.


#### 4.3.4. Comparison among Different Graphical Password Systems

We also make comparison among the GMGP system, P-GMGP system, and extended P-GMGP system, which is summarized in Table1. From this table, the proposed two systems, i.e., the proposed P-GMGP system and its extended version can resist the shoulder-surfing attacks effectively, while the CCPGP and GMGP systems cannot. Moreover, the proposed two systems only need a challenge-response round in login phase, which is much less than the CCPGP and GMGP systems. The extended GMGP system can allow a user to login to multiple servers, simultaneously, while the others cannot. Finally, since the CCPGP system needs to store a large number of pictures for authentication, it has high storage load. On the contrary, the GMGP, P-GMGP, and extended P-GMGP systems use the online Google Maps, and thus they have no storage load for storing pictures.Table 1
The comparison among different graphical password systems.
CCPGP
GMGP
P-GMGP
Extended
Resistance to the shoulder-surfing attacks
No
No
Yes
Yes
Number of challenge-response rounds
n
n
1
1
Login to multiple servers, simultaneously?
No
No
No
Yes
Storage load
Large number of pictures
No need
No need
No need


## 4.1. P-GMGP

Our design concept is based on one-degree polynomial (i.e., a straight line). The proposed P-GMGP system can resist shoulder-surfing attacks effectively. The registration phase of the P-GMGP system is the same as that of Spitzer et al.’s GMGP system. Thus, we only show the login/authentication phase. The operation byU and the operation with the help of computing device (say smartphone S) are separated to more clearly understand the process.


### 4.1.1. Login/Authentication Phase

In this phase,V sends a challenge point C=xC,yC and U responds a response point R for login.Step (1). U starts login by sending his identifier IDU to V.Step (2). After receiving IDU, V randomly selects a challenge point C and uses current timestamp T, and then sends {C, T} to U.Step (3). By receiving {C, T}, S determines a straight line L from two points, C and the shifted password point P′=xP′,yP′, where xP′=HxP,T and yP′=HyP,T, and shows this line L on screen.Step (4). U randomly selects a response point R=xR,yR on the line L and sends R to V.Step (5). V verifies whether R is on L or not (note: because V has the information of C, P, and T, it can determine the line L). If the verification passes, the authentication is successful.As we know, any two points will determine a straight line (i.e., one-degree polynomial), while a straight line contains infinite points theoretically. The proposed P-GMGP is based on the following Lemma.Lemma 1.
Suppose that any three distinct pointsP1, P2, and P3 in a plane are on a straight line (one-degree polynomial). For the straight line drawn by connecting P1 and P2, one knowing the point P3 can verify whether P3 is on the line. If others do not have information of P3, they cannot know P3 from the line.Proof.
The two pointsP1 and P2 can determine a line represented by a one-degree polynomial fx=a0+a1x. One can use the coordinates of P3=x3,y3 to determine whether P3 is on the line by checking y∈?a0+a1x3. On the other hand, because a straight line contains an infinite set of points theoretically, others cannot know the point P3 from the straight line fx=a0+a1x.Theorem 1.
The proposed P-GMGP is a one-time password scheme. Also, attackers cannot get the password point from the intercepted point, challenge point, and response point.Proof.
Denote the challenge point, the response point, the shifted password point, and the line asCi, Ri, Pi′, and Li for the current timestamp Ti, respectively. For the different timestamps TiandTj, where Ti≠Tj, we have different lines.
(i.e.,Li≠Lj). Thus, the response points are not static. From Step (2)∼Step (4), the points Ci, Ri, and Pi′ are on the straight line Li. From Lemma 1, we can conclude that V can verify whether Ri is on the line, and meanwhile attackers cannot obtain information about Pi′ from the line. As shown in Figure 4, the intercepted point of Li and Lj is just a normal point on Li and Lj rather than the password point Pi′. Moreover, because a straight line theoretically has an infinite set of points, we cannot reveal any information of Pi′ and Pi′ from the intercepted point. Even though attackers obtain Ci and Ri, where 1≤i≤n, from the above description, they have no information of Pi′=xPi′,yPi′. Also, the coordinates of password point are protected by hash function, i.e., xPi′=HxP,Ti and yPi′=HyP,Ti, attackers cannot get the original password point P=xP,yP.
Basically, the security of our P-GMGP is based on two factors: (i) infinite points theoretically contained in a line, which does not expose the shifted password points and (ii) the one-way property of cryptographic hash functionsH(·), which could resist severe collision attacks and preimage attacks [27]. By factor (i), attackers cannot guess the shifted password points from the lines. Even though attackers have the shifted password points (note: it is impossible), they still have no information of the original password point due to the one-way hash function in factor (ii).
It is worth noting that, since it is hard for some users to exactly click points on a line in practice, we set a tolerant distanceTD=100m to improve the usability of the proposed P-GMGP system, so that the user can easily pass the authentication by clicking any point within the tolerant distance TD=100m to the line. Moreover, although an infinite number of points are contained in a line theoretically, that is not true in a line drawn on Google Map. Therefore, in practice, the probability that attackers can successfully guess the shifted password points from the line can be computed by(2)PG≈AreaRAreaP=π×TD2L×2TD,where AreaR means the area of the region on which the user can click any point to successfully pass the authentication and AreaP means the area of the possible region in which the response points are located in Google Map. As the tolerant distance TD=100m is used in the proposed P-GMGP system and the length of line drawn on the whole Google Map is usually very large, by equation (2), the probability PG is equal to a very small value. That means it is still very hard for attackers to successfully guess the shifted password points from the line.
Another advantage of P-GMGP is to speed up the authentication process. When using ann-layer GMGP system, a user should select n response points in n challenge-response rounds in the login/authentication phase. As shown in Step (4) in the proposed P-GMGP system, the user only needs to send one response point in a single round.Figure 4
Diagrammatical representation of password point, shifted password points, and challenge and response points for different timestamps in the P-GMGP system.


## 4.1.1. Login/Authentication Phase

In this phase,V sends a challenge point C=xC,yC and U responds a response point R for login.Step (1). U starts login by sending his identifier IDU to V.Step (2). After receiving IDU, V randomly selects a challenge point C and uses current timestamp T, and then sends {C, T} to U.Step (3). By receiving {C, T}, S determines a straight line L from two points, C and the shifted password point P′=xP′,yP′, where xP′=HxP,T and yP′=HyP,T, and shows this line L on screen.Step (4). U randomly selects a response point R=xR,yR on the line L and sends R to V.Step (5). V verifies whether R is on L or not (note: because V has the information of C, P, and T, it can determine the line L). If the verification passes, the authentication is successful.As we know, any two points will determine a straight line (i.e., one-degree polynomial), while a straight line contains infinite points theoretically. The proposed P-GMGP is based on the following Lemma.Lemma 1.
Suppose that any three distinct pointsP1, P2, and P3 in a plane are on a straight line (one-degree polynomial). For the straight line drawn by connecting P1 and P2, one knowing the point P3 can verify whether P3 is on the line. If others do not have information of P3, they cannot know P3 from the line.Proof.
The two pointsP1 and P2 can determine a line represented by a one-degree polynomial fx=a0+a1x. One can use the coordinates of P3=x3,y3 to determine whether P3 is on the line by checking y∈?a0+a1x3. On the other hand, because a straight line contains an infinite set of points theoretically, others cannot know the point P3 from the straight line fx=a0+a1x.Theorem 1.
The proposed P-GMGP is a one-time password scheme. Also, attackers cannot get the password point from the intercepted point, challenge point, and response point.Proof.
Denote the challenge point, the response point, the shifted password point, and the line asCi, Ri, Pi′, and Li for the current timestamp Ti, respectively. For the different timestamps TiandTj, where Ti≠Tj, we have different lines.
(i.e.,Li≠Lj). Thus, the response points are not static. From Step (2)∼Step (4), the points Ci, Ri, and Pi′ are on the straight line Li. From Lemma 1, we can conclude that V can verify whether Ri is on the line, and meanwhile attackers cannot obtain information about Pi′ from the line. As shown in Figure 4, the intercepted point of Li and Lj is just a normal point on Li and Lj rather than the password point Pi′. Moreover, because a straight line theoretically has an infinite set of points, we cannot reveal any information of Pi′ and Pi′ from the intercepted point. Even though attackers obtain Ci and Ri, where 1≤i≤n, from the above description, they have no information of Pi′=xPi′,yPi′. Also, the coordinates of password point are protected by hash function, i.e., xPi′=HxP,Ti and yPi′=HyP,Ti, attackers cannot get the original password point P=xP,yP.
Basically, the security of our P-GMGP is based on two factors: (i) infinite points theoretically contained in a line, which does not expose the shifted password points and (ii) the one-way property of cryptographic hash functionsH(·), which could resist severe collision attacks and preimage attacks [27]. By factor (i), attackers cannot guess the shifted password points from the lines. Even though attackers have the shifted password points (note: it is impossible), they still have no information of the original password point due to the one-way hash function in factor (ii).
It is worth noting that, since it is hard for some users to exactly click points on a line in practice, we set a tolerant distanceTD=100m to improve the usability of the proposed P-GMGP system, so that the user can easily pass the authentication by clicking any point within the tolerant distance TD=100m to the line. Moreover, although an infinite number of points are contained in a line theoretically, that is not true in a line drawn on Google Map. Therefore, in practice, the probability that attackers can successfully guess the shifted password points from the line can be computed by(2)PG≈AreaRAreaP=π×TD2L×2TD,where AreaR means the area of the region on which the user can click any point to successfully pass the authentication and AreaP means the area of the possible region in which the response points are located in Google Map. As the tolerant distance TD=100m is used in the proposed P-GMGP system and the length of line drawn on the whole Google Map is usually very large, by equation (2), the probability PG is equal to a very small value. That means it is still very hard for attackers to successfully guess the shifted password points from the line.
Another advantage of P-GMGP is to speed up the authentication process. When using ann-layer GMGP system, a user should select n response points in n challenge-response rounds in the login/authentication phase. As shown in Step (4) in the proposed P-GMGP system, the user only needs to send one response point in a single round.Figure 4
Diagrammatical representation of password point, shifted password points, and challenge and response points for different timestamps in the P-GMGP system.


## 4.2. Extended P-GMGP

Also, we consider how to efficiently login toM servers (say V1, V2, …, VM) to get services or data resources in cloud environment. By using M-degree polynomial instead of one-degree polynomial, we can easily extend the P-GMGP system to allow a user to be authenticated by M servers, simultaneously. The registration process of the extended P-GMGP system is the same as that of the P-GMGP system. After registration, users have M password points PVm=xPVm,yPVm for the M servers Vm, 1≤m≤M, respectively. The modified login/authentication phase is described below.


### 4.2.1. Login/Authentication Phase

In this phase, a representative server of theseM servers sends a challenge point C and U selects a response point R for the login.Step (1). U starts login process by sending the login request IDU,IDV1,IDV2,…, IDVM to a representative server (say V1). Note that V1 has to collect all shifted password points from the other verification server PVm′=HxPVm,T,HyPVm,T, 2≤m≤M.Step (2). After receiving IDU,IDV1,IDV2,…,IDVM, V1 randomly selects a challenge point C=xC,yC and uses the current timestamp T, and then sends {C, T} to U.Step (3). By receiving {C, T}, S determines a curve line Ω (M-degree polynomial) from (M + 1) points, C and M shifted password points PVm′=HxPVm,T,HyPVm,T, 1≤m≤M. Then, it shows this curve line Ω on screen.Step (4). U selects a response point R=xR,yR on Ω and sends R to V1.Step (5). V1 verifies whether R is on Ω or not (Note: because V1 has C and all shifted password points, it can determine Ω). If the verification passes, the authentication is successful.The following lemma and theorem for the extended P-GMGP are similar to Lemma 1 and Theorem 1 for P-GMGP, respectively. By using the same argument, they can be easily proved.Lemma 2.
Suppose that any (M + 2) distinct points P1, P2,…, and PM+2 in a plane are on a curve line Ω (M-degree polynomial). By public (M + 1) points (say P1∼PM+1), one knowing the point PM+2 can easily verify whether PM+2 is on the curve line Ω. If one does not have the information of PM+2, they cannot know the point PM+2 from the curve line Ω.Theorem 2.
The extended P-GMGP is a one-time password scheme. Attackers cannot get the password point from intercepted points and challenge and response points. Also, servers can verify whether the user hasM passwords simultaneously PVm=xPVm,yPVm, 1≤m≤M.For the caseM=2, Figure 5 shows the password points, shifted password points, and challenge and response points for different timestamps in the extended P-GMGP system. Like the P-GMGP system, the security is also based on the two factors mentioned above. The password points PV1 and PV2 are not on the parabolic curves Ωi and Ωj; according to factor (ii), the password points are shifted and protected by hash function. Also, attackers cannot know the information of the shifted password points Pi,V1′, Pi,V2′, Pj,V1′, and Pj,V2′; according to factor (i), infinite points are theoretically contained in a line. Thus, the extended P-GMGP system has high security. Additionally, the servers can verify whether the user has M passwords PVm=xPVm,yPVm, 1≤m≤M, simultaneously, by checking if R is on Ω or not.Figure 5
Diagrammatical representation of password point and challenge and response points for different timestamps in the extended P-GMGP whenM = 2.


## 4.2.1. Login/Authentication Phase

In this phase, a representative server of theseM servers sends a challenge point C and U selects a response point R for the login.Step (1). U starts login process by sending the login request IDU,IDV1,IDV2,…, IDVM to a representative server (say V1). Note that V1 has to collect all shifted password points from the other verification server PVm′=HxPVm,T,HyPVm,T, 2≤m≤M.Step (2). After receiving IDU,IDV1,IDV2,…,IDVM, V1 randomly selects a challenge point C=xC,yC and uses the current timestamp T, and then sends {C, T} to U.Step (3). By receiving {C, T}, S determines a curve line Ω (M-degree polynomial) from (M + 1) points, C and M shifted password points PVm′=HxPVm,T,HyPVm,T, 1≤m≤M. Then, it shows this curve line Ω on screen.Step (4). U selects a response point R=xR,yR on Ω and sends R to V1.Step (5). V1 verifies whether R is on Ω or not (Note: because V1 has C and all shifted password points, it can determine Ω). If the verification passes, the authentication is successful.The following lemma and theorem for the extended P-GMGP are similar to Lemma 1 and Theorem 1 for P-GMGP, respectively. By using the same argument, they can be easily proved.Lemma 2.
Suppose that any (M + 2) distinct points P1, P2,…, and PM+2 in a plane are on a curve line Ω (M-degree polynomial). By public (M + 1) points (say P1∼PM+1), one knowing the point PM+2 can easily verify whether PM+2 is on the curve line Ω. If one does not have the information of PM+2, they cannot know the point PM+2 from the curve line Ω.Theorem 2.
The extended P-GMGP is a one-time password scheme. Attackers cannot get the password point from intercepted points and challenge and response points. Also, servers can verify whether the user hasM passwords simultaneously PVm=xPVm,yPVm, 1≤m≤M.For the caseM=2, Figure 5 shows the password points, shifted password points, and challenge and response points for different timestamps in the extended P-GMGP system. Like the P-GMGP system, the security is also based on the two factors mentioned above. The password points PV1 and PV2 are not on the parabolic curves Ωi and Ωj; according to factor (ii), the password points are shifted and protected by hash function. Also, attackers cannot know the information of the shifted password points Pi,V1′, Pi,V2′, Pj,V1′, and Pj,V2′; according to factor (i), infinite points are theoretically contained in a line. Thus, the extended P-GMGP system has high security. Additionally, the servers can verify whether the user has M passwords PVm=xPVm,yPVm, 1≤m≤M, simultaneously, by checking if R is on Ω or not.Figure 5
Diagrammatical representation of password point and challenge and response points for different timestamps in the extended P-GMGP whenM = 2.


## 4.3. Discussion

### 4.3.1. Entering Response Point with the Help of Smartphone

In Spitzer et al.’s GMGP system, with the help of Google Map functions (locating, sizing, zooming, and panning via Google Maps API), users can personally select a response point according to the knowledge about password point. In the proposed P-GMGP system, after receiving the challenge point, we need the smartphoneS to generate the M-degree curve (note: users can check whether the curve generated by smartphone is correct or not because he knows the password points). Then, he chooses any one point on the line as a response point.


### 4.3.2. Compatibility of the P-GMGP System and the Extended P-GMGP System

Actually, the two password schemes are compatible. Users can login to multiple servers one by one. Also, they can login to any set of multiple servers, simultaneously. The login/authentication processes of the two systems are very similar, and the only difference is that users choose a response point on a straight line (forM = 1) and a curve line (for M ≥ 2).


### 4.3.3. Single-Round Authentication

Ann-layer Spitzer et al.’s GMGP system needs n challenge-response rounds for authentication. The proposed P-GMGP system only sends a response point on a straight line in a single round, and this will speed up the authentication process. By the extended P-GMGP system, even authenticating by M servers, the user still needs to send one point on a curve line in one round.


### 4.3.4. Comparison among Different Graphical Password Systems

We also make comparison among the GMGP system, P-GMGP system, and extended P-GMGP system, which is summarized in Table1. From this table, the proposed two systems, i.e., the proposed P-GMGP system and its extended version can resist the shoulder-surfing attacks effectively, while the CCPGP and GMGP systems cannot. Moreover, the proposed two systems only need a challenge-response round in login phase, which is much less than the CCPGP and GMGP systems. The extended GMGP system can allow a user to login to multiple servers, simultaneously, while the others cannot. Finally, since the CCPGP system needs to store a large number of pictures for authentication, it has high storage load. On the contrary, the GMGP, P-GMGP, and extended P-GMGP systems use the online Google Maps, and thus they have no storage load for storing pictures.Table 1
The comparison among different graphical password systems.
CCPGP
GMGP
P-GMGP
Extended
Resistance to the shoulder-surfing attacks
No
No
Yes
Yes
Number of challenge-response rounds
n
n
1
1
Login to multiple servers, simultaneously?
No
No
No
Yes
Storage load
Large number of pictures
No need
No need
No need


## 4.3.1. Entering Response Point with the Help of Smartphone

In Spitzer et al.’s GMGP system, with the help of Google Map functions (locating, sizing, zooming, and panning via Google Maps API), users can personally select a response point according to the knowledge about password point. In the proposed P-GMGP system, after receiving the challenge point, we need the smartphoneS to generate the M-degree curve (note: users can check whether the curve generated by smartphone is correct or not because he knows the password points). Then, he chooses any one point on the line as a response point.


## 4.3.2. Compatibility of the P-GMGP System and the Extended P-GMGP System

Actually, the two password schemes are compatible. Users can login to multiple servers one by one. Also, they can login to any set of multiple servers, simultaneously. The login/authentication processes of the two systems are very similar, and the only difference is that users choose a response point on a straight line (forM = 1) and a curve line (for M ≥ 2).


## 4.3.3. Single-Round Authentication

Ann-layer Spitzer et al.’s GMGP system needs n challenge-response rounds for authentication. The proposed P-GMGP system only sends a response point on a straight line in a single round, and this will speed up the authentication process. By the extended P-GMGP system, even authenticating by M servers, the user still needs to send one point on a curve line in one round.


## 4.3.4. Comparison among Different Graphical Password Systems

We also make comparison among the GMGP system, P-GMGP system, and extended P-GMGP system, which is summarized in Table1. From this table, the proposed two systems, i.e., the proposed P-GMGP system and its extended version can resist the shoulder-surfing attacks effectively, while the CCPGP and GMGP systems cannot. Moreover, the proposed two systems only need a challenge-response round in login phase, which is much less than the CCPGP and GMGP systems. The extended GMGP system can allow a user to login to multiple servers, simultaneously, while the others cannot. Finally, since the CCPGP system needs to store a large number of pictures for authentication, it has high storage load. On the contrary, the GMGP, P-GMGP, and extended P-GMGP systems use the online Google Maps, and thus they have no storage load for storing pictures.Table 1
The comparison among different graphical password systems.
CCPGP
GMGP
P-GMGP
Extended
Resistance to the shoulder-surfing attacks
No
No
Yes
Yes
Number of challenge-response rounds
n
n
1
1
Login to multiple servers, simultaneously?
No
No
No
Yes
Storage load
Large number of pictures
No need
No need
No need


## 5. Conclusion

The shoulder-surfing attacks are more serious for graphical passwords than for text passwords, since a snooper can easily get the information of a location on map than a text password from a distance. Moreover, using the same password in the GMGP system may increase the risk of exposing the password under shoulder-surfing attacks. In this work, we have presented the polynomial-based graphical password systems, i.e., the P-GMGP system and its extended version.In the P-GMGP system and the extended P-GMGP system, since users do not need to directly click the password points to pass the authentication, the two systems can resist shoulder-surfing attacks effectively. The security of P-GMGP and extended P-GMGP is based on the two mentioned factors, i.e., the property of line and one-way hash function, and thus the two systems have high security. Also, the user only needs to send one response point in one round for login, and thus the proposed systems need much less authentication time than the GMGP system. In addition, since the extended P-GMGP system allows the user to be authenticated byM servers, simultaneously, it is very suitable for multiserver environment.



---

*Source: 2875676-2019-11-16.xml*