I'm sorry to hear this. For now: get the box off the net. You don't know if you're running a rootshell on some high port. Even after finding out which daemon(s) (is|are) exploited, what rootkit was used, which of the ps-utils have been replaced, etc etc, there should be no other clear answer than
"rebuild your box from scratch"
What you will need to do in the first place (as a lot of other people should do) is get an more active grip on your boxens security. I know it takes discipline, but subscribing to your vendors + a general Linux mailinglist (and actually reading it) :-] , looking at SANS
advisories shouldn't take much of your time. Acting on that info can be the difference between having root and being rooted.
Securing your server boxen should start at the base. Don't install development stuff, and compile a new kernel with either GRSecurity or LIDS which will take away a lot of capabilities that can be used against the system. Don't have user accounts,
and when needed use sudo to get root access. Set resource limits on processes and disk quota, and use PAM for authentication. When using GRSecurity, profile your binaries with "grtrace" and group your users as mentioned in the docs for allowing/taking away exec/suid/proc/net_raw and other capabilities, and turn logging on.
Lock down binaries (chattr +iu) when done installing and configuring or consider running em off a "-o ro" mounted partition. Add passive integrity detection to check up on your system's state using Aide or Tripwire (and save the databases offsite), add chkrootkit, and maybe top it off with another checking package like COPS, Tiger, TARA or the like.
Stop and uninstall all unnecessary services. Review any daemon version before installing. Ditch X11, Lpd, all "r" services (rsh, rlogin, rexec, rcp). Restrict access by firewall from obviously spoofed sources and rate-limit in/out traffic like ICMP. Add active intrusion detection using Snort. It will warn you of incoming exploits and other malicious actions against your system. (don't mistake portsentry for an alternative). If possible, set up remote logging so theyll have to go tru a lot to get to those logs, or have a separate log partition to twart DoSsing by filling up disks.
As for an MTA your choices are exim, postfix or qmail. IMO skipping Sshd isn't good, OpenSSH_2.9p2 is considered safe from aprox Feb last year, while the commercial counterpart had flaws. When configured w/o using Protocol 1 tighten security by using Allow|DenyGroups, and compile with TCP Wrappers. As for ftpd's Wu-ftpd is notorious for its flaws. A more secure ftpd could be Muddleftpd or Vsftpd, or if you only need ppl to download stuff you could check out oftpd. Ive been using Muddleftpd for about 3 yrs now, and there still isnt a root exploit to go with it.
For the MTA and ftpd part, if unsure, run as non-root, allow only anonymous read access to ftpd, and chroot the services. I'm using "rootjail" to help me chroot services and it works well.
For docs search (linuxdoc.org) for/check out:
, especially the "UNIX Computer Security Checklist",
CERT, root compromise, part F
LASG: Linux Administrator's Security Guide,
Security Quick-Start HOWTO for Linux,
"Bastille Linux Hardening System"
The rest of my security reference list is in the second reply here: "possibly a dumb(..)"