Network Working Group A. Pironti Internet-Draft INRIA Paris-Rocquencourt Expires: March 15, 2014 N. Mavrogiannopoulos Independent September 11, 2013 Length Hiding Padding for the Transport Layer Security Protocol draft-pironti-tls-length-hiding-02 Abstract This memo proposes length hiding methods of operation for the TLS protocol. It defines a TLS extension to allow arbitrary amount of padding in any TLS ciphersuite, and it presents guidelines and a reference implementation of record fragmentation and padding so that the length of the exchanged messages is effectively concealed within a given range of lengths. The latter guidelines also apply to the standard TLS padding allowed by the TLS block ciphers. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on March 15, 2014. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 1] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. TLS Extension: Extended Record Padding . . . . . . . . . . . . 5 3.1. Extension Negotiation . . . . . . . . . . . . . . . . . . 5 3.2. Record Payload . . . . . . . . . . . . . . . . . . . . . . 5 4. A Length Hiding Mechanism for TLS . . . . . . . . . . . . . . 8 4.1. Range Splitting . . . . . . . . . . . . . . . . . . . . . 8 4.1.1. Fragmenting Plaintext into Records . . . . . . . . . . 10 4.1.2. Adding the Length Hiding Padding . . . . . . . . . . . 11 4.1.3. A Length Hiding API . . . . . . . . . . . . . . . . . 11 4.2. Applicability . . . . . . . . . . . . . . . . . . . . . . 12 5. Security Considerations . . . . . . . . . . . . . . . . . . . 13 5.1. Length Hiding with extended record padding . . . . . . . . 13 5.2. Length Hiding with standard TLS block ciphers . . . . . . 13 5.3. Mitigating Denial of Service . . . . . . . . . . . . . . . 14 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 7. Normative References . . . . . . . . . . . . . . . . . . . . . 16 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 17 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 2] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 1. Introduction When using CBC block ciphers, the TLS protocol [RFC5246] provides means to frustrate attacks based on analysis of the length of exchanged messages, by adding extra pad to TLS records. However, the TLS specification does not define a length hiding (LH) method for applications that require it. In fact, current implementations of eager fragmentation strategies or random padding strategies have been showed to be ineffective against this kind of traffic analysis [LH-PADDING]. By design, in the standard TLS block cipher mode, only a limited amount of extra padding can be carried with each record fragment, and this can potentially require extra fragmentation to carry all required padding. Moreover, no LH can be implemented for stream ciphers. To overcome these limitations, the TLS extension proposed in this document enables efficient LH both for block and stream ciphers. In addition, it presents guidelines and a reference implementation of record fragmentation and padding so that the length of the exchanged messages is effectively concealed within a range of lengths provided by the user of the TLS record protocol. The proposed extension also eliminates padding oracles (both in errors and timing) that have been plaguing standard TLS block ciphers [CBCTIME] [DTLS-ATTACK]. The goals of LH for TLS are the following: 1. Length-Hiding: use message fragmentation and the allowed extra padding for block ciphers to conceal the real length of the exchanged message within a range of lengths chosen by the user of the TLS record protocol. All messages sent with the same range use the same network bandwidth, regardless of the real size of the message itself. 2. Efficiency: the minimum required amount of extra padding is used, and the minimum number of required fragments is sent. To maximize interoperability, this document also includes guidelines to implement LH by using the limited amount of padding provided by existing block ciphers. This variant of LH is backward compatible, in that an implementation sending length-hidden messages correctly interoperates with non LH-aware implementations of TLS, but leads to a less efficient LH implementation. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 3] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 2. Terminology This document uses the same notation and terminology used in the TLS Protocol specification [RFC5246]. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 4] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 3. TLS Extension: Extended Record Padding The TLS extended record padding is a variant of the TLS record protocol where every record can be padded up to 2^14 bytes, regardless of the cipher being used. 3.1. Extension Negotiation In order to indicate the support of the extended record padding, clients MUST include an extension of type "extended_record_padding" to the extended client hello message. The "extended_record_padding" TLS extension is assigned the value of TDB-BY-IANA from the TLS ExtensionType registry. This value is used as the extension number for the extensions in both the client hello message and the server hello message. The hello extension mechanism is described in [RFC5246]. This extension carries no payload and indicates support for the extended record padding. The "extension_data" field of this extension are of zero length in both the client and the server. The negotiated record padding applies for the duration of the session, including session resumption. A client wishing to resume a session where the extended record padding was negotiated SHOULD include the "extended_record_padding" extension in the client hello. 3.2. Record Payload The translation of the TLSCompressed structure into TLSCiphertext remains the same as in [RFC5246]. When the cipher is BulkCipherAlgorithm.null, the 'fragment' structure of TLSCiphertext also remains unchanged. That is, for the TLS_NULL_WITH_NULL_NULL ciphersuite and for MAC-only ciphersuites this extension has no effect. For all other ciphersuites, the 'fragment' structure of TLSCiphertext is modified as follows. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 5] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 stream-ciphered struct { opaque pad<0..2^14>; opaque content[TLSCompressed.length]; opaque MAC[SecurityParameters.mac_length]; } GenericStreamCipher; struct { opaque IV[SecurityParameters.record_iv_length]; block-ciphered ciphered struct { opaque pad<0..2^14>; opaque content[TLSCompressed.length]; opaque MAC[CipherSpec.hash_size]; }; } GenericBlockCipher; struct { opaque nonce_explicit[SecurityParameters.record_iv_length]; aead-ciphered struct { opaque pad<0..2^14>; opaque content[TLSCompressed.length]; }; } GenericAEADCipher; The padding can be filled with arbitrary data, and it is authenticated as part of the MAC. For block ciphers, the length of the pad MUST be such that the total length (i.e., the pad, the content and the MAC) are a multiple of the block size. For the various ciphers the data are authenticated as follows. Standard Stream Ciphers: MAC(MAC_write_key, seq_num + TLSCompressed.type + TLSCompressed.version + length + TLSCiphertext.fragment.GenericStreamCipher.pad + TLSCompressed.fragment); Block Ciphers: MAC(MAC_write_key, seq_num + TLSCompressed.type + TLSCompressed.version + length + TLSCiphertext.fragment.GenericBlockCipher.pad + TLSCompressed.fragment); Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 6] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 AEAD Ciphers: additional_data = seq_num + TLSCompressed.type + TLSCompressed.version + length; AEADEncrypted = AEAD-Encrypt(write_key, nonce, pad + plaintext, additional_data); length For all the above cases, a uint16 containing the sum of the padding length and the content length. Implementation note: With block and stream ciphers, in order to avoid padding oracles, decryption, MAC verification and payload decoding MUST be executed in the following order. 1. Decrypt TLSCiphertext.fragment. 2. Verify the MAC. 3. Split plaintext from pad. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 7] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 4. A Length Hiding Mechanism for TLS In order to send length-hidden messages, a user of a LH-TLS implementation provides the plaintext to be sent together with a range (low,high), meaning that an attacker can at most learn that the real plaintext length is between low and high. The LH mechanism described in the rest of this document applies both to standard TLS block ciphers and the extended record padding of Section 3. 4.1. Range Splitting Not all user-provided ranges can be conveyed in a singe TLS record fragment. A LH-TLS implementation uses a fragmentation algorithm that takes a message with a desired length range (low,high) and breaks it up into n suitably sized ranges each of which can be conveyed in a single TLS record fragment. The Range and FragmentRange are defined as follows. struct { uint32 low; unit32 high; } Range; struct { uint16 low; unit16 high; } FragmentRange; If the difference between Range.high and Range.low is greater than the maximum allowed padding size for a single fragment, or if their value is greater than the maximum fragment size, the given range must be split into multiple smaller FragmentRange structures each of which can be conveyed into a single TLS record. Range.low MUST be less or equal to Range.high. Declaring Range.low and Range.high as uint32 allows to send messages of length up to 2^32: TLS implementations MAY use larger data types for these fields. A FragmentRange, that can be conveyed in one record, MUST have both values of FragmentRange.low and FragmentRange.high not exceeding 2^14 (or the negotiated maximum value of TLSPlaintext.length [RFC6066]). A TLS implementation applies the range splitting algorithm starting from the user-provided Range structure, resulting into a sequence of FragmentRange structures. For each FragmentRange structure, it transmits a TLS record adhering into the limits of the corresponding FragmentRange. When a block cipher is in use, on each record the Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 8] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 implementation computes n bytes of minimal padding (the minimum amount of padding required to get block alignment) pretending the length of the plaintext is FragmentRange.high. The total padding added to the current fragment is finally n plus the difference between Range.high and the real plaintext length. This document does not mandate any specific algorithm to split a Range into multiple FragmentRange ranges. The only constraint is that the sum of the obtained sequence of ranges equals the range given as input. Implementations may use non-deterministic splitting algorithms to change the shape of the traffic each time messages with the same range are exchanged. A reference range splitting algorithm is provided in the following. // The maximum allowed TLSPlaintext.length uint16 FS = 2^14; // Maximum padding size: // p = 255 for standard TLS block ciphers; // p = 2^14 for extended record padding uint16 PS = p; // Length of the padlen: // pl = 1 for standard TLS block ciphers; // pl = 2 for extended record padding uint8 PL = pl; // Note: Block size is 0 for stream ciphers uint8 BS = SecurityParameters.block_length; // MAC size uint8 MS = SecurityParameters.mac_length; /* Returns the maximum pad that can be added for a fragment, * given that at least 'len' bytes of plaintext will be * transferred. */ uint16 max_lh_pad(uint16 len) { uint16 this_pad = min(PS,FS-len); if (BS == 0) { return this_pad; } else { uint8 overflow = (len + this_pad + MS + PL) % BS; if (overflow > this_pad) { return this_pad; } else { return this_pad - overflow; } } } Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 9] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 FragmentRange split_range(Range *total) { FragmentRange f; if (total.high == total.low) { // "Point" range, no real LH to do: // just implement standard fragmentation. uint16 len = min(total.high,FS); f.low = len; f.high = len; total->low -= len; total->high -= len; } else if (total.low >= FS) { // More bytes to send than a fragment can handle: // send as many bytes as possible. f.low = FS; f.high = FS; total->low -= FS; total->high -= FS; } else { // We are LH: add as much padding as necessary // in the current fragment. uint16 all_pad = max_lh_pad(total->low); all_pad = min(all_pad, total->high - total->low); f.low = total->low; f.high = total->low + all_pad; total->low = 0; total->high -= total->low + all_pad; } return f; } If invoked multiple times, this algorithm creates a list of FragmentRange structures, carrying all the payload up to Range.low, followed by a sequence of fragments carrying either padding or the remaining part of the message that exceeds Range.low. 4.1.1. Fragmenting Plaintext into Records There are many ways to fragment the message content across a sequence of FragmentRanges. This document does not mandate any fragmentation algorithm. In the following, a fragmentation algorithm that tries to put as many bytes as possible in the first fragments is provided. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 10] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 /* len: The total real plaintext length to be sent. * r0: a range that can be conveyed in one fragment, * as returned by split_range. * r1: the remaining range used to send the remaining data * Returns: the number of bytes of plaintext to be sent * in the next fragment with range r0. uint16 fragment(uint32 len, FragmentRange r0, Range r1) { return min(r0.high, len - r1.low); } 4.1.2. Adding the Length Hiding Padding If 'len' is the real plaintext length to be sent in a record fragment with range FragmentRange, a LH-TLS implementation MUST add at least FragmentRange.high - len bytes of padding to that record fragment (plus, if needed, some additional padding required to get block alignment). If the split_range and fragment functions above are used, then the difference FragmentRange.high - len is always smaller than the maximum available padding size (including further block alignment padding). 4.1.3. A Length Hiding API Finally, a LH-aware TLS implementation MAY use the algorithms described in Section 4.1 and Section 4.1.1 to offer a LH TLS API similar to the following, where it is assumed that a TLS_send(data, len, target_length) function sends a single TLS record fragment adding the necessary padding to match the target_length, as explained in Section 4.1.2. uint32 message_send(opaque data, Range total) { FragmentRange current; uint16 current_len, sent = 0; while (total.high != 0) { current = split_range(&total); next_len = fragment(data.length - sent, current, total); sent += TLS_send(&data[sent], next_len, current.high); } return sent; } This interface requires the TLS implementation to internally buffer Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 11] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 the entire application message. Alternatively, a LH TLS implementation MAY directly expose the split_range and fragment functions to the user, to avoid internal buffering. Note that it is only necessary to know the desired plaintext range to execute the split_range function, not the real plaintext size nor its content. 4.2. Applicability If a TLS-LH mechanism is used in a TLS session, then TLS record protocol compression MUST be disabled. Compression is known to leak substantial information about the plaintext, including its length [COMPLEAK], which defeats the purpose of LH. Moreover, since in TLS compression happens after fragmentation, and the compression ratio is not known a priori, it is impossible to define a precise fragmentation strategy when compression is in place. Length hiding can only work when some padding can be added before encryption, so that an attacker cannot distinguish whether the encrypted data are padding or application data. Hence, LH can only be used with block ciphers in standard TLS, and with any cipher when the extended record padding is used. In any case, length hiding MUST NOT be used with TLS_NULL_WITH_NULL_NULL or MAC-only ciphersuites. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 12] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 5. Security Considerations The LH scheme described in this document is effective in hiding the length of the exchanged messages, when an attacker observes the total bandwidth exchanged by a client and server using TLS. Crucially, the split_range algorithm, which determines the traffic shape and total bandwidth, MUST NOT depend on the real message length, but only on the Range.low and Range.high values, which are public. Similarly, only the application knows when the recipient of the message is expected to react, upon receiving the message. For example, a web browser may start loading a hyperlink contained in an HTML file, as soon as the hyperlink is received, before the HTML file has been fully parsed. By using a callback for the implementation of the fragment function, a LH-aware application using a TLS-LH library can decide how much data to send in each fragment. An application should consider the TLS LH mechanism effective only to conceal the length of the message exchanged over the network. Yet, an application on top of TLS could easily leak the message length, by performing visible actions after a known amount of bytes has been received. Hiding the length of the message at the application level is outside the scope of this document, and is a complex information flow property that should carefully considered when designing a LH-aware implementation. Even the way the bytes are transferred from the TLS library to the application could leak information about their length. 5.1. Length Hiding with extended record padding Since the padding is always included in the MAC computation, attacks that utilize the current CBC-padding timing channel (e.g., [DTLS-ATTACK]) are not applicable. In a way, the extended record padding can be seen as a special way of encoding application data before encryption (where application data given by the user are prefixed by some padding). Hence, previous security results on standard TLS block and stream ciphers still apply to the extended record padding. 5.2. Length Hiding with standard TLS block ciphers Section 6.2.3.2, Implementation note, of [RFC5246] acknowledges a small timing channel, due to the MAC timing depending on the length of each TLSCiphertext.content. Usage of large ranges with the LH scheme amplifies this timing channel, up to make it exploitable [LH-PADDING], because shorter messages within a range will be processed faster than longer messages in the same range. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 13] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 Implementations supporting the LH scheme SHOULD implement a MAC algorithm whose execution time depends on the length of the TLSCiphertext.content plus the length of the padding, thus eliminating this timing channel. 5.3. Mitigating Denial of Service The TLS protocol allows zero-length fragments of Application data, and these are exploited by the TLS length-hiding mechanism proposed in this document. For implementations that notify the application of such zero-length fragments, this poses no denial of service (DoS) issues. However, some TLS implementations will keep reading for the next fragment if a zero-length fragment is received. This exposes such implementations (especially server-side ones) to distributed DoS attacks, where a network of attackers connects to the same host and sends a sequence of zero-length fragments, keeping the host busy in processing them. This issue gets amplified when the "extended_record_padding" extension is used, because MAC computation includes a possibly large amount of padding. Implementations that keep reading for the next fragment when a zero- length one is received, and that are concerned by such DoS attacks, MAY implement a DoS countermeasure. For example, they could accept 'n' zero-length fragments in a row, before notifying the application or returning an error. This conflicts with the requirements of a length-hiding mechanism, where zero-length fragments are used to conceal the real plaintext length. The value of 'n' SHOULD be chosen such that it is the smallest number of fragments that can convey the application-required LH padding. Usually, this value is application specific, so TLS implementations that implement this DoS mitigation SHOULD let 'n' be set by the application. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 14] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 6. IANA Considerations This document defines a new TLS extension, "extended_record_padding", assigned a value of TBD-BY-IANA (the value 48015 is suggested) from the TLS ExtensionType registry defined in [RFC5246]. This value is used as the extension number for the extensions in both the client hello message and the server hello message. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 15] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 7. Normative References [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security (TLS) Protocol Version 1.2", RFC 5246, August 2008. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC6066] Eastlake, D., "Transport Layer Security (TLS) Extensions: Extension Definitions", RFC 6066, January 2011. [DTLS-ATTACK] Nadhem, N. and K. Paterson, "Plaintext-recovery attacks against datagram TLS.", Network and Distributed System Security Symposium , 2012. [LH-PADDING] Pironti, A., Strub, P., and K. Bhargavan, "Identifying Website Users by TLS Traffic Analysis: New Attacks and Effective Countermeasures.", INRIA Research Report 8067 , 2012. [CBCTIME] Canvel, B., Hiltgen, A., Vaudenay, S., and M. Vuagnoux, "Password Interception in a SSL/TLS Channel", Advances in Cryptology -- CRYPTO , 2003. [COMPLEAK] Kelsey, K., "Compression and information leakage of plaintext", Fast software encryption , 2002. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 16] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 Appendix A. Acknowledgements The authors wish to thank Kenny Paterson for his suggestions on improving this document. Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 17] Internet-Draft Length Hiding Padding for TLS Protocol September 2013 Authors' Addresses Alfredo Pironti INRIA Paris-Rocquencourt 23, Avenue d'Italie Paris, 75214 CEDEX 13 France Email: alfredo.pironti@inria.fr Nikos Mavrogiannopoulos Independent Leuven, B-3000 Belgium Email: nmav@gnutls.org Pironti & Mavrogiannopoulos Expires March 15, 2014 [Page 18]