idnits 2.17.1 draft-pironti-tls-length-hiding-02.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 (September 11, 2013) is 3879 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: March 15, 2014 N. Mavrogiannopoulos 5 Independent 6 September 11, 2013 8 Length Hiding Padding for the Transport Layer Security Protocol 9 draft-pironti-tls-length-hiding-02 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 March 15, 2014. 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 extended record padding . . . . . . . . 13 68 5.2. Length Hiding with standard TLS block ciphers . . . . . . 13 69 5.3. Mitigating Denial of Service . . . . . . . . . . . . . . . 14 70 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 71 7. Normative References . . . . . . . . . . . . . . . . . . . . . 16 72 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 17 73 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 75 1. Introduction 77 When using CBC block ciphers, the TLS protocol [RFC5246] provides 78 means to frustrate attacks based on analysis of the length of 79 exchanged messages, by adding extra pad to TLS records. However, the 80 TLS specification does not define a length hiding (LH) method for 81 applications that require it. In fact, current implementations of 82 eager fragmentation strategies or random padding strategies have been 83 showed to be ineffective against this kind of traffic analysis 84 [LH-PADDING]. 86 By design, in the standard TLS block cipher mode, only a limited 87 amount of extra padding can be carried with each record fragment, and 88 this can potentially require extra fragmentation to carry all 89 required padding. Moreover, no LH can be implemented for stream 90 ciphers. To overcome these limitations, the TLS extension proposed 91 in this document enables efficient LH both for block and stream 92 ciphers. 94 In addition, it presents guidelines and a reference implementation of 95 record fragmentation and padding so that the length of the exchanged 96 messages is effectively concealed within a range of lengths provided 97 by the user of the TLS record protocol. 99 The proposed extension also eliminates padding oracles (both in 100 errors and timing) that have been plaguing standard TLS block ciphers 101 [CBCTIME] [DTLS-ATTACK]. 103 The goals of LH for TLS are the following: 105 1. Length-Hiding: use message fragmentation and the allowed extra 106 padding for block ciphers to conceal the real length of the 107 exchanged message within a range of lengths chosen by the user of 108 the TLS record protocol. All messages sent with the same range 109 use the same network bandwidth, regardless of the real size of 110 the message itself. 112 2. Efficiency: the minimum required amount of extra padding is used, 113 and the minimum number of required fragments is sent. 115 To maximize interoperability, this document also includes guidelines 116 to implement LH by using the limited amount of padding provided by 117 existing block ciphers. This variant of LH is backward compatible, 118 in that an implementation sending length-hidden messages correctly 119 interoperates with non LH-aware implementations of TLS, but leads to 120 a less efficient LH implementation. 122 2. Terminology 124 This document uses the same notation and terminology used in the TLS 125 Protocol specification [RFC5246]. 127 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 128 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 129 document are to be interpreted as described in [RFC2119]. 131 3. TLS Extension: Extended Record Padding 133 The TLS extended record padding is a variant of the TLS record 134 protocol where every record can be padded up to 2^14 bytes, 135 regardless of the cipher being used. 137 3.1. Extension Negotiation 139 In order to indicate the support of the extended record padding, 140 clients MUST include an extension of type "extended_record_padding" 141 to the extended client hello message. The "extended_record_padding" 142 TLS extension is assigned the value of TDB-BY-IANA from the TLS 143 ExtensionType registry. This value is used as the extension number 144 for the extensions in both the client hello message and the server 145 hello message. The hello extension mechanism is described in 146 [RFC5246]. 148 This extension carries no payload and indicates support for the 149 extended record padding. The "extension_data" field of this 150 extension are of zero length in both the client and the server. 152 The negotiated record padding applies for the duration of the 153 session, including session resumption. A client wishing to resume a 154 session where the extended record padding was negotiated SHOULD 155 include the "extended_record_padding" extension in the client hello. 157 3.2. Record Payload 159 The translation of the TLSCompressed structure into TLSCiphertext 160 remains the same as in [RFC5246]. When the cipher is 161 BulkCipherAlgorithm.null, the 'fragment' structure of TLSCiphertext 162 also remains unchanged. That is, for the TLS_NULL_WITH_NULL_NULL 163 ciphersuite and for MAC-only ciphersuites this extension has no 164 effect. For all other ciphersuites, the 'fragment' structure of 165 TLSCiphertext is modified as follows. 167 stream-ciphered struct { 168 opaque pad<0..2^14>; 169 opaque content[TLSCompressed.length]; 170 opaque MAC[SecurityParameters.mac_length]; 171 } GenericStreamCipher; 173 struct { 174 opaque IV[SecurityParameters.record_iv_length]; 175 block-ciphered ciphered struct { 176 opaque pad<0..2^14>; 177 opaque content[TLSCompressed.length]; 178 opaque MAC[CipherSpec.hash_size]; 179 }; 180 } GenericBlockCipher; 182 struct { 183 opaque nonce_explicit[SecurityParameters.record_iv_length]; 184 aead-ciphered struct { 185 opaque pad<0..2^14>; 186 opaque content[TLSCompressed.length]; 187 }; 188 } GenericAEADCipher; 190 The padding can be filled with arbitrary data, and it is 191 authenticated as part of the MAC. For block ciphers, the length of 192 the pad MUST be such that the total length (i.e., the pad, the 193 content and the MAC) are a multiple of the block size. 195 For the various ciphers the data are authenticated as follows. 197 Standard Stream Ciphers: 199 MAC(MAC_write_key, seq_num + 200 TLSCompressed.type + 201 TLSCompressed.version + 202 length + 203 TLSCiphertext.fragment.GenericStreamCipher.pad + 204 TLSCompressed.fragment); 206 Block Ciphers: 208 MAC(MAC_write_key, seq_num + 209 TLSCompressed.type + 210 TLSCompressed.version + 211 length + 212 TLSCiphertext.fragment.GenericBlockCipher.pad + 213 TLSCompressed.fragment); 215 AEAD Ciphers: 217 additional_data = seq_num + TLSCompressed.type + 218 TLSCompressed.version + length; 220 AEADEncrypted = AEAD-Encrypt(write_key, nonce, 221 pad + plaintext, 222 additional_data); 224 length 225 For all the above cases, a uint16 containing the sum of the 226 padding length and the content length. 228 Implementation note: With block and stream ciphers, in order to avoid 229 padding oracles, decryption, MAC verification and payload decoding 230 MUST be executed in the following order. 232 1. Decrypt TLSCiphertext.fragment. 234 2. Verify the MAC. 236 3. Split plaintext from pad. 238 4. A Length Hiding Mechanism for TLS 240 In order to send length-hidden messages, a user of a LH-TLS 241 implementation provides the plaintext to be sent together with a 242 range (low,high), meaning that an attacker can at most learn that the 243 real plaintext length is between low and high. 245 The LH mechanism described in the rest of this document applies both 246 to standard TLS block ciphers and the extended record padding of 247 Section 3. 249 4.1. Range Splitting 251 Not all user-provided ranges can be conveyed in a singe TLS record 252 fragment. A LH-TLS implementation uses a fragmentation algorithm 253 that takes a message with a desired length range (low,high) and 254 breaks it up into n suitably sized ranges each of which can be 255 conveyed in a single TLS record fragment. The Range and 256 FragmentRange are defined as follows. 258 struct { 259 uint32 low; 260 unit32 high; 261 } Range; 263 struct { 264 uint16 low; 265 unit16 high; 266 } FragmentRange; 268 If the difference between Range.high and Range.low is greater than 269 the maximum allowed padding size for a single fragment, or if their 270 value is greater than the maximum fragment size, the given range must 271 be split into multiple smaller FragmentRange structures each of which 272 can be conveyed into a single TLS record. 274 Range.low MUST be less or equal to Range.high. Declaring Range.low 275 and Range.high as uint32 allows to send messages of length up to 276 2^32: TLS implementations MAY use larger data types for these fields. 277 A FragmentRange, that can be conveyed in one record, MUST have both 278 values of FragmentRange.low and FragmentRange.high not exceeding 2^14 279 (or the negotiated maximum value of TLSPlaintext.length [RFC6066]). 281 A TLS implementation applies the range splitting algorithm starting 282 from the user-provided Range structure, resulting into a sequence of 283 FragmentRange structures. For each FragmentRange structure, it 284 transmits a TLS record adhering into the limits of the corresponding 285 FragmentRange. When a block cipher is in use, on each record the 286 implementation computes n bytes of minimal padding (the minimum 287 amount of padding required to get block alignment) pretending the 288 length of the plaintext is FragmentRange.high. The total padding 289 added to the current fragment is finally n plus the difference 290 between Range.high and the real plaintext length. 292 This document does not mandate any specific algorithm to split a 293 Range into multiple FragmentRange ranges. The only constraint is 294 that the sum of the obtained sequence of ranges equals the range 295 given as input. Implementations may use non-deterministic splitting 296 algorithms to change the shape of the traffic each time messages with 297 the same range are exchanged. 299 A reference range splitting algorithm is provided in the following. 301 // The maximum allowed TLSPlaintext.length 302 uint16 FS = 2^14; 303 // Maximum padding size: 304 // p = 255 for standard TLS block ciphers; 305 // p = 2^14 for extended record padding 306 uint16 PS = p; 307 // Length of the padlen: 308 // pl = 1 for standard TLS block ciphers; 309 // pl = 2 for extended record padding 310 uint8 PL = pl; 311 // Note: Block size is 0 for stream ciphers 312 uint8 BS = SecurityParameters.block_length; 313 // MAC size 314 uint8 MS = SecurityParameters.mac_length; 316 /* Returns the maximum pad that can be added for a fragment, 317 * given that at least 'len' bytes of plaintext will be 318 * transferred. 319 */ 320 uint16 max_lh_pad(uint16 len) 321 { 322 uint16 this_pad = min(PS,FS-len); 323 if (BS == 0) { 324 return this_pad; 325 } else { 326 uint8 overflow = (len + this_pad + MS + PL) % BS; 327 if (overflow > this_pad) { 328 return this_pad; 329 } else { 330 return this_pad - overflow; 331 } 332 } 333 } 334 FragmentRange split_range(Range *total) 335 { 336 FragmentRange f; 338 if (total.high == total.low) { 339 // "Point" range, no real LH to do: 340 // just implement standard fragmentation. 341 uint16 len = min(total.high,FS); 342 f.low = len; 343 f.high = len; 344 total->low -= len; 345 total->high -= len; 346 } else if (total.low >= FS) { 347 // More bytes to send than a fragment can handle: 348 // send as many bytes as possible. 349 f.low = FS; 350 f.high = FS; 351 total->low -= FS; 352 total->high -= FS; 353 } else { 354 // We are LH: add as much padding as necessary 355 // in the current fragment. 356 uint16 all_pad = max_lh_pad(total->low); 357 all_pad = min(all_pad, total->high - total->low); 358 f.low = total->low; 359 f.high = total->low + all_pad; 360 total->low = 0; 361 total->high -= total->low + all_pad; 362 } 364 return f; 365 } 367 If invoked multiple times, this algorithm creates a list of 368 FragmentRange structures, carrying all the payload up to Range.low, 369 followed by a sequence of fragments carrying either padding or the 370 remaining part of the message that exceeds Range.low. 372 4.1.1. Fragmenting Plaintext into Records 374 There are many ways to fragment the message content across a sequence 375 of FragmentRanges. This document does not mandate any fragmentation 376 algorithm. In the following, a fragmentation algorithm that tries to 377 put as many bytes as possible in the first fragments is provided. 379 /* len: The total real plaintext length to be sent. 380 * r0: a range that can be conveyed in one fragment, 381 * as returned by split_range. 382 * r1: the remaining range used to send the remaining data 383 * Returns: the number of bytes of plaintext to be sent 384 * in the next fragment with range r0. 385 uint16 fragment(uint32 len, FragmentRange r0, Range r1) 386 { 387 return min(r0.high, len - r1.low); 388 } 390 4.1.2. Adding the Length Hiding Padding 392 If 'len' is the real plaintext length to be sent in a record fragment 393 with range FragmentRange, a LH-TLS implementation MUST add at least 394 FragmentRange.high - len bytes of padding to that record fragment 395 (plus, if needed, some additional padding required to get block 396 alignment). 398 If the split_range and fragment functions above are used, then the 399 difference FragmentRange.high - len is always smaller than the 400 maximum available padding size (including further block alignment 401 padding). 403 4.1.3. A Length Hiding API 405 Finally, a LH-aware TLS implementation MAY use the algorithms 406 described in Section 4.1 and Section 4.1.1 to offer a LH TLS API 407 similar to the following, where it is assumed that a TLS_send(data, 408 len, target_length) function sends a single TLS record fragment 409 adding the necessary padding to match the target_length, as explained 410 in Section 4.1.2. 412 uint32 message_send(opaque data, Range total) 413 { 414 FragmentRange current; 415 uint16 current_len, sent = 0; 417 while (total.high != 0) { 418 current = split_range(&total); 419 next_len = fragment(data.length - sent, current, total); 420 sent += TLS_send(&data[sent], next_len, current.high); 421 } 423 return sent; 424 } 426 This interface requires the TLS implementation to internally buffer 427 the entire application message. Alternatively, a LH TLS 428 implementation MAY directly expose the split_range and fragment 429 functions to the user, to avoid internal buffering. Note that it is 430 only necessary to know the desired plaintext range to execute the 431 split_range function, not the real plaintext size nor its content. 433 4.2. Applicability 435 If a TLS-LH mechanism is used in a TLS session, then TLS record 436 protocol compression MUST be disabled. Compression is known to leak 437 substantial information about the plaintext, including its length 438 [COMPLEAK], which defeats the purpose of LH. Moreover, since in TLS 439 compression happens after fragmentation, and the compression ratio is 440 not known a priori, it is impossible to define a precise 441 fragmentation strategy when compression is in place. 443 Length hiding can only work when some padding can be added before 444 encryption, so that an attacker cannot distinguish whether the 445 encrypted data are padding or application data. Hence, LH can only 446 be used with block ciphers in standard TLS, and with any cipher when 447 the extended record padding is used. In any case, length hiding MUST 448 NOT be used with TLS_NULL_WITH_NULL_NULL or MAC-only ciphersuites. 450 5. Security Considerations 452 The LH scheme described in this document is effective in hiding the 453 length of the exchanged messages, when an attacker observes the total 454 bandwidth exchanged by a client and server using TLS. Crucially, the 455 split_range algorithm, which determines the traffic shape and total 456 bandwidth, MUST NOT depend on the real message length, but only on 457 the Range.low and Range.high values, which are public. 459 Similarly, only the application knows when the recipient of the 460 message is expected to react, upon receiving the message. For 461 example, a web browser may start loading a hyperlink contained in an 462 HTML file, as soon as the hyperlink is received, before the HTML file 463 has been fully parsed. By using a callback for the implementation of 464 the fragment function, a LH-aware application using a TLS-LH library 465 can decide how much data to send in each fragment. An application 466 should consider the TLS LH mechanism effective only to conceal the 467 length of the message exchanged over the network. 469 Yet, an application on top of TLS could easily leak the message 470 length, by performing visible actions after a known amount of bytes 471 has been received. Hiding the length of the message at the 472 application level is outside the scope of this document, and is a 473 complex information flow property that should carefully considered 474 when designing a LH-aware implementation. Even the way the bytes are 475 transferred from the TLS library to the application could leak 476 information about their length. 478 5.1. Length Hiding with extended record padding 480 Since the padding is always included in the MAC computation, attacks 481 that utilize the current CBC-padding timing channel (e.g., 482 [DTLS-ATTACK]) are not applicable. 484 In a way, the extended record padding can be seen as a special way of 485 encoding application data before encryption (where application data 486 given by the user are prefixed by some padding). Hence, previous 487 security results on standard TLS block and stream ciphers still apply 488 to the extended record padding. 490 5.2. Length Hiding with standard TLS block ciphers 492 Section 6.2.3.2, Implementation note, of [RFC5246] acknowledges a 493 small timing channel, due to the MAC timing depending on the length 494 of each TLSCiphertext.content. Usage of large ranges with the LH 495 scheme amplifies this timing channel, up to make it exploitable 496 [LH-PADDING], because shorter messages within a range will be 497 processed faster than longer messages in the same range. 499 Implementations supporting the LH scheme SHOULD implement a MAC 500 algorithm whose execution time depends on the length of the 501 TLSCiphertext.content plus the length of the padding, thus 502 eliminating this timing channel. 504 5.3. Mitigating Denial of Service 506 The TLS protocol allows zero-length fragments of Application data, 507 and these are exploited by the TLS length-hiding mechanism proposed 508 in this document. For implementations that notify the application of 509 such zero-length fragments, this poses no denial of service (DoS) 510 issues. However, some TLS implementations will keep reading for the 511 next fragment if a zero-length fragment is received. This exposes 512 such implementations (especially server-side ones) to distributed DoS 513 attacks, where a network of attackers connects to the same host and 514 sends a sequence of zero-length fragments, keeping the host busy in 515 processing them. This issue gets amplified when the 516 "extended_record_padding" extension is used, because MAC computation 517 includes a possibly large amount of padding. 519 Implementations that keep reading for the next fragment when a zero- 520 length one is received, and that are concerned by such DoS attacks, 521 MAY implement a DoS countermeasure. For example, they could accept 522 'n' zero-length fragments in a row, before notifying the application 523 or returning an error. This conflicts with the requirements of a 524 length-hiding mechanism, where zero-length fragments are used to 525 conceal the real plaintext length. The value of 'n' SHOULD be chosen 526 such that it is the smallest number of fragments that can convey the 527 application-required LH padding. Usually, this value is application 528 specific, so TLS implementations that implement this DoS mitigation 529 SHOULD let 'n' be set by the application. 531 6. IANA Considerations 533 This document defines a new TLS extension, "extended_record_padding", 534 assigned a value of TBD-BY-IANA (the value 48015 is suggested) from 535 the TLS ExtensionType registry defined in [RFC5246]. This value is 536 used as the extension number for the extensions in both the client 537 hello message and the server hello message. 539 7. Normative References 541 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 542 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 544 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 545 Requirement Levels", BCP 14, RFC 2119, March 1997. 547 [RFC6066] Eastlake, D., "Transport Layer Security (TLS) Extensions: 548 Extension Definitions", RFC 6066, January 2011. 550 [DTLS-ATTACK] 551 Nadhem, N. and K. Paterson, "Plaintext-recovery attacks 552 against datagram TLS.", Network and Distributed System 553 Security Symposium , 2012. 555 [LH-PADDING] 556 Pironti, A., Strub, P., and K. Bhargavan, "Identifying 557 Website Users by TLS Traffic Analysis: New Attacks and 558 Effective Countermeasures.", INRIA Research Report 8067 , 559 2012. 561 [CBCTIME] Canvel, B., Hiltgen, A., Vaudenay, S., and M. Vuagnoux, 562 "Password Interception in a SSL/TLS Channel", Advances in 563 Cryptology -- CRYPTO , 2003. 565 [COMPLEAK] 566 Kelsey, K., "Compression and information leakage of 567 plaintext", Fast software encryption , 2002. 569 Appendix A. Acknowledgements 571 The authors wish to thank Kenny Paterson for his suggestions on 572 improving this document. 574 Authors' Addresses 576 Alfredo Pironti 577 INRIA Paris-Rocquencourt 578 23, Avenue d'Italie 579 Paris, 75214 CEDEX 13 580 France 582 Email: alfredo.pironti@inria.fr 584 Nikos Mavrogiannopoulos 585 Independent 586 Leuven, B-3000 587 Belgium 589 Email: nmav@gnutls.org