----- Original Message ----- From: ""Hal Finney"" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>; <cryptography@metzdowd.com>
Sent: Sunday, February 10, 2008 9:27 AM
Subject: Re: questions on RFC2631 and DH key agreement

Joseph Ashwood writes:
From: ""Hal Finney"" <[EMAIL PROTECTED]>
> Joseph Ashwood writes, regarding unauthenticated DH:
>> 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.

That's hardly grounds for saying that the value of the secret "will
slowly leak". You have given no reason to believe that this information
will be of any practical value to Eve.

We obviously disagree. Security is alway about information control, and disclosing additional information for no gain is always a bad idea.

Expressing the equations differently:
Y_i = g_i^X - k_i*p_i
is equivalent to
Y_i = g_i^X mod p_i

Since Y_i, g_i, and p_i are known, k_i is irrelevant, and g_i and p_i can even be chosen, simple algebra shows that not all Xs can be discovered from a given set, but it also says that sets of possible X can be determined from each triple, and by choosing g,p the overlap of the sets can be reduced. Creating an oracle for Y,g,p triples out of the client is begging for an adaptive attack.

After all, exactly the same observation might be made about a digital
signature, that each signature gives additional information about the
private exponent.

Actually there is an additional random variable in the signature, and 3 additional k_i so the algebra says that the sets will overlap simply too much for a similar set-based attack to work.

This is a largely fuzzy-logic based attack. And while I obviously haven't sorted it through that far should allow for a probability sorting of values for X. Joe
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to