Diffie Hellman Test "g likely does not generate a prime oder subgroup"

[Wolfgang]

Hi,

I was wondering why the Diffie-Hellman Test Suite (java/com/google/security/wycheproof/testcases/DhTest.java) tests for the assertion at line #301 ("g likely does not generate a prime oder subgroup").

In case of a safe prime "r" would be calculated as p >> 1 [that is (p-1)/2]. The condition requires that g^r = 1 mod p. 

Sometimes this should be true: if the g was chosen that it generates a subgroup of order (p-1)/2 then this condition would be fulfilled. 

However, if g generates the whole group [the order of g is (p-1)] then this condition would fail. 

Is there any reason why g should be chosen so that it generates the subgroup rather than the full group? I could not find a source for why that is favorable or necessary.

Could you please tell me if I am missing something?

Thanks,

Wolfgang

[Thai Duong]

Hi Wolfgang,

The comment on top of the test describes the issues when g doesn't generate a prime order subgroup. Suppose the order of g is n, Pohlig-Hellman makes the running time of discrete log in the subgroup generated by g depend only on the largest prime factor of n. Thus you want n to have large prime factors, so it's best just choosing it as a prime.

If r = (p-1)/2 is a prime, it's totally fine security-wise to choose g such that g has order r. Larger r gives better security, but also hurts performance (because you'll have to compute g^s (mod p) where s in [1, r-1] in DH). Thus the rule of thumb is to choose r = 2n where n is the security level that you get with the prime field. You have to multiply by 2 because all group-based crypto systems are vulnerable to the generic Shank's baby-step giant-step attack.

Not exact science, but if p is 1024-bit, n is 80 and r is 160. If p is 2048, n is 112 and r is 224. See also NIST SP 800-56A, section 5.5.1.1.

Cheers,

Thai.

Thanks,

Wolfgang

--
You received this message because you are subscribed to the Google Groups "wycheproof-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to wycheproof-users+unsubscribe@googlegroups.com.
To post to this group, send email to wycheproof-users@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/wycheproof-users/6f2c241a-53ce-47e1-a87f-aa28f737a672%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Daniel Bleichenbacher]

Another reason for choosing g with a prime order is that the group generated by g probably satisfies the 

Decision Diffie Hellman assumption, which is not the case when g generates the full multiplicative group.

This DDH assumption isn't completely necessary for security but all the standards I've checked

choose such groups, i.e. choose g with a prime order.

The question of using small subgroups for better performance is not so clear. Since the size q of

the subgroup generated by g is not part of the public key it is not possible to verify a public key.

A verification of a public key would be a clean way to avoid subgroup confinement attacks.

With no public key verification a provider is basically forced to use large keys to counter 

subgroup confinement attacks. 

The "likely" in "g likely does not generate a prime order subgroup" is there because smoothDivisor

takes short-cuts which could lead to false positives.

To view this discussion on the web visit https://groups.google.com/d/msgid/wycheproof-users/CAPnkLjweY42aPpLsPp%3Dt8JJADv-6rHaFDN9gsdKZCEdYwgpSSw%40mail.gmail.com.

[woif...@gmail.com]

Thank you for your answer. 

Please correct me if I got something wrong - as I understand it its not a _huge_ issue for security if the order of g is n*q (not prime) as long as the order q has a sufficiently large prime factor.

I checked with two open source (non-Java) libraries for DH parameter generation. I've seen that when I apply the tests specified in DhTest.java both of them fail. 

E.g. one library generated (python code):

p = int('00ef65c91d4444517f8e98b10c33a4142e3e075b1cd8aa24082a8e52410712ee819beb5e8631bc798b46f48f44e587cd9748cd00b1bc'+\

'ca68c8c6d816333d08a6cd9ddb7f33300dc0b8eab9bddb6c86e4ab4025affb3f22658af0ba6c8ad262cb1ed618cc211dd59ab8f65e7d3b966194'+\

'57921829915f07db97e9c916dcfd740301d3fa6bec0932bb75a7e903d3bd5777cd73d292b3ee2d809e86e34a1610d70da38bc3919d5765753874'+\

'2d11558fd79587ffbf4ca2890b0cbe47d56acd83ce328946969dbd117625ce14972c4278a01847faa503201f9c965b75d46b6af429bc2ef0e03d'+\

'5511bcaea69f54777def794a888d43c48b9ad8a145622bb232f7e842eb', 16)

g=2

I've checked that both p and (p-1)/2 are prime (therefore p is a safe prime). DhTest.java in this case calculates 

r = p >> 1 = (p-2) / 2 = q

DhTest.java then checks if g^r = 1 mod p. With the DH parameters generated by these libraries this check would fail (since only g^(r*2) = 1 mod p; order of g is not prime but rather 2*q when q is prime).

Since the libraries I tested would actually fail the wycheproof test suite I was wondering if there's something to be concerned? Should those libraries make sure that the order of g is prime?

Br,

Wolfgang

Thanks,

Wolfgang

To unsubscribe from this group and stop receiving emails from it, send an email to wycheproof-use...@googlegroups.com.
To post to this group, send email to wychepro...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/wycheproof-users/6f2c241a-53ce-47e1-a87f-aa28f737a672%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "wycheproof-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to wycheproof-use...@googlegroups.com.
To post to this group, send email to wychepro...@googlegroups.com.