User authentication using multi-party computation and public key cryptography

Techniques are disclosed relating to user authentication using multi-party computation and public key cryptography. In some embodiments, a client system may receive, from a server system, an authentication challenge that includes a first partial signature value. The client system may access key-pair information that includes, for a server key-pair, a server public key and a second component of a server private key, where the server system has access to a first component of the server private key. The client system may then generate a second partial signature value using the second component of the server private key but not an entirety of the server private key, and may generate a final signature value based on the first and second partial signature values. Using the final signature value, the client system may then determine whether the authentication challenge was sent by the server system.

RELATED APPLICATIONS

The present application is related to U.S. application Ser. No. 15/415,451 entitled “Secure Remote User Authentication Leveraging Public Key Cryptography and Key Splitting,” filed on Jan. 25, 2017, and U.S. application Ser. No. 15/476,833 entitled “Secure Internal User Authentication Leveraging Public Key Cryptography and Key Splitting,” filed on Mar. 31, 2017.

BACKGROUND

Technical Field

This disclosure relates generally to data security, and more particularly to performing message verification using key-splitting and public key cryptography.

Description of the Related Art

Server computer systems, such as web servers, application servers, email servers, etc., may provide various computing resources and services to an end user. For example, a web service may use a computer system to provide access to software applications to remote users via a network. A web service will commonly limit access to its resources and services to only those users with a valid user account with the service. One method for limiting access to a web service is to require an end user to establish a user account and authentication credentials (e.g., a username and password), and to require end users to provide valid authentication credentials prior to gaining access to the service.

In some instances, however, such user credentials may be discovered by a malicious third-party (e.g., through a phishing attack, brute-force attack, etc.), presenting security concerns for server systems that rely solely on such credentials for user authentication. For example, once a malicious third-party obtains a valid user's authentication credentials, the malicious third-party may access the web service to the same extent as the authorized user.

DETAILED DESCRIPTION

Server systems implement various user authentication techniques in an effort to limit unauthorized access to computing services. As noted above, one common technique is to require a requesting user to provide authentication credentials (such as a password, PIN code, etc.) that may be validated (e.g., by the server system or a separate authentication server system) prior to providing the user with access to the service. This authentication technique presents various security concerns.

For example, with the proliferation of web-based services and mobile devices, a given user is often required to establish an account—and corresponding authentication credentials—for numerous websites or services. Since they are required to remember numerous authentication credentials, it is common for people to use authentication credentials that are easy to remember (e.g., “password,” “12345,” etc.) or to use the same authentication credentials across multiple services. Both of these common practices present significant security risks.

For example, simple credentials that are easy to remember are particularly susceptible to discovery through a brute-force, password-guessing attack. To mitigate the risk of such brute-force attacks, some web services enforce policies specifying minimum requirements for a user's authentication credentials, such as their length (e.g., at least eight characters) or content (e.g., use of an uppercase letter, number, special character, etc.). Unfortunately, however, such policies typically only make authentication credentials marginally more secure against brute-force attacks while making them significantly more difficult for users to remember, further increasing the likelihood that people will reuse credentials across multiple web services. As noted above, using the same authentication credentials across multiple websites or services may increase the risk that the credentials are compromised by a malicious third-party. For example, if the user's credentials are compromised on a server for any one of the web services, all of the services would be susceptible to unauthorized access by a malicious third-party.

To help address these shortcomings, many web services implement multi-factor authentication (“MFA”) systems in which, in addition to providing something a user knows (e.g., an authentication credential) the requesting user must also provide one or more additional authentication factors, such as something the user “has” (e.g., a physical token, access to a linked email account or mobile device, etc.) or something the user “is” (e.g., by providing a biometric reading, etc.), to further prove their identity. While MFA systems can offer greater security than authentication credentials alone, such systems still suffer from various security concerns. For example, in many such MFA systems, the server still stores sensitive information, such as authentication credentials (either in plaintext or as a hash value), that may be susceptible to discovery by a malicious user. If a malicious third-party is able to obtain a valid user's authentication credentials and satisfy an additional authentication factor (e.g., through SIM card swapping, accessing the valid user's email account, etc.), the malicious third-party may be able to circumvent the MFA system. Further, in some instances, a user's authentication credentials (or other sensitive authentication information) may be vulnerable to discovery as they are sent between the server and client systems, even if MFA techniques are being used. For example, a malicious user may use a man-in-the-middle attack to intercept authentication information as it is sent between the server and client systems and use that authentication information to gain unauthorized access to the web service posing as the valid user. Accordingly, many authentication systems require a secure underlying connection (e.g., using Transport Layer Security (“TLS”) or any of various other security protocols) between the server and client systems before authentication operations may be safely performed.

In various embodiments, the disclosed systems and methods may ameliorate these and other technical problems by enabling message verification using key-splitting and public key cryptography to achieve multi party computation security capabilities. The disclosed systems and methods may be used by a first computer system, e.g., by a client system, to verify that a message it receives was actually sent by a second computer system (e.g., the server system that the client is attempting to access). In various embodiments, as described in more detail below, the server and client systems may establish an asymmetric key-pair (e.g., based on RSA, ElGamal, or any other suitable asymmetric key encryption scheme) and split the private key into multiple parts or “components.” (As used herein, splitting a key into “components” refers to the process of decomposing the key value into multiple addends that, when summed, add up to the entire key. In various embodiments, each such addend may be referred to as a “component” of the key.) In various embodiments, some—but not all—of the components are stored at the server system and some—but not all—of the components are stored at the client system such that no one entity has access to the entire private key. By not storing the entire private key at any one location, the risk of discovery of the private key by a malicious third-party is greatly reduced. In various embodiments, both the server and the client may use their respective components of the private key to independently generate signature values (e.g., based on some message or value, such as a digest value). These “partial” signature values (generated by the client and server systems) may then be combined to create a “final” signature value, which may be the same value as a signature value generated based on the entire private key.

For example, the server may generate its partial signature value based on the server's component of the private key and a digest value. The server may then send this partial signature value (along with other information, if desired) in a message to the client system. The client system may independently generate a partial signature value based on the client's component of the private key and the same digest value. The client system may then use these partial signature values to generate the final signature value, as explained below. This final signature value, in turn, may be used (along with the public key from the asymmetric key pair) to recover the original digest value on which the partial signature values were based. If the recovered digest value matches the original digest value, the client system may verify that the message it received originated from the server system.

Accordingly, in various embodiments, the disclosed systems and methods allow the client system to verify that a message is actually from a server system that it is attempting to access, rather than a malicious third-party (e.g., implementing a man-in-the-middle attack). This, in turn, may allow the client and server systems to securely perform authentication operations without reliance on a secure connection (e.g., using TLS) between the two systems, improving the security of the authentication process. Further, in instances in which the client and server systems are able to communicate over a secure connection, the disclosed systems and methods may still be used to increase security and provide further confidence in the authentication process, in some embodiments. Thus, in various embodiments, the disclosed systems and methods may improve data security for both a web service and its users, thereby improving the functioning of the service as a whole.

Note that the terms “partial signature value” and “final signature” are used as labels to facilitate discussion and to denote that a final signature value (e.g., final signature value412ofFIG. 4A) is generated subsequent to, and based on, two or more partial signature values (e.g., partial signature values144,146, and408ofFIG. 4A). The terms “partial signature value” and “final signature value” are not intended to limit the present disclosure to embodiments in which such values are the first and last signature values generated by the client or server systems. For example, in some embodiments, the server system120may create some other signature value (e.g., as part of some other authentication process) before generating partial signature value144, and the client system102may generate some other signature value (e.g., as part of some other authentication process) after generating the final signature value412.

Referring now toFIG. 1, a communication diagram illustrating an exchange100for user authentication using multi-party computation and public key cryptography is shown, according to some embodiments. In the depicted embodiment,FIG. 1includes client system102and server system120. Note that, although shown in direct connection, client system102and server system120may be connected via one or more communication networks (not shown for clarity). Note that, in various embodiments, client system102and server system120may communicate over either a secure or unsecured connection.

In various embodiments, server system120may host a web service122accessible to various remote users via one or more communication networks. For example, server system120may host an email service, streaming media service, customer-relationship management (“CRM”) software applications or data, or any other web service122, according to various embodiments. In some embodiments, for example, server system120may be (or be included in) a multi-tenant computer system or database system that provides computing resources for a plurality of tenants, each of which may include any suitable number of users. In the depicted embodiment, a user of client system102sends, at communication150, a request to access the service122provided by server system120. As discussed in more detail below, server system120may require the client system102to perform various authentication operations prior to gaining access to the service122.

In the depicted embodiment, server system120includes (or has access to) account information123associated with various user accounts for web service122. This account information123may include various items of information associated with the user accounts of the service122, such as authentication credentials, access permissions, etc. Server system120further includes authentication module121, which, in various embodiments, is operable to determine whether to authenticate a requesting user of client system102to the web service122. In various embodiments, authentication module121uses account information123and key information124in making this determination.

In various embodiments, key information124(which may be included as part of account information123, in some embodiments) includes information corresponding to one or more asymmetric key-pairs associated with various user accounts for the service122. The process of generating and exchanging key-pair information124between client system102and server system120will be discussed in more detail below with reference toFIGS. 2A-2B. For the purposes ofFIG. 1, note that key information124includes client key-pair information126and server key-pair information132associated with the user of client system102, which correspond to two separate asymmetric key-pairs generated during an enrollment phase. That is, in various embodiments, a client key-pair includes both a client public key and a client private key, and a server key-pair includes both a server public key and a server private key. As noted above and described in more detail below, both the client private key and the server private key may be “split” into two or more components and distributed between the client system102and the server system120(and, optionally, a user of client system102) such that no one entity has access to the entire client private key or server private key. In the depicted embodiment, key information124includes client key-pair information126and server key-pair information132. Similarly, client system102has (or has access to) key information106, which includes client key-pair information108and server key-pair information114. In various embodiments, client key-pair information108(at the client system102) and126(at the server system120) correspond to the same client key-pair generated during the enrollment phase, and the server key-pair information114(at the client system102) and132(at the server system120) correspond to the same server key-pair generated during the enrollment phase. As shown inFIG. 1, while both the client102and the server120may store the client public key110and server public key116, neither the client102nor the server120store the entire client private key or server private key, further protecting these key values in the event that either entity is compromised by a malicious third-party.

The client key-pair and server key-pair may be generated using any of various suitable public key encryption algorithms or schemes. For example, in various embodiments described throughout the present disclosure, the RSA algorithm is used to generate the client and server key-pairs. Note, however, that this embodiment is provided merely as an example and, in other embodiments, any other suitable public key encryption schemes, such as the ElGamal encryption system, may be used. Further note that, in some embodiments, the same public key encryption algorithm need not be used for both the client key-pair and server key-pair. As one non-limiting example, the RSA algorithm may be used to generate the server key-pair while the ElGamal system may be used to generate the client key-pair. (Although these two key-pairs are referred to as “client” and “server” key-pairs, these terms are used for convenience to facilitate discussion. As discussed in more detail below, the client and server key-pairs may both be generated by one entity (e.g., both generated by the client system102or the server system120) or each entity may create a separate key-pair, according to various embodiments.)

Once the server system120receives the access request at150, it may generate various items of authentication and verification information to be sent to the client system102. For example, in the depicted embodiment, server system120generates a challenge value138, which may be a random or pseudo-random numeric or alphanumeric value generated using any suitable algorithm or cryptographic hash function. The server system120may then encrypt the challenge value138using the client public key110to generate encrypted challenge value140. The server system120may then generate a partially decrypted challenge value142(based on the encrypted challenge value140) using client private key component130. As will be described in more detail below with reference toFIG. 3, as used herein, a “partially decrypted” challenge value refers to a challenge value that has been encrypted using a public key and then, using a component of the corresponding private key, decrypted. The resulting value may be referred to as a “partially decrypted challenge value.” This same process may be repeated using the remaining components of the private key such that when all of the partially decrypted challenge values are combined, the completely decrypted challenge value may be recovered.

As described in more detail below with reference toFIG. 4B, the encrypted challenge value140and partially decrypted challenge value142may be used by the client system102to generate an authentication value148, which may then be sent back to the server system120and used to determine whether to authenticate the user to the service122. The server system120may also generate information to be used, by the client system102, to verify that the authentication challenge was actually sent by the server system120. For example, in the depicted embodiment, the server system120generates a partial signature value144using the server private key component136. In various embodiments, partial signature value144may be a digital signature (e.g., an RSA signature, ElGamal signature, etc.) created by authentication module121based on a particular message. In some embodiments, for example, authentication module121may generate a digest value (e.g., using SHA-256, MD-5, etc.) based on an input value (e.g., encrypted challenge value140, a current time, a counter, etc.). A more detailed discussion of server system120is provided below with reference toFIG. 3.

At152, the server system120sends an authentication challenge to the client system102, which, in the depicted embodiment, includes the encrypted challenge value140, the partially decrypted challenge value142, and the partial signature value144. In various embodiments, authentication application104(included on client system102) may use these values to both verify that the authentication challenge originated at the server system120and to generate an authentication value148that may be used, by the server system120, to determine whether to authenticate the user to the service122. For example, client system102may generate a partial signature value146using its server private key component118. In various embodiments, partial signature value146may be a digital signature (e.g., an RSA signature, ElGamal signature, etc.) created by authentication application104based on a particular message. In various embodiments, the particular message is generated in the same manner by both the client system102and the server system120(e.g., a digest value generated using the same hash function and the same input value). Further, in various embodiments, partial signature values144and146are generated using the same digital signature schemes (e.g., both using RSA, ElGamal, etc.).

In various embodiments, authentication application104may combine the partial signature values144and146to generate a final signature value. In the depicted embodiment in which the server private key has been split into two components (that is, components118and136), the two partial signature values144and146may be combined in a manner that produces a final signature value that is the same as a signature value generated based on the entire server private key. As described in more detail below with reference toFIG. 4A, authentication application104may use this final signature value, along with the server public key116, to verify that the authentication challenge originated at the server system120(and not, for example, a malicious third-party posing as the server system). Note thatFIG. 1has been described with reference to an embodiment in which the server private key has been split into only two components. In other embodiments, however, the server private key may be split into any suitable number of components. For example, in some embodiments, the server private key may be split into three components—component118, component136, and a third component that may be provided by the user. In some such embodiments, for example, the third component may be a relatively short piece (e.g., a 4-6 digit portion that could be considered a personal identification number or “PIN”) of the server private key that the user provides on the client system102at the time of authentication.

Once it has verified the authentication challenge, client system102may use the client key-pair information108to decrypt the encrypted challenge value140and generate an authentication value148. Various embodiments of client system102, including the manner in which it decrypts encrypted challenge value140, are described in more detail below with reference toFIG. 4B. For the purposes ofFIG. 1, note that the authentication application104may use the encrypted challenge value140, the partially decrypted challenge value142, and the client private key component112to recover the challenge value138. The authentication application104may then generate an authentication value148based on this recovered challenge value (e.g., using a cryptographic hash function, such as SHA-256, MD5, etc.), or it may send the challenge value138to the server system120as the authentication value148itself.

In various embodiments, server system120may determine whether to authenticate the user of client system102to the service122based on the authentication value148. For example, in embodiments in which the authentication value148is a digest value based on the recovered challenge value, the server system120may similarly generate a digest value (e.g., using the same hash function) based on the challenge value138and compare. If the two values match, the server system120may authenticate the user and allow the user to access the service122. If, however, the two values do not match, the server system120may take one or more corrective actions, such as denying the user access to the service122, initiating additional authentication operations, etc.

Note that, in various embodiments, the disclosed systems and methods may be thought of as a form of multi-party computation (“MPC”) in which multiple parties jointly compute a function using their respective input values without revealing information about those input values. As one non-limiting example, as discussed above, server system120may generate a partial signature value144using the server private key component136and send partial signature value144to the client system102. The client system102may then generate its own partial signature value146using its server private key component118, and combine the partial signature values144and146to generate a final signature value. In doing so, both the server system120and the client system102contributed to the computation of the final signature value without revealing their respective server private key components. Accordingly, the server system120and client system102(and, in some embodiments, the user of client system102) may be considered the “parties” in such a MPC system.

The following discussion, with reference toFIGS. 2A-2E, describes example embodiments in which client system102and server system120generate and exchange key-pair information for a server key-pair and a client key-pair during an enrollment operation (in which a user of client system102enrolls in an authentication service provided by the server system120). More specifically,FIGS. 2A-2Bdepict block diagrams respectively illustrating operations performed by the client system102and the server system120to generate and exchange the key-pair information.FIGS. 2C-2Eshow example code snippets, provided in JAVA™, which may be used to implement various aspects of the operations described with reference toFIGS. 2A-2B.

Turning now toFIG. 2A, a block diagram200is depicted illustrating operations performed by the client system102(e.g., by the authentication application104) to generate and exchange the client key-pair information with server system120. In the depicted embodiment, client system102generates a client key-pair202, including client public key110and client private key204. As noted above, client key-pair202may be generated using any of various suitable asymmetric key encryption algorithms. For example, inFIG. 2C, code snippet230shows an example in which an asymmetric key-pair is generated using the RSA algorithm with keys 4096 bits in length. In the depicted embodiment, client system102stores the client public key110in key information106(although, in other embodiments, client system102may not store the client public key110at all, or may publish it to be stored remotely and retrieved as-needed).

InFIG. 2A, client system102splits the client private key204into multiple components. Note that, in various embodiments, when splitting the client private key204into components, the components may be selected such that, when all of the components are added together, their sum is equal to the original client private key204. As a simplified example, if the client private key204is the number 7, it could be split into three components such that the first component is 4, the second component is 2, and the third component is 1. In the depicted embodiment, client system102splits the client private key204into three components—the first component is a PIN code selected by the user (e.g., 4-6 digits in length) and the second and third components (components112and130) are based on the client private key204and the PIN code such that the sum of the PIN, component112, and component130is equal to the client private key204. Code snippet240and250, inFIGS. 2D-2E, show an example implementation to split the client private key204into three such components.

Client system102may then store the client private key component112in key information106, while sending the client public key110and the client private key component130to the server system120. Note that, in various embodiments, the client system102does not store at least one of the client private key components such that it does not store the entirety of the client private key204. For example, in the depicted embodiment, client system102stores the client private key component112but does not store the client private key component130or the PIN (which the user may provide at the time of authentication). As shown inFIG. 2A, the client system102receives the server public key116and server private key component118, from the server system120, which it may store in key information106.

InFIG. 2B, a block diagram220is depicted illustrating operations performed by the server system120(e.g., by authentication module121) to generate and exchange server key-pair information with client system102. Note that, in the embodiment depicted inFIGS. 2A-2B, client system102generates the client key-pair202and the server system120generates the server key-pair222. This embodiment is provided merely as an example and, in other embodiments, either the client system102or the server system120may generate both the client and server key-pairs, as desired.

In the depicted embodiment, server system120generates a server key-pair222, including server public key116and server private key224. As with client key-pair202, server key-pair222may be generated using any of various suitable asymmetric key encryption algorithms. In some embodiments, server key-pair222may be generated as illustrated in the code snippet230ofFIG. 2C. In the depicted embodiment, server system120stores the server public key116in key information124.

In various embodiments, server system120splits the server private key224into multiple components. As with the client private key204, server private key224may be split into components selected such that the sum of all of the components is equal to the entire server private key224. For example, in the depicted embodiment, server private key224is split into two components, component118and component136. Further, in the depicted embodiment, the server system120sends the server private key component118and the server public key116to the client system102, while storing the server private key component136. Note that, in various embodiments, the server system120does not store at least one of the server private key components such that it does not store the entirety of the server private key224. For example, in the depicted embodiment, server system120stores the server private key component136but does not store the server private key component118. As shown inFIG. 2B, the server system120receives the client public key110and client private key component130, from the client system102, which it may store in key information124.

Note that, in some embodiments, server private key224may be split into a greater number of components. For example, similar to the client private key204, server private key224may be split into three components, in some embodiments, with the first component being a PIN code (e.g., to be provided by the user, on the client system102, at the time of authentication and sent to the server system120) and the second and third components may be generated based on the server private key224and that PIN code. In some such embodiments, the PIN used as a component of the server private key224may be the same as or different than the PIN used as a component of the client private key204.

Referring now toFIG. 3, a block diagram illustrating an example embodiment of a server system120and authentication module121is shown. In various embodiments, authentication module121is operable to determine whether to authenticate a requesting user of client system102to the service122. For example, as discussed above, authentication module may be operable to generate challenge information—such as encrypted challenge value140and partially decrypted challenge value142—to be sent to the client system102. Server system120may then receive an authentication response, from client system102, that includes authentication value148, which the authentication module121may use to determine whether to authenticate the user to the service122. Note that in the following description ofFIGS. 3 and 4A-4B, reference will be made to the code snippets500-540shown inFIGS. 5A-5E, which may be used to implement various operations described with reference toFIGS. 3 and 4A-4B.

In the depicted embodiment, authentication module121includes challenge value generator302, which is operable to generate a challenge value138, according to various embodiments. Challenge value138, in various embodiments, may be a random or pseudo-random value generated using any suitable random or pseudo-random function. Authentication module121further includes encryption module304, which is operable to encrypt challenge value138to generate encrypted challenge value140. In various embodiments, encryption module304may use the RSA encryption algorithm to generate encrypted challenge value140by encrypting the challenge value138using the client public key110. In other embodiments, however, other suitable public key encryption systems may be used, such as the ElGamal encryption system.

Authentication module121further includes partial decryption module306, which is operable to generate a partially decrypted challenge value142, according to various embodiments. In some embodiments, for example, partial decryption module306may generate value142by decrypting the encrypted challenge value140using the client private key component130(e.g., using the RSA encryption algorithm or any other suitable public key encryption algorithm).

Further, in the depicted embodiment, authentication module121includes hash generator308, which is operable to generate a digest value310(which may also be referred to as a hash value310) based on an input value, such as encrypted challenge value140, a current time, a counter, etc. In various embodiments, hash generator308may use any suitable hash function, such as SHA-256, MD5, etc. For example, code snippet500ofFIG. 5Ashows an example implementation in which a digest value310is generated using SHA-512 based on a current time. Note, however, that this embodiment is provided merely as an example and is not intended to limit the scope of the present disclosure. In other embodiments, for example, hash generator308generates digest value310based on encrypted challenge value140. InFIG. 3, authentication module121also includes signature generator312, which is operable to generate a partial signature value144based on the digest value310. In some embodiments, partial signature value144may be a digital signature (e.g., an RSA signature value, an ElGamal signature value, etc.) generated based on the digest value310using the server private key component136. For example, in some embodiments, signature generator312may generate an RSA partial signature value144as follows:
PS144=(dv310)Component 136(modn)  (1)

Where PS144is the partial signature value144, dv310is the digest value310, Component136is the server private key component136, and n is the modulus for the server key-pair. Code snippet510ofFIG. 5Bprovides one example implementation that may be used to generate partial signature value144.

In various embodiments, server system120may send an authentication challenge to client system102in response to the access request. This authentication challenge may include, in various embodiments, the encrypted challenge value140, the partially decrypted challenge value142, and the partial signature value144. As described below with reference toFIGS. 4A and 4B, client system102may use the information in the authentication challenge to verify its sender and generate authentication value148. Once server system120receives the authentication response, including the authentication value148, authentication module121may determine whether to authenticate the user of client system102to the service122. For example, as provided below, client system102may perform operations to recover the challenge value138, which it may use to generate an authentication value148. In the depicted embodiment, for example, authentication value148may be a hash value generated based on the recovered challenge value138. In some such embodiments, authentication module121may verify the authentication value148by generating a hash value (using hash generator314) of the original challenge value138and comparing that to the authentication value148. If the two values match, the server system120may authenticate the user and allow the user to access the service122. If, however, the two values do not match, the server system120may take one or more corrective actions, such as denying the user access to the service122, initiating additional authentication operations, etc. Note that, in various embodiments, the authentication value148may simply be one of multiple factors used by the server system120in determining whether to authenticate a requesting user of client system102to the service122. In some embodiments, for example, server system120may further consider the geographic location of the client system102, whether a user is already logged into the user account, a number of login attempts, the amount of time between the authentication challenge and the authentication response, etc. when determining whether to authenticate a requesting user.

Turning now toFIGS. 4A and 4B, block diagrams illustrating an example embodiment of client system102and authentication application104are shown. More specifically,FIG. 4Adepicts an embodiment in which authentication application104verifies that an authentication challenge was sent by the server system120, andFIG. 4Bdepicts an embodiment in which the authentication application104generates an authentication value that may be sent to server system120and used to authenticate the user to the service. Note that, in some embodiments, authentication application104may be a software application associated with the service122such that, in addition to the various authentication and verification operations described herein, application104may also be used to access the service122. In other embodiments, however, authentication application104may be a software application operable to perform authentication and verification operations for one or more web services. Further note that, in the depicted embodiment, authentication application104is shown executing on the client system102being used to attempt to access the service122. As one non-limiting example, client system102may be a laptop computer and authentication application104may be software installed thereon that is used by the user during authentication. In other embodiments, however, authentication application104may instead be used on a user device (e.g., a mobile device, such as a cellphone, tablet computer, etc.) other than the client system102. For example, in some embodiments, the user may use a web browser on client system102to attempt to access a web service122. Further, the user may have a mobile device on which the authentication application104is installed. In such embodiments, the authentication application104on the mobile device may be used to perform the various authentication and verification operations, while the laptop client system102may be used to access the service122.

InFIG. 4A, authentication application104includes hash generator402, which is operable to generate digest value404based on an input value, such as encrypted challenge value140, a current time, a counter, etc. Hash generator402may use any suitable hash function, such as SHA-256, MD5, etc., to generate the digest value404. For example, code snippet500ofFIG. 5Ashows an example implementation in which a digest value404is generated using SHA-512 based on a current time value. Note, however, that this embodiment is provided merely as an example and is not intended to limit the scope of the present disclosure. In other embodiments, hash generator402may generate digest value404based on encrypted challenge value140received from server system120. As noted above, in various embodiments, authentication application104is operable to generate a digest value404in the same manner that authentication module121generates digest value310(e.g., using the same function and input value) such that, for a given authentication attempt, the digest values310and404are the same.

Authentication application104further includes signature generation module406, which is operable to generate partial signature values based on a particular message and one or more private key components. For example, in the embodiment depicted inFIG. 4A, the server private key has been split into three components—a user-selected PIN code, server private key component118stored on client system102, and server private key component136stored at the server system120. In various embodiments, each of these key-components may be used to generate a partial signature value, which may then be combined to generate a final signature value. For example, as discussed above with reference toFIG. 3, authentication module121may generate partial signature value144using server private key component136(e.g., as shown in Equation 1 and code snippet510ofFIG. 5B). Similarly, in the depicted embodiment, signature generation module406may generate partial signature values146and408. In some embodiments, partial signature values146and408may be generated as follows:
PS146=(dv404)Component 118(modn)  (2)
PS408=(dv404)PIN(modn)  (3)

Where PS146is the partial signature value146, PS408is the partial signature408, dv404is the digest value404, and Component118is the server private key component118. Code snippet520ofFIG. 5Cprovides one example implementation that may be used to generate partial signature values146and408. Note that, although the server private key has been split into three components in the depicted embodiment, this is provided merely as one non-limiting example. In other embodiments, the server private key may be split into any suitable number of components. In some embodiments, for example, the server private key may be split into two components during the enrollment process, component118stored at the client system102and component136stored at the server system120. In still other embodiments, the server private key may be split into two components, a PIN code provided by the user during the authentication process and a component136stored at the server system120. In such embodiments, the client system102may not store any components of the server private key, for example. Further note that, although the partial signature values may be generated using various techniques, in various embodiments the same technique is used to generate each of the partial signature values. That is, all signature values associated with a given key-pair may be generated in the same manner (e.g., RSA, ElGamal, etc.), using different private key components.

Authentication application104further includes signature combination module410, which is operable to combine partial signature values to generate a final signature value, according to some embodiments. For example, in the depicted embodiment, signature combination module410may generate the final signature value412based on partial signature values144,146, and408as follows:
SIG412=PS144*PS146(modn)*PS408(modn)  (4)

Where SIG412is the final signature value412. Code snippet530ofFIG. 5Dprovides one example implementation that may be used to combine the partial signature values144,146, and408to determine the final signature value412. Note that, in various embodiments, signature combination module410uses as many partial signature values as there are server private key components when generating the final signature value412. For example, in the depicted embodiment, the server private key was split into three components during the enrollment process, so signature combination module410uses three corresponding partial signature values (e.g., values144,146, and408) to generate the final signature value412. In embodiments in which the server private key is instead split into only two components, the signature combination module may instead use only two partial signature values to generate the final signature value412. Substituting Equations 1, 2, and 3 into Equation 4 may then yield:
SIG412=(dv310)Frag. 136(modn)*(dv404)Frag. 118(modn)*(dv404)PIN(modn)  (5)

Note that, as discussed above, digest values310and404may be generated in the same manner such that they have the same value for a given iteration, according to various embodiments. Further note that, when the server private key was split into multiple components, the components were selected such that their sum is equal to the entire server private key, as follows:
Private KeyServer=PIN+Frag.136+Frag.118(6)

Thus, in various embodiments, the final signature value412—generated using only components of the server private key and not the complete server private key—is the same signature value that would be obtained using the complete server private key. As no one entity has access to the entire server private key, in various embodiments the disclosed systems and methods are able to protect the server private key from discovery by malicious third-parties.

Authentication application104further includes verification value generator414, which is operable to generate a verification value416based on the final signature value412, according to various embodiments. For example, in the depicted embodiment, verification value generator414is operable to generate verification value416based on final signature value412, using server public key116. In some embodiments, verification value416may be generated as follows:
Verification Value416=SIG412Server Pub.Key116(modn)  (8)

Code snippet540ofFIG. 5Eprovides one example implementation that may be used to generate verification value416, according to some embodiments. Substituting Equation 7 into Equation 8 may then yield:
Verification Value416=(dvPrivate KeyServer)Public KeysServer(modn)=dv(modn)  (9)

Thus, in various embodiments, verification value416may be a “recovered” version of the digest value404. The authentication application104may compare this verification value416to the original digest value404(e.g., using comparator418) to determine whether the authentication challenge originated from the server system120. If the verification value416and the digest value404match, authentication application104may determine that the authentication challenge—including the partial signature value144—originated at the server system120.

FIG. 4Bdepicts an embodiment in which the authentication application104generates an authentication value148that may be sent to server system120and used to authenticate the user to the service. Note that, in some embodiments, authentication application104may generate the authentication value148after it has verified that the authentication challenge was sent by the server system120.

InFIG. 4B, authentication application104includes partial decryption module450, which is operable to generate one or more partially decrypted challenge values based on the encrypted challenge value140and one or more client private key components. In the depicted embodiment, for example, partial decryption module450uses two components of a client private key, component112and the user-provided PIN code, to generate partially decrypted challenge values456and458. As noted herein, the algorithms used to encrypt and decrypt the challenge value138may vary, according to different embodiments. As one non-limiting example, in some embodiments, partial decryption module450may generate the partially decrypted challenge values456and458as follows:
PDCV456=ECV140Component 112(modnc)  (10)
PDCV458=ECV140PIN(modnc)  (11)

Where PDCV456is the partially decrypted challenge value456, PDCV458is the partially decrypted challenge value458, ECV140is the encrypted challenge value140, Component112is the client private key component112, and ncis the modulus for the client key-pair.

Authentication application104further includes challenge value recovery module452, which is operable to generate the challenge value138based on the partially decrypted challenge values. For example, in the depicted embodiment, challenge value recovery module452generates the challenge value138based on the partially decrypted challenge values142,456, and458. In some embodiments, challenge value recovery module452may recover the challenge value138as follows:
CV138=PDCV142*PDCV456*PDCV458(12)

Where PDCV142is the partially decrypted challenge value142and CV138is the challenge value138. Note that, in various embodiments, when the client private key was split into multiple components, the components were selected such that their sum is equal to the entire client private key, as follows:
Private Keyclient=PIN+Component 112+Component 130  (13)

Accordingly, in some embodiments, Equation 12 may be re-written as follows:

Thus, in various embodiments, the challenge value recovery module452may recover the challenge value138using the partially decrypted challenge values142,456, and458. In some embodiments, this recovered challenge value138may be sent, to the server system120, as the authentication value148in the authentication response. In other embodiments, however, authentication application104may use the recovered challenge value138to generate an authentication value148. For example, in the depicted embodiment, authentication application104includes hash generator454that is operable to generate authentication value148using any suitable hash function, such as SHA-512, etc. Note, however, that this embodiment is provided merely as an example and, in other embodiments, authentication value148may be generated based on the recovered challenge value138in any other suitable manner. In various embodiments, the client system102may send the authentication value148(or the recovered challenge value138) to the server system120in an authentication response.

Example Methods

Referring now toFIG. 6A, a flow diagram illustrating an example method600for authenticating a user to a service using key-splitting and public key cryptography, according to some embodiments. In various embodiments, method600may be performed by server system120ofFIG. 1to determine whether to authenticate a user of client system102to the service122. For example, server system120may include (or have access to) a non-transitory, computer-readable medium having program instructions stored thereon that are executable by the server system120to cause the operations described with reference toFIG. 6A. InFIG. 6A, method600includes elements602-614. While these elements are shown in a particular order for ease of understanding, other orders may be used. In various embodiments, some of the method elements may be performed concurrently, in a different order than shown, or may be omitted. Additional method elements may also be performed as desired.

At602, in the illustrated embodiment, the server system receives, from a client system, a request to authenticate a user to a service. In some embodiments, the request specifies credentials (e.g., username and password) for a user account associated with the service. As noted above, the server system and the client system may communicate via either a secured or unsecured network connection. For example, in some embodiments, the server system and client system communicate over a secured network connection using the TLS protocol.

At604, in the illustrated embodiment, the server system accesses key-pair information associated with the user, where the key-pair information includes, for a server key-pair, a first component of a server private key and, for a client key-pair, includes a client public key and a first component of a client private key. For example, in the embodiment ofFIG. 1, the server system120may access key information124, which may include client key-pair information126and server key-pair information132. In various embodiments, the client key-pair information126may include the client public key110and the client private key component130, and the server key-pair information132may include the server public key116and the server private key component136.

At606, in the illustrated embodiment, the server system generates challenge information to be sent to the client system in response to the request. As described in more detail above with reference toFIG. 3, in some embodiments, element606may include encrypting an original challenge value (e.g., challenge value138) using the client public key to generate an encrypted challenge value (e.g., encrypted challenge value140). The server system may then create a partially decrypted challenge value (e.g., using partial decryption module306) based on the encrypted challenge value and the first component of the client private key. In some embodiments, the server system120may include the encrypted challenge value and the partially decrypted challenge value in challenge information that is sent to the client system.

At608, in the illustrated embodiment, the server system generates a partial signature value based on the first component of the server private key but not an entire server private key. In some embodiments, for example, generating the partial signature value includes generating a digest value based on an initial input value, which may help to prevent and detect tampering in the middle by a third-party. Generating the partial signature value may further include calculating the partial signature value based on the digest value and the first component of the server private key.

At610, in the illustrated embodiment, the server system sends, to the client system, an authentication challenge that includes the challenge information and the partial signature value. Note that, in various embodiments, the client system includes a second component of the server private key (e.g., server private key component118) and is operable to generate a final signature value using the second component of the server private key and the partial signature value.

At612, in the illustrated embodiment, the server system receives an authentication response from the client system. In various embodiments, the authentication response indicates a decrypted challenge value generated, by the client system, based on a second component of the client private key. For example, in some embodiments, the authentication response may include the decrypted challenge value generated by the client system. In other embodiments, however, the authentication response may include an authentication value (e.g., authentication value148), such as hash value generated based on the decrypted challenge value, which may be considered to be “indicative” of the decrypted challenge value.

At614, in the illustrated embodiment, the server system determines whether to authenticate the user to the service based on the authentication response. For example, in some embodiments, determining whether to authenticate the user to the service includes comparing the decrypted challenge value to the original challenge value (e.g., using comparator316ofFIG. 3).

Turning now toFIG. 6B, a flow diagram illustrates an example method650for verifying a message using key-splitting and public key cryptography, according to some embodiments. In various embodiments, method650may be performed by client system102ofFIG. 1to verify whether a message (e.g., an authentication challenge) was actually sent by the server system120that the client102is attempting to access. For example, client system102may include (or have access to) a non-transitory, computer-readable medium having program instructions stored thereon that are executable by the client system102to cause the operations described with reference toFIG. 6B. InFIG. 6B, method650includes elements652-662. While these elements are shown in a particular order for ease of understanding, other orders may be used. In various embodiments, some of the method elements may be performed concurrently, in a different order than shown, or may be omitted. Additional method elements may also be performed as desired.

At652, in the illustrated embodiment, the client system receives, from a server system, an authentication challenge that includes challenge information and a first partial signature value. In some embodiments, the challenge information includes an encrypted challenge value and a first partially decrypted challenge value.

At654, in the illustrated embodiment, the client system accesses key-pair information associated with a user account for a service, where the key-pair information includes, for a server key-pair, a server public key and a second component of a server private key, and for a client key-pair, includes a second component of a client key pair. For example, in the embodiment depicted inFIG. 1, client system102may access key information106, which may include client key-pair information108and server key-pair information114. In various embodiments, the client key-pair information108may include the client public key110and the client private key component112, and the server key-pair information114may include the server public key116and the server private key component118. As discussed herein, the server private key-pair and the client private key-pair may be generated using any of various suitable public key encryption systems. For example, in some embodiments, either (or both) key-pairs may be an RSA asymmetric key-pair, an ElGamal asymmetric key pair, etc. Note that, in some embodiments, both the server and client key-pairs may be based on the same public key encryption scheme while, in other embodiments, the server and client key-pairs may be based on different public key encryption schemes.

At656, in the illustrated embodiment, the client system generates a second partial signature value based on a digest value. For example, in the embodiment ofFIG. 4A, authentication application104may generate one or more partial signature values (e.g., partial signature values146and408) based on a digest value404and one or more components of a server private key (e.g., a PIN code and the server private key component118).

At658, in the illustrated embodiment, the client system generates a final signature value based on the first and second partial signature values. For example, as described above with reference toFIG. 4A, authentication application104may include a signature combination module410that is operable to combine one or more partial signature values (e.g., values144,146, and408) to generate a final signature value412.

At660, in the illustrated embodiment, the client system determines a verification value based on the final signature value and the server public key. At662, in the illustrated embodiment, the client system determines whether the authentication challenge was sent by the server system based on the verification value. In some embodiments, for example, element662includes comparing the verification value (e.g., verification value416) to the digest value (e.g., digest value404), and, in response to the verification value matching the digest value, verifying that the authentication challenge was sent by the server system.

In some embodiments, method650may further include, in response to a determination that the authentication challenge was sent by the server system120, decrypting the encrypted challenge value using the second component of the client private key. For example, in some embodiments, decrypting the encrypted challenge value includes using the second component of the client private key to generate a second partially decrypted challenge value based on the encrypted challenge value, and generating a decrypted challenge value based on the first and second partially decrypted challenge values.

Example Computer System

Referring now toFIG. 7, a block diagram of an example computer system700is depicted, which may implement one or more computer systems, such as client system102or server system120ofFIG. 1, according to various embodiments. Computer system700includes a processor subsystem720that is coupled to a system memory740and I/O interfaces(s)760via an interconnect780(e.g., a system bus). I/O interface(s)760is coupled to one or more I/O devices770. Computer system700may be any of various types of devices, including, but not limited to, a server computer system, personal computer system, desktop computer, laptop or notebook computer, mainframe computer system, server computer system operating in a datacenter facility, tablet computer, handheld computer, workstation, network computer, etc. Although a single computer system700is shown inFIG. 7for convenience, computer system700may also be implemented as two or more computer systems operating together.

Processor subsystem720may include one or more processors or processing units. In various embodiments of computer system700, multiple instances of processor subsystem720may be coupled to interconnect780. In various embodiments, processor subsystem720(or each processor unit within720) may contain a cache or other form of on-board memory.

System memory740is usable to store program instructions executable by processor subsystem720to cause system700perform various operations described herein. System memory740may be implemented using different physical, non-transitory memory media, such as hard disk storage, floppy disk storage, removable disk storage, flash memory, random access memory (RAM-SRAM, EDO RAM, SDRAM, DDR SDRAM, RAMBUS RAM, etc.), read only memory (PROM, EEPROM, etc.), and so on. Memory in computer system700is not limited to primary storage such as system memory740. Rather, computer system700may also include other forms of storage such as cache memory in processor subsystem720and secondary storage on I/O devices770(e.g., a hard drive, storage array, etc.). In some embodiments, these other forms of storage may also store program instructions executable by processor subsystem720.

I/O interfaces760may be any of various types of interfaces configured to couple to and communicate with other devices, according to various embodiments. In one embodiment, I/O interface760is a bridge chip (e.g., Southbridge) from a front-side to one or more back-side buses. I/O interfaces760may be coupled to one or more I/O devices770via one or more corresponding buses or other interfaces. Examples of I/O devices770include storage devices (hard drive, optical drive, removable flash drive, storage array, SAN, or their associated controller), network interface devices (e.g., to a local or wide-area network), or other devices (e.g., graphics, user interface devices, etc.). In one embodiment, I/O devices770includes a network interface device (e.g., configured to communicate over WiFi, Bluetooth, Ethernet, etc.), and computer system700is coupled to a network via the network interface device.

Although the embodiments disclosed herein are susceptible to various modifications and alternative forms, specific embodiments are shown by way of example in the figures and are described herein in detail. It should be understood, however, that figures and detailed description thereto are not intended to limit the scope of the claims to the particular forms disclosed. Instead, this application is intended to cover all modifications, equivalents and alternatives falling within the spirit and scope of the disclosure of the present application as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description.

This disclosure includes references to “one embodiment,” “a particular embodiment,” “some embodiments,” “various embodiments,” “an embodiment,” etc. The appearances of these or similar phrases do not necessarily refer to the same embodiment. Particular features, structures, or characteristics may be combined in any suitable manner consistent with this disclosure.

As used herein, the terms “first,” “second,” etc. are used as labels for nouns that they precede, and do not imply any type of ordering (e.g., spatial, temporal, logical, etc.), unless stated otherwise. As used herein, the term “or” is used as an inclusive or and not as an exclusive or. For example, the phrase “at least one of x, y, or z” means any one of x, y, and z, as well as any combination thereof (e.g., x and y, but not z).

Reciting in the appended claims that a structure is “configured to” perform one or more tasks is expressly intended not to invoke 35 U.S.C. § 112(f) for that claim element. Should Applicant wish to invoke Section 112(f) during prosecution, it will recite claim elements using the “means for” [performing a function] construct.

In this disclosure, various “modules” operable to perform designated functions are shown in the figures and described in detail above (e.g., encryption module304, hash generator308, comparator316, etc.). As used herein, the term “module” refers to circuitry configured to perform specified operations or to physical, non-transitory, computer-readable media that stores information (e.g., program instructions) that instructs other circuitry (e.g., a processor) to perform specified operations. Such circuitry may be implemented in multiple ways, including as a hardwired circuit or as a memory having program instructions stored therein that are executable by one or more processors to perform the operations. The hardware circuit may include, for example, custom very-large-scale integration (VLSI) circuits or gate arrays, off-the-shelf semiconductors such as logic chips, transistors, or other discrete components. A module may also be implemented in programmable hardware devices such as field programmable gate arrays, programmable array logic, programmable logic devices, or the like. A module may also be any suitable form of non-transitory computer readable media storing program instructions executable to perform specified operations.