Damian Gerow wrote:

"For this reason we now believe PuTTY's DSA implementation is probably OK. However, if you have the choice, we still recommend you use RSA instead."

Indeed so - but saying that (in their opinion) RSA IS implimented better and more securely in puTTY than DSA can hardly be the same as saying DSA should be avoided. As I understand it, the problem with DSA is that it is *very* dependent on the random number being random (collisions leading to weaknesses) - and everyone knows that windows is bad at RNG. What (as I understand it) the new putty scheme does is use the secret key to obfusc the random value a little - hashing it with both the private key and the hash of the message being signed - hoping to pull enough entropy out of those two to reduce the possibility of discovery of the random value due to it being limited to a subset of the "range" it should have. obviously, this approach won't produce gold from straw - you still have a limited set of possible values - but it should distribute them evenly across the range in a key-dependent manner, so that knowlege of the limited possible values would have to be per-key or involve knowledge of the private key (which is a game-over scenario anyhow) so my understanding of the above warning is that the games puTTY plays with the keyspace is *probably* enough to fix the lousy randomness of the windows platform - but they recommend that you use RSA where the randomness of a prng is not an issue.

At 07:44 PM 5/23/03 +0100, Dave Howe wrote: ...

Indeed so - but saying that (in their opinion) RSA IS implimented better and more securely in puTTY than DSA can hardly be the same as saying DSA should be avoided. As I understand it, the problem with DSA is that it is *very* dependent on the random number being random (collisions leading to weaknesses) - and everyone knows that windows is bad at RNG. What (as I understand it) the new putty scheme does is use the secret key to obfusc the random value a little - hashing it with both the private key and the hash of the message being signed - hoping to pull enough entropy out of those two to reduce the possibility of discovery of the random value due to it being limited to a subset of the "range" it should have. obviously, this approach won't produce gold from straw - you still have a limited set of possible values - but it should distribute them evenly across the range in a key-dependent manner, so that knowlege of the limited possible values would have to be per-key or involve knowledge of the private key (which is a game-over scenario anyhow)

If you're willing to make some plausible assumptions about SHA1, you can do this with a lot of confidence. SHA1(secret_key || hash(message)) is deterministic, but an attacker who doesn't know secret_key cannot distinguish it from random, and so can't predict it. Conditioned on the attacker's knowledge and computing resources, the random number generated in this way is uniformly distributed. This depends on an (IMO) unprovable assumption about SHA1: that the expected work needed to predict its output is approximately bounded by the lower of 2^{160} or the expected work needed to guess its input. FIPS186 (the document that specifies DSA) proposes a cryptographic pseudorandom number generator for use with DSA. That PRNG depends on more-or-less the same property, though it only uses SHA1's compression function. There was a Eurocrypt article describing this kind of idea a couple of years back, though I think they did something a little more mathematically clean than relying on SHA1 directly. (I'm away from my books, so you'll have to look it up yourself if you're interested.)

so my understanding of the above warning is that the games puTTY plays with the keyspace is *probably* enough to fix the lousy randomness of the windows platform - but they recommend that you use RSA where the randomness of a prng is not an issue.

RSA doesn't need randomness in generating signatures, though if you're generating the keypair on the same device, you really need to have some confidence in your random numbers, or you'll shoot yourself in the foot. And if you want to blind RSA to prevent timing and some power analysis attacks, you'll need to have a source of random or cryptographic pseudorandom numbers. --John Kelsey, kelsey.j@ix.netcom.com PGP: FA48 3237 9AD5 30AC EEDD BBC8 2A80 6948 4CAA F259

Thus spake Mike Rosing (eresrch@eskimo.com) [23/05/03 13:32]:

You might find this interesting: http://csrc.nist.gov/CryptoToolkit/tkdigsigs.html

I'll check it out. Thanks.

I'd think a web search on buzz words found there would come up with something to read :-)

Wrong buzzwords -- Dynamic Systems Analyst, Dynamic Signal Acquisition, Decision Support and Analysis, Design Sensitivity Analysis, etc. etc.