Source: https://patents.google.com/patent/US10382200B2/en
Timestamp: 2019-12-09 23:22:54
Document Index: 478308620

Matched Legal Cases: ['Application No. 2017204853', 'Application No. 2', 'Application No. 2', 'Application No. 2', 'Application No. 201480020500', 'Application No. 201480020482', 'Application No. 201480013039', 'Application No. 201480020517', 'Application No. 14751237', 'Application No. 14751612', 'Application No. 14751881', 'Application No. 14751256', 'Application No. 2016', 'Application No. 2015', 'Application No. 2015', 'Application No. 2015', 'Application No. 2015', 'Application No. 2017', 'Application No. 2017', 'Application No. 2015', 'Application No. 2015']

US10382200B2 - Probabilistic key rotation - Google Patents
Probabilistic key rotation Download PDF
US10382200B2
US10382200B2 US16/126,735 US201816126735A US10382200B2 US 10382200 B2 US10382200 B2 US 10382200B2 US 201816126735 A US201816126735 A US 201816126735A US 10382200 B2 US10382200 B2 US 10382200B2
US16/126,735
US20190007207A1 (en
2013-02-12 Priority to US13/764,944 priority Critical patent/US10467422B1/en
2013-06-13 Priority to US13/916,999 priority patent/US9608813B1/en
2013-06-20 Priority to US13/922,946 priority patent/US9300464B1/en
2016-03-03 Priority to US15/060,487 priority patent/US10075295B2/en
2018-09-10 Application filed by Amazon Technologies Inc filed Critical Amazon Technologies Inc
2018-09-10 Priority to US16/126,735 priority patent/US10382200B2/en
2018-09-10 Assigned to AMAZON TECHNOLOGIES, INC. reassignment AMAZON TECHNOLOGIES, INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: ROTH, Gregory Branchek
2019-01-03 Publication of US20190007207A1 publication Critical patent/US20190007207A1/en
2019-08-13 Publication of US10382200B2 publication Critical patent/US10382200B2/en
238000005309 stochastic process Methods 0 claims description 16
Information, such as a cryptographic key, is used repeatedly in the performance of operations, such as certain cryptographic operations. To prevent repeated use of the information from enabling security breaches, the information is rotated (replaced with other information). To avoid the resource costs of maintaining a counter on the number of operations performed, decisions of when to rotate the information are performed based at least in part on the output of stochastic processes.
This application is a continuation of U.S. patent application Ser. No. 15/060,487, filed on Mar. 3, 2016, entitled “PROBABILISTIC KEY ROTATION,” which is a continuation of U.S. patent application Ser. No. 13/922,946, filed on Jun. 20, 2013, entitled “PROBABILISTIC KEY ROTATION,” now U.S. Pat. No. 9,300,464, which incorporates by reference for all purposes the full disclosure of U.S. patent application Ser. No. 13/764,944, filed on Feb. 12, 2013, entitled “AUTOMATIC KEY ROTATION” and U.S. patent application Ser. No. 13/916,999, filed on Jun. 13, 2013, entitled “KEY ROTATION TECHNIQUES,” now U.S. Pat. No. 9,608,813.
FIG. 2 shows an illustrative example of an environment in which various embodiments may be practiced;
FIG. 3 shows an illustrative example of components of a cryptography service in accordance with an embodiment;
FIG. 4 shows a diagram illustrating a manner in which data may be stored in accordance with at least one embodiment;
FIG. 5 shows an illustrative example of a process for managing key rotation in accordance with an embodiment;
FIG. 6 shows an illustrative example of a process for managing key rotation in accordance with an embodiment;
FIG. 7 shows an illustrative example of a process for managing key rotation in accordance with an embodiment;
FIG. 8 shows an illustrative example of a process for managing key rotation in accordance with an embodiment; and
Techniques described and suggested herein relate to enhancements for data security in a manner that reduces the burden of such enhancements. In various embodiments, cryptographic keys (also referred to simply as keys) and other information are used to encrypt data. Generally, for the purpose of simplicity and efficiency, it is desirable to use the same cryptographic key multiple times. However, multiple uses of the same key for certain operations (such as encryption or message signing) can result in the generation of information (e.g., ciphertext or electronic signatures) that can be used in a cryptographic attack. Generally, the more often a cryptographic key is used in such operations, the more information is generated. The more of such information a malicious party has access to, the less difficult a cryptographic attack (e.g., where the key can be successfully guessed) becomes.
In various embodiments, cryptographic keys are probabilistically rotated. In some examples, when a request to perform a cryptographic operation is received, a stochastic process is performed to generate one or more values. As an example, a random number generator or pseudorandom number generator may be used to generate one or more numbers. The generated values may be used as arguments for conditions (also referred to as key rotation criteria) that are checked. As a result of the conditions being satisfied, a rotation of the corresponding key may be performed. As an illustrative example, an integer value may be stochastically generated. If the integer value satisfies a certain property (such as being divisible by a certain number) the key may be rotated. Rotation of the key may be performed by, for instance, replacing the key with a new key for future operations and updating metadata associated with the key/new key accordingly. The stochastic process and conditions applied to the output thereof may be configured to keep the probability of certain events from passing a threshold. For instance, in cryptographic ciphers that utilize nonces, it may be desirable to avoid use of the same nonce with the same cryptographic key for multiple operations. Accordingly, the stochastic process and conditions applied to the output of the stochastic process may be configured such that the probability of the same nonce being used with the same cryptographic key is below some acceptable threshold.
In some embodiments, more complex stochastic processes are utilized to change the shape of an applicable probability distribution in an advantageous manner. For instance, the stochastic process may be configured such that, on average, a greater number of operations (relative to more simple processes, such as by checking the output of a random number generator) are performed before a key is rotated. For instance, in some embodiments, a counter is probabilistically rotated. The output of a stochastic sub-process may be used to determine whether to update the counter. A threshold on the counter may be used to determine whether to rotate a key. In this manner, the probability of the undesired event occurring can be kept within an acceptable range while reducing the probability of a key rotation for lower numbers of operations using the key.
In some examples, while the various embodiments include those in non-distributed systems, operations using keys are performed using multiple devices (such as security modules) in a distributed system. In such distributed systems, the techniques described and suggested herein provide numerous technical advantages. For example, maintaining an accurate counter in a distributed system (to prevent the occurrence of an undesirable event from occurring) is a complex matter that requires significant computing resources such as network bandwidth. Therefore, the various embodiments of the present disclosure allow for determinations of when to perform key rotation in a manner that provides enhanced security while using significantly fewer resources. In particular, the stochastic processes used and conditions applied to the output of the stochastic processes can be configured such that an accurate counter of the number of operations performed is unnecessary for achieving high levels of security.
FIG. 1 is an illustrative example of a diagram illustrating various aspects of the present disclosure. As noted above, techniques described herein are applicable to insuring data security using cryptographic keys. Accordingly, FIG. 1 shows a cryptographic key 102 which is used to perform cryptographic operations whose output can contribute to cryptographic key wear out, which is a condition where a cryptogrpahic key is used in a particular way enough times that the danger of a successful cryptographic attack by someone with access to the output of the operations exceeds an acceptable level. Example operations that can cause cryptographic operations are operations that take plaintext as input and produce output, such as ciphertext or electronic (digital) signatures. As one example, many cryptographic cyphers, such as the Galois/counter mode of the Advance Encryption Standard (AES-GCM) utilize a nonce or other initialization value or vector. Use of the same key/nonce in multiople operations (even two operations) can provide enough information to unacceptably decrease the security of data encrypted under the key. As another example, enough blocks of encrypted data generated using the same key (and nonce, if applicable) can allow a cryptographic attacker to use a lookup table to determine the key in a known plaintext attack. Generally, for most practical cryptographic ciphers, cryptographic attacks become more and more possible as the same key is used again and again for certain operations.
Accordingly, as illustrated in FIG. 1 as the key 102 is used for such operations, the key is rotated at a point in time so as to maintain data security and keep the likelihood of a successful cryptographic attack below an acceptable level. In various embodiments of the present disclosure, the key 102 is rotated at a point in time when the probability of an event occurring (such as a repeated use of the same nonce/key pair) reaches a threshold. The threshold may be a a value selected based at least in part on an acceptable level of security. For instance, as a specific example, the threshold may be that a key rotation occurs when the probability of the event occurs reaches 1 in 232 (i.e., 1 divided by 4,294,967,296). Rotation of the key 102 may be performed by replacing the key 102 with a new key 104. As an example, in a key management system (also referred to as a cryptography service) the key 102 may have an associated identifier of the key 102. Multiple users (e.g., customers) may utilize the system and have their own identifiers for their own keys. The new key 104 may become associated with the identifier for the key 102 and other changes to the key management system may be accomplished so that the key management system utilizes the new key 104 for future encryption and/or message signing operations. The key 102 that has been rotated may remain available for various purposes, such as decryption of data encrypted using the key 102.
The computing resource service provider 202 may also include an on-demand data storage service. The on-demand data storage service 214 may be a collection of computing resources configured to synchronously process requests to store and/or access data. The on-demand data storage service 208 may operate using computing resources (e.g., databases) that enable the on-demand data storage service 208 to locate and retrieve data quickly, so as to allow data to be provided in responses to requests for the data. For example, the on-demand data storage service may maintain stored data in a manner such that, when a request for a data object is retrieved, the data object can be provided (or streaming of the data object can be initiated) in a response to the request. As noted, data stored in the on-demand data storage service 214 may be organized into data objects. The data objects may have arbitrary sizes except, perhaps, for certain constraints on size. Thus, the on-demand data storage service 214 may store numerous data objects of varying sizes. The on-demand data storage service 214 may operate as a key value store that associates data objects with identifiers of the data objects which may be used by the customer 204 to retrieve or perform other operations in connection with the data objects stored by the on-demand data storage service 210. The on-demand data storage service 214 may also be accessible to the cryptography service 212. For instance, in some embodiments, the cryptography service utilizes the on-demand data storage service to store keys of the customers in encrypted form, where keys usable to decrypt the customer keys are accessible only to particular devices of the cryptography service 212. Access to the data storage service by a customer, another service, or other entity may be through appropriately configured API calls.
To enable various efficiencies and security enhancements, a cryptography service may store and utilize cryptographic keys in various ways. Further, as noted above, a cryptography service may operate in connection with other services such as data storage services. FIG. 4 accordingly shows an illustrated example of an environment 400 in which various services may operate concurrently. As illustrated in FIG. 4, a data storage service 402 is configured to communicate with a cryptography service 404. For example, the data storage service 402 and the cryptography service 404 may be configured to configure appropriate API calls to each other for the purpose of transferring information and submitting requests and responses to the requests to one another.
As noted above, a data storage service 402 may store a plurality of data objects 406. Some, or even all, of the data objects 406 may be encrypted utilizing the cryptography service 404. As illustrated in cryptography services 404, data 408 of the data object 406 may be encrypted under a data object key 410. The data object 406 may also include the data object key 410 encrypted under a customer key 412 of a customer of the data storage service and the cryptography service 404. In other words, the data object 406 may include data encrypted under a key and the key encrypted under another key. In this manner, the data of the data object is stored in encrypted form with the key usable to decrypt the data, but the key is in encrypted form for the purpose of security. In other words, unauthorized access to the data object does not, by itself, enable access to the data inside of the data object in plaintext form. As shown in FIG. 4, the cryptography service 404 may store the customer key 412 encrypted under a domain key 414 such as described above. For instance, a cryptography service may store the customer key 412 encrypted under the domain key 414 in a repository of the cryptography service (not shown) or in an external data storage service.
As noted, the cryptography service 404 may store multiple customer keys in this manner. As further noted above, the cryptography service 404 may include a plurality of security modules 416 such as described above that store securely the domain key 414. In this manner, the data storage service 402 may interact with the cryptography service 404 for decryption of the data object key. The data storage service 402 may, for instance, provide the data object key 410 encrypted under the customer key 412 to the cryptography service 404. The cryptography service 404 may utilize a security module 416 to use the domain key 414 to decrypt the customer key 412 and use the customer key 412 to decrypt the data object key 410. The data object key 410 in plain text form may then be provided to the data storage service 402, which may then use the data object key 410 to decrypt the data 408.
Variations, of course, are considered as being within the scope of the present disclosure. For example, the security module 416 may be used to decrypt the data 408 using the data object key 410, thereby never providing the data storage service 402 access to the data object key 410.
As illustrated in FIG. 4, multiple cryptographic keys may be used directly or indirectly for encryption of data and/or for performing other cryptographic operations. Some or all of the keys involved may be rotated, in accordance with the various techniques described herein to maintain security for systems utilizing the keys and/or for data encrypted under any of the keys.
FIG. 5 shows an illustrative example of a process 500 which may be used to enhance data security. The process 500 may be performed by any suitable system, such as by the cryptography service described above in connection with FIG. 3 and/or an appropriate component thereof, such as by a webserver operating to provide the request API 306. Returning to FIG. 5, in an embodiment the process 500 includes receiving 502 a request to perform a cryptographic operation using a key. The request to perform the cryptographic operation may be received in any suitable manner. For example, referring to FIG. 3 the request may come in the form of an appropriately configured API call to the request API 306. A request may also be received internally within a system, such as from one component to another. The request that was received 502 may include various information that enables the request to be processed. Information may include, for example, information suitable to authenticate the request and/or in some embodiments an identifier for the key to be used. As illustrated in FIG. 5, upon receipt 502 of the request to perform a cryptographic operation using the key the process 500 may include causing 504 the request to be processed. Referring to FIG. 3, for example, causing 504 the request to be processed may include the request processing unit 304 to select an appropriate security module 312 to perform the cryptographic operation that was requested. Causing the request to be processed may include generating (or causing to be generated) a nonce or other initialization vector in embodiments where initialization vectors are used. In some embodiments, the nonce or other initialization vector is randomly or pseudorandomly generated.
The process 500 may also include determining 506 one or more arguments for one or more conditions for when the key should be rotated. Examples of arguments and conditions are described in more details below and, generally, the conditions may be one or more criteria that, when satisfied, result in rotation of a key. Briefly, as described below, determining the one or more arguments may be performed by performing a process to generate outcome having a known probability of occurring. The conditions may be configured based at least in part on the outcome. For instance, determining the one or more arguments may include performing a process that has a probability P of producing a particular outcome. A condition may be that the particular outcome occurs. Accordingly, the process 500 includes determining 508 whether the determined one or more arguments satisfy the one or more conditions. If it is determined 508 that the one or more arguments satisfy the one or more conditions, the process 500 includes rotating 510 the key.
Rotating 510 the key may be performed in any suitable manner. For example, referring to FIG. 3 a distributed system may utilize a plurality of security modules that each have access to the key. Rotating the key may be performed by causing the security modules to each have access to a new key to replace the key being rotated. Example processes that can be used to rotate keys include those described in U.S. patent application Ser. No. 13/764,944, filed on Feb. 12, 2013, titled Automatic Key Rotation and those described in U.S. patent application Ser. No. 13/916,999, filed on Jun. 13, 2013, and titled Key Rotation Techniques, both of which are incorporated by reference in their entirety for all purposes. As another example, as noted above, customer keys may be stored externally to security modules in a form encrypted using a key accessible to the security modules (e.g., a domain key). Rotating a key may include providing the encrypted key to a security module able to decrypt the key, generate a new key, encrypt the new key, and provide the encrypted new key. Further, rotating the key is not necessarily performed synchronously. For example, in some embodiments, an asynchronous process being performed by a system may be configured to rotate the key as part of its processing. Such a process may be, for instance, a background process that performs key rotation, garbage collection and/or other operations asynchronously. The process may be configured such that the key is eventually rotated over some time period, but not necessarily immediately. Generally, rotating the key may be performed by any suitable manner that results in the key being replaced by another key for future use in operations that contribute to cryptographic key wear out.
If it is determined 508 that the one or more arguments do not satisfy the one or more conditions (i.e., that the one or more arguments fail to satisfy a set of key rotation criteria), the key may be remain available for future use in such operations. Accordingly the process 500 may repeat such as described above. Similarly, once the key is rotated 510 the process 500 may be repeated as additional requests to perform cryptographic operations are performed. In this manner, the process 500 may be performed to manage key rotation without the need to maintain, in a distributed system, an accurate counter of use of the key to ensure that the key is not used enough times to provide a decrease in security beyond acceptable bounds. In other words, a technical advantage is achieved by defining conditions for key rotation in a manner that keeps the probability of undesirable events occurring below an acceptable threshold.
FIG. 6 shows an illustrative example of a process 600 for managing key rotation. The process 600, in this example, is a more specific, illustrative example of the process 500 discussed above in connection with FIG. 5. Accordingly, a system performing the process 500 may be a device performing the process 600. In an embodiment the process 600 includes receiving 602 a request to perform a cryptographic operation using a key. The request may be received and configured as described above. In addition, as with the process 500 discussed above in connection with FIG. 5, the process 600 includes causing 604 the request to be processed. The process 600 also as illustrated in FIG. 6 includes generating 606 a random number R which in reference to FIG. 5 may be an argument for a condition. The number R, in this example, is an integer in a range of integers that has length of at least K, where K is a positive integer. R, for instance, may be allowed to be a value between 0 and N*K−1, where N is a positive integer. R may be generated using a random or pseudorandom number generator configured to determine values within the set of acceptable R (e.g., within a range) where the set of acceptable values for R and the integer K are selected so that the probability of R being equivalent to zero modulo K (i.e., the probability of R being an integer multiple of K) is a predetermined amount such that, if R is equivalent to zero modulo K, the key is rotated. It should be noted that, for the purpose of illustration, a condition that a value be zero modulo K is used throughout the present disclosure for the purpose of illustration, but that other conditions are considered as being within the scope of the present disclosure. For example, instead of checking whether a value is zero modulo another number, whether the value is any positive number modulo another number may be used instead. Conditions that may be used are not necessarily dependent on modular arithmetic. For example, in some embodiments, a sequence of bits (which may be used as a nonce) is generated as an argument to one or more conditions. As an illustrative example, the one or more conditions may be that a specified number of leading or trailing digits are all equal to zero (or, alternatively, one). Generally, arguments and conditions applied to the arguments may be configured to minimize the computational resources required to determine whether the arguments satisfy the conditions.
As noted above, some embodiments perform probabilistic key rotation so as to keep the probability of using a particular nonce and key twice below an acceptable value, such as ½32. Let P1(i) represent the probability of not rotating the key after i cryptographic operations. In the example of FIG. 6 where a rotation occurs if R is equivalent to zero modulo K for the ith operation that contributes to cryptographic key wear out, assuming there is a 1/K probability of R being equivalent to zero modulo K, P1(i) would equal:
P 1 ⁡ ( i ) = ( K - 1 K ) i
Also let P2(i) represent the probability that, given i consecutive operations using the key, the probability that a nonce is repeated. Assuming that a new nonce is randomly generated for each operation, according to the generalized birthday problem, P2(i) would be equal to:
P 2 ⁡ ( i ) = { ( 1 - d ! d i ⁡ ( d - i ) ! ) if ⁢ ⁢ 1 ≤ i ≤ d 1 if ⁢ ⁢ d > i
where d represents the size of the nonce space (e.g., the number of possible nonces). Therefore, given the illustrative process of FIG. 6, the probability of both i consecutive operations performed without a key rotation and the same nonce being used twice after i consecutive operations is P1(i)*P2(i). As a result, since the number of operations performed without a key rotation is not known in advance, K (and/or d) may be selected such that
∑ i = 1 ∞ ⁢ P 1 ⁡ ( i ) ⁢ P 2 ⁡ ( i )
is within an acceptable bound, such as ½32. Generally, the above expression can be kept within an acceptable value for other probability functions which may vary according to the various ways in which arguments for key rotation conditions are determined in accordance with the various embodiments.
Returning to the illustrative example of FIG. 6, accordingly, a determination may then be made 608 whether the random number R that was generated 606 is equivalent to zero modulo K. If it is determined 608 that the random number R is equivalent to zero modulo K the process 600 may include rotating 610 the key such as described above. If, however, it is determined that the random number R is not equivalent to zero modulo K the process 600 may repeat such as described above in order to process additional requests using the same key. In this manner the process 600 may repeat until a random number R is generated that is equivalent to zero modulo K at which point the key is rotated.
As with all processes described herein, variations of the process 600 are considered as being within the scope of the present disclosure. For example, the process may be adapted for different ways of generating arguments for conditions that may result in different probability distributions. Similarly, the event (or multiple events) for which a probability of occurring is kept under an acceptable value may differ according to the various cryptographic processes used in various embodiments (e.g., different modes of AES and, generally, different ciphers and ways of using ciphers) and/or according to various tolerance for risk of such events occurring. For instance, values may be modified so that more operations, on average, are performable between key rotations for data that is considered less sensitive than other data for which fewer operations are, on average, performable for data that is considered more sensitive. As another example, the random number R may also be used in performance of the cryptographic operation. For example, R may be the nonce used in a cipher that uses nonces. As another example, the nonce used in a cipher that uses nonces may be generated using a function that takes R as input. As one example, the nonce may be a specified number of trailing digits of R. Generally, R may be used as input to a cryptographic process involving the key.
Various enhancements to the techniques described herein are usable to improve system performance and efficiency. For example, in a distributed system where a key is shared among numerous devices of the system, key rotation can be a complex process, especially when measures are taken to ensure that data is encrypted using a proper key. Adaptations to the processes described herein may be made to ensure, on average, a larger number of operations using a key before the key is rotated. FIG. 7, for instance, shows an illustrative example of a process 700 which may be performed to manage rotation of cryptographic keys in accordance with various embodiments. As illustrated, the process 700 illustrated in FIG. 7 is a variation of the process 600 described above with FIG. 6. As illustrated in FIG. 7 the process 700 includes receiving 702 a request to perform a cryptographic operation using a key where the request may be received and configured such as described above. Similarly, the process 700 includes causing 704 the request to be processed and calculating 706 a random number R, where R may be as described above in connection with FIG. 6.
As with the process 600 described above in connection with FIG. 6, the process 700 illustrated in FIG. 7 includes determining 708 whether the random number R is equivalent to zero modulo K. If it is determined 708 that the random number R is equivalent to zero modulo K, instead of rotating the key as illustrated in FIG. 6, the process 700 includes updating 710, a counter. In this example, the counter is a probabilistic counter since the counter is updated upon the occurrence of an event that has a probability less than one of occurring. The counter may be maintained centrally, such as by a security module coordinator described above in connection with FIG. 3 or by another component of a cryptography service or other system that performs cryptographic operations. Accordingly, updating the counter may include transmitting a request to the component maintaining the counter to update the counter.
A determination may then be made 712 whether the counter has met a threshold. If it is determined 712 that the counter has reached the threshold the key may be rotated 714 such as described above. If it is determined 708 that the random number R is not equivalent to zero modulo K or if it is determined 712 that the counter has not reach the threshold, the process 700 may be repeated such as described above so that the key may be continued to be used for additional operations until it is both determined 708, 712 that the random number R is equivalent to zero modulo K and that the counter has reached the threshold. In this manner, a counter is maintained for the key without having to account for every operation in which the key is performed, thereby reducing the burden of maintaining a counter and allowing on average more operations to be performed before the key is rotated.
In the process 700 described above in connection with FIG. 7, let P1(i) be the probability of the counter having a value T (T an integer), given i operations performed using the key. In other words, P1(i) can be expressed as the probability of updating the counter T−1 times in the first i−1 operations multiplied by the probability of updating the counter to T on the ith operation. The probability of updating the counter T−1 times in the first i−1 operations follows a binomial distribution and the probability of updating the counter on the ith operation is, in this example, 1/K. Therefore, P1(i) can be expressed as:
P 1 ⁡ ( i ) = { ( i - 1 T - 1 ) ⁢ ( 1 K ) T ⁢ ( K - 1 K ) i - T if ⁢ ⁢ T ≤ i 0 if ⁢ ⁢ T > i
If P2(i) represents the probability of a repeated nonce after i consecutive operations using the same key, as described as above, then T and K can be selected such that
which represents the probability that there will be a repeated nonce before a key rotation is performed, is within an acceptable limit, such as described above. In some embodiments, T is selected based on practical considerations, such as based on a decision how often the counter can be updated without unduly burdening the system, and K can be computed based on the selected value of T. Similarly, K may be selected and a value for T may be computed. Computing a value for K or T may be performed in any suitable manner, which may include using functions that approximate the various components of the mathematical expressions above (or otherwise used) but that are computationally easier to calculate.
As noted above, variations are considered as being within the scope of the present disclosure. For instance, the above formulas represent probabilities in accordance with specific embodiments. Different formulas may be used for different systems, different cryptographic ciphers, different security concerns, different levels of acceptable risk, and the like. In addition, as noted, various embodiments of the present disclosure involve rotation of keys that are managed by an entity on behalf of a customer of the entity. In such embodiments, various key rotation parameters may be customizable (e.g., via appropriately configured API calls) so that customers can tailor the average frequency of key rotations as desired. For instance, in some embodiments, customers may customize the acceptable probability of an undesirable event occurring. As another example of a variation considered as being within the scope of the present disclosure, additional probabilities may be taken into account. For instance, as noted above, variations of the present disclosure utilize a probabilistically updated counter. Probability distributions discussed above (which relate to a particular illustrative embodiment) assume that a counter is actually updated when the outcome of a stochastic process satisfies certain conditions. As noted, however, distributed systems may have multiple devices may be involved in a system and multiple devices may utilize techniques described herein (e.g., by making probabilistic key rotation determinations). As a result, a central counter may be maintained and updated over a network by the devices performing the stochastic processes that may result in update to the counter. There may be a nonzero probability of the counter being updated (e.g., due to possible network failure, device failure, etc.) when a device sends a request to a system maintaining the counter to update the counter. This probability may be estimated (e.g., through analysis of logs of past activity) and included into probability distributions as appropriate so that the probability of a counter failing to update does not cause the probability of an undesirable event from occurring from exceeding a desirable value.
As illustrated in FIGS. 5, 6, and 7 various embodiments of the present disclosure determine whether to rotate keys as a result of receiving requests to perform operations using the keys. The illustrative examples provided in FIGS. 5, 6, and 7 make this determination synchronously, that is when triggered by a request that has been received. Variations of the techniques used herein may also be performed asynchronously. For example, FIG. 8 shows an illustrative example of a process 800 which may be used to manage key rotation. Instead of certain operations being performed in response to a receipt of a request to perform an operation, the process 800 is performed independent of any request received. As illustrated in FIG. 8 the process 800 includes accessing 802 request logs, which may be logs that store information related to when requests were performed. For instance, referring to FIG. 3, logs may be accessed from the logging module to access request logs related to a particular key or account corresponding to a particular key. The process 800 may include determining 804 a number of operations performed using the key based at least in part on the information in the accessed request logs. Determining 804 the number of operations performed using the key may be performed in various ways in accordance with various embodiments. For example, in some embodiments the request logs are processed to determine an accurate count of the number of operations that have been performed using the key at the time the logs were last updated. In other embodiments, the requests logs sampled to estimate the number of operations that have been performed using the key.
Once the number of operations has been determined 804 the process 800 may include whether the determined number of operations has reached a threshold number of operations. The threshold may be determined to keep the probability of a particular event from occurring, such as repeated use of a nonce with the same cryptographic key, within an acceptable range. If it determined 806 that the number of operations has reached the threshold the process 800 may include rotating 808 the key such as described above.
Numerous variations of the process 800 may be performed. For example, the frequency at which logs are accessed may vary in accordance with the frequency at which requests to perform operations using a specified key are submitted. To prevent cryptographic key wear out, the frequency at which logs are accessed and analyzed may be set such that, based on past behavior in connection with the key, a customer is unlikely to cause cryptographic key wear out faster than a need to rotate the key is detected based at least in part on analysis of the logs. In other words, the more frequently a key is used, the more frequently logs may be accessed (and/or updated) and analyzed to detect a need to rotate the key before the customer is able to cause cryptographic key wear out. Also, as discussed above, the frequency at which keys are rotated and the frequency at which logs are accessed and analyzed may vary in accordance with the particular type of key wear out for which there is risk. As discussed above, the particular type of key wear out may differ depending on the particular cipher used.
In embodiments utilizing a web server, the web server can run any of a variety of server or mid-tier applications, including Hypertext Transfer Protocol (“HTTP”) servers, FTP servers, Common Gateway Interface (“CGP”) servers, data servers, Java servers and business application servers. The server(s) also may be capable of executing programs or scripts in response to? requests from user devices, such as by executing one or more web applications that may be implemented as one or more scripts or programs written in any programming language, such as Java®, C, C# or C++, or any scripting language, such as Perl, Python or TCL, as well as combinations thereof. The server(s) may also include database servers, including without limitation those commercially available from Oracle®, Microsoft®, Sybase® and IBM®.
obtaining a request to perform an operation, the performance of which involves an encryption operation using a first cryptographic key specified in the request;
causing a device to perform the encryption operation using the first cryptographic key;
determining, based at least in part on a stochastic process, to cause a counter to be updated; and
based at least in part on the counter satisfying a set of key rotation criteria, causing the first cryptographic key to be replaced with a second cryptographic key, the set of key rotation criteria having a probability of being satisfied that is associated with a frequency of key rotation.
the device is a hardware security module of a plurality of hardware security modules with access to the first cryptographic key when the request is received; and
causing the first cryptographic key to be replaced causes each hardware security module of the plurality of hardware security modules to replace the first cryptographic key with the second cryptographic key.
3. The computer-implemented method of claim 1, wherein determining, based at least in part on the stochastic process, to cause the counter to be updated is based at least in part on an output of a random or pseudorandom value generator.
4. The computer-implemented method of claim 1, wherein determining, based at least in part on the stochastic process, to cause the counter to be updated:
generating a value based at least in part on the stochastic process; and
as a result of the value satisfying a counter update condition, incrementing the counter.
5. The computer-implemented method of claim 1, wherein causing the device to perform the encryption operation using the first cryptographic key includes causing the device to use a value generated according to the stochastic process as input into an encryption algorithm.
6. The computer-implemented method of claim 1, wherein the counter satisfying the set of key rotation criteria is based at least in part on the first cryptographic key being used to fulfill at least a threshold number of encryption operations.
memory storing instructions that, as a result of execution by the one or more processors, cause the system to:
obtain a request to perform an operation, the performance of which involves an encryption operation using a first cryptographic key specified in the request;
cause a device to perform the encryption operation using the first cryptographic key;
determine, based at least in part on a stochastic process, to cause a counter to be updated; and
based at least in part on the counter satisfying a set of key rotation criteria, cause the first cryptographic key to be replaced with a second cryptographic key, the set of key rotation criteria having a probability of being satisfied that is associated with a frequency of key rotation.
8. The system of claim 7, wherein the instructions to determine to cause the counter to be updated include instructions that cause the system to:
obtain a stochastically-generated value;
supply the stochastically-generated value as an argument to a probabilistic process that has a known probability of producing a particular outcome; and
produce the particular outcome.
9. The system of claim 8, wherein the probabilistic process comprises determining whether the stochastically-generated value is an integer multiple of a second integer.
10. The system of claim 9, wherein a value of the second integer is selected such that a probability of the stochastically-generated value being the integer multiple of the second integer has a known probability distribution.
the first cryptographic key is accessible to a plurality of devices of the system; and
the instructions that cause the counter to be updated include instructions to submit a second request, to another device of the system, to update the counter.
12. The system of claim 7, wherein instructions to determine to cause the counter to be updated include instructions that cause the system to compare a stochastically-generated value with a threshold value, wherein the threshold value is selected based at least in part on the set of key rotation criteria.
13. A computer-readable storage medium having stored thereon instructions that, as a result of execution by one or more processors of a system, cause the system to:
14. The computer-readable storage medium of claim 13, wherein the first cryptographic key is a cryptographic key of a plurality cryptographic keys managed by the system.
15. The computer-readable storage medium of claim 13, wherein the set of rotation criteria is determined based at least in part on a probability of the counter failing to update.
16. The computer-readable storage medium of claim 13, wherein:
causing the first cryptographic key to be replaced with the second cryptographic key includes causing the second cryptographic key to become accessible to each device of the plurality of devices.
17. The computer-readable storage medium of claim 13, wherein the stochastic process comprises making a non-deterministic determination whether to update the counter.
18. The computer-readable storage medium of claim 13, wherein the set of key rotation criteria comprises the counter exceeding a threshold value.
19. The computer-readable storage medium of claim 13, wherein the instructions to determine, based at least in part on the stochastic process, to cause the counter to be updated include instructions that cause the system to determine whether a stochastically generated value is divisible by another value.
20. The computer-readable storage medium of claim 13, wherein the instructions to determine, based at least in part on the stochastic process, to cause the counter to be updated include instructions that cause the system to determine whether a stochastically generated sequence of bits satisfies one or more conditions on the sequence.
US16/126,735 2013-02-12 2018-09-10 Probabilistic key rotation Active US10382200B2 (en)
US13/764,944 US10467422B1 (en) 2013-02-12 2013-02-12 Automatic key rotation
US13/916,999 US9608813B1 (en) 2013-06-13 2013-06-13 Key rotation techniques
US13/922,946 US9300464B1 (en) 2013-02-12 2013-06-20 Probabilistic key rotation
US15/060,487 US10075295B2 (en) 2013-02-12 2016-03-03 Probabilistic key rotation
US16/126,735 US10382200B2 (en) 2013-02-12 2018-09-10 Probabilistic key rotation
US15/060,487 Continuation US10075295B2 (en) 2013-02-12 2016-03-03 Probabilistic key rotation
US20190007207A1 US20190007207A1 (en) 2019-01-03
US10382200B2 true US10382200B2 (en) 2019-08-13
ID=55537612
US13/922,946 Active 2033-11-10 US9300464B1 (en) 2013-02-12 2013-06-20 Probabilistic key rotation
US15/060,487 Active US10075295B2 (en) 2013-02-12 2016-03-03 Probabilistic key rotation
US16/126,735 Active US10382200B2 (en) 2013-02-12 2018-09-10 Probabilistic key rotation
US (3) US9300464B1 (en)
JP2007507760A (en) 2003-07-18 2007-03-29 ヴォーメトリック インコーポレイテッド Secure cluster configuration dataset transfer protocol
JP2008541273A (en) 2005-05-09 2008-11-20 プロビラ，インク． Cascading security architecture
US20100011448A1 (en) 2008-07-09 2010-01-14 The Go Daddy Group, Inc. Maintaining contact with a document storage file owner
US20100174919A1 (en) 2009-01-08 2010-07-08 Takayuki Ito Program execution apparatus, control method, control program, and integrated circuit
US20140201533A1 (en) 2012-10-29 2014-07-17 Empire Technology Development Llc Quorum-based virtual machine security
2013-06-20 US US13/922,946 patent/US9300464B1/en active Active
2016-03-03 US US15/060,487 patent/US10075295B2/en active Active
2018-09-10 US US16/126,735 patent/US10382200B2/en active Active
JP2014501955A (en) 2010-11-04 2014-01-23 シルバー スプリング ネットワークス インコーポレイテッドＳｉｌｖｅｒ Ｓｐｒｉｎｇ Ｎｅｔｗｏｒｋｓ， Ｉｎｃ． Physically secure authorization for utility applications
Australian Examination Report No. 2, dated Mar. 5, 2019, for Patent Application No. 2017204853, 3 pages.
Barker et al., "Recommendation for Random Number Generation Using Deterministic Random Bit Generators," National Institute Standards and Technology Special Publication 800-90A, Jan. 2012, 136 pages.
Canadian Office Action for Patent Application No. 2,899,008 dated Mar. 14, 2018, 4 pages.
Canadian Office Action for Patent Application No. 2,899,019 dated Jul. 3, 2018, 8 pages.
Canadian Office Action for Patent Application No. 2,899,027 dated Jul. 17, 2018, 6 pages.
Chinese Notice on Grant of Patent for Application No. 201480020500.X dated Dec. 28, 2017, 4 pages.
Chinese Second Office Action for Patent Application No. 201480020482.5 dated Jul. 19, 2018, 28 pages.
Chinese Second Office Action, dated Sep. 25, 2018, for Patent Application No. 201480013039.5, 11 pages.
Chinese Third Office Action for Patent Application No. 201480020517.5 dated Jul. 25, 2018, 6 pages.
European Communication pursuant to Article 94(3) EPC for Patent Application No. 14751237.0 dated May 28, 2018, 4 pages.
European Communication pursuant to Article 94(3) EPC for Patent Application No. 14751612.4 dated Jan. 3, 2018, 4 pages.
European Communication pursuant to Article 94(3) EPC for Patent Application No. 14751881.5 dated Oct. 25, 2018, 5 pages.
European Official Communication Pursuant to Article 94(3) EPC for Patent Application No. 14751256.0 dated Jan. 3, 2018, 5 pages.
Japanese Appeal Decision for Patent Application No. 2016-511994 dated Mar. 12, 2019, 3 pages.
Japanese Final Decision of Rejection for Patent Application No. 2015-558056 dated Mar. 13, 2018, 18 pages.
Japanese Final Decision on Rejection for Patent Application No. 2015-558070 dated Apr. 3, 2018, 7 pages.
Japanese Notice and Report for Revocation of Reconsideration Report for Patent Application No. 2015-558043 dated Mar. 9, 2018, 6 pages.
Japanese Notice of Allowance for Patent Application No. 2015-558056, dated Oct. 2, 2018, 6 pages.
Japanese Notice of Rejection for Patent Application No. 2017-217362 dated Feb. 12, 2019, 9 pages.
Japanese Notice of Rejection, dated Oct. 4, 2018, for Patent Application No. 2017-017908, 25 pages.
Japanese Notice of Revocation for Reconsideration and Report, dated Dec. 4, 2018, for Patent Application No. 2015-558070, 4 pages.
Japanese Report on Notice of Allowance for Patent Application No. 2015-558044 dated Mar. 27, 2018, 6 pages.
Olexiy et al., "Starting Share Files with NFS," Linux Journal, dated Jan. 1, 2002, retrieved on Jan. 2, 2018, from http://www.linuxjournal.com/article/4880?page=0,0, 13 pages.
Stack Exchange, "Storing secrets in software," by ninefingers, Stack Exchange Security Blog, dated Sep. 6, 2011, retrieved on Jan. 2, 2018, from http://security.blogoverflow.com/2011/09/storing-secrets-in-software/, 3 pages.
US20190007207A1 (en) 2019-01-03
US20160191237A1 (en) 2016-06-30
US9300464B1 (en) 2016-03-29
US10075295B2 (en) 2018-09-11
WO2009055434A1 (en) 2009-04-30 User-centric authentication system and method
CN102609640A (en) 2012-07-25 Secure data parser method and system
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ROTH, GREGORY BRANCHEK;REEL/FRAME:046831/0256