`----- Original Message -----`

`From: ""Hal Finney"" <[EMAIL PROTECTED]>`

To: <[EMAIL PROTECTED]>; <cryptography@metzdowd.com> Sent: Wednesday, February 06, 2008 8:54 AM Subject: Re: questions on RFC2631 and DH key agreement

Joseph Ashwood writes, regarding unauthenticated DH:I would actually recommend sending all the public data. This does nottakesignificant additional space and allows more verification to beperformed. Iwould also suggest looking at what exactly the goal is. As written thisprovides no authentication just privacy, and if b uses the same privatekeyto generate multiple yb the value of b will slowly leak.I'm not familiar with this last claim, that the value of b's private key (presuming that is what you mean) would slowly leak if it were reused for many DH exchanges. Can you explain what you mean? Are you talking about Lim&Lee style attacks where the recipient does not check the parameters for validity? In that case I would say the private exponent would leak quickly rather than slowly. But if the parameters are checked, I don't see how that would leak a reused exponent.

`I am not immediately aware of any known attacks that have been published`

`about it, but it is fairly obvious that Eve has more information about the`

`private key by having a second key set with the same unknown. With only a`

`single pair Eve's information set is:`

g_1,p_1,q_1,y_1 where y_1 = g_1^x mod p_1 By adding the second key set Eve now has g_1,p_1,q_1,y_1 where y_1 = g_1^x mod p_1 g_2,p_2,q_2,y_2 where y_2 = g_2^x mod p_2

`This is obviously additional information, and with addition key set _i`

`eventually Eve has the information to guess x with improves probability.`

You can then use the gpb trio for DSA, leveraging the key set for more capabilities.Presuming here you mean (g,p,q) as suitable for reuse. This raises the question, is the same set of (g,p,q) parameters suitable for use in both DH exchange and DSA signatures? From the security engineering perspective, I'd suggest that the goals and threat models for encryption vs signatures are different enough that one would prefer different parameters for the two.

`I agree with that, presuming that the private key values are different,`

`there is at least no harm in using different parameters, and it avoids some`

`possible avenues of attack.`

For DSA signatures, we'd like small subgroups, since the subgroup size determines the signature size. This constraint is not present with DH encryption, where a large subgroup will work as well as a small one. Large subgroups can then support larger private exponents in the DH exchange.

`Actually there is nothing stopping parameters for DSA from being prime(160`

`bit)*prime(50000 bit)*2+1 which would have a large enough subgroup as to be`

`effectively unbreakable. Now obviously 50000 bits is excessive, but my point`

`is that finding p with a moderately sized subgroup q and a large additional`

`subgroup is entirely possible, even though it is arguably unnecessary.`

Now it may be argued that large subgroups do not actually increase security in the DH exchange, because index calculus methods are independent of subgroup size. In fact, parameters for DSA signatures are typically chosen so that subgroup based methods such as Shanks that take sqrt(q) cost are balanced against estimates of index calculus work to break p. However, this balancing is inherently uncertain and it's possible that p-based attacks will turn out to be harder than ones based on q. Hence one would prefer to use a larger q to provide a margin of safety if the costs are not too high.

`I would consider that except for (semi)ephemeral parameters the cost of`

`finding an appropriate prime are minor relative to the other considerations.`

`This is especially true with signature parameters where a signing pair can`

`be worth more than all the data authenticated by it.`

While there is a computational cost to using a larger subgroup for DH exchange, there is no data cost, while for DSA there are both computational and data costs. Therefore the tradeoffs for DH would tend to be different than for DSA, and a larger q would be preferred for DH, all else equal. In fact it is rather common in DH parameter sets to use Sophie-Germain primes for q.

`I don't know if they are "common" but they are definitely a good idea, or at`

`the very least using parameters with very large factors of p-1. Primes of`

`the form q*k+1 for small k are certainly a good idea.`

We may also consider that breaking encryption keys is a passive attack which can be mounted over a larger period of time (potentially providing useful information even years after the keys were retired) and is largely undetectable; while breaking signatures, to be useful, must be performed actively, carries risks of detection, and must be completed within a limited time frame. All these considerations motivate using larger parameter sets for DH encryption than for DSA signatures.

`I'm not as certain about that last point. My experience has been that on`

`most occassions the parameters are close to the same size.`

`Joe`

--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]