idnits 2.17.1 draft-pironti-tls-length-hiding-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 7, 2013) is 4097 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 5246 (Obsoleted by RFC 8446) -- Possible downref: Non-RFC (?) normative reference: ref. 'DTLS-ATTACK' -- Possible downref: Non-RFC (?) normative reference: ref. 'LH-PADDING' -- Possible downref: Non-RFC (?) normative reference: ref. 'CBCTIME' -- Possible downref: Non-RFC (?) normative reference: ref. 'COMPLEAK' Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Pironti 3 Internet-Draft INRIA Paris-Rocquencourt 4 Expires: August 11, 2013 N. Mavrogiannopoulos 5 KU Leuven 6 February 7, 2013 8 Length Hiding Padding for the Transport Layer Security Protocol 9 draft-pironti-tls-length-hiding-00 11 Abstract 13 This memo proposes length hiding methods of operation for the TLS 14 protocol. It defines a TLS extension to allow arbitrary amount of 15 padding in any TLS ciphersuite, and it presents guidelines and a 16 reference implementation of record fragmentation and padding so that 17 the length of the exchanged messages is effectively concealed within 18 a given range of lengths. The latter guidelines also apply to the 19 standard TLS padding allowed by the TLS block ciphers. 21 Status of this Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on August 11, 2013. 38 Copyright Notice 40 Copyright (c) 2013 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 57 3. TLS Extension: Extended Record Padding . . . . . . . . . . . . 5 58 3.1. Extension Negotiation . . . . . . . . . . . . . . . . . . 5 59 3.2. Record Payload . . . . . . . . . . . . . . . . . . . . . . 5 60 4. A Length Hiding Mechanism for TLS . . . . . . . . . . . . . . 8 61 4.1. Range Splitting . . . . . . . . . . . . . . . . . . . . . 8 62 4.1.1. Fragmenting Plaintext into Records . . . . . . . . . . 10 63 4.1.2. Adding the Length Hiding Padding . . . . . . . . . . . 11 64 4.1.3. A Length Hiding API . . . . . . . . . . . . . . . . . 11 65 4.2. Applicability . . . . . . . . . . . . . . . . . . . . . . 12 66 5. Security Considerations . . . . . . . . . . . . . . . . . . . 13 67 5.1. Length Hiding with standard TLS block ciphers . . . . . . 13 68 5.2. Length Hiding with extended record padding . . . . . . . . 13 69 5.3. Mitigating Denial of Service . . . . . . . . . . . . . . . 14 70 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 71 7. Normative References . . . . . . . . . . . . . . . . . . . . . 16 72 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 17 74 1. Introduction 76 When using CBC block ciphers, the TLS protocol [RFC5246] provides 77 means to frustrate attacks based on analysis of the length of 78 exchanged messages, by adding extra pad to TLS records. However, the 79 TLS specification does not define a length hiding (LH) method for 80 applications that require it. In fact, current implementations of 81 eager fragmentation strategies or random padding strategies have been 82 showed to be ineffective against this kind of traffic analysis 83 [LH-PADDING]. 85 This document proposes a TLS extension to allow arbitrary amount of 86 padding in any TLS ciphersuite, and in addition it presents 87 guidelines and a reference implementation of record fragmentation and 88 padding so that the length of the exchanged messages is effectively 89 concealed within a range of lengths provided by the user of the TLS 90 record protocol. The latter guidelines also apply to the standard 91 TLS padding allowed by the TLS block ciphers. 93 The proposed extension also eliminates padding oracles (both in 94 errors and timing) that have been plaguing standard TLS block ciphers 95 [CBCTIME] [DTLS-ATTACK] 97 When using standard TLS block cipher padding, the goals of LH for TLS 98 are the following: 100 1. Length-Hiding: use message fragmentation and the allowed extra 101 padding for block ciphers to conceal the real length of the 102 exchanged message within a range of lengths chosen by the user of 103 the TLS record protocol. All messages sent with the same range 104 use the same network bandwidth, regardless of the real size of 105 the message itself. 107 2. Interoperability: an implementation sending length-hidden 108 messages correctly interoperates with non LH-aware 109 implementations of TLS. 111 3. Efficiency: the minimum required amount of extra padding is used, 112 and the minimum number of required fragments is sent. 114 By design, in the standard TLS block cipher mode, only a limited 115 amount of extra padding can be carried with each record fragment, and 116 this can potentially require extra fragmentation for wide ranges. 117 Moreover, no LH can be implemented for stream ciphers. To overcome 118 these limitations, the TLS extension proposed in this document 119 enables efficient LH both for block and stream ciphers (at the 120 partial cost of interoperability, as both parties must implement the 121 extension). 123 2. Terminology 125 This document uses the same notation and terminology used in the TLS 126 Protocol specification [RFC5246]. 128 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 129 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 130 document are to be interpreted as described in [RFC2119]. 132 3. TLS Extension: Extended Record Padding 134 The TLS extended record padding is a variant of the TLS record 135 protocol where every record can be padded up to 2^14 bytes, 136 regardless of the cipher being used. 138 3.1. Extension Negotiation 140 In order to indicate the support of the extended record padding, 141 clients MUST include an extension of type "extended_record_padding" 142 to the extended client hello message. The "extended_record_padding" 143 TLS extension is assigned the value of TDB-BY-IANA from the TLS 144 ExtensionType registry. This value is used as the extension number 145 for the extensions in both the client hello message and the server 146 hello message. The hello extension mechanism is described in 147 [RFC5246]. 149 This extension carries no payload and indicates support for the 150 extended record padding. The "extension_data" field of this 151 extension are of zero length in both the client and the server. 153 The negotiated record padding applies for the duration of the session 154 including session resumption. A client wishing to resume a session 155 where the extended record padding was negotiated SHOULD include the 156 "extended_record_padding" extension in the client hello. 158 3.2. Record Payload 160 The translation of the TLSCompressed structure into TLSCiphertext 161 remains the same as in [RFC5246]. When the cipher is 162 BulkCipherAlgorithm.null, the 'fragment' structure of TLSCiphertext 163 also remains unchanged. That is, for the TLS_NULL_WITH_NULL_NULL 164 ciphersuite and for MAC-only ciphersuites this extension has no 165 effect. For all other ciphersuites, the 'fragment' structure of 166 TLSCiphertext is modified as follows. 168 stream-ciphered struct { 169 opaque pad<0..2^14>; 170 opaque content[TLSCompressed.length]; 171 opaque MAC[SecurityParameters.mac_length]; 172 } GenericStreamCipher; 174 struct { 175 opaque IV[SecurityParameters.record_iv_length]; 176 block-ciphered ciphered struct { 177 opaque pad<0..2^14>; 178 opaque content[TLSCompressed.length]; 179 opaque MAC[CipherSpec.hash_size]; 180 }; 181 } GenericBlockCipher; 183 struct { 184 opaque nonce_explicit[SecurityParameters.record_iv_length]; 185 aead-ciphered struct { 186 opaque pad<0..2^14>; 187 opaque content[TLSCompressed.length]; 188 opaque MAC[CipherSpec.hash_size]; 189 }; 190 } GenericAEADCipher; 192 The padding can be filled with arbitrary data, and it is 193 authenticated as part of the MAC. For block ciphers, the length of 194 the pad MUST be such that the total length (i.e., the pad, the 195 content and the MAC) are a multiple of the block size. 197 For the various ciphers the data are authenticated as follows. 199 Standard Stream Ciphers: 201 MAC(MAC_write_key, seq_num + 202 TLSCompressed.type + 203 TLSCompressed.version + 204 TLSCompressed.length + 205 TLSCiphertext.fragment.GenericStreamCipher.pad + 206 TLSCompressed.fragment); 208 Block Ciphers: 210 MAC(MAC_write_key, seq_num + 211 TLSCompressed.type + 212 TLSCompressed.version + 213 TLSCompressed.length + 214 TLSCiphertext.fragment.GenericBlockCipher.pad + 215 TLSCompressed.fragment); 217 AEAD Ciphers: 219 AEADEncrypted = AEAD-Encrypt(write_key, nonce, 220 pad + plaintext, 221 additional_data); 223 Implementation note: With block and stream ciphers, in order to avoid 224 padding oracles, decryption, MAC verification and payload decoding 225 SHOULD be executed in the following order: 227 1. Decrypt TLSCiphertext.fragment. 229 2. Verify the MAC. 231 3. Split plaintext from pad. 233 4. A Length Hiding Mechanism for TLS 235 In order to send length-hidden messages, a user of a LH-TLS 236 implementation provides the plaintext to be sent together with a 237 range (low,high), meaning that an attacker can at most learn that the 238 real plaintext length is between low and high. 240 The LH mechanism described in the rest of this document applies both 241 to standard TLS block ciphers and the extended record padding of 242 section Section 3. 244 4.1. Range Splitting 246 Not all user-provided ranges can be conveyed in a singe TLS record 247 fragment. A LH-TLS implementation uses a fragmentation algorithm 248 that takes a message with a desired length range (low,high) and 249 breaks it up into n suitably sized ranges each of which can be 250 conveyed in a single TLS record fragment. The Range and 251 FragmentRange are defined as follows. 253 struct { 254 uint32 low; 255 unit32 high; 256 } Range; 258 struct { 259 uint16 low; 260 unit16 high; 261 } FragmentRange; 263 If the difference between Range.high and Range.low is greater than 264 the maximum allowed padding size for a single fragment, or if their 265 value is greater than the maximum fragment size, the given range must 266 be split into multiple smaller FragmentRange structures each of which 267 can be conveyed into a single TLS record. 269 Range.low MUST be less or equal to Range.high. Declaring Range.low 270 and Range.high as uint32 allows to send messages of length up to 271 2^32: TLS implementations MAY use larger data types for these fields. 272 A FragmentRange, that can be conveyed in one record, MUST have both 273 values of FragmentRange.low and FragmentRange.high not exceeding 2^14 274 (or the negotiated maximum value of TLSPlaintext.length [RFC6066]). 276 A TLS implementation applies the range splitting algorithm starting 277 from the user-provided Range structure, resulting into a sequence of 278 FragmentRange structures. For each FragmentRange structure, it 279 transmits a TLS record adhering into the limits of the corresponding 280 FragmentRange. When a block cipher is in use, on each record the 281 implementation computes n bytes of minimal padding (the minimum 282 amount of padding required to get block alignment) pretending the 283 length of the plaintext is FragmentRange.high. The total padding 284 added to the current fragment is finally n plus the difference 285 between Range.high and the real plaintext length. 287 This document does not mandate any specific algorithm to split a 288 Range into multiple FragmentRange ranges. The only constraint is 289 that the sum of the obtained sequence of ranges equals the range 290 given as input. Implementations may use non-deterministic splitting 291 algorithms to change the shape of the traffic each time messages with 292 the same range are exchanged. 294 A reference range splitting algorithm is provided in the following. 296 // The maximum allowed TLSPlaintext.length 297 uint16 FS = 2^14; 298 // Maximum padding size: 299 // p = 255 for standard TLS block ciphers; 300 // p = 2^14 for extended record padding 301 uint16 PS = p; 302 // Length of the padlen: 303 // pl = 1 for standard TLS block ciphers; 304 // pl = 2 for extended record padding 305 uint8 PL = pl; 306 // Note: Block size is 0 for stream ciphers 307 uint8 BS = SecurityParameters.block_length; 308 // MAC size 309 uint8 MS = SecurityParameters.mac_length; 311 /* Returns the maximum pad that can be added for a fragment, 312 * given that at least 'len' bytes of plaintext will be 313 * transferred. 314 */ 315 uint16 max_lh_pad(uint16 len) 316 { 317 uint16 this_pad = min(PS,FS-len); 318 if (BS == 0) { 319 return this_pad; 320 } else { 321 uint8 overflow = (len + this_pad + MS + PL) % BS; 322 if (overflow > this_pad) { 323 return this_pad; 324 } else { 325 return this_pad - overflow; 326 } 327 } 328 } 329 FragmentRange split_range(Range *total) 330 { 331 FragmentRange f; 333 if (total.high == total.low) { 334 // "Point" range, no real LH to do: 335 // just implement standard fragmentation. 336 uint16 len = min(total.high,FS); 337 f.low = len; 338 f.high = len; 339 total->low -= len; 340 total->high -= len; 341 } else if (total.low >= FS) { 342 // More bytes to send than a fragment can handle: 343 // send as many bytes as possible. 344 f.low = FS; 345 f.high = FS; 346 total->low -= FS; 347 total->high -= FS; 348 } else { 349 // We are LH: add as much padding as necessary 350 // in the current fragment. 351 uint16 all_pad = max_lh_pad(total->low); 352 all_pad = min(all_pad, total->high - total->low); 353 f.low = total->low; 354 f.high = total->low + all_pad; 355 total->low = 0; 356 total->high -= total->low + all_pad; 357 } 359 return f; 360 } 362 This algorithm if called multiple times creates a list of 363 FragmentRange structures, carrying all the payload up to Range.low, 364 followed by a sequence of fragments carrying either padding or the 365 remaining part of the message that exceeds Range.low. 367 4.1.1. Fragmenting Plaintext into Records 369 There are many ways to fragment the message content across a sequence 370 of FragmentRanges. This document does not mandate any fragmentation 371 algorithm. In the following, a fragmentation algorithm that tries to 372 put as many bytes as possible in the first fragments is provided. 374 /* len: The total real plaintext length to be sent. 375 * r0: a range that can be conveyed in one fragment, 376 * as returned by split_range. 377 * r1: the remaining range used to send the remaining data 378 * Returns: the number of bytes of plaintext to be sent 379 * in the next fragment with range r0. 380 uint16 fragment(uint32 len, FragmentRange r0, Range r1) 381 { 382 return min(r0.high, len - r1.low); 383 } 385 4.1.2. Adding the Length Hiding Padding 387 If 'len' is the real plaintext length to be sent in a record fragment 388 with range FragmentRange, a LH-TLS implementation MUST add at least 389 FragmentRange.high - len bytes of padding to that record fragment 390 (plus, if needed, some additional padding required to get block 391 alignment). 393 If the split_range and fragment functions above are used, then the 394 difference FragmentRange.high - len is always smaller than the 395 maximum available padding size (including further block alignment 396 padding). 398 4.1.3. A Length Hiding API 400 Finally, a LH-aware TLS implementation MAY use the algorithms 401 described in sections Section 4.1 and Section 4.1.1 to offer a LH TLS 402 API similar to the following, where it is assumed that a 403 TLS_send(data, len, target_length) function sends a single TLS record 404 fragment adding the necessary padding to match the target_length, as 405 explained in section Section 4.1.2. 407 uint32 message_send(opaque data, Range total) 408 { 409 FragmentRange current; 410 uint16 current_len, sent = 0; 412 while (total.high != 0) { 413 current = split_range(&total); 414 next_len = fragment(data.length - sent, current, total); 415 sent += TLS_send(&data[sent], next_len, current.high); 416 } 418 return sent; 419 } 421 This interface requires the TLS implementation to internally buffer 422 the entire application message. Alternatively, a LH TLS 423 implementation MAY directly expose the split_range and fragment 424 functions to the user, to avoid internal buffering. Note that it is 425 only necessary to know the desired plaintext range to execute the 426 split_range function, not the real plaintext size nor its content. 428 4.2. Applicability 430 If a TLS-LH mechanism is used in a TLS session, then TLS record 431 protocol compression MUST be disabled. Compression is known to leak 432 substantial information about the plaintext, including its length 433 [COMPLEAK], which defeats the purpose of LH. Moreover, since in TLS 434 compression happens after fragmentation, and the compression ratio is 435 not known a priori, it is impossible to define a precise 436 fragmentation strategy when compression is in place. 438 Length hiding can only work when some padding can be added before 439 encryption, so that an attacker cannot distinguish whether the 440 encrypted data are padding or application data. Hence, LH can only 441 be used with block ciphers in standard TLS, and with any cipher when 442 the extended record padding is used. In any case, length hiding MUST 443 NOT be used with TLS_NULL_WITH_NULL_NULL or MAC-only ciphersuites. 445 5. Security Considerations 447 The LH scheme described in this document is effective in hiding the 448 length of the exchanged messages, when an attacker observes the total 449 bandwidth exchanged by a client and server using TLS. Crucially, the 450 split_range algorithm, which determines the traffic shape and total 451 bandwidth, MUST NOT depend on the real message length, but only on 452 the Range.low and Range.high values, which are public. 454 Similarly, only the application knows when the recipient of the 455 message is expected to react, upon receiving the message. For 456 example, a web browser may start loading a hyperlink contained in an 457 HTML file, as soon as the hyperlink is received, before the HTML file 458 has been fully parsed. By using a callback for the implementation of 459 the fragment function, a LH-aware application using a TLS-LH library 460 can decide how much data to send in each fragment. An application 461 should consider the TLS LH mechanism effective only to conceal the 462 length of the message exchanged over the network. 464 Yet, an application on top of TLS could easily leak the message 465 length, by performing visible actions after a known amount of bytes 466 has been received. Hiding the length of the message at the 467 application level is outside the scope of this document, and is a 468 complex information flow property that should carefully considered 469 when designing a LH-aware implementation. Even the way the bytes are 470 transferred from the TLS library to the application could leak 471 information about their length. 473 5.1. Length Hiding with standard TLS block ciphers 475 Section 6.2.3.2, Implementation note, of [RFC5246] acknowledges a 476 small timing channel, due to the MAC timing depending on the length 477 of each TLSCiphertext.content. Usage of large ranges with the LH 478 scheme amplifies this timing channel, up to make it exploitable 479 [LH-PADDING], because shorter messages within a range will be 480 processed faster than longer messages in the same range. 481 Implementations supporting the LH scheme SHOULD implement a MAC 482 algorithm whose execution time depends on the length of the 483 TLSCiphertext.content plus the length of the padding, thus 484 eliminating this timing channel. 486 5.2. Length Hiding with extended record padding 488 Since the padding is always included in the MAC computation, attacks 489 that utilize the current CBC-padding timing channel (e.g., 490 [DTLS-ATTACK]) are not applicable. 492 In a way, the extended record padding can be seen as a special way of 493 encoding application data before encryption (where application data 494 given by the user are prefixed by some padding). Hence, previous 495 security results on standard TLS block and stream ciphers still apply 496 to the extended record padding. 498 5.3. Mitigating Denial of Service 500 The TLS protocol allows zero-length fragments of Application data, 501 and these are exploited by the TLS length-hiding mechanism proposed 502 in this document. If the user is notified of such zero-length 503 fragments, normally this poses no problem. However, some TLS 504 implementations will keep reading for the next fragment if a zero- 505 length fragment is received. This exposes implementations 506 (especially server-side ones) to distributed denial of service (DoS) 507 attacks, where a network of attackers connect to the same host and 508 send a sequence of zero-length fragments, keeping the host busy in 509 processing them. This issue gets amplified when the 510 "extended_record_padding" extension is used, because MAC computation 511 includes a possibly large amount of padding. 513 Implementations that keep reading for the next fragment when a zero- 514 length one is received, and that are concerned by such DoS attacks, 515 MAY implement a DoS countermeasure. For example, they could accept 516 'n' zero-length fragments in a row, before notifying the user or 517 returning an error. This conflicts with the requirements of a 518 length-hiding mechanism, where zero-length fragments are used to 519 conceal the real plaintext length. The value of 'n' SHOULD be chosen 520 to satisfy the tradeoff so that it is the smallest number of 521 fragments that can convey the required LH padding. Normally, this 522 value is application specific, so TLS implementations that implement 523 this mitigation SHOULD let 'n' be set by the application. 525 6. IANA Considerations 527 This document defines a new TLS extension, "extended_record_padding", 528 assigned a value of TBD-BY-IANA (the value 48015 is suggested) from 529 the TLS ExtensionType registry defined in [RFC5246]. This value is 530 used as the extension number for the extensions in both the client 531 hello message and the server hello message. The new extension type 532 is used for certificate type negotiation. 534 7. Normative References 536 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 537 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 539 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 540 Requirement Levels", BCP 14, RFC 2119, March 1997. 542 [RFC6066] Eastlake, D., "Transport Layer Security (TLS) Extensions: 543 Extension Definitions", RFC 6066, January 2011. 545 [DTLS-ATTACK] 546 Nadhem, N. and K. Paterson, "Plaintext-recovery attacks 547 against datagram TLS.", Network and Distributed System 548 Security Symposium , 2012. 550 [LH-PADDING] 551 Pironti, A., Strub, P., and K. Bhargavan, "Identifying 552 Website Users by TLS Traffic Analysis: New Attacks and 553 Effective Countermeasures.", INRIA Research Report 8067 , 554 2012. 556 [CBCTIME] Canvel, B., Hiltgen, A., Vaudenay, S., and M. Vuagnoux, 557 "Password Interception in a SSL/TLS Channel", Advances in 558 Cryptology -- CRYPTO , 2003. 560 [COMPLEAK] 561 Kelsey, K., "Compression and information leakage of 562 plaintext", Fast software encryption , 2002. 564 Authors' Addresses 566 Alfredo Pironti 567 INRIA Paris-Rocquencourt 568 23, Avenue d'Italie 569 Paris, 75214 CEDEX 13 570 France 572 Email: alfredo.pironti@inria.fr 574 Nikos Mavrogiannopoulos 575 Dept. of Electrical Engineering ESAT/COSIC KU Leuven - iMinds 576 Kasteelpark Arenberg 10, bus 2446 577 Leuven-Heverlee, B-3001 578 Belgium 580 Email: nikos.mavrogiannopoulos@esat.kuleuven.be