Having not made any other changes to the LDAP system they started digging. Luckily for them some Googling and some savvy admins managed to walk the cat back to NSS using a Fedora 18 bugzilla report.
The upstream Mozilla NSS disabled support for MD5 hash signed certificates in the 3.14 release, which was added to RHEL 6.4. From the upstream documentation the following workaround is noted:
sssd[be[LDAP]]: Could not start TLS encryption. TLS error-8016:The certificate was signed using a signature algorithm that is disabled because it is not secure.
The other solution would be to re-key the LDAP server which may potentially require more changes to the CA depending on how you originally built and signed your keys.
There are two ways to set the variable that have been reported to work. Option 1, export the variable at service startup with upstart via /etc/environment:
Support for MD5 may be manually enabled (but is discouraged) by setting the environment variable of "NSS_HASH_ALG_SUPPORT=+MD5" or by using the NSS_SetAlgorithmPolicy function.
Option 2, create (or add to) nss.sh in /etc/profile.d/ and export the variable there.
The folks who reported the problem to me are going with solution #2.
And so as not to take any credit for these, here's the link to the Fedora Bugzilla report that talks about the solution. The information from the Red Hat docs on the upstream release update can be found in the Technical Notes and the Release Notes. The upstream project had set a date on supporting MD5 hashes based on earlier issues discovered with the hash algorithm.
If you are having difficulty getting a working configuration, use your Red Hat support contract and call the experts.
Image courtesy of Vibeone.com.
UPDATE: Earlier versions of this article referred to a solution for systemd which is not the currently supported service management daemon for RHEL 6. The upstartd technique above will work for RHEL 6.