Enabling SSLv2Hello causes SSL handshake failure against AWS endpoints

We are hosting on AWS, and all our endpoints use predefined security policies that do not allow TLS below 1.2 (that is, TLS-1-2-2017-01 for ELB or TLSv1.2_2018 for CloudFront).

One of our customers complained that connecting to our endpoint from a Java client fails with SSLHandshakeException, and confirmed, that TLSv1.2 was enabled in the client.

Further investigation indicated that the client had also SSLv2Hello enabled for legacy reasons. Disabling it solved the issue, however, I still don't quite understand why it was an issue in the first place.

Experiments show that the issue only stands for AWS endpoints - I tried various websites hosted on AWS through ELB and Cloudfront, and got this error. Sites hosted on AWS, but using other SSL solutions (e.g. LetsEncrypt) do not have this issue, nor have it websites hosted elsewhere.

Here is a simple Java snippet that I used for experimenting:

import java.net.HttpURLConnection;
import java.net.URL;
import java.util.HashMap;

public class TestConnect {

    public static void main(String[] args) {
      String url="https://alertlogic.com"; // hosted on AWS behind ELB - failure
//      String url="https://myx.ostankin.net"; // hosted on AWS, but using LetsEncrypt - ok
//      String url="https://google.com"; // Not hosted on AWS - ok
        System.setProperty("https.protocols", "TLSv1.2,SSLv2Hello");
//        System.setProperty("https.protocols", "TLSv1.2");
      try {
        URL restURL = new URL(url);
        HttpURLConnection conn = (HttpURLConnection) restURL.openConnection();
        conn.setRequestMethod("GET");
        int responseCode = conn.getResponseCode();
        String responseMessage = conn.getResponseMessage();
        System.out.println("Response:");
        System.out.println(responseMessage);
      } catch(Exception e) {
        e.printStackTrace();
      }
    }
}

When run in the given configuration, it fails with the following exception:

javax.net.ssl.SSLHandshakeException: Received fatal alert: handshake_failure
    at sun.security.ssl.Alerts.getSSLException(Alerts.java:192)
    at sun.security.ssl.Alerts.getSSLException(Alerts.java:154)
    at sun.security.ssl.SSLSocketImpl.recvAlert(SSLSocketImpl.java:2023)
    at sun.security.ssl.SSLSocketImpl.readRecord(SSLSocketImpl.java:1125)
    at sun.security.ssl.SSLSocketImpl.performInitialHandshake(SSLSocketImpl.java:1375)
    at sun.security.ssl.SSLSocketImpl.startHandshake(SSLSocketImpl.java:1403)
    at sun.security.ssl.SSLSocketImpl.startHandshake(SSLSocketImpl.java:1387)
    at sun.net.www.protocol.https.HttpsClient.afterConnect(HttpsClient.java:559)
    at sun.net.www.protocol.https.AbstractDelegateHttpsURLConnection.connect(AbstractDelegateHttpsURLConnection.java:185)
    at sun.net.www.protocol.http.HttpURLConnection.followRedirect0(HttpURLConnection.java:2701)
    at sun.net.www.protocol.http.HttpURLConnection.followRedirect(HttpURLConnection.java:2623)
    at sun.net.www.protocol.http.HttpURLConnection.getInputStream0(HttpURLConnection.java:1806)
    at sun.net.www.protocol.http.HttpURLConnection.getInputStream(HttpURLConnection.java:1474)
    at java.net.HttpURLConnection.getResponseCode(HttpURLConnection.java:480)
    at sun.net.www.protocol.https.HttpsURLConnectionImpl.getResponseCode(HttpsURLConnectionImpl.java:338)
    at TestConnect.main(TestConnect.java:17)

Running with -Djavax.net.debug=ssl:handshake provides a rather lengthy output, but if I cut all the initialisation stuff, it ends like this:

main, READ: TLSv1.2 Handshake, length = 333
*** ECDH ServerKeyExchange
Signature Algorithm SHA1withRSA
Server key: Sun EC public key, 256 bits
  public x coord: 21436757520046799441414055942148383722667165679440737888092161490006597177581
  public y coord: 15404188333633930557065698234035214201299701177286160881126576519412706199661
  parameters: secp256r1 [NIST P-256, X9.62 prime256v1] (1.2.840.10045.3.1.7)
main, READ: TLSv1.2 Handshake, length = 4
*** ServerHelloDone
*** ECDHClientKeyExchange
ECDH Public value:  { 4, 244, 123, 66, 147, 148, 50, 164, 198, 11, 116, 147, 132, 129, 249, 46, 144, 69, 1, 121, 111, 104, 31, 233, 10, 114, 250, 76, 140, 98, 224, 1, 117, 35, 0, 227, 49, 251, 226, 190, 74, 117, 251, 22, 229, 1, 140, 173, 234, 126, 79, 206, 67, 169, 150, 47, 135, 212, 84, 98, 225, 148, 102, 145, 220 }
main, WRITE: TLSv1.2 Handshake, length = 70
SESSION KEYGEN:
PreMaster Secret:
0000: FB 1D 4C 57 26 1E 10 D9   57 2A 37 71 D8 B0 7A 4A  ..LW&...W*7q..zJ
0010: 1D 99 75 85 24 90 28 19   E4 B3 58 31 6E 02 B8 4A  ..u.$.(...X1n..J
CONNECTION KEYGEN:
Client Nonce:
0000: 5C 05 06 08 F6 7C 3F 5C   73 57 F0 E4 D0 A8 90 11  \.....?\sW......
0010: 3C D1 AB 9A 69 B6 4D A0   F3 13 6C 27 F5 09 80 9B  <...i.M...l'....
Server Nonce:
0000: E7 47 9B 66 69 81 2F 03   93 AE 49 BC 3C A7 97 6C  .G.fi./...I.<..l
0010: 3D D2 2E 08 5A C6 74 65   AB 97 87 DE 5F 2C E3 E1  =...Z.te...._,..
Master Secret:
0000: 99 E8 51 8A 8D A5 56 56   09 42 31 3B EA A6 25 B0  ..Q...VV.B1;..%.
0010: 69 73 EB 33 56 64 57 D1   10 86 55 1C 51 86 B2 23  is.3VdW...U.Q..#
0020: 89 51 FF 42 41 BB D5 50   FD BC EF 9B E0 10 38 3F  .Q.BA..P......8?
... no MAC keys used for this cipher
Client write key:
0000: 4C 86 23 06 D6 FA 06 BD   3C EE A2 CE 28 1F 77 9A  L.#.....<...(.w.
Server write key:
0000: 1D 93 C4 5B 2A 6D 74 F8   1C 51 23 7E 5C BA DA A9  ...[*mt..Q#.\...
Client write IV:
0000: DF 88 94 CB                                        ....
Server write IV:
0000: 5C 43 CA 31                                        \C.1
main, WRITE: TLSv1.2 Change Cipher Spec, length = 1
*** Finished
verify_data:  { 7, 235, 79, 105, 125, 222, 241, 252, 104, 122, 143, 122 }
***
main, WRITE: TLSv1.2 Handshake, length = 40
main, READ: TLSv1.2 Change Cipher Spec, length = 1
main, READ: TLSv1.2 Handshake, length = 40
*** Finished
verify_data:  { 177, 236, 151, 88, 195, 59, 82, 200, 25, 135, 145, 190 }
***
%% Cached client session: [Session-1, TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256]
main, WRITE: TLSv1.2 Application Data, length = 178
main, READ: TLSv1.2 Application Data, length = 540
main, called close()
main, called closeInternal(true)
main, SEND TLSv1.2 ALERT:  warning, description = close_notify
main, WRITE: TLSv1.2 Alert, length = 26
main, called closeSocket(true)
Allow unsafe renegotiation: false
Allow legacy hello messages: true
Is initial handshake: true
Is secure renegotiation: false
main, setSoTimeout(0) called
%% No cached client session
*** ClientHello, TLSv1.2
RandomCookie:  GMT: 1543833097 bytes = { 240, 7, 191, 159, 152, 93, 95, 120, 98, 108, 183, 39, 146, 177, 15, 17, 250, 215, 164, 123, 155, 232, 211, 112, 149, 107, 76, 139 }
Session ID:  {}
Cipher Suites: [TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256, TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256, TLS_RSA_WITH_AES_128_CBC_SHA256, TLS_ECDH_ECDSA_WITH_AES_128_CBC_SHA256, TLS_ECDH_RSA_WITH_AES_128_CBC_SHA256, TLS_DHE_RSA_WITH_AES_128_CBC_SHA256, TLS_DHE_DSS_WITH_AES_128_CBC_SHA256, TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA, TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA, TLS_RSA_WITH_AES_128_CBC_SHA, TLS_ECDH_ECDSA_WITH_AES_128_CBC_SHA, TLS_ECDH_RSA_WITH_AES_128_CBC_SHA, TLS_DHE_RSA_WITH_AES_128_CBC_SHA, TLS_DHE_DSS_WITH_AES_128_CBC_SHA, TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256, TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256, TLS_RSA_WITH_AES_128_GCM_SHA256, TLS_ECDH_ECDSA_WITH_AES_128_GCM_SHA256, TLS_ECDH_RSA_WITH_AES_128_GCM_SHA256, TLS_DHE_RSA_WITH_AES_128_GCM_SHA256, TLS_DHE_DSS_WITH_AES_128_GCM_SHA256, TLS_ECDHE_ECDSA_WITH_3DES_EDE_CBC_SHA, TLS_ECDHE_RSA_WITH_3DES_EDE_CBC_SHA, SSL_RSA_WITH_3DES_EDE_CBC_SHA, TLS_ECDH_ECDSA_WITH_3DES_EDE_CBC_SHA, TLS_ECDH_RSA_WITH_3DES_EDE_CBC_SHA, SSL_DHE_RSA_WITH_3DES_EDE_CBC_SHA, SSL_DHE_DSS_WITH_3DES_EDE_CBC_SHA, TLS_EMPTY_RENEGOTIATION_INFO_SCSV]
Compression Methods:  { 0 }
Extension elliptic_curves, curve names: {secp256r1, secp384r1, secp521r1, sect283k1, sect283r1, sect409k1, sect409r1, sect571k1, sect571r1, secp256k1}
Extension ec_point_formats, formats: [uncompressed]
Extension signature_algorithms, signature_algorithms: SHA512withECDSA, SHA512withRSA, SHA384withECDSA, SHA384withRSA, SHA256withECDSA, SHA256withRSA, SHA256withDSA, SHA224withECDSA, SHA224withRSA, SHA224withDSA, SHA1withECDSA, SHA1withRSA, SHA1withDSA
Extension server_name, server_name: [type=host_name (0), value=www.alertlogic.com]
***
main, WRITE: TLSv1.2 Handshake, length = 194
main, WRITE: SSLv2 client hello message, length = 140
main, READ: TLSv1.2 Alert, length = 2
main, RECV TLSv1.2 ALERT:  fatal, handshake_failure
main, called closeSocket()
main, handling exception: javax.net.ssl.SSLHandshakeException: Received fatal alert: handshake_failure

So basically handshake starts normally using TLSv1.2, but then abruptly fails with no explanation.

One of the following prevents the snippet from failing:

1. Replacing url with a non-AWS endpoint.
2. Removing SSLv2Hello from the list of supported protocols.
3. Commenting out the System.setProperty("https.protocols", ...) function altogether.

Can anyone explain why presence of SSLv2Hello breaks the handshake, why is it AWS-specific, and is there a way to solve this issue on our side without compromising our security?