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.

1. Introduction

In modern digital life, people cannot avoid to use passwords for identity authentication. Recently, the emerging technologies such as cloud computing [13] and big data processing [412] 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, 1518] and cued click-points graphical password (CCPGP) systems [1925]. 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.

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 by M servers simultaneously. Thus, the extended P-GMGP system can be applied successfully in cloud environment.

The rest of this paper is organized as follows. Section 2 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.

Denote the longitude and latitude of password point P as and the longitude and latitude of response point Ri as in the ith layer, where and belong to the grid . 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 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 which is easy to rememberStep (2). U sends the registration request to V via a secure channelStep (3). V stores the user’s ID and the longitude and latitude of the password point 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 to V.Step (2). After receiving , V generates an arbitrarily large Google Map including P, where , and then sends to U. If , repeat steps (3-1)∼(3-3).Step (3-1). After receiving the map , by the knowledge about P, U chooses a response point in the grid where the point P is located. Then, the user sends to V.Step (3-2). After receiving , V determines by and .Step (3-3). V zooms out the map in grid to generate the next map , and then sends to U.Step (3-4). For the last layer (i.e., ), U chooses a response point in the grid where the point P is located, and then sends to V.Step (4). V verifies whether every grid in the corresponding layer includes the password point, i.e., for .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 the n-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 map is enlarged from the grid in the previous map and thus , the grids have the following property, i.e., , , as shown in the following equation:

Consequently, a snooper could capture the last response point by a direct observation, and thus he knows the grid Gn. By the property and the knowledge of , , 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 the n-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 (say M 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 by U 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 and U responds a response point R for login.Step (1). U starts login by sending his identifier to V.Step (2). After receiving , 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 , where and , and shows this line L on screen.Step (4). U randomly selects a response point 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 points , , and in a plane are on a straight line (one-degree polynomial). For the straight line drawn by connecting and , one knowing the point can verify whether is on the line. If others do not have information of , they cannot know from the line.

Proof. The two points P1 and P2 can determine a line represented by a one-degree polynomial . One can use the coordinates of to determine whether is on the line by checking . 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 .

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 as , , , and for the current timestamp , respectively. For the different timestamps , where , we have different lines.
(i.e., ). Thus, the response points are not static. From Step (2)∼Step (4), the points , , and are on the straight line . From Lemma 1, we can conclude that V can verify whether is on the line, and meanwhile attackers cannot obtain information about from the line. As shown in Figure 4, the intercepted point of and is just a normal point on and rather than the password point . Moreover, because a straight line theoretically has an infinite set of points, we cannot reveal any information of and from the intercepted point. Even though attackers obtain and , where , from the above description, they have no information of . Also, the coordinates of password point are protected by hash function, i.e., and , attackers cannot get the original password point .
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 functions H(·), 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 distance 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 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 bywhere means the area of the region on which the user can click any point to successfully pass the authentication and means the area of the possible region in which the response points are located in Google Map. As the tolerant distance 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 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 an n-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.

4.2. Extended P-GMGP

Also, we consider how to efficiently login to M 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 for the M servers Vm, , respectively. The modified login/authentication phase is described below.

4.2.1. Login/Authentication Phase

In this phase, a representative server of these M 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 to a representative server (say V1). Note that V1 has to collect all shifted password points from the other verification server , .Step (2). After receiving , V1 randomly selects a challenge point 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 , . Then, it shows this curve line on screen.Step (4). U selects a response point 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 , ,…, and in a plane are on a curve line (M-degree polynomial). By public (M + 1) points (say ), one knowing the point can easily verify whether is on the curve line . If one does not have the information of , they cannot know the point 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 has M passwords simultaneously , .

For the case , 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 and are not on the parabolic curves and ; 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 , , , and ; 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 , , simultaneously, by checking if R is on or not.

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 smartphone S 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 (for M = 1) and a curve line (for M ≥ 2).

4.3.3. Single-Round Authentication

An n-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 Table 1. 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.

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 by M servers, simultaneously, it is very suitable for multiserver environment.

Data Availability

No data were used to support this study.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This work was supported in part by MOST under contracts 108-2634-F-259-001 through Pervasive Artificial Intelligence Research (PAIR) Labs, Taiwan, in part by the National Natural Science Foundation of China under Grant nos. 61972205, 61602253, U1836208, U1536206, U1836110, and 61672294, in part by the National Key R&D Program of China under Grant no. 2018YFB1003205, in part by the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD) fund, and in part by the Collaborative Innovation Center of Atmospheric Environment and Equipment Technology (CICAEET) fund, China.