Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 351 lines (294 sloc) 16.716 kB
c583818 @vincentbernat Article on SSL DoS
authored
1 ---
2 title: SSL computational DoS mitigation
3 keywords: "tls, ssl, dos, thc, denial of service, rsa, cryptography"
4 uuid: 508f723b-adbe-4d05-be2d-bc53b4a9cbb5
5 attachments:
6 "https://github.com/vincentbernat/ssl-dos": "Various tools related to SSL"
ac702dc @vincentbernat Add tags support.
authored
7 tags:
8 - ssl
c583818 @vincentbernat Article on SSL DoS
authored
9 ---
10
11 Some days ago, a hacker group, THC, released a
12 [denial of service tool][thc] for SSL web servers. As stated in its
13 description, the problem is not really new: a complete SSL handshake
14 implies costly cryptographic computations.
15
16 There are two different aspects in the presented attack:
17
18 - The computation cost of an handshake is more important on the
19 server side than on the client side. The advisory explains that a
20 server will require 15 times the processing power of a client. This
21 means a single average workstation could challenge a multi-core
22 high-end server.
f34c03c @vincentbernat Spelling: "allow to" changed to "allow one to"
authored
23 - The use of [SSL renegotiation][rfc5746] allows you to trigger hundreds
c583818 @vincentbernat Article on SSL DoS
authored
24 of handshakes in the same TCP connection. Even a client behind a
25 DSL connection can therefore bomb a server with a lot of
26 renegotiation requests.
27
28 [TOC]
29
30 # Mitigation techniques
31
32 There is no definitive solution to this attack but there exists some
33 workarounds. Since the DoS tool from THC relies heavily on
34 renegotiation, the most obvious one is to disable this mechanism on
35 the server side but we will explore other possibilities.
36
37 ## Disabling SSL renegotiation
38
39 Tackling the second problem seems easy: just disable SSL
40 renegotiation. It is hardly needed: a server can trigger a
41 renegotiation to ask a client to present a certificate but a client
42 usually does not have any reason to trigger one. Because of a
43 [past vulnerability in SSL renegotiation][cve-2009-3555], recent
44 version of _Apache_ and _nginx_ just forbid it, even when the
45 [non-vulnerable version][rfc5746] is available.
46
47 `openssl s_client` can be used to test if SSL renegotiation is really
48 disabled. Sending `R` on an empty line trigger renegotiation. Here is
49 an example where renegotiation is disabled (despite being advertised
50 as supported):
51
52 ::console
53 $ openssl s_client -connect www.luffy.cx:443 -tls1
54 [...]
55 New, TLSv1/SSLv3, Cipher is DHE-RSA-AES256-SHA
56 Server public key is 2048 bit
57 Secure Renegotiation IS supported
58 Compression: zlib compression
59 Expansion: zlib compression
60 [...]
61 R
62 RENEGOTIATING
63 140675659794088:error:1409E0E5:SSL routines:SSL3_WRITE_BYTES:ssl handshake failure:s3_pkt.c:591:
64
65 Disabling renegotation is not trivial with OpenSSL. As an example, I
66 have pushed a [patch to disable renegotiation in _stud_][studreneg],
67 the scalable TLS unwrapping daemon.
68
69 ## Rate limiting SSL handshakes
70
71 Disabling SSL renegotiation on the client side is not always
72 possible. For example, your web server may be too old to propose such
73 an option. Since those renegotiations should not happen often, a
74 workaround is to limit them.
75
76 When the flaw was first advertised, [F5 Networks][f5] provided a way
77 to configure such a limitation with an iRule on their load-balancers. We
78 can do something similar with just Netfilter. We can spot most TCP
79 packets triggering such a renegotiation by looking for encrypted TLS
80 handshake record. They may happen in a regular handshake but in this
81 case, they usually are not at the beginning of the TCP payload. There
82 is no field saying if a TLS record is encrypted or not (TLS is
83 stateful for this purpose). Therefore, we have to use some
84 heuristics. If the handshake type is unknown, we assume that this is
85 an encrypted record. Moreover, renegotiation requests are usually
86 encapsulated in a TCP packet flagged with "push".
87
88 ::sh
89 # Access to TCP payload (if not fragmented)
90 payload="0 >> 22 & 0x3C @ 12 >> 26 & 0x3C @"
91 iptables -A LIMIT_RENEGOCIATION \
92 -p tcp --dport 443 \
93 --tcp-flags SYN,FIN,RST,PSH PSH \
94 -m u32 \
95 --u32 "$payload 0 >> 8 = 0x160300:0x160303 && $payload 2 & 0xFF = 3:10,17:19,21:255" \
96 -m hashlimit \
97 --hashlimit-above 5/minute --hashlimit-burst 3 \
98 --hashlimit-mode srcip --hashlimit-name ssl-reneg \
99 -j DROP
100
101 The use of `u32` match is a bit difficult to read. The
102 [manual page][iptables] gives some insightful examples. `$payload`
f34c03c @vincentbernat Spelling: "allow to" changed to "allow one to"
authored
103 allows us to seek for the TCP payload. It only works if there is no
c583818 @vincentbernat Article on SSL DoS
authored
104 fragmentation. Then, we check if we have a handshake (`0x16`) and if
105 we recognise TLS version (`0x0300`, `0x0301`, `0x0302` or
106 `0x0303`). At least, we check if the handshake type is not a known
107 value.
108
109 There is a risk of false positives but since we use `hashlimit`, we
110 should be safe. This is not a bullet proof solution: TCP fragmentation
111 would allow an attacker to evade detection. Another equivalent
112 solution would be to use `CONNMARK` to record the fact the initial
113 handshake has been done and forbid any subsequent handshakes.
114
115 If you happen to disable SSL renegociation, you can still use some
116 Netfilter rule to limit the number of SSL handshakes by limiting the
117 number of TCP connections from one IP:
118
119 ::sh
120 iptables -A LIMIT_SSL \
121 -p tcp --dport 443 \
122 --syn -m state --state NEW \
123 -m hashlimit \
124 --hashlimit-above 120/minute --hashlimit-burst 20 \
125 --hashlimit-mode srcip --hashlimit-name ssl-conn \
126 -j DROP
127
128 Your servers will still be vulnerable to a large botnet but if there
129 is only a handful of source IP, this rule will work just fine[^a].
130
131 [^a]: However, since this rule relies on source IP to identify the
132 attacker, the risk of false positive is real. You can slow down
133 legitimate proxies, networks NATed behind a single IP, mobile
134 users sharing an IP address or people behind a CGN.
135
136 I have made all those solutions available in a
137 [single file][netfilter].
138
139 ## Increasing server-side power processing
140
141 SSL can easily be scaled up and out. Since
142 [SSL performance increases linearly with the number of cores][sslbench1],
143 scaling up can be done by throwing in more CPU or more cores per
144 CPU. Adding expensive SSL accelerators would also do the
145 trick. Scaling out is also relatively easy but you should care about
146 [SSL session resume][sslresume].
147
148 ## Putting more work on the client side
149
150 In their presentation of the [denial of service tool][thc], THC explains:
151
152 > Establishing a secure SSL connection requires 15× more processing
153 > power on the server than on the client.
154
155 I don't know where this figure comes from. To check it, I built a
156 [small tool to measure CPU time of a client and a server doing 1000 handshakes][server-vs-client]
157 with various parameters (cipher suites and key sizes). The results are
158 summarized on the following plot:
159
160 ![Plot to compare computational power required by servers and clients][s1]
e240866 @vincentbernat Move some SSL related image into the correct folder.
authored
161 [s1]: [[!!images/benchs-ssl/server-vs-client.png]] "Comparison of computational power needed by servers and clients"
c583818 @vincentbernat Article on SSL DoS
authored
162
51e1a37 @vincentbernat Mention of "Forward secrecy for Google HTTPS".
authored
163 **UPDATED:** Adam Langley announced
164 [Google HTTPS sites now support forward secrecy][ecdh] and
165 `ECDHE-RSA-RC4-SHA` is now the preferred cipher suite thanks to fast,
166 constant-time implementations of elliptic curves P-224, P-256 and
167 P-521 in OpenSSL. The tests above did not use those implementations.
168
c583818 @vincentbernat Article on SSL DoS
authored
169 For example, with 2048bit RSA certificates and a cipher suite like
170 `AES256-SHA`, the server needs 6 times more CPU power than the
171 client. However, if we use `DHE-RSA-AES256-SHA` instead, the server
172 needs 34% less CPU power. The most efficient cipher suite from the
173 server point of view seems to be something like `DHE-DSS-AES256-SHA`
174 where the server needs half the power of the client.
175
51e1a37 @vincentbernat Mention of "Forward secrecy for Google HTTPS".
authored
176 However, you can't really uses only those shiny cipher suites:
c583818 @vincentbernat Article on SSL DoS
authored
177
178 1. Some browsers do not support them: they are limited to RSA cipher
179 suites[^1].
180 2. Using them will increase your regular load a lot. Your servers may
181 collapse with just legitimate traffic.
182 3. They are expensive for some mobile clients: they need more memory,
183 more processing power and will drain battery faster.
184
185 [^1]: Cipher suites supported by all browsers are `RC4-MD5`, `RC4-SHA`
d115794 @vincentbernat SSL DoS: corrections.
authored
186 and `3DES-SHA`. <del>Support for `DHE-DSS-AES256-SHA` requires TLS
187 1.2</del> <del>(not supported by any browser).</del>
c583818 @vincentbernat Article on SSL DoS
authored
188
189 Let's dig a bit more on why the server needs more computational power
190 in the case of RSA. Here is a SSL handshake when using a cipher suite
191 like `AES256-SHA`:
192
193 ![SSL full handshake][s2]
194 [s2]: [[!!images/benchs-ssl/ssl-handshake.png]] "Full SSL handshake"
195
196 When sending the _Client Key Exchange_ message, the client will
197 **encrypt** TLS version and 46 random bytes with the public key of the
198 certificate sent by the server in its _Certificate_ message. The
199 server will have to **decrypt** this message with her private
200 key. Those are the two most expensive operations in the
201 handshake. Encryption and decryption are done with [RSA][rsa] (because
202 of the selected cipher suite). To understand why decryption is more
203 expensive than encryption, let me explain how RSA works.
204
205 First, the server needs a public and a private key. Here are the main
206 steps to generate them:
207
208 1. Pick two random distinct [prime numbers][prime] ·p· and ·q·, each
209 roughly the same size.
210 2. Compute ·n=pq·. It is the _modulus_.
211 3. Compute ·\\varphi(n)=(p-1)(q-1)·.
212 4. Choose an integer ·e· such that ·1<e<\\varphi(nand
213 ·\\gcd(\\varphi(n),e) = 1· (i.e. ·e· and ·\\varphi(nare
214 [coprime][coprime]). It is the _public exponent_.
215 5. Compute ·d=e^{-1}\\mod\\varphi(n)·. It is the _private key
216 exponent_.
217
218 The **public key** is ·(n,ewhile the **private key** is ·(n,d)·. A
219 message to be encrypted is first turned into an integer ·m<n· (with
220 some appropriate padding). It is then encrypted to a ciphered message
221 ·c· with the public key and should only be decrypted with the private
222 key:
223
224 - ·c=m^e\\mod n·  (encryption)
225 - ·m=c^d\\mod n·  (decryption)
226
227 So, why is decryption more expensive? In fact, the key pair is not
228 really generated like I said above. Usually, ·e· is a small fixed
229 prime number with a lot of 0, like 17 (`0x11`) or 65537 (`0x10001`)
230 and ·p· and ·q· are choosen such that ·\\varphi(nis coprime with
231 ·e·. This allows encryption to be fast using
232 [exponentiation by squaring][squaring]. On the other hand, its inverse
233 ·d· is a big number with no special property and therefore,
234 exponentiation is more costly and slow.
235
236 Instead of computing ·d· from ·e·, it is possible to choose ·d· and
237 compute ·e·. We could choose ·d· to be small and coprime with
238 ·\\varphi(nand then compute ·e=d^{-1}\\mod\\varphi(n)· and get
239 blazingly fast decryption. Unfortunately, there are two problems with
240 this:
241
242 - Most SSL implementation expects ·e· to be a 32bit integer.
243 - If ·d· is too small (less than one-quarter as many bits as the
244 modulus ·n·), it can be
245 [computed efficiently from the public key][wiener].
246
247 Therefore, we cannot use a small private exponent. The best we can do
248 is to choose the public exponent to be ·e'=4294967291· (the biggest
249 prime 32bit number and it contains only one 0). However, there is no
250 change as you can see on our comparative plot.
251
252 To summarize, no real solution here. You need to allow RSA cipher
253 suites and there is no way to improve the computational ratio between
254 the server and the client with such a cipher suite.
255
256 # Things get worse
257
258 Shortly after the release the [denial of service tool][thc], Eric
259 Rescorla[^0] published a
260 [good analysis on the impact of such a tool][educated]. He asks
261 himself about the efficiency to use renegotiation for such an attack:
262
263 > What you should be asking at this point is whether a computational DoS
264 > attack based on renegotiation is any better for the attacker than a
265 > computational DoS attack based on multiple connections. The way we
266 > measure this is by the ratio of the work the attacker has to do to the
267 > work that the server has to do. I've never seen any actual
268 > measurements here (and the THC guys don't present any), but some back
269 > of the envelope calculations suggest that the difference is small.
270 >
271 > If I want to mount the old, multiple connection attack, I need to
272 > incur the following costs:
273 >
274 > 1. Do the TCP handshake (3 packets)
275 > 2. Send the SSL/TLS _ClientHello_ (1 packet). This can be a canned message.
276 > 3. Send the SSL/TLS _ClientKeyExchange_, _ChangeCipherSpec_,
277 > _Finished_ messages (1 packet). These can also be canned.
278 >
279 > Note that I don't need to parse any SSL/TLS messages from the server,
280 > and I don't need to do any cryptography. I'm just going to send the
281 > server junk anyway, so I can (for instance) send the same bogus
282 > _ClientKeyExchange_ and _Finished_ every time. The server can't find
283 > out that they are bogus until it's done the expensive part. So,
284 > roughly speaking, this attack consists of sending a bunch of canned
285 > packets in order to force the server to do one RSA decryption.
286
287 [^0]: Eric is one of the author of several RFC related to TLS. He knows his stuff.
288
289 I have written a
290 [quick proof of concept of such a tool][brute-shake]. To avoid any
291 abuse, it will only work if the server supports `NULL-MD5`
292 cipher suite. No sane server in the wild will support such a
293 cipher. You need to configure your web server to support it before
294 using this tool.
295
296 While Eric explains that there is no need to parse any SSL/TLS
297 messages, I have found that if the key exchange message is sent before
298 the server send the answer, the connection will be aborted. Therefore,
299 I quickly parse the server's answer to check if I can continue. Eric
300 also says a bogus key exchange message can be sent since the server
301 will have to decrypt it before discovering it is bogus. I have choosen
302 to build a valid key exchange message during the first handshake
303 (using the certificate presented by the server) and replay it on
304 subsequent handshakes because I think the server may dismiss the
305 message before the computation is complete (for example, if the size
306 does not match the size of the certificate).
307
8363b10 @vincentbernat Add mention of ssl squeeze to SSL DoS article
authored
308 **UPDATED:** Michał Trojnara has written [sslsqueeze][sslsqueeze], a
309 similar tool. It uses `libevent2` library and should display better
310 performances than mine. It does not compute a valid key exchange
311 message but ensure the length is correct.
312
c583818 @vincentbernat Article on SSL DoS
authored
313 With such a tool and 2048bit RSA certificate, a server is using 100
314 times more processing power than the client. Unfortunately, this means
315 that most solutions, except rate limiting, exposed on this page
316 may just be ineffective.
317
318 *[DoS]: Denial of service
319 *[SSL]: Secure Socket Layer
320 *[TLS]: Transport Layer Security
321 *[DSL]: Digital Subscriber Line
322 *[RSA]: Rivest Shamir Adleman
323 *[THC]: The Hacker's Choice
324 *[CGN]: Carrier-grade NAT
325 [sslbench1]: [[en/blog/2011-ssl-benchmark.html]] "First round of SSL benchmarks"
326 [sslbench2]: [[en/blog/2011-ssl-benchmark-round2.html]] "Second round of SSL benchmarks"
327 [sslresume]: [[en/blog/2011-ssl-session-reuse-rfc5077.html]] "Speeding up SSL: enabling session reuse"
328 [rsa]: http://en.wikipedia.org/wiki/Rivest_Shamir_Adleman "Article on Wikipedia for RSA"
329 [prime]: http://en.wikipedia.org/wiki/Prime_number "Article on Wikipedia for prime numbers"
330 [coprime]: http://en.wikipedia.org/wiki/Coprime "Article on Wikipedia for coprime numbers"
331 [squaring]: http://en.wikipedia.org/wiki/Exponentiation_by_squaring "Article on Wikipedia for exponentiation by squaring"
332 [wiener]: http://en.wikipedia.org/wiki/Wiener%27s_Attack "Article on Wikipedia for Wiener's attack"
333 [thc]: http://www.thc.org/thc-ssl-dos/ "THC-SSL-DOS tool"
334 [rfc5746]: http://tools.ietf.org/html/rfc5746 "RFC 5746: TLS Renegotiation Indication Extension"
335 [studreneg]: https://github.com/bumptech/stud/pull/47 "CVE-2009-3555 fix for stud"
336 [educated]: http://www.educatedguesswork.org/2011/10/ssltls_and_computational_dos.html "Educated Guesswork: SSL/TLS and Computational DoS"
337 [f5]: http://www.f5.com/ "F5 Networks website"
338 [f5-ssl]: http://devcentral.f5.com/weblogs/david/archive/2011/05/03/ssl-renegotiation-dos-attack-ndash-an-irule-countermeasure.aspx "SSL Renegotiation DOS attack – an iRule Countermeasure"
339 [f5-bigip]: http://www.f5.com/products/hardware/big-ip.html "F5 Big-IP product line"
340 [cve-2009-3555]: http://cve.mitre.org/cgi-bin/cvename.cgi?name=CAN-2009-3555 "CVE-2009-3555"
341 [netfilter]: https://github.com/vincentbernat/ssl-dos/blob/master/iptables.sh "Firewall rules to mitigate SSL DoS"
342 [brute-shake]: https://github.com/vincentbernat/ssl-dos/blob/master/brute-shake.c "Tool to emit massive parallel SSL handshakes"
343 [server-vs-client]: https://github.com/vincentbernat/ssl-dos/blob/master/server-vs-client.c "Tool compare processing power needed by client and server"
344 [iptables]: http://linux.die.net/man/8/iptables "Manual page of iptables(8)"
8363b10 @vincentbernat Add mention of ssl squeeze to SSL DoS article
authored
345 [sslsqueeze]: ftp://ftp.stunnel.org/sslsqueeze/ "sslsqueeze, SSL service load generator"
51e1a37 @vincentbernat Mention of "Forward secrecy for Google HTTPS".
authored
346 [ecdh]: http://www.imperialviolet.org/2011/11/22/forwardsecret.html "Forward secrecy for Google HTTPS"
c583818 @vincentbernat Article on SSL DoS
authored
347
348 {# Local Variables: #}
349 {# mode: markdown #}
350 {# End: #}
Something went wrong with that request. Please try again.