Data recovery through reversal of hash values using probabilistic data structures
Inventors
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Assignees
Member
NoblisNoblis is a nonprofit research and technical organization supporting federal missions in defense, health, environment, and security. Emphasizing applied sciences, engineering, digital transformation, artificial intelligence, cloud, and cybersecurity, Noblis provides objective solutions for government agencies confronting complex operational and scientific challenges.
Noblis is a nonprofit research and technical organization supporting federal missions in defense, health, environment, and security. Emphasizing applied sciences, engineering, digital transformation, artificial intelligence, cloud, and cybersecurity, Noblis provides objective solutions for government agencies confronting complex operational and scientific challenges.
Publication Number
US-11055399-B2
Publication Date
2021-07-06
Expiration Date
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.
Core Innovation
The invention relates to recovering a password from a hash value input by segmenting a password space into a plurality of password sets. Each password set comprises a plurality of passwords, and for each password set a corresponding digest set is generated and stored. Each digest set comprises a respective hash value of each of the respective passwords in the corresponding password set.
The invention further generates and stores a plurality of probabilistic data structures, where each probabilistic data structure represents one of the digest sets. Generating each probabilistic data structure includes selecting a predefined false-positive probability for queries based on a size of storage resources on which the probabilistic data structure is stored. The probabilistic data structures are then queried with the hash value input to determine whether the hash value input is likely included in the digest sets represented by the probabilistic data structures.
In response to receiving result data indicating the hash value input is likely included in a digest set, the invention generates and stores the passwords constituting the password set corresponding to the digest set and generates and stores the hash values constituting the digest set. The generated hash values are compared to the hash value input to determine a matching hash value from among the digest set, and an indication of the generated password associated with the matching hash value is generated and output. In some embodiments, the invention uses a multi-level probabilistic data structure to query likely included digest sets in a hierarchical manner and to narrow the candidate digest sets.
Claims Coverage
The independent claims cover a method and corresponding implementations (system and non-transitory computer-readable storage medium) for recovering a password from a hash value input. Across the independent claims, the main inventive features include segmenting the password space into password sets, generating and storing digest sets of hash values, and using probabilistic data structures configured by predefined false-positive probabilities to identify likely digest-set membership before regenerating candidates and performing hash comparisons. Additional independent claims further refine the probabilistic lookup using a multi-level probabilistic data structure with hierarchical querying.
Recovering a password using probabilistic membership querying for digest sets
Segmenting a password space into a plurality of password sets; generating and storing a digest set for each password set, where each digest set comprises a respective hash value of each password in the password set; generating and storing a plurality of probabilistic data structures representing the digest sets, wherein generating each probabilistic data structure comprises selecting a predefined false-positive probability for queries based on a size of storage resources; querying one of the probabilistic data structures with the hash value input to determine whether the hash value input is likely included in the digest sets; receiving result data indicating the hash value input is likely included in the digest set; generating and storing the passwords and hash values constituting the digest set in response to the likelihood; comparing generated hash values to the hash value input to determine a matching hash value; and generating and outputting an indication of the generated password associated with the matching hash value.
System implementation using probabilistic membership querying for digest sets
A system comprising one or more processors and memory storing one or more programs configured to segment a password space into password sets, generate and store digest sets of hash values for each password set, generate and store a plurality of probabilistic data structures representing the digest sets with each probabilistic data structure generated by selecting a predefined false-positive probability for queries based on a size of storage resources, query one probabilistic data structure with the hash value input to determine likely included digest sets, receive result data indicating likely inclusion, generate and store the passwords and digest hash values for the corresponding digest set, compare the generated hash values to the hash value input to determine a matching hash value, and generate and output an indication of the generated password associated with the matching hash value.
Multi-level probabilistic digest-set recovery with hierarchical querying
Segmenting a password space into a plurality of password sets; generating and storing a digest set for each password set; generating and storing a multi-level probabilistic data structure including a first plurality of probabilistic data structures in a first level and a second plurality in a second level, where each probabilistic data structure represents one or more of the digest sets and generating each probabilistic data structure comprises selecting a predefined false-positive probability for queries based on a size of storage resources; querying a plurality of probabilistic data structures of the multi-level probabilistic data structure with the hash value input to determine whether the hash value input is likely included in any one or more of the digest sets; receiving result data from an identified probabilistic data structure indicating likely inclusion in the digest set represented by the identified probabilistic data structure; generating and storing the passwords and hash values constituting the digest set; comparing the generated hash values to the hash value input to determine a matching hash value from among the digest set; and generating and outputting an indication of the generated password associated with the matching hash value.
System implementation of multi-level probabilistic digest-set recovery
A system comprising one or more processors and memory storing one or more programs configured to segment a password space into a plurality of password sets, generate and store a digest set for each password set with respective hash values of passwords in the password set, generate and store a first plurality of probabilistic data structures in a first level and a second plurality in a second level of a multi-level probabilistic data structure where each probabilistic data structure represents one or more of the digest sets, and where generating each probabilistic data structure comprises selecting a predefined false-positive probability for queries based on a size of storage resources; query the multi-level probabilistic data structure with the hash value input to determine whether the hash value input is likely included in any one or more digest sets; receive result data from an identified probabilistic data structure indicating the hash value input is likely included in the digest set represented by the identified probabilistic data structure; generate and store the passwords and hash values constituting the digest set; compare the generated hash values to the hash value input to determine a matching hash value; and generate and output an indication of the generated password associated with the matching hash value.
Across the independent claims, the core claim coverage is the recovery workflow that segments a password space into password sets, precomputes digest sets of hash values for each set, and uses probabilistic data structures configured by predefined false-positive probability to identify which digest sets may likely include the hash value input. The claims then regenerate the passwords for the likely digest set, compare regenerated digest hash values to the input hash, and output an indication of the generated password. Additional independent claims cover the same workflow implemented with a multi-level probabilistic data structure for querying digest sets.
Stated Advantages
Speed and storage benefits versus brute-force/dictionary methods.
Documented Applications
Password recovery from a hash value input using probabilistic data structures and digest sets.
Interested in licensing this patent?