Solving sslv3 alert handshake failure when trying to use a client certificate

Not a definite answer but too much to fit in comments:

I hypothesize they gave you a cert that either has a wrong issuer (although their server could use a more specific alert code for that) or a wrong subject. We know the cert matches your privatekey -- because both curl and openssl client paired them without complaining about a mismatch; but we don't actually know it matches their desired CA(s) -- because your curl uses openssl and openssl SSL client does NOT enforce that a configured client cert matches certreq.CAs.

Do openssl x509 <clientcert.pem -noout -subject -issuer and the same on the cert from the test P12 that works. Do openssl s_client (or check the one you did) and look under Acceptable client certificate CA names; the name there or one of them should match (exactly!) the issuer(s) of your certs. If not, that's most likely your problem and you need to check with them you submitted your CSR to the correct place and in the correct way. Perhaps they have different regimes in different regions, or business lines, or test vs prod, or active vs pending, etc.

If the issuer of your cert does match desiredCAs, compare its subject to the working (test-P12) one: are they in similar format? are there any components in the working one not present in yours? If they allow it, try generating and submitting a new CSR with a subject name exactly the same as the test-P12 one, or as close as you can get, and see if that produces a cert that works better. (You don't have to generate a new key to do this, but if you choose to, keep track of which certs match which keys so you don't get them mixed up.) If that doesn't help look at the certificate extensions with openssl x509 <cert -noout -text for any difference(s) that might reasonably be related to subject authorization, like KeyUsage, ExtendedKeyUsage, maybe Policy, maybe Constraints, maybe even something nonstandard.

If all else fails, ask the server operator(s) what their logs say about the problem, or if you have access look at the logs yourself.

What SSL private key should be sent along with the client certificate?

None of them :)

One of the appealing things about client certificates is it does not do dumb things, like transmit a secret (like a password), in the plain text to a server (HTTP basic_auth). The password is still used to unlock the key for the client certificate, its just not used directly to during exchange or tp authenticate the client.

Instead, the client chooses a temporary, random key for that session. The client then signs the temporary, random key with his cert and sends it to the server (some hand waiving). If a bad guy intercepts anything, its random so it can't be used in the future. It can't even be used for a second run of the protocol with the server because the server will select a new, random value, too.

Fails with: error:14094410:SSL routines:SSL3_READ_BYTES:sslv3 alert handshake failure

Use TLS 1.0 and above; and use Server Name Indication.

You have not provided any code, so its not clear to me how to tell you what to do. Instead, here's the OpenSSL command line to test it:

openssl s_client -connect www.example.com:443 -tls1 -servername www.example.com \    -cert mycert.pem -key mykey.pem -CAfile <certificate-authority-for-service>.pem

You can also use -CAfile to avoid the “verify error:num=20”. See, for example, “verify error:num=20” when connecting to gateway.sandbox.push.apple.com.

The solution for me on a CentOS 8 system was checking the System Cryptography Policy by verifying the /etc/crypto-policies/config reads the default value of DEFAULT rather than any other value.

Once changing this value to DEFAULT, run the following command:

/usr/bin/update-crypto-policies --set DEFAULT

Rerun the curl command and it should work.