What program do you use for detecting Rootkits? How do you know what to trust?
On Unix-based systems, Tripwire is a good general "what changed on this machine today?" solution. There are other, more specific rootkit detectors out there, but I've always thought that it was a matter of playing catchup with the bad guys; you'll never be sure that your rootkit detector is up-to-date enough to catch all of 'em.
I have been using OSSEC and have been really impressed by the results
None of the available free rootkit checkers for Linux are very good. They can't even detect all the publicly available (most for many years) rootkits that you can find source code for on sites like packetstorm. Not only do they not do a good job with the known threats, but there is good reason to expect that they will perform worse against any intelligent attacker, who has the opportunity test against the detectors in advance of using his rootkit.
Furthermore, there is no reason to assume that a rootkit will have an on-disk footprint that can be detected with a tool like Tripwire. Kernel rootkits can deceive any software running on the infected system; even if you're running a trusted binary from read-only media it might be getting falsified information from the operating system. Furthermore, memory-resident-only malware is not just a theoretical worry any more; its use has been documented by security firms such as Mandiant. Against such a rootkit, even offline analysis would be ineffective, although on the plus side the malware might not survive the reboot.
There are some solutions, but not free or cheap. A large corporation or government entity can spring for a memory forensics tool like Second Look from Pikewerks, or one could hire a security consultant who might employ such a tool as part of their arsenal. Others, go ahead and use the available anti-rootkit programs. They are not 100% useless. Just do what you can to avoid being rooted by someone with a customized, non-public rootkit. How large is the risk? Unfortunately, there are no statistics I know of to go by. Clearly Linux does not suffer from the enormous volume of "mass malware" that Windows does, but how common are stealthy, targeted attacks?
(Disclosure: I am an author of the Second Look product mentioned above.)
I think the standards are chkrootkit and rkhunter.
I would use both, and run them daily. I know chkrootkit has an option to only notify you if anything changes (avoiding daily false-alerts).
Running both helps to 1) not need to "trust" either, and 2) protects against attacks that try to specifically hide from one or the other.
Rootkit checker should not be installed on your target machine. I do not know either chrootkit or rkjunter but if they required to be installed on the end machine they do not protect you much. A rootkitcheck software that runs on the target machine runs the risk that the rootkit (or the person who installed it) would compromise it and thus it would not provide you with the protection you seek.
Personnally I go with Tripwire. What Tripwire does is take a hash (fingerprint) of all the file on your system and it lets you know when a file change. It allows for a remote host to be your "trusted" machine and have it scan your target machines for any file change. If a change is detected then you know something went wrong. Of course, you need to have some change control so regular updates on your system does not get flagged as an intrusion.
To be on the safe side, at regular intervals, you want to go and make changes on your target machine to make sure that tripwire will report it. You also want to cut the connction between the target and the trusted machine running tripwire to make sure that it will be detected. This is as important as making sure you can restore your backups.