[rwg]

Solaris 9+, recentish Linux, and recentish BSD should all support algorithm $1$ (MD5) at an absolute minimum. Depending on OS versions, you might also be able to choose from $2a$ (Blowfish), $5$ (SHA-256), and $6$ (SHA-512). On Solaris, the list of supported algorithms is in /etc/security/crypt.conf. "man 3 crypt" might tell you what's supported on your Linux and BSD machines.

For NIS, you'd need to ensure that every machine that touches passwords via NIS is configured to use the same algorithm when users change passwords. On Solaris, just configure CRYPT_* in /etc/security/policy.conf the same on every machine. (See the policy.conf man page — in short, you want to change the default algorithm to 1 [or whatever] and set __unix__ to be deprecated.) On Linux and *BSD, how you do it depends on the distro/version.

Fun fact about changing passwords in NIS: When a yppasswd client contacts rpc.yppasswdd to change a user's password, the user's new password is sent crypt()ed, but the user's old password is sent in the clear.