Create Certificate messages in TLS1.3 format

Also updates TLSProxy to be able to understand the format and parse the
contained extensions.

Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/2020)

12 files changed, 462 insertions, 149 deletions

diff --git a/ssl/ssl_cert.c b/ssl/ssl_cert.c
index f26e876014..9668976324 100644
--- a/ssl/ssl_cert.c
+++ b/ssl/ssl_cert.c
@@ -740,116 +740,6 @@ int SSL_add_dir_cert_subjects_to_stack(STACK_OF(X509_NAME) *stack,
     return ret;
 }
 
-/* Add a certificate to the WPACKET */
-static int ssl_add_cert_to_buf(WPACKET *pkt, X509 *x)
-{
-    int len;
-    unsigned char *outbytes;
-
-    len = i2d_X509(x, NULL);
-    if (len < 0) {
-        SSLerr(SSL_F_SSL_ADD_CERT_TO_BUF, ERR_R_BUF_LIB);
-        return 0;
-    }
-    if (!WPACKET_sub_allocate_bytes_u24(pkt, len, &outbytes)
-            || i2d_X509(x, &outbytes) != len) {
-        SSLerr(SSL_F_SSL_ADD_CERT_TO_BUF, ERR_R_INTERNAL_ERROR);
-        return 0;
-    }
-
-    return 1;
-}
-
-/* Add certificate chain to internal SSL BUF_MEM structure */
-int ssl_add_cert_chain(SSL *s, WPACKET *pkt, CERT_PKEY *cpk)
-{
-    int i, chain_count;
-    X509 *x;
-    STACK_OF(X509) *extra_certs;
-    STACK_OF(X509) *chain = NULL;
-    X509_STORE *chain_store;
-
-    if (cpk == NULL || cpk->x509 == NULL)
-        return 1;
-
-    x = cpk->x509;
-
-    /*
-     * If we have a certificate specific chain use it, else use parent ctx.
-     */
-    if (cpk->chain)
-        extra_certs = cpk->chain;
-    else
-        extra_certs = s->ctx->extra_certs;
-
-    if ((s->mode & SSL_MODE_NO_AUTO_CHAIN) || extra_certs)
-        chain_store = NULL;
-    else if (s->cert->chain_store)
-        chain_store = s->cert->chain_store;
-    else
-        chain_store = s->ctx->cert_store;
-
-    if (chain_store) {
-        X509_STORE_CTX *xs_ctx = X509_STORE_CTX_new();
-
-        if (xs_ctx == NULL) {
-            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, ERR_R_MALLOC_FAILURE);
-            return (0);
-        }
-        if (!X509_STORE_CTX_init(xs_ctx, chain_store, x, NULL)) {
-            X509_STORE_CTX_free(xs_ctx);
-            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, ERR_R_X509_LIB);
-            return (0);
-        }
-        /*
-         * It is valid for the chain not to be complete (because normally we
-         * don't include the root cert in the chain). Therefore we deliberately
-         * ignore the error return from this call. We're not actually verifying
-         * the cert - we're just building as much of the chain as we can
-         */
-        (void)X509_verify_cert(xs_ctx);
-        /* Don't leave errors in the queue */
-        ERR_clear_error();
-        chain = X509_STORE_CTX_get0_chain(xs_ctx);
-        i = ssl_security_cert_chain(s, chain, NULL, 0);
-        if (i != 1) {
-#if 0
-            /* Dummy error calls so mkerr generates them */
-            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, SSL_R_EE_KEY_TOO_SMALL);
-            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, SSL_R_CA_KEY_TOO_SMALL);
-            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, SSL_R_CA_MD_TOO_WEAK);
-#endif
-            X509_STORE_CTX_free(xs_ctx);
-            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, i);
-            return 0;
-        }
-        chain_count = sk_X509_num(chain);
-        for (i = 0; i < chain_count; i++) {
-            x = sk_X509_value(chain, i);
-
-            if (!ssl_add_cert_to_buf(pkt, x)) {
-                X509_STORE_CTX_free(xs_ctx);
-                return 0;
-            }
-        }
-        X509_STORE_CTX_free(xs_ctx);
-    } else {
-        i = ssl_security_cert_chain(s, extra_certs, x, 0);
-        if (i != 1) {
-            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, i);
-            return 0;
-        }
-        if (!ssl_add_cert_to_buf(pkt, x))
-            return 0;
-        for (i = 0; i < sk_X509_num(extra_certs); i++) {
-            x = sk_X509_value(extra_certs, i);
-            if (!ssl_add_cert_to_buf(pkt, x))
-                return 0;
-        }
-    }
-    return 1;
-}
-
 /* Build a certificate chain for current certificate */
 int ssl_build_cert_chain(SSL *s, SSL_CTX *ctx, int flags)
 {
diff --git a/ssl/ssl_locl.h b/ssl/ssl_locl.h
index 5671a6fff9..c1b331a1a7 100644
--- a/ssl/ssl_locl.h
+++ b/ssl/ssl_locl.h
@@ -1896,7 +1896,6 @@ __owur X509 *ssl_cert_get0_next_certificate(CERT *c, int first);
 void ssl_cert_set_cert_cb(CERT *c, int (*cb) (SSL *ssl, void *arg), void *arg);
 
 __owur int ssl_verify_cert_chain(SSL *s, STACK_OF(X509) *sk);
-__owur int ssl_add_cert_chain(SSL *s, WPACKET *pkt, CERT_PKEY *cpk);
 __owur int ssl_build_cert_chain(SSL *s, SSL_CTX *ctx, int flags);
 __owur int ssl_cert_set_cert_store(CERT *c, X509_STORE *store, int chain,
                                    int ref);
@@ -1952,7 +1951,7 @@ __owur size_t ssl3_final_finish_mac(SSL *s, const char *sender, size_t slen,
 __owur int ssl3_finish_mac(SSL *s, const unsigned char *buf, size_t len);
 void ssl3_free_digest_list(SSL *s);
 __owur unsigned long ssl3_output_cert_chain(SSL *s, WPACKET *pkt,
-                                            CERT_PKEY *cpk);
+                                            CERT_PKEY *cpk, int *al);
 __owur const SSL_CIPHER *ssl3_choose_cipher(SSL *ssl,
                                             STACK_OF(SSL_CIPHER) *clnt,
                                             STACK_OF(SSL_CIPHER) *srvr);
diff --git a/ssl/statem/extensions_clnt.c b/ssl/statem/extensions_clnt.c
index 4975c7a831..1fd4d84f73 100644
--- a/ssl/statem/extensions_clnt.c
+++ b/ssl/statem/extensions_clnt.c
@@ -252,6 +252,10 @@ int tls_construct_ctos_status_request(SSL *s, WPACKET *pkt, X509 *x,
 {
     int i;
 
+    /* This extension isn't defined for client Certificates */
+    if (x != NULL)
+        return 1;
+
     if (s->tlsext_status_type != TLSEXT_STATUSTYPE_ocsp)
         return 1;
 
@@ -418,6 +422,10 @@ int tls_construct_ctos_sct(SSL *s, WPACKET *pkt, X509 *x, size_t chain, int *al)
     if (s->ct_validation_callback == NULL)
         return 1;
 
+    /* Not defined for client Certificates */
+    if (x != NULL)
+        return 1;
+
     if (!WPACKET_put_bytes_u16(pkt, TLSEXT_TYPE_signed_certificate_timestamp)
             || !WPACKET_put_bytes_u16(pkt, 0)) {
         SSLerr(SSL_F_TLS_CONSTRUCT_CTOS_SCT, ERR_R_INTERNAL_ERROR);
diff --git a/ssl/statem/extensions_srvr.c b/ssl/statem/extensions_srvr.c
index 14a8e15b49..0bdfce8c7d 100644
--- a/ssl/statem/extensions_srvr.c
+++ b/ssl/statem/extensions_srvr.c
@@ -224,6 +224,10 @@ int tls_parse_ctos_status_request(SSL *s, PACKET *pkt, X509 *x, size_t chain,
 {
     PACKET responder_id_list, exts;
 
+    /* Not defined if we get one of these in a client Certificate */
+    if (x != NULL)
+        return 1;
+
     if (!PACKET_get_1(pkt, (unsigned int *)&s->tlsext_status_type)) {
         *al = SSL_AD_DECODE_ERROR;
         return 0;
@@ -752,6 +756,9 @@ int tls_construct_stoc_status_request(SSL *s, WPACKET *pkt, X509 *x,
     if (!s->tlsext_status_expected)
         return 1;
 
+    if (SSL_IS_TLS13(s) && chain != 0)
+        return 1;
+
     if (!WPACKET_put_bytes_u16(pkt, TLSEXT_TYPE_status_request)
             || !WPACKET_put_bytes_u16(pkt, 0)) {
         SSLerr(SSL_F_TLS_CONSTRUCT_STOC_STATUS_REQUEST, ERR_R_INTERNAL_ERROR);
diff --git a/ssl/statem/statem_clnt.c b/ssl/statem/statem_clnt.c
index 8400c74944..00062ff5ce 100644
--- a/ssl/statem/statem_clnt.c
+++ b/ssl/statem/statem_clnt.c
@@ -1371,19 +1371,23 @@ MSG_PROCESS_RETURN tls_process_server_certificate(SSL *s, PACKET *pkt)
     const unsigned char *certstart, *certbytes;
     STACK_OF(X509) *sk = NULL;
     EVP_PKEY *pkey = NULL;
+    size_t chain;
+    unsigned int context = 0;
 
     if ((sk = sk_X509_new_null()) == NULL) {
         SSLerr(SSL_F_TLS_PROCESS_SERVER_CERTIFICATE, ERR_R_MALLOC_FAILURE);
         goto err;
     }
 
-    if (!PACKET_get_net_3(pkt, &cert_list_len)
-        || PACKET_remaining(pkt) != cert_list_len) {
+    if ((SSL_IS_TLS13(s) && !PACKET_get_1(pkt, &context))
+            || context != 0
+            || !PACKET_get_net_3(pkt, &cert_list_len)
+            || PACKET_remaining(pkt) != cert_list_len) {
         al = SSL_AD_DECODE_ERROR;
         SSLerr(SSL_F_TLS_PROCESS_SERVER_CERTIFICATE, SSL_R_LENGTH_MISMATCH);
         goto f_err;
     }
-    while (PACKET_remaining(pkt)) {
+    for (chain = 0; PACKET_remaining(pkt); chain++) {
         if (!PACKET_get_net_3(pkt, &cert_len)
             || !PACKET_get_bytes(pkt, &certbytes, cert_len)) {
             al = SSL_AD_DECODE_ERROR;
@@ -1405,6 +1409,23 @@ MSG_PROCESS_RETURN tls_process_server_certificate(SSL *s, PACKET *pkt)
                    SSL_R_CERT_LENGTH_MISMATCH);
             goto f_err;
         }
+
+        if (SSL_IS_TLS13(s)) {
+            RAW_EXTENSION *rawexts = NULL;
+            PACKET extensions;
+
+            if (!PACKET_get_length_prefixed_2(pkt, &extensions)) {
+                al = SSL_AD_DECODE_ERROR;
+                SSLerr(SSL_F_TLS_PROCESS_SERVER_CERTIFICATE, SSL_R_BAD_LENGTH);
+                goto f_err;
+            }
+            if (!tls_collect_extensions(s, &extensions, EXT_TLS1_3_CERTIFICATE,
+                                        &rawexts, &al)
+                    || !tls_parse_all_extensions(s, EXT_TLS1_3_CERTIFICATE,
+                                                 rawexts, x, chain, &al))
+                goto f_err;
+        }
+
         if (!sk_X509_push(sk, x)) {
             SSLerr(SSL_F_TLS_PROCESS_SERVER_CERTIFICATE, ERR_R_MALLOC_FAILURE);
             goto err;
@@ -2986,11 +3007,19 @@ WORK_STATE tls_prepare_client_certificate(SSL *s, WORK_STATE wst)
 
 int tls_construct_client_certificate(SSL *s, WPACKET *pkt)
 {
-    if (!ssl3_output_cert_chain(s, pkt,
+    int al;
+
+    /*
+     * TODO(TLS1.3): For now we must put an empty context. Needs to be filled in
+     * later
+     */
+    if ((SSL_IS_TLS13(s) && !WPACKET_put_bytes_u8(pkt, 0))
+            || !ssl3_output_cert_chain(s, pkt,
                                (s->s3->tmp.cert_req == 2) ? NULL
-                                                          : s->cert->key)) {
+                                                          : s->cert->key,
+                                &al)) {
         SSLerr(SSL_F_TLS_CONSTRUCT_CLIENT_CERTIFICATE, ERR_R_INTERNAL_ERROR);
-        ssl3_send_alert(s, SSL3_AL_FATAL, SSL_AD_INTERNAL_ERROR);
+        ssl3_send_alert(s, SSL3_AL_FATAL, al);
         return 0;
     }
 
@@ -3108,18 +3137,9 @@ static MSG_PROCESS_RETURN tls_process_encrypted_extensions(SSL *s, PACKET *pkt)
         goto err;
     }
 
-    /*
-     * TODO(TLS1.3): For now we are processing Encrypted Extensions and
-     * Certificate extensions as part of this one message. Later we need to
-     * split out the Certificate extensions into the Certificate message
-     */
-    if (!tls_collect_extensions(s, &extensions,
-                                EXT_TLS1_3_ENCRYPTED_EXTENSIONS
-                                    | EXT_TLS1_3_CERTIFICATE,
+    if (!tls_collect_extensions(s, &extensions, EXT_TLS1_3_ENCRYPTED_EXTENSIONS,
                                 &rawexts, &al)
-            || !tls_parse_all_extensions(s,
-                                         EXT_TLS1_3_ENCRYPTED_EXTENSIONS
-                                            | EXT_TLS1_3_CERTIFICATE,
+            || !tls_parse_all_extensions(s, EXT_TLS1_3_ENCRYPTED_EXTENSIONS,
                                          rawexts, NULL, 0, &al))
         goto err;
 
diff --git a/ssl/statem/statem_lib.c b/ssl/statem/statem_lib.c
index 742925f23e..f41da103a4 100644
--- a/ssl/statem/statem_lib.c
+++ b/ssl/statem/statem_lib.c
@@ -308,12 +308,139 @@ int tls_construct_change_cipher_spec(SSL *s, WPACKET *pkt)
     return 1;
 }
 
-unsigned long ssl3_output_cert_chain(SSL *s, WPACKET *pkt, CERT_PKEY *cpk)
+/* Add a certificate to the WPACKET */
+static int ssl_add_cert_to_wpacket(SSL *s, WPACKET *pkt, X509 *x, int chain,
+                                   int *al)
 {
+    int len;
+    unsigned char *outbytes;
+
+    len = i2d_X509(x, NULL);
+    if (len < 0) {
+        SSLerr(SSL_F_SSL_ADD_CERT_TO_BUF, ERR_R_BUF_LIB);
+        *al = SSL_AD_INTERNAL_ERROR;
+        return 0;
+    }
+    if (!WPACKET_sub_allocate_bytes_u24(pkt, len, &outbytes)
+            || i2d_X509(x, &outbytes) != len) {
+        SSLerr(SSL_F_SSL_ADD_CERT_TO_BUF, ERR_R_INTERNAL_ERROR);
+        *al = SSL_AD_INTERNAL_ERROR;
+        return 0;
+    }
+
+    if (SSL_IS_TLS13(s)
+            && !tls_construct_extensions(s, pkt, EXT_TLS1_3_CERTIFICATE, x,
+                                         chain, al))
+        return 0;
+
+    return 1;
+}
+
+/* Add certificate chain to provided WPACKET */
+static int ssl_add_cert_chain(SSL *s, WPACKET *pkt, CERT_PKEY *cpk, int *al)
+{
+    int i, chain_count;
+    X509 *x;
+    STACK_OF(X509) *extra_certs;
+    STACK_OF(X509) *chain = NULL;
+    X509_STORE *chain_store;
+    int tmpal = SSL_AD_INTERNAL_ERROR;
+
+    if (cpk == NULL || cpk->x509 == NULL)
+        return 1;
+
+    x = cpk->x509;
+
+    /*
+     * If we have a certificate specific chain use it, else use parent ctx.
+     */
+    if (cpk->chain)
+        extra_certs = cpk->chain;
+    else
+        extra_certs = s->ctx->extra_certs;
+
+    if ((s->mode & SSL_MODE_NO_AUTO_CHAIN) || extra_certs)
+        chain_store = NULL;
+    else if (s->cert->chain_store)
+        chain_store = s->cert->chain_store;
+    else
+        chain_store = s->ctx->cert_store;
+
+    if (chain_store) {
+        X509_STORE_CTX *xs_ctx = X509_STORE_CTX_new();
+
+        if (xs_ctx == NULL) {
+            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, ERR_R_MALLOC_FAILURE);
+            goto err;
+        }
+        if (!X509_STORE_CTX_init(xs_ctx, chain_store, x, NULL)) {
+            X509_STORE_CTX_free(xs_ctx);
+            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, ERR_R_X509_LIB);
+            goto err;
+        }
+        /*
+         * It is valid for the chain not to be complete (because normally we
+         * don't include the root cert in the chain). Therefore we deliberately
+         * ignore the error return from this call. We're not actually verifying
+         * the cert - we're just building as much of the chain as we can
+         */
+        (void)X509_verify_cert(xs_ctx);
+        /* Don't leave errors in the queue */
+        ERR_clear_error();
+        chain = X509_STORE_CTX_get0_chain(xs_ctx);
+        i = ssl_security_cert_chain(s, chain, NULL, 0);
+        if (i != 1) {
+#if 0
+            /* Dummy error calls so mkerr generates them */
+            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, SSL_R_EE_KEY_TOO_SMALL);
+            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, SSL_R_CA_KEY_TOO_SMALL);
+            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, SSL_R_CA_MD_TOO_WEAK);
+#endif
+            X509_STORE_CTX_free(xs_ctx);
+            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, i);
+            goto err;
+        }
+        chain_count = sk_X509_num(chain);
+        for (i = 0; i < chain_count; i++) {
+            x = sk_X509_value(chain, i);
+
+            if (!ssl_add_cert_to_wpacket(s, pkt, x, i, &tmpal)) {
+                X509_STORE_CTX_free(xs_ctx);
+                goto err;
+            }
+        }
+        X509_STORE_CTX_free(xs_ctx);
+    } else {
+        i = ssl_security_cert_chain(s, extra_certs, x, 0);
+        if (i != 1) {
+            SSLerr(SSL_F_SSL_ADD_CERT_CHAIN, i);
+            goto err;
+        }
+        if (!ssl_add_cert_to_wpacket(s, pkt, x, 0, &tmpal))
+            goto err;
+        for (i = 0; i < sk_X509_num(extra_certs); i++) {
+            x = sk_X509_value(extra_certs, i);
+            if (!ssl_add_cert_to_wpacket(s, pkt, x, i + 1, &tmpal))
+                goto err;
+        }
+    }
+    return 1;
+
+ err:
+    *al = tmpal;
+    return 0;
+}
+
+unsigned long ssl3_output_cert_chain(SSL *s, WPACKET *pkt, CERT_PKEY *cpk,
+                                     int *al)
+{
+    int tmpal = SSL_AD_INTERNAL_ERROR;
+
     if (!WPACKET_start_sub_packet_u24(pkt)
-            || !ssl_add_cert_chain(s, pkt, cpk)
+            || !ssl_add_cert_chain(s, pkt, cpk, &tmpal)
             || !WPACKET_close(pkt)) {
         SSLerr(SSL_F_SSL3_OUTPUT_CERT_CHAIN, ERR_R_INTERNAL_ERROR);
+        *al = tmpal;
         return 0;
     }
     return 1;
diff --git a/ssl/statem/statem_srvr.c b/ssl/statem/statem_srvr.c
index 5f6d6288f4..5e230f086b 100644
--- a/ssl/statem/statem_srvr.c
+++ b/ssl/statem/statem_srvr.c
@@ -3143,22 +3143,25 @@ MSG_PROCESS_RETURN tls_process_client_certificate(SSL *s, PACKET *pkt)
     unsigned long l, llen;
     const unsigned char *certstart, *certbytes;
     STACK_OF(X509) *sk = NULL;
-    PACKET spkt;
+    PACKET spkt, context;
+    size_t chain;
 
     if ((sk = sk_X509_new_null()) == NULL) {
         SSLerr(SSL_F_TLS_PROCESS_CLIENT_CERTIFICATE, ERR_R_MALLOC_FAILURE);
         goto f_err;
     }
 
-    if (!PACKET_get_net_3(pkt, &llen)
-        || !PACKET_get_sub_packet(pkt, &spkt, llen)
-        || PACKET_remaining(pkt) != 0) {
+    /* TODO(TLS1.3): For now we ignore the context. We need to verify this */
+    if ((SSL_IS_TLS13(s) && !PACKET_get_length_prefixed_1(pkt, &context))
+            || !PACKET_get_net_3(pkt, &llen)
+            || !PACKET_get_sub_packet(pkt, &spkt, llen)
+            || PACKET_remaining(pkt) != 0) {
         al = SSL_AD_DECODE_ERROR;
         SSLerr(SSL_F_TLS_PROCESS_CLIENT_CERTIFICATE, SSL_R_LENGTH_MISMATCH);
         goto f_err;
     }
 
-    while (PACKET_remaining(&spkt) > 0) {
+    for (chain = 0; PACKET_remaining(&spkt) > 0; chain++) {
         if (!PACKET_get_net_3(&spkt, &l)
             || !PACKET_get_bytes(&spkt, &certbytes, l)) {
             al = SSL_AD_DECODE_ERROR;
@@ -3179,6 +3182,23 @@ MSG_PROCESS_RETURN tls_process_client_certificate(SSL *s, PACKET *pkt)
                    SSL_R_CERT_LENGTH_MISMATCH);
             goto f_err;
         }
+
+        if (SSL_IS_TLS13(s)) {
+            RAW_EXTENSION *rawexts = NULL;
+            PACKET extensions;
+
+            if (!PACKET_get_length_prefixed_2(&spkt, &extensions)) {
+                al = SSL_AD_DECODE_ERROR;
+                SSLerr(SSL_F_TLS_PROCESS_CLIENT_CERTIFICATE, SSL_R_BAD_LENGTH);
+                goto f_err;
+            }
+            if (!tls_collect_extensions(s, &extensions, EXT_TLS1_3_CERTIFICATE,
+                                        &rawexts, &al)
+                    || !tls_parse_all_extensions(s, EXT_TLS1_3_CERTIFICATE,
+                                                 rawexts, x, chain, &al))
+                goto f_err;
+        }
+
         if (!sk_X509_push(sk, x)) {
             SSLerr(SSL_F_TLS_PROCESS_CLIENT_CERTIFICATE, ERR_R_MALLOC_FAILURE);
             goto f_err;
@@ -3266,6 +3286,7 @@ MSG_PROCESS_RETURN tls_process_client_certificate(SSL *s, PACKET *pkt)
 int tls_construct_server_certificate(SSL *s, WPACKET *pkt)
 {
     CERT_PKEY *cpk;
+    int al = SSL_AD_INTERNAL_ERROR;
 
     cpk = ssl_get_server_send_pkey(s);
     if (cpk == NULL) {
@@ -3273,8 +3294,14 @@ int tls_construct_server_certificate(SSL *s, WPACKET *pkt)
         return 0;
     }
 
-    if (!ssl3_output_cert_chain(s, pkt, cpk)) {
+    /*
+     * In TLSv1.3 the certificate chain is always preceded by a 0 length context
+     * for the server Certificate message
+     */
+    if ((SSL_IS_TLS13(s) && !WPACKET_put_bytes_u8(pkt, 0))
+            || !ssl3_output_cert_chain(s, pkt, cpk, &al)) {
         SSLerr(SSL_F_TLS_CONSTRUCT_SERVER_CERTIFICATE, ERR_R_INTERNAL_ERROR);
+        ssl3_send_alert(s, SSL3_AL_FATAL, al);
         return 0;
     }
 
@@ -3492,13 +3519,7 @@ static int tls_construct_encrypted_extensions(SSL *s, WPACKET *pkt)
 {
     int al;
 
-    /*
-     * TODO(TLS1.3): For now we send certificate extensions in with the
-     * encrypted extensions. Later we need to move these to the certificate
-     * message.
-     */
-    if (!tls_construct_extensions(s, pkt, EXT_TLS1_3_ENCRYPTED_EXTENSIONS
-                                          | EXT_TLS1_3_CERTIFICATE,
+    if (!tls_construct_extensions(s, pkt, EXT_TLS1_3_ENCRYPTED_EXTENSIONS,
                                   NULL, 0, &al)) {
         ssl3_send_alert(s, SSL3_AL_FATAL, al);
         SSLerr(SSL_F_TLS_CONSTRUCT_ENCRYPTED_EXTENSIONS, ERR_R_INTERNAL_ERROR);
diff --git a/test/recipes/70-test_tls13messages.t b/test/recipes/70-test_tls13messages.t
index 15dfa9f8d2..7286a67b60 100755
--- a/test/recipes/70-test_tls13messages.t
+++ b/test/recipes/70-test_tls13messages.t
@@ -87,10 +87,12 @@ $ENV{CTLOG_FILE} = srctop_file("test", "ct", "log_list.conf");
 
     [TLSProxy::Message::MT_ENCRYPTED_EXTENSIONS, TLSProxy::Message::EXT_SERVER_NAME,
         checkhandshake::SERVER_NAME_SRV_EXTENSION],
-    [TLSProxy::Message::MT_ENCRYPTED_EXTENSIONS, TLSProxy::Message::EXT_STATUS_REQUEST,
-        checkhandshake::STATUS_REQUEST_SRV_EXTENSION],
     [TLSProxy::Message::MT_ENCRYPTED_EXTENSIONS, TLSProxy::Message::EXT_ALPN,
         checkhandshake::ALPN_SRV_EXTENSION],
+
+    [TLSProxy::Message::MT_CERTIFICATE, TLSProxy::Message::EXT_STATUS_REQUEST,
+        checkhandshake::STATUS_REQUEST_SRV_EXTENSION],
+
     [0,0,0]
 );
 
diff --git a/test/testlib/checkhandshake.pm b/test/testlib/checkhandshake.pm
index 9529b949bd..0c3df6fde2 100644
--- a/test/testlib/checkhandshake.pm
+++ b/test/testlib/checkhandshake.pm
@@ -73,8 +73,14 @@ sub checkhandshake($$$$)
         if (($handtype & RENEG_HANDSHAKE) != 0) {
             $numtests += $#extensions + 2;
         }
-        #In TLS1.3 there are 3 messages with extensions (and no renegotiations)
-        $numtests += 1 if ($proxy->is_tls13());
+        #In TLS1.3 there are 4 messages with extensions (i.e. 2 extra) and no
+        #renegotiations: 1 ClientHello, 1 ServerHello, 1 EncryptedExtensions,
+        #1 Certificate
+        $numtests += 2 if ($proxy->is_tls13());
+        #Except in Client auth where we have an extra Certificate message, and
+        #one extension gets checked twice (once in each Certificate message)
+        $numtests += 2 if ($proxy->is_tls13()
+                          && ($handtype & CLIENT_AUTH_HANDSHAKE) != 0);
 
         plan tests => $numtests;
 
@@ -101,7 +107,11 @@ sub checkhandshake($$$$)
             next if ($message->mt() != TLSProxy::Message::MT_CLIENT_HELLO
                     && $message->mt() != TLSProxy::Message::MT_SERVER_HELLO
                     && $message->mt() !=
-                       TLSProxy::Message::MT_ENCRYPTED_EXTENSIONS);
+                       TLSProxy::Message::MT_ENCRYPTED_EXTENSIONS
+                    && $message->mt() != TLSProxy::Message::MT_CERTIFICATE);
+
+            next if $message->mt() == TLSProxy::Message::MT_CERTIFICATE
+                    && !TLSProxy::Proxy::is_tls13();
 
             if ($message->mt() == TLSProxy::Message::MT_CLIENT_HELLO) {
                 #Add renegotiate extension we will expect if renegotiating
diff --git a/util/TLSProxy/Certificate.pm b/util/TLSProxy/Certificate.pm
new file mode 100644
index 0000000000..d3bf7f2180
--- /dev/null
+++ b/util/TLSProxy/Certificate.pm
@@ -0,0 +1,219 @@
+# Copyright 2016 The OpenSSL Project Authors. All Rights Reserved.
+#
+# Licensed under the OpenSSL license (the "License").  You may not use
+# this file except in compliance with the License.  You can obtain a copy
+# in the file LICENSE in the source distribution or at
+# https://www.openssl.org/source/license.html
+
+use strict;
+
+package TLSProxy::Certificate;
+
+use vars '@ISA';
+push @ISA, 'TLSProxy::Message';
+
+sub new
+{
+    my $class = shift;
+    my ($server,
+        $data,
+        $records,
+        $startoffset,
+        $message_frag_lens) = @_;
+
+    my $self = $class->SUPER::new(
+        $server,
+        TLSProxy::Message::MT_CERTIFICATE,
+        $data,
+        $records,
+        $startoffset,
+        $message_frag_lens);
+
+    $self->{first_certificate} = "";
+    $self->{extension_data} = "";
+    $self->{remaining_certdata} = "";
+
+    return $self;
+}
+
+sub parse
+{
+    my $self = shift;
+
+    if (TLSProxy::Proxy->is_tls13()) {
+        my $context_len = unpack('C', $self->data);
+        my $context = substr($self->data, 1, $context_len);
+
+        my $remdata = substr($self->data, 1 + $context_len);
+
+        my ($hicertlistlen, $certlistlen) = unpack('Cn', $remdata);
+        $certlistlen += ($hicertlistlen << 16);
+
+        $remdata = substr($remdata, 3);
+
+        die "Invalid Certificate List length"
+            if length($remdata) != $certlistlen;
+
+        my ($hicertlen, $certlen) = unpack('Cn', $remdata);
+        $certlen += ($hicertlen << 16);
+
+        die "Certificate too long" if ($certlen + 3) > $certlistlen;
+
+        $remdata = substr($remdata, 3);
+
+        my $certdata = substr($remdata, 0, $certlen);
+
+        $remdata = substr($remdata, $certlen);
+
+        my $extensions_len = unpack('n', $remdata);
+        $remdata = substr($remdata, 2);
+
+        die "Extensions too long"
+            if ($certlen + 3 + $extensions_len + 2) > $certlistlen;
+
+        my $extension_data = "";
+        if ($extensions_len != 0) {
+            $extension_data = substr($remdata, 0, $extensions_len);
+
+            if (length($extension_data) != $extensions_len) {
+                die "Invalid extension length\n";
+            }
+        }
+        my %extensions = ();
+        while (length($extension_data) >= 4) {
+            my ($type, $size) = unpack("nn", $extension_data);
+            my $extdata = substr($extension_data, 4, $size);
+            $extension_data = substr($extension_data, 4 + $size);
+            $extensions{$type} = $extdata;
+        }
+        $remdata = substr($remdata, $extensions_len);
+
+        $self->context($context);
+        $self->first_certificate($certdata);
+        $self->extension_data(\%extensions);
+        $self->remaining_certdata($remdata);
+
+        print "    Context:".$context."\n";
+        print "    Certificate List Len:".$certlistlen."\n";
+        print "    Certificate Len:".$certlen."\n";
+        print "    Extensions Len:".$extensions_len."\n";
+    } else {
+        my ($hicertlistlen, $certlistlen) = unpack('Cn', $self->data);
+        $certlistlen += ($hicertlistlen << 16);
+
+        my $remdata = substr($self->data, 3);
+
+        die "Invalid Certificate List length"
+            if length($remdata) != $certlistlen;
+
+        my ($hicertlen, $certlen) = unpack('Cn', $remdata);
+        $certlen += ($hicertlen << 16);
+
+        die "Certificate too long" if ($certlen + 3) > $certlistlen;
+
+        $remdata = substr($remdata, 3);
+
+        my $certdata = substr($remdata, 0, $certlen);
+
+        $remdata = substr($remdata, $certlen);
+
+        $self->first_certificate($certdata);
+        $self->remaining_certdata($remdata);
+
+        print "    Certificate List Len:".$certlistlen."\n";
+        print "    Certificate Len:".$certlen."\n";
+    }
+}
+
+#Reconstruct the on-the-wire message data following changes
+sub set_message_contents
+{
+    my $self = shift;
+    my $data;
+    my $extensions = "";
+
+    if (TLSProxy::Proxy->is_tls13()) {
+        foreach my $key (keys %{$self->extension_data}) {
+            my $extdata = ${$self->extension_data}{$key};
+            $extensions .= pack("n", $key);
+            $extensions .= pack("n", length($extdata));
+            $extensions .= $extdata;
+            if ($key == TLSProxy::Message::EXT_DUPLICATE_EXTENSION) {
+              $extensions .= pack("n", $key);
+              $extensions .= pack("n", length($extdata));
+              $extensions .= $extdata;
+            }
+        }
+        $data = pack('C', length($self->context()));
+        $data .= $self->context;
+        my $certlen = length($self->first_certificate);
+        my $certlistlen = $certlen + length($extensions)
+                          + length($self->remaining_certdata);
+        my $hi = $certlistlen >> 16;
+        $certlistlen = $certlistlen & 0xffff;
+        $data .= pack('Cn', $hi, $certlistlen);
+        $hi = $certlen >> 16;
+        $certlen = $certlen & 0xffff;
+        $data .= pack('Cn', $hi, $certlen);
+        $data .= pack('n', length($extensions));
+        $data .= $extensions;
+        $data .= $self->remaining_certdata();
+        $self->data($data);
+    } else {
+        my $certlen = length($self->first_certificate);
+        my $certlistlen = $certlen + length($self->remaining_certdata);
+        my $hi = $certlistlen >> 16;
+        $certlistlen = $certlistlen & 0xffff;
+        $data .= pack('Cn', $hi, $certlistlen);
+        $hi = $certlen >> 16;
+        $certlen = $certlen & 0xffff;
+        $data .= pack('Cn', $hi, $certlen);
+        $data .= $self->remaining_certdata();
+        $self->data($data);
+    }
+}
+
+#Read/write accessors
+sub context
+{
+    my $self = shift;
+    if (@_) {
+      $self->{context} = shift;
+    }
+    return $self->{context};
+}
+sub first_certificate
+{
+    my $self = shift;
+    if (@_) {
+      $self->{first_certificate} = shift;
+    }
+    return $self->{first_certificate};
+}
+sub remaining_certdata
+{
+    my $self = shift;
+    if (@_) {
+      $self->{remaining_certdata} = shift;
+    }
+    return $self->{remaining_certdata};
+}
+sub extension_data
+{
+    my $self = shift;
+    if (@_) {
+      $self->{extension_data} = shift;
+    }
+    return $self->{extension_data};
+}
+sub set_extension
+{
+    my ($self, $ext_type, $ext_data) = @_;
+    $self->{extension_data}{$ext_type} = $ext_data;
+}
+sub delete_extension
+{
+    my ($self, $ext_type) = @_;
+    delete $self->{extension_data}{$ext_type};
+}
+1;
diff --git a/util/TLSProxy/Message.pm b/util/TLSProxy/Message.pm
index 7837787a03..704fe04db3 100644
--- a/util/TLSProxy/Message.pm
+++ b/util/TLSProxy/Message.pm
@@ -268,6 +268,15 @@ sub create_message
             [@message_frag_lens]
         );
         $message->parse();
+    } elsif ($mt == MT_CERTIFICATE) {
+        $message = TLSProxy::Certificate->new(
+            $server,
+            $data,
+            [@message_rec_list],
+            $startoffset,
+            [@message_frag_lens]
+        );
+        $message->parse();
     } elsif ($mt == MT_SERVER_KEY_EXCHANGE) {
         $message = TLSProxy::ServerKeyExchange->new(
             $server,
diff --git a/util/TLSProxy/Proxy.pm b/util/TLSProxy/Proxy.pm
index 84ca3a7510..067e9beb86 100644
--- a/util/TLSProxy/Proxy.pm
+++ b/util/TLSProxy/Proxy.pm
@@ -18,6 +18,7 @@ use TLSProxy::Message;
 use TLSProxy::ClientHello;
 use TLSProxy::ServerHello;
 use TLSProxy::EncryptedExtensions;
+use TLSProxy::Certificate;
 use TLSProxy::ServerKeyExchange;
 use TLSProxy::NewSessionTicket;