On Mon, Jun 15, 2015 at 12:09:19AM -0700, Mark D. Baushke wrote: > Daniel Kahn Gillmor <dkg@xxxxxxxxxxxxxxxxx> writes: > > > > From: "Roginsky, Allen" <allen.roginsky@xxxxxxxx> 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@xxxxxxxxxxx] 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@xxxxxxxx> To: Mark Baushke <mdb@xxxxxxxxxxx> 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
Attachment:
pgpAGHmPPN66F.pgp
Description: PGP signature
_______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
