On Tuesday 26 May 2015 13:43:13 Daniel Kahn Gillmor wrote:
> On Tue 2015-05-26 12:57:05 -0400, Hubert Kario wrote:
> > creating composites that will pass even 100000 rounds of Miller-Rabin is
> > relatively simple....
> > (assuming the values for M-R tests are picked randomly)
>
> Can you point me to the algorithms for doing that?
OEIS A014233
> This would suggest
> that we really do want primality proofs (and a good way to verify them).
yes, using ECPP and distributing proof with the prime (or just placing it on
the project website) is a reasonable minimum, that still leaves out the
possibility of a backdoor if the initial seed value is random
> Do those algorithms hold for creating composites that pass M-R tests for
> both p and (p-1)/2 ?
that I don't know, I'd assume it's much harder, that being said, the A014233
is suspiciously short...
> > I'd be against shipping any primes that are not generated from known,
> > expected values, like hash of "OpenSSH 1024 bit DH prime, try #1"
>
> This is trying to put some sort of NUMS-y ("Nothing Up My Sleeve")
> constraint on prime generation
yes
> -- presumably you'd count up from the
> hash value until you find something that passes M-R for both p and
> (p-1)/2, right?
yes, use it as the base for the PRNG to get candidates
> I observe that the values in ./moduli all seem quite
> similar in that respect (i.e. the values for any given length share most
> of the same prefix, and differ only in the trailing bits).
>
> Wouldn't primality proofs make this NUMS-y approach less relevant?
yes, it would basically exclude the chance that the primes are backdoored,
there's still the chance for the values to be composites
for values to be used on this many machines, I'd say we should have primality
proofs, not just M-R "guess"
--
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 RepublicAttachment:
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
