[TLS] Limiting replay time frame of 0-RTT data

Kyle Nekritz <knekritz@fb.com> Fri, 11 March 2016 20:21 UTC

Return-Path: <prvs=2878d19334=knekritz@fb.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 16C8612DB38 for <tls@ietfa.amsl.com>; Fri, 11 Mar 2016 12:21:17 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.72
X-Spam-Status: No, score=-2.72 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, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=fb.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id JksWMjoQBLd5 for <tls@ietfa.amsl.com>; Fri, 11 Mar 2016 12:21:14 -0800 (PST)
Received: from mx0b-00082601.pphosted.com (mx0b-00082601.pphosted.com []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9936912DB3D for <tls@ietf.org>; Fri, 11 Mar 2016 12:21:14 -0800 (PST)
Received: from pps.filterd (m0089730.ppops.net []) by m0089730.ppops.net ( with SMTP id u2BKIUMp017271 for <tls@ietf.org>; Fri, 11 Mar 2016 12:21:09 -0800
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=fb.com; h=from : to : subject : date : message-id : content-type : mime-version; s=facebook; bh=cWjnPF7zRlmmTNJlYX4tLNc6lUKwnsqqW4TGK/NN8Bw=; b=BWNhWInEt6sPsqMXaZj5VlNNsGETAfDgWwXDWVuOFbWxXoaPM7EHFmiBnCC2wz617Rl6 OIHOl1hPadm4pwMl6nduXh7dxrpEk5RrZc2CZHxCq3ia7yj+jolgIvRz5CxT4X9VcNiw lUCg1sOAJWwNZnDQEYjOBibQvhINrNsE9W4=
Received: from mail.thefacebook.com ([]) by m0089730.ppops.net with ESMTP id 21kg4mn0vr-1 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT) for <tls@ietf.org>; Fri, 11 Mar 2016 12:21:09 -0800
Received: from PRN-MBX02-1.TheFacebook.com ([]) by PRN-CHUB14.TheFacebook.com ([fe80::5977:3d0b:700b:8bb%12]) with mapi id 14.03.0248.002; Fri, 11 Mar 2016 12:21:08 -0800
From: Kyle Nekritz <knekritz@fb.com>
To: "tls@ietf.org" <tls@ietf.org>
Thread-Topic: [TLS] Limiting replay time frame of 0-RTT data
Thread-Index: AdF70pHzy4ySAXIcRV+Hke2bem/g9A==
Date: Fri, 11 Mar 2016 20:21:07 +0000
Message-ID: <8A79BFEDF6986C46996566F91BB63C860D64EA3F@PRN-MBX02-1.TheFacebook.com>
Accept-Language: en-US
Content-Language: en-US
x-originating-ip: []
Content-Type: multipart/alternative; boundary="_000_8A79BFEDF6986C46996566F91BB63C860D64EA3FPRNMBX021TheFac_"
MIME-Version: 1.0
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2016-03-11_10:, , signatures=0
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/K-PmKrP6Df_qIVq_BTielgtQwUY>
Subject: [TLS] Limiting replay time frame of 0-RTT data
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: Fri, 11 Mar 2016 20:21:17 -0000

Similar to the earlier discussion on 0.5-RTT data, I'm concerned with the long term ability to replay captured 0-RTT early data, and the attack vectors that it opens up. For example, take a GET request for an image to a CDN. This is a request that seems completely idempotent, and that applications will surely want to send as 0-RTT data. However, this request can result in a few things happening:
    1) Resource unavailable
    2) Resource cached locally at edge cluster
    3) Cache miss, resource must be fetched from origin data center
#1 can easily be differentiated by the length of the 0.5-RTT response data, allowing an attacker to determine when a resource has been deleted/modified. #2 and #3 can also be easily differentiated by the timing of the response. This opens up the following attack: if an attacker knows a client has requested a resource X_i in the attacker-known set {X_1, X_2, ..., X_n}, an attacker can do the following:
    1) wait for the CDN cache to be evicted
    2) request {X_1, X_2, ..., X_(n/2)} to warm the cache
    3) replay the captured client early data (the request for X_i)
    4) determine, based on the timing of the response, whether it resulted in a cache hit or miss
    5) repeat with set {X_1, X_2, ..., X_(n/2)} or {X_(n/2 + 1), X_(n/2 + 2), ..., X_n} depending on the result
This particular binary search example is a little contrived and requires that no-one else is requesting any resource in the set, however I think it is representative of a significant new attack vector that allowing long-term replay of captured early data will open up, even if 0-RTT is only used for seemingly simple requests without TLS client authentication. This is a much different threat than very short-term replay, which is already somewhat possible on any TLS protocol if clients retry failed requests.

Given this, I think it is worth attempting to limit the time frame that captured early data is useful to an attacker. This obviously doesn't prevent replay, but it can mitigate a lot of attacks that long-term replay would open up. This can be done by including a client time stamp along with early data, so that servers can choose to either ignore the early data, or to delay the 0.5-RTT response to 1.5-RTT if the time stamp is far off. This cuts down the time from days (until the server config/session ticket key is rotated) to minutes or seconds.

Including the client time also makes a client random strike register possible without requiring an unreasonably large amount of server-side state.

I am aware that client time had previously been removed from the client random, primarily due to fingerprinting concerns, however these concerns can be mitigated by
1) clients can choose to not include their time (or to include a random time), with only the risk of their .5-RTT data being delayed
2) placing the time stamp in an encrypted extension, so that it is not visible to eavesdroppers

Note: it's also useful for the server to know which edge cluster the early data was intended for, however this is already possible in the current draft. In ECDHE 0-RTT server configs can be segmented by cluster, and with tickets, the server can store cluster information in the opaque ticket.