illusoryTLS: Impersonate, Tamper, and Exploit

The entire X.509 PKI security architecture falls apart, if a single CA certificate with a secretly embedded backdoor enters the certificate store of relying parties. Have we sufficient assurance that this did not happen already? This talk explores this scenario from both an experimental and speculative point of view.

From the experimental standpoint, the talk reports on illusoryTLS, an entry to the first Underhanded Crypto Contest. illusoryTLS is an instance of the Young and Yung elliptic curve asymmetric backdoor in RSA key generation. It targets a Certification Authority public-key certificate imported in the certificate store of a pretty standard HTTPS client and TLS server. The security outcome is the worst possible outcome, because the backdoor completely perverts the security guarantees provided by the TLS protocol, allowing the attacker to impersonate the endpoints (i.e., authentication failure), tamper with their messages (i.e., integrity erosion), and actively eavesdrop their communications (i.e., confidentiality loss).

illusoryTLS has been shortlisted to the final rounds of the contest, which is still ongoing. Being the backdoored public-key indistinguishable (under the ECDDH assumption) to all probabilistic polynomial time algorithms from genuine public-keys, illusoryTLS is expected to withstand the review and scrutiny of contest judges.

In the Internet X.509 PKI the security impact of such backdoor would extend further; the presence of a single CA certificate with a secretly embedded backdoor in the certificate store renders the entire TLS security fictional. In fact, the current practice of universal implicit cross-certification makes the whole X.509 PKI as weak as its weakest link.

Therefore, when dealing with this class of attacks in the context of X.509 PKIs, it might be not sufficient to avoid outsourcing the key generation. It becomes essential also to have assurance about the security of each implementation of vulnerable key-generation algorithms employed by trusted credential issuers. Have we sufficient assurance about the tens or hundreds CA certificate we daily entrust our business upon?

Full source code and design of illusoryTLS will be made available at HITBSecConf 2015 Amsterdam.