Cookbook method for fixing ssh host-based authentication 
Problem: 
rsh hostname doesn't require a password.  I want 
ssh hostname to work the same way, for lots of users, such as within the student.cs environment, connecting to cpuxx.cs.  
 
-  First solution: use public-key encryption.  This requires copying each    user's public key (from the source machine to the destination machine).   This is not practical due to the number of users, and the per-user setup   requirements.  See Debian HowTo for some notes.
-  Second solution: use hosts-equiv with host authentication.  This requires more server setup, but luckily, most of it is already done in the cs.uwaterloo environment.   As with rsh, authentication is at the host-level, that is, we explicitly trust the client to not spoof the username.  If you do not trust the client (enough to list them in your /etc/hosts.equiv file), don't use this method! 
There are two parts; server-side and client-side.  
 Note on Nomenclature 
"Server" and "Client" are somewhat arbitrary, and could instead be "machine1" and "machine2," but this document was originally written to discuss connecting from a linux desktop to a cpuXX server.  "Server" is the machine you're connecting to, "Client" the machine you're connecting from. 
 Client side: 
 
-  enable host-based authentication and keysigning in ssh client configuration file /etc/ssh/ssh_config
      HostbasedAuthentication yes
      EnableSSHKeysign        yes
 
-  Your host  should have a  key pair of files (normally in /etc/ssh)  
-  ssh_host_TYPE_key 
-  Replace TYPE with one of ( rsa dsa ecdsa ed25519 )
 
-  ssh_host_TYPE_key.pub 
-  Replace TYPE with one of ( rsa dsa ecdsa ed25519 )
 
 
-  If there isn't, generate it with: ssh-keygen -tTYPErun as root (when it prompts you for a filename, use /etc/ssh/ssh_host_TYPE_key )
-  Replace TYPE with one of ( rsa dsa ecdsa ed25519 )
 
 Server side: 
Conveniently, for most cscf and math adminstered hosts, the server side has already been dealt with.
 
-  /etc/ssh/sshd_configshould enable host-based authentication:
      HostbasedAuthentication yes
      IgnoreRhosts            no
    If you changed this, you must restart the ssh daemon for the changes to take effect.
 
-  copy client's public key into the server's global ssh_known_hosts file      (linux client: /etc/ssh/ssh_host_rsa_key.pub; linux server:/etc/ssh/ssh_known_hosts2; solaris server: possibly:/software/ssh-openssh/data/local/ssh_known_hosts2)
-  copy client's full hostname to /etc/hosts.equiv(possibly already set up for rsh).
That's it.
 Debugging: 
On the client machine, run 
ssh -v host_machine
You should get a page of data that ends with something like:
      debug1: Authentications that can continue: publickey,password,keyboard-interactive,hostbased
      debug1: Next authentication method: hostbased
      debug1: Remote: Accepted for gl01.student.cs.uwaterloo.ca [129.97.152.34] by /etc/hosts.equiv.
      debug1: Authentication succeeded (hostbased).
      debug1: channel 0: new [client-session]
      debug1: Entering interactive session.
      Last login: Wed May 11 13:20:42 2005 from client_machine
      [etc. message of the day, & prompt]
If, instead, it ends with: 
      debug1: Authentications that can continue: publickey,password,keyboard-interactive,hostbased
      debug1: Next authentication method: hostbased
      ssh-keysign not enabled in /etc/ssh/ssh_config
      ssh_keysign: no reply
      key_sign failed
      debug1: Next authentication method: publickey
      debug1: Trying private key: /u5/drallen/.ssh/identity
      debug1: Trying private key: /u5/drallen/.ssh/id_rsa
      debug1: Trying private key: /u5/drallen/.ssh/id_dsa
      debug1: Next authentication method: keyboard-interactive
      debug1: Authentications that can continue: publickey,password,keyboard-interactive,hostbased
      debug1: Next authentication method: password
      drallen@cpu10.student.cs's password:
...you need to add the 
KeySign line to 
/etc/ssh/ssh_config on the client.
...similarly, ending with:
      debug1: Authentications that can continue: publickey,password,keyboard-interactive,hostbased
      debug1: Next authentication method: publickey
      debug1: Trying private key: /u5/drallen/.ssh/identity
      debug1: Trying private key: /u5/drallen/.ssh/id_rsa
      debug1: Trying private key: /u5/drallen/.ssh/id_dsa
      debug1: Next authentication method: keyboard-interactive
      debug1: Authentications that can continue: publickey,password,keyboard-interactive,hostbased
      debug1: Next authentication method: password
      drallen@cpu10.student.cs's password:
...you need to add the 
HostbasedAuthentication line on the client.
If the "Authentications that can continue:" lacks "hostbased", the server is not set up to allow hostbased authentication.
   debug1: Next authentication method: hostbased
   debug1: Authentications that can continue: publickey,keyboard-interactive,hostbased
   debug1: Authentications that can continue: publickey,keyboard-interactive,hostbased
   debug1: No more client hostkeys for hostbased authentication.
   debug1: Next authentication method: publickey
   debug1: Trying private key: /u5/drallen/.ssh/identity
   debug1: Trying private key: /u5/drallen/.ssh/id_rsa
   debug1: Trying private key: /u5/drallen/.ssh/id_dsa
   debug1: Next authentication method: keyboard-interactive
   Password:
"No more client hostkeys for hostbased authentication" suggests that either end of the
connection was having trouble looking up the reverse IP of the client
and matching it against the key. 
Hope this helps!
...some of this information came from 'man ssh' and other parts from the Open 
SSH quick reference: 
http://tiger.la.asu.edu/Quick_Ref/OpenSSH_quickref.pdf 
 Addendum: X Forwarding 
While you're editing sshd_config and ssh_config, you might want to enable X Forwarding.  
In sshd_config, you'll need 
X11Forwarding yes 
If you want to make X Forwarding turned on by default for outgoing connections, in ssh_config you'll need 
ForwardX11Trusted yes (for OpenSSH 3.8 and above) or 
ForwardX11 yes (for older OpenSSH versions)
See 
http://www.cs.uwaterloo.ca/cscf/howto/ssh/ForwardX11.shtml
 for more details.
-- 
DanielAllen - 11 May 2005
I found I had to install 
xauth in order for 
sshd to set up the proxying.  It appears 
sshd runs 
xauth to update 
~/.Xauthority before setting the 
DISPLAY environment variable.
-- 
IlguizLatypov - 22 Aug 2007
If you need to collect a bunch of public keys into the ssh_known_hosts file on the server side, you can also do this using ssh-keyscan.
-- 
ChristopherCalzonetti - 19 Feb 2009