• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Copyright 2019 the gRPC authors.
2#
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7#     http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14"""A search algorithm over the space of all bytestrings."""
15
16from __future__ import absolute_import
17from __future__ import division
18from __future__ import print_function
19
20import base64
21import hashlib
22import itertools
23import logging
24import struct
25
26from examples.python.cancellation import hash_name_pb2
27
28_LOGGER = logging.getLogger(__name__)
29_BYTE_MAX = 255
30
31
32def _get_hamming_distance(a, b):
33    """Calculates hamming distance between strings of equal length."""
34    distance = 0
35    for char_a, char_b in zip(a, b):
36        if char_a != char_b:
37            distance += 1
38    return distance
39
40
41def _get_substring_hamming_distance(candidate, target):
42    """Calculates the minimum hamming distance between between the target
43        and any substring of the candidate.
44
45    Args:
46      candidate: The string whose substrings will be tested.
47      target: The target string.
48
49    Returns:
50      The minimum Hamming distance between candidate and target.
51    """
52    min_distance = None
53    if len(target) > len(candidate):
54        raise ValueError("Candidate must be at least as long as target.")
55    for i in range(len(candidate) - len(target) + 1):
56        distance = _get_hamming_distance(candidate[i:i + len(target)].lower(),
57                                         target.lower())
58        if min_distance is None or distance < min_distance:
59            min_distance = distance
60    return min_distance
61
62
63def _get_hash(secret):
64    hasher = hashlib.sha1()
65    hasher.update(secret)
66    return base64.b64encode(hasher.digest()).decode('ascii')
67
68
69class ResourceLimitExceededError(Exception):
70    """Signifies the request has exceeded configured limits."""
71
72
73def _bytestrings_of_length(length):
74    """Generates a stream containing all bytestrings of a given length.
75
76    Args:
77      length: A positive integer length.
78
79    Yields:
80      All bytestrings of length `length`.
81    """
82    for digits in itertools.product(range(_BYTE_MAX), repeat=length):
83        yield b''.join(struct.pack('B', i) for i in digits)
84
85
86def _all_bytestrings():
87    """Generates a stream containing all possible bytestrings.
88
89    This generator does not terminate.
90
91    Yields:
92      All bytestrings in ascending order of length.
93    """
94    for bytestring in itertools.chain.from_iterable(
95            _bytestrings_of_length(length) for length in itertools.count()):
96        yield bytestring
97
98
99def search(target,
100           ideal_distance,
101           stop_event,
102           maximum_hashes,
103           interesting_hamming_distance=None):
104    """Find candidate strings.
105
106    Search through the space of all bytestrings, in order of increasing length,
107    indefinitely, until a hash with a Hamming distance of `maximum_distance` or
108    less has been found.
109
110    Args:
111      target: The search string.
112      ideal_distance: The desired Hamming distance.
113      stop_event: An event indicating whether the RPC should terminate.
114      maximum_hashes: The maximum number of hashes to check before stopping.
115      interesting_hamming_distance: If specified, strings with a Hamming
116        distance from the target below this value will be yielded.
117
118    Yields:
119      Instances  of HashNameResponse. The final entry in the stream will be of
120        `maximum_distance` Hamming distance or less from the target string,
121        while all others will be of less than `interesting_hamming_distance`.
122
123    Raises:
124      ResourceLimitExceededError: If the computation exceeds `maximum_hashes`
125        iterations.
126    """
127    hashes_computed = 0
128    for secret in _all_bytestrings():
129        if stop_event.is_set():
130            raise StopIteration()  # pylint: disable=stop-iteration-return
131        candidate_hash = _get_hash(secret)
132        distance = _get_substring_hamming_distance(candidate_hash, target)
133        if interesting_hamming_distance is not None and distance <= interesting_hamming_distance:
134            # Surface interesting candidates, but don't stop.
135            yield hash_name_pb2.HashNameResponse(
136                secret=base64.b64encode(secret),
137                hashed_name=candidate_hash,
138                hamming_distance=distance)
139        elif distance <= ideal_distance:
140            # Yield ideal candidate and end the stream.
141            yield hash_name_pb2.HashNameResponse(
142                secret=base64.b64encode(secret),
143                hashed_name=candidate_hash,
144                hamming_distance=distance)
145            raise StopIteration()  # pylint: disable=stop-iteration-return
146        hashes_computed += 1
147        if hashes_computed == maximum_hashes:
148            raise ResourceLimitExceededError()
149