Fwd: Tor security advisory: DH handshake flaw

[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 majordomo at metzdowd.com