Chuck wrote:

> > I'd clear OS partition to zero, then reformat prior to install.
> >
> > Grant.
>
> Who's to say the format utility isn't compromised as well? I'd boot from
> a CD-ROM (something non-writable) and do the format from there.

Doing the repartition is normally done from a boot CD or network boot.
Personally, if possible, I'd set aside the compromised disk and install
a new one, then use the compromised disk on an isolated Knoppix LiveCD
box to examine the logs with the tools from Knoppix, not local tools,
to see what traces of the attack are in place.

But the OP should consider every account that existed on that machine,
or which could be sniffed from that machine, compromised. This sort of
thing is common in environments where some admin says "we have a
firewall, we don't have to worry about internal machine updates,
they're stable, don't patch them" and one machine gets compromised.
It's now appropriate to lock down *EVERYTHING*, make sure your backups
are offsite, and probably change everyone's passwords and rebuild core
servers to make sure they haven't also been compromised.

These are harsh lessons learned way, way back in the Morris Worm
incident of 1988: the lessons are still valid.