Minimal TLS Extension for improved padding support
                             Nick Mathewson

                       *DRAFT    DRAFT    DRAFT*

Current status:

   I am showing this document to some TLS enthusiasts I know and asking
   whether its basic ideas are sound and/or adoptable by the community
   at large.

==============================

Motivation:

   In the TLS protocol today, some ciphersuites support padding, and
   some do not.  But padding can be necessary for various reasons,
   including resistance to website fingerprinting attacks, the CRIME
   attack and its relatives, and anonymity-breaking attacks.

   Using a ciphersuite (typically based on CBC) that supports padding
   isn't enough: some implementations in practice do not support
   receiving more than minimal padding.

   Notation here is as in RFC5246.


Description and scope:

   This document describe two modifications to the TLS protocol, for use
   in padding: An extension to advertise padding support, and a record
   format change to support padding with stream ciphers.

   This document does NOT describe any API for setting the padding in a
   TLS implementation.  Nor does it describe a particular padding
   algorithm: this is an area of active research.

A TLS extension to indicate padding compatibility:

   In a ClientHello message, a client may send a PaddingSupport extension to
   indicate that it would like to use padding.  Its extension data
   format is:

       struct {
        uint16_t nMethods;
        uint16_t PadMethods[PaddingSupport.nMethods]
       } PaddingSupportData;

   When a client sends this extension, it indicates that it would like
   to send padding, or would be willing to receive padding, and lists
   all of the padding methods it supports.  These are:

       enum {
           MinPadding (0),
           CBCPadding (1),
           RecordPadding (2)
       } PadMethod;

   If the server recognizes the extension and wishes to use padding, it
   replies with a PaddingSupport extension containing a single PadMethod,
   indicating the padding method it has chosen.

   The RecordPadding method is treated more thoroughly below.

   MinPadding means that no padding should be added in the case of stream or
   AEAD ciphers, and that only the smallest amount of padding should be added
   for CBC ciphers. (All TLS implementations currently support this, and it
   is typically the default without padding.)

   CBCPadding means that, if a CBC block cipher ciphersuite is used, a
   non-minimal amount of padding may be included with each encrypted
   record.  All conformant TLS implementations currently support this
   kind of padding, but not all implementations are conformant.


A padded record format for non-CBC ciphersuites:

   When a padding method other than MinPadding or CBCPadding is in use,
   TLSCompressed takes the following form:

      struct {
          ContentType type;       /* same as TLSPlaintext.type */
          ProtocolVersion version;/* same as TLSPlaintext.version */
          uint16 length;
          uint16 pad_length;
          opaque fragment[TLSCompressed.length];
          opaque padding[TLSCompressed.pad_length];
      } TLSCompressed;

   And the MAC is generated as:

      MAC(MAC_write_key, seq_num +
                            TLSCompressed.type +
                            TLSCompressed.version +
                            TLSCompressed.length +
                            TLSCompressed.pad_length +
                            TLSCompressed.fragment +
                            TLSCompressed.padding);

   Here, length+pad_len MUST NOT exceed 2^14+1024.

   The contents of padding SHOULD be a sequence of zero bytes.

   To avoid leaking the length of the padding to timing attacks,
   implementations MUST decrypt the padding even when using ciphers such
   as CBC in which it might otherwise be avoided.

Discussions on alternative designs:

   We might, by analogy with CBC padding, try to shoehorn a series of
   padding bytes into the end of the encrypted material after the MAC.
   But this would perpetuate the kludges of SSL, rather than replacing
   them.  The existing CBC padding scheme has created implementation
   issues and security problems in the past; let's not do more of it.