A friend of mine claims that all redhat 9 root passwords are encrypted using the exact same key. Is this true?

Passwords in Redhat are not encrypted using keys; they are run through a one-way encryption algorithm that cannot be reversed. There is no way to 'work backwards' from the encrypted password to figure out the plain-text password. When you put in a password linux runs it through the algorithm and compares the result to the encrypted stored password. If they are the same, it accepts the password as valid.

Do you have any more details on how it's encrypted and how it's not possible to work out the password backwards.

There are different types, but basically they all work by taking advantage of the fact that some mathematical operations can't be reversed. The password is converted into numbers, then some sort of irreversible operation is performed on it.

One example of an irreversible mathematical operation is modulo arithmetic. I could, for example, say that my password CAT. If I say that A is 1, B is 2, etc. then I could represent CAT by the numbers 3-1-20. I can combine them into a single number, 3120. Now I could take my number mod 50. 3120 = -30 mod (50). So now my encrypted password is -30. In order for the computer to accept your password, you have to put in some password such that password = -30 mod (50). There's no way to take the number -30 and figure out that my original password was; you just have to guess passwords until you find one that works. Of course in the real world this wouldn't work very well because it wouldn't take you long to find another number that was -30 mod (50), but you get the idea.

The algorithms used for encrypting passwords are designed so that it's very, very hard to find another password that will produce the same encrypted representation. Even a tiny variation in the password will produce a drastically different end result. Consider these similar passwords encrypted with the MD5 algorithm (I think this is the algorithm that linux uses).

password = 5f4dcc3b5aa765d61d8327deb882cf99
Password = dc647eb65e6711e155375218212b3964
Pasword = 4d2c105ff95dbd829718674aadd3254d

Notice how simply changing the first letter from lower case to capitol or removing an "s" causes the output to be completely different.

You can find a detailed explanation of a real-world password encryption function here: http://www.faqs.org/rfcs/rfc1321.html

Great explination, Nasor!