How to SSH after remotely restarting Redhat and enter recovery mode?

I need to enter recovery mode of my redhat box which is running remotely on a virtual machine.

I use RedHat 5 64-bit Enterprise Edition.

I am logged into the box using SSH. I can restart using the restart command but I need to know if I will be able to SSH to it, since I am using it remotely and cannot login through the UI.

The real problem is, I had done a chown -R $USER / on the root directory.

I was trying this as a trial not realizing the consequences, to make something work, which somehow was not working even with the use of sudo.

I killed it mid way. But, because of this stupidity, I can't use sudo.

I have read that I can do something in rescue mode, but I don't understand how do I get into rescue mode remotely. I cannot reinstall linux, that is not a possible option.

Is there anyway I can get back my sudo permissions?

Doing this does not work as of now:

chown root:root /usr/bin/sudo
chown: changing ownership of `/usr/bin/sudo': Operation not permitted
sudo chown root:root /usr/bin/sudo
sudo: must be setuid root

Solution 1:

You can't ssh into recovery mode as ssh won't be running. You need a way to get on to console. If this is a virtual machine and you own the host there should be some way to connect to the host and get on console. If this is a service like AWS then you are out of luck and you need to recover it someway else like building a new instance and detaching the root volume from the bad instance and mounting it on the new one to fix it.