Sequências de De Bruijn

Uma sequência de De Bruijn de ordem n é uma sequência de letras/números em que toda possível substring de comprimento n aparece somente uma vez.

Podemos usar sequências de letras de De Bruijn para identificar offsets (quantos caracteres colocar de espaçamento até o endereço alvo) em Buffer Overflow. Isso facilita demais o processo de achar offsets.

Imagine que queremos sobrescrever algo na memória, mas não sabemos o offset. Podemos simplesmente colocar uma sequência de De Bruijn de 200 letras e olhar o valor dentro do endereço alvo no GDB (Buffer Overflow sobrescreve a stack inteira). Mesmo que tenhamos passado do ponto onde queríamos chegar, a combinação de letras naquele endereço é única, e podemos identificar o offset numericamente.

No pwntools, criamos essa sequência e identificamos o offset com o comando cyclic.

# Gerando sequência de De Bruijn:
>>> from pwn import *
>>> print(cyclic(128))
b'aaaabaaacaaadaaaeaaafaaagaaahaaaiaaajaaakaaalaaamaaanaaaoaaapaaaqaaaraaasaaataaauaaavaaawaaaxaaayaaazaabbaabcaabdaabeaabfaabgaab'

# No GDB:

## Input
> aaaabaaacaaadaaaeaaafaaagaaahaaaiaaajaaakaaalaaamaaanaaaoaaapaaaqaaaraaasaaataaauaaavaaawaaaxaaayaaazaabbaabcaabdaabeaabfaabgaab

## Olhando endereço onde queremos chegar
pwndbg> x/x $rbp+0x8
0x7fffffffd9e8: 0x61616173

# Achando offset pela sequência:
>>> print(cyclic_find(0x61616173))
72 # Isso quer dizer que temos uma distância de 72 bytes até nosso alvo, que temos que preencher (padding)!

Internamente, o cyclic gera uma sequência de De Bruijn de caracteres onde n = 4. Isso faz a sequência funcionar para 32 e 64 bits.