# De Bruijn Sequences

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.

{% hint style="info" %}
For example, consider an alphabet with 4 symbols: 

```bash
{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 

{% code overflow="wrap" %}

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

{% endcode %}
{% endhint %}

## Generate sequences

The following command can be used to generate a sequence : 

<pre class="language-bash"><code class="lang-bash">$ pwn cyclic -n [sub string lenght] [sequence lenght]
<strong>
</strong>$ pwn cyclic -n 4 50
aaaabaaacaaadaaaeaaafaaagaaahaaaiaaajaaakaaalaaama
</code></pre>

GDB aslo provide a command to generate patterns :&#x20;

```bash
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) :&#x20;

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

&#x20;Then The offset can be determined by retrieving the sequence into the entire string&#x20;

It's possible to search a specific sequence into the entire string using the `-l` parameter : &#x20;

```bash
$ pwn cyclic -l aaam
45
```

It's also possible directly into GDB :&#x20;

```bash
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 :**&#x20;

```python
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))
```