Searching for secret data through an untrusted searcher

Embodiments of the present invention relate to searching for secret data through an untrusted searcher without exposing the secret data. In one embodiment, a method of and computer program product for searching for secret data through an untrusted searcher is provided. A secret value is read from a storage medium. The secret value is divided into a plurality of portions. Each of the plurality of portions is ranked. A subset of the secret value is determined from the ranking of the plurality of portions. A search string is constructed from the subset. The search string is transmitted to a searcher via a network. Search results are received from the searcher via the network. The search results are compared to the secret value to determine whether the searcher found the secret value.

BACKGROUND

Embodiments of the present invention relate to detecting leaked secret data, and more specifically, to searching for secret data through an untrusted searcher without exposing the secret data.

BRIEF SUMMARY

According to one embodiment of the present invention, a method of and computer program product for searching for secret data through an untrusted searcher is provided. A secret value is read from a storage medium. A plurality of portions is extracted from the secret value. Each of the plurality of portions is ranked. A subset of the secret value is determined from the ranking of the plurality of portions. A search string is constructed from the subset. The search string is transmitted to a searcher via a network. Search results are received from the searcher via the network. The search results are analyzed to determine whether the searcher found the secret value.

DETAILED DESCRIPTION

Searching for and discovering leaked secret information poses a security risk. In order to enable a searcher to search for leaked information, at least some portion of that leaked information must be disclosed to the searcher. Where the searcher is not the owner of the secret, this exposes the secret information to additional parties and thus creates additional security risks. This problem is particularly pronounced where it is unknown whether the secret information has been leaked or not. In such cases, the secret owner seeking to determine whether there has been a leak risks becoming the leak himself by searching for the secret information.

In the case of Internet searches or searches of large existing data stores, the only feasible search mechanism may be to use a third party. In the case of the Internet, it is not practical to perform a direct inspection of all accessible data. Existing search engines such as Google, Yahoo, Baidu or Bing may be the most effective and efficient means to perform a search. In addition, certain data repositories may be searchable only through a proprietary search mechanism. For example, a bulletin board system may be searchable only through a search tool provided by that bulletin board system. In such cases, submitting a search for secret information not only exposes the secret information to the search engine, but to any eavesdroppers, caches, or proxies. This exposure may be exacerbated by features such as autocorrect and autocomplete, which offer to subsequent visitors to a search engine suggested searches based on prior searches. Secret information that was previously the subject of a search may thereby be offered to another visitor. This highlights the fact that once a search engine has received a search term, it may republish that search term alone or in compilation (e.g., in a top searches list).

Despite the security risks, use of automated third party search may be desirable to provide ongoing detection of leaks. In addition, the use of a third party searcher may allow the secret owner to maintain his anonymity and conceal the fact that he is performing a search at all. Achieving this separation may require the use of a third party searcher.

According to an embodiment of the present invention, knowledge of a complete secret is limited to trusted parties. A trusted party reveals only a part of the secret data to a searcher responsible for finding instances of the secret information. The searcher may be a search engine that has access to document repositories, databases, file systems, web pages, social media outlets, forensic lab equipment, machine-readable memory, network monitor, bus monitor, or other digital resources. Searching may be conducted on a static resource, or may be conducted of ongoing traffic, such as through a network sniffer. The searcher provides to the trusted party additional context surrounding any search hits so that the trusted party may ascertain whether a search hit in fact corresponds with an instance of the entire secret.

In an exemplary embodiment, the secret is a passphrase that grants access to a protected resource. The provider of the passphrase may wish to ensure by regular Internet searches that the passphrase has not been published. However, searching for the entire passphrase may reveal the passphrase to the searcher and any intermediaries.

A passphrase may, for example, be a sequence of standard English words. Although each individual word is known, the particular sequence is unique and is used to control access to a protected system. An Internet search for an individual word may result in false hits. However, a search for certain subsets of the words in the passphrase have a low probability of resulting in false hits. Various subsets may be chosen for the search. The subset may be a subsequence of consecutive words drawn from the passphrase. The subset may comprise words in random order that appeared consecutively in the passphrase. The subset may also represent a random selection of words from the passphrase.

Each potential subset has different characteristics with regard to security and hit rate. For example, searching for an ordered subsequence of the passphrase may have a low probability of false hits, but reveals a substantial amount of information about the passphrase. If multiple different searches are conducted, an observer may be able to reconstruct the entire passphrase by stitching together the various search strings. In contrast, searching for a single word in the passphrase is likely to result in a large number of false hits, but reveals very little about the passphrase. A random subset of the passphrase, in random order, likewise reveals little about the passphrase. However, the size of the subset and the particular words included may have a substantial impact on the number of false hits. For example, the two words “green” and “apple” may appear in a highly unique passphrase, but also appear together in a large number of unrelated contexts.

In another exemplary embodiment, the secret is a document. The document may be either confidential or embargoed. The owner of the document may wish to regularly check that the document has not been revealed. Searching for the entire document not only has the drawbacks discussed above, but may be impractical due to variations between various document formats. For example, punctuation, pagination, or newline characters may vary between formats without changing the essential content. By searching for a subset of the document, the nature and content of the document may remain concealed.

In another exemplary embodiment, the secret is a numeric value. A numeric value may be expressed according to various encodings, including base 2 (binary), base 10 (decimal), base 16 (hexadecimal) or base 64. In such embodiments, the searcher is provided with a subsequence of the digits of the secret according to one or more encoding.

In some embodiments, the secret owner specifies to the searcher the type of context to be collected regarding each candidate hit. The specification may include an amount of content to be included around the potential hit. The specification may also include a request for metadata, such as date of publication, URL of publication, overall content size, content language, or other characteristics of the content in which the candidate hit occurs.

In some embodiments, the secret owner provides additional information regarding the secret sought. This information may include the semantic data type of the search string, e.g., a name, a string, a binary blob, a number, a date, or a location. The searcher may use this information to aid in searching for the secret. In some embodiments, the searcher may use the semantic information to determine what variations of the search string may be matches. For example, a search string “05272013” that is known to be a date may match May 27, 2013 as well as various other potential formats of the same information.

Turning now toFIG. 1, an exemplary data flow is provided. Secret owner101is in possession of a secret102. A subset103of secret102is generated. The subset103is transformed into a search string104appropriate for searcher105. In some embodiments, the search string may comprise operators that are specific to the searcher, such as Boolean operators or proximity operators. In some embodiments, secret owner101includes a blacklist106that contains entities to be excluded from the search string. In some embodiments, search string104includes exclusion operators based on the contents of blacklist106. In other embodiments, blacklist106is compared to subset103, and a new subset is generated if there are too many blacklisted terms.

Secret owner101sends search request107to searcher105. In some embodiments, an intermediary (not pictured) may relay search request107from secret owner101to searcher105. Search request107comprises search string104. In some embodiments, search request107further comprises a context specification108and/or a type specification109. Upon receipt of search request107, searcher105performs a search, and provides search result110back to the requester. Search results110include results string111. In some embodiments, search results110also include result context112, as specified by context specification108.

Secret owner101takes secret102and search results110, and performs a comparison113. The results of the comparison indicate whether a match has been found. Once a match has been found, the secret owner may take further action, such as to change a passphrase that has been leaked. In some embodiments, secret owner101and searcher105communicate via a network. In other embodiments, secret owner101and searcher105are resident in the same computing environment, and communicate through an API, socket, pipe, shared memory, RPC, or other method known in the art.

In some embodiments, deliberate errors are introduced in the search string in order to disguise the secret further. For example, a misspelling may be introduced. If there exists an instance of the search string with the correct spelling, the search engine may provide that proper spelling as a potential hit, despite the variation (e.g., by applying autocorrect). In another example, noise may be introduced into the searches in the form of either additional random searches or additional terms in the search strings. In the case of additional terms in a given search string, the search engine may provide results omitting the superfluous search term if there is a potential hit containing the other terms. In general, where a fuzzy search is used to search for the secret, the search string may be crafted to be within the tolerance of the search engine without necessarily being the precise string sought.

In some embodiments, ranking heuristics are applied to select the search string that is least likely to lead to false hits for the secret. In general, these are the values that are least likely to occur randomly, and are least known. For example, in an embodiment using passphrases, the words “the”, “be”, “to”, “of” and “and” appear so frequently in English as to be likely sources of false hits. Therefore, less common words or word combinations are preferred for inclusion in the search string. In an embodiment using numerical values, the values 0x00, 0xff, and 0xdeadbeef are likely sources of false hits, as are hexadecimal encodings of printable characters. Likewise, numerical values forming simple sequences are also likely sources of false hits (e.g., 0x1234 or 101010).

In some embodiments, the ranking heuristics vary over time. However, ranking heuristics should not be changed in such a way as to gradually reveal the entire secret. In some embodiments, the ranking heuristics applied vary based on the data type of the secret. For example, the string “eeee” may be common in hexadecimal, but uncommon in standard English.

In some embodiments, there are several heuristics applied to candidate search strings, and a best result is chosen from among them. The choice among heuristics may be based on voting among the results. In some embodiments, the various heuristics are weighted and applied according to their respective weights. In other embodiments, the various heuristics have relative priorities and are applied in the order of priority.

In some embodiments, a blacklist is applied to any candidate search string. Once a heuristic is applied to select candidate search strings, they are screened against a list of frequently occurring subsets. For example, seemingly random strings that appear frequently despite their apparent randomness may be added to the blacklist.

In some embodiments, a secret is screened against one or more of the above discussed heuristics to determine whether it is suitable for searching. If the passphrase proves to be unsuitable for search because it is likely to generate many false positives, a new passphrase may be generated in its place. In some embodiments, the passphrase is presented to a user, and they may accept or reject that passphrase. If the user rejects the passphrase, a new passphrase is generated as discussed above. In other embodiments, a user provides the candidate passphrase, which is then screened as discussed above.

In one exemplary embodiment, a ranking function for hexadecimal values is provided. Repeated hex digits are counted in each subset, and the sum of the squares of the counts is computed for each subset. If two subsets have the same value, then the tie is broken by the squares of count-of-relative-distances. If still tied (not shown), then a pseudorandom function may be applied to each subset to determine relative value. If still tied (not shown), the first occurring subset in the secret is chosen. Exemplary pseudocode is provided below at Inset 1.

In another exemplary embodiment, a ranking function for passphrases is provided. The sum of the squares of word counts are calculated based on a dictionary of word frequencies. The lowest scoring subset of the passphrase is selected as the least likely to result in false hits.

In some embodiments, where the secret is random, a fixed subset may be selected without the application of a ranking function. For example, a fixed length substring may be selected at a fixed offset from the start of the secret string.

Turning toFIG. 2, an exemplary method according to an embodiment of the present disclosure is provided. A secret is divided into segments201. A subset of those segments is selected202. A search string is generated based on that subset203. The search string is submitted to a searcher204. Search results are received from the searcher205. The results are compared to the secret to determine whether the secret was found206.