Comment 70 for bug 305264

I ran into the same problem (the update to libgnutls13 2.0.4-1ubuntu2.5 broke LDAP auth, due to the certificate chain no longer validating). The quick fix was to set TLS_REQCERT to allow in /etc/ldap/ldap.conf, but that is just a temporary workaround.

Indeed, using gnutls-cli to connect to server:636 fails verification with this version, whereas after rolling back to -ubuntu2.3 it succeeds. 'openssl s_client' is still happy. I discovered that this is because both my CA cert and the server cert were using md5/rsa, which are no longer supported by gnutls. Note the changelog entry " - Deprecate X.509 validation chains using MD5 and MD2 signatures"; apparently by "deprecate" they mean "no longer support at all".

Apparently gnutls doesn't mind the self-signed CA cert being MD5, but it's not happy with the server cert:
andrew@shiny:~$ echo|gnutls-cli --print-cert --x509cafile isc-ca.crt -p 636 ldap.server | certtool -e
Certificate[0]: C=US,ST=Texas,L=College Station,O=TAMU,OU=VPR,CN=ldap.server,<email address hidden>
 Issued by: C=US,ST=Texas,L=College Station,O=TAMU,OU=VPR,CN=ISC CA,<email address hidden>
 Verifying against certificate[1].
 Verification output: Not verified, Insecure algorithm.

Certificate[1]: C=US,ST=Texas,L=College Station,O=TAMU,OU=VPR,CN=ISC CA,<email address hidden>
 Issued by: C=US,ST=Texas,L=College Station,O=TAMU,OU=VPR,CN=ISC CA,<email address hidden>
 Verification output: Verified.
[names/emails sanitized somewhat]

After generating a new server cert using sha1/rsa and plugging it into slapd (but still using the same md5/rsa CA cert), gnutls is now happy, and in turn, so is pam_ldap. I suppose the better solution would be to create a new sha1 CA cert also, but that would require copying it to all the clients, which is a lot more work.

Andy, I notice you have default_md=md5 in your openssl.cnf. You should change this to sha1 or something else not considered broken, and generate a new server cert, and that should solve your problem.

In summary, the recent gnutls update broke MD5 certs, but this was intentional. It would've been nice to announce this more loudly though. (To me, "deprecate" means "discourage future use", not "remove support".)