O sudo deve ser de propriedade do root e ter o bit set uid set. O bit uid do conjunto da máscara de permissão efetivamente faz com que o binário seja executado como o usuário que o possui, independentemente de quem o invocou. Assim, o sudo pode mudar de qualquer processo que surja.
Ao alterar a propriedade em / usr / bin, você praticamente optou pela instalação. Muitos binários confiam no suid, e tê-los de posse do usuário de qualquer maneira o abre para muitos ataques interessantes.
link tem uma boa explicação de como o suid funciona em detalhes.
Neste ponto, a melhor dica é reinstalar o Ubuntu ...:)