What exactly differentiates the root user from every other user?

Root is user 0

The key thing is the user ID 0. There are many places in the kernel that check the user ID of the calling process and grant permission to do something only if the user ID is 0.

The user name is irrelevant; the kernel doesn't even know about user names.

Android's permission mechanism is identical at the kernel level but completely different at the application level. Android has a root user (UID 0), just like any other system based on a Linux kernel. Android doesn't have user accounts though, and on most setups doesn't allow the user (as in the human operating and owning the device) to perform actions as the root user. A “rooted” Android is a setup that does allow the device owner/user to perform actions as root.

How setuid works

A setuid executable runs as the user who owns the executable. For example, su is setuid and owned by root, so when any user runs it, the process running su runs as the root user. The job of su is to verify that the user that calls it is allowed to use the root account, to run the specified command (or a shell if no command is specified) if this verification succeeds, and to exit if this verification fails. For example, su might ask the user to prove that they know the root password.

In more detail, a process has three user IDs: the effective UID, which is used for security checks; the real UID, which is used in a few privilege checks but is mainly useful as a backup of the original user ID, and the saved user ID which allows a process to temporarily switch its effective UID to the real user ID and then go back to the former effective UID (this is useful e.g. when a setuid program needs to access a file as the original user). Running a setuid executable sets the effective UID to the owner of executable and retains the real UID.

Running a setuid executable (and similar mechanisms, e.g. setgid) is the only way to elevate the privileges of a process. Pretty much everything else can only decrease the privileges of a process.

Beyond traditional Unix

Until now I described traditional Unix systems. All of this is true on a modern Linux system, but Linux brings several additional complications.

Linux has a capability system. Remember how I said that the kernel has many checks where only processes running as user ID 0 are allowed? In fact, each check gets its own capability (well, not quite, some checks use the same capability). For example, there's a capability for accessing raw network sockets, and another capability for rebooting the system. Each process has a set of capabilities along side its users and groups. The process passes the check if it is running as user 0 or if it has the capability that corresponds to the check. A process that requires a specific privilege can run as a non-root user but with the requisite capability; this limits the impact if the process has a security hole. An executable can be setcap to one or more capabilities: this is similar to setuid, but works on the process's capability set instead of the process's user ID. For example, ping only needs raw network sockets, so it can be setcap CAP_NET_RAW instead of setuid root.

Linux has several security modules, the best known being SELinux. Security modules introduce additional security checks, which can apply even to processes running as root. For example, it's possible (not easy!) to set up SELinux so as to run a process as user ID 0 but with so many restrictions that it can't actually do anything.

Linux has user namespaces. Inside the kernel, a user is in fact not just a user ID, but a pair consisting of a user ID and a namespace. Namespaces form a hierarchy: a child namespace refines permissions within its parent. The all-powerful user is user 0 in the root namespace. User 0 in a namespace has powers only inside that namespace. For example, user 0 in a user namespace can impersonate any user of that namespace; but from the outside all the processes in that namespace run as the same user.

In Linux there are 4 UIDs: RUID (real), EUID (effective), SUID (saved), FSUID (filesystem).

These are nothing more than numbers and are properties of processes, which are stored in a control block in the process table of the Kernel.

The UID '0' has a special characteristic, as it denotes the user root, which has generally unrestricted access rights.

su and sudo are programs to change the user's effective access rights, by starting a new sub-process with the EUID set to the new UID through the SetUID bit of su. This su process then spawns a new shell again in a new sub-process with the 4 UIDs set to the new UID value.

The following example should demonstrate this. Let's say a user rda is logged in over an ssh terminal. ps fax will show the following processes involved:

472 ?        Ss     0:00 /usr/sbin/sshd -D
9151 ?        Ss     0:00  \_ sshd: rda [priv]
9153 ?        S      0:00  |   \_ sshd: rda@pts/1
9154 pts/1    Ss+    0:00  |       \_ -bash

4 processes, the ssh daemon, two processes for the ssh session (and terminal?), the last process is a login shell (denoted by a - in front of bash)

ps faw -eo euser,ruser,suser,fuser,f,comm will show the UIDs of the processes:

EUSER    RUSER    SUSER    FUSER    F COMMAND
...
root     root     root     root     4 sshd
root     root     root     root     4  \_ sshd
rda      rda      rda      rda      5  |   \_ sshd
rda      rda      rda      rda      0  |       \_ bash

Invoking su followed by a successful authentication will result in the following:

EUSER    RUSER    SUSER    FUSER    F COMMAND
...
root     root     root     root     4 sshd
root     root     root     root     4  \_ sshd
rda      rda      rda      rda      5  |   \_ sshd
rda      rda      rda      rda      0  |       \_ bash
root     rda      root     root     4  |           \_ su
root     root     root     root     4  |               \_ bash

The 'bash' process starts a new 'su' child-process with EUID set by SetUID bit to '0' (root), RUID is still set to rda's UID at this point. The 'su' process again starts a new child-process with a new shell, granting the user root access (RUID is now set to '0' too). The user remains at his working directory and the new shell will use the same environment as the parent shell, for example:

server:/home/rda# echo $PATH
/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin
server:/home/rda# pwd
/home/rda

The shell can be closed with exit and the user will be in the parent shell with his original access rights.

The situation is different if 'su' is invoked with a hyphen '-' parameter:

rda@server:~$ su -
Password:
server:~# echo $PATH
/root/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin
server:~# pwd
/root

The shell environment has changed, as the new shell is a login shell, see '-su', which executes some additional configuration scripts:

 9151 ?        Ss     0:00  \_ sshd: rda [priv]
 9153 ?        S      0:00  |   \_ sshd: rda@pts/1
 9154 pts/1    Ss     0:00  |       \_ -bash
 9613 pts/1    S      0:00  |           \_ su -
 9614 pts/1    S+     0:00  |               \_ -su

A login shell should be closed with logout.

In theory, I think it is possible to prevent the user from gaining elevated privileges by removing sudo and su and give no possibility to log on to the system directly (via terminal, ssh, etc) and with no physical access to the device.

Update: Rooting process on Android

As explained in detail here, the possible methods for rooting an Android device depend on the bootloader and the Android system property ro.secure.

The target is always the same, to install the su binary in /system and make it setuid(0).

Device with unlocked bootloader:

Pull the stock ROM with dd from the device, add su, repackage (or download such a modified ROM), reboot the device in flash mode and flash the modified ROM.

Device with ro.secure=0:

This system property controls whether commands typed in an adb shell are run as root (ro.secure=0) or as an unprivileged user (ro.secure=1) The value of ro.secure is set at boot time from the default.prop file in the root directory, which is only accessible by user root and thus, secure.

In most cases this ro.secure is set to 1, but some manufacturers set this to 0. This can be checked by running the command getprop ro.secure in a terminal emulator on the device or in an adb shell. If it is set to 0, rooting is quite easy, connect it to a computer, run adb, mount /system as read-write, install su.

Device with locked bootloader:

Such a device has a recovery that does not allow to flash a custom ROM, which has not been signed by the manufacturer. The only way to gain root access in this situation is by exploiting a security vulnerability in one of the running system processes, which run in privileged mode, and hack it to allow the execution of "arbitrary code". This code usually mounts /system and installs su permanently.

In general, it's just that the effective uid is 0. The "setuid" bit on executables actually sets the effective uid of the process. If the effective uid is not zero and the real uid is not zero, the program is running as an "unprivileged" user. The following apply:

Unprivileged processes may only set the effective user ID to the real user ID, the effective user ID, or the saved set-user-ID. Unprivileged users may only set the real user ID to the real user ID or the effective user ID.

As far as Android is concern, no, I don't think removing sudo and su is enough -- if any program can have the seteuid bit set, that program can potentially run with uid = 0. If there is any possibility of having access to the internal filesystem as root at any time, then such a program may be introduced and root access is feasible.