How do you manage passwords for a large number of servers?

Given how important it is to have different passwords for different systems, how does a data centre with thousands of servers manage? I'm only managing a few dozen machines at the moment, but the number tends to grow, especially virtual machines. If you clone a VM, it will have the same password, and if that's part of an automated workflow, there isn't much chance to change it. If you automate changing the passwords, that needs to be done securely, and you're back to a single point of failure. So, what do people do?

I should explain that the problem isn't thinking of passwords (there are plenty of password generators for that) but having an efficient process for setting and recording them, especially when the machines are created automatically.

Most places uses two sets of passwords: On-line authentication and off-line passwords. On-line authentication is typically done with an authentication/authorization (AA) system like Kerberos. Each administrator user is assigned the proper tokens and access rights on the servers

For off-line administration of critical systems the root passwords are stored separately (in our case in a physically disconnected system). All access to the password list is logged, and the user needs to enter a motivation for retrieving the root password of a server. Previously the off-line password list was a printed list stored in a safe.

When provisioning a VM you can typically settle for not having any root password, and just assign on-line authentication/authorization. It's very unlikely that you need to administrate VM machines when your AA servers are off-line.

Even tough you use LDAP, most system have a root/superadmin account for offline authentication, in case of every LDAP instance is down. Things that shouldn´t happen, will sooner than later happen.

LDAP could be your answer in this case, but for the offline root admin password you should use a central CMDB, a new random password for each server, and some sort of automate routines for regularly changing these passwords, and of course verify the changes which have been done.

If you clone a VM (which I don´t think you should do but that is another matter), certain routines must be performed, and one of those should be resetting all passwords.

Edit: To answer your headline "How do you choose passwords for a large number of servers?" - You don't. I would use random for all servers. The real question is how and when you will discover when someone have breached on of your servers.

I'd advise against sharing passwords between machines. If one gets cracked, potentially all your machines are compromised. However if you like the idea of re-installing them all... :)

I wouldn't use passwords that you can work out, e.g. part of the hostname, ip/mac address etc. Personally, I'd use some software designed to store passwords in a secure manner, such as Keepass. Allow keepass to generate the passwords for you. I use at least 12 chars, and include numbers, uppercase & lowercase, but I do use the 'avoid similar looking characters' option, for times when you have to manually type the password.

With that many systems two factor authentication via LDAP would work well. With one factor being an RSA secureid. If a cracker were to discover a user password they would still need at least three RSA number generations in a row before being able to duplicate future generations. Strong password policies to boot.