SSL/TLS and Computational DoS

| Comments (4) | COMSEC
Threat Level writes about the release of a denial of service tool for SSL/TLS web servers.
The tool, released by a group called The Hackers Choice, exploits a known flaw in the Secure Socket Layer (SSL) protocol by overwhelming the system with secure connection requests, which quickly consume server resources. SSL is what's used by banks, online e-mail providers and others to secure communications between the website and the user.

The flaw exists in the process called SSL renegotiation, which is used in part to verify a user's browser to a remote server. Sites can still use HTTPS without that renegotiation process turned on, but the researchers say many sites have it on by default.

"We are hoping that the fishy security in SSL does not go unnoticed. The industry should step in to fix the problem so that citizens are safe and secure again. SSL is using an aging method of protecting private data which is complex, unnecessary and not fit for the 21st century," said the researchers in a blog post.

The attack still works on servers that don't have SSL renegotiation enabled, the researchers said, though it takes some modifications and some additional attack machines to bring down the system.

Background
In order to understand what's going on, you need to have some background about SSL/TLS. An SSL/TLS connection has two phases:

  • A handshake phase in which the keys are exchanged
  • A data transfer phase in which the actual data is passed back and forth.

For technical cryptographic reasons which aren't relevent here, the handshake phase is generally much more expensive than the data transfer phase (though not as expensive as people generally think). Moreover, the vast majority of the cost is to the server. Thus, if I'm an attacker and you're a server and I can initiate a lot of handshakes to you, I can force you to do a lot of computations. In large enough quantity, then, this is a computation denial of service attack. This is all very well known. What the attack would look like is that I would set up a client or set of clients which would repeatedly connect to your server, do enough of a handshake to force you to incur computational cost, and disconnect.

What's slightly less well-known is that SSL/TLS includes a feature called "renegotiation", in which either side can ask to do a new handshake on an existing connection. Unsurprisingly, the cost of a new handshake is roughly the same as an initial one. [Technical note: not if you're doing resumption but in this case the client wouldn't offer resumption, since he wants to maximize server cost.] So, what this attack would look like is that instead of opening multiple connections, I'd open a single connection and just renegotiate over and over. As I said, this is slightly less well-known, but it's certainly been known that it's a possibility for some time, but most of the analyses I have seen suggested that it wasn't a major improvement from the attacker's perspective.

The Impact of This Attack
What you should be asking at this point is whether a computational DoS attack based on renegotiation is any better for the attacker than a computational DoS attack based on multiple connections. The way we measure this is by the ratio of the work the attacker has to do to the work that the server has to do. I've never seen any actual measurements here (and the THC guys don't present any), but some back of the envelope calculations suggest that the difference is small.

If I want to mount the old, multiple connection attack, I need to incur the following costs:

  1. Do the TCP handshake (3 packets)
  2. Send the SSL/TLS ClientHello (1 packet). This can be a canned message.
  3. Send the SSL/TLS ClientKeyExchange, ChangeCipherSpec, Finished messages (1 packet). These can also be canned.

Note that I don't need to parse any SSL/TLS messages from the server, and I don't need to do any cryptography. I'm just going to send the server junk anyway, so I can (for instance) send the same bogus ClientKeyExchange and Finished every time. The server can't find out that they are bogus until it's done the expensive part [Technical note: the RSA decryption is the expensive operation.] So, roughly speaking, this attack consists of sending a bunch of canned packets in order to force the server to do one RSA decryption.

Now let's look at the "new" single connection attack based on renegotiation. I need to incur the following costs.

  1. Do the TCP handshake (3 packets) [once per connection.]
  2. Send the SSL/TLS ClientHello (1 packet). This can be a canned message.
  3. Receive the server's messages and parse the server's ServerHello to get the ServerRandom (1-3 packets).
  4. Send the SSL/TLS ClientKeyExchange and ChangeCipherSpec messages (1 packet).
  5. Compute the SSL/TLS PRF to generate the traffic keys.
  6. Send a valid Finished message.
  7. Repeat steps 2-7 as necessary.

The advantage of this variant is that I get to amortize the TCP handshake (which is very cheap). The disadvantage is that I can't just use canned packets. I need to do actual cryptographic computations in order to force the server to do an RSA private key decryption. This is just a bunch of hashes, but it's still not free.

Briefly then, we've taken an attack which was previously limited by network bandwidth and slightly reduced the bandwidth (by a factor of about 2 in packets/sec and less than 10% in number of bytes) at the cost of significantly higher computational effort on the attacker's client machines. Depending on the exact characteristics of your attack machines, this might be better or worse, but it's not exactly a huge improvement in any case.

Another factor to consider is the control discipline on the server. Remember that the point of the exercise is to deny service to legitimate users. It's not uncommon for servers to service each SSL/TLS connection in a single thread. If you're attacking a server that does this, and you use a single connection with renegotiation, then you're putting a lot of load on that one thread; a sane thread scheduler will try to give each thread equivalent amounts of CPU, which means that you don't have a lot of impact on other legitimate users; your thread just falls way behind. By contrast, if you use a lot of connections then you get much better crowding out of legitimate users. On the other hand, if you have some anti-DoS device in front of your server, it might be designed to prevent a lot of connections from the same client, in which case the single connection approach would be more effective. Of course, if single-connection attacks become popular, it's trivial to enhance anti-DoS devices to stop them. [Technical note: SSL/TLS content types are in the clear so renegotiation is easily visible.]

Is this a flaw in SSL/TLS?
Zetter and the THC guys characterize this as a flaw in SSL/TLS. Without offering a general defense of SSL/TLS, this seems overstated at best. First, this isn't really a threat that endangers citizens ability to be "safe and secure". Rather, it's a mechanism for bringing down the Web sites they visit. This isn't to say that there aren't problems in SSL/TLS that would lead to compromise of user's data, but this sort of DoS attack doesn't fall into that category.

Second, computational DoS attacks of this type have been known about for a very long time and in general security protocol designers have made a deliberate choice not to attempt to defend against them. Defenses against computational DoS typically fall into two categories:

  • Force users to demonstrate that they are reachable at their claimed IP address. This prevents "blind" attacks where the attacker can send forged packets and thus makes it easier to track down attackers.
  • Try to impose costs on users so that the ratio of attacker work to defender work is more favorable. (There are a variety of schemes of this type but the general term is "client puzzles").

Because SSL/TLS runs over TCP, it gets the first type of defense automatically. [Technical note: Datagram TLS runs over UDP and so Nagendra Modadugu and I explicitly added a reachability proof mechanism to protect against blind attack.] However, SSL/TLS, like most other Internet security protocols, doesn't do anything to push work onto the client. The general reasoning here is that DoS attackers generally use botnets (i.e., other people's compromised computers) to mount their attacks and therefore they have a very large amount of CPU available to them. This makes it very hard to create a puzzle which creates enough of a challenge to attackers to reduce the attack threat without severely impacting people with low computational resources such as those on mobile devices. Obviously, there is a tradeoff here, but my impression of the history of DoS attacks has been that this sort of CPU-based attack isn't that common and so this has been a generally reasonable design decision.

More generally, defending against computational DoS attacks is a really hard problem; you need to be able to serve large numbers of people you don't really have a relationship with, but it's easy for attackers who control large botnets to pretend to be a lot of legitimate users. All the known defenses are about trying to make it easier to distinguish legitimate users from attackers before you've invested a lot of resources in them, but this turns out to be inherently difficult and we don't have any really good solutions.

UPDATE: Fixed a writing error. Thanks to Joe Hall for pointing this out.

4 Comments

mod_ssl was changed to reject client-initiated renegotiations as the workaround for CVE-2009-3555, and that restriction is still present in current releases of Apache httpd. The reneg-specific part of this so-called "DoS" is hence ineffective against current installs.

I was told that IIS also rejects client-initiated renegotiations, but haven't verified that myself.

The tool as it is provided does unnecessary work, as it performs the real client side processing, including crypto operations.
As such, if the server uses a (EC)DSA key, the load will be reversed, i.e. more work on the client side. This will be balanced by the extra DH operation performed by the server.
If an RSA certificate is used on the server, then the CA could have a big public exponent that will be used by the client to verify the certificate (that's not a property you usually look after, I admit). Public RSA operations can't be accelerated by CRT, so a full 2048 bits modexp will be done on the client side, and only 2 1024 bits ones on the server. Provide a long chain of "big-e RSA key" certificates, and the client will have a lot of work to do, while the server would only have the 2 same 1024 bits modexp (for a 2048 bits key).
The THC-provided tool is suboptimal, at most. Clean canned messages as you described would be much more effective, and easy to compile.

One advantage the renegotiation DoS has is that it requires a little bit more depth of inspection into the data stream in order to mitigate it. Not saying that this is a huge advantage for this type of DoS, only that it could be a significant consideration for some sites.

As defenses have evolved based on historical attack patterns, it would seem likely that there are many sites that are in a much better position to defend against an ordinary TCP SYN or complete three-way TCP connection floods than they are a DoS that only needs a relatively small number of otherwise valid-looking connections.

Now is as good a time as any for sites to revisit their DoS mitigation strategy with the latest attacks in mind. This seems like a case where even the most basic IPS/IDS, load balancers, and SSL offload hardware could amount to a big win.

What's up with their numbers though? Is the server assumed to be running on Atom?

The average server can do 300 handshakes per second. This would require
10-25% of your laptops CPU.

Leave a comment