Please disconnect your box from the network, now.
I started building a SuSE 8.2 System in the morning, by the evening, there was a new root user with no password.
Then you probably had it connected to the network all the time after you first rebooted from installing Linux. Next time just tear down any network interfaces that are up while you work on hardening the system. If you need a connection, first set up ACL's using (this is an AND list, not an OR list) xinetd, daemon config, tcp wrappers, firewall or close down any network-facing daemons, add firewall rules that will only allow traffic to and from trusted repositories like your vendor's and log traffic. Tear down when done.
I have been hacked, Im sure of this
I'd rather rely on a report from your filesystem integrity checker and running Chkrootkit if you have them. Else you could check the logs leading up to the time you saw the user get in, look for anomalies and try to verify the contents of the drives against a copy of your package managers database.
To do this it is necessary you run all by booting an OS from cdrom or floppy distro and not run the OS on the drives and preferably mount partitions read-only. Any databases you use should be trusted copies, made before the compromise and stored on read-only media.
What is the best way forward (without rebuilding the system)??
If logs and audits indicate your box is compromised, or if you want to make a better start then let me first warn you that NOT rebuilding a system is only for people and cases where one would have
- and enough knowledge of Linux, security, compromises and cracker tools
- and are able to identify exactly how the compromise took place
- and are able to identify exactly what changes where made to the disk, partitions and filesystem.
And even then.
If you are not able to perform those basic auditing and forensic tasks, then the three R's are yours to follow: repartition, reformat and reinstall from scratch.
*You could debate that until anyone gives proof positive your system is compromised it isn't, but that's wrong: you have a doubt, and you have (probably) no means to audit your system. This makes using a system that's untrusted a hazard not only for you, but for any box connected to the same (inter)network. I would like to emphasise there are NO valid reasons for postponing what is necessary: Linux is powerful, and running it comes with advantages and responsabilities. Please don't dodge your responsabilities.
For threads on past compromises please look at these:
And for more information about compromises, checking for, or recovery please check out the LQ FAQ: Security references
, post #1 under "Compromise, breach of security, detection".