OpenSSL connection: alert internal error

Question

I have 100 HTTPS services running on a single server using SNI. (Actually, I don't have access to them. It's an assignment. All I know are their domain names N.xxx.yy where N is in range from 00 to 99.) The goal of the assignment is to evaluate security of every single connection to each of these servers. So some of the servers contain expired certificates, certificates with wrong CN, etc.

My problem is that I cannot get past the handshake on some of the servers. I have written my own application in C++ using OpenSSL, but I've also tried it with openssl s_client. This is how I connect to the server:

openssl s_client -host N.xxx.yy -port 443 -verify 1 -servername N.xxx.yy -CAfile assignment-ca.pem

And this is what I get:

139625941858168:error:14094438:SSL routines:ssl3_read_bytes:tlsv1 alert internal error:s3_pkt.c:1493:SSL alert number 80
139625941858168:error:140790E5:SSL routines:ssl23_write:ssl handshake failure:s23_lib.c:177:

In Wireshark, I see that client sent ClientHello, server responded with ServerHello (choosing TLSv1.2 and ECDHE-RSA-AES256-GCM-SHA384) followed by Certificate and then it sent me Alert message containing Internal Error (80).

After trying different thing I have found out that if I run s_client with -tls1 or -tls1_1 I can successfully get past the handshake. -tls1_2 does not work. What is even stranger is that connection through Chrome/Firefox/any other browser succeeds even if TLSv1.2 is negotiated. From what I see, Chrome is sending a different cipher list than me or s_client but even after modifying the cipher list to match the one in Chrome (and making sure that server chooses ECDHE-RSA-AES128-GCM-SHA256), it does not work either. Chrome is sending these TLS extensions, which I don't but most of them seem empty:

Unknown 47802
renegotiation_info
Extended Master Secret
signed_certificate_timestamp
status_request
Application Layer Protocol Negotiation
channel_id
Unknown 6682

Can anybody explain me what is happening here? Unfortunately, I have no way to debug it on the server side so this is all I know.

UPDATE:

After playing around with forged ClientHello messages I managed to track it down to signature_algorithms extension. My app and s_client provide SHA384 + {RSA,DSA,ECDSA} but if I remove these and keep just SHA256 + {RSA,DSA,ECDSA}, as Chrome does, it works and I receive Server Key Exchange message successfully. Could it be that server somehow does not support it, but instead of providing meaningful error message, it just ends unexpectedly and gives me this internal error?

UPDATE 2:

I found answer to why it works with TLS versions prior to 1.2 in RFC5246. Question from the previous UPDATE still holds.

Note: this extension is not meaningful for TLS versions prior to 1.2.
   Clients MUST NOT offer it if they are offering prior versions.
   However, even if clients do offer it, the rules specified in [TLSEXT]
   require servers to ignore extensions they do not understand.

Answer 1

Since you wrote that -tls1_2 does not work I assume either you and/or the server uses an older openssl library. The current version while writing this is 1.1.0e

There were quite some fixes since 0.9.8, which could often be seen on older systems.

For Version 1.0.1 there was this fix, which sounds like your problem:

 `Some servers which support TLS 1.0 can choke if we initially indicate
 support for TLS 1.2 and later renegotiate using TLS 1.0 in the RSA
 encrypted premaster secret. As a workaround use the maximum permitted
 client version in client hello, this should keep such servers happy
 and still work with previous versions of OpenSSL.`

Maybe also notable:

Don't allow TLS 1.2 SHA-256 ciphersuites in TLS 1.0, 1.1 connections.

So I would suggest to update your openssl-Version and in case of the servers out of your control I would stick to the settings you already found.