openldap TLS failure -- ldap_start_tls: Connect error (-11)

Question

From what I can tell it's a certificate verification issue, but I have no idea why.

~ > ldapsearch -x -ZZ -LLL -H ldap://ldap.dark.kow.is -b dc=dark,dc=kow,dc=is
ldap_start_tls: Connect error (-11)

However, when I use gnutls-cli on the same host to connect, everything is completely fine. I am truly at a loss as to why this is happening. The CA-Certificate is available in the system store, other certificates signed with it are fine. The certificates/CA are not expired. The hostnames match in DNS, so it's not failing that validity.

Ubuntu 18.04.

gnutls-cli --starttls-proto=ldap --print-cert -p 389 ldap.dark.kow.is

Processed 134 CA certificate(s).
Resolving 'ldap.dark.kow.is:389'...
Connecting to '10.10.220.213:389'...
- Certificate type: X.509
- Got a certificate list of 2 certificates.
- Certificate[0] info:
 - subject `CN=ldap.dark.kow.is', issuer `CN=dark.kow.is CA', serial 0x637523035782280200a2dd2e262980d1, RSA key 4096 bits, signed using RSA-SHA256, activated `2018-01-13 20:22:12 UTC', expires `2028-01-11 20:22:12 UTC', pin-sha256="Xywzn8R32GsgoWQol5pKSJYrFVOrpXk1stF4kKPl1yY="
        Public Key ID:
                sha1:d7aa0336e36c3e63c8c0acb4d80dfa0541cadc0a
                sha256:5f2c339fc477d86b20a16428979a4a48962b1553aba57935b2d17890a3e5d726
        Public Key PIN:
                pin-sha256:Xywzn8R32GsgoWQol5pKSJYrFVOrpXk1stF4kKPl1yY=
        Public key's random art:
                +--[ RSA 4096]----+
                |  .              |
                |oo.              |
                |Eo..             |
                |. ..       .     |
                | +.     S . .    |
                | .=.  =  . .     |
                |o+.=.= +  .      |
                |+...+ B ..       |
                | ..  +.o..       |
                +-----------------+


-----BEGIN CERTIFICATE-----
OMITTED
-----END CERTIFICATE-----

- Certificate[1] info:
 - subject `CN=dark.kow.is CA', issuer `CN=dark.kow.is CA', serial 0x00d0d752ba5297a770, RSA key 2048 bits, signed using RSA-SHA256, activated `2016-12-24 17:49:30 UTC', expires `2026-12-22 17:49:30 UTC', pin-sha256="0Gze+gcPQQ0Dq4mT5pdt5H7z6HMM/NOeHc8pZ5z/BHg="

-----BEGIN CERTIFICATE-----
OMITTED
-----END CERTIFICATE-----

- Status: The certificate is trusted.
- Description: (TLS1.2)-(ECDHE-RSA-SECP256R1)-(AES-256-GCM)
- Session ID: BA:E5:46:52:6E:76:82:94:E7:AE:F2:5C:B5:74:95:54:7E:62:54:86:9F:23:D4:C3:D3:AF:C4:76:10:63:84:7A
- Ephemeral EC Diffie-Hellman parameters
 - Using curve: SECP256R1
 - Curve size: 256 bits
- Version: TLS1.2
- Key Exchange: ECDHE-RSA
- Server Signature: RSA-SHA256
- Cipher: AES-256-GCM
- MAC: AEAD
- Compression: NULL
- Options: extended master secret, safe renegotiation,
- Handshake was completed

- Simple Client Mode:

Answer 1

Okay, I finally figured this out. The solution lies in my /etc/ldap.conf

# Ubuntu has stuff built against GNUtls instead of openssl
# Get this from the gnutls-cli manpage under --priority
TLS_CIPHER_SUITE SECURE256

I was not specifying --priority SECURE256 when issuing the gnutls-cli commands, so it was using different algorithms. When including that:

~ > gnutls-cli --starttls-proto=ldap --priority SECURE256  -p 389 ldap.dark.kow.is
Processed 134 CA certificate(s).
Resolving 'ldap.dark.kow.is:389'...
Connecting to '10.10.220.213:389'...
- Certificate type: X.509
- Got a certificate list of 2 certificates.
- Certificate[0] info:
 - subject `CN=ldap.dark.kow.is', issuer `CN=dark.kow.is CA', serial 0x637523035782280200a2dd2e262980d1, RSA key 4096 bits, signed using RSA-SHA256, activated `2018-01-13 20:22:12 UTC', expires `2028-01-11 20:22:12 UTC', pin-sha256="Xywzn8R32GsgoWQol5pKSJYrFVOrpXk1stF4kKPl1yY="
        Public Key ID:
                sha1:d7aa0336e36c3e63c8c0acb4d80dfa0541cadc0a
                sha256:5f2c339fc477d86b20a16428979a4a48962b1553aba57935b2d17890a3e5d726
        Public Key PIN:
                pin-sha256:Xywzn8R32GsgoWQol5pKSJYrFVOrpXk1stF4kKPl1yY=
        Public key's random art:
                +--[ RSA 4096]----+
                |  .              |
                |oo.              |
                |Eo..             |
                |. ..       .     |
                | +.     S . .    |
                | .=.  =  . .     |
                |o+.=.= +  .      |
                |+...+ B ..       |
                | ..  +.o..       |
                +-----------------+

- Certificate[1] info:
 - subject `CN=dark.kow.is CA', issuer `CN=dark.kow.is CA', serial 0x00d0d752ba5297a770, RSA key 2048 bits, signed using RSA-SHA256, activated `2016-12-24 17:49:30 UTC', expires `2026-12-22 17:49:30 UTC', pin-sha256="0Gze+gcPQQ0Dq4mT5pdt5H7z6HMM/NOeHc8pZ5z/BHg="
- Status: The certificate is NOT trusted. The certificate chain uses insecure algorithm. 
*** PKI verification of server certificate failed...
*** Fatal error: Error in the certificate.
*** handshake has failed: Error in the certificate.

Now I have the same failure as the LDAP commands, and I have to disable that level of security in my ldap.conf to have it working again. Changing my certificates would work also, using an algorithm that falls within the SECURE256 category.