Comment by ekr____

Yes, this is a seriously difficult problem with only partial solutions.

The basic math of any kind of negotiation is that you need the minimum set of cryptographic parameters supported by both sides to be secure enough to resist downgrade. This is too small a space to support a complete accounting of the situation, but roughly:

- In pre-TLS 1.3 versions of TLS, the Finished message was intended to provide secure negotiation as long as the weakest joint key exchange was secure, even if the weakest joint record protection algorithm was insecure, because the Finished provides integrity for the handshake outside of the record layer.

- In TLS 1.3, the negotiation messages are also signed by the server, which is intended to protect negotiation as long as the weakest joint signature algorithm is secure. This is (I believe) the best you can do with a client and server which have never talked to each other, because if the signature algorithm is insecure, the attacker can just impersonate the server directly.

- TLS 1.3 also includes a mechanism intended to prevent against TLS 1.3 -> TLS 1.2 downgrade as long as the TLS 1.2 cipher suite involves server signing (as a practical matter, this means ECDHE). Briefly, the idea is to use a sentinel value in the random nonces, which are signed even in TLS 1.2 (https://www.rfc-editor.org/rfc/rfc8446#section-4.1.3).