COMSEC: August 2008 Archives


August 20, 2008

Some colleagues (Hovav Shacham, Brendan Enright, Scott Yikel, Stefan Savage) and I have been tracking the aftermath of the Debian OpenSSL PRNG bug (see Hovav's Work-In-Progress presentation at USENIX WIP here). One of the questions that comes up is what you can do with this Here's what's obvious (I'm talking about SSL only below):
  • If the server key was generated with the weak PRNG, you can guess the server key and:
    • Impersonate the server.
    • Passively decode traffic encrypted with static RSA (which a lot of traffic is). This doesn't help with ephemeral Diffie-Hellman (DHE).
  • If the server key is strong but the server has a weak PRNG:
    • If the server has a DSA private key, you can recover it. This isn't much of an issue for SSL but SSH does use DSA reasonably often.
    • This doesn't directly allow you to recover traffic in static RSA mode. The reason for this is that in static RSA mode, the client generates the only secret data (the PreMaster Secret).
  • If the client stack is insecure, then you could in principle guess the client's random values. However, none of the major browsers use OpenSSL, so this is probably limited to non-browser clients.

But this raises the interesting question: can you passively attack DHE mode? In this mode, the server generates a fresh DH key for each transaction. Knowing the server's long-term private key doesn't help here— that just lets you impersonate the server. So, the implementation used to generate the long-term key doesn't matter. However, unlike RSA DHE requires the server to generate secret random values, so if the server is running a broken version, this may give us a way in.

We're not the only ones to think along these lines: along these lines: Luciano Bello describes a partial attack and has posted a patch to Wireshark to attack DHE connections:

If an eavesdropper can explore the complete private key space (the all possible numbers for Xc or Xs), 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.

Bello demonstrates attacking a connection between a broken client and a decent server. However, the attack as described doesn't work with secure clients (which, as I said, is pretty much any browser) and broken non-toy Web servers (the situation is different for non-Web servers (e.g., IMAP and POP servers which run out of inetd): even if the server's PRNG is broken, there isn't a fixed-size list of keys it generates.

To understand why, you need to understand the vulnerability better. Effectively, the vulnerability stopped any invocations of RAND_seed() from mixing data into the PRNG. The only time new seed data gets mixed in is when you get new randomness values via RAND_bytes(). Each time you call RAND_bytes() the current process ID gets mixed into the PRNG. So, for a given PID and a given sequence of invocations of RAND_bytes(), you always get the same string of random values. These values are (statistically) unique, but predictable: you can say "the nth value will always be one of the following 2^15 values depending on the PID". However, it should be clear that even for a given PID, you can generate an arbitrary (well, almost) number of distinct values. So, if you had a process which generated a million DH keys in sequence, they'd all be different. Unfortunately for Bello's attack, this is exactly how many real Web servers work. For instance, Apache w/ Mod_SSL forks off a bunch of long-lived server processes which each handle many requests. Bello's attack would potentially work on the first connection, but the second connection would not be on the key list. You need another 2^15 values to handle the second connection. We've confirmed this by setting up a server, connecting to it, and pulling out more than 2^15 distinct public keys. So, you need to do something more complicated.

What follows is our initial analysis of Apache with Mod_SSL, which we're currently working on confirming. The details may not be quite right, but I suspect the general contours are.

With Apache and Mod_SSL it turns out that RAND_bytes() gets called in the parent process before it forks off the subprocesses, so each subprocess has both the parent process and the subprocess PIDs mixed in. So, you have 2^30 distinct PID combinations and therefore random value streams to deal with. In general, however, since the parent process forks off an initial set of children immediately and children aren't killed or started that often, the entropy is probably a lot less than 2^30, and even 2^30 is still searchable if you've got even modest computer power.

So, if you get to observe the server from the time of startup, you're in fine shape. As soon as you observe a connection, you check your table of known keys (basically a bigger version of Bello's table that takes into account both parent and child PIDs). [Actually, you can save some compute time by building a table of ServerRandom values, which saves you doing the modular exponentiation to compute the public key for a given private key.] That tells you what the PID pair of the server process you're observing is, and of course it's current state. You've got the private key so you can decrypt the connection. To handle the next connection to that server process, you roll the PRNG forward to compute the next expected key. When the next connection comes in, you repeat this process, so at any given time you know the next value for each active PID pair.

If you're not lucky enough to see the server from the time of startup, then life gets more complicated, since you don't know where in its random number stream each server process is. So, you would need to try candidate numbers of connections. Unfortunately, there's another complicating factor: TLS handshakes with Diffie-Hellman and RSA key exchanges involve different patterns of random values: the DH exchange involves an extra 128-byte random value for the Xs (the DH private key) No problem you say, we'll just compute reasonably sized sections of the random value stream and look for matches within the probable zone. Unfortunately, this doesn't look like it's going to work. As I said earlier, each time you invoke RAND_bytes() the PID gets mixed into the PRNG. In other words: RAND_bytes(128); RAND_bytes(32); does not produce the same 160 bytes as RAND_bytes(32); RAND_bytes(128);. This means that every connection introduces one bit of entropy: whether DHE or RSA was used. If you're not observing these connections, this entropy quickly adds up and it becomes impractical to search the space. It's possible that there's some analytic attack on the PRNG that would let you reduce this search space, but nothing popped out at us on casual inspection. This suggests that if you have a server which only does DHE, you can attack individual connections, but if it does both DHE and RSA, you need to observe all the connections from the server to make sure you know the DHE/RSA pattern.

I should mention one more issue: OpenSSL uses a random blinding value to stop remote timing attacks on static RSA. If you can predict the blinding value, then it may be possible to mount a timing attack on the static RSA key, even if it was generated with a strong PRNG. We're still looking into this as well.

As I said at the beginning all this is preliminary and only partly confirmed. We're hoping to have definitive results sometime in the next few weeks and be publishing soon after that.

UPDATE: Fixed Luciano's name to be "Luciano" from "Lucian". Also, I should add that the Wireshark work was done by Paolo Abeni and Maximiliano Bertacchini as well as Luciano Bello.


August 15, 2008

At long last, TLS 1.2 has been published:

1.2.  Major Differences from TLS 1.1

   This document is a revision of the TLS 1.1 [TLS1.1] protocol which
   contains improved flexibility, particularly for negotiation of
   cryptographic algorithms.  The major changes are:

   -  The MD5/SHA-1 combination in the pseudorandom function (PRF) has
      been replaced with cipher-suite-specified PRFs.  All cipher suites
      in this document use P_SHA256.

   -  The MD5/SHA-1 combination in the digitally-signed element has been
      replaced with a single hash.  Signed elements now include a field
      that explicitly specifies the hash algorithm used.

   -  Substantial cleanup to the client's and server's ability to
      specify which hash and signature algorithms they will accept.
      Note that this also relaxes some of the constraints on signature
      and hash algorithms from previous versions of TLS.

   -  Addition of support for authenticated encryption with additional
      data modes.

   -  TLS Extensions definition and AES Cipher Suites were merged in
      from external [TLSEXT] and [TLSAES].

   -  Tighter checking of EncryptedPreMasterSecret version numbers.

   -  Tightened up a number of requirements.

   -  Verify_data length now depends on the cipher suite (default is
      still 12).

   -  Cleaned up description of Bleichenbacher/Klima attack defenses.

   -  Alerts MUST now be sent in many cases.

   -  After a certificate_request, if no certificates are available,
      clients now MUST send an empty certificate list.

   -  TLS_RSA_WITH_AES_128_CBC_SHA is now the mandatory to implement
      cipher suite.

   -  Added HMAC-SHA256 cipher suites.

   -  Removed IDEA and DES cipher suites.  They are now deprecated and
      will be documented in a separate document.

   -  Support for the SSLv2 backward-compatible hello is now a MAY, not
      a SHOULD, with sending it a SHOULD NOT.  Support will probably
      become a SHOULD NOT in the future.

   -  Added limited "fall-through" to the presentation language to allow
      multiple case arms to have the same encoding.

   -  Added an Implementation Pitfalls sections

   -  The usual clarifications and editorial work.

V-T day!


August 13, 2008

In today's Threat Level, Ryan Singel quotes a bunch of DNS types complaining about how USG isn't signing the DNS root (sorry for the long blockquote, but the context is important):
Those extensions cryptographically sign DNS records, ensuring their authenticity like a wax seal on an letter. The push for DNSSEC has been ramping up over the last few years, with four regions -- including Sweden (.SE) and Puerto Rico (.PR) -- already securing their own domains with DNSSEC. Four of the largest top-level domains -- .org, .gov, .uk and .mil, are not far behind.

But because DNS servers work in a giant hierarchy, deploying DNSSEC successfully also requires having someone trustworthy sign the so-called "root file" with a public-private key. Otherwise, an attacker can undermine the entire system at the root level, like cutting down a tree at the trunk. That's where the politics comes in. The DNS root is controlled by the Commerce Department's NTIA, which thus far has refused to implement DNSSEC.

The NTIA brokers the contracts that divide the governance and top-level operations of the internet between the nonprofit ICANN and the for-profit VeriSign, which also runs the .com domain.

"They're the only department of the government that isn't on board with securing the Domain Name System, and unfortunately, they're also the ones who Commerce deputized to oversee ICANN," Woodcock said.

"The biggest difference is that once the root is signed and the public key is out, it will be put in every operating system and will be on all CDs from Apple, Microsoft, SUSE, Freebsd, etc," says Russ Mundy, principal networking scientist at Sparta, Inc, which has been developing open-source DNSSEC tools for years with government funding, He says the top-level key is "the only one you have to have, to go down the tree."


"We would want to bring the editing, creation and signing of the root zone file here," to IANA, Lamb said, noting that VeriSign would likely still control distribution of the file to the root servers, and there would be a public consultation process that the change was right for the net.

But changing that system could be perceived as reducing U.S. control over the net -- a touchy geopolitical issue. ICANN is often considered by Washington politicians to be akin to the United Nations, and its push to control the root-zone file could push the U.S. to give more control to VeriSign, experts say.


Woodcock isn't buying the assurances of NTIA that it is simply moving deliberatively.

"If the root isn't signed, then no amount of work that responsible individuals and companies do to protect their domains will be effective," Woodcock said. "You have to follow the chain of signatures down from the root to the top-level domain to the user's domain. If all three pieces aren't there, the user isn't protected."

Without getting into how important/useful DNSSEC is (see Tom Ptacek's quite negative assessment for a contrary opinion), I'm having some trouble understanding the arguments on offer here.

It's true that the system is arranged in a hierarchy and that if the root were signed that would be nice, but as far as I know that's not at all necessary for DNSSEC to be useful. As long as the TLD operators (.com, .org, .net, etc.) sign their zones, than it's quite possible to have a secure system. All that needs to happen is that someone publishes a list of the public keys for each root zone and that list gets integrated into the resolvers. There's plenty of precedent for this: when certificate systems were first designed, the concept was that there would be a single root CA and that all other CAs would be certified by the root CA. This isn't how things actually worked out, though. Instead there were a bunch of different CAs and their public keys got built into browsers, operating systems etc. There are order 100 such CAs in your average browser, so it's not at all like 300 signing keys would necessarily be infeasible to distribute with resolvers.

In some respects, the situation with DNS is superior because each signing key would be scoped. So, for instance, the key for .com couldn't be used for .org. This is different than current PKI systems where any of those 100 or so CAs can sign any hostname, so a compromise of any of those CAs is quite serious. By contrast, if you're a .com customer, you don't need to worry so much about the security of .zw unless you happen to do a lot of business with sites in Zimbabwe.

With that in mind, if the root were to be signed tomorrow, it's not like it would be tremendously useful unless the individual TLS operators start signing their zones. It sounds like some of them are starting to, but at least from my perspective, this seems rather more important than the root. Now, it's true that having the root signed might have some sort of PR impact in terms of incentivizing the TLS operators, but technically, I don't see that it makes that much of a difference. The primary advantage is that it wouldn't be necessary to distribute a file full of individual zone keys, but that doesn't really seem to be the primary obstacle to DNSSEC deployment/usefulness, and given how fraught the political issues around signing the root are, it seems worth thinking about how we can make progresss without it.

UPDATE: I should mention that another way in which TLD keys are simpler than CA keys is that because of this problem where any CA can sign any name the browser vendors have to have a fairly complicated vetting process to decide whether a given CA follows appropriate practices and can be trusted. But because the TLD registries are already responsible for the zones they would be signing and can't sign names outside their zones, it's relatively clear who should and shouldn't be included on the list.


August 9, 2008

Some MIT students broke the fare card system used by the Massachusetts Bay Transit Authority (slides here) and were scheduled to present at DEFCON. MBTA responded by seeking (and obtaining) a temporary restraining order forbidding them from disclosing "for ten days any information that could be used by others to get free subway rides." [*]. Unfortunately for the MBTA, the presentations had already been distributed on CDROM to DEFCON attendees, so this didn't have quite the impact one might have wanted. Plus the MIT Tech published a copy of the slides, so the information is pretty much out there now. Some thoughts:

  • Attempts to suppress this sort of information rarely work well. That's especially true in this case because the best attack in terms of cost/benefit ratio is also the obvious attack: making duplicates of the card magstripes to mount a replay attack. As soon as you know this is possible—and something that simple is hard to hide—then the game is over.
  • According to this Wired article the researchers didn't notify the MbtA and refused to give them details of the vulnerabilities they found:
    On August 5th, the court documents reveal, a detective with the transit police and an FBI agent met with the MIT students, Rivest, and an MIT lawyer to discuss their concerns and inquire about what the students would disclose in their talk. But the students would not provide the MBTA with a copy of the materials they planned to present in their talk or information about the security flaws they found in the transit system.

    I'd be interested in hearing more about their reasons for choosing not to reveal the information. Is it just that they didn't trust the MBTA?

  • There's sort of a collective action problem here. If organizations respond to notifications of security vulnerabilities by trying to suppress them, researchers are likely to respond by simply publishing all the details unilaterally so there's no possibility of suppression. So, while it may be MBTA's best strategy to try to suppress this information (and I'm not saying it is (see above), but they clearly think it is), it is likely to lead to a regime in which organizations don't get any warning before disclosure, which doesn't seem optimal.

Of course, this is a ritual that's happened at DefCon and Black Hat before, so it wasn't exactly unexpected. Still, you'd think that organizations would get smarter about not trying to suppress stuff once it's already too late.


August 4, 2008

Peter Saint-Andre recently suggested that we add a "Short Authentication String" (SAS) mode to TLS. SAS is only one solution to a not too uncommon problem: preventing man-in-the-middle attacks on public key protocols without the use of a third-party authentication system such as certificates or Kerberos. The general assumption is that you have some low-bandwidth, non-machine readable, trusted side channel (e.g., telephone) 1 that isn't good enough to do a real key exchange but that you want to use to bootstrap your way to a secure channel. You only need to do this once: after the first time you can have your software memorize the peer's public key or some other keying material and use that to provide continuity.

I'm aware of three major techniques here: fingerprints, password authenticated key agreement/exchange, and short authentication strings.

Fingerprints are probably the best known technique; they're what's used by SSH. You compute a message digest of your public key (or your self-signed certificate in DTLS-SRTP) and then communicate it to the other party over the trusted channel. Then when you do the key exchange over the untrusted channel, each side compares the other side's fingerprint to the key they presented. If they match, you're golden. If not, you may have been subject to a man-in-the-middle attack (or something else has gone wrong). The advantage of this technique is that you can compute a single static fingerprint and use it all the time, and the fingerprint can be public (this is what makes certificate systems work after all). Another advantage is that it's already compatible with TLS without any changes to the protocol. The disadvantage is that the fingerprint has to be comparatively long in order to prevent exhaustive search attacks on your public key where the attacker generates candidate private keys until they find one that has the right fingerprint. The complexity of this attack is dictated by the size of the fingerprint, so if you want 64 bits of security (probably the practical minimum), you need a 64 bit fingerprint, which means you're reading 16 hex digits over the phone, which starts to get into the inconvenient range.

Another approach is a password-authenticated key exchange (PAKE) system like EKE or SRP. These systems let you securely bootstrap a low-entropy secret password up to a secure channel [I'm not going to explain the crypto rocket science here] in a way that isn't subject to offline dictionary attacks; the attacker needs to form a new connection to one of the sides for each password guess it wants to verify. The big advantage of a scheme like this is that the password can be short—32-bits is probably plenty. The disadvantage is that you can't use a single password, you need a different one for each person you are trying to authenticate with. Otherwise one counterparty can impersonate the other. Again, this is compatible with TLS as-is, since TLS provides an SRP cipher suite.

Finally, there are SAS schemes such as that described by Vaudenay. The idea here is that the key agremeent protocol lets the parties jointly compute some value which they can then read over the secure channel. You need to take some care doing this because the protocol needs to stop an attacker from forcing the SAS to specific values, but there are well-known techniques for that (again, see the Vaudenay paper). One problem with schemes like this is that you can't exchange the SAS over the trusted channel until after you've done the key exchange, whereas with the other two schemes you can exchange the key in advance—though you don't have to with the fingerprint scheme and even with the SRP scheme there are ways to do it afterwards [technical note: do your standard key exchange with self-signed certs, then rehandshake with SRP over the other channel when you want to verify the connection and then pass a fingerprint over the SRP-established channel.].

None of these schemes is perfect. Optimally you'd be able to have a short, public, static authenticator, but I'm not not aware of any such system, so you need to figure out which compromise is best for your environment.

1. ZRTP carries the SAS in the established audio channel trusting voice recognition to provide a secure channel. There are some reasons why I don't think this will work well, but they're orthogonal to what I'm talking about here.