----- 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 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 [EMAIL PROTECTED]
