What the latest OpenSSH security issue is actually about

------------------------------------------------------------------------
Theory
------------------------------------------------------------------------

    But that's not like me, I'm breaking free
        -- The Interrupters, "Haven't Seen the Last of Me"

The SIGALRM handler of this OpenSSH version calls packet_close(), which
calls buffer_free(), which calls xfree() and hence free(), which is not
async-signal-safe:

------------------------------------------------------------------------
 302 grace_alarm_handler(int sig)
 303 {
 ...
 307         packet_close();
------------------------------------------------------------------------
 329 packet_close(void)
 330 {
 ...
 341         buffer_free(&input);
 342         buffer_free(&output);
 343         buffer_free(&outgoing_packet);
 344         buffer_free(&incoming_packet);
------------------------------------------------------------------------
 35 buffer_free(Buffer *buffer)
 36 {
 37         memset(buffer->buf, 0, buffer->alloc);
 38         xfree(buffer->buf);
 39 }
------------------------------------------------------------------------
 51 xfree(void *ptr)
 52 {
 53         if (ptr == NULL)
 54                 fatal("xfree: NULL pointer given as argument");
 55         free(ptr);
 56 }
------------------------------------------------------------------------

Consequently, we started to read the malloc code of this Debian's glibc
(2.2.5), to see if a first call to free() can be interrupted by SIGALRM
and exploited during a second call to free() inside the SIGALRM handler
(at lines 341-344, above). Because this glibc's malloc is not hardened
against the unlink() technique pioneered by Solar Designer in 2000, we
quickly spotted an interesting code path in chunk_free() (which is
called internally by free()):

------------------------------------------------------------------------
1028 struct malloc_chunk
1029 {
1030   INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
1031   INTERNAL_SIZE_T size;      /* Size in bytes, including overhead. */
1032   struct malloc_chunk* fd;   /* double links -- used only if free. */
1033   struct malloc_chunk* bk;
1034 };
------------------------------------------------------------------------
2516 #define unlink(P, BK, FD)                                           \
2517 {                                                                   \
2518   BK = P->bk;                                                       \
2519   FD = P->fd;                                                       \
2520   FD->bk = BK;                                                      \
2521   BK->fd = FD;                                                      \
2522 }                                                                   \
------------------------------------------------------------------------
3160 chunk_free(arena *ar_ptr, mchunkptr p)
....
3164 {
3165   INTERNAL_SIZE_T hd = p->size; /* its head field */
....
3177   sz = hd & ~PREV_INUSE;
3178   next = chunk_at_offset(p, sz);
3179   nextsz = chunksize(next);
....
3230   if (!(inuse_bit_at_offset(next, nextsz)))   /* consolidate forward */
3231   {
....
3241       unlink(next, bck, fwd);
....
3244   }
3245   else
3246     set_head(next, nextsz);                  /* clear inuse bit */
....
3251     frontlink(ar_ptr, p, sz, idx, bck, fwd);
------------------------------------------------------------------------

To exploit this code path, we arrange for sshd's heap to have the
following layout (chunk_X, chunk_Y, and chunk_Z are malloc()ated chunks
of memory, and p, s, f, b are their prev_size, size, fd, and bk fields):

-----|---+---------------|---+---------------|---+---------------|-----
 ... |p|s|f|b|  chunk_X  |p|s|f|b|  chunk_Y  |p|s|f|b|  chunk_Z  | ...
-----|---+---------------|---+---------------|---+---------------|-----
                             |<------------->|
                                 user data

- First, if a call to free(chunk_Y) is interrupted by SIGALRM *after*
  line 3246 but *before* line 3251, then chunk_Y is already marked as
  free (because chunk_Z's PREV_INUSE bit is cleared at line 3246) but it
  is not yet linked into its doubly-linked list (at line 3251): in other
  words, chunk_Y's fd and bk pointers still contain user data (attacker-
  controlled data).

- Second, if (inside the SIGALRM handler) packet_close() calls
  free(chunk_X), then the code block at lines 3230-3244 is entered
  (because chunk_Y is marked as free) and chunk_Y is unlink()ed (at line
  3241): a so-called aa4bmo primitive (almost arbitrary 4 bytes mirrored
  overwrite), because chunk_Y's fd and bk pointers are still attacker-
  controlled. For more information on the unlink() technique and the
  aa4bmo primitive:

  https://www.openwall.com/articles/JPEG-COM-Marker-Vulnerability#exploit
  http://phrack.org/issues/61/6.html#article

- Last, with this aa4bmo primitive we overwrite the glibc's __free_hook
  function pointer (this old Debian version does not have ASLR, nor NX)
  with the address of our shellcode in the heap, thus achieving remote
  code execution during the next call to free() in packet_close().

------------------------------------------------------------------------
Practice
------------------------------------------------------------------------

    Now they're taking over and they got complete control
        -- The Interrupters, "Liberty"

To mount this attack against sshd, we interrupt a call to free() inside
sshd's parsing code of a DSA public key (i.e., line 144 below is our
free(chunk_Y)) and exploit it during one of the free() calls in
packet_close() (i.e., one of the lines 341-344 above is our
free(chunk_X)):

------------------------------------------------------------------------
136 buffer_get_bignum2(Buffer *buffer, BIGNUM *value)
137 {
138         u_int len;
139         u_char *bin = buffer_get_string(buffer, &len);
...
143         BN_bin2bn(bin, len, value);
144         xfree(bin);
145 }
------------------------------------------------------------------------

Initially, however, we were never able to win this race condition (i.e.,
interrupt the free() call at line 144 at the right time). Eventually, we
realized that we could greatly improve our chances of winning this race:
the DSA public-key parsing code allows us to call free() four times (at
lines 704-707 below), and furthermore sshd allows us to attempt six user
authentications (AUTH_FAIL_MAX); if any one of these 24 free() calls is
interrupted at the right time, then we later achieve remote code
execution inside the SIGALRM handler.

------------------------------------------------------------------------
678 key_from_blob(u_char *blob, int blen)
679 {
...
693         switch (type) {
...
702         case KEY_DSA:
703                 key = key_new(type);
704                 buffer_get_bignum2(&b, key->dsa->p);
705                 buffer_get_bignum2(&b, key->dsa->q);
706                 buffer_get_bignum2(&b, key->dsa->g);
707                 buffer_get_bignum2(&b, key->dsa->pub_key);
------------------------------------------------------------------------

With this improvement, we finally won the race condition after ~1 month:
we were happy (and did a root-shell dance), but we also felt that there
was still room for improvement.