Exploiting DSA-1571: How to break PFS in SSL with EDH

The following paragraphs assume that you're familiar with the Debian OpenSSL Package Random Number Generator Weakness, which was published on May 13th 2008, and described in DSA-1571-1 (CVE-2008-0166).

At this point, all of you probably know and have seen how H D Moore's toys work. Those toys attack SSH public-key authentication using clone keys and online brute force.

Furthermore, many of you know that there are other effects produced by a biased PRNG besides this one.

Strangely, even though I searched, I couldn't find more of these toys exploiting other aspects (update: check Other related works/links). So, I would like to show you a Wireshark patch which attacks Perfect Forward Secrecy (PFS) provided by Ephemeral Diffie Hellman (EDH).

Introduction to EDH

• The server selects a random prime p and a generator g of the field Z*_p (Let's ignore the mathematical properties of these values). So, the components p and g are public.
  
• The server picks a secret random number X_s and calculates Y_s=g^X_s mod p. Y_s is public and is sent to the client (just like p and g).
  
• The client does something similar, selecting a secret random number X_c and calculating Y_c=g^X_c mod p too. The client makes Y_c public by sending it to the server.
  
• The shared secret s is the public key of the other part to the exponential of the own private number, all in p modulus. That is, for the client s=Y_s^X_cmod p and for the server s=Y_c^X_smod p.
  
• With this shared secret the parties can encrypt all the following messages in a secure way.
  
• In the Ephemeral Diffie Hellman (EDH), the private numbers are ruled out, so s is mathematically secure and nobody can obtain it even having access to one of the parties after the aforementioned handshake.
  

The "exploit"

If an eavesdropper can explore the complete private key space (the all possible numbers for X_c or X_s), he/she will be able to get access to the shared secret. With it all the communication can be deciphered. That's what this patch can do.

A Wireshark with this patch and a list of possible private keys will try to brute force the share secret. If one of the parties is using the vulnerable OpenSSL package the communication is totally insecure and will be decrypted.

• The patch for Wireshark 1.0.2 can be downloaded from here.
  
• Debian packages with the patch applied can be found here.
• Binary for Windows with the patch applied can be found here (Thanks to Ulises Cuñé). MD5: 207b2f2583f80933585d45a4c161026e
• This is a list of all 2¹⁵ possible 64 and 128 bit DH private keys in systems vulnerable to the predictable OpenSSL PRNG described by DSA-1571.
  
• An example of a pcap file can be found here (it was built with a vulnerable client and one of the Moore toys, a hacked getpid by running $ MAGICPID=101 LD_PRELOAD='getpid.so' ./vulnerable-openssl/apps/openssl s_client -connect db.debian.org:443 )

Issues that can be improved

• When the packets are out-of-order the decipher will stop itself.
  
• The brute force attack should run in a background process (and with a progres bar)
  
• Check the length of the keys before trying to brute force them.
  
• The patch also implements the display of public DH parameters in the packet tree. It's incomplete.

Credits

• Debian OpenSSL Predictable PRNG Toys - H D Moore
• SSH tools decipher SSH traffic and retrieve DSA private keys (even from non weak keys) using the OpenSSL/Debian vulnerability - Raphaël Rigo and Yoann Guillot
• SSL Blacklist extension for Firefox - Márton Anka