external/boringssl: Sync to 9770532afa91dd1441ba0d3e9d4bb86d7e501f19.

am: a450c925ed

Change-Id: Id0808707269914644df205b82355d45f4d5911b3

13 files changed, 330 insertions, 148 deletions

diff --git a/BORINGSSL_REVISION b/BORINGSSL_REVISION
index ed9a1831..509a8a9e 100644
--- a/BORINGSSL_REVISION
+++ b/BORINGSSL_REVISION
@@ -1 +1 @@
-915c121bb5d424e09bf05c3aabf172a44e958e28
+9770532afa91dd1441ba0d3e9d4bb86d7e501f19
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 95e2590f..78623075 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -355,8 +355,8 @@ endif()
 
 # Add minimal googletest targets. The provided one has many side-effects, and
 # googletest has a very straightforward build.
-add_library(gtest third_party/googletest/src/gtest-all.cc)
-target_include_directories(gtest PRIVATE third_party/googletest)
+add_library(boringssl_gtest third_party/googletest/src/gtest-all.cc)
+target_include_directories(boringssl_gtest PRIVATE third_party/googletest)
 
 include_directories(third_party/googletest/include)
 
diff --git a/src/crypto/CMakeLists.txt b/src/crypto/CMakeLists.txt
index 640f2069..469838a1 100644
--- a/src/crypto/CMakeLists.txt
+++ b/src/crypto/CMakeLists.txt
@@ -267,11 +267,11 @@ add_executable(
   x509v3/v3name_test.cc
 
   $<TARGET_OBJECTS:crypto_test_data>
-  $<TARGET_OBJECTS:gtest_main>
+  $<TARGET_OBJECTS:boringssl_gtest_main>
   $<TARGET_OBJECTS:test_support>
 )
 
-target_link_libraries(crypto_test crypto gtest)
+target_link_libraries(crypto_test crypto boringssl_gtest)
 if (WIN32)
   target_link_libraries(crypto_test ws2_32)
 endif()
diff --git a/src/crypto/bytestring/bytestring_test.cc b/src/crypto/bytestring/bytestring_test.cc
index 1969e73e..10eac69c 100644
--- a/src/crypto/bytestring/bytestring_test.cc
+++ b/src/crypto/bytestring/bytestring_test.cc
@@ -981,3 +981,73 @@ TEST(CBBTest, AddOIDFromText) {
     EXPECT_FALSE(text);
   }
 }
+
+TEST(CBBTest, FlushASN1SetOf) {
+  const struct {
+    std::vector<uint8_t> in, out;
+  } kValidInputs[] = {
+    // No elements.
+    {{}, {}},
+    // One element.
+    {{0x30, 0x00}, {0x30, 0x00}},
+    // Two identical elements.
+    {{0x30, 0x00, 0x30, 0x00}, {0x30, 0x00, 0x30, 0x00}},
+    // clang-format off
+    {{0x30, 0x02, 0x00, 0x00,
+      0x30, 0x00,
+      0x01, 0x00,
+      0x30, 0x02, 0x00, 0x00,
+      0x30, 0x03, 0x00, 0x00, 0x00,
+      0x30, 0x00,
+      0x30, 0x03, 0x00, 0x00, 0x01,
+      0x30, 0x01, 0x00,
+      0x01, 0x01, 0x00},
+     {0x01, 0x00,
+      0x01, 0x01, 0x00,
+      0x30, 0x00,
+      0x30, 0x00,
+      0x30, 0x01, 0x00,
+      0x30, 0x02, 0x00, 0x00,
+      0x30, 0x02, 0x00, 0x00,
+      0x30, 0x03, 0x00, 0x00, 0x00,
+      0x30, 0x03, 0x00, 0x00, 0x01}},
+    // clang-format on
+  };
+
+  for (const auto &t : kValidInputs) {
+    SCOPED_TRACE(Bytes(t.in));
+
+    bssl::ScopedCBB cbb;
+    CBB child;
+    ASSERT_TRUE(CBB_init(cbb.get(), 0));
+    ASSERT_TRUE(CBB_add_asn1(cbb.get(), &child, CBS_ASN1_SET));
+    ASSERT_TRUE(CBB_add_bytes(&child, t.in.data(), t.in.size()));
+    ASSERT_TRUE(CBB_flush_asn1_set_of(&child));
+    EXPECT_EQ(Bytes(t.out), Bytes(CBB_data(&child), CBB_len(&child)));
+
+    // Running it again should be idempotent.
+    ASSERT_TRUE(CBB_flush_asn1_set_of(&child));
+    EXPECT_EQ(Bytes(t.out), Bytes(CBB_data(&child), CBB_len(&child)));
+
+    // The ASN.1 header remain intact.
+    ASSERT_TRUE(CBB_flush(cbb.get()));
+    EXPECT_EQ(0x31, CBB_data(cbb.get())[0]);
+  }
+
+  const std::vector<uint8_t> kInvalidInputs[] = {
+    {0x30},
+    {0x30, 0x01},
+    {0x30, 0x00, 0x30, 0x00, 0x30, 0x01},
+  };
+
+  for (const auto &t : kInvalidInputs) {
+    SCOPED_TRACE(Bytes(t));
+
+    bssl::ScopedCBB cbb;
+    CBB child;
+    ASSERT_TRUE(CBB_init(cbb.get(), 0));
+    ASSERT_TRUE(CBB_add_asn1(cbb.get(), &child, CBS_ASN1_SET));
+    ASSERT_TRUE(CBB_add_bytes(&child, t.data(), t.size()));
+    EXPECT_FALSE(CBB_flush_asn1_set_of(&child));
+  }
+}
diff --git a/src/crypto/bytestring/cbb.c b/src/crypto/bytestring/cbb.c
index b12a66c2..eac6aa4a 100644
--- a/src/crypto/bytestring/cbb.c
+++ b/src/crypto/bytestring/cbb.c
@@ -18,6 +18,7 @@
 #include <limits.h>
 #include <string.h>
 
+#include <openssl/buf.h>
 #include <openssl/mem.h>
 
 #include "../internal.h"
@@ -569,3 +570,77 @@ int CBB_add_asn1_oid_from_text(CBB *cbb, const char *text, size_t len) {
 
   return 1;
 }
+
+static int compare_set_of_element(const void *a_ptr, const void *b_ptr) {
+  // See X.690, section 11.6 for the ordering. They are sorted in ascending
+  // order by their DER encoding.
+  const CBS *a = a_ptr, *b = b_ptr;
+  size_t a_len = CBS_len(a), b_len = CBS_len(b);
+  size_t min_len = a_len < b_len ? a_len : b_len;
+  int ret = OPENSSL_memcmp(CBS_data(a), CBS_data(b), min_len);
+  if (ret != 0) {
+    return ret;
+  }
+  if (a_len == b_len) {
+    return 0;
+  }
+  // If one is a prefix of the other, the shorter one sorts first. (This is not
+  // actually reachable. No DER encoding is a prefix of another DER encoding.)
+  return a_len < b_len ? -1 : 1;
+}
+
+int CBB_flush_asn1_set_of(CBB *cbb) {
+  if (!CBB_flush(cbb)) {
+    return 0;
+  }
+
+  CBS cbs;
+  size_t num_children = 0;
+  CBS_init(&cbs, CBB_data(cbb), CBB_len(cbb));
+  while (CBS_len(&cbs) != 0) {
+    if (!CBS_get_any_asn1_element(&cbs, NULL, NULL, NULL)) {
+      return 0;
+    }
+    num_children++;
+  }
+
+  if (num_children < 2) {
+    return 1;  // Nothing to do. This is the common case for X.509.
+  }
+  if (num_children > ((size_t)-1) / sizeof(CBS)) {
+    return 0;  // Overflow.
+  }
+
+  // Parse out the children and sort. We alias them into a copy of so they
+  // remain valid as we rewrite |cbb|.
+  int ret = 0;
+  size_t buf_len = CBB_len(cbb);
+  uint8_t *buf = BUF_memdup(CBB_data(cbb), buf_len);
+  CBS *children = OPENSSL_malloc(num_children * sizeof(CBS));
+  if (buf == NULL || children == NULL) {
+    goto err;
+  }
+  CBS_init(&cbs, buf, buf_len);
+  for (size_t i = 0; i < num_children; i++) {
+    if (!CBS_get_any_asn1_element(&cbs, &children[i], NULL, NULL)) {
+      goto err;
+    }
+  }
+  qsort(children, num_children, sizeof(CBS), compare_set_of_element);
+
+  // Rewind |cbb| and write the contents back in the new order.
+  cbb->base->len = cbb->offset + cbb->pending_len_len;
+  for (size_t i = 0; i < num_children; i++) {
+    if (!CBB_add_bytes(cbb, CBS_data(&children[i]), CBS_len(&children[i]))) {
+      goto err;
+    }
+  }
+  assert(CBB_len(cbb) == buf_len);
+
+  ret = 1;
+
+err:
+  OPENSSL_free(buf);
+  OPENSSL_free(children);
+  return ret;
+}
diff --git a/src/crypto/test/CMakeLists.txt b/src/crypto/test/CMakeLists.txt
index 88579133..46a40f83 100644
--- a/src/crypto/test/CMakeLists.txt
+++ b/src/crypto/test/CMakeLists.txt
@@ -9,7 +9,7 @@ add_library(
 )
 
 add_library(
-  gtest_main
+  boringssl_gtest_main
 
   OBJECT
 
diff --git a/src/decrepit/CMakeLists.txt b/src/decrepit/CMakeLists.txt
index 34707fd2..80e65185 100644
--- a/src/decrepit/CMakeLists.txt
+++ b/src/decrepit/CMakeLists.txt
@@ -44,11 +44,11 @@ add_executable(
   ripemd/ripemd_test.cc
   cfb/cfb_test.cc
 
-  $<TARGET_OBJECTS:gtest_main>
+  $<TARGET_OBJECTS:boringssl_gtest_main>
   $<TARGET_OBJECTS:test_support>
 )
 
-target_link_libraries(decrepit_test crypto decrepit gtest)
+target_link_libraries(decrepit_test crypto decrepit boringssl_gtest)
 if (WIN32)
   target_link_libraries(decrepit_test ws2_32)
 endif()
diff --git a/src/include/openssl/bytestring.h b/src/include/openssl/bytestring.h
index 43349e9a..2f25f14e 100644
--- a/src/include/openssl/bytestring.h
+++ b/src/include/openssl/bytestring.h
@@ -461,6 +461,15 @@ OPENSSL_EXPORT int CBB_add_asn1_uint64(CBB *cbb, uint64_t value);
 OPENSSL_EXPORT int CBB_add_asn1_oid_from_text(CBB *cbb, const char *text,
                                               size_t len);
 
+// CBB_flush_asn1_set_of calls |CBB_flush| on |cbb| and then reorders the
+// contents for a DER-encoded ASN.1 SET OF type. It returns one on success and
+// zero on failure. DER canonicalizes SET OF contents by sorting
+// lexicographically by encoding. Call this function when encoding a SET OF
+// type in an order that is not already known to be canonical.
+//
+// Note a SET type has a slightly different ordering than a SET OF.
+OPENSSL_EXPORT int CBB_flush_asn1_set_of(CBB *cbb);
+
 
 #if defined(__cplusplus)
 }  // extern C
diff --git a/src/ssl/CMakeLists.txt b/src/ssl/CMakeLists.txt
index 912327b3..35288e19 100644
--- a/src/ssl/CMakeLists.txt
+++ b/src/ssl/CMakeLists.txt
@@ -49,11 +49,11 @@ add_executable(
   span_test.cc
   ssl_test.cc
 
-  $<TARGET_OBJECTS:gtest_main>
+  $<TARGET_OBJECTS:boringssl_gtest_main>
   $<TARGET_OBJECTS:test_support>
 )
 
-target_link_libraries(ssl_test ssl crypto gtest)
+target_link_libraries(ssl_test ssl crypto boringssl_gtest)
 if (WIN32)
   target_link_libraries(ssl_test ws2_32)
 endif()
diff --git a/src/ssl/internal.h b/src/ssl/internal.h
index 78d7aa63..d59ecc47 100644
--- a/src/ssl/internal.h
+++ b/src/ssl/internal.h
@@ -1324,11 +1324,6 @@ struct SSL_HANDSHAKE {
   // |SSL_OP_NO_*| and |SSL_CTX_set_max_proto_version| APIs.
   uint16_t max_version = 0;
 
-  // session_id is the session ID in the ClientHello, used for the experimental
-  // TLS 1.3 variant.
-  uint8_t session_id[SSL_MAX_SSL_SESSION_ID_LENGTH] = {0};
-  uint8_t session_id_len = 0;
-
   size_t hash_len = 0;
   uint8_t secret[EVP_MAX_MD_SIZE] = {0};
   uint8_t early_traffic_secret[EVP_MAX_MD_SIZE] = {0};
@@ -1517,6 +1512,11 @@ struct SSL_HANDSHAKE {
   // early_data_written is the amount of early data that has been written by the
   // record layer.
   uint16_t early_data_written = 0;
+
+  // session_id is the session ID in the ClientHello, used for the experimental
+  // TLS 1.3 variant.
+  uint8_t session_id[SSL_MAX_SSL_SESSION_ID_LENGTH] = {0};
+  uint8_t session_id_len = 0;
 };
 
 UniquePtr<SSL_HANDSHAKE> ssl_handshake_new(SSL *ssl);
@@ -2305,8 +2305,6 @@ struct SSL3_STATE {
   // fired, were it not a draft.
   bool draft_downgrade:1;
 
-  uint8_t send_alert[2] = {0};
-
   // hs_buf is the buffer of handshake data to process.
   UniquePtr<BUF_MEM> hs_buf;
 
@@ -2319,6 +2317,11 @@ struct SSL3_STATE {
   // been successfully written.
   uint32_t pending_flight_offset = 0;
 
+  // ticket_age_skew is the difference, in seconds, between the client-sent
+  // ticket age and the server-computed value in TLS 1.3 server connections
+  // which resumed a session.
+  int32_t ticket_age_skew = 0;
+
   // aead_read_ctx is the current read cipher state.
   UniquePtr<SSLAEADContext> aead_read_ctx;
 
@@ -2344,6 +2347,8 @@ struct SSL3_STATE {
   uint8_t previous_server_finished_len = 0;
   uint8_t previous_server_finished[12] = {0};
 
+  uint8_t send_alert[2] = {0};
+
   // established_session is the session established by the connection. This
   // session is only filled upon the completion of the handshake and is
   // immutable.
@@ -2373,11 +2378,6 @@ struct SSL3_STATE {
   //     verified Channel ID from the client: a P256 point, (x,y), where
   //     each are big-endian values.
   uint8_t tlsext_channel_id[64] = {0};
-
-  // ticket_age_skew is the difference, in seconds, between the client-sent
-  // ticket age and the server-computed value in TLS 1.3 server connections
-  // which resumed a session.
-  int32_t ticket_age_skew = 0;
 };
 
 // lengths of messages
@@ -2518,10 +2518,6 @@ struct SSLConnection {
   // further constrainted by |SSL_OP_NO_*|.
   uint16_t conf_min_version;
 
-  // tls13_variant is the variant of TLS 1.3 we are using for this
-  // configuration.
-  enum tls13_variant_t tls13_variant;
-
   uint16_t max_send_fragment;
 
   // There are 2 BIO's even though they are normally both the same. This is so
@@ -2558,6 +2554,10 @@ struct SSLConnection {
   // milliseconds. It's used to initialize the timer any time it's restarted.
   unsigned initial_timeout_duration_ms;
 
+  // tls13_variant is the variant of TLS 1.3 we are using for this
+  // configuration.
+  enum tls13_variant_t tls13_variant;
+
   // session is the configured session to be offered by the client. This session
   // is immutable.
   SSL_SESSION *session;
diff --git a/src/ssl/ssl_x509.cc b/src/ssl/ssl_x509.cc
index 5c0365f9..cc27a601 100644
--- a/src/ssl/ssl_x509.cc
+++ b/src/ssl/ssl_x509.cc
@@ -1240,9 +1240,16 @@ int SSL_set1_verify_cert_store(SSL *ssl, X509_STORE *store) {
 
 int SSL_alert_from_verify_result(long result) {
   switch (result) {
-    case X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT:
+    case X509_V_ERR_CERT_CHAIN_TOO_LONG:
+    case X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT:
+    case X509_V_ERR_INVALID_CA:
+    case X509_V_ERR_PATH_LENGTH_EXCEEDED:
+    case X509_V_ERR_SELF_SIGNED_CERT_IN_CHAIN:
     case X509_V_ERR_UNABLE_TO_GET_CRL:
     case X509_V_ERR_UNABLE_TO_GET_CRL_ISSUER:
+    case X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT:
+    case X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT_LOCALLY:
+    case X509_V_ERR_UNABLE_TO_VERIFY_LEAF_SIGNATURE:
       return SSL_AD_UNKNOWN_CA;
 
     case X509_V_ERR_UNABLE_TO_DECRYPT_CERT_SIGNATURE:
@@ -1252,8 +1259,6 @@ int SSL_alert_from_verify_result(long result) {
     case X509_V_ERR_ERROR_IN_CERT_NOT_AFTER_FIELD:
     case X509_V_ERR_ERROR_IN_CRL_LAST_UPDATE_FIELD:
     case X509_V_ERR_ERROR_IN_CRL_NEXT_UPDATE_FIELD:
-    case X509_V_ERR_CERT_NOT_YET_VALID:
-    case X509_V_ERR_CRL_NOT_YET_VALID:
     case X509_V_ERR_CERT_UNTRUSTED:
     case X509_V_ERR_CERT_REJECTED:
     case X509_V_ERR_HOSTNAME_MISMATCH:
@@ -1266,7 +1271,9 @@ int SSL_alert_from_verify_result(long result) {
       return SSL_AD_DECRYPT_ERROR;
 
     case X509_V_ERR_CERT_HAS_EXPIRED:
+    case X509_V_ERR_CERT_NOT_YET_VALID:
     case X509_V_ERR_CRL_HAS_EXPIRED:
+    case X509_V_ERR_CRL_NOT_YET_VALID:
       return SSL_AD_CERTIFICATE_EXPIRED;
 
     case X509_V_ERR_CERT_REVOKED:
@@ -1278,15 +1285,6 @@ int SSL_alert_from_verify_result(long result) {
     case X509_V_ERR_STORE_LOOKUP:
       return SSL_AD_INTERNAL_ERROR;
 
-    case X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT:
-    case X509_V_ERR_SELF_SIGNED_CERT_IN_CHAIN:
-    case X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT_LOCALLY:
-    case X509_V_ERR_UNABLE_TO_VERIFY_LEAF_SIGNATURE:
-    case X509_V_ERR_CERT_CHAIN_TOO_LONG:
-    case X509_V_ERR_PATH_LENGTH_EXCEEDED:
-    case X509_V_ERR_INVALID_CA:
-      return SSL_AD_UNKNOWN_CA;
-
     case X509_V_ERR_APPLICATION_VERIFICATION:
       return SSL_AD_HANDSHAKE_FAILURE;
 
diff --git a/src/third_party/fiat/README.md b/src/third_party/fiat/README.md
index eaf0a60a..db67dc9d 100644
--- a/src/third_party/fiat/README.md
+++ b/src/third_party/fiat/README.md
@@ -7,7 +7,7 @@ licensed under the MIT license. (See LICENSE file.)
 ## Curve25519
 
 To generate the field arithmetic procedures in `curve25519.c` from a fiat-crypto
-checkout (as of `c47f48268f15e202a28b556845f231b2038cb426`), run
+checkout (as of `693d62c6fd7370bf71b8eb3b9a5825dfd071fcac`), run
 `make src/Specific/solinas32_2e255m19_10limbs/femul.c` (replacing `femul` with
 the desired field operation). The "source" file specifying the finite field and
 referencing the desired implementation strategy is
diff --git a/src/third_party/fiat/curve25519.c b/src/third_party/fiat/curve25519.c
index 2e564507..73d76a02 100644
--- a/src/third_party/fiat/curve25519.c
+++ b/src/third_party/fiat/curve25519.c
@@ -41,9 +41,6 @@
 #include "../../crypto/internal.h"
 
 
-static const int64_t kBottom25Bits = INT64_C(0x1ffffff);
-static const int64_t kBottom26Bits = INT64_C(0x3ffffff);
-
 static uint64_t load_3(const uint8_t *in) {
   uint64_t result;
   result = (uint64_t)in[0];
@@ -73,6 +70,12 @@ static uint64_t load_4(const uint8_t *in) {
   } \
 } while (0)
 
+#define assert_fe_frozen(f) do { \
+  for (unsigned _assert_fe_i = 0; _assert_fe_i< 10; _assert_fe_i++) { \
+    assert(f[_assert_fe_i] < (1u<<(26-(_assert_fe_i&1)))); \
+  } \
+} while (0)
+
 static void fe_frombytes_impl(uint32_t h[10], const uint8_t *s) {
   // Ignores top bit of s.
   uint32_t a0 = load_4(s);
@@ -100,115 +103,140 @@ static void fe_frombytes(fe *h, const uint8_t *s) {
   fe_frombytes_impl(h->v, s);
 }
 
-// Preconditions:
-//  |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
-//
-// Write p=2^255-19; q=floor(h/p).
-// Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
-//
-// Proof:
-//   Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
-//   Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4.
-//
-//   Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
-//   Then 0<y<1.
-//
-//   Write r=h-pq.
-//   Have 0<=r<=p-1=2^255-20.
-//   Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
-//
-//   Write x=r+19(2^-255)r+y.
-//   Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
-//
-//   Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
-//   so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
-static void fe_tobytes_impl(uint8_t s[32], const uint32_t h[10]) {
-  assert_fe_loose(h);
-  int32_t h0 = h[0];
-  int32_t h1 = h[1];
-  int32_t h2 = h[2];
-  int32_t h3 = h[3];
-  int32_t h4 = h[4];
-  int32_t h5 = h[5];
-  int32_t h6 = h[6];
-  int32_t h7 = h[7];
-  int32_t h8 = h[8];
-  int32_t h9 = h[9];
-  int32_t q;
-
-  q = (19 * h9 + (((int32_t) 1) << 24)) >> 25;
-  q = (h0 + q) >> 26;
-  q = (h1 + q) >> 25;
-  q = (h2 + q) >> 26;
-  q = (h3 + q) >> 25;
-  q = (h4 + q) >> 26;
-  q = (h5 + q) >> 25;
-  q = (h6 + q) >> 26;
-  q = (h7 + q) >> 25;
-  q = (h8 + q) >> 26;
-  q = (h9 + q) >> 25;
-
-  // Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20.
-  h0 += 19 * q;
-  // Goal: Output h-2^255 q, which is between 0 and 2^255-20.
-
-  h1 += h0 >> 26; h0 &= kBottom26Bits;
-  h2 += h1 >> 25; h1 &= kBottom25Bits;
-  h3 += h2 >> 26; h2 &= kBottom26Bits;
-  h4 += h3 >> 25; h3 &= kBottom25Bits;
-  h5 += h4 >> 26; h4 &= kBottom26Bits;
-  h6 += h5 >> 25; h5 &= kBottom25Bits;
-  h7 += h6 >> 26; h6 &= kBottom26Bits;
-  h8 += h7 >> 25; h7 &= kBottom25Bits;
-  h9 += h8 >> 26; h8 &= kBottom26Bits;
-                  h9 &= kBottom25Bits;
-                  // h10 = carry9
-
-  // Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
-  // Have h0+...+2^230 h9 between 0 and 2^255-1;
-  // evidently 2^255 h10-2^255 q = 0.
-  // Goal: Output h0+...+2^230 h9.
-
-  s[0] = h0 >> 0;
-  s[1] = h0 >> 8;
-  s[2] = h0 >> 16;
-  s[3] = (h0 >> 24) | ((uint32_t)(h1) << 2);
-  s[4] = h1 >> 6;
-  s[5] = h1 >> 14;
-  s[6] = (h1 >> 22) | ((uint32_t)(h2) << 3);
-  s[7] = h2 >> 5;
-  s[8] = h2 >> 13;
-  s[9] = (h2 >> 21) | ((uint32_t)(h3) << 5);
-  s[10] = h3 >> 3;
-  s[11] = h3 >> 11;
-  s[12] = (h3 >> 19) | ((uint32_t)(h4) << 6);
-  s[13] = h4 >> 2;
-  s[14] = h4 >> 10;
-  s[15] = h4 >> 18;
-  s[16] = h5 >> 0;
-  s[17] = h5 >> 8;
-  s[18] = h5 >> 16;
-  s[19] = (h5 >> 24) | ((uint32_t)(h6) << 1);
-  s[20] = h6 >> 7;
-  s[21] = h6 >> 15;
-  s[22] = (h6 >> 23) | ((uint32_t)(h7) << 3);
-  s[23] = h7 >> 5;
-  s[24] = h7 >> 13;
-  s[25] = (h7 >> 21) | ((uint32_t)(h8) << 4);
-  s[26] = h8 >> 4;
-  s[27] = h8 >> 12;
-  s[28] = (h8 >> 20) | ((uint32_t)(h9) << 6);
-  s[29] = h9 >> 2;
-  s[30] = h9 >> 10;
-  s[31] = h9 >> 18;
+static uint8_t /*bool*/ addcarryx_u25(uint8_t /*bool*/ c, uint32_t a,
+                                      uint32_t b, uint32_t *low) {
+  // This function extracts 25 bits of result and 1 bit of carry (26 total), so
+  // a 32-bit intermediate is sufficient.
+  uint32_t x = a + b + c;
+  *low = x & ((1 << 25) - 1);
+  return (x >> 25) & 1;
+}
+
+static uint8_t /*bool*/ addcarryx_u26(uint8_t /*bool*/ c, uint32_t a,
+                                      uint32_t b, uint32_t *low) {
+  // This function extracts 26 bits of result and 1 bit of carry (27 total), so
+  // a 32-bit intermediate is sufficient.
+  uint32_t x = a + b + c;
+  *low = x & ((1 << 26) - 1);
+  return (x >> 26) & 1;
+}
+
+static uint8_t /*bool*/ subborrow_u25(uint8_t /*bool*/ c, uint32_t a,
+                                      uint32_t b, uint32_t *low) {
+  // This function extracts 25 bits of result and 1 bit of borrow (26 total), so
+  // a 32-bit intermediate is sufficient.
+  uint32_t x = a - b - c;
+  *low = x & ((1 << 25) - 1);
+  return x >> 31;
 }
 
-static void fe_tobytes(uint8_t s[32], const fe *h) {
-  fe_tobytes_impl(s, h->v);
+static uint8_t /*bool*/ subborrow_u26(uint8_t /*bool*/ c, uint32_t a,
+                                      uint32_t b, uint32_t *low) {
+  // This function extracts 26 bits of result and 1 bit of borrow (27 total), so
+  // a 32-bit intermediate is sufficient.
+  uint32_t x = a - b - c;
+  *low = x & ((1 << 26) - 1);
+  return x >> 31;
 }
 
-static void fe_loose_tobytes(uint8_t s[32], const fe_loose *h) {
-  fe_tobytes_impl(s, h->v);
+static uint32_t cmovznz32(uint32_t t, uint32_t z, uint32_t nz) {
+  t = -!!t; // all set if nonzero, 0 if 0
+  return (t&nz) | ((~t)&z);
+}
+
+static void fe_freeze(uint32_t out[10], const uint32_t in1[10]) {
+  { const uint32_t x17 = in1[9];
+  { const uint32_t x18 = in1[8];
+  { const uint32_t x16 = in1[7];
+  { const uint32_t x14 = in1[6];
+  { const uint32_t x12 = in1[5];
+  { const uint32_t x10 = in1[4];
+  { const uint32_t x8 = in1[3];
+  { const uint32_t x6 = in1[2];
+  { const uint32_t x4 = in1[1];
+  { const uint32_t x2 = in1[0];
+  { uint32_t x20; uint8_t/*bool*/ x21 = subborrow_u26(0x0, x2, 0x3ffffed, &x20);
+  { uint32_t x23; uint8_t/*bool*/ x24 = subborrow_u25(x21, x4, 0x1ffffff, &x23);
+  { uint32_t x26; uint8_t/*bool*/ x27 = subborrow_u26(x24, x6, 0x3ffffff, &x26);
+  { uint32_t x29; uint8_t/*bool*/ x30 = subborrow_u25(x27, x8, 0x1ffffff, &x29);
+  { uint32_t x32; uint8_t/*bool*/ x33 = subborrow_u26(x30, x10, 0x3ffffff, &x32);
+  { uint32_t x35; uint8_t/*bool*/ x36 = subborrow_u25(x33, x12, 0x1ffffff, &x35);
+  { uint32_t x38; uint8_t/*bool*/ x39 = subborrow_u26(x36, x14, 0x3ffffff, &x38);
+  { uint32_t x41; uint8_t/*bool*/ x42 = subborrow_u25(x39, x16, 0x1ffffff, &x41);
+  { uint32_t x44; uint8_t/*bool*/ x45 = subborrow_u26(x42, x18, 0x3ffffff, &x44);
+  { uint32_t x47; uint8_t/*bool*/ x48 = subborrow_u25(x45, x17, 0x1ffffff, &x47);
+  { uint32_t x49 = cmovznz32(x48, 0x0, 0xffffffff);
+  { uint32_t x50 = (x49 & 0x3ffffed);
+  { uint32_t x52; uint8_t/*bool*/ x53 = addcarryx_u26(0x0, x20, x50, &x52);
+  { uint32_t x54 = (x49 & 0x1ffffff);
+  { uint32_t x56; uint8_t/*bool*/ x57 = addcarryx_u25(x53, x23, x54, &x56);
+  { uint32_t x58 = (x49 & 0x3ffffff);
+  { uint32_t x60; uint8_t/*bool*/ x61 = addcarryx_u26(x57, x26, x58, &x60);
+  { uint32_t x62 = (x49 & 0x1ffffff);
+  { uint32_t x64; uint8_t/*bool*/ x65 = addcarryx_u25(x61, x29, x62, &x64);
+  { uint32_t x66 = (x49 & 0x3ffffff);
+  { uint32_t x68; uint8_t/*bool*/ x69 = addcarryx_u26(x65, x32, x66, &x68);
+  { uint32_t x70 = (x49 & 0x1ffffff);
+  { uint32_t x72; uint8_t/*bool*/ x73 = addcarryx_u25(x69, x35, x70, &x72);
+  { uint32_t x74 = (x49 & 0x3ffffff);
+  { uint32_t x76; uint8_t/*bool*/ x77 = addcarryx_u26(x73, x38, x74, &x76);
+  { uint32_t x78 = (x49 & 0x1ffffff);
+  { uint32_t x80; uint8_t/*bool*/ x81 = addcarryx_u25(x77, x41, x78, &x80);
+  { uint32_t x82 = (x49 & 0x3ffffff);
+  { uint32_t x84; uint8_t/*bool*/ x85 = addcarryx_u26(x81, x44, x82, &x84);
+  { uint32_t x86 = (x49 & 0x1ffffff);
+  { uint32_t x88; addcarryx_u25(x85, x47, x86, &x88);
+  out[0] = x52;
+  out[1] = x56;
+  out[2] = x60;
+  out[3] = x64;
+  out[4] = x68;
+  out[5] = x72;
+  out[6] = x76;
+  out[7] = x80;
+  out[8] = x84;
+  out[9] = x88;
+  }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
+}
+
+static void fe_tobytes(uint8_t s[32], const fe *f) {
+  assert_fe(f->v);
+  uint32_t h[10];
+  fe_freeze(h, f->v);
+  assert_fe_frozen(h);
+
+  s[0] = h[0] >> 0;
+  s[1] = h[0] >> 8;
+  s[2] = h[0] >> 16;
+  s[3] = (h[0] >> 24) | (h[1] << 2);
+  s[4] = h[1] >> 6;
+  s[5] = h[1] >> 14;
+  s[6] = (h[1] >> 22) | (h[2] << 3);
+  s[7] = h[2] >> 5;
+  s[8] = h[2] >> 13;
+  s[9] = (h[2] >> 21) | (h[3] << 5);
+  s[10] = h[3] >> 3;
+  s[11] = h[3] >> 11;
+  s[12] = (h[3] >> 19) | (h[4] << 6);
+  s[13] = h[4] >> 2;
+  s[14] = h[4] >> 10;
+  s[15] = h[4] >> 18;
+  s[16] = h[5] >> 0;
+  s[17] = h[5] >> 8;
+  s[18] = h[5] >> 16;
+  s[19] = (h[5] >> 24) | (h[6] << 1);
+  s[20] = h[6] >> 7;
+  s[21] = h[6] >> 15;
+  s[22] = (h[6] >> 23) | (h[7] << 3);
+  s[23] = h[7] >> 5;
+  s[24] = h[7] >> 13;
+  s[25] = (h[7] >> 21) | (h[8] << 4);
+  s[26] = h[8] >> 4;
+  s[27] = h[8] >> 12;
+  s[28] = (h[8] >> 20) | (h[9] << 6);
+  s[29] = h[9] >> 2;
+  s[30] = h[9] >> 10;
+  s[31] = h[9] >> 18;
 }
 
 // h = f
@@ -775,8 +803,10 @@ static void fe_cmov(fe_loose *f, const fe_loose *g, unsigned b) {
 // return 0 if f == 0
 // return 1 if f != 0
 static int fe_isnonzero(const fe_loose *f) {
+  fe tight;
+  fe_carry(&tight, f);
   uint8_t s[32];
-  fe_loose_tobytes(s, f);
+  fe_tobytes(s, &tight);
 
   static const uint8_t zero[32] = {0};
   return CRYPTO_memcmp(s, zero, sizeof(zero)) != 0;