pwnlib.util.cyclic — Generation of unique sequences

class pwnlib.util.cyclic.cyclic_gen(alphabet=None, n=None)[source]

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)
__init__(alphabet=None, n=None)[source]
find(subseq)[source]

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)
get(length=None)[source]

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
__weakref__[source]

list of weak references to the object (if defined)

pwnlib.util.cyclic._gen_find(subseq, generator)[source]

Returns the first position of subseq in the generator or -1 if there is no such position.

pwnlib.util.cyclic.cyclic(length=None, alphabet=None, n=None) list/str[source]

A simple wrapper over 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.

Parameters
  • 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 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)
pwnlib.util.cyclic.cyclic_find(subseq, alphabet=None, n=None) int[source]

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

Parameters
  • 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 context.cyclic_alphabet.

  • n (int) – The length of subsequences that should be unique. By default, uses 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
pwnlib.util.cyclic.cyclic_metasploit(length=None, sets=[string.ascii_uppercase, string.ascii_lowercase, string.digits]) str[source]

A simple wrapper over metasploit_pattern(). This function returns a string of length length.

Parameters
  • 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
pwnlib.util.cyclic.cyclic_metasploit_find(subseq, sets=[string.ascii_uppercase, string.ascii_lowercase, string.digits]) int[source]

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

Parameters
  • 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
pwnlib.util.cyclic.de_bruijn(alphabet=None, n=None) generator[source]

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.

Parameters
  • alphabet – List or string to generate the sequence over.

  • n (int) – The length of subsequences that should be unique.

pwnlib.util.cyclic.metasploit_pattern(sets=[string.ascii_uppercase, string.ascii_lowercase, string.digits]) generator[source]

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.

Parameters

sets – List of strings to generate the sequence over.