DSA harmful for remote authentication to compromised hosts?

[Joshua Hill]

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