# Overview
The binary is an implementation of a suffix array to efficiently search for needles in large haystack strings. I expected a logical bug in the algorithmic part, but my teammate informed me about a very easy yet powerful bug so I just used it instead. I think it's probably unintentional...
# The bug
The bug is triggered when the needle is longer than the haystack in the `recant needle` feature. By using the proof of concept below we can easily get a heap overflow.
```payload = p64(0)*2 #our datapayload += p64(0)+p64(0x31) #next heap headerpayload += p64(0x100)+chr(0)
add ("A"*0x10)add ('')add (payload)delete(1)
recant (2, payload+"\x00")```
We can overwrite the haystack structure of index 2, so I changed the length to a long value and its `buf` pointer's least significant byte so that it leaks a heap pointer.
Afterwards getting a LIBC leak and getting arbitrary write is super easy in tcache malloc so i'll just skip that part. 
# Unintentional Solution?
I looked at other teams' writeups and found out they used a much complex exploit primitive and used a ptmalloc exploit technique to get arbitrary write. Based on the scoring (500 point for a heap overflow challenge?) and other people's opinions I concluded that this bug is most likely unintentional. 