Random Number Generation Failure Detection and Entropy Estimation

Abstract

In accordance with one or more aspects, an initial output string is generated by a random number generator. The initial output string is sent to a random number service, and an indication of failure is received from the random number service if the initial output string is the same as a previous initial output string received by the random number service. Operation of the device is ceased in response to the indication of failure. Additionally, entropy estimates for hash values of an entropy source can be generated by an entropy estimation service based on hash values of various entropy source values received by the entropy estimation service. The hash values can be incorporated into an entropy pool of the device, and the entropy estimate of the pool being updated based on the estimated entropy of the entropy source.

What is claimed is: 
     
         1 . A device comprising:
 one or more processors;   one or more computer storage media having stored thereon multiple instructions that, when executed by the one or more processors, cause the one or more processors to:
 generate a hash value for a value of an entropy source of the device; 
 send the hash value to an entropy estimation service; 
 receive, from the entropy estimation service, an entropy estimate for the value that is based on both the hash value and hash values previously received by the entropy estimation service; 
 incorporate the hash value into an entropy pool of the device; and 
 generate a new entropy estimate for the entropy pool based on the entropy estimate for the value. 
   
     
     
         2 . The device as recited in  claim 1 , wherein the hash values previously received by the entropy estimation service include hash values received from additional devices. 
     
     
         3 . The device as recited in  claim 1 , wherein a value H represents the entropy estimate for the entropy source value, a value M represents an occurrence count of the hash value, and a value N represents a total number of hash values for the entropy source received by the entropy estimation service, and wherein the entropy estimate for the value is generated as: 
       
         
           
             
               H 
               = 
               
                 - 
                 
                   
                     
                       log 
                       2 
                     
                      
                     
                       ( 
                       
                         M 
                         N 
                       
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     
         4 . The device as recited in  claim 1 , further comprising determining which one of multiple entropy estimation services to send the hash value to based on the entropy source. 
     
     
         5 . The device as recited in  claim 1 , the multiple instructions further causing the one or more processors to:
 store multiple hash values for multiple values of the entropy source as a set;   reorder the multiple hash values in the set; and   send the set of multiple hash values to the entropy estimation service.   
     
     
         6 . The device as recited in  claim 5 , the multiple instructions further causing the one or more processors to send the set of multiple hash values when an estimate of an expected difficulty in reconstructing an order in which the multiple values of the entropy source occurred is at least a threshold amount. 
     
     
         7 . A method comprising:
 generating a hash value for a value of an entropy source of a device;   sending the hash value to an entropy estimation service;   receiving, from the entropy estimation service, an entropy estimate for the value that is based on both the hash value and hash values previously received by the entropy estimation service;   incorporating the hash value into an entropy pool of the device; and   generating a new entropy estimate for the entropy pool based on the entropy estimate for the value.   
     
     
         8 . The method as recited in  claim 1 , wherein the hash values previously received by the entropy estimation service include hash values received from additional devices. 
     
     
         9 . The method as recited in  claim 1 , wherein a value H represents the entropy estimate for the entropy source value, a value M represents an occurrence count of the hash value, and a value N represents a total number of hash values for the entropy source received by the entropy estimation service, and wherein the entropy estimate for the value is generated as: 
       
         
           
             
               H 
               = 
               
                 - 
                 
                   
                     
                       log 
                       2 
                     
                      
                     
                       ( 
                       
                         M 
                         N 
                       
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     
         10 . The method as recited in  claim 1 , further comprising determining which one of multiple entropy estimation services to send the hash value to based on the entropy source. 
     
     
         11 . The method as recited in  claim 1 , further comprising:
 storing multiple hash values for multiple values of the entropy source as a set;   reordering the multiple hash values in the set; and   sending the set of multiple hash values to the entropy estimation service.   
     
     
         12 . The method as recited in  claim 11 , further comprising sending the set of multiple hash values when an estimate of an expected difficulty in reconstructing an order in which the multiple values of the entropy source occurred is at least a threshold amount. 
     
     
         13 . A device comprising:
 one or more processors;   one or more computer storage media having stored thereon multiple instructions that, when executed by the one or more processors, cause the one or more processors to:
 generate a hash value for a value of an entropy source of the device; 
 send the hash value to an entropy estimation service on the device; 
 receive, from the entropy estimation service, an entropy estimate for the value that is based on both the hash value and hash values previously received by the entropy estimation service on the device; 
 incorporate the hash value into an entropy pool of the device; and 
 generate a new entropy estimate for the entropy pool based on the entropy estimate for the value. 
   
     
     
         14 . The device as recited in  claim 13 , wherein the hash values previously received by the entropy estimation service include hash values received from additional devices. 
     
     
         15 . The device as recited in  claim 13 , wherein a value H represents the entropy estimate for the entropy source value, a value M represents an occurrence count of the hash value, and a value N represents a total number of hash values for the entropy source received by the entropy estimation service, and wherein the entropy estimate for the value is generated as: 
       
         
           
             
               H 
               = 
               
                 - 
                 
                   
                     
                       log 
                       2 
                     
                      
                     
                       ( 
                       
                         M 
                         N 
                       
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     
         16 . The device as recited in  claim 13 , further comprising determining which one of multiple entropy estimation services to send the hash value to based on the entropy source. 
     
     
         17 . The device as recited in  claim 13 , the multiple instructions further causing the one or more processors to:
 store multiple hash values for multiple values of the entropy source as a set;   reorder the multiple hash values in the set; and   send the set of multiple hash values to the entropy estimation service.   
     
     
         18 . The device as recited in  claim 17 , the multiple instructions further causing the one or more processors to send the set of multiple hash values when an estimate of an expected difficulty in reconstructing an order in which the multiple values of the entropy source occurred is at least a threshold amount.