openssh unix dev - Jun 2015 - [Bug 2302] with DH-GEX, ssh (and sshd) should not fall back to unconfigured DH groups or at least document this behaviour and use a stronger group

On Fri 2015-06-12 01:52:54 -0400, Mark D. Baushke wrote:
> I have communicated with Allen Roginsky on this topic and I have been given
permission to post his response.
>
> In this message below, the 'vendor' was Darren Tucker's
generated prime
> that used a generator value of 5.
>
> 	-- Mark
>
> From: "Roginsky, Allen" <allen.roginsky at nist.gov>
> Subject: RE: Question on SP 800-56A rev2
>
> The reason the y^q=1 (mod p) tests exists is to verify that y is in the
> required subgroup.
I think this answer "begs the question" -- yes, the mathematical test
verifies that y generates a subgroup of size q.  But the question we
were discussing is why does the subgroup need to be of size q instead of
size p-1?  

     --dkg

Daniel Kahn Gillmor <dkg at fifthhorseman.net> writes:
> > From: "Roginsky, Allen" <allen.roginsky at nist.gov>
> > Subject: RE: Question on SP 800-56A rev2
> >
> > The reason the y^q=1 (mod p) tests exists is to verify that y is in
the
> > required subgroup.
> 
> I think this answer "begs the question" -- yes, the mathematical
test
> verifies that y generates a subgroup of size q.  But the question we
> were discussing is why does the subgroup need to be of size q instead of
> size p-1?  
I forwarded your post to Allen Raginsky with this note:
> > From: Mark Baushke [mailto:mdb at juniper.net]
> > Sent: Friday, June 12, 2015 10:23 PM
> > To: Roginsky, Allen
> > Subject: Fwd: [Bug 2302] with DH-GEX, ssh (and sshd) should not fall
back to unconfigured DH groups or at least document this behaviour and use a
stronger group
> > 
> > Hi Allen,
> > 
> > It seems that there is a followup question to your statements?
> > 
> > It really is sort of the root question, whey does anyone actually
> > care if we have a q-ordered subgroup or not? Is there an attack
> > which is not published on this kind of issue?
> > 
> > -- Mark
I have received this reply from Allen...

	-- Mark

 ------- forwarded message -------
From: "Roginsky, Allen" <allen.roginsky at nist.gov>
To: Mark Baushke <mdb at juniper.net>
Subject: RE: [Bug 2302] with DH-GEX, ssh (and sshd) should not fall back to
 unconfigured DH groups or at least document this behaviour and use a stronger
 group
Date: Mon, 15 Jun 2015 06:17:55 +0000

Hi Mark,

The private key x may be placed in the smaller subgroup ? of size q ? precisely
because there are no known attacks against the DH method that could exploit the
structure of this subgroup.  The public key must be in a larger group because
there are attacks exploiting the structure of the DH public key (the attacks
against the discreet logarithm problem in the multiplicative group of a finite
field).

Regards,
Allen

 ------- end of forwarded message -------

On Mon, Jun 15, 2015 at 12:09:19AM -0700, Mark D. Baushke
wrote:
> Daniel Kahn Gillmor <dkg at fifthhorseman.net> writes:
> 
> > > From: "Roginsky, Allen" <allen.roginsky at
nist.gov> Subject: RE:
> > > Question on SP 800-56A rev2
> > >
> > > The reason the y^q=1 (mod p) tests exists is to verify that y is
> > > in the required subgroup.
> > 
> > I think this answer "begs the question" -- yes, the
mathematical
> > test verifies that y generates a subgroup of size q.  But the
> > question we were discussing is why does the subgroup need to be of
> > size q instead of size p-1?  
> 
> I forwarded your post to Allen Raginsky with this note:
> 
> > > From: Mark Baushke [mailto:mdb at juniper.net] Sent: Friday, June
12,
> > > 2015 10:23 PM To: Roginsky, Allen Subject: Fwd: [Bug 2302] with
> > > DH-GEX, ssh (and sshd) should not fall back to unconfigured DH
> > > groups or at least document this behaviour and use a stronger
> > > group
> > > 
> > > Hi Allen,
> > > 
> > > It seems that there is a followup question to your statements?
> > > 
> > > It really is sort of the root question, whey does anyone actually
> > > care if we have a q-ordered subgroup or not? Is there an attack
> > > which is not published on this kind of issue?
> > > 
> > > -- Mark
> 
> I have received this reply from Allen...
> 
> 	-- Mark
> 
>  ------- forwarded message ------- From: "Roginsky, Allen"
>  <allen.roginsky at nist.gov> To: Mark Baushke <mdb at
juniper.net> Subject:
>  RE: [Bug 2302] with DH-GEX, ssh (and sshd) should not fall back to
>  unconfigured DH groups or at least document this behaviour and use a
>  stronger group Date: Mon, 15 Jun 2015 06:17:55 +0000
> 
> Hi Mark,
> 
> The private key x may be placed in the smaller subgroup ? of size q ?
> precisely because there are no known attacks against the DH method
> that could exploit the structure of this subgroup.  The public key
> must be in a larger group because there are attacks exploiting the
> structure of the DH public key (the attacks against the discreet
> logarithm problem in the multiplicative group of a finite field).
> 
> Regards, Allen
> 
>  ------- end of forwarded message -------
Hi Mark.

Thanks for following up on this important and interesting issue and for
serving as interlocutor with the good folks at NIST.

Regarding Allen's last comment, I believe what he means is there doesn't
appear to be a way to apply the methods of the index-calculus directly
to the q-subgroup. In these subgroups, the state of the art algorithms
have much lower O(n^(1/2)) runtimes.

This is probably why NIST feels comfortable with the low q
bit-requirements compared to the p bit-requirements in SP-800-56:

   p    q
1024  160
2048  224
2048  256

In OpenSSH's case, where p=2q+1 by construction, the bit profiles are:

   p     q
1024  1023
2048  2047
4096  4095

In this latter situation, an attacker would choose to compute discrete
logs in (Z/pZ)* even when the generator generates the subgroup order q.
Why? Because O(sqrt(2^||q||)) costs are so much much greater.

In other words, the decision to attack the subgroup directly or the full
group depends on the relative bit sizes of p & q. However, of note, when
the generator used generates the q-subgroup, one can always fall back to
computing the discrete log in the full group.

Finally, as I wrote in an earlier email, all else equal, one reason to
avoid the full group is the leakage of the Legendre symbol. This is
particularly bad for ElGamal where one leaks the Legendre symbol of the
cleartext. For example, imagine an e-voting system than encrypts "GOP"
and "DEM" such that their Legendre symbols differ. There, the leakage
would be catastrophic.

Feel free to forward my email to NIST for comments/review/corrections.

Best,

--mancha
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150615/a35ce95e/attachment-0001.bin>