Re: Fwd: Tor security advisory: DH handshake flaw
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
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
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
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
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
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
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
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
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
Dont be concerned about secrecy of prime generated with Maurers 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
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
[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
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 cant find a counter-example, but Pomerance hasnt found one yet, and thats 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 Maurers 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. Maurers method doesnt pick and test random candidates, rather it constructs, in a special way, an integer that is guaranteed to be prime. Dont be concerned about secrecy of prime generated with Maurers 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). Maurers 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
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
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
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
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
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
- 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]
Fwd: Tor security advisory: DH handshake flaw
- Forwarded message from Roger Dingledine [EMAIL PROTECTED] -
From: Roger Dingledine [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Date: Thu, 11 Aug 2005 21:31:32 -0400
Subject: Tor security advisory: DH handshake flaw
Versions affected: stable versions up through 0.1.0.13 and experimental
versions up through 0.1.1.4-alpha.
Impact: Tor clients can completely lose anonymity, confidentiality,
and data integrity if the first Tor server in their path is malicious.
Specifically, if the Tor client chooses a malicious Tor server for
her first hop in the circuit, that server can learn all the keys she
negotiates for the rest of the circuit (or just spoof the whole circuit),
and then read and/or modify all her traffic over that circuit.
Solution: upgrade to at least Tor 0.1.0.14 or 0.1.1.5-alpha.
The details:
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)
As far as we can tell, there are two classes of weak keys. The first class
(0, 1, p-1=-1) works great in the above attack. The new versions of Tor
thus refuse handshakes involving these keys, as well as keys 0 and = p.
The second class of weak keys are ones that allow Mallory to solve for y
given g^y and some guessed plaintext. These are rumored to exist when the
key has only one bit set [3]. But in Tor's case, Mallory does not know
g^x, so nothing she can say to Alice will be acceptable. Thus, we believe
Tor's handshake is not vulnerable to this second class of weak keys.
Nonetheless, we refuse those keys too. The current Tor release refuses
all keys with less than 16 0 bits set, with less than 16 1 bits set,
with values less than 2**24, and with values more than p - 2**24. This
is a trivial piece of the overall keyspace, and might help with next
year's weak key discoveries too.
Yay full disclosure,
--Roger
[1] http://tor.eff.org/doc/tor-spec.txt section 0 and section 4.1
[2] http://tor.eff.org/doc/design-paper/tor-design.html#subsec:circuits
[3]
http://www.chiark.greenend.org.uk/ucgi/~cjwatson/cvsweb/openssh/dh.c?rev=1.1.1.7content-type=text/x-cvsweb-markup
and look for dh_pub_is_valid()
- End forwarded message -
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
