questions on RFC2631 and DH key agreement

[Joseph Ashwood]

----- Original Message ----- 
From: ""Hal Finney"" <hal at finney.org>
To: <ashwood at msn.com>; <cryptography at 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 not 
>> take
>> significant additional space and allows more verification to be 
>> performed. I
>> would also suggest looking at what exactly the goal is. As written this
>> provides no authentication just privacy, and if b uses the same private 
>> key
>> to 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 majordomo at metzdowd.com