Subject: Re: [Curdle] draft-ietf-curdle-ssh-modp-dh-sha2

From: Anna Johnston <[email-masked]>
Date: Fri, 31 Mar 2017 18:27:00 +0000

A ‘Backdoor’ in crypto is an attack which is hard to find.  It is trivial to test that an element is in a prime order subgroup.  In primes, backdoor’s generally refer to a prime vulnerable to the SpecialNumberFieldSieve.  Being ‘safe’ does not mean that the prime is not vulnerable to the SNFS, which is the back door of concern.  For example 2^{2048}-194228 is a safe prime, but is vulnerable to the SNFS – at least theoretically (SNFS is still not currently possible at 2048 bits, as it roughly reduces computation on the sieve by about ¼ the size – ex: 768 (IACR ePrint 2017/067) bit GNFS is about as expensive as a 1024 (IACR ePrint 2016/961 )).  

Using a subgroup of order 2q is not safe.  It can easily be manipulated to leak one bit per exponentiation.  The only safe subgroup is one that has a large prime order

On 3/31/17, 5:32 AM, "Hubert Kario" <[email-masked]> wrote:

    On Thursday, 30 March 2017 17:54:55 CEST Tero Kivinen wrote:
    > Anna Johnston writes:
    > > There isn’t that much to Pocklington’s theorem.  A decent write up
    > > of it is in Wikipedia.  As for your comments:
    > > 
    > > 1.  Proof of no backdoor:  Of course there is no proof that
    > > backdoors do not exist.  Show me such a proof for the fixed primes.
    > 
    > I know there is no backdoors on the primes I generated, as I did not
    > put backdoor there... :-)
    > 
    > Fixed primes uses Nothing up my sleeve numbers [1] just to try to
    > convince people that they cannot be backdoored.
    
    safe primes can't be backdoored too
    
    they have subgroups of size p-1, (p-1)/2, 2 and 1.
    Subgroups of size p-1 and (p-1)/2 are safe, subgroups of size 2 and 1 are 
    trivially detectable (just don't process values of p-1, 0 and 1).
    
    -- 
    Regards,
    Hubert Kario
    Senior 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

---

From: Hubert Kario <[email-masked]>
Date: Mon, 03 Apr 2017 12:49:06 +0200

On Friday, 31 March 2017 20:27:00 CEST Anna Johnston wrote:
> A ‘Backdoor’ in crypto is an attack which is hard to find.  It is trivial to
> test that an element is in a prime order subgroup.  In primes, backdoor’s
> generally refer to a prime vulnerable to the SpecialNumberFieldSieve. 
> Being ‘safe’ does not mean that the prime is not vulnerable to the SNFS,
> which is the back door of concern.  For example 2^{2048}-194228 is a safe
> prime, but is vulnerable to the SNFS

but for a published parameter, it's trivial to say if it is vulnerable to SNFS 
or not, isn't it?

> – at least theoretically (SNFS is
> still not currently possible at 2048 bits, as it roughly reduces
> computation on the sieve by about ¼ the size – ex: 768 (IACR ePrint
> 2017/067) bit GNFS is about as expensive as a 1024 (IACR ePrint 2016/961
> )).  

but if you operate on a non-safe prime, you can manipulate the group so that 
it's as easy as attacking a 512 bit, if not smaller, prime.
 
> Using a subgroup of order 2q is not safe.  It can easily be manipulated to
> leak one bit per exponentiation.  The only safe subgroup is one that has a
> large prime order

Interesting, any pointers on how it's done?

Also, wouldn't that be a problem only if your key share is static or your RNG 
was really crappy?

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 3 Apr 2017 17:26:22 +0300

> but for a published parameter, it's trivial to say if it is vulnerable to SNFS 

AFAIK, at least some "backdoored" DH primes were primes that are
secretly vulernable to SNFS, in a way that is quite hard to discover.

> Interesting, any pointers on how it's done?

AFAIK, using subgroup of order 2q leaks a bit, but it is always the LSB that
leaks, so one can't recover the scalar even from many outputs.

And one way to recover the LSB is to raise the public key to power of q
modulo p. If the LSB is clear, the result is 1, if the LSB is set, the
result is -1.

Then in some protocols, you absolutely have to use subgroup of order 2q,
because if you don't, you get absolutely fatal information leakage.

-Ilari

---

From: Hubert Kario <[email-masked]>
Date: Mon, 03 Apr 2017 19:10:57 +0200

On Monday, 3 April 2017 16:26:22 CEST Ilari Liusvaara wrote:
> > > A ‘Backdoor’ in crypto is an attack which is hard to find.  It is
> > > trivial to test that an element is in a prime order subgroup.  In
> > > primes, backdoor’s generally refer to a prime vulnerable to the
> > > SpecialNumberFieldSieve. Being ‘safe’ does not mean that the prime is
> > > not vulnerable to the SNFS, which is the back door of concern.  For
> > > example 2^{2048}-194228 is a safe prime, but is vulnerable to the SNFS
> > 
> > but for a published parameter, it's trivial to say if it is vulnerable to
> > SNFS or not, isn't it?
> 

Wikipedia[1] says that the algorithm is "very efficient" (I'm assuming it's 
the 25% reduction in effective key size) for numbers in form r^e +- s ($ r^{e}
\pm s $), only if r and s are "relatively small". What "relatively small" 
means in this context? Relatively small in relation to general numbers used in 
crypto, or in relation to number tested?

194228 is only 18bit long, iterating over all `r` up to, say, 2^20 and 
checking if the needed s is smaller than 2^64 shouldn't take more time than 
verifying primality certificates for a 2048 or 4096 bit safe prime anyway...

It also states that it is "efficient" (no idea if that means 20% or 5% 
reduction in effective key size) for number in form ar^e+-bs^f ($ ar^{e}\pm 
bs^{f} $) or ones with low Hamming weight. While Hamming weight is trivial to 
test, the more complex form is more problematic.

> modulo p. If the LSB is clear, the result is 1, if the LSB is set, the

that was my understanding too

 1 - Please excuse me, I'm not a cryptographer/mathematician, I just play one 
on TV.
-- 
Regards,
Hubert Kario
Senior 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

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 3 Apr 2017 20:30:02 +0300

> crypto, or in relation to number tested?

AFAIK, the problem is that those numbers (however "small" is defined)
aren't the only ones SNFS is efficient for: There are random-looking
numbers that turn out to be vulernable to SNFS, or worse, are vulernable
to SNFS if one knows some hidden piece of information.

-Ilari

---

From: Kyle Rose <[email-masked]>
Date: Mon, 3 Apr 2017 12:34:57 -0500

> to SNFS if one knows some hidden piece of information.

How likely are you to end up with one of those numbers (the
unintentionally-vulnerable to SNFS variety) if you choose a prime in a
nothing-up-my-sleeve manner?

Kyle

---

From: Hubert Kario <[email-masked]>
Date: Mon, 03 Apr 2017 20:03:03 +0200

On Monday, 3 April 2017 19:30:02 CEST Ilari Liusvaara wrote:
> > the 25% reduction in effective key size) for numbers in form r^e +- s ($
> > r^{e} \pm s $), only if r and s are "relatively small". What "relatively
> > small" means in this context? Relatively small in relation to general
> > numbers used in crypto, or in relation to number tested?
> 

But if I read the MathWorld correctly[1], the speedup for polynomials is 
marginal (from crypto PoV) compared to numbers of no special form...

Unless you mean something else by "hidden piece of information".

I mean, 25% margin on keysize is quite reasonable, so there is use in 
backdooring this way, but <5% margin on keysize is crazy small. So if we show 
that the prime does not lie near a large power, we gain a lot of trust in it. 

 1 - http://mathworld.wolfram.com/NumberFieldSieve.html
-- 
Regards,
Hubert Kario
Senior 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

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 3 Apr 2017 11:39:41 -0700

> nothing-up-my-sleeve manner?

I don't think we know how effective Nothing Up My Sleeve (NUMS)
techniques will be in the long run.

I do not know if transcendental numbers are more or less vulnerable than
plain irrational numbers as the basis for NUMS.

Now that we have selected pi (RFC 3526) which is shared by IKE and SSH,
or e (RFC 7919) for TLS, we can expect they will be the focus of
extensive precoputation efforts.

I guess I will hope that transcendental numbers are safe for NUMS.

For now, does everyone believe that adding 

    diffie-hellman-group14-sha256
    diffie-hellman-group15-sha512
    diffie-hellman-group16-sha512
    diffie-hellman-group17-sha512
    diffie-hellman-group18-sha512

is a good next step?

Or, are folks sufficiently concerned that should we generate another set
of NUMS MODP safe primes with 2048, 3072, 4096, 6144, 8192-bit modulus
values primarily for use with SSH?

I suppose we could select digits from some other irrational or
transcendental number...

	Thanks,
	-- Mark

---

From: Kyle Rose <[email-masked]>
Date: Mon, 3 Apr 2017 14:06:03 -0500

> techniques will be in the long run.

I guess what I'm asking is: do we have a sense for how common these numbers
are? As the point of NUMS is presumably to choose something short and
natural (i.e., without magic numbers) as a seed for a well-known random
prime number generation algorithm such that it's easy to convince the world
that the resulting prime doesn't have secret properties relative to the
target cryptosystem, it makes a difference to our confidence level whether
SNFS-susceptible 2048-bit primes are 1 in a thousand, 1 in ten billion, or
1 in 10^100 if we can't tell but others (e.g., state-level actors) can.

If they're 1 in 1000, then FFDH should probably just be considered broken
until we can definitely test for and rule out those primes, or rule out the
ability to find the unintentional weakness without first generating the
prime that way.

In the other cases, having multiple groups chosen in a NUMS manner in which
all but the first are held in reserve in case we got unlucky on the first
try (or in case other attacks appear for different subsets of primes) is
probably a prudent approach.

But getting back to this specific case: what is the provenance of the IKE
groups?

Kyle

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 3 Apr 2017 22:55:05 +0300

> Unless you mean something else by "hidden piece of information".

Might have been misremembering that it had something to do with
polynomials.

What I mean: Numbers that look random and one can't apply SNFS in any
obvious way, but knowing some hidden piece of information enables one
to get decent speedup from SNFS.

That was at least my understanding of some "backdoored DH primes"
stuff.

Obviously, generating numbers in NUMS fashion eliminates that
problem: The probability that anyone knows how to apply SNFS to
arbitrary number is vanishingly small.

-Ilari

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 3 Apr 2017 16:23:11 -0700

> But getting back to this specific case: what is the provenance of the IKE

The RFC 3526 DH MODP groups were provided by Tero Kivinen and Mika Kojo
based on pi. You may find Tero's respsonse <[email-masked]> about them
https://www.ietf.org/mail-archive/web/curdle/current/msg00808.html

Reference o the proofs of the primality of both RFC 3526 and RFC 7919
numbers may be found here:

  https://www.ietf.org/mail-archive/web/curdle/current/msg00790.html

which leads to URLs:

  https://kivinen.iki.fi/primes/
and
  https://www.ietf.org/mail-archive/web/tls/current/msg15716.html

For what it is worth, I also used Primo to verify the RFC 3526 prime p
and q values (q = (p-1)/2) a few years ago, but I have misplaced the
proofs. (Primo URL: http://www.ellipsa.eu/public/primo/primo.html)

    Primo is a primality proving program based on the ECPP (Elliptic
    Curve Primality Proving) algorithm. Given positive odd integers,
    it tests whether these integers are prime, and if they are it
    produces primality certificates. With Primo, one can check
    crypto-primes and prove whether they are actually prime... or
    not.

So, again for this specific case, are there any objections to proceeding
with the RFC 3526 prime numbers as provided in this draft?

	-- Mark

---

From: Kyle Rose <[email-masked]>
Date: Mon, 3 Apr 2017 21:33:22 -0400

> with the RFC 3526 prime numbers as provided in this draft?

This non-cryptographer has no specific objections based on what I've read
here. FWIW.

Kyle

---

From: Hubert Kario <[email-masked]>
Date: Tue, 04 Apr 2017 10:28:01 +0200

> to get decent speedup from SNFS.

yes, but that "decent" speedup is in practice an order or two in magnitude 
(downgrade of a 1024 bit prime to 1000 bit)[2]. That applies only for the 
sieve step of the attack, it does not apply to the linear algebra (the thing 
that dominates the precomputation) or the descent step[1].

 1 - https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf
 2 - Coppersmith, D. "Modifications to the Number Field Sieve." J. Cryptology 
6, 169-180, 1993
-- 
Regards,
Hubert Kario
Senior 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

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 4 Apr 2017 15:09:28 +0300

> https://www.ietf.org/mail-archive/web/curdle/current/msg00808.html

And the method used was following the method described in the RFC2412
Appendix E:

----------------------------------------------------------------------
   Classical Diffie-Hellman Modular Exponentiation Groups

   The primes for groups 1 and 2 were selected to have certain
   properties.  The high order 64 bits are forced to 1.  This helps the
   classical remainder algorithm, because the trial quotient digit can
   always be taken as the high order word of the dividend, possibly +1.
   The low order 64 bits are forced to 1.  This helps the Montgomery-
   style remainder algorithms, because the multiplier digit can always
   be taken to be the low order word of the dividend.  The middle bits
   are taken from the binary expansion of pi.  This guarantees that they
   are effectively random, while avoiding any suspicion that the primes
   have secretly been selected to be weak.

   Because both primes are based on pi, there is a large section of
   overlap in the hexadecimal representations of the two primes.  The
   primes are chosen to be Sophie Germain primes (i.e., (P-1)/2 is also
   prime), to have the maximum strength against the square-root attack
   on the discrete logarithm problem.

   The starting trial numbers were repeatedly incremented by 2^64 until
   suitable primes were located.

   Because these two primes are congruent to 7 (mod 8), 2 is a quadratic
   residue of each prime.  All powers of 2 will also be quadratic
   residues.  This prevents an opponent from learning the low order bit
   of the Diffie-Hellman exponent (AKA the subgroup confinement
   problem).  Using 2 as a generator is efficient for some modular
   exponentiation algorithms.  [Note that 2 is technically not a
   generator in the number theory sense, because it omits half of the
   possible residues mod P.  From a cryptographic viewpoint, this is a
   virtue.]
----------------------------------------------------------------------

> proofs. (Primo URL: http://www.ellipsa.eu/public/primo/primo.html)

In addition to verify that primality of the primes, it is important to
verify that the primes are also the first ones you will find by
following the algorithm described above. I.e., that the one generating
them did not skip a number trying to find the "good" one. I.e., that
there was not a bug in our software we used to find those primes...

Btw, in early days I used program called ECPP written by Francois
Morain (INRIA) on alpha architecture to verify the primes, and moved
to Primo 1.0.0 on x86 when starting to work on the 6144, and 8192.
Then I moved to primo 2.0 when trying to proove 12288 and 16384 bit
primes. So the smaller primes (<6144) have been verified by using two
different programs, on two different architectures and using different
operating systems, so perhaps we can trust those verifications...

-- 
[email-masked]

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 6 Apr 2017 12:14:09 +0000

Tero Kivinen <[email-masked]> writes:

>In SSH RFC4419 allows transfering also p and g only. There is no space for q
>or h.
>
>Not sure about TLS.

TLS-LTS updates the spec to send { p, q, g }, that was one of the explicit
changes made so you can now verify the DH values.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 6 Apr 2017 12:20:59 +0000

Tero Kivinen <[email-masked]> writes:

>How about you verifying both IKE and TLS groups and make sure they are
>actually generated as explained, and that they are first primes matching the
>process...

And now we run into the Bystander Effect problem of security audits, everyone
wants to have source code for whatever security tool they use published but
no-one would ever dream of checking the code themselves, they all expect
someone else to do it for them...

>If you are scared about that then just go to the 4096 bit Diffie-Hellman. If
>it will take years to break 1024-bit DH, and billion years (10^9) more to
>break 2048-bit DH, then 4096-bit DH should be safe... :-)

I think we'll have to agree to disagree on our approaches here, you seem to be
advocating putting all your trust in a single honkin' big key, while I prefer
to diversify as much as possible so that if something breaks in one location
then there are a pile of other measures that'll serve as a backup.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 6 Apr 2017 12:58:55 +0000

Mark D. Baushke <[email-masked]> writes:

>I don't think we know how effective Nothing Up My Sleeve (NUMS) techniques
>will be in the long run.

I think the first thing we'd need to do is figure out what people agree on as
being NUMS.  The Brainpool ECC curves, for example, are meant to be NUMS, but
then people have pointed out that there are various sources of attacker-
controlled (or at least curve-generator-controlled) entropy that went into
those such as the choice of hash algorithm (you can get several bits by
deciding to use SHA-1 vs SHA2-256 vs SHA2-512 vs. ...), and other odds and
ends.   What PRF do you use?  What constant(s) do you start with?  etc.  In
any case, is this actually an issue or is it just people nitpicking?

Then there's the question of how you generate them.  I'd prefer something that
can be coded up relatively easily in your bignum library of choice, so that
anybody can verify, using something they've built themselves, that things are
kosher.  It's been pointed out that https://kivinen.iki.fi/primes/ contains
primality proofs, but what it really contains is a huge amount of text that
doesn't mean anything to anyone who isn't intimately familiar with the tool
used.  This isn't in any way meant as a criticism of Tero, but more to point
out that saying "here is a large amount of incomprehensible machine-generated
text, trust me, the primes are OK" reduces directly to "trust me, the primes
are OK".  Since most people won't be able to make head or tail of what's on
that page, the result ends up as "trust me" again.

Extending this further, if I wanted to replicate the results on that web page,
I'd end up on http://www.ellipsa.eu/public/primo/primo.html, an HTTP (non-
HTTPS) web page with an unsigned, unauthenticated 7z file containing a binary
blob that I'm expected to download and run on a 64-bit Linux box to verify
that my precious crypto parameters aren't backdoored.  

So, how many people can see the problem here?

Again, I'm not saying that any of this has been deliberately backdoored or
rigged, but more that if you're going for NUMS then it needs to be NUMS all
the way down, not "this bit can be verified, and after that you'll just have
to trust me".  So perhaps the doc that specifies the values could contain
pseudocode that anyone can use with (at least) GMP and the OpenSSL bignum
routines to check that all is OK.  And by that I don't mean a full-on
primality prover, just a standard probabilistic check of the kind that a
generic crypto library would be using in any case to generate DH parameter
sets.

Peter.

---

From: Hubert Kario <[email-masked]>
Date: Thu, 06 Apr 2017 15:23:35 +0200

On Thursday, 6 April 2017 14:58:55 CEST Peter Gutmann wrote:
> Then there's the question of how you generate them.  I'd prefer something
> that can be coded up relatively easily in your bignum library of choice, so
> that anybody can verify, using something they've built themselves, that
> things are kosher.  It's been pointed out that
> https://kivinen.iki.fi/primes/ contains primality proofs, but what it
> really contains is a huge amount of text that doesn't mean anything to
> anyone who isn't intimately familiar with the tool used.  This isn't in any
> way meant as a criticism of Tero, but more to point out that saying "here
> is a large amount of incomprehensible machine-generated text, trust me, the
> primes are OK" reduces directly to "trust me, the primes are OK".  Since
> most people won't be able to make head or tail of what's on that page, the
> result ends up as "trust me" again.

That how _all of cryptography_ works.

Either you understand enough of the maths to follow along or you delegate it 
to others and trust them.
 
> Extending this further, if I wanted to replicate the results on that web
> page, I'd end up on http://www.ellipsa.eu/public/primo/primo.html, an HTTP
> (non- HTTPS) web page with an unsigned, unauthenticated 7z file containing
> a binary blob that I'm expected to download and run on a 64-bit Linux box
> to verify that my precious crypto parameters aren't backdoored.
> 

the point of generating primality certificates is that you don't care where 
they come from, either you can verify them and then you know that the number 
tested is prime or you can't verify it and the number is likely not a prime 
(or the certificate is bogus)

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 6 Apr 2017 17:31:43 +0300

> someone else to do it for them...

I did verify the tools I used to verify those numbers, and I did
verify the numbers generated by others. I cannot really do anything
else than try to convince others to do same, so we get more
independent audits done.

> then there are a pile of other measures that'll serve as a backup.

Yes, I definately think it is good to have one secure lock leading to
room having dozen of important things, compared to have dozen rooms
each with important things, and of those rooms have separate door and
weak lock on the door.

In my case the attacker needs to break the one secure lock, but when
they do that they get everything, in your case they just need to break
one weak lock to get something, and then they need to repeat the
process dozen time, but their expected time to complete is still small
fraction of time they require to break the one secure lock.

And actually you also want to weak locks to be manufactured by
different companies, where some of the companies might tell how the
lock designed and manufactured, but most of the companies do not tell
anything how the lock was designed or manufactured, you just assume
they are good as they are the one providing the lock. And from the
outside you cannot even see if the lock has any internal mechanisms
inside, or wheter it can be opened with just screw driver...
-- 
[email-masked]

---

From: Anna Johnston <[email-masked]>
Date: Thu, 6 Apr 2017 17:38:23 +0000

Perhaps it would be wise to provide documentation on what is in the certificate and how it is used to verify primality?  That way ‘trust me’ can be verified mathematically.  

Anna

---

From: Hubert Kario <[email-masked]>
Date: Thu, 06 Apr 2017 20:03:37 +0200

On Thursday, 6 April 2017 19:38:23 CEST Anna Johnston wrote:
> Perhaps it would be wise to provide documentation on what is in the
> certificate and how it is used to verify primality?  That way ‘trust me’
> can be verified mathematically.  

It is. If you download the archive, there's a primo.html file inside. In that 
file there is a "What is a primality certificate?" section that explains it.

We will Real Soon Now™ release a pure python verifier for the Primo 
certificates (in version 4 format).

(if somebody wants it now, I can provide it to them, but the code has horrible 
usability currently - it's basically a prototype).

> Cc: "Mark D. Baushke" <[email-masked]>, Kyle Rose <[email-masked]>, Ilari
> Liusvaara <[email-masked]>, Anna Johnston <[email-masked]>,
> "[email-masked]" <[email-masked]>, "Salz, Rich" <[email-masked]>, Tero
> Kivinen <[email-masked]>
> Subject: Re: [Curdle]
>     > that anybody can verify, using something they've built
>     > themselves, that things are kosher.  It's been pointed out that
>     > way meant as a criticism of Tero, but more to point out that
>     > saying "here is a large amount of incomprehensible machine-generated
>     > text, trust me, the primes are OK" reduces directly to "trust me, the
>     > primes are OK".  Since most people won't be able to make head or tail
>     > of what's on that page, the result ends up as "trust me" again.
> 
>     
> they come from, either you can verify them and then you know that
> the number tested is prime or you can't verify it and the number is likely
> not a prime (or the certificate is bogus)
>     
>     -- 
>     Regards,
>     Hubert Kario

---

From: Anna Johnston <[email-masked]>
Date: Thu, 6 Apr 2017 18:21:30 +0000

All the primes in the list are safe.  The certificates are based off elliptic curve testing, a variant of Pocklington’s which ONLY makes sense to use if you don’t know the complete factorization of at least ½ the bits of (P-1).  Why not replace these with much easier to verify Pocklington certificates?  This would also guarantee, at no extra cost, an element of order q.

A. Johnston

---

From: Hubert Kario <[email-masked]>
Date: Thu, 06 Apr 2017 20:32:14 +0200

On Thursday, 6 April 2017 20:21:30 CEST Anna Johnston wrote:
> All the primes in the list are safe.  The certificates are based off
> elliptic curve testing, a variant of Pocklington’s which ONLY makes sense
> to use if you don’t know the complete factorization of at least ½ the bits
> of (P-1).  Why not replace these with much easier to verify Pocklington
> certificates?  This would also guarantee, at no extra cost, an element of
> order q.

but for Pocklington to work, we need to be certain that q is prime, don't we?

> Cc: Peter Gutmann <[email-masked]>, Mark Baushke
> <[email-masked]>, Kyle Rose <[email-masked]>, Ilari Liusvaara
> <[email-masked]>, "[email-masked]" <[email-masked]>, "Salz,
> Rich" <[email-masked]>, Tero Kivinen <[email-masked]>
>  Subject: Re:
> [Curdle] draft-ietf-curdle-ssh-modp-dh-sha2
> 
> Liusvaara <[email-masked]>, Anna Johnston
>     > <[email-masked]>, "[email-masked]" <[email-masked]>, "Salz, Rich"
>     > <[email-masked]>, Tero Kivinen <[email-masked]>
>     > Subject: Re: [Curdle]
>     >     > that can be coded up relatively easily in your bignum library
>     >     > of
>     >     > choice, so
>     >     > really contains is a huge amount of text that doesn't mean
>     >     > anything
>     >     > to
>     >     > anyone who isn't intimately familiar with the tool used.  This
>     >     > isn't
>     >     > in any
>     >     Either you understand enough of the maths to follow along or you
>     > 
>     > delegate it 
>     >     > Extending this further, if I wanted to replicate the results on
>     >     > that
>     >     > web
>     >     > page, I'd end up on
>     >     > http://www.ellipsa.eu/public/primo/primo.html, an
>     >     > HTTP
>     >     > a binary blob that I'm expected to download and run on a 64-bit
>     >     > Linux
>     >     > box
>     >     the point of generating primality certificates is that you don't
>     >     care
>     > 
>     > where

---

From: Anna Johnston <[email-masked]>
Date: Thu, 6 Apr 2017 18:45:42 +0000

Yes, but another primality proof of the same size is also required for EC primality testing.  EC primality testing is similar to Pocklington’s – it just goes around the problem of partially factoring (P-1) by moving to an EC group and partially factoring the order of the group (~ same size as prime), and proving that those factors are prime.  Since you’re going to need to prove that (p-1)/2 is prime anyway, it’s a huge waste of resources and adding a lot more complication to a simple validation than is necessary to use EC.

A. Johnston

---

From: denis bider <[email-masked]>
Date: Thu, 6 Apr 2017 23:40:51 -0600

I agree with Tero in this case. Having four keys instead of one adds 2 bits
of security. If one of those keys is broken, the others are most likely too.

To quote Carnegie from June 1885:

*The concerns which fail are those which have scattered their capital,
which means that they have scattered their brains also. They have
investments in this, or that, or the other, here, there and everywhere.
“Don’t put all your eggs in one basket” is all wrong. I tell you “put all
your eggs in one basket, and then watch that basket.”*

On Thu, Apr 6, 2017 at 6:20 AM, Peter Gutmann <[email-masked]>
wrote:

> _______________________________________________
> Curdle mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/curdle
>

---

From: Hubert Kario <[email-masked]>
Date: Fri, 07 Apr 2017 12:06:09 +0200

On Thursday, 6 April 2017 20:45:42 CEST Anna Johnston wrote:
> Yes, but another primality proof of the same size is also required for EC
> primality testing.  EC primality testing is similar to Pocklington’s – it
> just goes around the problem of partially factoring (P-1) by moving to an
> EC group and partially factoring the order of the group (~ same size as
> prime), and proving that those factors are prime.  Since you’re going to
> need to prove that (p-1)/2 is prime anyway, it’s a huge waste of resources
> and adding a lot more complication to a simple validation than is necessary
> to use EC.

But then you reduce the size of the p by one bit. Primo in first step usually 
reduces the size of the number-needed-to-be-proven-prime by 20-30 bits, and 
jumps of 50 bits are not uncommon either.

So while yes, you can use that property of the safe primes, the gain isn't 
much and the primality certificate will be unnecessarily large.

Either way, I'm just a user of Primo, you should talk to developers of it if 
you really are convinced that special approach for safe primes will make the 
process faster.

>     >     > certificate and how it is used to verify primality?  That way
>     >     > ‘trust
>     >     > me’
>     >     It is. If you download the archive, there's a primo.html file
>     >     inside. In
>     > 
>     > that 
>     >     (if somebody wants it now, I can provide it to them, but the code
>     >     has
>     > 
>     > horrible 
>     >     > Cc: "Mark D. Baushke" <[email-masked]>, Kyle Rose
>     >     > <[email-masked]>,
>     >     > Ilari
>     > 
>     >     >     > Then there's the question of how you generate them.  I'd
>     >     >     > prefer
>     >     >     > something
>     >     >     > https://kivinen.iki.fi/primes/ contains primality proofs,
>     >     >     > but
>     >     >     > what it
>     >     >     > text, trust me, the primes are OK" reduces directly to
>     >     >     > "trust
>     >     >     > me, the
>     >     >     > primes are OK".  Since most people won't be able to make
>     >     >     > head or
>     >     >     > tail
>     >     >     > (non- HTTPS) web page with an unsigned, unauthenticated 7z
>     >     >     > file
>     >     >     > containing
>     >     > the number tested is prime or you can't verify it and the number
>     >     > is
>     >     > likely

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 8 Apr 2017 03:37:19 +0000

>of security. If one of those keys is broken, the others are most likely too.

I've already responded to this when someone else made the same erroneous
claim, this only holds if you can solve the DLP for (say) a 2048-bit parameter
set in constant time.  Unless you have a mechanism for mapping a solution for
any given 2048-bit DLP to every other 2048-bit DLP in O( 1 ) time, that claim
is fallacious.

(Or perhaps disingenious, if you're aware of, but have omitted to mention,
that each bit of security represents 10,000 years of supercomputer time, or
whatever it takes to solve a 2048-bit DLP).

There's a great analysis of security by diversification by "Daniel" from Bruce
Schneier's blog, in the discussion of the Kalnya block cipher:

  The issue of efficiency vs security works both ways. Let me draw on an
  example from the law. Currently, in the USA, it is well recognized that more
  than 90% of all criminal cases end with a plea bargain. Further, it is
  recognized that the system has become financially dependent on this reality.
  The consequence being is that if everyone stopped pleading guilty and
  instead went to trial the entire system would freeze because there is no
  manpower or funding to try all the case, not even 25% of them.

  So same situation is true for crypto. Anyone who rolls their own crypto is
  at one level a fool because anyone can make a standard they themselves
  cannot break. Yet imagine if the world of hurt the NSA would be in if it had
  to confront one million different kinds of crypto. Each one individually
  might be trivial to break but collectively they would freeze the agency.
  There simply isn't the manpower or the funding to go through a million cases
  and break each individually.

  So there is a strong argument that with crypto standards, whether they be
  set by NIST or the Ukrainian government, makes individuals stronger while
  making the collective weaker whereas if everyone rolled their own the
  individual cyphers would be weaker but the collective would be stronger.

Peter.

---

From: denis bider <[email-masked]>
Date: Sat, 8 Apr 2017 05:13:19 -0600

This rides entirely on the assumption that if a widely known large DH group
is broken, the break will be just feasible enough to be doable, and just
difficult enough that repeating it two or three times is outside the budget.

This is an extraordinarily contrived set of circumstances, which is
probably not true even now for 1024-bit groups.

Note that the argument you cite is for "one million different kinds of
crypto", not "two or three different kinds of crypto". One million is 20
additional bits.

This is a solid argument for dynamically generated groups, which seem to me
a problem worth solving (i.e. provide a way the other party can be sure the
group is good). But it does not appear to be a particularly strong argument
in favor of different fixed groups in SSH vs. e.g. IKE.

---

From: Daniel Migault <[email-masked]>
Date: Wed, 12 Apr 2017 11:37:14 -0400

Hi,

Would we have any consensus considering IKE group for this draft and leave
random alternatives for the future ?

Yours,
Daniel

On Sat, Apr 8, 2017 at 7:13 AM, denis bider <[email-masked]>
wrote:

> This rides entirely on the assumption that if a widely known large DH
> group is broken, the break will be just feasible enough to be doable, and
> just difficult enough that repeating it two or three times is outside the
> budget.
>
> This is a solid argument for dynamically generated groups, which seem to
> me a problem worth solving (i.e. provide a way the other party can be sure
> the group is good). But it does not appear to be a particularly strong
> argument in favor of different fixed groups in SSH vs. e.g. IKE.
>
>