Q: DH Parameter Generation and Confinement Attacks
Jeffrey Walton
Current standardized DH parameters are {p, q, g} [1], where p and g
are the classical prime and generator. The generator generates a prime-
order subgroup of size q. q offers assurances (or a quantitative
security level) against confinement attacks.
If a cryptographic library generates DH parameters {p, g} using a
secure PRNG, how can one be assured that "weak" parameters are not
returned to the caller. That is, how can I tell that {p, g} does not
suffer from a small subgroup or confinement?
I am less concerned about an adversary manipulating and injecting
messages in the secure channel during the conversation. I am *most*
concerned that the adversary can capture the key exchange and
messages, and then later (for example, after 4 days of computation),
recover the plain text of the messages (or one party's side of the
conversation). Of course, the latter presumes the parameters have a
small subgroup order.
To summarize:
(1) Is it acceptable for a library to only provide {p, g}?
Or should I insist on {p, q, g} so I can ensure the
DH parameters meet security levels?
(2) Are confinement attacks limited to MITM?
(3) How do I calculate 'q' given 'p' and 'g'?
Jeff
[1] Additional Diffie-Hellman Groups for Use with IETF Standards,
http://tools.ietf.org/html/rfc5114
Ertugrul Söylemez
> Current standardized DH parameters are {p, q, g} [1], where p and g
> are the classical prime and generator. The generator generates a
> prime- order subgroup of size q. q offers assurances (or a
> quantitative security level) against confinement attacks.
>
> If a cryptographic library generates DH parameters {p, g} using a
> secure PRNG, how can one be assured that "weak" parameters are not
> returned to the caller. That is, how can I tell that {p, g} does not
> suffer from a small subgroup or confinement?
>
> I am less concerned about an adversary manipulating and injecting
> messages in the secure channel during the conversation. I am *most*
> concerned that the adversary can capture the key exchange and
> messages, and then later (for example, after 4 days of computation),
> recover the plain text of the messages (or one party's side of the
> conversation). Of course, the latter presumes the parameters have a
> small subgroup order.
>
> To summarize:
> (1) Is it acceptable for a library to only provide {p, g}? Or should
> I insist on {p, q, g} so I can ensure the DH parameters meet
> security levels?
It is acceptable, because you can easily verify whether the parameters
are good or not. See below.
> (2) Are confinement attacks limited to MITM?
With a confinement attack the attacker gains information offline. This
is different from an MITM attack, which is an online attack.
> (3) How do I calculate 'q' given 'p' and 'g'?
Make sure that p = 2*q + 1 and q is prime. The 'g' parameter is a small
number like 2 or 3. This ensures that it either is a primitive root
generating the entire group of size 2*q or it generates a subgroup of
size q. See the Pohlig-Hellman attack for more information.
Greets,
Ertugrul
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
Jeffrey Walton
Thanks Ertugrul. The scenario I described can simple be attributed to
bad luck, and I wanted a way to est for the un-luckiness.
Jeff
Greg Rose
Jeffrey Walton <nolo...@gmail.com> wrote:
>On Nov 25, 11:37 pm, Ertugrul Söylemez <e...@ertes.de> wrote:
>> Jeffrey Walton <noloa...@gmail.com> wrote:
>> > Current standardized DH parameters are {p, q, g} [1], where p and g
>> > are the classical prime and generator. The generator generates a
>> > prime- order subgroup of size q. q offers assurances (or a
>> > quantitative security level) against confinement attacks.
>>
>> > If a cryptographic library generates DH parameters {p, g} using a
>> > secure PRNG, how can one be assured that "weak" parameters are not
>> > returned to the caller. That is, how can I tell that {p, g} does not
>> > suffer from a small subgroup or confinement?
>>
>> > I am less concerned about an adversary manipulating and injecting
>> > messages in the secure channel during the conversation. I am *most*
>> > concerned that the adversary can capture the key exchange and
>> > messages, and then later (for example, after 4 days of computation),
>> > recover the plain text of the messages (or one party's side of the
>> > conversation). Of course, the latter presumes the parameters have a
>> > small subgroup order.
>>
>> > To summarize:
>> > (1) Is it acceptable for a library to only provide {p, g}? Or should
>> > I insist on {p, q, g} so I can ensure the DH parameters meet
>> > security levels?
>>
>> It is acceptable, because you can easily verify whether the parameters
>> are good or not. See below.
I think what you are saying is that, if q is not
specified, it should be because q = (p-1)/2 should
be prime.
>>
>> > (2) Are confinement attacks limited to MITM?
>>
>> With a confinement attack the attacker gains information offline. This
>> is different from an MITM attack, which is an online attack.
>>
>> > (3) How do I calculate 'q' given 'p' and 'g'?
>>
>> Make sure that p = 2*q + 1 and q is prime. The 'g' parameter is a small
>> number like 2 or 3. This ensures that it either is a primitive root
>> generating the entire group of size 2*q or it generates a subgroup of
>> size q. See the Pohlig-Hellman attack for more information.
Here I disagree. You want g to be a generator of
the subgroup of order q, whether or not q is
(p-1)/2 or just some 160- or 256-bit prime. In the
former case, a generator for the whole group
reveals one bit of information about the secret
exponent (whether it was odd or even) by testing
the public key to see whether it had order q or
not. In the later case, you open up the possibility
of small subgroup attacks.
For the parameters, check that p and q are both
prime, and that g has order q (you check this by
verifying that g^(q-1) == 1 mod P).
When doing a D-H agreement, check that the
received value is in the order-q subgroup (same
way as above, but including the check that it's
not 1!).
To get a g that is in the order q subgroup, just
choose a random element, and raise it to the power
(p-1)/q. Now, if it isn't 1, it is what you want.
In the case that q=(p-1)/2, 4 will always be a
generator of the subgroup... but maybe you want to
just check whether 2 or 3 are also generators
first.
Greg.
--
Mark Wooding
> For the parameters, check that p and q are both prime, and that g has
> order q (you check this by verifying that g^(q-1) == 1 mod P).
I think you mean: check that g^q == q (mod p).
-- [mdw]
Greg Rose
Same thing, but with one less multiplication in my
case, nu?
Greg.
--
Mark Wooding
D'oh! My idiotic typo. I think you mean g^q == 1 (mod p).
-- [mdw]
Peter Gutmann
>If a cryptographic library generates DH parameters {p, g} using a
>secure PRNG, how can one be assured that "weak" parameters are not
>returned to the caller. That is, how can I tell that {p, g} does not
>suffer from a small subgroup or confinement?
Alongside the other advice that's already been provided, you may want to look
at DSA keygen requirements. DSA uses the same public parameters as DH, and is
much more rigorously specified in terms of the checks that you need to apply.
Peter.
Jeffrey Walton
Thanks Doctor. I'm not sure why I did not make the leap myself.......
Jeff
Jeffrey Walton
> g...@nope.ucsd.edu (Greg Rose) writes:
> > Mark Wooding <m...@distorted.org.uk> wrote:
> > >g...@nope.ucsd.edu (Greg Rose) writes:
>
> > >> For the parameters, check that p and q are both prime, and that g has
> > >> order q (you check this by verifying that g^(q-1) == 1 mod P).
>
> > >I think you mean: check that g^q == q (mod p).
>
> > Same thing, but with one less multiplication in my
> > case, nu?
>
> D'oh! My idiotic typo. I think you mean g^q == 1 (mod p).
>
> -- [mdw]
Thanks Mark and Greg. I suspect this is precisely what I need.
Jeff
Jeffrey Walton
> Hi All,
>
> [SNIP]
>
> To summarize:
> (1) Is it acceptable for a library to only provide {p, g}?
> Or should I insist on {p, q, g} so I can ensure the
> DH parameters meet security levels?
> (2) Are confinement attacks limited to MITM?
> (3) How do I calculate 'q' given 'p' and 'g'?
Efficient Primes for Discrete Log Cryptosystems'.
Greg Rose
Mark Wooding <m...@distorted.org.uk> wrote:
>g...@nope.ucsd.edu (Greg Rose) writes:
>
>> In article <8762vjyhq...@metalzone.distorted.org.uk>,
>> Mark Wooding <m...@distorted.org.uk> wrote:
>> >g...@nope.ucsd.edu (Greg Rose) writes:
>> >
>> >> For the parameters, check that p and q are both prime, and that g has
>> >> order q (you check this by verifying that g^(q-1) == 1 mod P).
>> >
>> >I think you mean: check that g^q == q (mod p).
>>
>> Same thing, but with one less multiplication in my
>> case, nu?
>
>D'oh! My idiotic typo. I think you mean g^q == 1 (mod p).
Yes, of course you're right. I was thinking of
Fermat's little theorem, and confusing myself.
thanks,
Greg.
--
Scott Contini
There is an assumption here that if p = (2q + 1)
where q is prime, then there are no attacks faster
than general number field sieve, assuming DH is properly
implemented. But is this assumption justified? For
example, how do you know that the parameters were not
generated with some trapdoor information that makes it
vulnerable to say a special number field sieve attack?
i.e. if there is some very sparse low degree polynomial
f(x) such that f(m) = p for some integer m , then
your p is in fact much weaker than correctly generated
values of p of the same size.
More generally, one can ask how can one prove that the
parameters were generated in a way that a trapdoor
could not have been put into them (regardless of the
type of attack)?
The original poster assumed that a secure prng was
used in the generation, but did not say how it was used.
I don't think it is too difficult to come up with a
software package that uses a secure prng to generate
parameters that are weaker than they appear.
My memory is very bad, but I seem to think that Certicom
has come up with algorithms for generating parameters
that are verifiably random. That is, they were generated
in such a way that a trapdoor could not have been put in,
assuming something or other... ?
Scott
Kristian Gj�steen
>My memory is very bad, but I seem to think that Certicom
>has come up with algorithms for generating parameters
>that are verifiably random. That is, they were generated
>in such a way that a trapdoor could not have been put in,
>assuming something or other... ?
A reasonable approach is to use pseudo-randomness when generating primes,
and publish the (random) seed of the generator. For most reasonable
generators, this would make it very hard to insert trapdoors into the
parameters.
--
kg
Greg Rose
FIPS ummm... 186-2 has a procedure for this too.
Basically, take a seed and hash it with SHA-1.
Iterate checking primality and incrementing until
you get a prime... call that q. Then generate
other hashes (as a source of randomness) and
multiply by q and add 1, and check again for
primality. Iterate until it's prime, call it p.
Publishing the seed gives you proof that the
parameters weren't cooked.
I have code that will do it, which I will make
available if there is enough interest. (I have to
jump through export control/legal hoops these
days, so I won't do it unless people care. It uses
libtomcrypt.)
Greg.
--
Mark Wooding
> FIPS ummm... 186-2 has a procedure for this too. Basically, take a
> seed and hash it with SHA-1.
[...]
For extra joy, FIPS 186--3 has a slightly different procedure, which
uses SHA-256 and friends -- but lets you generate keys with larger
subgroups, so there is a point.
> I have code that will do it, which I will make available if there is
> enough interest. (I have to jump through export control/legal hoops
> these days, so I won't do it unless people care. It uses libtomcrypt.)
I also have code which will do the FIPS 186--2 version of the procedure.
(My crypto library is a bit behind the times nowadays; it's awaiting
some shiny new toys I need for a major overhaul, and they're waiting on
something else, so don't expect the --3 version for a while.)
-- [mdw]