DH exchange: conspiracy or ignorance?

[leichter_jerrold at emc.com (Leichter, Jerry)]

| Yes, this is certainly bad and a very interesting finding.  These
| checks should clearly be present.  Are there serious practical
| ramifications of this problem though?  In other words, how likely is
| it that the generated public key in the DH key exchange will actually
| be 0 or 1?  It can certainly happen, but our passive attacker would
| have to be passive for a very long time and there is no guarantee that
| the secret key they might eventually get will be of interest to them
| (since the attacker cannot control when a weak public key is
| produced).  Just a thought.
What's special about an computed local value of 1 is that anyone can
easily compute the log of 1:  It's 0.  (Note that a public key value
of 0 is impossible - 0 isn't in the group.  The same goes for any
value greater than p-1.  Checking for these isn't so much checking
for security as checking for the sanity of the sender - if he sends
such a value, he's buggy and shouldn't be trusted!)

In typical implementations of DH, both the group and the generator are
assumed to be public.  In that case, anyone can generate a table of
x, g^x pairs for as many x's as they resources to cover.  Given such a
table, a passive attacker can find log of the secret whenever the
secret happens to be in the table.

Of course, the group is chosen large enough that any conceivable table
will only cover a tiny proportion of the possible values, so in practical
terms this attack is uninteresting.

The fact that two entries in the table (for x=0 and x=p-2) can be
computed "in your head" (well, you might need a pencil and paper for the
second) doesn't make the table any more of an viable attack mechanism.
So the passive observer attack doesn't make much sense to me.

Is there some other attack specific to these values that I'm missing?

BTW, the paper suggest a second test, (K_a)^g = 1 (mod p).  This test
makes sense if you're working over a subgroup of Z* mod p (as is often,
but not always, done).  If you're working over the full group, any
K_a between 1 and p-1 is "legal", so this can only test the common
parameter g, which is fixed.  That hardly seems worth doing - if the
public parameters are bad, you're completely screwed anyway.

                                                        -- Jerry

| Evgeny
| 
| -------------------------------------------------
| Evgeny Lebanidze
| Senior Security Consultant, Cigital
| 703-585-5047, http://www.cigital.com
| Software Confidence.  Achieved.
| 
| 
| -----Original Message-----
| From: sc-l-bounces at securecoding.org [mailto:sc-l-bounces at securecoding.org] On Behalf Of Kowsik
| Sent: Wednesday, September 19, 2007 1:24 AM
| To: SC-L at securecoding.org
| Subject: [SC-L] DH exchange: conspiracy or ignorance?
| 
| http://labs.musecurity.com/2007/09/18/widespread-dh-implementation-weakness/
| 
| K.
| 
| ps: I work for Mu.
| _______________________________________________
| Secure Coding mailing list (SC-L) SC-L at securecoding.org
| List information, subscriptions, etc - http://krvw.com/mailman/listinfo/sc-l
| List charter available at - http://www.securecoding.org/list/charter.php
| SC-L is hosted and moderated by KRvW Associates, LLC (http://www.KRvW.com)
| as a free, non-commercial service to the software security community.
| _______________________________________________
| 
| _______________________________________________
| Secure Coding mailing list (SC-L) SC-L at securecoding.org
| List information, subscriptions, etc - http://krvw.com/mailman/listinfo/sc-l
| List charter available at - http://www.securecoding.org/list/charter.php
| SC-L is hosted and moderated by KRvW Associates, LLC (http://www.KRvW.com)
| as a free, non-commercial service to the software security community.
| _______________________________________________
| 
|