De Bruijn Sequences

"Calculating" offset

A de Bruijn sequence is a sequence of symbols over a given alphabet that contains every possible substring (of a given length) of the alphabet exactly once as a contiguous block. This makes finding the offset until EIP much simpler - we can just pass in a De Bruijn sequence, get the value within EIP and find the one possible match within the sequence to calculate the offset.

For example, consider an alphabet with 4 symbols:

{0, 1, 2, 3}

A de Bruijn sequence of length 2 over this alphabet would be a sequence of symbols that contains every possible two-symbol substring of the alphabet exactly once as a contiguous block.

One possible de Bruijn sequence of length 2 over this alphabet is: 0123010220130123.

This sequence contains every possible two-symbol substring of the alphabet exactly once, including

"00", "01", "02", "03", "10", "11", "12", "13", "20", "21", "22", "23", and "30", "31", "32", "33".

Generate sequences

The following command can be used to generate a sequence :

$ pwn cyclic -n [sub string lenght] [sequence lenght]

$ pwn cyclic -n 4 50
aaaabaaacaaadaaaeaaafaaagaaahaaaiaaajaaakaaalaaama

GDB aslo provide a command to generate patterns :

gdb-peda$ pattern create 70
'AAA%AAsAABAA$AAnAACAA-AA(AADAA;AA)AAEAAaAA0AAFAAbAA1AAGAAcAA2AAHAAdAA3'

Usage

This type of pattern is mostly used to retrieve the offset between user input and EIP. The entire string will be send as user input, then the program will crash because there is no instruction at any of the possible address (0x61616166 for example) :

Invalid $SP address: 0x61616166
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
Stopped reason: SIGSEGV
0x56556302 in main ()
gdb-peda$

Then The offset can be determined by retrieving the sequence into the entire string

It's possible to search a specific sequence into the entire string using the -l parameter :

$ pwn cyclic -l aaam
45

It's also possible directly into GDB :

gdb-peda$ pattern search $eip
Registers contain pattern buffer:
EBX+0 found at offset: 20
ESI+0 found at offset: 24
EIP+0 found at offset: 28
Registers point to pattern buffer:
[EDX] --> offset 0 - size ~70
[ESP] --> offset 32 - size ~38
[EBP] --> offset 40 - size ~30

There is a python code that directly use De Bruijn Sequences to retrieve offset between user input and saved instruction pointer :

from pwn import *

# Connect to the target program
p = process("./chall")

# Send the payload containing cyclic data
payload = cyclic(1024)
p.sendline(payload)

# Print the crash message
print(p.recvall())

# Get the offset to the saved EIP
offset = cyclic_find(p.corefile.fault_addr)

log.success("Offset to saved EIP: {}".format(offset))