HK1113525B - Authentication system and method based upon random partial digitized path recognition - Google Patents

Description

Authentication system and method based on random partial digitized path identification

Technical Field

The present invention relates generally to user authentication systems for computers and network security access control systems; and more particularly to improved authentication factors based on what a user knows (what) in client/server network architectures and other architectures.

Background

The most widely used method of user authentication is referred to herein as the standard static password identification (SSPR) algorithm. The SSPR algorithm simply requires the user to enter a username and password for authentication. This is a type of authentication factor of "what the user knows". Other types of authentication factors are less widely used and include "what the user has" (keys) and "what the user is" (fingerprints). The "what the user has" and "what the user is" types of authentication factors require specialized hardware devices on the input terminal, such as card readers, tokens, fingerprint sensors, etc., and are therefore generally much more expensive and difficult to implement than "what the user knows" types. The type of authentication factor by which the user knows what is limited by the ability of the individual to remember the relevant factor. For example, a typical user selects the SSPR password within a "comfort level" of memory complexity, typically in the range of 1 to 7 (or 8) alphanumeric characters long. Often, passwords are simple words or integers (e.g., "patriots," "London," 11223344, etc.). Technological advances and the need for contemporary industry social security have led to at least two serious problems associated with password security in typical SSPR, including:

1. an intruder may employ a brute force technique (known as a dictionary attack) to successively try all the words in the exhaustive list against the password file. Each successive attempted word is encrypted using the same algorithm as used by the hacked logon program. Dictionary attacks, whether directed to hashed passwords intercepted on the communication line or directly on the password entry device, allow the password to be easily reset.

2. Another problem is password combining capability with respect to typical passwords within a "comfort level" of complexity for most users. For large organizations, a range of passwords within these comfort levels may not be sufficient.

Typical enterprise-level solutions (enterprise-wide IT department policy) that consider items 1 and 2 above require users to have at least 4-5 (or more) case-specific alphanumeric passwords that should not be simple words (but, for example: 1patRIOT, Lon7Don, etc.). This approach results in multiple password resets by users who forget or lose their passwords, which has become a very expensive and cumbersome difficulty for organizations and businesses (or service companies) to strive for higher security levels.

Objective considerations show that the minimum number of characters in a password is limited by at least two factors: the necessary combinatorial capability and high sensitivity to combinatorial attacks. The maximum number of characters in a static password is limited by the user's "comfort level" for memory. Finally, in the range of 4-8 alphanumeric characters (characters case-insensitive) or 3-7 alphanumeric characters (characters case-insensitive). Until recently, organizations and businesses (or service companies) have suffered from these well-known deficiencies that result from the relatively simple, low-cost, and widely used SSPR user authentication techniques.

At the same time, emerging requirements are forcing the security industry (authentication-authorization-accounting (AAA or 3A) procedures, encryption, enterprise software, financial service providers, etc.) to reconsider SSPR based on user authentication techniques:

1. the first problem is that the increase in data processing capability of ASIC chips makes the combinatorial attack of breaking static passwords much more efficient. A conceivable defensive route may be to increase the length of the static password. Unfortunately, as we have discussed, this capability has been greatly limited by the "comfort level" of the user. Thus, SSPR-based security systems appear to be dilemma because the minimum password length (3-4 alphanumeric characters) must be increased to withstand more and more efficient combinatorial attacks, while the overall static password length has to be kept constant and limited to the range of 6-7 alphanumeric characters due to human memory limitations.

2. Furthermore, a number of security issues arise in large-scale systems, such as deficiencies of state/national voting systems, credit card fraud by health data banks and financial services organizations, privacy and security breaches, vulnerabilities to Microsoft 2000 and XP operating systems, etc., which make it necessary to enhance or rebuild large-scale security systems. The evolution of these systems will eventually require a static password combination capability that may be much higher than the organizational/enterprise level. Assuming that there are approximately 1000 million users on a state level and approximately 1 million users throughout a country, a password having at least 5 characters is required for a state-wide system, and a password having at least 6 characters is required for a nationwide password-based security system (assuming that the characters are case-insensitive, or 4 and 5 characters are case-insensitive, respectively). As processing power in the hands of hackers increases, the minimum password size of the security system approaches or exceeds the "comfort level".

3. Once national security systems, databases and various markets are internationally integrated (say US and EU), the number of users requiring unique passwords is increased to the point that the combining capabilities of these systems will require at least 6 alphanumeric characters (case-differentiated passwords) or 7 (for character-case-indistinguishable systems). This is already at the boundary of the "comfort level" of the user.

Therefore, SSPR is reaching the limits of its practical application for large-scale static password-based security systems. This can also explain the serious concerns recently given to alternative high security user authentication methods such as biometrics, tokens and smart cards. Among these techniques, biometrics is the only true user authentication method. Other techniques may be part of the user authentication system, but are not sufficiently unique.

Unfortunately, biometrics are generally more expensive and difficult to deploy than SSPR-based systems. Moreover, due to religious and cultural concerns, the public has a number of conflicts with biometric authentication methods. Another strong concern is the security of private biometric data in the case of using biometrics. Once stolen, the biometric data can be permanently reused to impersonate the person whose data was taken.

B. Attacks against SSPR-based systems

In addition to the several problems listed above, static password technology is particularly vulnerable to a variety of attacks, for which the scope of protection is limited. Some possible attacks and defenses against attacks include the following:

1. password guessing

● an intruder attempts to log in with a real username while password guessing based on the user's personal knowledge.

● defense — automatically block sessions after several failed attempts; possible account invalidations or forced password resets.

2. Login session video

● to aid in covert viewing. Video and/or audio recording can be made from a significant distance at any time, threatening the secret password or PIN entered by a computer or network online user at a public location (ATM machine; customers at point of sale; internet terminals provided at various meetings, cafes, libraries; employees sharing a large office, their desktop computer terminals within each person's line of sight, and other locations).

● defense-there is no standard protection technique other than keeping vigilance.

3. Peeping screen (shoulder surfing)

● an intruder next to the legitimate user views the password entry.

● defense — there is no standard protection technique except that a loopback dummy character and a different number of characters are displayed.

4. Interplay consummation (Social Engineering)

● an intruder pretends to be an administrator or a real user requesting password recovery/reset.

● defend against a no recovery/reset policy.

5. Trojan horse program

● hide the downloaded software from looking like a standard login session but instead collects the username and password.

● defense — there may be some protection for alert users and administrators with antivirus protection and intrusion detection software.

6. Keystroke monitoring

● the secretly downloaded software keeps a record of all keystrokes.

● defense — if the employer is the originator of the attack, the employee is not defendable; legal protection is one possible option.

7. Fraud high hand

● can recognize the password far from the actual user with special hearing/viewing skills/training.

● defense-there is no standard protection technique other than keeping vigilance.

8. Network exploration (sniffing)

● the intruder records the username and password transmitted on the communication line.

● defense — encryption protocol: kerberos, SSL, IPsec; challenge response (challenge response), using a token or a one-time password of the smart card; the biometric replaces the password.

9. Keyboard buffer memory probing

● some desktop operating systems do not have hardware protection for software that an intruder copies passwords from a keyboard buffer.

● defense — there is no standard protection other than to do hardware protection at the microprocessor level.

10. Password file stealing

● each username has a password entry in hashed form that can be read.

● defense — using needleham-Guy algorithm: each password is an encryption key to encrypt a hash of itself.

All of the above attacks can be divided into three different categories: communication line attacks (8, dictionary attacks), attacks on input/output devices (1, 2, 3, 4, 5,6, 7, 9) and database attacks (10).

C. Enhanced safety requirements

As the attack list above indicates, SSPR security techniques are vulnerable to well-known security breaches. Unlike other authentication factors based on "what the user has" (e.g., a hardware token) or "what the user is" (e.g., biometric features, long phases, fingerprints, face, eye, and voice recognition), SSPR is based on "what the user knows". It is well known that authentication systems based on "what the user knows" are attractive in that they are cheap, user friendly, easy to deploy electronically, and do not require additional hardware, compared to other authentication factors. This is why numerous attempts have been made to improve the SSPR technology and meet the needs of the internet mass trading and e-commerce communities. Several enhanced user authentication security needs include the following:

1. even without encryption, the authentication secrets (e.g., passwords and PINs) shared between the client and server should not be compromised if intercepted by an intruder while transmitting over the communication line.

2. Authentication systems are intended to show strong resilience to attacks on input/output devices (see, e.g., B1-B7, B9).

3. Authentication systems based on "what the user knows" should use secret knowledge shared with the server, which is easier for humans to remember or comparable in difficulty to static passwords. Otherwise, the system has no opportunity to be widely adopted.

4. The client and the server need to perform mutual authentication with each other.

5. The client should be able to be authenticated by the server and access the protected resource from any computer platform on the internet.

6. The authentication system should have zero trace downloaded software on the client computer platform.

7. There is no additional hardware compared to the SSPR technique.

8. Easily and cheaply match any other authentication factor in setting up a "strong authentication" security system (with two or more authentication factors).

9. And the security compatibility with the Web service technology (such as SOAP, SAML, XML, WSDL and the like) oriented to the message.

US 2002/0029341 in Juels; U.S. patent No.6,327,659 to Boroditsky; U.S. patent No.6,332,192 to Boroditsky; US 2001/0039618 to Azuma; U.S. patent No.6,209,104 to Jalili; U.S. patent No.5,664,099 to Ozzie; U.S. patent No.5,608,387 to Davies; U.S. patent No.5,559,961 to Blonder; U.S. patent No.5,428,084 to Baker; U.S. patent No.5,465,084 to Cottrell; and Martino U.S. patent No.5,276,314.

Many of the methods claim to make some improvement toward meeting some of the requirements (1-9) listed above. However, no known method (other than SSPR) is widely accepted by the public and industry. Furthermore, none of the comprehensive security systems and user authentication methods that allow coverage of the entire list of requirements listed above. Therefore, there is a need for an authentication system and method that allows greatly improved practical security against most known attacks on communication lines and data input devices, while ensuring sufficient combining capabilities. Furthermore, the user interface of the new authentication system is required to be easy to use and secure.

Disclosure of Invention

The present invention provides a new Random Partial Digitized Path Recognition (RPDPR) algorithm and authentication system and method built on the algorithm. The RPDPR authentication technique has the positive features of an SSPR-based security system, but at the same time is much more robust in terms of security. RPDPR techniques are very effective against computer data processing dictionary or brute force attacks, password guessing, password file stealing, screensurfing, eavesdropping, video recording, trojan horse program attacks, memory exploration attacks, keystroke monitoring, and network exploration. At the same time, RPDPR provides an "what the user knows" authentication method with a great combinatorial power and remains within the "comfort level" of the user for memory.

The invention is realized by an interactive method for identifying a client. The method is interactive in the sense that the server provides the client with a hint that has been identified by the server, and the client enters data suggested by the hint. Embodiments of the method use a complete pattern comprising a set of data fields storing parameters specifying a digitized path on a reference grid for identification. Further, embodiments of the method use a random partial subset of the complete pattern stored in the server to implement the authentication factor.

According to an embodiment of the method, an ordered set of data fields is stored in a secure memory. The data fields in the ordered set include respective field contents that store coordinates of points on the digitized path on the reference frame. The location of a data field in the ordered set and the contents of the data field specify a point on the digitized path. The server provides a hint, e.g., a location in a random subset of the data fields in the ordered set, to the client over the communication medium, the hint identifying a random partial pattern from the complete pattern stored in the ordered set of data fields. For purposes of clarity, the term "random" as used herein is intended to include pseudo-random.

The server provides the input structure as part of a graphical user interface, for example, displaying a hint. The input structure facilitates entry of data corresponding to the field contents of the location indicated by the hint. For example, in one embodiment, the input structure includes an instance of a representation of a reference frame, such as a rectangular grid. An example of a representation of a reference frame includes a randomized array of indicators occupying locations having coordinates in the reference frame that correspond to coordinates stored in a set of data fields that specify a digitization path. In some embodiments, the indicator displayed in the instance of the reference frame displayed during the authentication session comprises one or more of an alphanumeric character, an image, and a color.

The input structure includes an input field for inserting an indicator from the randomized indicator array. The client satisfies the authentication factor by inserting an indicator from an instance of the reference frame, the indicator being derived from coordinates represented by field contents of data fields in the data set, the data fields specifying the digitization path and having locations along the digitization path specified by the hint. The server generates different instances of the reference frame where the randomized indicator array is varied for each random combination of data field positions on the full digitization path and for different authentication sessions. Thus, a particular indicator corresponds to the field contents of a particular combination of identification coordinates only during one authentication session. The server verifies the indicator with reference to the cue, the stored full pattern, and the instance of the reference frame provided for that particular authentication session. If the input data matches, the authentication is notified of success. Otherwise, the authentication is notified of the failure.

In some embodiments of the invention, the processing involves providing an input structure for account establishment to the client. The input structure may include a graphical user interface provided using an internet browser or thin client software. The user provides the field contents for an ordered subset of the data fields that specify a digitization path on a reference frame.

An embodiment of the present invention includes an initial step of detecting an attempt to access a protected resource in a data network. In response to detection of an attempted access, an authentication process is initiated. After the authentication process is successfully completed, the client is notified of the authentication, allowing access to the protected resource.

Other embodiments of the present invention display an icon during at least one of the first and second prompting and verification steps. The icon has a first state during the prompting, a second state during waiting for verification, and a third state after verification. For example, in one embodiment, the icons include a stop light icon, a red light being displayed during the prompt, a yellow light being displayed during the wait for verification, and a green light being displayed after verification.

Embodiments of the invention include a system for authenticating a client. The system comprises: a data processor comprising an interface to a database and an interface to a data network; and an authentication system program executable by the data processor. The system program includes authentication logic that supports an RPDPR authentication factor to authenticate a client based on client credentials including an account username.

The present invention is also implemented by authentication systems based on client/server architectures and other architectures. In one embodiment, the process extends to authentication servers for a large number of users. In this embodiment, the processing involves maintaining a secure database of user accounts, including a data set of data fields as described above. In the system, attempts to access protected network resources are detected or redirected to a server. The server then conducts an authentication session as described above to allow the client to access the protected resource.

A system implementing the invention includes data processing resources including a processor, memory, and a network interface. Authentication server software executing in the data processing resources implements the process of account establishment and client authentication as described above.

RPDPR-based authentication techniques are as user-friendly, cost-effective, and electronically deployable as standard static password techniques (SSPR). At the same time, with RPDPR-based authentication, the security is much higher compared to SSPR. It allows effective protection against a variety of intrusion attacks on data input devices and on communication lines during data transmission. RPDPR-based authentication techniques are applicable to both hardware and customers, while having scalable security, allowing tradeoffs between cost, traffic requirements, and hardware resources.

Other aspects and advantages of the invention can be seen from the following drawings, detailed description and claims.

Drawings

Fig. 1 shows a client/server architecture implementing a user authentication process based on a random partial digitized path recognition, RPDPR, algorithm according to the present invention.

Fig. 2 is a flow diagram of a basic random partially digitized path identifying RPDPR authentication session according to the present invention.

Fig. 3A through 3F provide various examples of a secret full digitized path selection menu during a login session and a full continuous path with 10 locations for online user setup in support of the RPDPR authentication process in accordance with the present invention.

Fig. 4A through 4F provide various examples of complete discontinuous paths with 10 locations for online user setup that support the RPDPR authentication process during a login session in accordance with the present invention.

Fig. 5 shows a graphical user interface supporting a login process in a random partial path data input state, used in an example of an authentication procedure according to the present invention.

Fig. 6 is a basic architecture diagram of an embodiment of a client/server system according to the present invention, including support for RPDPR authentication processing.

Detailed Description

A detailed description of embodiments of the present invention is provided with reference to fig. 1 to 6.

Fig. 1 illustrates basic communication setup of a representative RPDPR authentication process according to the present invention. The client subsystems 1010 communicate with the server subsystem 1030 over a communication medium, such as a local area network or wide area network communication subsystem 1020. Protected network target 1130 controls access to resources such as a secure website identified by a URL, a link to a secure network, and the like.

To establish access, client subsystem 1010 and server subsystem 1030 execute a pre-authentication session 3040. In pre-authentication session 3040, a user account is established in server subsystem 1030, a username and a secret digitized path represented by an ordered set of data fields are selected by the user and stored in server subsystem 1030. The ordered data set defines a complete pattern (fullpattern) for the user, with data fields having locations in the data set and having respective field contents. For RPDPR, the field contents include a combination of field coordinates on the frame of the reference point. The coordinates define the data field location along the directional digitization path on the reference frame. The location in the data set corresponds to the location (e.g., field number) of the corresponding point on the directional digitization path, with coordinates on the reference frame known to the client. The location in the data set thus indicates these coordinates to the client, and the coordinates can be used to select an indicator to provide to complete a portion of the authentication factor corresponding to the location indicated by the thread (true).

The ordered set of user account information, username, and data fields are stored in a security server database along with other information used during the authentication session. In some embodiments, information supporting additional authentication factors is stored in the database.

To gain access to protected network object 1130, client subsystem 1010 and server subsystem 1030 execute an authentication session 3050 that includes an RPDPR-based client/server interaction communication protocol. A more detailed description of an embodiment of the authentication session 3050 is provided with reference to fig. 2.

According to a basic flow, an authentication session is initiated when a user attempts to reach a protected network target (block 1060). The protected network target redirects the user's attempted access to the authentication server or otherwise detects the attempted access at the authentication server 1030. In one example, the user returns a communication interface including a graphical user interface to the user's browser, including a link to the authentication server 1030, regardless of where the user attempted access using the internet browser (block 1070). The communication interface may be returned by the authentication server or another network resource, for example, by redirection. Through the communication interface, the server prompts the user to enter a username into a field in the graphical user interface (block 1080). The user enters a username, which is returned to the authentication server (block 1090). If the username is valid, the authentication server identifies a random partial subset of data fields from the ordered data set, the field contents and field positions together indicating the coordinates of a set of points that together define a complete digitization path on a reference frame. For example, in one embodiment, there are 10 data fields that comprise the full digitized path, with the starting path field having position 0, the next successive data field having position 1, and so on, until the last data field at the end of the full digitized path has position 9. Then, a random partial subset (clue) identified by the authentication server and provided to the user through the graphical user interface will look like a random set of random number combinations, e.g., 24, 019, 7, 68. The user is prompted to populate input field values corresponding to coordinates in member data fields in the random partial subset of data fields using a graphical user interface (block 4100). In one example, the input field value is selected from an array of indicators located on an instance of the reference frame, the indicators in the array having locations on the instance of the reference frame corresponding to candidate coordinates in the reference frame. The user enters an indicator or other data corresponding to the coordinates of the random partial subset of the digitized path as input field content and the input data is returned to the server (block 4110). If the input data matches the field contents of the random subset, the user is notified of the authentication success, e.g., via a graphical user interface, the protected network object and/or other resources that need to know that the authentication session was successful, such as an authentication and billing system, are notified, and a network connection to the requested protected network object is allowed (block 1120).

Fig. 3A-3F and 4A-4F illustrate how the digitized path is specified for a reference frame to be used as an RPDPR discriminator. In this example, the reference frame includes a reference grid as shown in FIG. 3A. The reference grid 8010 in this embodiment comprises an array of positions (e.g. 8011) which may be defined by coordinates along horizontal and vertical axes 8012, 8013, respectively, as in a rectangular coordinate system. Other reference frames may be organized according to other coordinate systems, such as a polar coordinate system. In the example shown in fig. 3A, position 8011 may be defined by coordinates (6, 3). Fig. 3A shows an example of a reference frame displayed on a user interface, such as during an account setup process, for a user to specify a full digitization path. Thus, the example includes icon 8014 at the intersection of the reference axes, which serves as a button to turn the example on and off. The client may draw (or pick or select) a path on the reference grid using a mouse, keyboard or other input device, or the path may be provided by the server when a particular instance of the set-up algorithm is satisfied.

Fig. 3B-3F illustrate representative full digitization paths that may be created using reference frame 8010. Thus, fig. 3B shows a path 8021 on an example 8020 of a reference grid. The path comprises a set of points starting from the point of coordinates (9, 7). The path proceeds along a straight line, the order of the points being the coordinates (8, 7), (7, 7), (6, 7),. ·, (0, 7). The data set corresponding to the digitization path includes a set of data fields having positions 0 through 9 in the data set (where positions may be represented by field numbers using a data set that includes a linear array of data fields). The data fields at these 10 positions store combinations of coordinates (9, 7) to (0, 7) in order, respectively. In this manner, if the customer knows the path and location of the data fields in the data set, the customer can determine the coordinates stored in the data fields. These coordinates may be used to accomplish the discrimination factors as described below.

Fig. 3C shows the path represented by arrows 8031, 8032, 8033 on the instance 8030 of the reference frame. The path of FIG. 3C includes, in order, the coordinates: (0, 8), (1, 9), (2, 8), (2, 7), (3, 6), (4, 5), (5, 4), (6, 3) and (7, 2). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 3C.

Fig. 3D shows the path represented by arrows 8041, 8042 on the instance 8040 of the reference frame. The path of FIG. 3D includes, in order, the coordinates: (0, 5), (1, 6), (2, 7), (3, 8), (4, 9), (5, 9), (6, 8), (7, 7), (8, 6) and (9, 5). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 3D.

Fig. 3E shows the path represented by arrows 8051, 8052 on the instance 8050 of the reference frame. The path of FIG. 3E includes, in order, the coordinates: (9, 9), (9, 8), (9, 7), (9, 6), (9, 5), (8, 5), (7, 5), (6, 5), (5, 5) and (4, 5). These coordinates are stored in data fields having locations 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 3E.

Fig. 3F shows the path represented by arrows 8061, 8062, 8063, 8064, 8065 on the instance 8060 of the reference frame. The path of FIG. 3F includes, in order, the coordinates: (2, 9), (2, 8), (3, 9), (4, 8), (5, 9), (6, 9) and (6, 8). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 3F.

The digitizing paths shown in fig. 3B through 3F are considered continuous digitizing paths here because all coordinates on the path are adjacent in sequence to other coordinates on the path. For some customers, a continuous path may be easier to remember.

In addition, all representative digitization paths have the same number of points. Using the same number of points on each path facilitates the execution of the RPDPR authentication algorithm, but this is not necessary for the concept of the RPDPR authentication factor for different customers.

Other embodiments of the present invention use discontinuous digitizing paths, such as described with reference to fig. 4A-4F.

Fig. 4A shows discontinuous paths represented by arrows 9011, 9012, 9013 on an instance 9010 of the reference frame. The path of FIG. 4A includes, in order, the coordinates: (0, 0), (1, 1), (2, 2), (7, 2), (8, 1), (9, 0), (9, 6), (9, 7), (9, 8) and (9, 9). A discontinuity in the path occurs between coordinates (2, 2) and (7, 2). Moreover, a discontinuity occurs between the coordinates (9, 0) and (9, 6). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 4A.

Fig. 4B shows discontinuous paths represented by arrows 9021, 9022 on an instance 9020 of the reference frame. The path of FIG. 4B includes, in order, the coordinates: (5, 3), (6, 3), (7, 3), (8, 3), (9, 6), (8, 6), (7, 6), (6, 6) and (5, 6). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 4B.

Fig. 4C shows discontinuous paths represented by arrows 9031, 9032, 9033 and cross 9034 on the instance 9030 of the reference frame. The path of FIG. 4C includes, in order, the coordinates: (0, 0), (1, 0), (2, 0), (9, 1), (9, 2), (9, 9), (8, 9), (7, 9) and (0, 9). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 4C.

Fig. 4D shows discontinuous paths represented by crosses 9041, 9042, 9043, 9044, 9045, 9046, 9047, 9048, 9049, 9059 on the instance 9040 of the reference frame. The path of FIG. 4D includes, in order, the coordinates: (0, 0), (2, 2), (4, 4), (6, 6), (8, 8), (0, 9), (2, 7), (4, 5), (6, 3) and (8, 1). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 4D.

Fig. 4E shows discontinuous paths represented by crosses 9051, 9052, 9053, 9054 and arrows 9055 on the instance 9050 of the reference frame. The path of FIG. 4E includes, in order, the coordinates: (0, 0), (9, 9), (0, 9), (2, 7), (3, 6), (4, 5), (5, 4), (6, 3) and (7, 2). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 4E.

Fig. 4F shows discontinuous paths represented by arrows 9061, 9062, 9063 and cross 9064 on the instance 9060 of the reference frame. The path of FIG. 4F includes, in order, the coordinates: (7, 9), (8, 9), (9, 8), (9, 7), (9, 6), (8, 7), (7, 8), (6, 9) and (8, 8). These coordinates are stored in data fields having positions 0 through 9, respectively, in the data set, and serve as an authentication factor based on the path in fig. 4F.

Fig. 5 illustrates a graphical user interface screen 2090 presented at the beginning of an RPDPR-based authentication session. After the server identifies the username in field 2010, interface 2090 prompts the client to fill in the RPDPR authentication factor. Otherwise, if the username is not accepted by the authentication server, the "random partially digitized path" prompt and its corresponding fields (8040, 8050), field indicator 8030, and second stop light icon 8020 do not appear on screen 2090, and first stop light icon 2110 will turn red to indicate that access is denied (or the username is incorrect). In this example, two stop light icons 2110, 8020 are presented. First stop light icon 2110 turns green after the user's static username is identified. The second stop light icon 8020 appears during data entry of the random partial subset. It appears red before data is entered into the data field or before the login button is indicated. Stop light icon 8020 appears yellow during client/server communication and before input data representing the contents of the fields is accepted. Stop light icon 8020 appears green to notify of successful authentication.

The username entered and accepted may be displayed in username field 2010, whether displayed as plain text or as a sequence of loopback points for security reasons. Each data entry field (e.g., 8040) is presented as a pattern that includes a corresponding number of fields that will constitute a random partial subset of the data set of data fields that are stored by the user. In this example, the user is presented with a plurality of random partial subsets by a set of field position numbers (e.g. 8030), and among the data sets corresponding to, for example, 10 data fields of a digitized path comprising 10 points, a set of field position numbers 27 (position 2 and position 7), a set of field position numbers 049, a field position number 6. Associated with each data entry field in this embodiment is a button 8050, with a corresponding window for entry of the user selected indicator. By clicking on button 8050, a drop down menu 8010 is displayed. The drop down menu 8010 includes an example of a reference grid, as shown in fig. 9A-9F and 10A-10F, in which points on the grid are filled in with a randomized array of indicators. Thus, the indicator on the point with coordinates (4, 5) is the number 5. The server generates a different instance of the indicator array for each instance of the reference grid. In a preferred embodiment, different instances of the indicator array may be randomly or pseudo-randomly generated. Alternatively, a previously generated set of indicator arrays may be used in a random order. In some embodiments, the look and feel of the reference grid is maintained between different sessions, but the array of indicators is changed. In other embodiments, the reference grid may take different forms, so long as the coordinates of the points on the digitized path may be used to identify the locations on the form of the reference grid. Other techniques may be used to variably present the reference grid and the array of indicators in order to enhance the discrimination factor.

The graphical user interface 2090 presents the clue represented by the set of field location numbers (e.g., 8030). The corresponding input field 8040 is presented to the user. The user completes the authentication factor by populating an indicator from a point on a reference grid having coordinates corresponding to a field position number in the set, the field position number identifying a random partial subset of the full path associated with the input field as a clue. Thus, in the input field corresponding to field position number 27, for the full digitization path shown in FIG. 3B, the indicator selected would be the indicator stored at the coordinates in field position number 2 and at the coordinates in field position number 7 in the entire data set. The field position number 2 in the example of fig. 3B stores coordinates (7, 7). The indicator at coordinates (7, 7) is the number 6. The field position number 7 in the example of fig. 3B stores the coordinates (2, 7). The indicator at coordinates (2, 7) is the number 3. Thus, entry field 8040 is completed by entering indicators 6 and 3. Following a similar process, fields corresponding to threads comprising sets 049 and 6 of field location numbers are completed for the interface 8070 shown in FIG. 5.

Fig. 6 illustrates a client/server system including an authentication resource for an RPDPR authentication factor in accordance with the present invention. The client subsystem 1010 includes a data input device 4010 (keyboard, mouse, voice input, etc.), a display device 4020(CRT, LCD panel, etc.), and a physical platform 4030 (personal computer, handheld computer, internet appliance, etc.) that includes a processing unit, memory, and other data processing resources. Software running on the client, including browser 4050 or "thin" software client 4060, may be provided, for example, on personal digital assistants, cellular telephones, and other simple internet appliances that do not support full browser functionality. Browser 4050 comprises a Java virtual machine or.net environment that supports client/server sessions. Likewise, a "thin" software client 4060 may support a client/server conversation. Finally, an interface 4040 to the network communication medium 4130 is provided. The communication medium 4130 may be a private or public local or wide area network using wired, wireless or optical media in representative systems.

The server subsystem 1030 includes network server resources 4070, an account management tool 4080 for authenticating user account aspects of the process, and a platform 4090 that includes processing units, memory, disk space, and other data processing resources. A kernel 4100 supporting authentication processing is included in the server sub-system 1030. The core program may be implemented, for example, using Java or. NET object oriented technology. Further, a server database and database connector 4120 is included. Finally, an interface 4110 to the communication medium of the server LAN/WAN communication line 4130 is provided. In some embodiments, the server and server data are implemented with security features to protect the user account information file from intruders.

In various embodiments, the inventive system is used in user authentication in a client/server network architecture, authentication of hardware devices (clients include, for example, peer routers), and other environments that support interactive authentication sessions. Mutual authentication based on Random Partial Digital Path Recognition (RPDPR) algorithms provides important security protection against multiple known intruder attacks. The interactive, multi-field pattern processing of the present invention creates a new paradigm, replacing or enhancing standard static password techniques. By taking advantage of modern high clock frequency client/server CPU processing power and high network throughput, the RPDPR authentication process is easy to use.

In the above example, user authentication begins with an initial request by a client to a protected network target. The server, having knowledge of the client's username and the shared secret complete pattern (the complete digitized path with the data fields of its location, the respective coordinates defining these locations, arranged along the path according to their location), then prompts the user to complete, via the client's GUI, a subset of the user's complete pattern that the server randomly selected. The full pattern is a secret pre-shared between the client and the server, established during the client account setup. The complete pattern resides in a database on the server side. Each field in the random subset of client requests is associated with a displayed sequence number corresponding to a location in the full pattern. Each field in the GUI allows any combination of objects to be entered (at least one object is entered per field). In the example presented for RPDPR, the objects entered in the field may be selected from a randomized set of indicators represented by a reference grid located at coordinates stored in a subset of a data set storing the full digitized path. Upon receiving the client's response, the server compares the internally computed expected combination with the client's input data, and makes a denial/continuation authentication decision assuming the response is false/true.

While the present invention has been disclosed with reference to the preferred embodiments and examples detailed above, it is to be understood that these examples are intended in an illustrative rather than in a limiting sense. Modifications and combinations will readily occur to those skilled in the art, which modifications and combinations will be within the spirit of the invention and the scope of the following claims.

Claims (38)

1. An interactive method for client authentication by a server, comprising:

storing data defining a graphical representation of a reference frame adapted to be presented on a display, the reference frame comprising a plurality of predefined locations in the reference frame having coordinates of the reference frame;

storing in a memory a data set comprising a plurality of data fields having respective locations in the data set and having field contents representing coordinates of a plurality of the predefined locations, the plurality of data fields having an order such that the plurality of predefined locations represented by the field contents of the data fields define a digitized targeting path known to a client along a reference frame in the order;

identifying, to a client over a data communication medium, locations of a random subset of data fields in the data set;

accepting, over a data communications medium, input data from a client, the input data corresponding to coordinates of a frame of reference for a subset of the plurality of predefined locations along the digitization path, the subset of the plurality of predefined locations being represented by locations in the data set of data fields of a random subset of the data fields in the data set; and

it is determined whether the input data matches a predefined location represented by the field contents of the data fields in the random subset and authentication success is notified if the input data matches and authentication failure is notified if the input data does not match.

2. The method of claim 1, comprising: providing an instance of a graphical representation of said reference frame comprising an array of indicators at said predefined locations of the reference frame, and wherein said input data comprises said indicators.

3. The method of claim 1, comprising: providing an instance of a graphical representation of the reference frame, the instance comprising an array of indicators at the predefined locations of the reference frame, and wherein the input data comprises the indicators, wherein the indicators comprise alphanumeric characters.

4. The method of claim 1, comprising: providing an instance of a graphical representation of the reference frame comprising an array of indicators at the predefined locations of the reference frame, and the input data comprising the indicators, wherein the indicators are randomly or pseudo-randomly generated by the server, such that the provided instance uses a different indicator than the predefined locations used in other instances of the graphical representation.

5. The method of claim 1, comprising: providing an input structure from the server to the client via the data communication medium for inputting data from the data set corresponding to the field contents of said random subset of data fields, and wherein said accepting data input from the client comprises accepting data based on said input structure.

6. The method of claim 1, comprising: providing a graphical user interface from a server to a client via a data communication medium, the graphical user interface comprising an input structure to facilitate the client to input data corresponding to the location, wherein the input structure comprises an instance of a graphical representation of the reference frame having an array of indicators of the predefined locations of the reference frame and an input field for inserting indicators from the array of indicators corresponding to the random subset.

7. The method of claim 1, comprising: an input structure for account establishment is provided to the client, and data is accepted from the client based on the input structure to set field contents for data fields in the data set.

8. The method of claim 1, comprising: an input structure for account establishment is provided to the client and data is accepted from the client based on the input structure to set field contents for data fields in the data set, wherein the input structure includes a graphical representation of the reference frame.

9. The method of claim 1, wherein the digitized path on a reference frame comprises a sequence of the first set of predefined locations and the additional set of predefined locations in the order, and wherein field contents of data fields in the data set represent coordinates of the first set of predefined locations and coordinates of the additional set of predefined locations, respectively, and locations of data fields in the data set correspond to the order.

10. The method of claim 1, wherein the digitization path comprises a sequence of the first set of predefined locations and an additional set of the predefined locations in the order, wherein the first set of predefined locations and the sequence of the additional set of predefined locations form a continuous digitization path on the reference frame.

11. The method of claim 1, wherein the digitization path comprises a sequence of the first set of predefined locations and an additional set of the predefined locations in the order, wherein the first set of predefined locations and the sequence of the additional set of predefined locations form a discontinuous digitization path on the reference frame.

12. The method of claim 1, wherein the digitized path on a reference frame has a predetermined number of sets of the predefined locations and includes a sequence of the first set of predefined locations and additional sets of the predefined locations in a client-set order to define a complete digital path.

13. The method of claim 1, comprising selecting an instance of the random subset on a server, wherein the instance comprises a variable number of data field positions in the data set.

14. The method of claim 1, comprising representing locations of data fields for a plurality of random subsets of the data set.

15. The method of claim 1, comprising providing a session timer, and comprising: the client session is disabled if the time elapsed before the authentication event in the client session exceeds a threshold.

16. The method of claim 1, comprising:

during the identifying, accepting, and determining, displaying an icon, the icon having a first state during the identifying, a second state after the accepting, and a third state after the determining.

17. The method of claim 1, comprising:

during the identifying, accepting, and determining, displaying a stop light icon, the icon displaying a red light during the identifying, a yellow light after the accepting, and a green light after the determining.

18. The method of claim 1, wherein the client provides the input data in a client system connected to the communication medium.

19. The method of claim 1, wherein the client provides the input data in a client system comprising a browser connected to a communication medium.

20. The method of claim 1, comprising:

detecting an attempt by a user to access a network resource;

in response to a detected attempt to access a protected network resource, providing an interface to a client over a data communication medium, the interface supporting the identifying and the accepting; and

if the input data matches, the client is notified of the authentication.

21. The method of claim 20, wherein the interface includes an instance of a graphical representation of a reference frame, the instance including an array of indicators at the predefined locations in the reference frame, and the input data includes the indicators.

22. An authentication system for a client, comprising:

a data processing resource comprising a processor, a memory, and a communication interface;

the data stored in the memory defines a graphical representation of a reference frame adapted to be presented on a display, the reference frame comprising a plurality of predefined locations in the reference frame having coordinates of the reference frame;

user account information stored in the memory, including for each customer a data set comprising a plurality of data fields having respective locations in the data set and having field contents representing coordinates of a plurality of the predefined locations, the plurality of data fields having an order such that the plurality of predefined locations represented by the field contents of the data fields define a complete digitized targeting path known to the customer along a reference frame in the order;

an authentication server adapted to be executed by a data processing resource, comprising: logic for identifying, to a client over a communication interface, a location of a random subset of data fields in the set of data; logic for accepting, over a communication interface, input data from a client, the input data corresponding to coordinates of a reference frame of a subset of the plurality of predefined locations, the subset of the plurality of predefined locations being represented by locations in the set of data in a data field of a random subset; and logic for determining whether the input data matches field contents of corresponding data fields in the random subset, wherein the authentication server comprises logic for: if the input data match, an authentication success is notified, and if the input data do not match, an authentication failure is notified.

23. The system of claim 22, wherein the authentication server comprises logic to provide an instance of the graphical representation of the reference frame, the instance comprising an array of indicators at the predefined locations of the reference frame, and the input data comprises the indicators.

24. The system of claim 22, wherein the authentication server comprises logic to provide an instance of the graphical representation of the reference frame, the instance comprising an array of indicators at the predefined locations of the reference frame, and the input data comprises the indicators, wherein the indicators comprise alphanumeric characters.

25. The system of claim 22, wherein the authentication server comprises: logic that provides an instance of a graphical representation of the reference frame, the instance comprising an array of indicators at the predefined locations of the reference frame, and the input data comprising the indicators; and logic to randomly or pseudo-randomly generate the array of indicators such that the provided instance uses a different indicator than used in other instances of the graphical representation.

26. The system of claim 22, wherein authentication server comprises logic to provide a graphical user interface comprising an input structure to facilitate a client to input data corresponding to the data field location, wherein the input structure comprises an instance of the reference frame with an array indicator at the predefined location of the reference frame and an input field for inserting an indicator from the array of indicators corresponding to the random subset.

27. The system of claim 22, comprising logic to: an input structure for account establishment is provided to the client, and data is accepted from the client based on the input structure to set field contents for data fields in the data set, wherein the input structure includes an instance of a graphical representation of the reference frame.

28. The system of claim 22, wherein the complete digitization path on a reference frame comprises a sequence of the first set of predefined locations and the additional set of predefined locations in the order, and wherein field contents of data fields in the data set respectively represent the first set of coordinates of the predefined locations and the additional set of coordinates of the predefined locations, and locations of data fields in the data set correspond to the order.

29. The system of claim 22, wherein the digitization path includes a sequence of the first set of predefined locations and an additional set of the predefined locations in the order, wherein the first set of predefined locations and the sequence of the additional set of predefined locations form a continuous digitization path on the reference frame.

30. The system of claim 22, wherein the digitization path comprises a sequence of the first set of predefined locations and an additional set of the predefined locations in that order, wherein the first set of predefined locations and the sequence of the additional set of predefined locations comprise a discontinuous digitization path on the reference frame.

31. The system of claim 22, wherein the complete digitized path on a reference frame is defined by a set of a predetermined number of the predefined locations and includes a sequence of the first set of predefined locations and the additional set of predefined locations in a client-set order to define a digital path.

32. The system of claim 22, wherein the authentication server comprises logic to: generating an instance of the random subset, wherein the instance comprises a variable number of data field positions in the data set.

33. The system of claim 22, wherein the authentication server comprises logic to: the location of the data field is represented in the client session for a plurality of random subsets of the set of data.

34. The system of claim 22, comprising logic to: an input structure for account establishment is provided to the client, and data is accepted from the client based on the input structure to set field contents for data fields in the data set.

35. The system of claim 22, comprising logic to: providing a graphical input structure to a client to input field contents of the random subset of data fields.

36. The system of claim 22, comprising logic to provide a session timer and logic to disable a client session if an elapsed time before an authentication event in the client session exceeds a threshold.

37. The system of claim 22, wherein the authentication server comprises logic to: an icon is displayed, the icon having a first state during an initial phase of the client session, a second state after accepting the input data, and a third state after determining whether the input data matches.

38. The system of claim 22, wherein the authentication server comprises logic to: a stop light icon is displayed that displays a red light during an initial phase of the client session, a yellow light after accepting the input data, and a green light after determining whether the input data matches.