java.security.cert.CertificateException: Certificates does not conform to algorithm constraints

Background

MD2 was widely recognized as insecure and thus disabled in Java in version JDK 6u17 (see release notes http://www.oracle.com/technetwork/java/javase/6u17-141447.html, "Disable MD2 in certificate chain validation"), as well as JDK 7, as per the configuration you pointed out in java.security.

Verisign was using a Class 3 root certificate with the md2WithRSAEncryption signature algorithm (serial 70:ba:e4:1d:10:d9:29:34:b6:38:ca:7b:03:cc:ba:bf), but deprecated it and replaced it with another certificate with the same key and name, but signed with algorithm sha1WithRSAEncryption. However, some servers are still sending the old MD2 signed certificate during the SSL handshake (ironically, I ran into this problem with a server run by Verisign!).

You can verify that this is the case by getting the certificate chain from the server and examining it:

openssl s_client -showcerts -connect <server>:<port>

Recent versions of the JDK (e.g. 6u21 and all released versions of 7) should resolve this issue by automatically removing certs with the same issuer and public key as a trusted anchor (in cacerts by default).

If you still have this issue with newer JDKs

Check if you have a custom trust manager implementing the older X509TrustManager interface. JDK 7+ is supposed to be compatible with this interface, however based on my investigation when the trust manager implements X509TrustManager rather than the newer X509ExtendedTrustManager (docs), the JDK uses its own wrapper (AbstractTrustManagerWrapper) and somehow bypasses the internal fix for this issue.

The solution is to:

1. use the default trust manager, or

2. modify your custom trust manager to extend X509ExtendedTrustManager directly (a simple change).

Eclipse failed to connect to SVN https repositories (should also apply to any app using SSL/TLS).

svn: E175002: Connection has been shutdown: javax.net.ssl.SSLHandshakeException: java.security.cert.CertificateException: Certificates does not conform to algorithm constraints

The issue was caused by latest Java 8 OpenJDK update that disabled MD5 related algorithms. As a workaround until new certificates are issued (if ever), change the following keys at java.security file

WARNING
Keep in mind that this could have security implications as disabled algorithms are considered weak. As an alternative, the workaround can be applied on a JVM basis by a command line option to use an external java.security file with this changes, e.g.:
java -Djava.security.properties=/etc/sysconfig/noMD5.java.security
For Eclipse, add a line on eclipse.ini below -vmargs
-Djava.security.properties=/etc/sysconfig/noMD5.java.security

original keys

jdk.certpath.disabledAlgorithms=MD2, MD5, RSA keySize < 1024
jdk.tls.disabledAlgorithms=SSLv3, RC4, MD5withRSA, DH keySize < 768

change to

jdk.certpath.disabledAlgorithms=MD2, RSA keySize < 1024
jdk.tls.disabledAlgorithms=SSLv3, RC4, DH keySize < 768

java.security file is located in linux 64 at /usr/lib64/jvm/java/jre/lib/security/java.security