Module: Pwnlib::Util::Cyclic

Included in:
Pwn
Defined in:
lib/pwnlib/util/cyclic.rb

Overview

Generate string with easy-to-find pattern.

Examples:

Call by specifying full module path.

require 'pwnlib/util/cyclic'
Pwnlib::Util::Cyclic.cyclic_find(Pwnlib::Util::Cyclic.cyclic(200)[123, 4]) #=> 123

require 'pwn' and have all methods.

require 'pwn'
cyclic_find(cyclic(200)[123, 4]) #=> 123

Class Method Summary collapse

Class Method Details

.cyclic(length = nil, alphabet: ASCII_LOWERCASE, n: 4) ⇒ String, Array

Simple wrapper over de_bruijn, returning at most length items.

Examples:

cyclic(alphabet: 'ABC', n: 3) #=> 'AAABAACABBABCACBACCBBBCBCCC'
cyclic(20) #=> 'aaaabaaacaaadaaaeaaa'

Parameters:

  • length (Integer, nil) (defaults to: nil) —

    Desired length of the sequence, or nil for the entire sequence.

  • alphabet (String, Array) (defaults to: ASCII_LOWERCASE) —

    Alphabet to be used.

  • n (Integer) (defaults to: 4) —

    Length of substring that should be unique.

Returns:

  • (String, Array) —

    The result sequence of at most length items, with same type as alphabet.



81
82
83
84
85
 
# File 'lib/pwnlib/util/cyclic.rb', line 81

def cyclic(length = nil, alphabet: ASCII_LOWERCASE, n: 4)
  enum = de_bruijn(alphabet: alphabet, n: n)
  r = length.nil? ? enum.to_a : enum.take(length)
  alphabet.is_a?(String) ? r.join : r
end

.cyclic_find(subseq, alphabet: ASCII_LOWERCASE, n: nil) ⇒ Integer?

TODO:

Speed! See comment in Python pwntools.

Find the position of a substring in a De Bruijn sequence.

Examples:

cyclic_find(cyclic(300)[217, 4]) #=> 217

Parameters:

  • subseq (String, Array) —

    The substring to be found in the sequence.

  • alphabet (String, Array) (defaults to: ASCII_LOWERCASE) —

    Alphabet to be used.

  • n (Integer) (defaults to: nil) —

    Length of substring that should be unique. Default to subseq.size.

Returns:

  • (Integer, nil) —

    The index subseq first appear in the sequence, or nil if not found.



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
# File 'lib/pwnlib/util/cyclic.rb', line 104

def cyclic_find(subseq, alphabet: ASCII_LOWERCASE, n: nil)
  n ||= subseq.size
  subseq = subseq.chars if subseq.is_a?(String)
  return nil unless subseq.all? { |c| alphabet.include?(c) }

  pos = 0
  saved = []
  de_bruijn(alphabet: alphabet, n: n).each do |c|
    saved << c
    if saved.size > subseq.size
      saved.shift
      pos += 1
    end
    return pos if saved == subseq
  end
  nil
end

.de_bruijn(alphabet: ASCII_LOWERCASE, n: 4) {|c| ... } ⇒ void .de_bruijn(alphabet: ASCII_LOWERCASE, n: 4) ⇒ Enumerator

Generator for a sequence of unique substrings of length n. This is implemented using a De Bruijn Sequence over the given alphabet. Returns an Enumerator if no block given.

Overloads:

  • .de_bruijn(alphabet: ASCII_LOWERCASE, n: 4) {|c| ... } ⇒ void

    This method returns an undefined value.

    Parameters:

    • alphabet (String, Array) (defaults to: ASCII_LOWERCASE) —

      Alphabet to be used.

    • n (Integer) (defaults to: 4) —

      Length of substring that should be unique.

    Yield Parameters:

    • c —

      Item of the result sequence in order.

  • .de_bruijn(alphabet: ASCII_LOWERCASE, n: 4) ⇒ Enumerator

    Returns The result sequence.

    Parameters:

    • alphabet (String, Array) (defaults to: ASCII_LOWERCASE) —

      Alphabet to be used.

    • n (Integer) (defaults to: 4) —

      Length of substring that should be unique.

    Returns:

    • (Enumerator) —

      The result sequence.



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/pwnlib/util/cyclic.rb', line 44

def de_bruijn(alphabet: ASCII_LOWERCASE, n: 4)
  return to_enum(__method__, alphabet: alphabet, n: n) { alphabet.size**n } unless block_given?

  k = alphabet.size
  a = [0] * (k * n)

  db = lambda do |t, p|
    if t > n
      (1..p).each { |j| yield alphabet[a[j]] } if (n % p).zero?
    else
      a[t] = a[t - p]
      db.call(t + 1, p)
      (a[t - p] + 1...k).each do |j|
        a[t] = j
        db.call(t + 1, t)
      end
    end
  end

  db[1, 1]
end