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: Sunday, February 10, 2008 9:27 AM
Subject: Re: questions on RFC2631 and DH key agreement


> Joseph Ashwood writes:
>> From: ""Hal Finney"" <hal at finney.org>
>> > 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 majordomo at metzdowd.com