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

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

Dr. Markku-Juhani O. Saarinen <mjos@iki.fi>

On Fri, Mar 8, 2019 at 11:30 PM Markku-Juhani Olavi Saarinen
<mjos@iki.fi> wrote:
>
> 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 <mjos@iki.fi>
>
> On Fri, Mar 8, 2019 at 11:17 PM Andrey Jivsov <crypto@brainhub.org> 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:
> >>
> >> 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 <cfrg-bounces@irtf.org> On Behalf Of Andrey Jivsov
> >> Sent: Friday, March 08, 2019 5:44 PM
> >> To: cfrg@irtf.org
> >> Subject: [Cfrg] Unknown order DH groups, e.g. as in RFC3526.
> >>
> >>
> >>
> >> 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.
> >
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg