Comment 3 for bug 582858

Yes, indeed, this is a problem with the rsh-server package. The problem is that per libpam-modules:

pam (1.1.0-3) unstable; urgency=low

  * pam_rhosts_auth module obsolete, symlink removed

    The pam_rhosts_auth module was dropped upstream prior to the lenny
    release and a compatibility symlink provided in the libpam-modules
    package, pointing at the new (and not 100% compatible) pam_rhosts
    module. This symlink has now been dropped. If you still have
    references to pam_rhosts_auth in your /etc/pam.d/* config files, you
    will need to fix these, since they no longer work.

    For information on using pam_rhosts, see the pam_rhosts(8) manpage.

 -- Steve Langasek <email address hidden> Wed, 02 Sep 2009 16:17:16 -0700

Yet in /etc/pam.d/rsh from rsh-server:

auth required pam_nologin.so
auth required pam_env.so
auth required pam_rhosts_auth.so
account required pam_unix_acct.so
session required pam_unix_session.so