• I reproduced the problem and also observed that the same issue existed for several
  others ciphers (like DHE-RSA-AES128-SHA) although it is said to be surported

{{{
ldapsearch ... -b "cn=encryption,cn=config" "nsSSLSupportedCiphers"
...
nsSSLSupportedCiphers: TLS::tls_dhe_rsa_aes_128_sha::AES::SHA1::128
}}}

• On the server side, the connection is closed with

{{{
[21/Aug/2013:19:51:34 +0200] conn=16 fd=64 slot=64 SSL connection from ::1 to ::1
[21/Aug/2013:19:51:34 +0200] conn=16 op=-1 fd=64 closed - Cannot communicate securely with peer: no common encryption algorithm(s).

}}}

Here is the current status

• DHE ciphers are said to be supported. Directory Server gets the list of the supported ciphers by calling SSL_GetCipherSuiteInfo from underlying NSS layer.

• Current NSS layer does not implement DHE server side ciphers. This functionality was logged in https://bugzilla.mozilla.org/show_bug.cgi?id=102794 but is not yet implemented.
  This is described in ssl3conn.c

{{{

if NSS_SERVER_DHE_IMPLEMENTED

    /* XXX NSS does not yet implement the server side of _DHE_
     * cipher suites.  Correcting the computation for svrAuth,
     * as the case below does, causes NSS SSL servers to begin to
     * negotiate cipher suites they do not implement.  So, until
     * server side _DHE_ is implemented, keep this disabled.
     */
    case kea_dhe_rsa:

endif

}}}

• Note for debugging purpose, during the handshake the clientHello triggers an abort because requesting a not yet implemented cipher.

{{{
#3 0x0000003c5500f4c6 in SSL3_SendAlert (ss=ss@entry=0xfbcef0, level=<optimized out>, desc=desc@entry=handshake_failure)
at ssl3con.c:2847
#4 0x0000003c55014671 in ssl3_HandleClientHello (length=0, b=0xddb0b5 "", ss=0xfbcef0) at ssl3con.c:7319
#5 ssl3_HandleHandshakeMessage (ss=ss@entry=0xfbcef0, b=<optimized out>, length=<optimized out>) at ssl3con.c:9443
#6 0x0000003c55017509 in ssl3_HandleHandshake (origBuf=0xfbd288, ss=0xfbcef0) at ssl3con.c:9592
#7 ssl3_HandleRecord (ss=ss@entry=0xfbcef0, cText=cText@entry=0x7f17652db890, databuf=databuf@entry=0xfbd288) at ssl3con.c:10230
#8 0x0000003c55018305 in ssl3_GatherCompleteHandshake (ss=0xfbcef0, flags=0) at ssl3gthr.c:361
#9 0x0000003c55019905 in ssl_GatherRecord1stHandshake (ss=0xfbcef0) at sslcon.c:1227
#10 0x0000003c55020985 in ssl_Do1stHandshake (ss=ss@entry=0xfbcef0) at sslsecur.c:120
#11 0x0000003c55021e6f in ssl_SecureRecv (ss=0xfbcef0, buf=0xfb4590 "\370\t;\356;", len=512, flags=0) at sslsecur.c:1134
#12 0x0000003c55025e76 in ssl_Recv (fd=<optimized out>, buf=0xfb4590, len=512, flags=0, timeout=0) at sslsock.c:2071
#13 0x0000000000415a97 in connection_read_ldap_data (conn=0x7f17652e2410, err=0x7f17652dba18)
at ldap/servers/slapd/connection.c:1903
#14 0x0000000000415d16 in connection_read_operation (conn=0x7f17652e2410, op=0xfab670, tag=0x7f17652dba88,
remaining_data=0x7f17652dba84) at ldap/servers/slapd/connection.c:1973
#15 0x0000000000416a56 in connection_threadmain () at ldap/servers/slapd/connection.c:2380
#16 0x0000003c53028b46 in ?? () from /lib64/libnspr4.so
#17 0x0000003bee407d14 in start_thread (arg=0x7f17652dc700) at pthread_create.c:309
#18 0x0000003bee0f168d in clone () from /lib64/libc.so.6

}}}

Here are the next step

• Determine when https://bugzilla.mozilla.org/show_bug.cgi?id=102794 will be available
• Possibly open a new bug about SSL_GetCipherSuiteInfo that reported supported ciphers that are actually not implemented

On the latest version on Fedoras:
{{{
389 Directory Server 1.3.3.8 (February 5, 2015)
389 Directory Server 1.3.2.26 (February 5, 2015)
}}}
the following ciphers are supported.
{{{
ldapsearch ... -D 'cn=directory manager' -w pw -b "cn=encryption,cn=config" -s base nssslenabledciphers
dn: cn=encryption,cn=config
nssslenabledciphers: TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256::AES-GCM::AEAD::1 28
nssslenabledciphers: TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256::AES-GCM::AEAD::128
nssslenabledciphers: TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA::AES::SHA1::256
nssslenabledciphers: TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA::AES::SHA1::128
nssslenabledciphers: TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA::AES::SHA1::128
nssslenabledciphers: TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256::AES::SHA256::128
nssslenabledciphers: TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256::AES::SHA256::128
nssslenabledciphers: TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA::AES::SHA1::256
nssslenabledciphers: TLS_DHE_RSA_WITH_AES_128_GCM_SHA256::AES-GCM::AEAD::128
nssslenabledciphers: TLS_DHE_RSA_WITH_AES_128_CBC_SHA::AES::SHA1::128
nssslenabledciphers: TLS_DHE_DSS_WITH_AES_128_CBC_SHA::AES::SHA1::128
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
nssslenabledciphers: TLS_DHE_RSA_WITH_AES_128_CBC_SHA256::AES::SHA256::128
nssslenabledciphers: TLS_DHE_RSA_WITH_CAMELLIA_128_CBC_SHA::CAMELLIA::SHA1::12 8
nssslenabledciphers: TLS_DHE_DSS_WITH_CAMELLIA_128_CBC_SHA::CAMELLIA::SHA1::12 8
nssslenabledciphers: TLS_DHE_RSA_WITH_AES_256_CBC_SHA::AES::SHA1::256
nssslenabledciphers: TLS_DHE_DSS_WITH_AES_256_CBC_SHA::AES::SHA1::256
nssslenabledciphers: TLS_DHE_RSA_WITH_AES_256_CBC_SHA256::AES::SHA256::256
nssslenabledciphers: TLS_DHE_RSA_WITH_CAMELLIA_256_CBC_SHA::CAMELLIA::SHA1::25 6
nssslenabledciphers: TLS_DHE_DSS_WITH_CAMELLIA_256_CBC_SHA::CAMELLIA::SHA1::25 6
nssslenabledciphers: TLS_ECDH_ECDSA_WITH_AES_128_CBC_SHA::AES::SHA1::128
nssslenabledciphers: TLS_ECDH_RSA_WITH_AES_128_CBC_SHA::AES::SHA1::128
nssslenabledciphers: TLS_ECDH_ECDSA_WITH_AES_256_CBC_SHA::AES::SHA1::256
nssslenabledciphers: TLS_ECDH_RSA_WITH_AES_256_CBC_SHA::AES::SHA1::256
nssslenabledciphers: TLS_RSA_WITH_AES_128_GCM_SHA256::AES-GCM::AEAD::128
nssslenabledciphers: TLS_RSA_WITH_AES_128_CBC_SHA::AES::SHA1::128
nssslenabledciphers: TLS_RSA_WITH_AES_128_CBC_SHA256::AES::SHA256::128
nssslenabledciphers: TLS_RSA_WITH_CAMELLIA_128_CBC_SHA::CAMELLIA::SHA1::128
nssslenabledciphers: TLS_RSA_WITH_AES_256_CBC_SHA::AES::SHA1::256
nssslenabledciphers: TLS_RSA_WITH_AES_256_CBC_SHA256::AES::SHA256::256
nssslenabledciphers: TLS_RSA_WITH_CAMELLIA_256_CBC_SHA::CAMELLIA::SHA1::256
nssslenabledciphers: TLS_RSA_WITH_SEED_CBC_SHA::SEED::SHA1::128
}}}
Note: this is the NSS version on my F20.
nss-3.17.2-1.fc20.x86_64

As of 389-ds-base-1.2.11.15, it'll be released in a short time.

See also https://fedorahosted.org/389/ticket/47928

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/389ds/389-ds-base/issues/771

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.