On Wed 2015-05-27 05:23:41 -0400, Hubert Kario wrote:> On Tuesday 26 May 2015 15:10:01 Daniel Kahn Gillmor wrote: >> On Tue 2015-05-26 14:02:07 -0400, Hubert Kario wrote: >> > OEIS A014233 >> >> Hm, this is a sequence, but not an algorithm. It looks to me like it is >> not exhaustive, just a list of those integers which are known to have >> the stated property ("Smallest odd number for which Miller-Rabin >> primality test on bases <= n-th prime does not reveal compositeness"). >> >> Taking the final integer in that sequence (a(11)) fails even the default >> >> 25-round M-R test in gmp: >> >>> k = gmpy2.mpz(3825123056546413051) >> >>> gmpy2.is_prime(k) >> >> False > > I'm quite sure that this means that gmpy doesn't use pure M-R with randomly > selected witnesses.https://gmplib.org/manual/Prime-Testing-Algorithm.html#Prime-Testing-Algorithm suggests is chooses a random base, but it also runs some non-M-R tests before executing M-R: http://sources.debian.net/src/gmp/2:6.0.0%2Bdfsg-6/mpz/pprime_p.c/ GMP's M-R tests are using randomly selected witnesses, though: http://sources.debian.net/src/gmp/2:6.0.0%2Bdfsg-6/mpz/millerrabin.c/#L92> Hmm, I have a distinct recollection of reading of a possibility of a > small subgroup attacks on primes (as in very few primes have this > property, so randomly selected one are almost certainly not > problematic, but if you can pick any prime, you can find them) > > Maybe what they mean is that this may does not apply to Sophie Germain > primes, but to "DSA style" primes, I haven't dug too deep into > this. Creating it pseudo-randomly from nothing up my sleeve numbers > fixes this issue anyway.I think you mean "safe primes" where you say "Sophie Germain primes" -- if q = (p-1)/2, and p and q are primes, then p is a "safe prime" and q is a "Sophie Germain prime". Small subgroup attacks are not possible for safe primes as long as you test your peer's public share and the generator to ensure that they are in the range (exclusive) 1 < x < p-1. This is because totient(p) = p-1 (because p is prime), and p-1 has only two factors: 2 and q. So there exists one small subgroup, but it's of order 2, and its generator is p-1 (the subgroup cycles between p-1 and 1). All other elements are generators of order either q or p-1. There are no other subgroups, iiuc. If this is the only attack you're trying to address, and you've already limited yourself to safe primes, then NUMS properties don't really add anything. The NUMS approach is there are to try to avoid the possibility of other, unknown cryptanalytic attacks against some infrequent type of group, so that the entity who defines the group can't force you into this secret corner case if they have special knowledge. --dkg
On Wednesday 27 May 2015 13:11:43 Daniel Kahn Gillmor wrote:> On Wed 2015-05-27 05:23:41 -0400, Hubert Kario wrote: > > Hmm, I have a distinct recollection of reading of a possibility of a > > small subgroup attacks on primes (as in very few primes have this > > property, so randomly selected one are almost certainly not > > problematic, but if you can pick any prime, you can find them) > > > > Maybe what they mean is that this may does not apply to Sophie Germain > > primes, but to "DSA style" primes, I haven't dug too deep into > > this. Creating it pseudo-randomly from nothing up my sleeve numbers > > fixes this issue anyway. > > I think you mean "safe primes" where you say "Sophie Germain primes" -- > if q = (p-1)/2, and p and q are primes, then p is a "safe prime" and q > is a "Sophie Germain prime".yes, I used it as a synonym for "safe prime"> Small subgroup attacks are not possible for safe primes as long as you > test your peer's public share and the generator to ensure that they are > in the range (exclusive) 1 < x < p-1. > > This is because totient(p) = p-1 (because p is prime), and p-1 has only > two factors: 2 and q. So there exists one small subgroup, but it's of > order 2, and its generator is p-1 (the subgroup cycles between p-1 and > 1). All other elements are generators of order either q or p-1. There > are no other subgroups, iiuc.yes, this does sound right> If this is the only attack you're trying to address, and you've already > limited yourself to safe primes, then NUMS properties don't really add > anything. The NUMS approach is there are to try to avoid the > possibility of other, unknown cryptanalytic attacks against some > infrequent type of group, so that the entity who defines the group can't > force you into this secret corner case if they have special knowledge.that being said, how using NUMS seeds to generate safe prime would hurt? also, doesn't that require us to provide primality certificates for q rather than p? -- Regards, Hubert Kario Quality Engineer, QE BaseOS Security team Web: www.cz.redhat.com Red Hat Czech s.r.o., Purky?ova 99/71, 612 45, Brno, Czech Republic -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 819 bytes Desc: This is a digitally signed message part. URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150528/7fbcffd2/attachment-0001.bin>
On Thu 2015-05-28 10:54:21 -0400, Hubert Kario wrote:> that being said, how using NUMS seeds to generate safe prime would hurt?I don't see how it would hurt, but i'm just pointing out that i don't think it provides any additional defense against small subgroup attacks once you've settled on requiring safe primes. Of course, if you use some sort of NUMS process then you have to verify that the NUMS process was followed as well, which adds an additional chunk of work for anyone who is trying to do corroboration.> also, doesn't that require us to provide primality certificates for q rather > than p?Yes, if we expect to use safe primes, i think we need primality proofs for both p and q. For the new TLS FFDHE groups, i've posted those here: https://dkg.fifthhorseman.net/ffdhe-primality-proofs/ (i'm not recommending using the same groups for TLS and SSH, fwiw. splitting the potential attack surface by application type seems like a good thing; it adds no additional fingerprinting/metadata, because the protocols themselves are already fingerprintable) I guess i'd summarize the situation as: * NUMS requires extra work for both people who choose the moduli, and for corroborators (moduli.c's gen_candidates starts from BN_rand on line 328, so we're not even claiming to use NUMS in the current method) * primality proofs require a significant amount of extra work for people who choose the moduli, and some extra work for corroborators (verification at least) * even basic random M-R checks (which wouldn't defend against an attacker who knows how to generate strong pseudoprimes) require work from corroborators * we haven't had much public corroboration of the moduli shipped by default in the past (or if we have, i've missed it) * it's not fair to Darren and Damien that they should be single points of failure here. Any thoughts on things that we might be able to improve? --dkg
On Thu, 28 May 2015, Hubert Kario wrote:> > If this is the only attack you're trying to address, and you've > > already limited yourself to safe primes, then NUMS properties don't > > really add anything. The NUMS approach is there are to try to avoid > > the possibility of other, unknown cryptanalytic attacks against some > > infrequent type of group, so that the entity who defines the group > > can't force you into this secret corner case if they have special > > knowledge. > > that being said, how using NUMS seeds to generate safe prime would > hurt?If you're concerned about precomputation, then it effectively gives the attackers a list of what you're going to use in the future.> also, doesn't that require us to provide primality certificates for q > rather than p?IMO you'd want both to prove a safe prime -d