DSA harmful for remote authentication to compromised hosts?

[Simon Kirby]

Hello!

I'd just like to run this by some people who are more familiar with
the RSA and DSA algorithms and their use within (Open)SSH.

I've been using OpenSSH happily with the assumption that using key-based
authentication (RSA or DSA public keys pushed to .ssh/authorized_keys on
remote hosts) provides a number of benefits, including an important
security-related one -- Logging in to a known-root-compromised host is
"safe" in that whatever is done on the remote machine would not
compromise my private key in any way that would allow an attacker to
further use data from an established session to compromise other hosts
where the same pulic key is installed.

However, a little while ago, as part of the whole Debian "oops we
commented out the rand() part of the random function", their
announcements at the time mentioned that use of DSA keys to hosts with
broken random generators would also compromise the DSA key.

If this is true, any compromised host could also have a compromised
random generator, and this breaks my containment assumption.

Does anybody know if this is true, and if so, is RSA also in a similar
boat?  If not, is it really safe to use DSA keys at all where a remote
random generator cannot be trusted?

Simon-