Fwd: Tor security advisory: DH handshake flaw

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