[Cryptography] Other obvious issues being ignored?

[Joshua Hill]

On Mon, Oct 19, 2015 at 01:10:30PM +0000, Thierry Moreau wrote:
> The recent realization that public key cryptosystems having common 
> parameters (DH) may be vulnerable from the very fact that they rely on 
> common parameters is puzzling to me.

These aren't unknown; if you read through papers that present the
sieving-based discrete log algorithms, this sort of thing is commonly
parenthetically mentioned. The "Imperfect forward security" paper did us
the service of putting tab A in to slot B, and then actually highlighting
reach of the result.

I'd suggest (after going through the painful exercise of chasing down
the specifics of exactly which DH parameters were in common use about a
year ago) that it's a case of the people who know about these algorithm
characteristics not really being that interested in the (often poorly
documented or completely un-documented) implementation details, and
those doing the implementation not knowing.

To help with this, I suggest the following: if you implement a system
that uses cryptographic constants, document what constants you use,
how you arrived at these constants, and why you decided to use them.

> What other "obvious" questions are we ignoring?

I realize that this is intended as a rhetorical question, but I'll
mention one thing that falls into the same category.

If you know the factorization of the order of the group, you can apply
Pohlig-Hellman to decompose the discrete log problem on a large group
into several discrete log problems on (perhaps much!) smaller groups. This
was traditionally coupled with the Pollard-rho algorithm or brute force,
but in cases where more modern discrete log algorithms work, you can
just as well use these more advanced algorithms to solve the subproblems.

This is a non-issue for almost all of the IKE groups, because they
are mostly "safe primes" (all but the RFC5114 groups). In the "safe
prime" case, (p-1)/2 = q is prime, and for the IKE groups, the provided
generators produce this q-order subgroup.

It's more of an issue for the various FIPS 186 complying systems; in this
construction, one creates parameters so that the generator produces a
large subgroup of order q (which is too large for brute force guessing,
*but not too large to easily perform discrete logs in*). One is then
left with a substantial leftover cofactor, which _probably_ shouldn't
be too smooth (but this value isn't controlled).

In the large-key-generated-correctly case this shouldn't generally matter,
because smooth numbers are rare.

For the 1024 bit key case, this leads to a nominally attackable system,
because a 1024 bit discrete log can then be solved by factoring the 863-
bit cofactor, and then performing a DL in the q-order group (160 bits for
this key size) and then for whatever the factorization of the co-factor
ends up being.

Even without factoring, the end cost is effectively the same as performing
a DL computation on the 863-bit cofactor, not the full 1024 bit group.
In the case of very bad luck, or where the parameters were generated
by a hostile party (who may have assembled to the group so that the
cofactor was smooth), this could reduce the cost of the full discrete
log to discrete log on very small groups.

Interestingly, if the attacker can specify the group parameters, then
they can make the co-factor factorization:
  1) known to the attacker
  2) hard for others to compute
  3) smooth enough so that the attacker can solve discrete logs with
     only modest effort.

As a result, one should make sure to actually verify the reasonableness
of any group parameters provided to you (e.g, Appendix A of FIPS 186-4
suggests how one should generate group parameters so that these parameters
can later be independently verified).

As a consequence of this problem, I wouldn't suggest using the RFC 5114
parameters unless the RFC authors release the generation method used,
including all the seed data.

Best regards,
Josh