Re: Fwd: Tor security advisory: DH handshake flaw

2005-09-03 Thread astiglic
 On Thu, 01 Sep 2005 15:04:43 +0200, Simon Josefsson said:

 If you control the random number generator, you control which
 Miller-Rabin bases that are used too.

 Oh well, if you are able to do this you have far easier ways of
 compromising the security.  Tricking the RNG to issue the same number
 to requests for the secret exponent of an DSA sign operation seems to
 be easier.

I agree.  Either assume that the code on the PC is valid, or don't.  If
you don't, anything can have a back door in it, the encryption or
signature code, the Miller-Rabin test, the RNG, the encoding scheme you
use, etc.

--Anton



-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-09-02 Thread Werner Koch
On Thu, 01 Sep 2005 15:04:43 +0200, Simon Josefsson said:

 If you control the random number generator, you control which
 Miller-Rabin bases that are used too.

Oh well, if you are able to do this you have far easier ways of
compromising the security.  Tricking the RNG to issue the same number
to requests for the secret exponent of an DSA sign operation seems to
be easier.

 Designing this fake random number generator is not trivial, and must
 likely be done separately for each crypto library that is used.  If
 software only used prime numbers that came with a prime certificate,
 you combat this attack.

Here it would be easier to add a backdoor to the prime certificate
check than to implement a fake RNG.


Shalom-Salam,

   Werner


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-09-01 Thread Ben Laurie

Simon Josefsson wrote:

Btw, could you describe the threat scenario where you believe this
test would be useful?


Well, that's an interesting question. I have to admit that I am no 
longer sure there is any point. If people do an appropriate number of 
rounds of Miller-Rabin whenever they're handed a number that is 
supposedly prime, they're pretty safe.


Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/

There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-09-01 Thread Simon Josefsson
Werner Koch [EMAIL PROTECTED] writes:

 On Mon, 29 Aug 2005 17:32:47 +0200, Simon Josefsson said:

 which are Fermat pseudoprime in every base.  Some applications,
 e.g. Libgcrypt used by GnuPG, use Fermat tests, so if you have control
 of the random number generator, I believe you could make GnuPG believe
 it has found a prime when it only found a Carmichael number.

 5 Rabin-Miller tests using random bases are run after a passed Fermat
 test.

If you control the random number generator, you control which
Miller-Rabin bases that are used too.

Of course, it must be realized that the threat scenario here is
slightly obscure.  The scenario I have been thinking about is when an
attacker has gained control of the hardware or kernel.  The attacker
might then be able to see when a crypto library requests randomness,
and return carefully constructed data to fool the user.  The
constructed data should be so the RSA/DH parameters become weak [for
the attacker].  The attacker may not be in a position to send the
generated prime back home over the network, and doing that may also be
detected by firewalls.  The target system might not even be networked.

Designing this fake random number generator is not trivial, and must
likely be done separately for each crypto library that is used.  If
software only used prime numbers that came with a prime certificate,
you combat this attack.

Too bad you can't mathematically certify that real randomness was
used in choosing the prime too.  Although perhaps you get pretty close
with algorithms that both generate a prime and a prime certificate in
one go.

Regards,
Simon

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-31 Thread Simon Josefsson
Ben Laurie [EMAIL PROTECTED] writes:

 Simon Josefsson wrote:
 No, the certificate is verifiable in deterministic polynomial time.
 The test is probabilistic, though, but as long as it works, I don't
 see why that matters.  However, I suspect the ANSI X9.80 or ISO 18032
 paths are more promising.  I was just tossing out URLs.

 Surely Miller-Rabin is polynomial time anyway?

Yes, but it doesn't produce certificates; the algorithm that I cited
do.  The algorithm to _verify_ the certificate was not probabilistic,
only the algorithm to _produce_ the certificates was probabilistic.

Btw, could you describe the threat scenario where you believe this
test would be useful?

Thanks,
Simon

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-31 Thread Werner Koch
On Mon, 29 Aug 2005 17:32:47 +0200, Simon Josefsson said:

 which are Fermat pseudoprime in every base.  Some applications,
 e.g. Libgcrypt used by GnuPG, use Fermat tests, so if you have control
 of the random number generator, I believe you could make GnuPG believe
 it has found a prime when it only found a Carmichael number.

5 Rabin-Miller tests using random bases are run after a passed Fermat
test.


Salam-Shalom,

   Werner




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-30 Thread Ben Laurie

Simon Josefsson wrote:

No, the certificate is verifiable in deterministic polynomial time.
The test is probabilistic, though, but as long as it works, I don't
see why that matters.  However, I suspect the ANSI X9.80 or ISO 18032
paths are more promising.  I was just tossing out URLs.


Surely Miller-Rabin is polynomial time anyway?

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/

There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-29 Thread Simon Josefsson
Ben Laurie [EMAIL PROTECTED] writes:

 Simon Josefsson wrote:
 Ben Laurie [EMAIL PROTECTED] writes:
 
[EMAIL PROTECTED] wrote:

So Miller-Rabin is good for testing random candidates, but it is easy to
maliciously construct an n that passes several rounds of
 Miller-Rabin.  

Interesting! So how does one go about constructing such an n?
 I wonder if the original author didn't think of Carmichael numbers,
 which are Fermat pseudoprime in every base.  Some applications,
 e.g. Libgcrypt used by GnuPG, use Fermat tests, so if you have control
 of the random number generator, I believe you could make GnuPG believe
 it has found a prime when it only found a Carmichael number.

 Surely the attack of interest is where the attacker provides the prime - 
 no control of RNGs is required for this.

Right.  The attack I mentioned was a tangent off the Fermat test.

However, controlling the prime numbers seem to be comparable to
controlling the random number generator.  I.e., you have some access
to the subject's hardware, and want to trick the software into using
crackable parameters for RSA, DH etc.  If the application doesn't use
prime numbers without a proof, neither of these two attacks aren't
possible.  So this is actually a class of attacks.

 However, for Miller-Rabin, it has been proven that all composite
 numbers pass the test for at most 1/4 of the possible bases.  So as
 long as you do sufficiently many independent tests (different bases,
 preferably chosen at random), I don't see how you could be fooled.
 http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
 Doing the test for more than 1/4 of the bases (which would actually
 prove the number prime, although without a succinct witness) for large
 numbers is too expensive though.
 One algorithm that results in a polynomially verifiable witness is:
 Almost All Primes Can be Quickly Certified
 http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc-gk.pdf

 This appears to be a probabilistic certificate, which strikes me as 
 rather pointless.

No, the certificate is verifiable in deterministic polynomial time.
The test is probabilistic, though, but as long as it works, I don't
see why that matters.  However, I suspect the ANSI X9.80 or ISO 18032
paths are more promising.  I was just tossing out URLs.

Regards,
Simon

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-29 Thread Simon Josefsson
Ben Laurie [EMAIL PROTECTED] writes:

 [EMAIL PROTECTED] wrote:
 So Miller-Rabin is good for testing random candidates, but it is easy to
 maliciously construct an n that passes several rounds of
 Miller-Rabin.  

 Interesting! So how does one go about constructing such an n?

I wonder if the original author didn't think of Carmichael numbers,
which are Fermat pseudoprime in every base.  Some applications,
e.g. Libgcrypt used by GnuPG, use Fermat tests, so if you have control
of the random number generator, I believe you could make GnuPG believe
it has found a prime when it only found a Carmichael number.

However, for Miller-Rabin, it has been proven that all composite
numbers pass the test for at most 1/4 of the possible bases.  So as
long as you do sufficiently many independent tests (different bases,
preferably chosen at random), I don't see how you could be fooled.

http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

Doing the test for more than 1/4 of the bases (which would actually
prove the number prime, although without a succinct witness) for large
numbers is too expensive though.

One algorithm that results in a polynomially verifiable witness is:

Almost All Primes Can be Quickly Certified
http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc-gk.pdf

Btw, I've been playing with prime proving in the past, and if you want
to specify a format for prime proofs that OpenSSL would understand, I
would consider supporting the same format in GnuTLS.  Trusting that
numbers are prime for cryptographic purposes should require a proof.
There are several prime proof formats, but I can't tell if they are
practical for this purpose.

Regards,
Simon

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-29 Thread astiglic

 Don’t be concerned about secrecy of prime generated with Maurer’s
 method,
 the method generates primes that are almost uniformly distributed over
 the
 set of all numbers (this is different from another algorithm called
 Shawe-Taylor, which is similar in functioning but only reaches 10% of
 all
 primes of a specified set).

 I presume you mean densely distributed over the set of all primes?
 Uniform distribution isn't much use if its sparse!

What I wanted to say is the method generates primes that are close to
uniformly distributed over the set of primes in the specified interval,
as stated in Maurer's papers.  In other words, the distribution of primes
created is similar that that when using the method of picking uniformly at
random candidates in an interval and passing the Miller-Rabin test
(except, of cours, there is no probability of error (picking a
pseudo-prime)), which most crypto libraries do.

--Anton




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-29 Thread astiglic

 One algorithm that results in a polynomially verifiable witness is:

 Almost All Primes Can be Quickly Certified
 http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc-gk.pdf

That's a very old algorithm.  It was an intersting result at the time
(1986) because it is a primality proving algorithm that is not based on
any hypothesis and runs in *expected polynomial time* on almost all inputs
(note the *expected*).  It uses elliptic curves.  However, the algorithm
is not efficient in practice, and we have better theoretical results today
(Agrawal-Kayal-Saxena that is a true primality test that works in
polynomial time on all inputs.  Note that such a deterministic
polynomial-time primality testing algorithm implicitly provides a trivial
certificate of primality, which simply consists of the prime number
itself).

Goldwasser and Kilian's result was extended by ADleman and Huang, later
Atkin developed a simialr algorithm known as the Elliptic Curves for
Primality Proving (ECPP), which I also referred to in my initial post.
Morain worked on implementing Atkin's algorithm.  This is efficient. 
Morain has a web page with lot's of info and nice working code:
http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html

The advantage of Maurer's construction, however, is that it is much
simpler to code.

--Anton


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-28 Thread Ben Laurie

[EMAIL PROTECTED] wrote:

So Miller-Rabin is good for testing random candidates, but it is easy to
maliciously construct an n that passes several rounds of Miller-Rabin.  


Interesting! So how does one go about constructing such an n?


Maurer’s method doesn’t pick and test random candidates, rather it
constructs, in a special way, an integer that is guaranteed to be prime.
Don’t be concerned about secrecy of prime generated with Maurer’s method,
the method generates primes that are almost uniformly distributed over the
set of all numbers (this is different from another algorithm called
Shawe-Taylor, which is similar in functioning but only reaches 10% of all
primes of a specified set).


I presume you mean densely distributed over the set of all primes? 
Uniform distribution isn't much use if its sparse!


Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/

There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-26 Thread astiglic
Some info on primality testing.

Miller-Rabin probabilistic primality tests work really well when you are
searching for a prime and picking candidates from a uniform random
distribution, also works well if you pick an initial candidate from a
uniform random distribution and then increment on that initial candidate,
until you find a probable prime. See the references

Damgard, Landrock and Pomerance (1993), Average case error estimates for
the strong probable prime test, Mathematics of Computation 61 (203).

Brandt, Damgard (1993) On generation of probable primes by incremental
search.  CRYPTO 92.

Summaries of the results can be found in the Handbook of applied
Cryptography.

On a side note about Miller-Rabin, there is something allot of people get
wrong.  The basic results we know is that one iteration of the
Miller-Rabin test will err in declaring a composite integer to be prime
with probability less than 1/4, while t iterations will err with
probability (1/4)^t.
You can find a proof for this is textbooks such as that of Koblitz.
If X stands for n is composite, and Y_t stands for RepeatRabin(n, t)
returned prime, where RepeatRabin is the algorithm that executes t
iterations of Miller-Rabin's test and outputs composite as soon as an
iteration fails, prime if all iterations passed.
Now, given the basic theorem mentioned above, all we can say is that
Prob[Y_t | X ] = (1/4)^t, in English “if n is composite, then
RepeatRabin(n,t) will return “prime” with probability less than or equal
to (1/4)^t”.  Much more interesting is to figure out Prob[X | Y_t], that
is “if RepeatRabin(n,t) returns “prime”, what is the probability that X is
actually composite and we got screwed?”.  It just happens to be that
Prob[X | Y_t] = (1/4)^t when n is chosen from a uniform random
distribution, because in such cases prob[Y_1 | X] is actually much smaller
than ¼.
See
Beauchemin, Brassard, Crépeau, Goutier, Pomerance. The generation of
random numbers that are probably prime”, Journal of Cryptology, 1, 53-64.

Ok, back to the main topic.
So Miller-Rabin is good for testing random candidates, but it is easy to
maliciously construct an n that passes several rounds of Miller-Rabin.  
The Miller-Rabin probabilistic primality test actually comes from a true
primality test, called Miller test, which is polynomial (but not efficient
in practice) and works assuming the Extended Riemann Hypothesis.

On proposed algorithm is to use two iterations of the Miller-Rabin test
followed by a single iteration of the Lucas probable prime test.  The
advantage of this test is that there is yet no known composite integer
that passes even a single Miller-Rabin test to the base 2 followed by a
single Lucas probable prime test.  There is also an open challenge
regarding this (something like 640$ coming directly from the pockets of
Pomerance and al.).  See
Pomerance (1984) Are There Counter-Examples to the Baillie-PSW Primality
Test?

This is the algorithm mentioned by Hal.  No, there is no proof that you
can’t find a counter-example, but Pomerance hasn’t found one yet, and
that’s good enough for me for the time being!

If you want primality certificates, and not just a randomized test that
has some probability of given you a wrong answer, look at Elliptic curve
primality test and Maurer’s algorithm.  These are both described in the
ISO 18032 “prime number generation” standard and ANSI X9.80 (this just
goes to show that these are not purely academic creations, but stuff you
can use in practice).

Elliptic Curves for Primality Proving (ECPP) is used like Miller-Rabin in
order to generate a prime:  chose random candidates until one passes the
test; but in addition it produces a certificate that allows you to verify
primality using a different algorithm (much less complicated than the one
used to generate a prime, so this allows you to validate the correctness
of the implementation of the prime generating algorithm as well).
See
Atkin, Morain (1993).  Elliptic curves and primality proving.  Mathematics
of Computations.


Maurer’s method doesn’t pick and test random candidates, rather it
constructs, in a special way, an integer that is guaranteed to be prime.
Don’t be concerned about secrecy of prime generated with Maurer’s method,
the method generates primes that are almost uniformly distributed over the
set of all numbers (this is different from another algorithm called
Shawe-Taylor, which is similar in functioning but only reaches 10% of all
primes of a specified set).
Maurer’s method is much easier to code than ECPP. See
Maurer (1995) Fast generation of prime numbers and secure public-key
cryptographic parameters.  Journal of Cryptology, 8(3), 123-155
Maurer.  Fast generation of secure RSA-moduli with almost maximal
diversity.  EUROCRYPT'89.



So, in conclusion, there is allot of good stuff to choose from!

--Anton


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe 

Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-22 Thread Ben Laurie

Jerrold Leichter wrote:

| Apologies, slightly at cross-purposes here. For a start, Sophie Germain primes
| are needed for D-H (or rather, safe primes), and secondly, I was talking about
| proving arbitrary primes, rather than constructing provable primes.


Isn't *proving* primality rather overkill for the purpose at hand (which seems 
to be verifying that an alleged prime isn't a non-prime, sent to spike the 
system).  Are there any known sets of numbers - much less ways to *choose* 
members of those sets - which will show up as prime with significant 
probability to Miller-Rabin?  As far as I know, M-R has a *worst case* false 
positive rate of 1/4.  Even a fairly small number of random M-R tests should 
make slipping in a non-prime less probable than a variety of other attacks.


There aren't any such sets known to me. Can I be sure there are none 
known to anyone? No.


Not sure I agree with the false positive rate. What is known is that 3/4 
of the bases are strong witnesses for a composite number. But is it 
known that these are evenly distributed? I don't know, but that would be 
required for a 1/4 false positive rate.


If you want to go further, there's the Baille-PSW test 
(http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) which it appears 
has no false positives for any integer of less than about 10,000 digits - 
way beyond what you would likely use in the near future.


Based on a statistical argument from a closed source prover and 
verifier. Hmm.


The point of proofs (at least, useful proofs) is that they produce 
certificates that are cheap to verify. So, yeah, sure it may be 
overkill, but I'll do the killing so you don't have to.


Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/

There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-22 Thread Hal Finney
Ben Laurie writes:
 Apologies, slightly at cross-purposes here. For a start, Sophie Germain 
 primes are needed for D-H (or rather, safe primes), and secondly, I was 
 talking about proving arbitrary primes, rather than constructing 
 provable primes.

Dan Bernstein has lots of good information on the state of the art in
general primality (and compositeness) proving.

http://cr.yp.to/primetests.html points to his recent survey paper and has
a table of the various algorithms.  Interestingly there are considerable
tradeoffs between proving time and verification time.  There are some
methods that create instant proofs but then take a long time to verify.

http://cr.yp.to/ntheory.html has some of Dan's own work, including an
algorithm which creates a certificate in time quadratic in length, with
verification costing time proportional to the 4th power of the length.

He suggests that at this point the best practical algorithm is based on
elliptic curves, which is conjectured to have running time proportional
to the 4th power of length for finding proofs and to the 3rd power for
verifying them.  I don't know what the actual numbers are for prime sizes
of interest (presumably 1K-8K bits or so).  References are available
from his papers.

Several programs to implement ECPP can be found from
http://primes.utm.edu/links/programs/seeking_large_primes/.  I don't
know about source code however.  It might be interesting to run these
over some of the Oakley primes and publish the certs - I vaguely recall
seeing something like that in an RFC.

Hal

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-21 Thread Hal Finney
Ben Laurie writes:
 Related to this is a project I keep considering and never quite getting 
 around to is to include a prime proof verifier in OpenSSL. It would be 
 pretty cool to have modes which only work when all relevant primes come 
 with proofs.

 I've looked into this a few times, but have always ended up at a slight 
 brick wall: I'd like to use proofs for which there's efficient (yes, I 
 know efficient means only takes a few months to run) code to produce 
 the proofs, as well as (obviously) efficient (where efficient means 
 really fast) verifiers. This is, of course, so new proven primes can 
 be produced without having to wait for someone with proprietary code to 
 feel so inclined.

If you look at Wei Dai's Crypto++ library, www.cryptopp.com, you
will see two implementations of provable prime generators, called
MihailescuProvablePrime and MaurerProvablePrime.  The first in particular
was quite fast and took only about 10 seconds to generate a 1024 bit
prime on my laptop (1GHz Mac G4).  However 2048 bit primes took more like
6 to 8 minutes, so it does slow down quite a bit for larger primes.

These functions don't output the certificate that proves it to be prime,
but they have a recursive structure and if you preserve the intermediate
values then there is a fast way of verifying the resulting primes.
The Mihailescu version is from his Crypto 94 paper which is available
from his web site, http://www-math.uni-paderborn.de/~preda/ and also
discusses verification.  I googled and found a someone more recent paper
by Mihailescu,
http://grouper.ieee.org/groups/1363/P1363a/contributions/mihailescu.pdf.

 Oh, BTW, bonus points if the prover can be run on large numbers of 
 processors in parallel. Even more points if communication between the 
 CPUs are low bandwidth.

Unless you're looking for primes with a special format, like Sophie
Germain primes or ones with lots of 1's up front and/or in the back, or
primes considerably larger than 2048 bits, current methods should be fast
enough for most applications even on sequential processors.

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-21 Thread Ben Laurie

Hal Finney wrote:

Ben Laurie writes:

Related to this is a project I keep considering and never quite getting 
around to is to include a prime proof verifier in OpenSSL. It would be 
pretty cool to have modes which only work when all relevant primes come 
with proofs.


I've looked into this a few times, but have always ended up at a slight 
brick wall: I'd like to use proofs for which there's efficient (yes, I 
know efficient means only takes a few months to run) code to produce 
the proofs, as well as (obviously) efficient (where efficient means 
really fast) verifiers. This is, of course, so new proven primes can 
be produced without having to wait for someone with proprietary code to 
feel so inclined.



If you look at Wei Dai's Crypto++ library, www.cryptopp.com, you
will see two implementations of provable prime generators, called
MihailescuProvablePrime and MaurerProvablePrime.  The first in particular
was quite fast and took only about 10 seconds to generate a 1024 bit
prime on my laptop (1GHz Mac G4).  However 2048 bit primes took more like
6 to 8 minutes, so it does slow down quite a bit for larger primes.

These functions don't output the certificate that proves it to be prime,
but they have a recursive structure and if you preserve the intermediate
values then there is a fast way of verifying the resulting primes.
The Mihailescu version is from his Crypto 94 paper which is available
from his web site, http://www-math.uni-paderborn.de/~preda/ and also
discusses verification.  I googled and found a someone more recent paper
by Mihailescu,
http://grouper.ieee.org/groups/1363/P1363a/contributions/mihailescu.pdf.


Oh, BTW, bonus points if the prover can be run on large numbers of 
processors in parallel. Even more points if communication between the 
CPUs are low bandwidth.



Unless you're looking for primes with a special format, like Sophie
Germain primes or ones with lots of 1's up front and/or in the back, or
primes considerably larger than 2048 bits, current methods should be fast
enough for most applications even on sequential processors.


Apologies, slightly at cross-purposes here. For a start, Sophie Germain 
primes are needed for D-H (or rather, safe primes), and secondly, I was 
talking about proving arbitrary primes, rather than constructing 
provable primes.


Incidentally, I presume that using constructed primes rather narrows the 
search space if they need to be secret (though I believe that proving 
arbitrary primes is rather too painful for routine use in this case, sadly).


Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/

There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-20 Thread Ben Laurie

Hal Finney wrote:

I was just at Crypto yesterday and Hugo Krawczyk in his talk emphasized
the difficulty of securely designing key exchange protocols.  He was
talking about implicit authorization protocols where the exponentiation
involves the long term public key(s).  This protocol is different but
there are still many ways things can go wrong.

This attack is an example of a small subgroup attack where the derived
value is forced into a small subgroup mod p, in this case the trivial
subgroup with one element.  Sometimes other subgroups can be used,
such as the group with order two (consisting of 1, p-1), or potentially
other groups.  But I checked the source code and Tor is using an Oakley
prime from RFC2409, with a generator g = 2.  The prime p is such that
q = (p-1)/2 is prime also, and g generates the prime order subgroup of
size q.  The only subgroups of such a p have order 1, 2, q, and 2q==(p-1).
By checking the received bignum is not 1, -1, or 0 (good catch, I forgot
about that one) and also not = p, you should be okay.


This is one reason everyone should use well-known primes for 
Diffie-Hellman (the other reason is the more obscure non-prime 
substitution attack using hash collisions discussed here a few months ago).


Related to this is a project I keep considering and never quite getting 
around to is to include a prime proof verifier in OpenSSL. It would be 
pretty cool to have modes which only work when all relevant primes come 
with proofs.


I've looked into this a few times, but have always ended up at a slight 
brick wall: I'd like to use proofs for which there's efficient (yes, I 
know efficient means only takes a few months to run) code to produce 
the proofs, as well as (obviously) efficient (where efficient means 
really fast) verifiers. This is, of course, so new proven primes can 
be produced without having to wait for someone with proprietary code to 
feel so inclined.


Do the experts out there have suggestions? Perhaps this time I'll get 
around to implementing.


Oh, BTW, bonus points if the prover can be run on large numbers of 
processors in parallel. Even more points if communication between the 
CPUs are low bandwidth.


It would also be nice to have a collection of primes and proofs in 
OpenSSL, so if people want to point me at such things, I'll do my best 
to make it so.


Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/

There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-19 Thread Hal Finney
 - Forwarded message from Roger Dingledine [EMAIL PROTECTED] -
 In Tor, clients negotiate a separate ephemeral DH handshake with each
 server in the circuit, such that no single server (Bob) in the circuit
 can know both the client (Alice) and her destinations. The DH handshake
 is as follows. (See [1,2] for full details.)

 Alice - Bob: E_{Bob}(g^x)
 Bob - Alice: g^y, H(K)

 Encrypting g^x to Bob's public key ensures that only Bob can learn g^x,
 so only Bob can generate a K=g^{xy} that Alice will accept. (Alice, of
 course, has no need to authenticate herself.)

 The problem is that certain weak keys are unsafe for DH handshakes:

 Alice - Mallory: E_{Bob}(g^x)
 Mallory - Bob:   E_{Bob}(g^0)
 Bob - Mallory:   g^y, H(1^y)
 Mallory - Alice: g^0, H(1^y)

 Now Alice and Bob have agreed on K=1 and they're both happy. In fact,
 we can simplify the attack:

 Alice - Mallory: E_{Bob}(g^x)
 Mallory - Alice: g^0, H(1)

I was just at Crypto yesterday and Hugo Krawczyk in his talk emphasized
the difficulty of securely designing key exchange protocols.  He was
talking about implicit authorization protocols where the exponentiation
involves the long term public key(s).  This protocol is different but
there are still many ways things can go wrong.

This attack is an example of a small subgroup attack where the derived
value is forced into a small subgroup mod p, in this case the trivial
subgroup with one element.  Sometimes other subgroups can be used,
such as the group with order two (consisting of 1, p-1), or potentially
other groups.  But I checked the source code and Tor is using an Oakley
prime from RFC2409, with a generator g = 2.  The prime p is such that
q = (p-1)/2 is prime also, and g generates the prime order subgroup of
size q.  The only subgroups of such a p have order 1, 2, q, and 2q==(p-1).
By checking the received bignum is not 1, -1, or 0 (good catch, I forgot
about that one) and also not = p, you should be okay.

Oh, I just thought of another small-subgroup related attack.  Very minor,
but a leak.  Mallory lets Alice's message goes through but negates Bob's
g^y value:

Alice - Mallory: E_{Bob}(g^x)
Mallory - Bob:   E_{Bob}(g^x)
Bob - Mallory:   g^y, H(K)
Mallory - Alice: -g^y, H(K)

Now, the exchange will complete successfully only if x is even.
So Mallory learns this fact.

You also want to think about replay attacks with these protocols, but
I don't see much of an issue there.  As long as x is fresh each time
then a replay shouldn't be possible.  And if you're re-using x values
you probably have a lot more serious problems than replay attacks.

I'm not in love with publishing H(K), especially with the iffy state
of hash functions these days.  Theoretically it provides another avenue
of attack to find the key.  Granted, K is 1024 bits and H(K) only 160,
so even if H were invertable, K would still be unguessable, and we're a
long, long ways from inverting any modern hash functions.

Another way to accomplish the same thing would be to encrypt a known
value under the derived encryption key.  Since you're going to be
encrypting lots of other stuff with the key, some of which you have to
pretty much assume is going to be known plaintext, you aren't exposing
any new weaknesses by doing that.

If you do want to use a hash, it's usually a good idea to throw as much
stuff into it as you have lying around.  I would include g^x and g^y in
the hash.  This would solve the attack you're worried about right there,
because Mallory doesn't know g^x.  Probably include p and g as well,
and Bob's identity.  It may be overkill but you never know when it will
stop an attack you didn't think of.

Ideally, I think Tor should switch to a different key exchange
protocol, one which has some degree of provable security, but
I am hesitant to recommend one.  Looking at your docs I gather
that you have some pretty severe space constraints.  Your article
http://tor.eff.org/doc/design-paper/tor-design.html#subsec:circuits says
that you didn't want to use a signature because you didn't have room
for it in your packet.  It also says, Preliminary analysis with the
NRL protocol analyzer [35] shows this protocol to be secure (including
perfect forward secrecy) under the traditional Dolev-Yao model.
It's interesting that these attacks exist given this security analysis.
Maybe it was treating the arithmetic as something of a black box?
Chalk it up as another example of the limitations of these kinds of tools.

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]