Gaining root on one box shouldn't give you easy access to all others.
Yes, but this statement relates to my original reply in what way?
And brute force IS affected by complexity, in that a lower-case alphabetic password only requires 26 possible combination, while a password using characters from the entire 8-bit set, requires 256 possible combination. That's the base, so brute-force time goes exponential from there depending on range of characters used.
Only if you know that you can limit your search space that way.
Even if you structure your brute-force by initially ignoring special characters, do some math.
8 characters, letters only, assuming at most the initial letter could be a capital: 417654129152 possible combinations, i.e. ~1^12
8 characters, 7-bit set (8-bit is nonsense, most of them are non-printable): 67675234241018881, i.e. ~1^17
But "letters only" allows us to use pronouncable passwords that people can remember. Hf$6o/r^ may be a 1^17 complexity password, but 99% of the average user will write it down. "sophisticated" is a 1^19 complexity password, and a lot easier to remember.
Special characters are way overrated. The idiocity of limiting password length is a lot more harmful. If your attacker knows how long your password can at most be, his brute-forcing becomes a ton easier, because he can estimate how much of the search space he's got. If my password can be anything (because it's hashed anyways, so what do you care?) then he never knows if he's close or not, and he can not estimate how long it will take at most.
Even if you use a dictionary attack, more space is the answer, not special characters. The OED contains about 300,000 words. Adding a special character or number brings the complexity up to only 1^9. But allowing for two words instead of one brings the complexity to 1^12, and is equally easy to remember.
