On Fedora, root is coming up invalid. WHat is solution?
Nothing that we can do.
If you have bare-metal access (or access to somebody that does), you should be able to boot into single user mode (aka rescue mode) as root and then reset the root password.
Needless to say, you need to limit internet access to this until you've fixed everything.
I've seen a few people saying restore to a backup is the only way to get clean. Restoring a backup isn't the whole solution. That gets your attacker back outside and stops your machine doing anything evil on their behalf.
The main problem after an attack is there's still a vector into your machine. Before you nuke your old install, grab the logs, databases, web files, etc. If it's a recent backup,
diff all the files so you can see any changes. Look in the logs to see what IPs were attacking what. You need to find out how they got into your machine or you'll get re-hacked within minutes of going live.
If it is possible to boot from a medium such as USB or CD, download and run a LiveCD. Then you can make a new password for the machine by chrooting into it and issuing passwd root afterwards to give the root user a new password.
Though I would be very causious about what files and other stuff you back up. Preferably you should reinstall the machine and on the new install you should rethink your security on the server and make it tougher for the people to just hack it.
You will need physical access, at your boot prompt pass "init=/bin/sh" then mount the filesystems you need (/ for sure needs to be remounted readwrite) and change the password back. Once that's done, reboot.
Now you should be aware that you may not have access to the system back, considering you suspect the machine was compromised, you have other work you need to do to ensure that your system is sane. Try and identify when it was breached, and assume everything after that point has been tempered with, go back to a known secure point in time and restore those backups.
Boot from a different OS (LiveCD, USB, etc. - anything that was not connected to the machine previously). Save your documents, sources and anything else that is not an executable binary. Format the machine and install everything from scratch.
Once a machine has been compromised, you can't clean it up. The bad guy owns it; your only solution is to wipe it up.