openssh unix dev - Dec 2008 - DSA harmful for remote authentication to compromised hosts?

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-

On Tue, Dec 09, 2008 at 04:07:17PM -0800, Simon Kirby
wrote:
> [...] 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?
This is true for DSA because a DSA signature features a per-signature
random 'k' variable which is used in the signing calculation and then
discarded.

This k value must be kept secret.  If the attacker can guess this k value
(and they know the message being signed and the domain parameters, which
are all normally considered public) they can almost always calculate
the client's private key with no extended calculation.

Hence, if the attacker can break the client's RNG and witness a signature,
they can break the private key.

RSA does not suffer from this particular problem.  There is no
non-deterministic element to the basic RSA signature generation (though
certain padding methods do feature non-deterministic elements)

In either case the private key resides on the client, so a client
vulnerability can result in the private key being compromised.
An insecure RNG is just one sort of host vulnerability in this context.

		Josh