Keep in mind that I am no expert or anything, but I just like to rant on rootkit, so forgive me.
this is just my 2cents (take it for what its worth):
Rootkits are a major pain in the ass.
If you have gotten a rootkit or you strongly suspect it and you want to do some investigating, don't shutdown or reboot the machine. Pull the plug on the powersupply to bring the machine down hard. Then pull the drive, put it in another machine and DON'T MOUNT IT. Use dd to make a drive image of it.
Then do all your investigations with that drive image or copies of that image. You don't want to risk altering any of the data on the actual drive. You want to keep at least one untouched copy of the drive image. So multiple copies is a good thing.
To recover from a rootkit you format the harddrive and reinstall and recover your data from backups (as long as the backups can be trusted, the purpose of investigating is to determine how badly you've been compromised and hopefully for how long. You don't use the same sudo-enabled or root passwords on multiple machine right? Don't use any ssh keys or anything like that on that rooted server, right? .. otherwise you can probably expect rootkits on your other machines also. Keyloggers are a bitch).
Probably a good:
dd if=/dev/urandom of=/dev/hda
or similar is a nice way to oblterate anything that may be hiding in your mbr.
Things like rootkit hunter are nice, but they will completely fail against any sophisticated attack or remotely modern kernel-module rootkit.
Combining skills and observations with the standard tools and things like chrootkit can usually help you detect a rootkit, but it's not 100% reliable. Some rootkits are going to be devilishly hard to detect.
Kernel module rootkit modifies your kernel behavior in order to hide any sort of hacker activity. So you can do things like return false sizes on files, record keyloggers, hide network activity, hide folders and similar such things.
Since everything in your system depends on the kernel anything running on your system can't be trusted.
For instance RPM has a handy checksum feature to check to see if files are corrupted. Well with a kernel level rootkit they can fool RPM into calculating out the 'correct' checksum for a modified file.
To reliably detect rootkits you can do a few different things though.
One is to run a checksum'ng program like Tripwire. The first time you run it it will make hashes of every file you want it to check. Then on subsiquent runs you will use those stored hashes to ensure the purity of your system.
Since you can't trust your system you have to run it from something other then the installed OS. So you'd run tripwire from a knoppix cdrom or use removable drives and keep a workstation handy (and off network) for that sort of thing. Then you'd record the checksums to read-only media preferably.
Also you'd have to run it before and after each time you perform a system update.
Needless to say this sort of thing quickly becomes a huge headache and very expensive very quickly.
The second way is to run a 'network intrusion detection system' like Snort. With snort you can monitor networks for any sort of 'naughty' behavior.
It'll make it possible to detect things very quickly like a IRC channel being run from a FTP server.
Of course the best thing for Snort is to be ran on a workstation that is undetectable so that attackers don't try to take over it or try to hide activity from it. Having a 'passive newtork tap' is a effective way to do this.
With nicer switches they often have a tap built-in so you can sniff the network activity going on on all the ports.
Otherwise you can make passive taps fairly easily from things like hubs or you can purchase them and you can place that tap in between your network and your external firewall to capture all traffic going in and out of your network.
Again this can get expensive and give big headaches.
But these are about the only reliable way to determine if you have a sophisticated rootkit installed. Remember if you suspect you've been rooted you can't trust anything your system tells you.
Of course a more reasonable approach is just to keep your system as secure as possible and as updated as possible.
Of course be happy that your running Linux and have these capabilities like Snort or Tripwire freely aviable if you need them.
Those poor Windows bastards didn't have a OS sophisticated enough to require kernel driver rootkits until W2k/Windows XP came along and now they are being raped right and left with them. (which is why it's becoming more and more difficult to remove 'viruses' from Windows and one of the reasons why if you 'remove' a hacked file or service and after you reboot often it will be back like nothing ever happenned)
Windows simply lacks the openness and tools to deal with this sort of thing... Vista tries to counter this threat a bit by requiring signed drivers for the 64bit version of Vista, but I beleive this has already been circumvented.
Want to find some Windows rootkits and discussion, just head on down to:
http://www.rootkit.com/