DhTest.testKeyPairGenerator assertion

[calvin...@rsa.com]

Hi,

I have a question about an assertion used by the DhTest.testKeyPairGenerator and DhTest.testDefaultKeyPairGenerator tests.

These tests generate a DH key pair and then makes the assertion:

assertTrue(x.bitLength() >= (keySize / 2) - 32)

where x is the DH private key value.

According to NIST.SP.800-56Ar2, section 5.6.1.1, the private key, x, is a randomly selected integer in the range 1-(q-1) which doesn't limit the minimum bit length.

FIPS 186-4 section B.1.1 also states that: 0 ≤ c mod (q–1) ≤ q–2 and implies that 1 ≤ x ≤ q–1. So this also indicates that there is not a minimum bit length required.

Is the requirement for this assertion documented anywhere or is it a ‘best practices’ requirement?

Regards,

Calvin.

[Daniel Bleichenbacher]

The test is there to detect weak key generation.

The test itself is probabilistic, meaning that there is a chance that it may generate false positives.

Generally, if a test is probabilistic then I'm choosing the parameters so that  the probability for false positives is 

not bigger than 2^{-32}, so that false positives even in continuous test builds are unlikely and test failures

are therefore investigated.

NIST generally assumes that both p and the order q of the generator g are known.

q is necessary to check if an ephemeral key is a valid element in the group generated by g.

If the validity of an ephemeral key is check, i.e. if the receiver checks that the ephemeral key

has order q, then it would be sufficient to choose the secret key in the range 1 .. q-1.

I.e. in this case it is possible to use a 256-bit q for a 2048-bit p and a 256-bit secret key x.

DH on the receiver side would require two exponentiations (one for the shared secret and one

to validate the ephemeral key).

However, the class DHParameterSpec does not specify a parameter q. As a consequence

the group membership of the ephemeral key cannot be checked in the general case.

No JCA provider I've looked at makes any attempt at validating the order of an ephemeral

key. (They can't be blamed for this, they don't have enough information).

Hence one has to be concerned about subgroup confinement attacks.

Generating a secret key in the range 1 .. q - 1 only, without key validation would

almost certainly be insufficient.

Choosing the secret key in the range 1..p-1 is one possibility. E.g. BouncyCastle is doing this.

OpenJdk is generating secret keys half of the size of p. This would be exploitable if the

attacker can choose the DH parameters. Otherwise the situation is unclear.

Until there is an attack exploiting the key generation in OpenJdk the test simply checks

that the key generation does not become worse.

--
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/9c0aaa4a-734e-4074-92f4-a0f9c3a6e830%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[calvin...@rsa.com]

Thanks for the detailed response.

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.