Bug 1295163 - Bloom filter for anti-replay, r=ekr NSS_TLS13_DRAFT19_BRANCH
authorMartin Thomson <martin.thomson@gmail.com>
Thu, 06 Jul 2017 09:41:13 +1000
branchNSS_TLS13_DRAFT19_BRANCH
changeset 13482 216e69dcc3c64ec405d3dc160661de8678a40acc
parent 13481 e63b527213546bbabeed4f5daae26acea340ae30
child 13484 39c3e1c06ae0be9204c9edcf166bb26693e3ad26
push id2286
push usermartin.thomson@gmail.com
push dateFri, 28 Jul 2017 02:16:06 +0000
reviewersekr
bugs1295163
Bug 1295163 - Bloom filter for anti-replay, r=ekr
gtests/ssl_gtest/bloomfilter_unittest.cc
gtests/ssl_gtest/libssl_internals.c
gtests/ssl_gtest/libssl_internals.h
gtests/ssl_gtest/manifest.mn
gtests/ssl_gtest/ssl_0rtt_unittest.cc
gtests/ssl_gtest/ssl_gtest.gyp
gtests/ssl_gtest/tls_connect.cc
lib/ssl/manifest.mn
lib/ssl/ssl.gyp
lib/ssl/ssl.h
lib/ssl/sslbloom.c
lib/ssl/sslbloom.h
lib/ssl/sslexp.h
lib/ssl/sslimpl.h
lib/ssl/sslsock.c
lib/ssl/tls13con.c
lib/ssl/tls13con.h
lib/ssl/tls13replay.c
new file mode 100644
--- /dev/null
+++ b/gtests/ssl_gtest/bloomfilter_unittest.cc
@@ -0,0 +1,108 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+extern "C" {
+#include "sslbloom.h"
+}
+
+#include "gtest_utils.h"
+
+namespace nss_test {
+
+// Some random-ish inputs to test with.  These don't result in collisions in any
+// of the configurations that are tested below.
+static const uint8_t kHashes1[] = {
+    0x79, 0x53, 0xb8, 0xdd, 0x6b, 0x98, 0xce, 0x00, 0xb7, 0xdc, 0xe8,
+    0x03, 0x70, 0x8c, 0xe3, 0xac, 0x06, 0x8b, 0x22, 0xfd, 0x0e, 0x34,
+    0x48, 0xe6, 0xe5, 0xe0, 0x8a, 0xd6, 0x16, 0x18, 0xe5, 0x48};
+static const uint8_t kHashes2[] = {
+    0xc6, 0xdd, 0x6e, 0xc4, 0x76, 0xb8, 0x55, 0xf2, 0xa4, 0xfc, 0x59,
+    0x04, 0xa4, 0x90, 0xdc, 0xa7, 0xa7, 0x0d, 0x94, 0x8f, 0xc2, 0xdc,
+    0x15, 0x6d, 0x48, 0x93, 0x9d, 0x05, 0xbb, 0x9a, 0xbc, 0xc1};
+
+typedef struct {
+  unsigned int k;
+  unsigned int bits;
+} BloomFilterConfig;
+
+class BloomFilterTest
+    : public ::testing::Test,
+      public ::testing::WithParamInterface<BloomFilterConfig> {
+ public:
+  BloomFilterTest() : filter_() {}
+
+  void SetUp() { Init(); }
+
+  void TearDown() { sslBloom_Destroy(&filter_); }
+
+ protected:
+  void Init() {
+    if (filter_.filter) {
+      sslBloom_Destroy(&filter_);
+    }
+    ASSERT_EQ(SECSuccess,
+              sslBloom_Init(&filter_, GetParam().k, GetParam().bits));
+  }
+
+  bool Check(const uint8_t* hashes) {
+    return sslBloom_Check(&filter_, hashes) ? true : false;
+  }
+
+  void Add(const uint8_t* hashes, bool expect_collision = false) {
+    EXPECT_EQ(expect_collision, sslBloom_Add(&filter_, hashes) ? true : false);
+    EXPECT_TRUE(Check(hashes));
+  }
+
+  sslBloomFilter filter_;
+};
+
+TEST_P(BloomFilterTest, InitOnly) {}
+
+TEST_P(BloomFilterTest, AddToEmpty) {
+  EXPECT_FALSE(Check(kHashes1));
+  Add(kHashes1);
+}
+
+TEST_P(BloomFilterTest, AddTwo) {
+  Add(kHashes1);
+  Add(kHashes2);
+}
+
+TEST_P(BloomFilterTest, AddOneTwice) {
+  Add(kHashes1);
+  Add(kHashes1, true);
+}
+
+TEST_P(BloomFilterTest, Zero) {
+  Add(kHashes1);
+  sslBloom_Zero(&filter_);
+  EXPECT_FALSE(Check(kHashes1));
+  EXPECT_FALSE(Check(kHashes2));
+}
+
+TEST_P(BloomFilterTest, Fill) {
+  sslBloom_Fill(&filter_);
+  EXPECT_TRUE(Check(kHashes1));
+  EXPECT_TRUE(Check(kHashes2));
+}
+
+static const BloomFilterConfig kBloomFilterConfigurations[] = {
+    {1, 1},    // 1 hash, 1 bit input - high chance of collision.
+    {1, 2},    // 1 hash, 2 bits - smaller than the basic unit size.
+    {1, 3},    // 1 hash, 3 bits - same as basic unit size.
+    {1, 4},    // 1 hash, 4 bits - 2 octets each.
+    {3, 10},   // 3 hashes over a reasonable number of bits.
+    {3, 3},    // Test that we can read multiple bits.
+    {4, 15},   // A credible filter.
+    {2, 18},   // A moderately large allocation.
+    {16, 16},  // Insane, use all of the bits from the hashes.
+    {16, 9},   // This also uses all of the bits from the hashes.
+};
+
+INSTANTIATE_TEST_CASE_P(BloomFilterConfigurations, BloomFilterTest,
+                        ::testing::ValuesIn(kBloomFilterConfigurations));
+
+}  // namespace nspr_test
--- a/gtests/ssl_gtest/libssl_internals.c
+++ b/gtests/ssl_gtest/libssl_internals.c
@@ -376,18 +376,11 @@ SECStatus SSLInt_SetSocketMaxEarlyDataSi
   ssl_GetSpecWriteLock(ss);
   ss->ssl3.crSpec->earlyDataRemaining = size;
   ss->ssl3.cwSpec->earlyDataRemaining = size;
   ssl_ReleaseSpecWriteLock(ss);
 
   return SECSuccess;
 }
 
-SECStatus SSLInt_SetTicketAgeTolerance(PRFileDesc *fd, PRUint16 tolerance) {
-  sslSocket *ss = ssl_FindSocket(fd);
-
-  if (!ss) {
-    return SECFailure;
-  }
-
-  ss->opt.ticketAgeTolerance = tolerance;
-  return SECSuccess;
+void SSLInt_RolloverAntiReplay(void) {
+  tls13_AntiReplayRollover(ssl_TimeUsec());
 }
--- a/gtests/ssl_gtest/libssl_internals.h
+++ b/gtests/ssl_gtest/libssl_internals.h
@@ -46,11 +46,11 @@ SECStatus SSLInt_SetCipherSpecChangeFunc
                                          void *arg);
 PK11SymKey *SSLInt_CipherSpecToKey(PRBool isServer, ssl3CipherSpec *spec);
 SSLCipherAlgorithm SSLInt_CipherSpecToAlgorithm(PRBool isServer,
                                                 ssl3CipherSpec *spec);
 unsigned char *SSLInt_CipherSpecToIv(PRBool isServer, ssl3CipherSpec *spec);
 void SSLInt_SetTicketLifetime(uint32_t lifetime);
 void SSLInt_SetMaxEarlyDataSize(uint32_t size);
 SECStatus SSLInt_SetSocketMaxEarlyDataSize(PRFileDesc *fd, uint32_t size);
-SECStatus SSLInt_SetTicketAgeTolerance(PRFileDesc *fd, PRUint16 tolerance);
+void SSLInt_RolloverAntiReplay(void);
 
 #endif  // ndef libssl_internals_h_
--- a/gtests/ssl_gtest/manifest.mn
+++ b/gtests/ssl_gtest/manifest.mn
@@ -7,16 +7,17 @@ DEPTH      = ../..
 MODULE = nss
 
 # These sources have access to libssl internals
 CSRCS = \
       libssl_internals.c \
       $(NULL)
 
 CPPSRCS = \
+      bloomfilter_unittest.cc \
       ssl_0rtt_unittest.cc \
       ssl_agent_unittest.cc \
       ssl_auth_unittest.cc \
       ssl_cert_ext_unittest.cc \
       ssl_ciphersuite_unittest.cc \
       ssl_custext_unittest.cc \
       ssl_damage_unittest.cc \
       ssl_dhe_unittest.cc \
--- a/gtests/ssl_gtest/ssl_0rtt_unittest.cc
+++ b/gtests/ssl_gtest/ssl_0rtt_unittest.cc
@@ -40,16 +40,105 @@ TEST_P(TlsConnectTls13, ZeroRttServerRej
   client_->Set0RttEnabled(true);
   ExpectResumption(RESUME_TICKET);
   ZeroRttSendReceive(true, false);
   Handshake();
   CheckConnected();
   SendReceive();
 }
 
+TEST_P(TlsConnectTls13, ZeroRttApparentReplayAfterRestart) {
+  // The test fixtures call SSL_SetupAntiReplay() in SetUp().  This results in
+  // 0-RTT being rejected until at least one window passes.  SetupFor0Rtt()
+  // forces a rollover of the anti-replay filters, which clears this state.
+  // Here, we do the setup manually here without that forced rollover.
+
+  ConfigureSessionCache(RESUME_BOTH, RESUME_TICKET);
+  ConfigureVersion(SSL_LIBRARY_VERSION_TLS_1_3);
+  server_->Set0RttEnabled(true);  // So we signal that we allow 0-RTT.
+  Connect();
+  SendReceive();  // Need to read so that we absorb the session ticket.
+  CheckKeys();
+
+  Reset();
+  server_->StartConnect();
+  client_->StartConnect();
+  client_->Set0RttEnabled(true);
+  server_->Set0RttEnabled(true);
+  ExpectResumption(RESUME_TICKET);
+  ZeroRttSendReceive(true, false);
+  Handshake();
+  CheckConnected();
+  SendReceive();
+}
+
+class TlsZeroRttReplayTest : public TlsConnectTls13 {
+ private:
+  class SaveFirstPacket : public PacketFilter {
+   public:
+    PacketFilter::Action Filter(const DataBuffer& input,
+                                DataBuffer* output) override {
+      if (!packet_.len() && input.len()) {
+        packet_ = input;
+      }
+      return KEEP;
+    }
+
+    const DataBuffer& packet() const { return packet_; }
+
+   private:
+    DataBuffer packet_;
+  };
+
+ protected:
+  void RunTest(bool rollover) {
+    // Run the initial handshake
+    SetupForZeroRtt();
+
+    // Now run a true 0-RTT handshake, but capture the first packet.
+    auto first_packet = std::make_shared<SaveFirstPacket>();
+    client_->SetPacketFilter(first_packet);
+    client_->Set0RttEnabled(true);
+    server_->Set0RttEnabled(true);
+    ExpectResumption(RESUME_TICKET);
+    ZeroRttSendReceive(true, true);
+    Handshake();
+    EXPECT_LT(0U, first_packet->packet().len());
+    ExpectEarlyDataAccepted(true);
+    CheckConnected();
+    SendReceive();
+
+    if (rollover) {
+      SSLInt_RolloverAntiReplay();
+    }
+
+    // Now replay that packet against the server.
+    Reset();
+    server_->StartConnect();
+    server_->Set0RttEnabled(true);
+
+    // Capture the early_data extension, which should not appear.
+    auto early_data_ext =
+        std::make_shared<TlsExtensionCapture>(ssl_tls13_early_data_xtn);
+    server_->SetPacketFilter(early_data_ext);
+    early_data_ext->EnableDecryption();
+
+    // Finally, replay the ClientHello and force the server to consume it.  Stop
+    // after the server sends its first flight; the client will not be able to
+    // complete this handshake.
+    server_->adapter()->PacketReceived(first_packet->packet());
+    server_->Handshake();
+    EXPECT_FALSE(early_data_ext->captured());
+  }
+};
+
+TEST_P(TlsZeroRttReplayTest, ZeroRttReplay) { RunTest(false); }
+
+TEST_P(TlsZeroRttReplayTest, ZeroRttReplayAfterRollover) { RunTest(true); }
+
 // Test that we don't try to send 0-RTT data when the server sent
 // us a ticket without the 0-RTT flags.
 TEST_P(TlsConnectTls13, ZeroRttOptionsSetLate) {
   ConfigureSessionCache(RESUME_BOTH, RESUME_TICKET);
   Connect();
   SendReceive();  // Need to read so that we absorb the session ticket.
   CheckKeys(ssl_kea_ecdh, ssl_auth_rsa_sign);
   Reset();
@@ -97,22 +186,25 @@ TEST_P(TlsConnectTls13, ZeroRttServerOnl
   Handshake();
   CheckConnected();
   SendReceive();
   CheckKeys();
 }
 
 // A small sleep after sending the ClientHello means that the ticket age that
 // arrives at the server is too low.  With a small tolerance for variation in
-// ticket age, the server then rejects early data.
+// ticket age (which is determined by the |window| parameter that is passed to
+// SSL_SetupAntiReplay()), the server then rejects early data.
 TEST_P(TlsConnectTls13, ZeroRttRejectOldTicket) {
   SetupForZeroRtt();
   client_->Set0RttEnabled(true);
   server_->Set0RttEnabled(true);
-  SSLInt_SetTicketAgeTolerance(server_->ssl_fd(), 1);
+  EXPECT_EQ(SECSuccess, SSL_SetupAntiReplay(1, 1, 3));
+  SSLInt_RolloverAntiReplay();  // Make sure to flush replay state.
+  SSLInt_RolloverAntiReplay();
   ExpectResumption(RESUME_TICKET);
   ZeroRttSendReceive(true, false, []() {
     PR_Sleep(PR_MillisecondsToInterval(10));
     return true;
   });
   Handshake();
   ExpectEarlyDataAccepted(false);
   CheckConnected();
@@ -136,17 +228,19 @@ TEST_P(TlsConnectTls13, ZeroRttRejectPre
   Handshake();  // Remainder of handshake
   CheckConnected();
   SendReceive();
   CheckKeys();
 
   Reset();
   client_->Set0RttEnabled(true);
   server_->Set0RttEnabled(true);
-  SSLInt_SetTicketAgeTolerance(server_->ssl_fd(), 1);
+  EXPECT_EQ(SECSuccess, SSL_SetupAntiReplay(1, 1, 3));
+  SSLInt_RolloverAntiReplay();  // Make sure to flush replay state.
+  SSLInt_RolloverAntiReplay();
   ExpectResumption(RESUME_TICKET);
   ExpectEarlyDataAccepted(false);
 
   server_->StartConnect();
   client_->StartConnect();
   ZeroRttSendReceive(true, false);
   Handshake();
   CheckConnected();
--- a/gtests/ssl_gtest/ssl_gtest.gyp
+++ b/gtests/ssl_gtest/ssl_gtest.gyp
@@ -6,16 +6,17 @@
     '../../coreconf/config.gypi',
     '../common/gtest.gypi',
   ],
   'targets': [
     {
       'target_name': 'ssl_gtest',
       'type': 'executable',
       'sources': [
+        'bloomfilter_unittest.cc',
         'libssl_internals.c',
         'selfencrypt_unittest.cc',
         'ssl_0rtt_unittest.cc',
         'ssl_agent_unittest.cc',
         'ssl_auth_unittest.cc',
         'ssl_cert_ext_unittest.cc',
         'ssl_ciphersuite_unittest.cc',
         'ssl_custext_unittest.cc',
--- a/gtests/ssl_gtest/tls_connect.cc
+++ b/gtests/ssl_gtest/tls_connect.cc
@@ -176,16 +176,17 @@ void TlsConnectTestBase::ClearServerCach
   SSL_ConfigServerSessionIDCache(1024, 0, 0, g_working_dir_path.c_str());
 }
 
 void TlsConnectTestBase::SetUp() {
   SSL_ConfigServerSessionIDCache(1024, 0, 0, g_working_dir_path.c_str());
   SSLInt_ClearSelfEncryptKey();
   SSLInt_SetTicketLifetime(30);
   SSLInt_SetMaxEarlyDataSize(1024);
+  SSL_SetupAntiReplay(1 * PR_USEC_PER_SEC, 1, 3);
   ClearStats();
   Init();
 }
 
 void TlsConnectTestBase::TearDown() {
   client_ = nullptr;
   server_ = nullptr;
 
@@ -546,16 +547,19 @@ void TlsConnectTestBase::CheckSrtp() con
 void TlsConnectTestBase::SendReceive() {
   client_->SendData(50);
   server_->SendData(50);
   Receive(50);
 }
 
 // Do a first connection so we can do 0-RTT on the second one.
 void TlsConnectTestBase::SetupForZeroRtt() {
+  // If we don't do this, then all 0-RTT attempts will be rejected.
+  SSLInt_RolloverAntiReplay();
+
   ConfigureSessionCache(RESUME_BOTH, RESUME_TICKET);
   ConfigureVersion(SSL_LIBRARY_VERSION_TLS_1_3);
   server_->Set0RttEnabled(true);  // So we signal that we allow 0-RTT.
   Connect();
   SendReceive();  // Need to read so that we absorb the session ticket.
   CheckKeys();
 
   Reset();
--- a/lib/ssl/manifest.mn
+++ b/lib/ssl/manifest.mn
@@ -19,16 +19,17 @@ MODULE = nss
 MAPFILE = $(OBJDIR)/ssl.def
 
 CSRCS = \
         dtlscon.c \
         prelib.c \
         ssl3con.c \
         ssl3gthr.c \
         sslauth.c \
+        sslbloom.c \
         sslcon.c \
         ssldef.c \
         sslencode.c \
         sslenum.c \
         sslerr.c \
         sslerrstrs.c \
         sslinit.c \
         ssl3ext.c \
@@ -44,16 +45,17 @@ CSRCS = \
         authcert.c \
         cmpcert.c \
         selfencrypt.c \
         sslinfo.c \
         ssl3ecc.c \
         tls13con.c \
         tls13exthandle.c \
         tls13hkdf.c \
+        tls13replay.c \
         sslcert.c \
         sslgrp.c \
         $(NULL)
 
 LIBRARY_NAME = ssl
 LIBRARY_VERSION = 3
 
 # This part of the code, including all sub-dirs, can be optimized for size
--- a/lib/ssl/ssl.gyp
+++ b/lib/ssl/ssl.gyp
@@ -16,16 +16,17 @@
         'prelib.c',
         'selfencrypt.c',
         'ssl3con.c',
         'ssl3ecc.c',
         'ssl3ext.c',
         'ssl3exthandle.c',
         'ssl3gthr.c',
         'sslauth.c',
+        'sslbloom.c',
         'sslcert.c',
         'sslcon.c',
         'ssldef.c',
         'sslencode.c',
         'sslenum.c',
         'sslerr.c',
         'sslerrstrs.c',
         'sslgrp.c',
@@ -37,16 +38,17 @@
         'sslsecur.c',
         'sslsnce.c',
         'sslsock.c',
         'ssltrace.c',
         'sslver.c',
         'tls13con.c',
         'tls13exthandle.c',
         'tls13hkdf.c',
+        'tls13replay.c',
       ],
       'conditions': [
         [ 'OS=="win"', {
           'sources': [
             'win32err.c',
           ],
           'defines': [
             'IN_LIBSSL',
--- a/lib/ssl/ssl.h
+++ b/lib/ssl/ssl.h
@@ -1371,16 +1371,17 @@ extern const char *NSSSSL_GetVersion(voi
  * value for second argument (error), or if SSL_AuthCertificateComplete returns
  * anything other than SECSuccess, then the application should close the
  * connection.
  */
 SSL_IMPORT SECStatus SSL_AuthCertificateComplete(PRFileDesc *fd,
                                                  PRErrorCode error);
 
 /*
+<<<<<<< dest
  * SSL_GetExtensionSupport() returns whether NSS supports a particular TLS extension.
  *
  * - ssl_ext_none indicates that NSS does not support the extension and
  *   extension hooks can be installed.
  *
  * - ssl_ext_native indicates that NSS supports the extension natively, but
  *   allows an application to override that support and install its own
  *   extension hooks.
new file mode 100644
--- /dev/null
+++ b/lib/ssl/sslbloom.c
@@ -0,0 +1,94 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * A bloom filter.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "sslbloom.h"
+#include "prnetdb.h"
+#include "secport.h"
+
+static inline unsigned int
+sslBloom_Size(unsigned int bits)
+{
+    return (bits >= 3) ? (1 << (bits - 3)) : 1;
+}
+
+SECStatus
+sslBloom_Init(sslBloomFilter *filter, unsigned int k, unsigned int bits)
+{
+    PORT_Assert(filter);
+    PORT_Assert(bits > 0);
+    PORT_Assert(bits <= sizeof(PRUint32) * 8);
+    PORT_Assert(k > 0);
+
+    filter->filter = PORT_ZNewArray(PRUint8, sslBloom_Size(bits));
+    if (!filter->filter) {
+        return SECFailure; /* Error code already set. */
+    }
+
+    filter->k = k;
+    filter->bits = bits;
+    return SECSuccess;
+}
+
+void
+sslBloom_Zero(sslBloomFilter *filter)
+{
+    PORT_Memset(filter->filter, 0, sslBloom_Size(filter->bits));
+}
+
+void
+sslBloom_Fill(sslBloomFilter *filter)
+{
+    PORT_Memset(filter->filter, 0xff, sslBloom_Size(filter->bits));
+}
+
+static PRBool
+sslBloom_AddOrCheck(sslBloomFilter *filter, const PRUint8 *hashes, PRBool add)
+{
+    unsigned int iteration;
+    unsigned int bitIndex;
+    PRUint32 tmp = 0;
+    PRUint8 mask;
+    unsigned int bytes = (filter->bits + 7) / 8;
+    unsigned int shift = (bytes * 8) - filter->bits;
+    PRBool found = PR_TRUE;
+
+    PORT_Assert(bytes <= sizeof(unsigned int));
+
+    for (iteration = 0; iteration < filter->k; ++iteration) {
+        PORT_Memcpy(((PRUint8 *)&tmp) + (sizeof(tmp) - bytes),
+                    hashes, bytes);
+        hashes += bytes;
+        bitIndex = PR_ntohl(tmp) >> shift;
+
+        mask = 1 << (bitIndex % 8);
+        found = found && filter->filter[bitIndex / 8] & mask;
+        if (add) {
+            filter->filter[bitIndex / 8] |= mask;
+        }
+    }
+    return found;
+}
+
+PRBool
+sslBloom_Add(sslBloomFilter *filter, const PRUint8 *hashes)
+{
+    return sslBloom_AddOrCheck(filter, hashes, PR_TRUE);
+}
+
+PRBool
+sslBloom_Check(sslBloomFilter *filter, const PRUint8 *hashes)
+{
+    return sslBloom_AddOrCheck(filter, hashes, PR_FALSE);
+}
+
+void
+sslBloom_Destroy(sslBloomFilter *filter)
+{
+    PORT_Free(filter->filter);
+    PORT_Memset(filter, 0, sizeof(*filter));
+}
new file mode 100644
--- /dev/null
+++ b/lib/ssl/sslbloom.h
@@ -0,0 +1,32 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * A bloom filter.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef __sslbloom_h_
+#define __sslbloom_h_
+
+#include "prtypes.h"
+#include "seccomon.h"
+
+typedef struct sslBloomFilterStr {
+    unsigned int k;    /* The number of hashes. */
+    unsigned int bits; /* The number of bits in each hash: bits = log2(m) */
+    PRUint8 *filter;   /* The filter itself. */
+} sslBloomFilter;
+
+SECStatus sslBloom_Init(sslBloomFilter *filter, unsigned int k, unsigned int bits);
+void sslBloom_Zero(sslBloomFilter *filter);
+void sslBloom_Fill(sslBloomFilter *filter);
+/* Add the given hashes to the filter.  It's the caller's responsibility to
+ * ensure that there is at least |ceil(k*bits/8)| bytes of data available in
+ * |hashes|. Returns PR_TRUE if the entry was already present or it was likely
+ * to be present. */
+PRBool sslBloom_Add(sslBloomFilter *filter, const PRUint8 *hashes);
+PRBool sslBloom_Check(sslBloomFilter *filter, const PRUint8 *hashes);
+void sslBloom_Destroy(sslBloomFilter *filter);
+
+#endif /* __sslbloom_h_ */
--- a/lib/ssl/sslexp.h
+++ b/lib/ssl/sslexp.h
@@ -17,11 +17,77 @@ SEC_BEGIN_PROTOS
  * future NSS versions. Code that uses these functions needs to safeguard
  * against the function not being available. */
 
 #define SSL_EXPERIMENTAL_API(name, arglist, args)                   \
     (SSL_GetExperimentalAPI(name)                                   \
          ? ((SECStatus(*) arglist)SSL_GetExperimentalAPI(name))args \
          : SECFailure)
 
+/*
+ * Setup the anti-replay buffer for supporting 0-RTT in TLS 1.3 on servers.
+ *
+ * To use 0-RTT on a server, you must call this function.  Failing to call this
+ * function will result in all 0-RTT being rejected.  Connections will complete,
+ * but early data will be rejected.
+ *
+ * NSS uses a Bloom filter to track the ClientHello messages that it receives
+ * (specifically, it uses the PSK binder).  This function initializes a pair of
+ * Bloom filters.  The two filters are alternated over time, with new
+ * ClientHello messages recorded in the current filter and, if they are not
+ * already present, being checked against the previous filter.  If the
+ * ClientHello is found, then early data is rejected, but the handshake is
+ * allowed to proceed.
+ *
+ * The false-positive probability of Bloom filters means that some valid
+ * handshakes will be marked as potential replays.  Early data will be rejected
+ * for a false positive.  To minimize this and to allow a trade-off of space
+ * against accuracy, the size of the Bloom filter can be set by this function.
+ *
+ * The first tuning parameter to consider is |window|, which determines the
+ * window over which ClientHello messages will be tracked.  This also causes
+ * early data to be rejected if a ClientHello contains a ticket age parameter
+ * that is outside of this window (see Section 4.2.10.4 of
+ * draft-ietf-tls-tls13-20 for details).  Set |window| to account for any
+ * potential sources of clock error.  |window| is the entire width of the
+ * window, which is symmetrical.  Therefore to allow 5 seconds of clock error in
+ * both directions, set the value to 10 seconds (i.e., 10 * PR_USEC_PER_SEC).
+ *
+ * After calling this function, early data will be rejected until |window|
+ * elapses.  This prevents replay across crashes and restarts.  Only call this
+ * function once to avoid inadvertently disabling 0-RTT (use PR_CallOnce() to
+ * avoid this problem).
+ *
+ * The primary tuning parameter is |bits| which determines the amount of memory
+ * allocated to each Bloom filter.  NSS will allocate two Bloom filters, each
+ * |2^(bits - 3)| octets in size.  The value of |bits| is primarily driven by
+ * the number of connections that are expected in any time window.  Note that
+ * this needs to account for there being two filters both of which have
+ * (presumably) independent false positive rates.  The following formulae can be
+ * used to find a value of |bits| and |k| given a chosen false positive
+ * probability |p| and the number of requests expected in a given window |n|:
+ *
+ *   bits = log2(n) + log2(-ln(1 - sqrt(1 - p))) + 1.0575327458897952
+ *   k = -log2(p)
+ *
+ * ... where log2 and ln are base 2 and e logarithms respectively.  For a target
+ * false positive rate of 1% and 1000 handshake attempts, this produces bits=14
+ * and k=7.  This results in two Bloom filters that are 2kB each in size.  Note
+ * that rounding |k| and |bits| up causes the false positive probability for
+ * these values to be a much lower 0.123%.
+ *
+ * IMPORTANT: This anti-replay scheme has several weaknesses.  See the TLS 1.3
+ * specification for the details of the generic problems with this technique.
+ *
+ * In addition to the generic anti-replay weaknesses, the state that the server
+ * maintains is in local memory only.  Servers that operate in a cluster, even
+ * those that use shared memory for tickets, will not share anti-replay state.
+ * Early data can be replayed at least once with every server instance that will
+ * accept tickets that are encrypted with the same key.
+ */
+#define SSL_SetupAntiReplay(window, k, bits)                                    \
+    SSL_EXPERIMENTAL_API("SSL_SetupAntiReplay",                                 \
+                         (PRTime _window, unsigned int _k, unsigned int _bits), \
+                         (window, k, bits))
+
 SEC_END_PROTOS
 
 #endif /* __sslexp_h_ */
--- a/lib/ssl/sslimpl.h
+++ b/lib/ssl/sslimpl.h
@@ -257,20 +257,16 @@ typedef struct {
 /* MAX_SIGNATURE_SCHEMES allows for all the values we support. */
 #define MAX_SIGNATURE_SCHEMES 15
 
 typedef struct sslOptionsStr {
     /* If SSL_SetNextProtoNego has been called, then this contains the
      * list of supported protocols. */
     SECItem nextProtoNego;
 
-    /* The amount of tolerance to allow for relative clock drift and network
-     * delays when validating the age of a TLS 1.3. */
-    PRUint16 ticketAgeTolerance;
-
     unsigned int useSecurity : 1;
     unsigned int useSocks : 1;
     unsigned int requestCertificate : 1;
     unsigned int requireCertificate : 2;
     unsigned int handshakeAsClient : 1;
     unsigned int handshakeAsServer : 1;
     unsigned int noCache : 1;
     unsigned int fdx : 1;
--- a/lib/ssl/sslsock.c
+++ b/lib/ssl/sslsock.c
@@ -49,17 +49,16 @@ static const sslSocketOps ssl_secure_ops
                                              ssl_DefGetsockname
 };
 
 /*
 ** default settings for socket enables
 */
 static sslOptions ssl_defaults = {
     { siBuffer, NULL, 0 }, /* nextProtoNego */
-    1000,                  /* ticketAgeTolerance (1s) */
     PR_TRUE,               /* useSecurity        */
     PR_FALSE,              /* useSocks           */
     PR_FALSE,              /* requestCertificate */
     2,                     /* requireCertificate */
     PR_FALSE,              /* handshakeAsClient  */
     PR_FALSE,              /* handshakeAsServer  */
     PR_FALSE,              /* noCache            */
     PR_FALSE,              /* fdx                */
@@ -3898,16 +3897,17 @@ SSL_CanBypass(CERTCertificate *cert, SEC
     {                      \
         "SSL_" #n, SSL_##n \
     }
 struct {
     const char *const name;
     void *function;
 } ssl_experimental_functions[] = {
 #ifndef SSL_DISABLE_EXPERIMENTAL_API
+    EXP(SetupAntiReplay),
 #endif
     { "", NULL }
 };
 #undef EXP
 #undef PUB
 
 void *
 SSL_GetExperimentalAPI(const char *name)
--- a/lib/ssl/tls13con.c
+++ b/lib/ssl/tls13con.c
@@ -960,18 +960,16 @@ tls13_CanResume(sslSocket *ss, const ssl
     }
 
     return PR_TRUE;
 }
 
 static PRBool
 tls13_CanNegotiateZeroRtt(sslSocket *ss, const sslSessionID *sid)
 {
-    PRInt32 timeDelta;
-
     PORT_Assert(ss->ssl3.hs.zeroRttState == ssl_0rtt_sent);
 
     if (!sid)
         return PR_FALSE;
     PORT_Assert(ss->statelessResume);
     if (!ss->statelessResume)
         return PR_FALSE;
     if (ss->ssl3.hs.cipher_suite != sid->u.ssl3.cipherSuite)
@@ -979,24 +977,17 @@ tls13_CanNegotiateZeroRtt(sslSocket *ss,
     if (!ss->opt.enable0RttData)
         return PR_FALSE;
     if (!(sid->u.ssl3.locked.sessionTicket.flags & ticket_allow_early_data))
         return PR_FALSE;
     if (SECITEM_CompareItem(&ss->xtnData.nextProto,
                             &sid->u.ssl3.alpnSelection) != 0)
         return PR_FALSE;
 
-    /* Calculate the difference between the client's view of the age of the
-     * ticket (in |ss->xtnData.ticketAge|) and the server's view, which we now
-     * calculate.  The result should be close to zero.  timeDelta is signed to
-     * make the comparisons below easier. */
-    timeDelta = ss->xtnData.ticketAge -
-                ((ssl_TimeUsec() - sid->creationTime) / PR_USEC_PER_MSEC);
-    if (timeDelta > ss->opt.ticketAgeTolerance ||
-        timeDelta < (-1 * ss->opt.ticketAgeTolerance)) {
+    if (tls13_IsReplay(ss, sid)) {
         return PR_FALSE;
     }
 
     return PR_TRUE;
 }
 
 /* Called from tls13_HandleClientHelloPart2 to update the state of 0-RTT handling.
  *
--- a/lib/ssl/tls13con.h
+++ b/lib/ssl/tls13con.h
@@ -89,9 +89,14 @@ PRInt32 tls13_Read0RttData(sslSocket *ss
 SECStatus tls13_HandleEarlyApplicationData(sslSocket *ss, sslBuffer *origBuf);
 PRBool tls13_ClientAllow0Rtt(const sslSocket *ss, const sslSessionID *sid);
 PRUint16 tls13_EncodeDraftVersion(SSL3ProtocolVersion version);
 PRUint16 tls13_DecodeDraftVersion(PRUint16 version);
 SECStatus tls13_NegotiateVersion(sslSocket *ss,
                                  const TLSExtension *supported_versions);
 SECStatus tls13_SendNewSessionTicket(sslSocket *ss);
 
+PRBool tls13_IsReplay(const sslSocket *ss, const sslSessionID *sid);
+void tls13_AntiReplayRollover(PRTime now);
+SECStatus SSLExp_SetupAntiReplay(PRTime window, unsigned int k,
+                                 unsigned int bits);
+
 #endif /* __tls13con_h_ */
new file mode 100644
--- /dev/null
+++ b/lib/ssl/tls13replay.c
@@ -0,0 +1,276 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * Anti-replay measures for TLS 1.3.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "nss.h"      /* for NSS_RegisterShutdown */
+#include "nssilock.h" /* for PZMonitor */
+#include "pk11pub.h"
+#include "prinit.h" /* for PR_CallOnce */
+#include "prmon.h"
+#include "prtime.h"
+#include "secerr.h"
+#include "ssl.h"
+#include "sslbloom.h"
+#include "sslimpl.h"
+#include "tls13hkdf.h"
+
+static struct {
+    /* Used to ensure that we only initialize the cleanup function once. */
+    PRCallOnceType init;
+    /* Used to serialize access to the filters. */
+    PZMonitor *lock;
+    /* The filters, use of which alternates. */
+    sslBloomFilter filters[2];
+    /* Which of the two filters is active (0 or 1). */
+    PRUint8 current;
+    /* The time that we will next update. */
+    PRTime nextUpdate;
+    /* The width of the window; i.e., the period of updates. */
+    PRTime window;
+    /* This key ensures that the bloom filter index is unpredictable. */
+    PK11SymKey *key;
+} ssl_anti_replay;
+
+/* Clear the current state and free any resources we allocated. The signature
+ * here is odd to allow this to be called during shutdown. */
+static SECStatus
+tls13_AntiReplayReset(void *appData, void *nssData)
+{
+    if (ssl_anti_replay.key) {
+        PK11_FreeSymKey(ssl_anti_replay.key);
+        ssl_anti_replay.key = NULL;
+    }
+    if (ssl_anti_replay.lock) {
+        PZ_DestroyMonitor(ssl_anti_replay.lock);
+        ssl_anti_replay.lock = NULL;
+    }
+    sslBloom_Destroy(&ssl_anti_replay.filters[0]);
+    sslBloom_Destroy(&ssl_anti_replay.filters[1]);
+    return SECSuccess;
+}
+
+static PRStatus
+tls13_AntiReplayInit(void)
+{
+    SECStatus rv = NSS_RegisterShutdown(tls13_AntiReplayReset, NULL);
+    if (rv != SECSuccess) {
+        return PR_FAILURE;
+    }
+    return PR_SUCCESS;
+}
+
+static SECStatus
+tls13_AntiReplayKeyGen()
+{
+    PRUint8 buf[32];
+    SECItem keyItem = { siBuffer, buf, sizeof(buf) };
+    PK11SlotInfo *slot;
+    SECStatus rv;
+
+    slot = PK11_GetInternalSlot();
+    if (!slot) {
+        PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
+        return SECFailure;
+    }
+    rv = PK11_GenerateRandomOnSlot(slot, buf, sizeof(buf));
+    if (rv != SECSuccess) {
+        goto loser;
+    }
+
+    ssl_anti_replay.key = PK11_ImportSymKey(slot, CKM_NSS_HKDF_SHA256,
+                                            PK11_OriginUnwrap, CKA_DERIVE,
+                                            &keyItem, NULL);
+    if (!ssl_anti_replay.key) {
+        goto loser;
+    }
+
+    PK11_FreeSlot(slot);
+    return SECSuccess;
+
+loser:
+    PK11_FreeSlot(slot);
+    return SECFailure;
+}
+
+/* Set a limit on the combination of number of hashes and bits in each hash. */
+#define SSL_MAX_BLOOM_FILTER_SIZE 64
+
+/*
+ * The structures created by this function can be called concurrently on
+ * multiple threads if the server is multi-threaded.  A monitor is used to
+ * ensure that only one thread can access the structures that change over time,
+ * but no such guarantee is provided for configuration data.
+ *
+ * Functions that read from static configuration data depend on there being a
+ * memory barrier between the setup and use of this function.
+ */
+SECStatus
+SSLExp_SetupAntiReplay(PRTime window, unsigned int k, unsigned int bits)
+{
+    SECStatus rv;
+
+    if (k == 0 || bits == 0) {
+        PORT_SetError(SEC_ERROR_INVALID_ARGS);
+        return SECFailure;
+    }
+    if ((k * (bits + 7) / 8) > SSL_MAX_BLOOM_FILTER_SIZE) {
+        PORT_SetError(SEC_ERROR_INVALID_ARGS);
+        return SECFailure;
+    }
+
+    if (PR_SUCCESS != PR_CallOnce(&ssl_anti_replay.init,
+                                  tls13_AntiReplayInit)) {
+        PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
+        return SECFailure;
+    }
+
+    (void)tls13_AntiReplayReset(NULL, NULL);
+
+    ssl_anti_replay.lock = PZ_NewMonitor(nssILockSSL);
+    if (!ssl_anti_replay.lock) {
+        goto loser; /* Code already set. */
+    }
+
+    rv = tls13_AntiReplayKeyGen();
+    if (rv != SECSuccess) {
+        goto loser; /* Code already set. */
+    }
+
+    rv = sslBloom_Init(&ssl_anti_replay.filters[0], k, bits);
+    if (rv != SECSuccess) {
+        goto loser; /* Code already set. */
+    }
+    rv = sslBloom_Init(&ssl_anti_replay.filters[1], k, bits);
+    if (rv != SECSuccess) {
+        goto loser; /* Code already set. */
+    }
+    /* When starting out, ensure that 0-RTT is not accepted until the window is
+     * updated.  A ClientHello might have been accepted prior to a restart. */
+    sslBloom_Fill(&ssl_anti_replay.filters[1]);
+
+    ssl_anti_replay.current = 0;
+    ssl_anti_replay.nextUpdate = ssl_TimeUsec() + window;
+    ssl_anti_replay.window = window;
+    return SECSuccess;
+
+loser:
+    (void)tls13_AntiReplayReset(NULL, NULL);
+    return SECFailure;
+}
+
+/* This is exposed to tests.  Though it could, this doesn't take the lock on the
+ * basis that those tests use thread confinement. */
+void
+tls13_AntiReplayRollover(PRTime now)
+{
+    ssl_anti_replay.current ^= 1;
+    ssl_anti_replay.nextUpdate = now + ssl_anti_replay.window;
+    sslBloom_Zero(ssl_anti_replay.filters + ssl_anti_replay.current);
+}
+
+static void
+tls13_AntiReplayUpdate()
+{
+    PRTime now;
+
+    PR_ASSERT_CURRENT_THREAD_IN_MONITOR(ssl_anti_replay.lock);
+
+    now = ssl_TimeUsec();
+    if (now < ssl_anti_replay.nextUpdate) {
+        return;
+    }
+
+    tls13_AntiReplayRollover(now);
+}
+
+PRBool
+tls13_InWindow(const sslSocket *ss, const sslSessionID *sid)
+{
+    PRInt32 timeDelta;
+
+    /* Calculate the difference between the client's view of the age of the
+     * ticket (in |ss->xtnData.ticketAge|) and the server's view, which we now
+     * calculate.  The result should be close to zero.  timeDelta is signed to
+     * make the comparisons below easier. */
+    timeDelta = ss->xtnData.ticketAge -
+                ((ssl_TimeUsec() - sid->creationTime) / PR_USEC_PER_MSEC);
+
+    /* Only allow the time delta to be at most half of our window.  This is
+     * symmetrical, though it doesn't need to be; this assumes that clock errors
+     * on server and client will tend to cancel each other out.
+     *
+     * There are two anti-replay filters that roll over each window.  In the
+     * worst case, immediately after a rollover of the filters, we only have a
+     * single window worth of recorded 0-RTT attempts.  Thus, the period in
+     * which we can accept 0-RTT is at most one window wide.  This uses PR_ABS()
+     * and half the window so that the first attempt can be up to half a window
+     * early and then replays will be caught until the attempts are half a
+     * window late.
+     *
+     * For example, a 0-RTT attempt arrives early, but near the end of window 1.
+     * The attempt is then recorded in window 1.  Rollover to window 2 could
+     * occur immediately afterwards.  Window 1 is still checked for new 0-RTT
+     * attempts for the remainder of window 2.  Therefore, attempts to replay
+     * are detected because the value is recorded in window 1.  When rollover
+     * occurs again, window 1 is erased and window 3 instated.  If we allowed an
+     * attempt to be late by more than half a window, then this check would not
+     * prevent the same 0-RTT attempt from being accepted during window 1 and
+     * later window 3.
+     */
+    return PR_ABS(timeDelta) < (ssl_anti_replay.window / 2);
+}
+
+/* Checks for a duplicate in the two filters we have.  Performs maintenance on
+ * the filters as a side-effect. This only detects a probable replay, it's
+ * possible that this will return true when the 0-RTT attempt is not genuinely a
+ * replay.  In that case, we reject 0-RTT unnecessarily, but that's OK because
+ * no client expects 0-RTT to work every time. */
+PRBool
+tls13_IsReplay(const sslSocket *ss, const sslSessionID *sid)
+{
+    PRBool replay;
+    unsigned int size;
+    PRUint8 index;
+    SECStatus rv;
+    static const char *label = "tls13 anti-replay";
+    PRUint8 buf[SSL_MAX_BLOOM_FILTER_SIZE];
+
+    /* If SSL_SetupAntiReplay hasn't been called, then treat all attempts at
+     * 0-RTT as a replay. */
+    if (!ssl_anti_replay.init.initialized) {
+        return PR_TRUE;
+    }
+
+    if (!tls13_InWindow(ss, sid)) {
+        return PR_TRUE;
+    }
+
+    size = ssl_anti_replay.filters[0].k *
+           (ssl_anti_replay.filters[0].bits + 7) / 8;
+    PORT_Assert(size <= SSL_MAX_BLOOM_FILTER_SIZE);
+    rv = tls13_HkdfExpandLabelRaw(ssl_anti_replay.key, ssl_hash_sha256,
+                                  ss->xtnData.pskBinder.data,
+                                  ss->xtnData.pskBinder.len,
+                                  label, strlen(label),
+                                  buf, size);
+    if (rv != SECSuccess) {
+        return PR_TRUE;
+    }
+
+    PZ_EnterMonitor(ssl_anti_replay.lock);
+    tls13_AntiReplayUpdate();
+
+    index = ssl_anti_replay.current;
+    replay = sslBloom_Add(&ssl_anti_replay.filters[index], buf);
+    if (!replay) {
+        replay = sslBloom_Check(&ssl_anti_replay.filters[index ^ 1],
+                                buf);
+    }
+
+    PZ_ExitMonitor(ssl_anti_replay.lock);
+    return replay;
+}