[TLS] Simple, secure 0-RTT for the masses

Bill Cox <waywardgeek@google.com> Tue, 15 March 2016 19:51 UTC

Return-Path: <waywardgeek@google.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0218412DD66 for <tls@ietfa.amsl.com>; Tue, 15 Mar 2016 12:51:47 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Level:
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_RED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id P_96QgazOZFM for <tls@ietfa.amsl.com>; Tue, 15 Mar 2016 12:51:44 -0700 (PDT)
Received: from mail-io0-x231.google.com (mail-io0-x231.google.com [IPv6:2607:f8b0:4001:c06::231]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E092212DD52 for <TLS@ietf.org>; Tue, 15 Mar 2016 12:51:40 -0700 (PDT)
Received: by mail-io0-x231.google.com with SMTP id z76so37520429iof.3 for <TLS@ietf.org>; Tue, 15 Mar 2016 12:51:40 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:date:message-id:subject:from:to; bh=lEY2xCgV50FiWqLKKUu36UZg0U83rdUPL/EYzG9KIAo=; b=cD/jyO5tMfdMnZj/h8DB5y83MjalbirKbWIg0FHKtLPj3nGkY6VkPCc8uCa3xhPxa5 +0VD+dtahuQjgcMjm/f/bZZHACOKEax7clvjfWnVCan9YvdIBk6U58rokurmOyWOq09U sPJDP81KAgWFcEulr0auGWupxlHAeIOxxKRrW98fwQBdbynU31PHxTm7dhEdFtBNrpaj U0jB3hds4pX4LQUcxtku0Gau3gZ+RbDvB8Z+p8rLh9hjOdlMh6UMQ2WPf3Ddr1kG6a7O Gm4Rw3fqnnNI1lxNMmNmh/o3qDFXgb7XPURoyqgR9/0Sfsb2czKTnJuPYmGrFUxUUFsL c96Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to; bh=lEY2xCgV50FiWqLKKUu36UZg0U83rdUPL/EYzG9KIAo=; b=cWUL06jG2lRE6eNP/Op6/wDZXSMwJsFwxi+mSiNPpsIsyn6T9WZnIYLXkR6myXfRYX bcY3xnfdyOzI0AvCVcybHfwpgy7P+vDhcIe9C9ks2MICBsf/TJDN5kmptu4vgjFwb1Jk uag9UFqCbn/ODmCTIZh2Rc7/lQhOqLcyxB4kzRdqH4DiR/1IB/7x3Gaodgzalyj8BtnQ STbzdCd4CLO4n5UdCCnmIpwfPqXW1mQth2GeFUCXPAR4O0JP3rTT+7XVLhs1nuXcwsDs U2ynzc+pEcUI+GAMCjg+APXIfPwAgCKeOsLrSiyCO8thHOCLzHiMZZnhH0KJyQy1Utso 5MJw==
X-Gm-Message-State: AD7BkJKZIpFhqT+4qDa6yx/4En54AJySNj3U/1Na69dneTM1Y2XTMc9CUi+9b9BekrNfvn6QHY1/kgwiWkklmPyD
MIME-Version: 1.0
X-Received: by 10.107.131.169 with SMTP id n41mr525405ioi.132.1458071500088; Tue, 15 Mar 2016 12:51:40 -0700 (PDT)
Received: by 10.107.137.80 with HTTP; Tue, 15 Mar 2016 12:51:39 -0700 (PDT)
Date: Tue, 15 Mar 2016 12:51:39 -0700
Message-ID: <CAH9QtQGdZ9=XG-Qc5G6amM1pOnBse5jZndL0kExxArWXoQbhsQ@mail.gmail.com>
From: Bill Cox <waywardgeek@google.com>
To: "tls@ietf.org" <TLS@ietf.org>
Content-Type: multipart/alternative; boundary=001a113ebf84d23c8f052e1bb9c6
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/4FUxrHevLeArib3_Ev6Bx0K2FSA>
Subject: [TLS] Simple, secure 0-RTT for the masses
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 15 Mar 2016 19:51:47 -0000

I think it is worth documenting what we feel would be the simplest secure
0-RTT mode that is safe for any company to use.  I think we owe the users a
link to such a document in the TLS 1.3 spec.  Here is my attempt at
creating the simplest possible TLS 1.3 compatible safe 0-RTT scheme.  It
uses a traditional server-side session-cache.  The protocol looks like this:

During the initial 1-RTT handshake:
- create an unencrypted ticket containing only the session ID and a
"resumption count" set to 0
- send the ticket to the client

During a 0-RTT resumption handshake:
- Get the session ID from the ticket, check for a cache hit, and drop to
1-RTT if not found
- compare the resumption counts in the session state and ticket, and fall
back to 1-RTT if they do not match
- increment the resumption count in the ticket and session state
- send the updated ticket to the client

With this protocol, POST requests are allowed in 0-RTT application data,
just like TLS 1.2.  Client certs are allowed only on the initial 1-RTT
handshake, since the 0-RTT connection cannot complete proofs of possession
before the 0-RTT application requests are executed by the server.

To see that this provides roughly TLS 1.2 security, note that so long as
the protocol never has to drop to 1-RTT, it is basically equivalent to TLS
1.2 session-ID based resumption.  When we do drop down to 1-RTT, we will
replay 0-RTT application data, opening up new replay attacks.  However,
after this paper
<http://blog.valverde.me/2015/12/07/bad-life-advice/#.VucOsJMrIxN>;, I do
not believe there are any significant new replay attacks against HTTPS,
ssh, or any real protocol I can think of.  There may be weaknesses in TLS
1.3 resumption caused by the client forgetting the original connection's
security parameters, but if any are found, a client-side cache can be added.

Can this protocol be simplified by dropping the server cache?  No.  While
we can play with various server-side stateful schemes, such as strike
registers, it turns out that state on the server is _required_ for TLS 1.2
levels of security when using 0-RTT resumption.  Without server-side state,
0-RTT application data can be infinitely replayed, strong client
authentication stops working, and full PFS becomes impossible.  Note that
the above protocol does not deliver full PFS, but I claim that the modified
version described below does.

That's all I have for my attempt at "Simple, secure 0-RTT for the masses".
Below I just talk about extending the protocol to provide full PFS, which
AFAIK, the world has never implemented.

. . .

It turns out that providing full PFS over 0-RTT resumptions requires
server-side state.

Proof: Assume a server Sam has no server-side remembered session state, and
uses the same ticket decryption key to decrypt session tickets from both
Alice and Bob.  Different decryption keys are not possible because that
would require remembering which session ticket used which key.  Eve records
Alice’s resumed session, and later when Bob resumes, a server compromise
reveals Sam’s ticket decryption key to Eve.  Now Eve can decrypt Alice’s
previous resumed session since the ticket is sent from Alice to Bob before
encryption is enabled.  Clearly, the ticket contains all the information
needed to resume the encrypted session, since Sam does so without access to
any other server-side state.  Also, Alice is sending 0-RTT application data
before any new ephemeral keys can be established.  Eve simply simulates
resuming Alice's session and decrypts the 0-RTT application data, proving
that Alice's original session lacked forward secrecy.

So, stateless ticket resumption does not, and never will provide full PFS.
On the other hand, AFAIK, no one has ever provided full PFS using session
caching either.  Is there a solution?

Yes, there are multiple solutions.  For example, if TLS 1.3 were enhanced
to allow the session secrets to be re-keyed before saving the session state
to the cache, that would stop a server compromise from leaking session
secrets from past connections.  Given the current TLS 1.3 protocol as I
understand it, this is not possible, so my next-best solution is to have
the clients hold the server's session-cache decryption keys, which are
generated uniquely for each 0-RTT resumption.

In this scheme, the server stores a session-cache decryption key in the
ticket, and the ticket is not encrypted.  The protocol looks like this:

During the initial 1-RTT handshake:
- create a ticket containing the session ID, "resumption count" set to 0,
and a new session encryption key
- encrypt the session state in the cache with the session encryption key
- send the ticket to the client, and delete the session encryption key.
Note that the ticket is sent after encryption is enabled on the connection.

During a 0-RTT resumption handshake:
- check for a cache hit, and drop to 1-RTT if not found
- decrypt the cached session state with the encryption key from the ticket
- compare the resumption counts in the session-cache entry and ticket, and
fall back to 1-RTT if they do not match
- increment the resumption count
- create a new session encryption key in the ticket
- encrypt the updated session cache entry with the new session encryption
key
- send the updated ticket to the client

Did I miss anything?  Can it be simplified?

This time, when Sam's server is compromised, Eve cannot decrypt the 0-RTT
application data from Alice's previous session, because the session state
in the cache is encrypted with keys held only by the clients.  These 0-RTT
connections enjoy full PFS.

Bill