How to I resolve "sudo: /usr/bin/sudo must be owned by uid 0 and have the setuid bit set" error?

Based on that error message it sounds like you might be better off rebuilding this server from scratch, or deploying from any older backups you might have available to you from before the possible security concern.

The reason for this is that the error message you're seeing is indicative of a much larger security problem that can come from destroying the permission structure of your entire filesystem.

There are some posts out there that discuss ways to fix this, but since this could be indicative of a larger problem (see post below), it might be best to deploy from an uncompromised backup (if available) or rebuild from scratch.

https://askubuntu.com/a/452868

They also asked us for cloud trail logs? Do you have that type of logs?

You should be able to find your auth logs (logs that show access to your server) here:

/var/log/auth.log

Also why would a server break if it is turned off? Could the backups have caused this?

This is not something that would break when the server is turned off, or by your backups. This is something that could happen when someone unintentionally sets the permission on the /usr directory to 777 for all the directories recursively or when your /usr/bin/sudo directory is not owned by the root user.

There are some posts that go over ways to fix this, but again, this may just be a band-aid and I'd follow the advice outlined in the below posts at your own discretion:

• https://bitmapcake.blogspot.com/2014/08/linux-fixing-error-sudo-usr-bin-sudo-must-be-owned-by-uid.html
• https://stackoverflow.com/questions/39361453/usr-bin-sudo-must-be-owned-by-uid-0-and-have-the-setuid-bit-set