8912ca5a8c3a9725c3ba6d30561607150a6faebe-PR-2205

pending completion

Build # 8912ca5a8c3a9725c3ba6d30561607150a6faebe-PR-2205

Build Type

Pull #2205

github-actions

Committed by

web-flow

Commit Message

Merge 81f463e2c into 8b4cacf8b

Pull Request Pull Request #2205: Fix stable Python 2 installation from a built wheel

Run Details

3878 of 6371 branches covered (60.87%)

12199 of 16604 relevant lines covered (73.47%)

0.73 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.55

/pwnlib/util/cyclic.py

from __future__ import absolute_import
from __future__ import division

import six
import string

from pwnlib.context import context, LocalNoarchContext
from pwnlib.log import getLogger
from pwnlib.util import packing, iters

log = getLogger(__name__)

# Taken from https://en.wikipedia.org/wiki/De_Bruijn_sequence but changed to a generator
def de_bruijn(alphabet = None, n = None):
    """de_bruijn(alphabet = None, n = None) -> generator

    Generator for a sequence of unique substrings of length `n`. This is implemented using a
    De Bruijn Sequence over the given `alphabet`.

    The returned generator will yield up to ``len(alphabet)**n`` elements.

    Arguments:
        alphabet: List or string to generate the sequence over.
        n(int): The length of subsequences that should be unique.
    """
    if alphabet is None:
        alphabet = context.cyclic_alphabet
    if n is None:
        n = context.cyclic_size
    if isinstance(alphabet, bytes):
        alphabet = bytearray(alphabet)
    k = len(alphabet)
    a = [0] * k * n
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    yield alphabet[a[j]]
        else:
            a[t] = a[t - p]
            for c in db(t + 1, p):
                yield c

            for j in range(a[t - p] + 1, k):
                a[t] = j
                for c in db(t + 1, t):
                    yield c

    return db(1,1)

def cyclic(length = None, alphabet = None, n = None):
    """cyclic(length = None, alphabet = None, n = None) -> list/str

    A simple wrapper over :func:`de_bruijn`. This function returns at most
    `length` elements.

    If the given alphabet is a string, a string is returned from this function. Otherwise
    a list is returned.

    Arguments:
        length: The desired length of the list or None if the entire sequence is desired.
        alphabet: List or string to generate the sequence over.
        n(int): The length of subsequences that should be unique.

    Notes:
        The maximum length is `len(alphabet)**n`.

        The default values for `alphabet` and `n` restrict the total space to ~446KB.

        If you need to generate a longer cyclic pattern, provide a longer `alphabet`,
        or if possible a larger `n`.

    Example:

        Cyclic patterns are usually generated by providing a specific `length`.

        >>> cyclic(20)
        b'aaaabaaacaaadaaaeaaa'

        >>> cyclic(32)
        b'aaaabaaacaaadaaaeaaafaaagaaahaaa'

        The `alphabet` and `n` arguments will control the actual output of the pattern

        >>> cyclic(20, alphabet=string.ascii_uppercase)
        'AAAABAAACAAADAAAEAAA'

        >>> cyclic(20, n=8)
        b'aaaaaaaabaaaaaaacaaa'

        >>> cyclic(20, n=2)
        b'aabacadaeafagahaiaja'

        The size of `n` and `alphabet` limit the maximum length that can be generated.
        Without providing `length`, the entire possible cyclic space is generated.

        >>> cyclic(alphabet = "ABC", n = 3)
        'AAABAACABBABCACBACCBBBCBCCC'

        >>> cyclic(length=512, alphabet = "ABC", n = 3)
        Traceback (most recent call last):
        ...
        PwnlibException: Can't create a pattern length=512 with len(alphabet)==3 and n==3

        The `alphabet` can be set in `context`, which is useful for circumstances
        when certain characters are not allowed.  See :obj:`.context.cyclic_alphabet`.

        >>> context.cyclic_alphabet = "ABC"
        >>> cyclic(10)
        b'AAAABAAACA'

        The original values can always be restored with:

        >>> context.clear()

        The following just a test to make sure the length is correct.

        >>> alphabet, n = range(30), 3
        >>> len(alphabet)**n, len(cyclic(alphabet = alphabet, n = n))
        (27000, 27000)
    """
    if n is None:
        n = context.cyclic_size

    if alphabet is None:
        alphabet = context.cyclic_alphabet

    if length is not None and len(alphabet) ** n < length:
        log.error("Can't create a pattern length=%i with len(alphabet)==%i and n==%i",
                  length, len(alphabet), n)

    generator = de_bruijn(alphabet, n)
    out = iters.take(length, generator)

    return _join_sequence(out, alphabet)

@LocalNoarchContext
def cyclic_find(subseq, alphabet = None, n = None):
    """cyclic_find(subseq, alphabet = None, n = None) -> int

    Calculates the position of a substring into a De Bruijn sequence.

    .. todo:

       "Calculates" is an overstatement. It simply traverses the list.

       There exists better algorithms for this, but they depend on generating
       the De Bruijn sequence in another fashion. Somebody should look at it:

       https://www.sciencedirect.com/science/article/pii/S0012365X00001175

    Arguments:
        subseq: The subsequence to look for. This can be a string, a list or an
                integer. If an integer is provided it will be packed as a
                little endian integer.
        alphabet: List or string to generate the sequence over.
                  By default, uses :obj:`.context.cyclic_alphabet`.
        n(int): The length of subsequences that should be unique.
                By default, uses :obj:`.context.cyclic_size`.

    Examples:

        Let's generate an example cyclic pattern.

        >>> cyclic(16)
        b'aaaabaaacaaadaaa'

        Note that 'baaa' starts at offset 4.  The `cyclic_find` routine shows us this:

        >>> cyclic_find(b'baaa')
        4

        The *default* length of a subsequence generated by `cyclic` is `4`.
        If a longer value is submitted, it is automatically truncated to four bytes.

        >>> cyclic_find(b'baaacaaa')
        4

        If you provided e.g. `n=8` to `cyclic` to generate larger subsequences,
        you must explicitly provide that argument.

        >>> cyclic_find(b'baaacaaa', n=8)
        3515208

        We can generate a large cyclic pattern, and grab a subset of it to
        check a deeper offset.

        >>> cyclic_find(cyclic(1000)[514:518])
        514

        Instead of passing in the byte representation of the pattern, you can
        also pass in the integer value.  Note that this is sensitive to the
        selected endianness via `context.endian`.

        >>> cyclic_find(0x61616162)
        4
        >>> cyclic_find(0x61616162, endian='big')
        1

        Similarly to the case where you can provide a bytes value that is longer
        than four bytes, you can provided an integer value that is larger than
        what can be held in four bytes. If such a large value is given, it is
        automatically truncated.

        >>> cyclic_find(0x6161616361616162)
        4
        >>> cyclic_find(0x6261616163616161, endian='big')
        4

        You can use anything for the cyclic pattern, including non-printable
        characters.

        >>> cyclic_find(0x00000000, alphabet=unhex('DEADBEEF00'))
        621
    """

    if n is None:
        n = context.cyclic_size

    if isinstance(subseq, six.integer_types):
        if subseq >= 2**(8*n):
            # Assumption: The user has given an integer that is more than 2**(8n) bits, but would otherwise fit within
            #  a register of size 2**(8m) where m is a multiple of four
            notice = ("cyclic_find() expected an integer argument <= {cap:#x}, you gave {gave:#x}\n"
                      "Unless you specified cyclic(..., n={fits}), you probably just want the first {n} bytes.\n"
                      "Truncating the data at {n} bytes.  Specify cyclic_find(..., n={fits}) to override this.").format(
                cap=2**(8*n)-1,
                gave=subseq,
                # The number of bytes needed to represent subseq, rounded to the next 4
                fits=int(round(float(subseq.bit_length()) / 32 + 0.5) * 32) // 8,
                n=n,
            )
            log.warn_once(notice)
            if context.endian == 'little':
                subseq &= 2**(8*n) - 1
            else:
                while subseq >= 2**(8*n):
                    subseq >>= 8*n
        subseq = packing.pack(subseq, bytes=n)
    subseq = packing._need_bytes(subseq, 2, 0x80)

    if len(subseq) != n:
        log.warn_once("cyclic_find() expected a %i-byte subsequence, you gave %r\n"
            "Unless you specified cyclic(..., n=%i), you probably just want the first %d bytes.\n"
            "Truncating the data at %d bytes.  Specify cyclic_find(..., n=%i) to override this.",
            n, subseq, len(subseq), n, n, len(subseq))
        subseq = subseq[:n]

    if alphabet is None:
        alphabet = context.cyclic_alphabet
    alphabet = packing._need_bytes(alphabet, 2, 0x80)

    if any(c not in alphabet for c in subseq):
        return -1

    n = n or len(subseq)

    return _gen_find(subseq, de_bruijn(alphabet, n))

def metasploit_pattern(sets = None):
    """metasploit_pattern(sets = [ string.ascii_uppercase, string.ascii_lowercase, string.digits ]) -> generator

    Generator for a sequence of characters as per Metasploit Framework's
    `Rex::Text.pattern_create` (aka `pattern_create.rb`).

    The returned generator will yield up to
    ``len(sets) * reduce(lambda x,y: x*y, map(len, sets))`` elements.

    Arguments:
        sets: List of strings to generate the sequence over.
    """
    sets = sets or [ string.ascii_uppercase, string.ascii_lowercase, string.digits ]
    offsets = [ 0 ] * len(sets)
    offsets_indexes_reversed = list(reversed(range(len(offsets))))

    while True:
        for i, j in zip(sets, offsets):
            if isinstance(i, bytes):
                i = bytearray(i)
            yield i[j]
        # increment offsets with cascade
        for i in offsets_indexes_reversed:
            offsets[i] = (offsets[i] + 1) % len(sets[i])
            if offsets[i] != 0:
                break
        # finish up if we've exhausted the sequence
        if offsets == [ 0 ] * len(sets):
            return

def cyclic_metasploit(length = None, sets = None):
    """cyclic_metasploit(length = None, sets = [ string.ascii_uppercase, string.ascii_lowercase, string.digits ]) -> str

    A simple wrapper over :func:`metasploit_pattern`. This function returns a
    string of length `length`.

    Arguments:
        length: The desired length of the string or None if the entire sequence is desired.
        sets: List of strings to generate the sequence over.

    Example:
        >>> cyclic_metasploit(32)
        b'Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab'
        >>> cyclic_metasploit(sets = [b"AB",b"ab",b"12"])
        b'Aa1Aa2Ab1Ab2Ba1Ba2Bb1Bb2'
        >>> cyclic_metasploit()[1337:1341]
        b'5Bs6'
        >>> len(cyclic_metasploit())
        20280
    """
    sets = sets or [ string.ascii_uppercase.encode(), string.ascii_lowercase.encode(), string.digits.encode() ]

    generator = metasploit_pattern(sets)
    out = iters.take(length, generator)

    if length is not None and len(out) < length:
        log.error("Can't create a pattern of length %i with sets of lengths %s. Maximum pattern length is %i.",
                  length, list(map(len, sets)), len(out))

    return _join_sequence(out, sets[0])

def cyclic_metasploit_find(subseq, sets = None):
    """cyclic_metasploit_find(subseq, sets = [ string.ascii_uppercase, string.ascii_lowercase, string.digits ]) -> int

    Calculates the position of a substring into a Metasploit Pattern sequence.

    Arguments:
        subseq: The subsequence to look for. This can be a string or an
                integer. If an integer is provided it will be packed as a
                little endian integer.
        sets: List of strings to generate the sequence over.

    Examples:

        >>> cyclic_metasploit_find(cyclic_metasploit(1000)[514:518])
        514
        >>> cyclic_metasploit_find(0x61413161)
        4
    """
    sets = sets or [ string.ascii_uppercase.encode(), string.ascii_lowercase.encode(), string.digits.encode() ]

    if isinstance(subseq, six.integer_types):
        subseq = packing.pack(subseq, 'all', 'little', False)

    return _gen_find(subseq, metasploit_pattern(sets))

def _gen_find(subseq, generator):
    """Returns the first position of `subseq` in the generator or -1 if there is no such position."""
    if isinstance(subseq, bytes):
        subseq = bytearray(subseq)
    subseq = list(subseq)
    pos = 0
    saved = []

    for c in generator:
        saved.append(c)
        if len(saved) > len(subseq):
            saved.pop(0)
            pos += 1
        if saved == subseq:
            return pos
    return -1

def _join_sequence(seq, alphabet):
    if isinstance(alphabet, six.text_type):
        return ''.join(seq)
    elif isinstance(alphabet, bytes):
        return bytes(bytearray(seq))
    else:
        return seq

class cyclic_gen(object):
    """
    Creates a stateful cyclic generator which can generate sequential chunks of de Bruijn sequences.

    >>> g = cyclic_gen() # Create a generator
    >>> g.get(4) # Get a chunk of length 4
    b'aaaa'
    >>> g.get(4) # Get a chunk of length 4
    b'baaa'
    >>> g.get(8) # Get a chunk of length 8
    b'caaadaaa'
    >>> g.get(4) # Get a chunk of length 4
    b'eaaa'
    >>> g.find(b'caaa') # Position 8, which is in chunk 2 at index 0
    (8, 2, 0)
    >>> g.find(b'aaaa') # Position 0, which is in chunk 0 at index 0
    (0, 0, 0)
    >>> g.find(b'baaa') # Position 4, which is in chunk 1 at index 0
    (4, 1, 0)
    >>> g.find(b'aaad') # Position 9, which is in chunk 2 at index 1
    (9, 2, 1)
    >>> g.find(b'aada') # Position 10, which is in chunk 2 at index 2
    (10, 2, 2)
    >>> g.get() # Get the rest of the sequence
    b'faaagaaahaaaiaaajaaa...yyxzyzxzzyxzzzyyyyzyyzzyzyzzzz'
    >>> g.find(b'racz') # Position 7760, which is in chunk 4 at index 7740
    (7760, 4, 7740)
    >>> g.get(12) # Generator is exhausted
    Traceback (most recent call last):
      ...
    StopIteration

    >>> g = cyclic_gen(string.ascii_uppercase, n=8) # Custom alphabet and item size
    >>> g.get(12) # Get a chunk of length 12
    'AAAAAAAABAAA'
    >>> g.get(18) # Get a chunk of length 18
    'AAAACAAAAAAADAAAAA'
    >>> g.find('CAAAAAAA') # Position 16, which is in chunk 1 at index 4
    (16, 1, 4)
    """

    def __init__(self, alphabet = None, n = None):
        if n is None:
            n = context.cyclic_size

        if alphabet is None:
            alphabet = context.cyclic_alphabet

        self._generator = de_bruijn(alphabet, n)
        self._alphabet = alphabet
        self._total_length = 0
        self._n = n
        self._chunks = []

    def get(self, length = None):
        """
        Get the next de Bruijn sequence from this generator.

        >>> g = cyclic_gen()
        >>> g.get(4) # Get a chunk of length 4
        b'aaaa'
        >>> g.get(4) # Get a chunk of length 4
        b'baaa'
        >>> g.get(8) # Get a chunk of length 8
        b'caaadaaa'
        >>> g.get(4) # Get a chunk of length 4
        b'eaaa'
        >>> g.get() # Get the rest of the sequence
        b'faaagaaahaaaiaaajaaa...yyxzyzxzzyxzzzyyyyzyyzzyzyzzzz'
        >>> g.get(12) # Generator is exhausted
        Traceback (most recent call last):
          ...
        StopIteration
        """

        if length is not None:
            self._chunks.append(length)
            self._total_length += length
            if len(self._alphabet) ** self._n < self._total_length:
                log.error("Can't create a pattern length=%i with len(alphabet)==%i and n==%i",
                          self._total_length, len(self._alphabet), self._n)
            out = [next(self._generator) for _ in range(length)]
        else:
            self._chunks.append(float("inf"))
            out = list(self._generator)

        return _join_sequence(out, self._alphabet)

    def find(self, subseq):
        """
        Find a chunk and subindex from all the generates de Bruijn sequences.

        >>> g = cyclic_gen()
        >>> g.get(4)
        b'aaaa'
        >>> g.get(4)
        b'baaa'
        >>> g.get(8)
        b'caaadaaa'
        >>> g.get(4)
        b'eaaa'
        >>> g.find(b'caaa') # Position 8, which is in chunk 2 at index 0
        (8, 2, 0)
        """

        global_index = cyclic_find(subseq, self._alphabet, self._n)
        remaining_index = global_index
        for chunk_idx in range(len(self._chunks)):
            chunk = self._chunks[chunk_idx]
            if remaining_index < chunk:
                return (global_index, chunk_idx, remaining_index)
            remaining_index -= chunk
        return -1

1	from __future__ import absolute_import	1✔
2	from __future__ import division	1✔
3
4	import six	1✔
5	import string	1✔
6
7	from pwnlib.context import context, LocalNoarchContext	1✔
8	from pwnlib.log import getLogger	1✔
9	from pwnlib.util import packing, iters	1✔
10
11	log = getLogger(__name__)	1✔
12
13	# Taken from https://en.wikipedia.org/wiki/De_Bruijn_sequence but changed to a generator
14	def de_bruijn(alphabet = None, n = None):	1✔
15	"""de_bruijn(alphabet = None, n = None) -> generator
16
17	Generator for a sequence of unique substrings of length `n`. This is implemented using a
18	De Bruijn Sequence over the given `alphabet`.
19
20	The returned generator will yield up to ``len(alphabet)**n`` elements.
21
22	Arguments:
23	alphabet: List or string to generate the sequence over.
24	n(int): The length of subsequences that should be unique.
25	"""
26	if alphabet is None:	1✔
27	alphabet = context.cyclic_alphabet	1✔
28	if n is None:	1✔
29	n = context.cyclic_size	1✔
30	if isinstance(alphabet, bytes):	1✔
31	alphabet = bytearray(alphabet)	1✔
32	k = len(alphabet)	1✔
33	a = [0] * k * n	1✔
34	def db(t, p):	1✔
35	if t > n:	1✔
36	if n % p == 0:	1✔
37	for j in range(1, p + 1):	1✔
38	yield alphabet[a[j]]	1✔
39	else:
40	a[t] = a[t - p]	1✔
41	for c in db(t + 1, p):	1✔
42	yield c	1✔
43
44	for j in range(a[t - p] + 1, k):	1✔
45	a[t] = j	1✔
46	for c in db(t + 1, t):	1✔
47	yield c	1✔
48
49	return db(1,1)	1✔
50
51	def cyclic(length = None, alphabet = None, n = None):	1✔
52	"""cyclic(length = None, alphabet = None, n = None) -> list/str
53
54	A simple wrapper over :func:`de_bruijn`. This function returns at most
55	`length` elements.
56
57	If the given alphabet is a string, a string is returned from this function. Otherwise
58	a list is returned.
59
60	Arguments:
61	length: The desired length of the list or None if the entire sequence is desired.
62	alphabet: List or string to generate the sequence over.
63	n(int): The length of subsequences that should be unique.
64
65	Notes:
66	The maximum length is `len(alphabet)**n`.
67
68	The default values for `alphabet` and `n` restrict the total space to ~446KB.
69
70	If you need to generate a longer cyclic pattern, provide a longer `alphabet`,
71	or if possible a larger `n`.
72
73	Example:
74
75	Cyclic patterns are usually generated by providing a specific `length`.
76
77	>>> cyclic(20)
78	b'aaaabaaacaaadaaaeaaa'
79
80	>>> cyclic(32)
81	b'aaaabaaacaaadaaaeaaafaaagaaahaaa'
82
83	The `alphabet` and `n` arguments will control the actual output of the pattern
84
85	>>> cyclic(20, alphabet=string.ascii_uppercase)
86	'AAAABAAACAAADAAAEAAA'
87
88	>>> cyclic(20, n=8)
89	b'aaaaaaaabaaaaaaacaaa'
90
91	>>> cyclic(20, n=2)
92	b'aabacadaeafagahaiaja'
93
94	The size of `n` and `alphabet` limit the maximum length that can be generated.
95	Without providing `length`, the entire possible cyclic space is generated.
96
97	>>> cyclic(alphabet = "ABC", n = 3)
98	'AAABAACABBABCACBACCBBBCBCCC'
99
100	>>> cyclic(length=512, alphabet = "ABC", n = 3)
101	Traceback (most recent call last):
102	...
103	PwnlibException: Can't create a pattern length=512 with len(alphabet)==3 and n==3
104
105	The `alphabet` can be set in `context`, which is useful for circumstances
106	when certain characters are not allowed. See :obj:`.context.cyclic_alphabet`.
107
108	>>> context.cyclic_alphabet = "ABC"
109	>>> cyclic(10)
110	b'AAAABAAACA'
111
112	The original values can always be restored with:
113
114	>>> context.clear()
115
116	The following just a test to make sure the length is correct.
117
118	>>> alphabet, n = range(30), 3
119	>>> len(alphabet)**n, len(cyclic(alphabet = alphabet, n = n))
120	(27000, 27000)
121	"""
122	if n is None:	1✔
123	n = context.cyclic_size	1✔
124
125	if alphabet is None:	1✔
126	alphabet = context.cyclic_alphabet	1✔
127
128	if length is not None and len(alphabet) ** n < length:	1✔
129	log.error("Can't create a pattern length=%i with len(alphabet)==%i and n==%i",	1✔
130	length, len(alphabet), n)
131
132	generator = de_bruijn(alphabet, n)	1✔
133	out = iters.take(length, generator)	1✔
134
135	return _join_sequence(out, alphabet)	1✔
136
137	@LocalNoarchContext	1✔
138	def cyclic_find(subseq, alphabet = None, n = None):	1✔
139	"""cyclic_find(subseq, alphabet = None, n = None) -> int
140
141	Calculates the position of a substring into a De Bruijn sequence.
142
143	.. todo:
144
145	"Calculates" is an overstatement. It simply traverses the list.
146
147	There exists better algorithms for this, but they depend on generating
148	the De Bruijn sequence in another fashion. Somebody should look at it:
149
150	https://www.sciencedirect.com/science/article/pii/S0012365X00001175
151
152	Arguments:
153	subseq: The subsequence to look for. This can be a string, a list or an
154	integer. If an integer is provided it will be packed as a
155	little endian integer.
156	alphabet: List or string to generate the sequence over.
157	By default, uses :obj:`.context.cyclic_alphabet`.
158	n(int): The length of subsequences that should be unique.
159	By default, uses :obj:`.context.cyclic_size`.
160
161	Examples:
162
163	Let's generate an example cyclic pattern.
164
165	>>> cyclic(16)
166	b'aaaabaaacaaadaaa'
167
168	Note that 'baaa' starts at offset 4. The `cyclic_find` routine shows us this:
169
170	>>> cyclic_find(b'baaa')
171	4
172
173	The default length of a subsequence generated by `cyclic` is `4`.
174	If a longer value is submitted, it is automatically truncated to four bytes.
175
176	>>> cyclic_find(b'baaacaaa')
177	4
178
179	If you provided e.g. `n=8` to `cyclic` to generate larger subsequences,
180	you must explicitly provide that argument.
181
182	>>> cyclic_find(b'baaacaaa', n=8)
183	3515208
184
185	We can generate a large cyclic pattern, and grab a subset of it to
186	check a deeper offset.
187
188	>>> cyclic_find(cyclic(1000)[514:518])
189	514
190
191	Instead of passing in the byte representation of the pattern, you can
192	also pass in the integer value. Note that this is sensitive to the
193	selected endianness via `context.endian`.
194
195	>>> cyclic_find(0x61616162)
196	4
197	>>> cyclic_find(0x61616162, endian='big')
198	1
199
200	Similarly to the case where you can provide a bytes value that is longer
201	than four bytes, you can provided an integer value that is larger than
202	what can be held in four bytes. If such a large value is given, it is
203	automatically truncated.
204
205	>>> cyclic_find(0x6161616361616162)
206	4
207	>>> cyclic_find(0x6261616163616161, endian='big')
208	4
209
210	You can use anything for the cyclic pattern, including non-printable
211	characters.
212
213	>>> cyclic_find(0x00000000, alphabet=unhex('DEADBEEF00'))
214	621
215	"""
216
217	if n is None:	1✔
218	n = context.cyclic_size	1✔
219
220	if isinstance(subseq, six.integer_types):	1✔
221	if subseq >= 2*(8n):	1✔
222	# Assumption: The user has given an integer that is more than 2**(8n) bits, but would otherwise fit within
223	# a register of size 2**(8m) where m is a multiple of four
224	notice = ("cyclic_find() expected an integer argument <= {cap:#x}, you gave {gave:#x}\n"	1✔
225	"Unless you specified cyclic(..., n={fits}), you probably just want the first {n} bytes.\n"
226	"Truncating the data at {n} bytes. Specify cyclic_find(..., n={fits}) to override this.").format(
227	cap=2*(8n)-1,
228	gave=subseq,
229	# The number of bytes needed to represent subseq, rounded to the next 4
230	fits=int(round(float(subseq.bit_length()) / 32 + 0.5) * 32) // 8,
231	n=n,
232	)
233	log.warn_once(notice)	1✔
234	if context.endian == 'little':	1✔
235	subseq &= 2*(8n) - 1	1✔
236	else:
237	while subseq >= 2*(8n):	1✔
238	subseq >>= 8*n	1✔
239	subseq = packing.pack(subseq, bytes=n)	1✔
240	subseq = packing._need_bytes(subseq, 2, 0x80)	1✔
241
242	if len(subseq) != n:	1✔
243	log.warn_once("cyclic_find() expected a %i-byte subsequence, you gave %r\n"	1✔
244	"Unless you specified cyclic(..., n=%i), you probably just want the first %d bytes.\n"
245	"Truncating the data at %d bytes. Specify cyclic_find(..., n=%i) to override this.",
246	n, subseq, len(subseq), n, n, len(subseq))
247	subseq = subseq[:n]	1✔
248
249	if alphabet is None:	1✔
250	alphabet = context.cyclic_alphabet	1✔
251	alphabet = packing._need_bytes(alphabet, 2, 0x80)	1✔
252
253	if any(c not in alphabet for c in subseq):	1✔
254	return -1	1✔
255
256	n = n or len(subseq)	1✔
257
258	return _gen_find(subseq, de_bruijn(alphabet, n))	1✔
259
260	def metasploit_pattern(sets = None):	1✔
261	"""metasploit_pattern(sets = [ string.ascii_uppercase, string.ascii_lowercase, string.digits ]) -> generator
262
263	Generator for a sequence of characters as per Metasploit Framework's
264	`Rex::Text.pattern_create` (aka `pattern_create.rb`).
265
266	The returned generator will yield up to
267	``len(sets) * reduce(lambda x,y: x*y, map(len, sets))`` elements.
268
269	Arguments:
270	sets: List of strings to generate the sequence over.
271	"""
272	sets = sets or [ string.ascii_uppercase, string.ascii_lowercase, string.digits ]	1✔
273	offsets = [ 0 ] * len(sets)	1✔
274	offsets_indexes_reversed = list(reversed(range(len(offsets))))	1✔
275
276	while True:	1✔
277	for i, j in zip(sets, offsets):	1✔
278	if isinstance(i, bytes):	1!
279	i = bytearray(i)	1✔
280	yield i[j]	1✔
281	# increment offsets with cascade
282	for i in offsets_indexes_reversed:	1✔
283	offsets[i] = (offsets[i] + 1) % len(sets[i])	1✔
284	if offsets[i] != 0:	1✔
285	break	1✔
286	# finish up if we've exhausted the sequence
287	if offsets == [ 0 ] * len(sets):	1✔
288	return	1✔
289
290	def cyclic_metasploit(length = None, sets = None):	1✔
291	"""cyclic_metasploit(length = None, sets = [ string.ascii_uppercase, string.ascii_lowercase, string.digits ]) -> str
292
293	A simple wrapper over :func:`metasploit_pattern`. This function returns a
294	string of length `length`.
295
296	Arguments:
297	length: The desired length of the string or None if the entire sequence is desired.
298	sets: List of strings to generate the sequence over.
299
300	Example:
301	>>> cyclic_metasploit(32)
302	b'Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab'
303	>>> cyclic_metasploit(sets = [b"AB",b"ab",b"12"])
304	b'Aa1Aa2Ab1Ab2Ba1Ba2Bb1Bb2'
305	>>> cyclic_metasploit()[1337:1341]
306	b'5Bs6'
307	>>> len(cyclic_metasploit())
308	20280
309	"""
310	sets = sets or [ string.ascii_uppercase.encode(), string.ascii_lowercase.encode(), string.digits.encode() ]	1✔
311
312	generator = metasploit_pattern(sets)	1✔
313	out = iters.take(length, generator)	1✔
314
315	if length is not None and len(out) < length:	1!
316	log.error("Can't create a pattern of length %i with sets of lengths %s. Maximum pattern length is %i.",	×
317	length, list(map(len, sets)), len(out))
318
319	return _join_sequence(out, sets[0])	1✔
320
321	def cyclic_metasploit_find(subseq, sets = None):	1✔
322	"""cyclic_metasploit_find(subseq, sets = [ string.ascii_uppercase, string.ascii_lowercase, string.digits ]) -> int
323
324	Calculates the position of a substring into a Metasploit Pattern sequence.
325
326	Arguments:
327	subseq: The subsequence to look for. This can be a string or an
328	integer. If an integer is provided it will be packed as a
329	little endian integer.
330	sets: List of strings to generate the sequence over.
331
332	Examples:
333
334	>>> cyclic_metasploit_find(cyclic_metasploit(1000)[514:518])
335	514
336	>>> cyclic_metasploit_find(0x61413161)
337	4
338	"""
339	sets = sets or [ string.ascii_uppercase.encode(), string.ascii_lowercase.encode(), string.digits.encode() ]	1✔
340
341	if isinstance(subseq, six.integer_types):	1✔
342	subseq = packing.pack(subseq, 'all', 'little', False)	1✔
343
344	return _gen_find(subseq, metasploit_pattern(sets))	1✔
345
346	def _gen_find(subseq, generator):	1✔
347	"""Returns the first position of `subseq` in the generator or -1 if there is no such position."""
348	if isinstance(subseq, bytes):	1!
349	subseq = bytearray(subseq)	1✔
350	subseq = list(subseq)	1✔
351	pos = 0	1✔
352	saved = []	1✔
353
354	for c in generator:	1!
355	saved.append(c)	1✔
356	if len(saved) > len(subseq):	1✔
357	saved.pop(0)	1✔
358	pos += 1	1✔
359	if saved == subseq:	1✔
360	return pos	1✔
361	return -1	×
362
363	def _join_sequence(seq, alphabet):	1✔
364	if isinstance(alphabet, six.text_type):	1!
365	return ''.join(seq)	×
366	elif isinstance(alphabet, bytes):	1✔
367	return bytes(bytearray(seq))	1✔
368	else:
369	return seq	1✔
370
371	class cyclic_gen(object):	1✔
372	"""
373	Creates a stateful cyclic generator which can generate sequential chunks of de Bruijn sequences.
374
375	>>> g = cyclic_gen() # Create a generator
376	>>> g.get(4) # Get a chunk of length 4
377	b'aaaa'
378	>>> g.get(4) # Get a chunk of length 4
379	b'baaa'
380	>>> g.get(8) # Get a chunk of length 8
381	b'caaadaaa'
382	>>> g.get(4) # Get a chunk of length 4
383	b'eaaa'
384	>>> g.find(b'caaa') # Position 8, which is in chunk 2 at index 0
385	(8, 2, 0)
386	>>> g.find(b'aaaa') # Position 0, which is in chunk 0 at index 0
387	(0, 0, 0)
388	>>> g.find(b'baaa') # Position 4, which is in chunk 1 at index 0
389	(4, 1, 0)
390	>>> g.find(b'aaad') # Position 9, which is in chunk 2 at index 1
391	(9, 2, 1)
392	>>> g.find(b'aada') # Position 10, which is in chunk 2 at index 2
393	(10, 2, 2)
394	>>> g.get() # Get the rest of the sequence
395	b'faaagaaahaaaiaaajaaa...yyxzyzxzzyxzzzyyyyzyyzzyzyzzzz'
396	>>> g.find(b'racz') # Position 7760, which is in chunk 4 at index 7740
397	(7760, 4, 7740)
398	>>> g.get(12) # Generator is exhausted
399	Traceback (most recent call last):
400	...
401	StopIteration
402
403	>>> g = cyclic_gen(string.ascii_uppercase, n=8) # Custom alphabet and item size
404	>>> g.get(12) # Get a chunk of length 12
405	'AAAAAAAABAAA'
406	>>> g.get(18) # Get a chunk of length 18
407	'AAAACAAAAAAADAAAAA'
408	>>> g.find('CAAAAAAA') # Position 16, which is in chunk 1 at index 4
409	(16, 1, 4)
410	"""
411
412	def __init__(self, alphabet = None, n = None):	1✔
413	if n is None:	1✔
414	n = context.cyclic_size	1✔
415
416	if alphabet is None:	1✔
417	alphabet = context.cyclic_alphabet	1✔
418
419	self._generator = de_bruijn(alphabet, n)	1✔
420	self._alphabet = alphabet	1✔
421	self._total_length = 0	1✔
422	self._n = n	1✔
423	self._chunks = []	1✔
424
425	def get(self, length = None):	1✔
426	"""
427	Get the next de Bruijn sequence from this generator.
428
429	>>> g = cyclic_gen()
430	>>> g.get(4) # Get a chunk of length 4
431	b'aaaa'
432	>>> g.get(4) # Get a chunk of length 4
433	b'baaa'
434	>>> g.get(8) # Get a chunk of length 8
435	b'caaadaaa'
436	>>> g.get(4) # Get a chunk of length 4
437	b'eaaa'
438	>>> g.get() # Get the rest of the sequence
439	b'faaagaaahaaaiaaajaaa...yyxzyzxzzyxzzzyyyyzyyzzyzyzzzz'
440	>>> g.get(12) # Generator is exhausted
441	Traceback (most recent call last):
442	...
443	StopIteration
444	"""
445
446	if length is not None:	1✔
447	self._chunks.append(length)	1✔
448	self._total_length += length	1✔
449	if len(self._alphabet) ** self._n < self._total_length:	1!
450	log.error("Can't create a pattern length=%i with len(alphabet)==%i and n==%i",	×
451	self._total_length, len(self._alphabet), self._n)
452	out = [next(self._generator) for _ in range(length)]	1✔
453	else:
454	self._chunks.append(float("inf"))	1✔
455	out = list(self._generator)	1✔
456
457	return _join_sequence(out, self._alphabet)	1✔
458
459	def find(self, subseq):	1✔
460	"""
461	Find a chunk and subindex from all the generates de Bruijn sequences.
462
463	>>> g = cyclic_gen()
464	>>> g.get(4)
465	b'aaaa'
466	>>> g.get(4)
467	b'baaa'
468	>>> g.get(8)
469	b'caaadaaa'
470	>>> g.get(4)
471	b'eaaa'
472	>>> g.find(b'caaa') # Position 8, which is in chunk 2 at index 0
473	(8, 2, 0)
474	"""
475
476	global_index = cyclic_find(subseq, self._alphabet, self._n)	1✔
477	remaining_index = global_index	1✔
478	for chunk_idx in range(len(self._chunks)):	1!
479	chunk = self._chunks[chunk_idx]	1✔
480	if remaining_index < chunk:	1✔
481	return (global_index, chunk_idx, remaining_index)	1✔
482	remaining_index -= chunk	1✔
483	return -1	×

Gallopsled / pwntools / 8912ca5a8c3a9725c3ba6d30561607150a6faebe-PR-2205

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous