Subject: [Cfrg] Unknown order DH groups, e.g. as in RFC3526.

From: Andrey Jivsov <[email-masked]>
Date: Fri, 8 Mar 2019 14:43:38 -0800

Greetings.

A quick question on DH primes.

The IKE DH groups document didn't specify the group order
https://tools.ietf.org/html/rfc3526 .

This is in contrast to https://tools.ietf.org/html/rfc3526 that uses safe
primes.

Is my understanding correct that, as a general rule, these primes should
not be used, e.g. where a contributory behaviour of DH is needed? The issue
here is that a random element, received from a peer, can be in any
subgroup, possibly in a subroup with lower security than 128 bits, and
there is no way to verify this efficiently.

Thank you.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 8 Mar 2019 22:59:42 +0000

I suspect you mistyped the RFC number you meant; instead of saying that the groups listed in RFC3526 didn’t specify an order (they do), you meant to talk about the groups in some other RFC…

From: Cfrg <[email-masked]> On Behalf Of Andrey Jivsov
Sent: Friday, March 08, 2019 5:44 PM
To: [email-masked]
Subject: [Cfrg] Unknown order DH groups, e.g. as in RFC3526.

Greetings.

The IKE DH groups document didn't specify the group order https://tools.ietf.org/html/rfc3526 .

This is in contrast to https://tools.ietf.org/html/rfc3526 that uses safe primes.

Is my understanding correct that, as a general rule, these primes should not be used, e.g. where a contributory behaviour of DH is needed? The issue here is that a random element, received from a peer, can be in any subgroup, possibly in a subroup with lower security than 128 bits, and there is no way to verify this efficiently.

Thank you.

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 8 Mar 2019 15:16:32 -0800

Sorry, a correction: https://tools.ietf.org/html/rfc7919 is the RFC that
defines safe primes, and thus the group order is (p-1)/2 for each of them.

What's the group order for random primes in
https://tools.ietf.org/html/rfc3526 ? Do you mean the composite group order
p-1 with potentially unpleasant many-small-factors factorization?

On Fri, Mar 8, 2019 at 2:59 PM Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

> I suspect you mistyped the RFC number you meant; instead of saying that
> the groups listed in RFC3526 didn’t specify an order (they do), you meant
> to talk about the groups in some other RFC…
>
>
>
> *From:* Cfrg <[email-masked]> *On Behalf Of * Andrey Jivsov
> *Sent:* Friday, March 08, 2019 5:44 PM
> *To:* [email-masked]
> *Subject:* [Cfrg] Unknown order DH groups, e.g. as in RFC3526.
>
>
>
> Greetings.
>
>
>

---

From: Markku-Juhani Olavi Saarinen <[email-masked]>
Date: Fri, 8 Mar 2019 23:30:34 +0000

Hi Andrey,

It is true that RFC 3526 does not explicitly give out the group orders
-- these are safe primes. I recall when my late colleague at SSH, Mika
Kojo computed (or "found") them some 20 years ago -- they were
published posthumously and that's probably why such mathematical
details are missing. You can run a primality test of your choosing on
each (p-1)/2 to verify this if you like.

All of this, including Diffie-Hellman in a basically any group, is of
course of historical interest only.. but let me expand on this for
posteriority:

It is (or at least used to be) "common knowledge" that the MODP groups
(including RFC3526) were based on Sophie Germain primes, i.e. primes
of type p=2q+1 where q is also a prime. Therefore the group order of
any element x that is coprime with p can only be one of {1, 2, q,
2*q}. The latter two classes correspond to quadratic residues and
quadratic non-residues. There are O(log a log b) algorithms for
Legendre/Jacobi symbol so the group order of any element can be
efficiently evaluated if you accept that p is a "S.G." prime. In most
cases it is sufficient to check that x mod p is not one of { 0, 1, p-1
}, meaning that the group order is at least q -- the quadratic residue
check will only reveal the least significant bit of a secret exponent
-- if the generator happens to be a q.n.r.

Cheers,
- markku

Dr. Markku-Juhani O. Saarinen <[email-masked]>

On Fri, Mar 8, 2019 at 11:17 PM Andrey Jivsov <[email-masked]> wrote:
>
> Sorry, a correction: https://tools.ietf.org/html/rfc7919 is the RFC that defines safe primes, and thus the group order is (p-1)/2 for each of them.
>
> What's the group order for random primes in https://tools.ietf.org/html/rfc3526 ? Do you mean the composite group order p-1 with potentially unpleasant many-small-factors factorization?
>
> On Fri, Mar 8, 2019 at 2:59 PM Scott Fluhrer (sfluhrer) <sfluhrer@cisco..com> wrote:
>>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Markku-Juhani Olavi Saarinen <[email-masked]>
Date: Fri, 8 Mar 2019 23:48:21 +0000

Hi,

Further note: The primes of RFC 3526 were generated to match the
criteria given in Appendix E of RFC 2412 - those earlier computations
were performed by Richard Schroeppel for OAKLEY, a predecessor of IKE.
Mika Kojo just used the same "cookbook formula" to determnistically
search for larger primes. If you applied the same rules, you should be
able to find the same primes. The primes in RFC 2412 and RFC 3526 are
based on binary digits of Pi, while primes RFC 7919 seem to be based
on natural exponent e.

Cheers,
- markku