How does sudo actually work?

Question

How is it possible for sudo to actually function? If it's just a normal program, couldn't you make the same thing without requiring the user to authenticate, giving anyone with access to a computer automatic root access? And how can it do things as root without root's password?

Answer 1

TL;DR: Sudo has a special flag

Sudo has the set uid bit set as you can see here:

ls -l `which sudo`
-rwsr-xr-x 2 root root 127668 2013-02-27 21:41 /usr/bin/sudo

Setting the suid bit for a file means what the program gets run with the effective uid or the suid-ed user. And in this this case user root has uid 0, granting it elevated permissions.