Cent OS genkey bad certificate request error -8016

This looks like it's a bug reported here in the RHEL/CentOS 6.4 crypto-utils. It's also been reported on the CentOS forums.

Description of problem: Since EL 6.4, a new version of NSS considers MD5 signatures as invalid. 1 keyutils generated ssl certificates with md5 signatures. Since EL 6.4 trying to generate a ssl self-signed certificate leads to segfault.

Possible workaround - from the bug report - generate the files manually

Manual creation works (creates an sha1 signed certificate):
openssl genrsa -out ca.key 2048
openssl req -new -x509 -days 1095 -key ca.key -out ca.crt  -subj "/CN=ca.puzzle.ch /O=Puzzle ITC/L=Bern/ST=Bern/C=CH"
openssl genrsa -out server.key 2048
openssl req -new -key server.key -out server.csr -subj "/CN=server.example.com/O=Puzzle ITC/L=Bern/ST=Bern/C=CH" 
openssl x509 -req -days 1095 -CA ca.crt -CAkey ca.key -set_serial 01 -in server.csr -out server.crt 
openssl x509 -in server.crt -text

Signature Algorithm: sha1WithRSAEncryption