Data recovery through reversal of hash values using probabilistic data structures

Abstract

Systems and methods for recovering passwords from a hash value input are provided. A password space may be segmented into password sets, and a digest set may be generated for each password set. Probabilistic data structures representing the digest sets may be generated. One of the probabilistic data structures may be queried with the hash value input to determine whether the hash value input is likely included in the digest sets. In response to the hash value input being determined to be likely included in the digest set, the passwords constituting the password set corresponding to the digest set may be regenerated, and the hash values constituting the digest set may be regenerated. The generated hash values may be compared to the hash value input to determine a hash value from the digest set that matches the hash value input to recover the password associated with the matched hash value.

1 . A method for recovering a password from a hash value input, the method comprising:
 querying a probabilistic data structure with the hash value input wherein the probabilistic data structure represents a digest set, comprising hash values of respective passwords in a password set;   receiving, in response to the querying of the probabilistic data structure, result data from the probabilistic data structure indicating that the hash value input is likely included in the digest set represented by the probabilistic data structure;   in response to receiving the result data indicating that the hash value input is likely included in the digest set represented by the probabilistic data structure, generating and storing the passwords of the password set, and generating and storing the hash values of the digest set;   comparing one or more of the generated hash values constituting the digest set to the hash value input to determine a hash value from among the generated hash values that matches the hash value input;   determining a generated password, from among the generated passwords, associated with the determined hash value that matches the has value input; and   generating and outputting an indication of the generated password associated with the generated hash value that matches the hash value input.   
     
     
         2 . The method of  claim 1 , wherein the password set comprises a contiguous portion of a password space as defined by a plurality of rules governing password eligibility and by a predefined ordering criteria. 
     
     
         3 . The method of  claim 2 , wherein the password space comprises all possible passwords in accordance with the plurality of rules governing password eligibility. 
     
     
         4 . The method of  claim 2 , wherein passwords in the password space are arranged in an order in accordance with the one or more predefined ordering criteria. 
     
     
         5 . The method of  claim 1 , wherein the digest set is generated at least in part by calculating a respective hash value for each password of the password set. 
     
     
         6 . The method of  claim 1 , wherein the probabilistic data structure is generated at least in part by selecting a predefined false-positive probability for queries of the probabilistic data structure. 
     
     
         7 . The method of  claim 6 , wherein selecting the predefined false-positive probability is based on a size of storage resources on which the probabilistic data structure is to be stored. 
     
     
         8 . The method of  claim 1 , comprising:
 segmenting a password space into a plurality of password sets including the password set, wherein each of the password sets comprises a respective plurality of passwords in the password space;   generating and storing a plurality of respective digest sets, including the digest set for each password set of the plurality of password sets, wherein each of the plurality of digest sets comprises a respective set of hash values of each of the respective passwords in the corresponding associated password set; and   generating and storing a plurality of probabilistic data structures, including the probabilistic data structure, wherein each of the plurality of probabilistic data structures represents a respective one of the plurality of the digest sets.   
     
     
         9 . The method of  claim 1 , wherein the probabilistic data structure is configured to generate result data indicating either:
 that the query input value is likely included in the digest set represented by the probabilistic data structure, or   that the query input value is definitely not included in the digest set represented by the probabilistic data structure.   
     
     
         10 . The method of  claim 1 , wherein the probabilistic data structure is a Bloom filter. 
     
     
         11 . The method of  claim 1 , wherein querying the probabilistic data structure is performed as part of querying a plurality of probabilistic data structures of a multi-level probabilistic data structure, wherein the multi-level probabilistic data structure comprises a tree-structure of probabilistic data structures in which probabilistic data structures in a first level are each associated with multiple probabilistic data structures in a second level. 
     
     
         12 . The method of  claim 11 , wherein:
 each of the probabilistic data structures in the second level represents a single respective digest set; and   each of the probabilistic data structures in the first level represents all of the digest sets represented by a set of multiple probabilistic data structures in the second level.   
     
     
         13 . The method of  claim 11 , wherein querying the plurality of probabilistic data structures of the multi-level probabilistic data structure comprises:
 querying, with the hash value input, a first-level probabilistic data structure of the first level of the multi-level probabilistic data structure;   receiving, in response to the querying of the first-level probabilistic data structure, result data indicating that the hash value input is likely included in one of a set of multiple digest sets represented by the first-level probabilistic data structure;   in accordance with receiving the result data indicating that the hash value input is likely included in one of a set of multiple digest sets represented by the first-level probabilistic data structure, querying a set of multiple second-level probabilistic data structures, including the probabilistic data structure, of the second level of the multi-level probabilistic data structure.   
     
     
         14 . The method of  claim 11 , wherein:
 probabilistic data structures in the first level are configured to have a first false-positive rate; and   probabilistic data structures in the second level are configured to have a second false-positive rate different from the first false-positive rate   
     
     
         15 . A system for recovering a password from a hash value input, the system comprising:
 one or more processors;   a memory storing one or more programs, the one or more programs configured to be executed by the one or more processors and including instructions to:
 query a probabilistic data structure with the hash value input, wherein the probabilistic data structure represents a digest set comprising hash values of respective passwords in a password set; 
 receive, in response to the querying of the probabilistic data structure, result data from the probabilistic data structure indicating that the hash value input is likely included in the digest set represented by the probabilistic data structure; 
 in response to receiving the result data indicating that the hash value input is likely included in the digest set represented by the probabilistic data structure, generate and store the passwords of the password set, and generating and storing the hash values of the digest set; 
 compare one or more of the generated hash values to the hash value input to determine a hash value from among the generated hash values that matches the hash value input; 
 determine a generated password, from among the generated passwords, associated with the determined hash value that matches the has value input; and 
 generating and outputting an indication of the generated password associated with the generated hash value that matches the hash value input. 
   
     
     
         16 . The system of  claim 15 , wherein the one or more programs include instructions to:
 segment a password space into a plurality of password sets including the password set, wherein each of the password sets comprises a respective plurality of passwords in the password space;   generate and store a plurality of respective digest sets, including the digest set for each password set of the plurality of password sets, wherein each of the plurality of digest sets comprises a respective set of hash values of each of the respective passwords in the corresponding associated password set; and   generate and store a plurality of probabilistic data structures, including the probabilistic data structure, wherein each of the plurality of probabilistic data structures represents a respective one of the plurality of the digest sets.   
     
     
         17 . The system of  claim 15 , wherein querying the probabilistic data structure is performed as part of querying a plurality of probabilistic data structures of a multi-level probabilistic data structure, wherein the multi-level probabilistic data structure comprises a tree-structure of probabilistic data structures in which probabilistic data structures in a first level are each associated with multiple probabilistic data structures in a second level. 
     
     
         18 . A non-transitory computer-readable storage medium storing one or more programs for recovering a password from a hash value input, the one or more programs configured to be executed by one or more processors and including instructions to:
 query a probabilistic data structure with the hash value input, wherein the probabilistic data structure represents a digest set comprising hash values of respective passwords in a password set;   receive, in response to the querying of the probabilistic data structure, result data from the probabilistic data structure indicating that the hash value input is likely included in the digest set represented by the probabilistic data structure;   in response to receiving the result data indicating that the hash value input is likely included in the digest set represented by the probabilistic data structure, generate and store the passwords of the password set, and generating and storing the hash values of the digest set;   compare one or more of the generated hash values to the hash value input to determine a hash value from among the generated hash values that matches the hash value input;   determine a generated password, from among the generated passwords, associated with the determined hash value that matches the has value input; and   generating and outputting an indication of the generated password associated with the generated hash value that matches the hash value input.   
     
     
         19 . The non-transitory computer-readable storage medium of  claim 18 , wherein the one or more programs configured to be executed by one or more processors and including instructions to:
 segment a password space into a plurality of password sets including the password set, wherein each of the password sets comprises a respective plurality of passwords in the password space;   generate and store a plurality of respective digest sets, including the digest set for each password set of the plurality of password sets, wherein each of the plurality of digest sets comprises a respective set of hash values of each of the respective passwords in the corresponding associated password set; and   generate and store a plurality of probabilistic data structures, including the probabilistic data structure, wherein each of the plurality of probabilistic data structures represents a respective one of the plurality of the digest sets.   
     
     
         20 . The non-transitory computer-readable storage medium of  claim 18 , wherein querying the probabilistic data structure is performed as part of querying a plurality of probabilistic data structures of a multi-level probabilistic data structure, wherein the multi-level probabilistic data structure comprises a tree-structure of probabilistic data structures in which probabilistic data structures in a first level are each associated with multiple probabilistic data structures in a second level.