Subject: Re: [TLS] DH parameters, primality

From: Joseph Birr-Pixton <[email-masked]>
Date: Fri, 7 Mar 2014 10:17:55 +0000

On 7 March 2014 09:45,  Hanno Böck <[email-masked]> wrote:
> ---------- Forwarded message ----------
> From: Hanno Böck <[email-masked]>
> To: [email-masked]
> Cc:
> Date: Fri, 7 Mar 2014 10:45:13 +0100
> Subject: [TLS] DH parameters, primality
>
> The more difficult part is if primality should be tested in some way.
> The finders of the triple handshake issue propose to define a number
> of good primes. This is a good idea, but it doesn't solve the problem
> for connections with existing implementations.
> Currently, most DH exchanges are still 1024 bit. Primality tests for
> them are feasible. However, for 2048 bit they're challenging and for
> 4096 probably not feasible at all (about 1 second on my core2).
>
> Maybe it would be possible to run a miller rabin test with less rounds
> and have a "high probability prime" and consider that good enough?

Since these primes are adversarially chosen, you need to choose
drastically many more RM rounds to get even a "high probability
prime".

To be clear: most of the primality tests you'll find in your crypto
library or textbook only deal with randomly chosen candidates.

Cheers,
Joe

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 7 Mar 2014 12:30:27 +0200

> drastically many more RM rounds to get even a "high probability

I thought that if RM base is randomly chosen, it will pick composites
with probability of 3/4 per iteration, no matter how the number to
test to is picked.

-Ilari

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 07 Mar 2014 12:40:06 +0200

I'm far from an expert, but I seem to remember there are "pseudo primes" 
that will appear as prime to any Miller-Rabin test. I don't know how 
feasible it is for an attacker to generate such numbers.

Thanks,
	Yaron

On 03/07/2014 12:30 PM, Ilari Liusvaara wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Tanja Lange <[email-masked]>
Date: Fri, 7 Mar 2014 11:56:42 +0100

> feasible it is for an attacker to generate such numbers.
There are none for Miller Rabin, what you're thinking of is the Fermat
test.  You shold be fine with random tests but often bases are chosen
deterministically s small primes in order -- this makes the computaitons
somewhat cheaper.

More constructively though, verifying primality given a certificate is
much faster -- certificate here is not a CA kind of thing, it's what
number theorists (and complexity theorists) call a statement that goes
like this (using Pocklington as an example):
p is prime because:
* p_1 is prime,  divides p-1, is larger than sqrt(p-1) and a1 is a base
* p_2 is prime and divides p_1-1 and is larger than sqrt(p_1-1-1)  and
* a2 is a base .....

* 3 is a prime because I now it's a prime.

Finiding the p_i  costs time and effort, but verifying them is fast.
Note that there are several versions of Pocklington's test and there is
ECPP, so any number can be handled by these.

All the best
	Tanja

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 7 Mar 2014 13:01:28 +0200

On Fri, Mar 07, 2014 at 12:40:06PM +0200, Yaron Sheffer wrote:
> I'm far from an expert, but I seem to remember there are "pseudo
> primes" that will appear as prime to any Miller-Rabin test. I don't
> know how feasible it is for an attacker to generate such numbers.

There are such pseudoprimes for Fermat test but not Miller-Rabin.
Those pseudoprimes are known as "absolute pseudoprimes" or "Carmichael
numbers".

And then there are numbers that are primes, but are very weak as
DH primes.

-Ilari

---

From: Isaac Chua <[email-masked]>
Date: Fri, 7 Mar 2014 19:50:48 +0800

Generally when we talk about primes for Diffie-Hellman, we look at a
sufficiently large prime (1024-4096 bit as mentioned), with also a
sufficiently large subgroup order (256 bits for instance). There are two
basic classes of attacks: index calculus and its derivatives, and
Pollig-Hellman. The former, crudely speaking, is countered by a large
enough prime modulus, and the latter a large enough subgroup order (its
running time is sqrt(n) so you'd choose 256 bits for 128-bit security).

It has been suggested that safe primes be used (p = 2q + 1 where q is
prime), but Schnorr groups (p = qr + 1 where q is prime) were presented in
NIST publications and eventually included in RFCs such as 5114. q, in such
a construction determines the subgroup size, hence a safe prime by
definition would have a subgroup size almost as large as the prime itself
which isn't necessary.

FIPS 186-4 specifies in appendix A several methods for generating and
verifying DH parameters, perhaps that's a good place to start.

Isaac

Sent from my mobile device

-Ilari