Implement a handshake hint for certificate compression.

While decompression is deterministic, compression is not. New revisions
of the compression algorithm may start using different (hopefully
smaller!) compressions. So this doesn't cause hint mismatches, add a
certificate compression hint. If the shim's Certificate message matches
the handshaker, we'll reuse the already compressed message.

This also adds what appears to be a missing test for when the server
cannot find compression algorithms in common.

Change-Id: Idbedaceb20208463d8f61581ee27971c17fcd126
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/48005
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/ssl/handoff.cc b/ssl/handoff.cc
index 7186b00..4324c75 100644
--- a/ssl/handoff.cc
+++ b/ssl/handoff.cc
@@ -779,6 +779,7 @@
 //     -- them up.
 //     decryptedPSKHint        [3] IMPLICIT OCTET STRING OPTIONAL,
 //     ignorePSKHint           [4] IMPLICIT NULL OPTIONAL,
+//     compressCertificateHint [5] IMPLICIT CompressCertificateHint OPTIONAL,
 // }
 //
 // KeyShareHint ::= SEQUENCE {
@@ -793,6 +794,12 @@
 //     subjectPublicKeyInfo    OCTET STRING,
 //     signature               OCTET STRING,
 // }
+//
+// CompressCertificateHint ::= SEQUENCE {
+//     algorithm               INTEGER,
+//     input                   OCTET STRING,
+//     compressed              OCTET STRING,
+// }
 
 // HandshakeHints tags.
 static const unsigned kServerRandomTag = CBS_ASN1_CONTEXT_SPECIFIC | 0;
@@ -802,6 +809,7 @@
     CBS_ASN1_CONSTRUCTED | CBS_ASN1_CONTEXT_SPECIFIC | 2;
 static const unsigned kDecryptedPSKTag = CBS_ASN1_CONTEXT_SPECIFIC | 3;
 static const unsigned kIgnorePSKTag = CBS_ASN1_CONTEXT_SPECIFIC | 4;
+static const unsigned kCompressCertificateTag = CBS_ASN1_CONTEXT_SPECIFIC | 5;
 
 int SSL_serialize_handshake_hints(const SSL *ssl, CBB *out) {
   const SSL_HANDSHAKE *hs = ssl->s3->hs.get();
@@ -811,15 +819,14 @@
   }
 
   const SSL_HANDSHAKE_HINTS *hints = hs->hints.get();
-  CBB seq, server_random, key_share_hint, signature_hint, decrypted_psk,
-      ignore_psk;
+  CBB seq, child;
   if (!CBB_add_asn1(out, &seq, CBS_ASN1_SEQUENCE)) {
     return 0;
   }
 
   if (!hints->server_random.empty()) {
-    if (!CBB_add_asn1(&seq, &server_random, kServerRandomTag) ||
-        !CBB_add_bytes(&server_random, hints->server_random.data(),
+    if (!CBB_add_asn1(&seq, &child, kServerRandomTag) ||
+        !CBB_add_bytes(&child, hints->server_random.data(),
                        hints->server_random.size())) {
       return 0;
     }
@@ -827,13 +834,11 @@
 
   if (hints->key_share_group_id != 0 && !hints->key_share_public_key.empty() &&
       !hints->key_share_secret.empty()) {
-    if (!CBB_add_asn1(&seq, &key_share_hint, kKeyShareHintTag) ||
-        !CBB_add_asn1_uint64(&key_share_hint, hints->key_share_group_id) ||
-        !CBB_add_asn1_octet_string(&key_share_hint,
-                                   hints->key_share_public_key.data(),
+    if (!CBB_add_asn1(&seq, &child, kKeyShareHintTag) ||
+        !CBB_add_asn1_uint64(&child, hints->key_share_group_id) ||
+        !CBB_add_asn1_octet_string(&child, hints->key_share_public_key.data(),
                                    hints->key_share_public_key.size()) ||
-        !CBB_add_asn1_octet_string(&key_share_hint,
-                                   hints->key_share_secret.data(),
+        !CBB_add_asn1_octet_string(&child, hints->key_share_secret.data(),
                                    hints->key_share_secret.size())) {
       return 0;
     }
@@ -841,33 +846,45 @@
 
   if (hints->signature_algorithm != 0 && !hints->signature_input.empty() &&
       !hints->signature.empty()) {
-    if (!CBB_add_asn1(&seq, &signature_hint, kSignatureHintTag) ||
-        !CBB_add_asn1_uint64(&signature_hint, hints->signature_algorithm) ||
-        !CBB_add_asn1_octet_string(&signature_hint,
-                                    hints->signature_input.data(),
-                                    hints->signature_input.size()) ||
-        !CBB_add_asn1_octet_string(&signature_hint,
-                                    hints->signature_spki.data(),
-                                    hints->signature_spki.size()) ||
-        !CBB_add_asn1_octet_string(&signature_hint, hints->signature.data(),
-                                    hints->signature.size())) {
+    if (!CBB_add_asn1(&seq, &child, kSignatureHintTag) ||
+        !CBB_add_asn1_uint64(&child, hints->signature_algorithm) ||
+        !CBB_add_asn1_octet_string(&child, hints->signature_input.data(),
+                                   hints->signature_input.size()) ||
+        !CBB_add_asn1_octet_string(&child, hints->signature_spki.data(),
+                                   hints->signature_spki.size()) ||
+        !CBB_add_asn1_octet_string(&child, hints->signature.data(),
+                                   hints->signature.size())) {
       return 0;
     }
   }
 
   if (!hints->decrypted_psk.empty()) {
-    if (!CBB_add_asn1(&seq, &decrypted_psk, kDecryptedPSKTag) ||
-        !CBB_add_bytes(&decrypted_psk, hints->decrypted_psk.data(),
+    if (!CBB_add_asn1(&seq, &child, kDecryptedPSKTag) ||
+        !CBB_add_bytes(&child, hints->decrypted_psk.data(),
                        hints->decrypted_psk.size())) {
       return 0;
     }
   }
 
   if (hints->ignore_psk &&  //
-      !CBB_add_asn1(&seq, &ignore_psk, kIgnorePSKTag)) {
+      !CBB_add_asn1(&seq, &child, kIgnorePSKTag)) {
     return 0;
   }
 
+  if (hints->cert_compression_alg_id != 0 &&
+      !hints->cert_compression_input.empty() &&
+      !hints->cert_compression_output.empty()) {
+    if (!CBB_add_asn1(&seq, &child, kCompressCertificateTag) ||
+        !CBB_add_asn1_uint64(&child, hints->cert_compression_alg_id) ||
+        !CBB_add_asn1_octet_string(&child, hints->cert_compression_input.data(),
+                                   hints->cert_compression_input.size()) ||
+        !CBB_add_asn1_octet_string(&child,
+                                   hints->cert_compression_output.data(),
+                                   hints->cert_compression_output.size())) {
+      return 0;
+    }
+  }
+
   return CBB_flush(out);
 }
 
@@ -882,9 +899,10 @@
     return 0;
   }
 
-  CBS cbs, seq, server_random, key_share, signature_hint, ticket, ignore_psk;
+  CBS cbs, seq, server_random, key_share, signature_hint, ticket, ignore_psk,
+      cert_compression;
   int has_server_random, has_key_share, has_signature_hint, has_ticket,
-      has_ignore_psk;
+      has_ignore_psk, has_cert_compression;
   CBS_init(&cbs, hints, hints_len);
   if (!CBS_get_asn1(&cbs, &seq, CBS_ASN1_SEQUENCE) ||
       !CBS_get_optional_asn1(&seq, &server_random, &has_server_random,
@@ -895,7 +913,9 @@
                              kSignatureHintTag) ||
       !CBS_get_optional_asn1(&seq, &ticket, &has_ticket, kDecryptedPSKTag) ||
       !CBS_get_optional_asn1(&seq, &ignore_psk, &has_ignore_psk,
-                             kIgnorePSKTag)) {
+                             kIgnorePSKTag) ||
+      !CBS_get_optional_asn1(&seq, &cert_compression, &has_cert_compression,
+                             kCompressCertificateTag)) {
     OPENSSL_PUT_ERROR(SSL, SSL_R_COULD_NOT_PARSE_HINTS);
     return 0;
   }
@@ -947,6 +967,21 @@
     hints_obj->ignore_psk = true;
   }
 
+  if (has_cert_compression) {
+    uint64_t alg;
+    CBS input, output;
+    if (!CBS_get_asn1_uint64(&cert_compression, &alg) ||  //
+        alg == 0 || alg > 0xffff ||
+        !CBS_get_asn1(&cert_compression, &input, CBS_ASN1_OCTETSTRING) ||
+        !hints_obj->cert_compression_input.CopyFrom(input) ||
+        !CBS_get_asn1(&cert_compression, &output, CBS_ASN1_OCTETSTRING) ||
+        !hints_obj->cert_compression_output.CopyFrom(output)) {
+      OPENSSL_PUT_ERROR(SSL, SSL_R_COULD_NOT_PARSE_HINTS);
+      return 0;
+    }
+    hints_obj->cert_compression_alg_id = static_cast<uint16_t>(alg);
+  }
+
   ssl->s3->hs->hints = std::move(hints_obj);
   return 1;
 }
diff --git a/ssl/internal.h b/ssl/internal.h
index 9c904b7..cb79494 100644
--- a/ssl/internal.h
+++ b/ssl/internal.h
@@ -1651,6 +1651,10 @@
 
   Array<uint8_t> decrypted_psk;
   bool ignore_psk = false;
+
+  uint16_t cert_compression_alg_id = 0;
+  Array<uint8_t> cert_compression_input;
+  Array<uint8_t> cert_compression_output;
 };
 
 struct SSL_HANDSHAKE {
diff --git a/ssl/test/runner/common.go b/ssl/test/runner/common.go
index b753dc8..4c4ddff 100644
--- a/ssl/test/runner/common.go
+++ b/ssl/test/runner/common.go
@@ -1789,6 +1789,10 @@
 	// used on this connection, or zero if there are no special requirements.
 	ExpectedCompressedCert uint16
 
+	// ExpectUncompressedCert, if true, specifies that certificate compression
+	// should not be used on this connection.
+	ExpectUncompressedCert bool
+
 	// SendCertCompressionAlgID, if not zero, sets the algorithm ID that will be
 	// sent in the compressed certificate message.
 	SendCertCompressionAlgID uint16
diff --git a/ssl/test/runner/handshake_client.go b/ssl/test/runner/handshake_client.go
index 158e52c..424b206 100644
--- a/ssl/test/runner/handshake_client.go
+++ b/ssl/test/runner/handshake_client.go
@@ -1200,6 +1200,10 @@
 			if expected := c.config.Bugs.ExpectedCompressedCert; expected != 0 && expected != compressedCertMsg.algID {
 				return fmt.Errorf("tls: expected certificate compressed with algorithm %x, but message used %x", expected, compressedCertMsg.algID)
 			}
+
+			if c.config.Bugs.ExpectUncompressedCert {
+				return errors.New("tls: compressed certificate received")
+			}
 		} else {
 			if certMsg, ok = msg.(*certificateMsg); !ok {
 				c.sendAlert(alertUnexpectedMessage)
diff --git a/ssl/test/runner/handshake_server.go b/ssl/test/runner/handshake_server.go
index 7319f92..00bfd41 100644
--- a/ssl/test/runner/handshake_server.go
+++ b/ssl/test/runner/handshake_server.go
@@ -1072,7 +1072,10 @@
 			for _, id := range hs.clientHello.compressedCertAlgs {
 				if id == candidate {
 					if expected := config.Bugs.ExpectedCompressedCert; expected != 0 && expected != id {
-						return fmt.Errorf("expected to send compressed cert with alg %d, but picked %d", expected, id)
+						return fmt.Errorf("tls: expected to send compressed cert with alg %d, but picked %d", expected, id)
+					}
+					if config.Bugs.ExpectUncompressedCert {
+						return errors.New("tls: expected to send uncompressed cert")
 					}
 
 					if override := config.Bugs.SendCertCompressionAlgID; override != 0 {
@@ -1101,7 +1104,7 @@
 
 		if !sentCompressedCertMsg {
 			if config.Bugs.ExpectedCompressedCert != 0 {
-				return errors.New("unexpectedly sent uncompressed certificate")
+				return errors.New("tls: unexpectedly sent uncompressed certificate")
 			}
 			hs.writeServerHash(certMsgBytes)
 			c.writeRecord(recordTypeHandshake, certMsgBytes)
diff --git a/ssl/test/runner/runner.go b/ssl/test/runner/runner.go
index 657394c..3ab350d 100644
--- a/ssl/test/runner/runner.go
+++ b/ssl/test/runner/runner.go
@@ -15681,51 +15681,72 @@
 	}
 }
 
-func addCertCompressionTests() {
+const (
+	shrinkingCompressionAlgID = 0xff01
+	expandingCompressionAlgID = 0xff02
+	randomCompressionAlgID    = 0xff03
+)
+
+var (
 	// shrinkingPrefix is the first two bytes of a Certificate message.
-	shrinkingPrefix := []byte{0, 0}
+	shrinkingPrefix = []byte{0, 0}
 	// expandingPrefix is just some arbitrary byte string. This has to match the
 	// value in the shim.
-	expandingPrefix := []byte{1, 2, 3, 4}
+	expandingPrefix = []byte{1, 2, 3, 4}
+)
 
-	shrinking := CertCompressionAlg{
-		Compress: func(uncompressed []byte) []byte {
-			if !bytes.HasPrefix(uncompressed, shrinkingPrefix) {
-				panic(fmt.Sprintf("cannot compress certificate message %x", uncompressed))
-			}
-			return uncompressed[len(shrinkingPrefix):]
-		},
-		Decompress: func(out []byte, compressed []byte) bool {
-			if len(out) != len(shrinkingPrefix)+len(compressed) {
-				return false
-			}
+var shrinkingCompression = CertCompressionAlg{
+	Compress: func(uncompressed []byte) []byte {
+		if !bytes.HasPrefix(uncompressed, shrinkingPrefix) {
+			panic(fmt.Sprintf("cannot compress certificate message %x", uncompressed))
+		}
+		return uncompressed[len(shrinkingPrefix):]
+	},
+	Decompress: func(out []byte, compressed []byte) bool {
+		if len(out) != len(shrinkingPrefix)+len(compressed) {
+			return false
+		}
 
-			copy(out, shrinkingPrefix)
-			copy(out[len(shrinkingPrefix):], compressed)
-			return true
-		},
-	}
+		copy(out, shrinkingPrefix)
+		copy(out[len(shrinkingPrefix):], compressed)
+		return true
+	},
+}
 
-	expanding := CertCompressionAlg{
-		Compress: func(uncompressed []byte) []byte {
-			ret := make([]byte, 0, len(expandingPrefix)+len(uncompressed))
-			ret = append(ret, expandingPrefix...)
-			return append(ret, uncompressed...)
-		},
-		Decompress: func(out []byte, compressed []byte) bool {
-			if !bytes.HasPrefix(compressed, expandingPrefix) {
-				return false
-			}
-			copy(out, compressed[len(expandingPrefix):])
-			return true
-		},
-	}
+var expandingCompression = CertCompressionAlg{
+	Compress: func(uncompressed []byte) []byte {
+		ret := make([]byte, 0, len(expandingPrefix)+len(uncompressed))
+		ret = append(ret, expandingPrefix...)
+		return append(ret, uncompressed...)
+	},
+	Decompress: func(out []byte, compressed []byte) bool {
+		if !bytes.HasPrefix(compressed, expandingPrefix) {
+			return false
+		}
+		copy(out, compressed[len(expandingPrefix):])
+		return true
+	},
+}
 
-	const (
-		shrinkingAlgID = 0xff01
-		expandingAlgID = 0xff02
-	)
+var randomCompression = CertCompressionAlg{
+	Compress: func(uncompressed []byte) []byte {
+		ret := make([]byte, 1+len(uncompressed))
+		if _, err := rand.Read(ret[:1]); err != nil {
+			panic(err)
+		}
+		copy(ret[1:], uncompressed)
+		return ret
+	},
+	Decompress: func(out []byte, compressed []byte) bool {
+		if len(compressed) != 1+len(out) {
+			return false
+		}
+		copy(out, compressed[1:])
+		return true
+	},
+}
 
+func addCertCompressionTests() {
 	for _, ver := range tlsVersions {
 		if ver.version < VersionTLS12 {
 			continue
@@ -15770,9 +15791,11 @@
 				name:     "CertCompressionIgnoredBefore13-" + ver.name,
 				flags:    []string{"-install-cert-compression-algs"},
 				config: Config{
-					MinVersion:          ver.version,
-					MaxVersion:          ver.version,
-					CertCompressionAlgs: map[uint16]CertCompressionAlg{expandingAlgID: expanding},
+					MinVersion: ver.version,
+					MaxVersion: ver.version,
+					CertCompressionAlgs: map[uint16]CertCompressionAlg{
+						expandingCompressionAlgID: expandingCompression,
+					},
 				},
 			})
 
@@ -15784,11 +15807,13 @@
 			name:     "CertCompressionExpands-" + ver.name,
 			flags:    []string{"-install-cert-compression-algs"},
 			config: Config{
-				MinVersion:          ver.version,
-				MaxVersion:          ver.version,
-				CertCompressionAlgs: map[uint16]CertCompressionAlg{expandingAlgID: expanding},
+				MinVersion: ver.version,
+				MaxVersion: ver.version,
+				CertCompressionAlgs: map[uint16]CertCompressionAlg{
+					expandingCompressionAlgID: expandingCompression,
+				},
 				Bugs: ProtocolBugs{
-					ExpectedCompressedCert: expandingAlgID,
+					ExpectedCompressedCert: expandingCompressionAlgID,
 				},
 			},
 		})
@@ -15798,17 +15823,39 @@
 			name:     "CertCompressionShrinks-" + ver.name,
 			flags:    []string{"-install-cert-compression-algs"},
 			config: Config{
-				MinVersion:          ver.version,
-				MaxVersion:          ver.version,
-				CertCompressionAlgs: map[uint16]CertCompressionAlg{shrinkingAlgID: shrinking},
+				MinVersion: ver.version,
+				MaxVersion: ver.version,
+				CertCompressionAlgs: map[uint16]CertCompressionAlg{
+					shrinkingCompressionAlgID: shrinkingCompression,
+				},
 				Bugs: ProtocolBugs{
-					ExpectedCompressedCert: shrinkingAlgID,
+					ExpectedCompressedCert: shrinkingCompressionAlgID,
+				},
+			},
+		})
+
+		// Test that the shim behaves consistently if the compression function
+		// is non-deterministic. This is intended to model version differences
+		// between the shim and handshaker with handshake hints, but it is also
+		// useful in confirming we only call the callbacks once.
+		testCases = append(testCases, testCase{
+			testType: serverTest,
+			name:     "CertCompressionRandom-" + ver.name,
+			flags:    []string{"-install-cert-compression-algs"},
+			config: Config{
+				MinVersion: ver.version,
+				MaxVersion: ver.version,
+				CertCompressionAlgs: map[uint16]CertCompressionAlg{
+					randomCompressionAlgID: randomCompression,
+				},
+				Bugs: ProtocolBugs{
+					ExpectedCompressedCert: randomCompressionAlgID,
 				},
 			},
 		})
 
 		// With both algorithms configured, the server should pick its most
-		// preferable. (Which is expandingAlgID.)
+		// preferable. (Which is expandingCompressionAlgID.)
 		testCases = append(testCases, testCase{
 			testType: serverTest,
 			name:     "CertCompressionPriority-" + ver.name,
@@ -15817,11 +15864,29 @@
 				MinVersion: ver.version,
 				MaxVersion: ver.version,
 				CertCompressionAlgs: map[uint16]CertCompressionAlg{
-					shrinkingAlgID: shrinking,
-					expandingAlgID: expanding,
+					shrinkingCompressionAlgID: shrinkingCompression,
+					expandingCompressionAlgID: expandingCompression,
 				},
 				Bugs: ProtocolBugs{
-					ExpectedCompressedCert: expandingAlgID,
+					ExpectedCompressedCert: expandingCompressionAlgID,
+				},
+			},
+		})
+
+		// With no common algorithms configured, the server should decline
+		// compression.
+		testCases = append(testCases, testCase{
+			testType: serverTest,
+			name:     "CertCompressionNoCommonAlgs-" + ver.name,
+			flags:    []string{"-install-one-cert-compression-alg", strconv.Itoa(shrinkingCompressionAlgID)},
+			config: Config{
+				MinVersion: ver.version,
+				MaxVersion: ver.version,
+				CertCompressionAlgs: map[uint16]CertCompressionAlg{
+					expandingCompressionAlgID: expandingCompression,
+				},
+				Bugs: ProtocolBugs{
+					ExpectUncompressedCert: true,
 				},
 			},
 		})
@@ -15834,10 +15899,10 @@
 				MinVersion: ver.version,
 				MaxVersion: ver.version,
 				CertCompressionAlgs: map[uint16]CertCompressionAlg{
-					expandingAlgID: expanding,
+					expandingCompressionAlgID: expandingCompression,
 				},
 				Bugs: ProtocolBugs{
-					ExpectedCompressedCert: expandingAlgID,
+					ExpectedCompressedCert: expandingCompressionAlgID,
 				},
 			},
 		})
@@ -15850,10 +15915,10 @@
 				MinVersion: ver.version,
 				MaxVersion: ver.version,
 				CertCompressionAlgs: map[uint16]CertCompressionAlg{
-					shrinkingAlgID: shrinking,
+					shrinkingCompressionAlgID: shrinkingCompression,
 				},
 				Bugs: ProtocolBugs{
-					ExpectedCompressedCert: shrinkingAlgID,
+					ExpectedCompressedCert: shrinkingCompressionAlgID,
 				},
 			},
 		})
@@ -15866,10 +15931,10 @@
 				MinVersion: ver.version,
 				MaxVersion: ver.version,
 				CertCompressionAlgs: map[uint16]CertCompressionAlg{
-					shrinkingAlgID: shrinking,
+					shrinkingCompressionAlgID: shrinkingCompression,
 				},
 				Bugs: ProtocolBugs{
-					ExpectedCompressedCert:   shrinkingAlgID,
+					ExpectedCompressedCert:   shrinkingCompressionAlgID,
 					SendCertCompressionAlgID: 1234,
 				},
 			},
@@ -15885,10 +15950,10 @@
 				MinVersion: ver.version,
 				MaxVersion: ver.version,
 				CertCompressionAlgs: map[uint16]CertCompressionAlg{
-					shrinkingAlgID: shrinking,
+					shrinkingCompressionAlgID: shrinkingCompression,
 				},
 				Bugs: ProtocolBugs{
-					ExpectedCompressedCert:     shrinkingAlgID,
+					ExpectedCompressedCert:     shrinkingCompressionAlgID,
 					SendCertUncompressedLength: 12,
 				},
 			},
@@ -15904,10 +15969,10 @@
 				MinVersion: ver.version,
 				MaxVersion: ver.version,
 				CertCompressionAlgs: map[uint16]CertCompressionAlg{
-					shrinkingAlgID: shrinking,
+					shrinkingCompressionAlgID: shrinkingCompression,
 				},
 				Bugs: ProtocolBugs{
-					ExpectedCompressedCert:     shrinkingAlgID,
+					ExpectedCompressedCert:     shrinkingCompressionAlgID,
 					SendCertUncompressedLength: 1 << 20,
 				},
 			},
@@ -17230,6 +17295,101 @@
 				},
 			})
 		}
+
+		// The shim and handshaker may disagree on the certificate compression
+		// algorithm, whether to enable certificate compression, or certificate
+		// compression inputs.
+		testCases = append(testCases, testCase{
+			name:               protocol.String() + "-HintMismatch-CertificateCompression-ShimOnly",
+			testType:           serverTest,
+			protocol:           protocol,
+			skipSplitHandshake: true,
+			config: Config{
+				MinVersion: VersionTLS13,
+				MaxVersion: VersionTLS13,
+				CertCompressionAlgs: map[uint16]CertCompressionAlg{
+					shrinkingCompressionAlgID: shrinkingCompression,
+				},
+				Bugs: ProtocolBugs{
+					ExpectedCompressedCert: shrinkingCompressionAlgID,
+				},
+			},
+			flags: []string{
+				"-allow-hint-mismatch",
+				"-on-shim-install-cert-compression-algs",
+			},
+		})
+		testCases = append(testCases, testCase{
+			name:               protocol.String() + "-HintMismatch-CertificateCompression-HandshakerOnly",
+			testType:           serverTest,
+			protocol:           protocol,
+			skipSplitHandshake: true,
+			config: Config{
+				MinVersion: VersionTLS13,
+				MaxVersion: VersionTLS13,
+				CertCompressionAlgs: map[uint16]CertCompressionAlg{
+					shrinkingCompressionAlgID: shrinkingCompression,
+				},
+				Bugs: ProtocolBugs{
+					ExpectUncompressedCert: true,
+				},
+			},
+			flags: []string{
+				"-allow-hint-mismatch",
+				"-on-handshaker-install-cert-compression-algs",
+			},
+		})
+		testCases = append(testCases, testCase{
+			testType:           serverTest,
+			name:               protocol.String() + "-HintMismatch-CertificateCompression-AlgorithmMismatch",
+			protocol:           protocol,
+			skipSplitHandshake: true,
+			config: Config{
+				MinVersion: VersionTLS13,
+				MaxVersion: VersionTLS13,
+				CertCompressionAlgs: map[uint16]CertCompressionAlg{
+					shrinkingCompressionAlgID: shrinkingCompression,
+					expandingCompressionAlgID: expandingCompression,
+				},
+				Bugs: ProtocolBugs{
+					// The shim's preferences should take effect.
+					ExpectedCompressedCert: shrinkingCompressionAlgID,
+				},
+			},
+			flags: []string{
+				"-allow-hint-mismatch",
+				"-on-shim-install-one-cert-compression-alg", strconv.Itoa(shrinkingCompressionAlgID),
+				"-on-handshaker-install-one-cert-compression-alg", strconv.Itoa(expandingCompressionAlgID),
+			},
+		})
+		testCases = append(testCases, testCase{
+			testType:           serverTest,
+			name:               protocol.String() + "-HintMismatch-CertificateCompression-InputMismatch",
+			protocol:           protocol,
+			skipSplitHandshake: true,
+			config: Config{
+				MinVersion: VersionTLS13,
+				MaxVersion: VersionTLS13,
+				CertCompressionAlgs: map[uint16]CertCompressionAlg{
+					shrinkingCompressionAlgID: shrinkingCompression,
+				},
+				Bugs: ProtocolBugs{
+					ExpectedCompressedCert: shrinkingCompressionAlgID,
+				},
+			},
+			flags: []string{
+				"-allow-hint-mismatch",
+				"-install-cert-compression-algs",
+				// Configure the shim and handshaker with different OCSP
+				// responses, so the compression inputs do not match.
+				"-on-shim-ocsp-response", base64.StdEncoding.EncodeToString(testOCSPResponse),
+				"-on-handshaker-ocsp-response", base64.StdEncoding.EncodeToString(testOCSPResponse2),
+			},
+			expectations: connectionExpectations{
+				// The shim's configuration should take precendence.
+				ocspResponse: testOCSPResponse,
+			},
+		})
 	}
 }
 
diff --git a/ssl/test/test_config.cc b/ssl/test/test_config.cc
index 9fa8c0f..e24f79b 100644
--- a/ssl/test/test_config.cc
+++ b/ssl/test/test_config.cc
@@ -234,6 +234,8 @@
     {"-read-size", &TestConfig::read_size},
     {"-expect-ticket-age-skew", &TestConfig::expect_ticket_age_skew},
     {"-quic-use-legacy-codepoint", &TestConfig::quic_use_legacy_codepoint},
+    {"-install-one-cert-compression-alg",
+     &TestConfig::install_one_cert_compression_alg},
     {"-early-write-after-message", &TestConfig::early_write_after_message},
 };
 
@@ -1326,6 +1328,17 @@
     SendQuicAlert,
 };
 
+static bool MaybeInstallCertCompressionAlg(
+    const TestConfig *config, SSL_CTX *ssl_ctx, uint16_t alg,
+    ssl_cert_compression_func_t compress,
+    ssl_cert_decompression_func_t decompress) {
+  if (!config->install_cert_compression_algs &&
+      config->install_one_cert_compression_alg != alg) {
+    return true;
+  }
+  return SSL_CTX_add_cert_compression_alg(ssl_ctx, alg, compress, decompress);
+}
+
 bssl::UniquePtr<SSL_CTX> TestConfig::SetupCtx(SSL_CTX *old_ctx) const {
   bssl::UniquePtr<SSL_CTX> ssl_ctx(
       SSL_CTX_new(is_dtls ? DTLS_method() : TLS_method()));
@@ -1456,48 +1469,65 @@
     return nullptr;
   }
 
-  if (install_cert_compression_algs &&
-      (!SSL_CTX_add_cert_compression_alg(
-           ssl_ctx.get(), 0xff02,
-           [](SSL *ssl, CBB *out, const uint8_t *in, size_t in_len) -> int {
-             if (!CBB_add_u8(out, 1) || !CBB_add_u8(out, 2) ||
-                 !CBB_add_u8(out, 3) || !CBB_add_u8(out, 4) ||
-                 !CBB_add_bytes(out, in, in_len)) {
-               return 0;
-             }
-             return 1;
-           },
-           [](SSL *ssl, CRYPTO_BUFFER **out, size_t uncompressed_len,
-              const uint8_t *in, size_t in_len) -> int {
-             if (in_len < 4 || in[0] != 1 || in[1] != 2 || in[2] != 3 ||
-                 in[3] != 4 || uncompressed_len != in_len - 4) {
-               return 0;
-             }
-             const bssl::Span<const uint8_t> uncompressed(in + 4, in_len - 4);
-             *out = CRYPTO_BUFFER_new(uncompressed.data(), uncompressed.size(),
-                                      nullptr);
-             return 1;
-           }) ||
-       !SSL_CTX_add_cert_compression_alg(
-           ssl_ctx.get(), 0xff01,
-           [](SSL *ssl, CBB *out, const uint8_t *in, size_t in_len) -> int {
-             if (in_len < 2 || in[0] != 0 || in[1] != 0) {
-               return 0;
-             }
-             return CBB_add_bytes(out, in + 2, in_len - 2);
-           },
-           [](SSL *ssl, CRYPTO_BUFFER **out, size_t uncompressed_len,
-              const uint8_t *in, size_t in_len) -> int {
-             if (uncompressed_len != 2 + in_len) {
-               return 0;
-             }
-             std::unique_ptr<uint8_t[]> buf(new uint8_t[2 + in_len]);
-             buf[0] = 0;
-             buf[1] = 0;
-             OPENSSL_memcpy(&buf[2], in, in_len);
-             *out = CRYPTO_BUFFER_new(buf.get(), 2 + in_len, nullptr);
-             return 1;
-           }))) {
+  // These mock compression algorithms match the corresponding ones in
+  // |addCertCompressionTests|.
+  if (!MaybeInstallCertCompressionAlg(
+          this, ssl_ctx.get(), 0xff02,
+          [](SSL *ssl, CBB *out, const uint8_t *in, size_t in_len) -> int {
+            if (!CBB_add_u8(out, 1) || !CBB_add_u8(out, 2) ||
+                !CBB_add_u8(out, 3) || !CBB_add_u8(out, 4) ||
+                !CBB_add_bytes(out, in, in_len)) {
+              return 0;
+            }
+            return 1;
+          },
+          [](SSL *ssl, CRYPTO_BUFFER **out, size_t uncompressed_len,
+             const uint8_t *in, size_t in_len) -> int {
+            if (in_len < 4 || in[0] != 1 || in[1] != 2 || in[2] != 3 ||
+                in[3] != 4 || uncompressed_len != in_len - 4) {
+              return 0;
+            }
+            const bssl::Span<const uint8_t> uncompressed(in + 4, in_len - 4);
+            *out = CRYPTO_BUFFER_new(uncompressed.data(), uncompressed.size(),
+                                     nullptr);
+            return *out != nullptr;
+          }) ||
+      !MaybeInstallCertCompressionAlg(
+          this, ssl_ctx.get(), 0xff01,
+          [](SSL *ssl, CBB *out, const uint8_t *in, size_t in_len) -> int {
+            if (in_len < 2 || in[0] != 0 || in[1] != 0) {
+              return 0;
+            }
+            return CBB_add_bytes(out, in + 2, in_len - 2);
+          },
+          [](SSL *ssl, CRYPTO_BUFFER **out, size_t uncompressed_len,
+             const uint8_t *in, size_t in_len) -> int {
+            if (uncompressed_len != 2 + in_len) {
+              return 0;
+            }
+            std::unique_ptr<uint8_t[]> buf(new uint8_t[2 + in_len]);
+            buf[0] = 0;
+            buf[1] = 0;
+            OPENSSL_memcpy(&buf[2], in, in_len);
+            *out = CRYPTO_BUFFER_new(buf.get(), 2 + in_len, nullptr);
+            return *out != nullptr;
+          }) ||
+      !MaybeInstallCertCompressionAlg(
+          this, ssl_ctx.get(), 0xff03,
+          [](SSL *ssl, CBB *out, const uint8_t *in, size_t in_len) -> int {
+            uint8_t byte;
+            return RAND_bytes(&byte, 1) &&   //
+                   CBB_add_u8(out, byte) &&  //
+                   CBB_add_bytes(out, in, in_len);
+          },
+          [](SSL *ssl, CRYPTO_BUFFER **out, size_t uncompressed_len,
+             const uint8_t *in, size_t in_len) -> int {
+            if (uncompressed_len + 1 != in_len) {
+              return 0;
+            }
+            *out = CRYPTO_BUFFER_new(in + 1, in_len - 1, nullptr);
+            return *out != nullptr;
+          })) {
     fprintf(stderr, "SSL_CTX_add_cert_compression_alg failed.\n");
     abort();
   }
diff --git a/ssl/test/test_config.h b/ssl/test/test_config.h
index 2478d49..a1860c7 100644
--- a/ssl/test/test_config.h
+++ b/ssl/test/test_config.h
@@ -173,6 +173,7 @@
   bool decline_ocsp_callback = false;
   bool fail_ocsp_callback = false;
   bool install_cert_compression_algs = false;
+  int install_one_cert_compression_alg = 0;
   bool reverify_on_resume = false;
   bool enforce_rsa_key_usage = false;
   bool is_handshaker_supported = false;
diff --git a/ssl/tls13_both.cc b/ssl/tls13_both.cc
index 5837187..0354f39 100644
--- a/ssl/tls13_both.cc
+++ b/ssl/tls13_both.cc
@@ -534,9 +534,37 @@
                                  SSL3_MT_COMPRESSED_CERTIFICATE) ||
       !CBB_add_u16(body, hs->cert_compression_alg_id) ||
       !CBB_add_u24(body, msg.size()) ||
-      !CBB_add_u24_length_prefixed(body, &compressed) ||
-      !alg->compress(ssl, &compressed, msg.data(), msg.size()) ||
-      !ssl_add_message_cbb(ssl, cbb.get())) {
+      !CBB_add_u24_length_prefixed(body, &compressed)) {
+    OPENSSL_PUT_ERROR(SSL, ERR_R_INTERNAL_ERROR);
+    return false;
+  }
+
+  SSL_HANDSHAKE_HINTS *const hints = hs->hints.get();
+  if (hints && !hs->hints_requested &&
+      hints->cert_compression_alg_id == hs->cert_compression_alg_id &&
+      hints->cert_compression_input == MakeConstSpan(msg) &&
+      !hints->cert_compression_output.empty()) {
+    if (!CBB_add_bytes(&compressed, hints->cert_compression_output.data(),
+                       hints->cert_compression_output.size())) {
+      OPENSSL_PUT_ERROR(SSL, ERR_R_INTERNAL_ERROR);
+      return false;
+    }
+  } else {
+    if (!alg->compress(ssl, &compressed, msg.data(), msg.size())) {
+      OPENSSL_PUT_ERROR(SSL, ERR_R_INTERNAL_ERROR);
+      return false;
+    }
+    if (hints && hs->hints_requested) {
+      hints->cert_compression_alg_id = hs->cert_compression_alg_id;
+      if (!hints->cert_compression_input.CopyFrom(msg) ||
+          !hints->cert_compression_output.CopyFrom(
+              MakeConstSpan(CBB_data(&compressed), CBB_len(&compressed)))) {
+        return false;
+      }
+    }
+  }
+
+  if (!ssl_add_message_cbb(ssl, cbb.get())) {
     OPENSSL_PUT_ERROR(SSL, ERR_R_INTERNAL_ERROR);
     return false;
   }