Hashing schemes for cryptographic private key generation

Techniques are disclosed relating to generation of cryptographic private keys. In some embodiments, a computing system receives a request for a private key for use with a service that uses a key of a first length, where the request specifies a key of a second length that is less than the first length. The system then generates a hashing scheme based on the second length and a key computation time, where the hashing scheme includes a number of hashing rounds and a set of hashing functions. The system creates a synthetic key of the second length and uses the synthetic key and the hashing scheme to create a normal key of the first length, where the synthetic key permits a user to access the service by supplying the synthetic key and without having to supply the normal key. The disclosed cryptographic techniques may advantageously allow for memorization of private keys.

BACKGROUND

Technical Field

This disclosure relates generally to computer security, and, more specifically, to techniques for generating cryptographic private keys, e.g., for transaction security.

Description of the Related Art

Cryptographic private keys are often used by different systems to exchange secure messages. For example, a first user may encrypt or “sign” a message using their cryptographic private key before providing this message to another user. In this situation, only the first user knows their private key, but the other user is able to verify that the signed message originated from the first user. Users are often required to remember their private key in order to prove their identity by signing messages when communicating with other users. For example, a user may memorize or otherwise store their private key when a cryptographic system provides them with their private key for the first time. In order to maintain the integrity of a user's private key, cryptographic systems often generate long private keys which are difficult for users to memorize. In other words, a cryptographic system may generate private keys that have a very large key space in order to prohibit malicious users from using brute-force methods to guess the user's private key.

This specification includes references to various embodiments, to indicate that the present disclosure is not intended to refer to one particular implementation, but rather a range of embodiments that fall within the spirit of the present disclosure, including the appended claims. Particular features, structures, or characteristics may be combined in any suitable manner consistent with this disclosure.

Within this disclosure, different entities (which may variously be referred to as “units,” “circuits,” other components, etc.) may be described or claimed as “configured” to perform one or more tasks or operations. This formulation—[entity] configured to [perform one or more tasks]—is used herein to refer to structure (i.e., something physical, such as an electronic circuit). More specifically, this formulation is used to indicate that this structure is arranged to perform the one or more tasks during operation. A structure can be said to be “configured to” perform some task even if the structure is not currently being operated. A “computing system configured to generate a synthetic cryptographic private key” is intended to cover, for example, a computer system that performs this function during operation, even if it is not currently being used (e.g., when its power supply is not connected). Thus, an entity described or recited as “configured to” perform some task refers to something physical, such as a device, circuit, memory storing program instructions executable to implement the task, etc. This phrase is not used herein to refer to something intangible.

The term “configured to” is not intended to mean “configurable to.” An unprogrammed mobile computing device, for example, would not be considered to be “configured to” perform some specific function, although it may be “configurable to” perform that function. After appropriate programming, the mobile computing device may then be configured to perform that function.

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 specifically stated. For example, in a computing system having multiple user accounts, the terms “first” and “second” user accounts can be used to refer to any users. In other words, the “first” and “second” user accounts are not limited to the initial two created user accounts, for example.

When the term “or” is used in this disclosure with respect to a list of options, it will generally be understood to be used in the exclusive sense unless the context provides otherwise. Thus, a recitation of “x or y” is equivalent to “either x or y, but not both.” On the other hand, a recitation such as “x or y, or both” is to be interpreted in the inclusive sense. A recitation of “w, x, y, or z, or any combination thereof” or “at least one of . . . w, x, y, and z” is intended to cover all possibilities involving a single element up to the total number of elements in the set. For example, given the set [w, x, y, z], these phrasings cover any single element of the set (e.g., w but not x, y, or z), any two elements (e.g., w and x, but not y or z), any three elements (e.g., w, x, and y, but not z), and all four elements. The phrase “at least one of . . . w, x, y, and z” thus refers to at least one of element of the set [w, x, y, z], thereby covering all possible combinations in this list of options. This phrase is not to be interpreted to require that there is at least one instance of w, at least one instance of x, at least one instance of y, and at least one instance of z.

As used herein, the term “based on” is used to describe one or more factors that affect a determination. This term does not foreclose the possibility that additional factors may affect the determination. That is, a determination may be solely based on specified factors or based on the specified factors as well as other, unspecified factors. Consider the phrase “determine A based on B.” This phrase specifies that B is a factor and is used to determine A or affects the determination of A. This phrase does not foreclose that the determination of A may also be based on some other factor, such as C. This phrase is also intended to cover an embodiment in which A is determined based solely on B. As used herein, the phrase “based on” is synonymous with the phrase “based at least in part on.”

As used herein, a “module” refers to software and/or hardware that is operable to perform a specified set of operations. A module may refer to a set of software instructions that are executable by a computer system to perform the set of operations. A module may also refer to hardware that is configured to perform the set of operations. A hardware module may constitute general-purpose hardware as well as a non-transitory computer-readable medium that stores program instructions, or specialized hardware such as a customized ASIC. Accordingly, a module that is described as being “executable” to perform operations refers to a software module, while a module that is described as being “configured” to perform operations refers to a hardware module. A module that is described as operable to perform operations refers to both a software and a hardware module.

DETAILED DESCRIPTION

In order to provide sufficient security, cryptographic systems have commonly utilized relatively long cryptographic private keys. Generally, private keys that include a larger number of elements (e.g., characters or numbers, or both) are considered more secure than private keys with a smaller number of elements. Thus, in order to prohibit others from guessing a given user's private key, a cryptographic system generates a very long key. This, however, may places a burden on the user in that they must either memorize or otherwise store (e.g., on their device or as a hardcopy, such as a piece of paper) their private key for later use after it is generated by a cryptographic system. In situations where users store their private keys, this may introduce more opportunities for their keys to be accessed by unauthorized users.

In general, long private keys are associated with a large key space. As used herein, the term “key space” is intended to be construed according to its well-understood meaning, which includes a set of all possible permutations of a given key. For example, a key that is one character long and is generated from a set of six characters has a key space of 6. In the field of cryptocurrency, private keys may be chosen from a given field of values. For example, BITCOIN private keys are 32 bytes (64 hexadecimal characters) long, resulting in a key space that is 2256. A key space with these dimensions makes it very difficult for an attacker to check every possible value within the key space in order to access a user's account. For example, according to one estimate, it might take more than a trillion U.S. dollars in hardware cost for an attacker to have a reasonable chance of guessing another user's private key in a year, given a key space of 2256.

Cryptographic private keys that are 32 bytes long, however, are nearly impossible for most users to remember. Thus, many users may manually record their private keys on a piece of paper or store their private keys on their computer. Both of these scenarios present opportunities for other, unauthorized users to obtain these private keys. For example, consider a situation where a computing system provides a user with a private key that is 64 characters (32 bytes) long. In this example, the user will likely be unable to memorize the private key and will, therefore, need to write down their key or store the key digitally on their device. The present inventors have recognized that if instead, the user were presented with a private key that was 8 characters (4 bytes) long, it would be more likely that they would be able to memorize the 8-character private key for later use in secure transactions. This may prevent other users from obtaining the private key because the key is not written down where it could be seen or is not stored on a device that could be hacked. The disclosed techniques may advantageously provide users with secure private keys that are short enough for these users to remember for later use without having to externally store the private key. These private keys also take less time for the user to enter.

Techniques are disclosed for providing users with “synthetic” keys to users that can be translated to longer “normal” keys (e.g., 10 characters versus 32 characters). For example, a synthetic key may be generated from a synthetic field that includes a set of characters, while a normal key may be generated from a normal field that includes a different, larger set of characters. A field may include, for example, a set of elements, such as integers (e.g., {0, 1, 2, 3}) or binary digits (e.g., {00, 01, 10, 11}).

This synthetic-to-normal key translation process may be advantageously used by a software program that acts as an interface between the user and a service (e.g., BITCOIN). Such a program may allow a user to enter a key of length N, translate the key to length M (where M>N), and provide the key of length M to the service, with the result that the user only has to remember the shorter key of length N because the longer key of length M may be derived from the shorter key. In various embodiments, the program may be a cryptographic application stored on a user device, and in some cases may be part of a payment application that facilitates payment transactions such as those that utilize a service such as BITCOIN. During a first user interaction with the disclosed system and prior to the user receiving a private key, the program may generate a synthetic key and map this synthetic key to a longer, normal key using a hashing scheme that includes a particular number of hashing rounds and a determined set of hashing functions. Once the computing system has generated the synthetic key, it provides this short key to a user of the user device for use in securely transmitting messages to a service. This short key is ideally of a length that makes it easier for a user to remember it and, therefore, advantageously removes or lessens the need for the user to record or store the shorter key.

The disclosed techniques are not simply a matter of replacing a longer key with a shorter key. The present inventors have recognized that by properly selecting the hashing scheme which is used to map the synthetic key to the normal key, the security of the service will not be compromised. Consider an example in which a payment application is used that permits a user to enter an 8-character synthetic key that is mapped to a 32-character normal key that is used to access BITCOIN. Now consider the amount of computation time it would take for an attacker to perform a brute force entry into the BITCOIN key space. In the proposed technique, an attacker would not only have to try a brute-force entry into the smaller synthetic key space, but would have to perform the hashing scheme in order to translate the synthetic key to a normal key that would be recognized by BITCOIN. If the hashing scheme is selected to be sufficiently computationally intensive, the amount of computation time for brute force entry would remain the same. Thus, the service (here BITCOIN) and its users remain as secure as before, but the key required to provide at least the same level of security can be shorter because some of the “burden” of the security can be undertaken by the hashing scheme.

These techniques may be used to access the service in various ways. As one specific example, a user may wish to complete a BITCOIN transaction and send a transaction request to a BITCOIN server via their digital wallet. Prior to sending the transaction request, the user enters their synthetic key and the computing system maps this synthetic key to the normal key and then signs the request using the normal key. This signed transaction request is then transmitted to the server for authorization. Note that access to BITCOIN is just one possible example of a service that might be accessed using these techniques; the service may be of any arbitrary functionality, including financial or non-financial applications. For example, private keys may be used in contract management software or software distribution. In the contract management context, a legal service may sign a legal contract using their private key for security and then transmit this contract to one of their clients. The client is able to authenticate the source of the legal contract by decrypting the signed legal contract using a public key of the legal service.

Example Synthetic Key Generation

FIG. 1is a block diagram illustrating an example computing system configured to generate a synthetic key of key length N that is shorter than a normal key of key length M. In the illustrated embodiment, system100includes a computing system110configured to access a service150that uses cryptographic keys of a key length M. In some embodiments, computing system110is a user device as discussed in detail with reference toFIGS. 3A and 3B. In other embodiments, computing system110is a server as discussed in detail with reference toFIGS. 4A and 4B.

Computing system110, in the illustrated embodiment, receives a key request102from a user requesting a key that is a key length N that is shorter than key length M. A user may specify an arbitrary key length or may select a particular key length from a predetermined set of key lengths provided by computing system110.FIG. 6shows examples of input that may be provided by the user when sending key request102to computing system110for a private key. Once a user has specified a key length in their request, computing system110is configured to generate a key corresponding to the specified length. (Herein, “key length” may be measured in any suitable units—e.g., characters, bits, bytes, etc.) For example, a user may request a cryptographic private key that is 8 characters long. Based on the key length specified in key request102, computing system110generates a synthetic key132and maps the synthetic key to a normal key134that is a key length M. Key length M is longer than key length N. That is, the normal key includes more elements (e.g., characters) than the synthetic key. Example synthetic and normal keys are shown inFIG. 2.

In some embodiments, prior to generating synthetic key132, computing system110is configured to identify whether the key length N specified in key request102satisfies a key length threshold. For example, computing system may reject key request102if the key length does not satisfy the threshold (e.g., is too short). That is, if a key is short, its key space may be small and, therefore, this short key may be easily guessed using brute-force determination techniques. Such a short key would not satisfy the key length threshold. The key length threshold may be predetermined based on key spaces associated with different key lengths.

Computing system110is then configured to provide the synthetic key132to a user who sent key request102. For example, computing system110may display synthetic key132via a user interface in a one-time display for memorization by the user. In other situations, computing system110may store the synthetic key132and supply the synthetic key to the user at a later time upon request from the user or during a key recovery process (e.g., if the user broke their phone and replaced their phone with a new one). For example, if a user were to forget their synthetic key, the computing system could provide the synthetic key in response to the user answering a set of recovery questions. In some embodiments, computing system110may further be configured to register normal key134with service150(e.g., a cryptocurrency server, a bank server, a third-party financial server, a web server, a person-to-person communication system, an employee authentication system, etc.). For example, in some situations, in order for the synthetic key to be used to request transactions, the normal key needs to be registered with the transaction service. In other situations, service150may be a transaction ledger that facilitates transaction requests that are signed using normal keys that do not need to be registered prior to use.

In some embodiments, after providing a user with synthetic key132, computing system110receives a message request from a user, that includes a synthetic key, to send a private message to service150. Based on such a request, computing system110is configured to derive a normal key from the synthetic key by hashing the synthetic key included in the request using hashing scheme142. Once it has derived a normal key from the provided synthetic key, computing system110is configured to use normal key134to perform access114of service150. For example, computing system110may be configured to sign the requested message using normal key134and transmit this message to service150.

Service150is then configured to authenticate the message based on the signature using the normal key134. As one specific example, access114may include a signed transaction request. In this example, service150may determine whether to authorize the requested transaction by verifying the authenticity of the computing system110requesting the transaction. This verification is performed based on the transaction request being signed with the correct normal key134, which in turn was generated based on the correct synthetic key132using the correct hashing scheme142.

As used herein, the term “hashing” is intended to be construed according to its well-understood meaning, which includes using a mathematical algorithm to convert an input value of arbitrary size into a different value of fixed size. For example, a hash function may be a mathematical algorithm that takes a private key having a first length as input and outputs a different key having a second, different length. In various embodiments described in the present disclosure, a hashing scheme made up of one or more hashing operations may result in an input key within a first key space being mapped to an output key within a second, larger key space. Hashing functions are often one-way hashing algorithms whose output hash values cannot be converted back into the original input. For example, a hash function, denoted H(x), takes in an input x and outputs a deterministic scrambled response. This means if H(1) returns the value 5249, it will always return 5249. In addition, because H(x) is a one-way hash function, it is not possible to take the value 5249 and figure out that the value 1 was used to generate it. The following are non-limiting examples of hashing functions: Scrypt, MD5, SHA256, SHA512, CRC-32, Shake-128, etc. Hashing rounds refer to iterations of hashing. In some situations, performing a single hashing round may include a single iteration of hashing a private key (or some other piece of information) using a particular hashing function. For example, each round of three rounds of hashing performed on a particular synthetic key may be performed using a different hashing function. As one specific example, a synthetic key may be hashed using the following formula: SHA256(MD5(Keccak256(synthetic key))). In other situations, all three rounds of hashing may be performed using the same hashing function. For example, a synthetic key may be hashed using the following formula: SHA256(SHA256(SHA256(synthetic key))).

In some embodiments, computing system110is a server computing system configured to receive key requests120from user devices. For example, computing system110may be a cryptographic server that is configured to process requests for private keys received from users via cryptographic applications downloaded on user devices. In other embodiments, computing system110is a user device configured to receive key requests102from users. In such embodiments, computing system110may include a cryptographic application downloaded and executable by the computing system to allow a user to request private keys and then use these private keys to sign messages for authentication.

Computing system110includes a hashing module140and a key generator module130. Hashing module140is operable by computing system110to generate a hashing scheme142. Hashing module140receives information specifying a key length N104and computation time106as inputs and provides a hashing scheme142to key generator module130. In some embodiments, computation time106is specified in key request102in addition to key length N104. Computation time106may specify a length of time which computing system110may spend generating a key (and mapping it to a normal key) based on key request102. For example, key length N104may be 10 characters long, while the computation time106to generate the requested key may be one hour. Based on this information, hashing module140determines a number of hashing rounds to perform on a synthetic key as well as a set of one or more hashing functions usable to perform the determined number of hashing rounds. Example hashing schemes are discuss in further detail below with reference toFIG. 5.

As used herein, the term “computation time” refers to an amount of time it will take a computing system having some known set of hardware and software resources to derive a normal key from a synthetic key of a given length using a given hashing scheme. Derivation of normal keys from short synthetic keys, for example, may require a longer computation time than from long synthetic keys with all else, including security, being equal. The computation time may be inversely related to the total computing resources available to the computing system. For example, a computing system that has a smaller amount of computing resources may have a longer computation time than another computing system with a larger amount of computing resources when both computing systems are deriving a normal key of the same length using the same hashing scheme. In addition to key length and computing resources, a hashing scheme may affect key computation time. That is, a hashing scheme that includes a large number of hashing rounds may require a longer key computation time than a hashing scheme with a small number of hashing rounds.

Key generator module130generates a synthetic key132and maps this synthetic key to a normal key134using hashing scheme142. For example, key generator module130may generate synthetic key132using random or near-random techniques. Key generator module130may generate synthetic key132by randomly selecting characters (e.g., letters, number, symbols, etc.) from a set of characters included in a synthetic field (see example synthetic field shown inFIG. 2). For example, synthetic key132may be generated by randomly selecting 8 characters from a set that includes letters A-F and numbers 0-9. Key generator module130then maps synthetic key132to normal key134using hashing scheme142. An example mapping is discussed below with reference toFIG. 2.

As used herein, the term “cryptographic private key” is intended to be construed according to its well-understood meaning, which includes a variable in the field of cryptography that is used in combination with an algorithm to sign or decrypt information, or both. Private keys are shared only with a single, authorized user at generation to maintain the security of the key. This single user may prove that they are who they say they are by “signing” information using their private key. A private key may also be referred to as a secret key. Cryptographic private keys may be different lengths and may be generated from different sets of characters. For example, a “synthetic key” may be a shorter private key that includes 12 characters and is generated from a first set of characters, while a “normal key” may be a longer private key that includes 64 characters and is generated from a second, different set of characters. The first set of characters may make up a synthetic field, while the second set of characters may make up a normal field, as discussed below with reference toFIG. 2B.

Example Fields and Private Keys

FIGS. 2A and 2Bare diagrams illustrating an example hashing scheme142and application of the example hashing scheme to map a synthetic field to a normal field, respectively. InFIG. 2B, example200illustrates application of example hashing scheme142to synthetic keys included in a synthetic field210.

InFIG. 2A, hashing scheme142is applied to synthetic private key230. For example, three different hashing rounds204are performed on the synthetic key to generate normal private key240. Hashing rounds204X,204Y, and204Z may be performed using the same or different hashing functions. In addition, in other embodiments, more (or less) than three hashing rounds may be performed on synthetic key230. Note that the hashing scheme shown inFIG. 2Ais one non-limiting example of hashing scheme142, and that other steps or operations may be performed as part of the scheme. For example, the hashing scheme shown in the illustrated embodiment may include feedback and/or feedforward operations between the three hashing rounds.

InFIG. 2B, synthetic field210includes a set of three possible synthetic key values: {0, 1, 2}, while normal field220includes a set of six possible normal key values {0, 1, 2, 3, 4, 5}. The dotted arrows in the illustrated embodiment represent the application202of hashing scheme142in mapping synthetic keys of synthetic field210to normal keys of normal field220. The fields shown inFIG. 2Billustrate two non-limiting example sets of keys (synthetic and normal). In other embodiments, fields may include private keys with values other than integers (e.g., letters, symbols, etc.). Note that the synthetic and normal key values shown inFIG. 2Bare non-limiting examples of private keys and that private keys may be much longer (include more than one character).

In the illustrated example, for each synthetic key in synthetic field210, computing system110may determine a corresponding normal key of normal field220by inputting each key value into a hashing function H(x). As shown in the illustrated embodiment, H(0)=4, H(1)=0, and H(2)=5, so the synthetic field keys 0, 1, and 2, are mapped to the normal field keys 4, 0, and 5. Note that the embodiment shown inFIG. 2Bis one non-limiting example of derivation of normal keys from synthetic keys. That is, the mapping between normal keys and private keys may be a 2-digit (or three, five, ten, etc. -digit) to 1-digit mapping. For example, in other situations, a normal key derived from a synthetic key may be three, five, ten, etc. times longer than a synthetic key. In some situations, a synthetic key may include only numbers while its corresponding normal key may include both letters and numbers.

Given the mapping shown inFIG. 2B, suppose that computing system110provides a synthetic key to a user Alice, where this synthetic key includes a single value (a key of length1) in synthetic field210. Now, in this example, Alice's synthetic key maps to a corresponding element in normal field220. Given this example scenario, another user (e.g., an attacker) Eve can guess Alice's private key using two different methods. The first method is a traditional method in which Eve may disregard the synthetic field entirely and guess every integer in the normal field220(0 to 5), resulting in six different guesses. The second is a new method in which Eve may apply the hashing scheme to all of the elements in the synthetic field210(0, 1, and 2) to obtain the corresponding elements of the normal field220(4, 0, and 5) and guess these normal field values, resulting in three guesses. In both scenarios, Eve must complete six steps in order to brute-force guess Alice's private key. In some situations, Alice's synthetic key is mapped to a normal key using three hashing rounds, which may advantageously increase the security of Alice's synthetic key. In this example situation, Eve would need to complete 12 steps (9 hashing rounds (three rounds for each of the three potential key)+3 guesses) to determine Alice's private key.

In situations where a single hashing round is performed to map synthetic field values to normal field values, the amount of work to brute-force guess Alice's private using the traditional method is not equal to the amount of work to brute-force guess Alice's private key using the new method. That is, the work to compute a hash of a value is often cheaper than simply brute-force guessing a value. Therefore, the disclosed techniques use multiple hashing rounds to map values of synthetic field210to values of normal field220. For example, computing system110may use a hashing scheme H(H( . . . H(x) . . . ) to map values of synthetic field210to values of normal field220, where each H(x) applied to a synthetic field value is one hashing round.

Computing system110may apply n rounds of hashing, with the work of performing n hashing rounds being equal to or greater than the work of brute-force guessing, where n may be any real number. Said another way, if computing system110uses a hashing scheme142that includes n hashing rounds to map Alice's synthetic field value to a normal field value, then Eve will have to perform the same or a greater amount work to brute-force guess Alice's key using the new method than the amount of work to brute-force guess Alice's key using the traditional method.

In this non-limiting example, computing system110has advantageously reduced the complexity of Alice's data element (e.g., a value within a smaller field of values) without decreasing the difficulty to brute force guess her private key. Now, Alice only has to remember a number from 0 to 2, while Eve has to guess numbers from 0 to 5. Therefore, the disclosed techniques may advantageously provide a user with a shorter, rememberable private key, without compromising the security of the private key (e.g., without reducing the difficulty of guessing the private key using brute-force techniques).

Example Cryptographic Application

FIGS. 3A & 3Bare block diagrams illustrating example generation of a synthetic key and use of the generated synthetic key, respectively, by a user device320. InFIG. 3A, system300includes a user device320, while inFIG. 3Bsystem302includes user device320and service150. Note that user device320is one example of computing system110.

InFIG. 3A, user device320includes a cryptographic application322and a user interface350. Cryptographic application322may be a digital wallet application downloaded on a user's cell phone, for example. User device320, in the illustrated embodiment, receives a user key request304for a synthetic key. Based on this request, cryptographic application322generates synthetic key132using key generator module130and executes hashing module140to generate hashing scheme142for deriving a normal key134from synthetic key132. Key generator module130includes a derivation module360that uses hashing scheme142to map synthetic key132to normal key134. Cryptographic application322sends synthetic key132to user interface350for display in a one-time key display352for memorization by the user of user device320. In this example embodiment, synthetic key132is only displayed once and is not stored for later use.

InFIG. 3B, user device320receives a user message request306that includes a synthetic key132. In some embodiments, user message request306is a request to authorize a transaction between user device320and service150. For example, a user may send a request to initiate a transaction via a BITCOIN server. User device320is configured to execute cryptographic application322to derive a normal key from the synthetic key132provided in request306using derivation module360. For example, derivation module may utilize hashing scheme142, generated by hashing module140(not shown inFIG. 3B), to derive normal key134. Key generator module130then provides normal key134to signature module370.

Signature module370uses normal key134to sign (encrypt) the message requested by the user of user device320and transmits this signed messaged324to service150. Service150then verifies the authenticity of user device320by decrypting signed message324using a public key corresponding to normal key134. If signed message324is signed using a normal key that is derived from the correct synthetic key, then service150will know that the user of user device320is authentic (e.g., they are who they say they are). If, however, the synthetic key supplied in request306is incorrect, then the result of decrypting signed message324will indicate that the user of user device320is not authentic. Based on decrypting signed message324, service150sends a secure response356to cryptographic application322.

User interface350provides a display354of secure response356to the user of user device. In some embodiments, secure response356indicates that a transaction requested by the user has been approved based on service150being able to authenticate the user. In other embodiments, secure response356indicates that the transaction has been declined.

Note that various examples herein are discussed in the context of transactions, but these examples are discussed for purposes of explanation and are not intended to limit the scope of the present disclosure. In other embodiments, any of various secure transmissions may be implemented between a computing system and a service using private keys.

In contrast to the embodiments illustrated inFIGS. 3A and 3B, key generation and hashing operations may be performed by a cryptographic server rather than an application (such as cryptographic application322) downloaded on user device320. That is, a cryptographic server may facilitate secure communication between user device320and service150.

Example Cryptographic Server

FIGS. 4A & 4Bare block diagrams illustrating example generation of a synthetic key and use of the generated synthetic key, respectively. InFIG. 4A, system400includes a user device320and cryptographic server460, while inFIG. 4Bsystem402includes user device320, cryptographic server460, and service150. Note that cryptographic server460is one example of computing system110. Note that hashing scheme140is discussed in detail below with reference toFIG. 5.

Similar toFIG. 3A,FIG. 4Aillustrates generation and display of synthetic key132in a one-time key display352. UnlikeFIG. 3A, however, inFIG. 4A, cryptographic server460is configured to generated synthetic key132rather than user device320. In addition, in some embodiments, cryptographic server460is configured to register normal key134with service150after deriving normal key134from synthetic key132using hashing scheme142. For example, cryptographic server460may provide a public key corresponding to normal (private) key134to a BITCOIN server in association with a particular user account. The BITCOIN server is then able to use this public key to verify that messages received from the particular user account have been signed using normal key134.

InFIG. 4B, user device320provides synthetic key132to cryptographic server460in response to receiving user message request306which specifies synthetic key132. Cryptographic server460executes derivation module360to derive normal key134from synthetic key132. Cryptographic server460then signs the requested message and transmits the signed message462to service150. In some embodiments, cryptographic server460transmits signed message462to user device320and user device provides this signed message directly to service150instead of communicating through server460.

InFIG. 4B, service150provides secure response452to cryptographic server460and server460, in turn, transmits the secure response452to user device320. In embodiments where user device320provides signed message462directly to service150, this service may transmit secure response452directly to user device320instead of communicating through server460. User device320generates display454of the secure response452via user interface350.

Example Hashing Module

FIG. 5is a diagram illustrating a detailed example hashing module. In the illustrated embodiment, system500includes user device320which includes hashing module140, which in turn includes work determination module510, hashing number selection module520, and hashing function selection module530.

Hashing module140, in the illustrated embodiment, receives a second key length502and a key computation time506from a user, generates hashing scheme142and provides hashing scheme142to derivation module360for deriving normal key134. Hashing function selection module530selects one or more hashing functions based on second key length502and a key computation time506. Module530then provides a set532of hashing functions to work determination module510. For example, if the second key length is 10 characters and the key computation time506is 10 minutes, hashing function selection module530may select two different hashing functions to be included in set532.

Hashing number selection module520selects a particular number of hashing rounds522based on second key length502and key computation time506and provides this number to work determination module510. For example, for a key length of 10 characters and a key computation time of 10 minutes, hashing number selection module520may specify to perform 500,000 hashing rounds.

Work determination module510receives key computation time506, second key length502, set532of hashing functions, and number of hashing rounds522. Work determination module510randomly generates a synthetic key of the second key length502. Module510then calculates an amount of work514to perform the number of hashing rounds522on the synthetic key of the second key length502and to perform a brute-force determination of normal key resulting from hashing the synthetic key. For example, module510calculates the amount of work it will take to hash an 8-character key 100,000 times and then multiplies this amount by the number of permutations a 32-character normal key can have based on the number of characters in a normal field of 16 different characters (e.g., 0-9 and A-F) that the 9-character key maps to (this will only be 8 different characters). The result of this calculation is the amount of work514for the second key length.

Module510also determines an amount of work512to perform a brute-force determination of a normal key of a first length that is longer than the second length. For example, module510calculates the amount of work it will take to guess the total number of permutations that a 32-character normal key can have in a normal field of 16 different characters. That is, module510estimates how long it would take for an attacker to guess a user's normal key using two different techniques (1. brute-force guessing the longer normal key or 2. guessing the shorter synthetic key and deriving the normal key from this synthetic key using a hashing scheme). Module510provides amount of work512and514to scheme generator module550.

Based on the amount of work514being equal to or greater than the amount of work512, hashing scheme generator module550generates hashing scheme142that includes the number of hashing rounds522and the set532of hashing functions. If, however, amount of work514is less than amount of work512, scheme generator module550may provide feedback to hashing number selection module520or hashing function selection module530, or both, specifying to adjust the number of hashing rounds or the set532of hashing functions, or both. For example, if amount of work514is less than amount of work512, scheme generator module550may tell hashing number selection module520to select a greater number of hashing rounds522for hashing a synthetic key.

Example User Interface

FIG. 6is a block diagram illustrating example security options displayed via a user interface. In the illustrated embodiment, user interface350includes a plurality of security options610A-N. Each of security options610include a security score604, key length602, and key computation time606.

A user may send a request to user device320requesting a private key. In some embodiments, in response to such a request, user device320displays one or more security options (such as options610). The user may then select one of the options displayed via user interface350(e.g., by clicking or taping a screen of their smart phone). Based on the user selection, user device320implements a particular security option when generating a synthetic private key. Specifically, user device provides the information specified in the selected security option (security score604, key length602, and key computation time606) to hashing module140. A user may select a security option by clicking (e.g., using a computer mouse) or taping (e.g., using their finger on a touch screen) a particular security option.

In the illustrated embodiment, the security scores604included in each security option610may specify a level of security associated with a synthetic key that is generated using the corresponding security option. For example, security option610A has a security score604A of 5 (out of 10), a key length602A of 4 characters, and a key computation time606A of 15 minutes, while security option610B has a security score604B of 7 (out of 10), a key length602B of 4 characters, and a key computation time606B of two hours. In this example, security option610B is considered more secure because more hashing rounds may be performed for a 4-character key within two hours than within 15 minutes. That is, guessing a normal key corresponding to the synthetic key generated using security option610A will take less work than guessing a normal key corresponding to the synthetic key generated using security option610B.

In some embodiments, user interface350displays security options610in order of increasing security. For example, security options with higher scores are displayed in the right-hand portion of interface350, while options with lower scores are displayed on the left-hand portion. In some embodiments, the key computation time for different user devices320may differ based on the hardware limitations of these devices. For example, with all else being equal (e.g., specified key length, number of hashing rounds, and types of hashing functions used), a user device with fewer hardware limitations may have a shorter key computation time (e.g., because this device is faster and more powerful) than a user device with more hardware limitations (e.g., because this device is slower).

Example Method

FIG. 7is a flow diagram illustrating a method for generating a synthetic cryptographic private key for use with a service that uses a normal cryptographic private key that is longer in length than the synthetic key, according to some embodiments. The method shown inFIG. 7may be used in conjunction with any of the computer circuitry, systems, devices, elements, or components disclosed herein, among other devices. In various embodiments, some of the method elements shown may be performed concurrently, in a different order than shown, or may be omitted. Additional method elements may also be performed as desired.

At710, in the illustrated embodiment, a computing system receives a request for a cryptographic private key for use with a service that uses a key of a first length, wherein the request specifies a key of a second length that is less than the first length. In some embodiments, the service accepts messages that have been signed using a key of the first length.

At720, the computing system generates, in response to the request, a hashing scheme, wherein the hashing scheme is generated based on the second length and a key computation time. In some embodiments, the generated hashing scheme includes: a determined number of hashing rounds and a selected set of hashing functions. In some embodiments, the selected set of hashing functions includes one or more of the following: a scrypt function, a BLAKE function, and a SHA function. In some embodiments, the key computation time specifies, based on hardware limitations of the computing system, an amount of time to generate the normal key using the hashing scheme. In some embodiments, the key computation time is specified by a user and is included in the received request for a cryptographic private key.

In some embodiments, generating the hashing scheme includes displaying, via the user device, a set of security options, where at least one of the security options in the set of security options specifies a security score, a key length, and a key computation time. In some embodiments, the displayed security options are generated based on a length of time (a key computation time) a user is willing to wait for their synthetic key to be generated. In some embodiments, generating the hashing scheme includes receiving, based on user clicking activity, information specifying a security option, included in the set of security options, selected by the user.

In some embodiments, generating the hashing scheme includes selecting a particular number of hashing rounds. In some embodiments, generating the hashing scheme includes calculating a first amount of work to complete the particular number of hashing rounds for a key of the second length and to perform a brute-force determination of a key of the second length. In some embodiments, generating the hashing scheme includes calculating a second amount of work to perform a brute-force determination of a cryptographic private key of the first length. In some embodiments, generating the hashing scheme includes comparing the first amount of work and the second amount of work. In some embodiments, generating the hashing scheme further includes selecting, based on the comparing, a particular number of hashing rounds for the hashing scheme such that a first expected amount of work associated with a brute-force determination of a key of the second length and an associated hashing scheme exceeds a second expected amount of work associated with a brute-force determination of a key of the first length.

At730, the computing system creates a synthetic key of the second length. In some embodiments, the computing system generates the synthetic key by randomly selecting 8 characters from a set of 16 letters and numbers. In some embodiments, the synthetic key is a length that is rememberable by a user.

At740, the computing system uses the synthetic key and the hashing scheme to create a normal key of the first length. In some embodiments, the synthetic key permits a user to access the service by supplying the synthetic key and without having to supply the normal key. In some embodiments, in response to the request, the computing system transmits the synthetic key to a cryptographic application downloaded on a user device. In some embodiments, the computing system is a cryptographic server that facilitates communication between the cryptographic application and the service.

In some embodiments, the transmitting causes display of the synthetic key via a user interface of the user device in a one-time display for memorization by a user of the user device. In some embodiments, the user interface is included in a user device and the computing device is a cryptographic server that facilitates communication between a cryptographic application downloaded on the user device and the service. In some embodiments, the computing system receives, from a user, a request to send a private message to the service, wherein the request includes a synthetic key. In some embodiments, the computing system derives, based on the received synthetic key, a normal key, where the deriving is performed using the hashing scheme. In some embodiments, the computing system stores the synthetic key on a hardware device. For example, the synthetic key may be locked in a safe while daily transactions may be performed using a memorized synthetic key.

In some embodiments, the computing system signs a message using the result of the deriving. In some embodiments, the computing system transmits the signed message to the service. In some embodiments, the computing system receives, based on the signed message being authenticated by the service, a confirmation message for the requested message. In some embodiments, the user requests to perform a transaction via the service.

Example Computing Device

Turning now toFIG. 8, a block diagram of one embodiment of computing device (which may also be referred to as a computing system)810is depicted. Computing device810may be used to implement various portions of this disclosure. Computing device810may be any suitable type of device, including, but not limited to, a personal computer system, desktop computer, laptop or notebook computer, mainframe computer system, web server, workstation, or network computer. As shown, computing device810includes processing unit850, storage812, and input/output (I/O) interface830coupled via an interconnect860(e.g., a system bus). I/O interface830may be coupled to one or more I/O devices840. Computing device810further includes network interface832, which may be coupled to network820for communications with, for example, other computing devices.

In various embodiments, processing unit850includes one or more processors. In some embodiments, processing unit850includes one or more coprocessor units. In some embodiments, multiple instances of processing unit850may be coupled to interconnect860. Processing unit850(or each processor within850) may contain a cache or other form of on-board memory. In some embodiments, processing unit850may be implemented as a general-purpose processing unit, and in other embodiments it may be implemented as a special purpose processing unit (e.g., an ASIC). In general, computing device810is not limited to any particular type of processing unit or processor subsystem.

Storage subsystem812is usable by processing unit850(e.g., to store instructions executable by and data used by processing unit850). Storage subsystem812may be implemented by any suitable type of physical memory media, including hard disk storage, floppy disk storage, removable disk storage, flash memory, random access memory (RAM-SRAM, EDO RAM, SDRAM, DDR SDRAM, RDRAM, etc.), ROM (PROM, EEPROM, etc.), and so on. Storage subsystem812may consist solely of volatile memory, in one embodiment. Storage subsystem812may store program instructions executable by computing device810using processing unit850, including program instructions executable to cause computing device810to implement the various techniques disclosed herein.

I/O interface830may represent one or more interfaces and may 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 interface830is a bridge chip from a front-side to one or more back-side buses. I/O interface830may be coupled to one or more I/O devices840via one or more corresponding buses or other interfaces. Examples of I/O devices include storage devices (hard disk, optical drive, removable flash drive, storage array, SAN, or an associated controller), network interface devices, user interface devices or other devices (e.g., graphics, sound, etc.).

Various articles of manufacture that store instructions (and, optionally, data) executable by a computing system to implement techniques disclosed herein are also contemplated. The computing system may execute the instructions using one or more processing elements. The articles of manufacture include non-transitory computer-readable memory media. The contemplated non-transitory computer-readable memory media include portions of a memory subsystem of a computing device as well as storage media or memory media such as magnetic media (e.g., disk) or optical media (e.g., CD, DVD, and related technologies, etc.). The non-transitory computer-readable media may be either volatile or nonvolatile memory.