Re: SSL and IPS (was RE: ssh and ids)

["Michael H. Warfield" <mhw () wittsend com>]

On Wed, Jun 30, 2004 at 02:28:51PM -0400, Rob Shein wrote:
> To determine the symmetric key that results from a DH exchange, all you need
> is the private key of one party (provided here by key escrow, as Peter
> Schawacker described) and the public key of the other party (captured off
> the wire).  You then perform the same calculation as the party whose private
> key you hold, and voila; you become a third party with the symmetric key.
> This is exactly why private keys are so sensitive, and there's nothing
> miraculous about it.  The same goes for any rekeys, which are also done with
> DH.  They aren't breaking DH, they're just taking advantage of the fact that
> their device is, like the SSL server, a trusted device which is granted
> access to private keys.

        I'm sorry, that's just totally bogus.  Unless you are seriously
misstating what you are talking about, you are mixing apples and oranges.

        Where you say "To determine the symmetric key that results from
a DH exchange, all you need is the private key of one party (provided
here by key escrow, as Peter Schawacker described) and the public key
of the other party (captured off the wire)."  Are you talking about
the private key stored in the servers key file or are you talking
about the D-H exponents (which are not keys at all but might be
referred to as keys) which are not even stored on disk at all?

        Then you go on to say: "This is exactly why private keys are so
sensitive."  The Diffie-Hellman exponents are never even stored to disk.
So, what's your point here?  It sounds like you are talking about the
private key, from the servers key file.  The thing that bounded by these
lines, in OpenSSL parleyance:

-----BEGIN RSA PRIVATE KEY-----
        :
-----END RSA PRIVATE KEY-----

        That private key?  The thing typically stored on RedHat Linux
systems as /etc/httpd/conf/ssl.key/server.key ?  (Yes, it's not
always there and yes virtual servers have them under their own name,
you get the point).

        Which is it?  The private RSA key from the server's certificate
keyfile or the Diffie-Hellman exponents.  They are not related.  If it's
the later, please stop incorrectly referring to them as keys and explain
how you are obtaining them.

        To clarify my side of this discussion and insure we are not mixing
apples and oranges at this point, I'll refer to the servers long term
static key which is associated with the servers signed certificate file
as the servers "private RSA key" so it can't be mistakenly confused with
the Diffie Hellman parameters.

        The "secret exponents" for the Diffie-Hellman key exchange
are not the private RSA keys from the certificates.  They are large prime
numbers choosen at random for each session.  The D-H modulus and
base (n and g) are public and advertised in the certificates.  The
D-H session exponents (x and y) are chosen at random for each session.
The two parties exchange (g**x mod n) and (g**y mod n) and each then
computes (k = g**(x*y) mod n) which no one passively listening into the
channel can compute.  The value "k" is the session key.  Nothing from the
server's private RSA key (the key from which the certificate is derived)
is used in the D-H transaction.

        Just to be formal about this whole thing, I'll remind everyone
of the Diffie Hellman math (apologies to the other cryptographers on
this list for boring you and turning this into crypto 101 hell...).

        (Notation here is from Applied Crytography, OpenSSL source
code uses different nominclature for the variable names).

        Basic Diffie Hellman Key Exchange Algorithm...

        Alice (the client) and Bob (the server) agree on large primes,
n and g, subject to some constraints (g primative mod n, n is a "strong"
prime [i.e. (n-1)/2 is also prime], no special generators, yada, yada,
yada - just accept it as an initialization conditions - these are static
public values anyways - more information is avaiable in the OpenSSL
sources about how these are derived and why .../crypto/dh/dh_gen.c for
anyone interested).

        1) Alice choses a random large integer x and sends Bob

                X = g**x mod n

        2) Bob choses a random large integer y and sends Alice

                Y = g**y mod n

        3) Alice computes

                k = Y**x mod n

        4) Bob computes

                k' = X**y mod n

        With a little algebraic manipulation, you find that k' == k.  That
is based on:

                k = Y**x mod n
                  = (g**y mod n) ** x mod n
                  = (g**y)**x mod n
                  = (g**(y*x)) mod n
                  = (g**(x*y)) mod n
                  = (g**x)**y mod n
                  = (g**x mod n) ** y mod n
                  = X**y mod n
                  = k'

        So Alice and Bob now have the same number k.  At this point,
neither Alice nor Bob have any further use for x or y and may discard
them.

        No one listening on the channel can compute that value.  They only
know n, g, X, and Y.  Unless they can compute the discrete logarithm (and
here I'm almost quoting verbatum from Schneier) and recover x or y, they
do not solve the problem.  So, k is the secret key that both Alice and
Bob computed independently.

        So, unless you have a solution to the discrete logarithm problem
(which is AFAAK is intractible) and can compute y given g, n, and (g**y mod n)
you can listen to the complete and total session key negotiation (even
after any public key authentication with the servers public and private
keys) and be left with insufficient information by which to compute the
session key.

        The key (figuratively and literally) in perfect forward secrecy
is that you can apply this, in a compromised channel, to compute your
next ephemeral session key and anyone listening in can not compute the
next session key for the next period.  Since x and y are different
for the next session key, even knowing the old values of x and y will
not reveal the new session key to you.  This might not be really important
for https web pages, which are relatively static and short lived sessions,
but would be of VITAL importance to SSL based persistant tunnels and other
SSL based VPNs which are becoming real popular lately.

        IAC, actually, in my lines of algebra, above, I did pulled two of
those "the obvious next step then is..." type steps.  The steps are not
obvious, but, as it so happens, I can formally prove them mathematically
or point you to the proofs, if you so desire.  They're simple enough.  They
just take a little thought to spot (and NOT assume "of course") and only a
little more thought to reach "Ah ha, of course" realization.  :-)

        Now, tell me how, from the private RSA key of the certificate, do
you get either x or y so you can compute k = g**(x*y) mod n.  Private
RSA keys are not even, in and of themselves, necessarily prime numbers
( ed == 1 mod (p-1)(q-1) ) even though they are derived from prime numbers
(p and q are prime but p-1 and q-1 are even so what is the inverse modulo of
something *4).  Soooo....  Show me how you get from "1 mod (p-1)(q-1)"
to "y".  Show me the math.  If you have g and n from the certificate
and g**x mod n from the client side of the exchange, how do you get
"y" to complete the calculation of g**(x*y) mod n ?  Where did "y"
come from.  It's not the server's private key.  It's a temporary
random value computed on a session by session basis.

        openssl-0.9.7d/crypto/dh/dh_key.c around line 222.

===
        if (generate_new_key)
                {
                l = dh->length ? dh->length : BN_num_bits(dh->p)-1; /* secret exponent length */
                if (!BN_rand(priv_key, l, 0, 0)) goto err;
> NOTE HERE     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                }
        if (!dh->meth->bn_mod_exp(dh, pub_key, dh->g, priv_key,dh->p,ctx,mont))
                goto err;
===

        It's rather difficult to "escrow" either x or y since they
are large primes chosen at random for each connection and not saved
anywhere.  How are you obtaining x or y?  They are never even stored
on disk on the server (with the possible exception of rare cases of
swapping).  How did you get that value from "dh->priv_key" in the dh_st
structure back to your sniffer???  THIS is the miracle I want explained.

        Also, x and y are not keys.  They are merely temporary large
primes used in the key negotiation and discarded after k is computed.
They are never used again.  Ok, ok, OpenSSL stores the large prime in
a data structure element they call, "priv_key" but it's never stored
to disk nor loaded from disk and it's not really a key, per se.

        Now, lets try it again.  Show me the math.  This is the TAMO
of which I spoke.  The D-H exponents are not derived from the private
RSA key of the server.  How do you derive ether of the D-H exponents
(obviously you only need one side if you have the advertised exchange
component - I won't call it a public key - from the other side).

        OTOH...  IF you are NOT talking about the private RSA key
associated the server's certificate but are talking about "y" (the
D-H exponent on the servers side) and calling it a private key, then
fine, I'll buy that.  How are you obtaining that exponent.  It's never
stored on disk and it's merely an ephemeral large prime that changes with
each and every connection.  

        Let me elucidate just WHY this is so serious and better be wrong.
If you are referring to the server's static long-term RSA private key,
then one can infer that an attacker could sniff traffic off the wire and
LATER compromise the server and go back and decrypt all the traffic that
he had previously sniffed (he still has all the same data that he would
have if he were doing what you claim to be doing).  That leaves all SSL
communications traffic and all SSL VPN's vulnerable to FUTURE compromise
of a private key on either side of the communications channel?  This does
NOT sound reasonable to me.  Consider the implications and consequences
of that for SSL based VPNs!

        Tell you what...  I've got a few spare IP addresses to throw
about.  I can set up a secure web server and certs and generate some
traffic to it.  I can then provide you with the private key from the
server (no password) and the certificate file and the complete tcpdump of
all the traffic to and from that IP address.  You can then post back to
this list what the clear text traffic was.  That would settle the issue,
now wouldn't it?  Up for a challenge?

        Mike
-- 
 Michael H. Warfield    |  (770) 985-6132   |  mhw () WittsEnd com
  /\/\|=mhw=|\/\/       |  (678) 463-0932   |  http://www.wittsend.com/mhw/
  NIC whois:  MHW9      |  An optimist believes we live in the best of all
 PGP Key: 0xDF1DD471    |  possible worlds.  A pessimist is sure of it!

Attachment: _bin
Description: