Assessing cryptographic entropy
View Patent ↗Systems, methods, software, and combinations thereof for evaluating entropy in a cryptography system are described. In some aspects, sample values are produced by an entropy source system. A typicality can be determined for each of the sample values. A grading is determined for preselected distributions based on the typicalities of the sample values. A subset of the preselected distributions are selected based on the gradings. An entropy of the entropy source system is calculated based on the subset of the plurality of distributions.
1. A method for assessing entropy in a cryptography system, the method comprising:
obtaining, by a hardware data processing apparatus, a plurality of sample values produced by an entropy source system;
determining, by the hardware data processing apparatus, a typicality grading for each of a preselected plurality of probability distributions, the typicality gradings providing a comparison among the plurality of probability distributions, the typicality grading for each individual probability distribution being determined based on the respective probabilities of selecting the plurality of sample values from that individual probability distribution, wherein the typicality grading for each individual probability distribution is determined based on a cumulative probability with respect to that individual probability distribution, and determining the typicality grading for each individual probability distribution comprises calculating
∑
y
:
P
p
(
y
)
≤
P
p
(
x
)
P
p
(
y
)
,
where P p (x) represents a probability of a sample value x of the plurality of sample values according to the individual probability distribution p, and y:P p (y)≤P p (x) represents values that are at most as probable as the sample value x;
selecting, by the hardware data processing apparatus, a subset of the plurality of probability distributions based on the typicality gradings;
calculating, by the hardware data processing apparatus, an entropy of the entropy source system based on the subset of the plurality of probability distributions, wherein the calculated entropy is used to determine a security risk of the entropy source system;
determining, by the hardware data processing apparatus, whether the entropy source system has adequate entropy to achieve a specified security level in the cryptography system;
modifying, by the hardware data processing apparatus, the entropy source system based on a determination that the entropy source system has inadequate entropy;
encrypting, by the hardware data processing apparatus, a message using the modified entropy source system; and
transmitting, by the hardware data processing apparatus, the encrypted message.
2. The method of claim 1 , wherein determining the typicality gradings includes determining typicalities for each of the sample values.
3. The method of claim 2 , wherein the typicality for a given sample value indicates a probability that a randomly-selected sample value from the entropy source system is at most as probable as the given sample value.
4. The method of claim 1 , wherein encrypting the message using the modified entropy source system comprises:
seeding a pseudorandom number generator based on a sample value produced by the modified entropy source system;
obtaining a cryptographic secret based on an output of the seeded pseudorandom number generator; and
encrypting the message using the cryptographic secret.
5. The method of claim 1 , comprising determining a typicality and a likelihood for each of the sample values, wherein the typicality gradings are determined based on the typicalities of the sample values and the likelihoods of the sample values.
6. The method of claim 1 , wherein selecting a subset of the plurality of probability distributions based on the typicality gradings includes at least one of:
selecting one or more probability distributions having a maximum typicality grading; or
selecting one or more probability distributions having a typicality grading above a specified threshold typicality grading.
7. The method of claim 1 , wherein calculating the entropy includes:
identifying side channel information and computational resources available to an adversary;
determining, for each probability distribution in the subset of the plurality of probability distributions, a logarithm of a maximal probability of the adversary guessing a cryptographic secret using the side channel information and the computational resources available to the adversary; and
identifying as the entropy a minimal value of the logarithms determined for the subset of the plurality of probability distributions.
8. A hardware data processing apparatus comprising:
an entropy source component;
an entropy-assessor component operable to:
obtain, by the hardware data processing apparatus, a plurality of sample values produced by the entropy source component;
determine, by the hardware data processing apparatus, a typicality grading for each of a preselected plurality of probability distributions, the typicality gradings providing a comparison among the plurality of probability distributions, the typicality grading for each individual probability distribution being determined based on the respective probabilities of selecting the plurality of sample values from that individual probability distribution, wherein the typicality grading for each individual probability distribution is determined based on a cumulative probability with respect to that individual probability distribution, and determining the typicality grading for each individual probability distribution comprises calculating
∑
y
:
P
p
(
y
)
≤
P
p
(
x
)
P
p
(
y
)
,
where P p (x) represents a probability of a sample value x of the plurality of sample values according to the individual probability distribution p, and y:P p (y)≤P p (x) represents values that are at most as probable as the sample value x;
select, by the hardware data processing apparatus, a subset of the plurality of probability distributions based on the typicality gradings;
calculate, by the hardware data processing apparatus, an entropy of the entropy source component based on the subset of the plurality of probability distributions, wherein the calculated entropy is used to determine a security risk of the entropy source component;
determine, by the hardware data processing apparatus, whether the entropy source component is configured to produce adequate entropy for a specified security level in a cryptography system; and
modify, by the hardware data processing apparatus, the entropy source component based on a determination that the entropy source component is not configured to produce adequate entropy; and
a cryptographic communication component operable to:
encrypt, by the hardware data processing apparatus, a message using the modified entropy source system; and
transmit, by the hardware data processing apparatus, the encrypted message.
9. The hardware data processing apparatus of claim 8 , further comprising:
a cryptographic secret generator component seeded based on a value produced by the modified entropy source component; and
wherein the cryptographic communication component is further operable to:
obtain a cryptographic secret from the cryptographic secret generator component; and
encrypt the message using the cryptographic secret.
10. The hardware data processing apparatus of claim 8 , the entropy-assessor component being operable to determine a typicality and a likelihood for each of the sample values, wherein the typicality gradings are determined based on the typicalities of the sample values and the likelihoods of the sample values.
11. The hardware data processing apparatus of claim 8 , wherein calculating the entropy includes:
identifying side channel information and computational resources available to an adversary;
determining, for each of the subset of the plurality of probability distributions, a logarithm of a maximal probability of the adversary guessing a cryptographic secret using the side channel information and the computational resources available to the adversary; and
identifying as the entropy a minimal value of the logarithms determined for the subset of the plurality of probability distributions.
12. A non-transitory computer-readable medium comprising instructions for assessing entropy in a cryptography system, the instructions operable to perform operations when executed by a hardware data processing apparatus, the operations comprising:
obtaining, by the hardware data processing apparatus, a plurality of sample values produced by an entropy source system;
determining, by the hardware data processing apparatus, a typicality grading for each of a preselected plurality of probability distributions, the typicality gradings providing a comparison among the plurality of probability distributions, the typicality grading for each individual probability distribution being determined based on the respective probabilities of selecting the plurality of sample values from that individual probability distribution, wherein the typicality grading for each individual probability distribution is determined based on a cumulative probability with respect to that individual probability distribution, and determining the typicality grading for each individual probability distribution comprises calculating
∑
y
:
P
p
(
y
)
≤
P
p
(
x
)
P
p
(
y
)
,
where P p (x) represents a probability of the sample value x of the plurality of sample values according to the individual probability distribution p, and y:P p (y)≤P p (x) represents values that are at most as probable as the sample value x;
selecting, by the hardware data processing apparatus, a subset of the plurality of probability distributions based on the typicality gradings;
calculating, by the hardware data processing apparatus, an entropy of the entropy source system based on the subset of the plurality of probability distributions, wherein the calculated entropy is used to determine a security risk of the entropy source system;
determining, by the hardware data processing apparatus, whether the entropy source system has adequate entropy to achieve a specified security level in the cryptography system;
modifying, by the hardware data processing apparatus, the entropy source system based on a determination that the entropy source system has inadequate entropy;
encrypting, by the hardware data processing apparatus, a message using the modified entropy source system; and
transmitting, by the hardware data processing apparatus, the encrypted message.
13. The computer-readable medium of claim 12 , wherein determining a typicality grading includes determining typicalities for each of the sample values, and the typicality for a given sample value indicates a probability that a randomly-selected sample value from the entropy source system is at most as probable as the given sample value.
14. The computer-readable medium of claim 12 , wherein encrypting the message using the modified entropy source system comprises:
seeding a pseudorandom number generator based on a sample value produced by the modified entropy source system;
obtaining a cryptographic secret based on an output of the seeded pseudorandom number generator; and
encrypting the message using the cryptographic secret.
15. The computer-readable medium of claim 12 , the operations comprising determining a typicality and a likelihood for each of the sample values, wherein the typicality gradings are determined based on the typicalities of the sample values and the likelihoods of the sample values.
16. The computer-readable medium of claim 12 , wherein selecting a subset of the plurality of probability distributions based on the typicality gradings includes at least one of:
selecting one or more probability distributions having a maximum grading; or
selecting one or more probability distributions having a grading above a specified threshold grading.
17. The computer-readable medium of claim 12 , wherein calculating the entropy includes:
identifying side channel information and computational resources available to an adversary;
determining, for each of the subset of the plurality of probability distributions, a logarithm of a maximal probability of the adversary guessing a cryptographic secret using the side channel information and the computational resources available to the adversary; and
identifying as the entropy a minimal value of the logarithms determined for the subset of the plurality of probability distributions.