DeepSec 2015 Talk: illusoryTLS – Nobody But Us. Impersonate,Tamper and Exploit (secYOUre)

Sanna/ September 11, 2015/ Conference, Internet, Security

Transport Layer Security is a cornerstone of modern infrastructure. The „Cloud“ is full of it (at least it should be). For most people it is the magic bullet to solve security problems. Well, it is helpful, but only until you try to dive into the implementation on servers, clients, certificate vendors, or Certificate Authorities. Alfonso De Gregorio has done this. He will present his findings at DeepSec 2015 in his presentation aptly titled „illusoryTLS: Nobody But Us. Impersonate,Tamper and Exploit“. Learn how to embed an elliptic-curve asymmetric backdoor into a RSA modulus using Elligator. Find out how the entire TLS security may turn to be fictional, if a single CA certificate with a secretly embedded backdoor enters the certificate store of relying parties. Discover how some entities might have practically explored cryptographic backdoors for intelligence purposes regardless of the policy framework.

Still relying on TLS? Read on! Alfonso explains what you can expect from his presentation. It’s a long read, but it is a fine example of information security research.

Today’s Web PKI is fragile. We are, as a security community, witnessing with increasing frequency incidents, vulnerabilities, dramas, and failures of the infrastructure we daily entrust our business upon. There are numerous incidents involving TLS:

All these incidents, malicious or otherwise, allowed the impersonation of a number of high profile websites and granted the ability to spy on a sizable number of unsuspecting site users to the impersonating entities.

This is already unfortunate. If “No silent failure” is the pinnacle goal of security engineering [DG2], undetected impersonation is no measure of success in our engineering effort. As if that were not enough cause for concern, let’s discuss building cryptographic backdoors.

This is a timely topic often debated as matter for a government to legislate on. This work approaches it as a space that some entities might have practically explored regardless of the policy framework. [BULLRUN] If somebody in the belief, however questionable, that a “technically secure backdoor with a golden key” is possible had built one, would we be able to notice if our communications were being exploited?

The common view is that backdoors are symmetric in nature and require the presence of malicious logic in the target system code base (i.e., everyone with knowledge about the internals of the backdoor can exploit it, and code review can spot their presence). This research challenges this view. Backdoors can be asymmetric (i.e., the complete code for the backdoored system does not enable anyone except the designer to exploit the backdoor) and be planted in data. Or: to paraphrase a popular quote on homoiconicity of some programming languages: backdoor is data, data is backdoor.

To illustrate the security implications of this family of malicious security artifacts this work

  • Provides a working implementation of a backdoor embedded into the RSA modulus of a Certification Authority public-key certificate and the code for a minimalistic client and server communicating over a TLS channel;
  • Shows how this backdoor can completely pervert the security guarantees provided by the TLS protocol;
  • Argues that, from a network security perspective, the architecture of illusoryTLS resembles the standard architecture of web browsers and the associated certificate stores, communicating with web servers over TLS channels; and
  • Points out that even the presence of a single CA certificate with a secretly embedded backdoor in the certificate store would render the entire TLS security fictional. In fact, the current practice of universal implicit cross-certification makes the whole PKI as weak as its weakest link [PG, AA14, Gu11].

Hence, as long as the implementations of RSA – or, more generally, algorithms vulnerable to this class of attacks – used by trusted entities (e.g., CAs) cannot be audited by relying parties, and whenever the backdoor designer is a threat to the target users, the assurance provided by illusoryTLS (i.e., none whatsoever) is not any different from the assurance provided by systems relying upon TLS for origin authentication, confidentiality, and message integrity guarantees.

illusoryTLS

illusoryTLS is an instance of the Young and Yung elliptic curve asymmetric backdoor in RSA key generation. 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).

The design choices for this backdoor reflect the following threat model. The backdoor designer can

  • “insert vulnerabilities into commercial encryption systems, IT systems, networks and endpoint communications devices used by targets”,
  • “influence policies, standards and specifications for commercial public key technologies” [BULLRUN],
  • interfere with the supply-chain [EFF],
  • disregard everything about policy [RJA],
  • or she is simply in the position to build the security module used by the Certification Authority for generating the key material.

illusoryTLS consists of three modules:

  1. a HTTPS client,
  2. a TLSserver,
  3. a certificate store.

The code is part of network-simple-tls – an Haskell library for simple network sockets usage patterns using TLS security – and is used as-is, without any modification [NST].

For the sake of simplicity, and without loss of generality, the server implements an Echo service over TLS. The client sends a basic HTTP command over a TLS channel an awaits the server response.

From a network security perspective, the architecture of illusoryTLS is similar to the architecture of standard Web technology, where browsers – or other HTTP clients – and servers rely on database of public-key certificates (i.e., certificate stores) as trust-anchors in the validation of the certification paths.

Where is the backdoor?

There is one backdoor in illusoryTLS and it is highly robust against reverse-engineering. It is hidden in the public-key certificate of the CA the communicating entities rely upon to mutually authenticate (file path: env/certificatestore/cacert.pem).

In particular, the upper order bits of the RSA modulus encode the asymmetric encryption of a seed generated at random. The same seed was used to generate one of the RSA primes of the CA public-key modulus. Hence, the RSA modulus is at the same time a RSA public key and an asymmetric ciphertext that gives to the backdoor designer, and only to the designer, the ability to factor with ease the said modulus.

No backdoor was slipped into the cryptographic credentials issued to the communicating endpoints.

Related Work

The backdoor hidden in illusoryTLS implements a security notion that is twenty years old. Adam Young and Moti Yung introduced the notion of secretly embedded trapdoor with universal protection (SETUP) at Crypto ’96 [YY96]. The backdoor hidden in illusoryTLS implements this security notion. More specifically, it is an instance of the Young and Yung elliptic curve asymmetric backdoor in RSA key generation [YY]. The work by Adam Young and Moti Yung expands on the research they published in the proceedings of Selected Areas in Cryptography 2005 [YY05]. The same authors present a working implementation of their attack at the Cryptovirology web site.

Security Properties

illusoryTLS has some noteworthy properties.

NOBUS (Nobody But Us): [A14, Go14] The exploitation requires access to resources not embedded in the backdoor itself. In this case the secret resource is an elliptic-curve private key. Hence, the vulnerability can be exploited by the backdoor designer and by whoever gains access to the backdoor elliptic-curve private-key or to the associated key-recovery system. Hence, it is opportune to ask ourself: Is it possible to forbid an enemy intelligence organization from gaining access to a private key?
Those of us who believe that this is possible should be inclined to regard secure backdoors as also technical possibility. And those of us who believe that all measures to prevent disclosure of the private-key will be circumvented should be inclined to regard backdoors as inherently insecure.

Indistinguishability: As long as a computational hardness assumption called Elliptic-Curve Decision Diffie-Hellman (ECDDH) holds, the backdoored key pairs appear to all probabilistic polynomial time algorithms like genuine RSA key pairs. Therefore black-box access to the key-generator does not allow detection.

Forward Secrecy: If a reverse-engineer breaches the key-generator, then the previously stolen information remains confidential (secure against reverse-engineering).

Reusability: The backdoor can be used multiple times and against multiple targets.

The Impact and the Implications

The backdoor designer can use the private-key recovered by factoring the CA public modulus to break the TLS security guarantees at will, exposing the relying parties to a variety of attacks. They range  from impersonation (i.e., authentication failure), to message tampering (i.e., integrity erosion), to active eavesdropping of  encrypted communications (i.e., confidentiality loss), whenever the attacker mounts a MITM attack.

In order to exploit the backdoor, the designer needs to retain control over the key-generation of the target RSA modulus. However, s/he does not need to have access to any private key used by system actors, namely the Certification Authority and the communicating endpoints. Hence, the attacker does not need to purloin code or data from the work environment (i.e., the attack works without any need to tamper with the communicating endpoints).

In the Web 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.

To see why this is the case, it is necessary to look at how cross-certification and trust relationships among CAs are managed in theory and in practice.

„Cross certification enables entities in one public key infrastructure (PKI) to trust entities in another PKI. This mutual trust relationship [should be] typically supported by a cross-certification agreement between the certification authorities (CAs) in each PKI. The agreement establishes the responsibilities and liability of each party.“ [MS]

„[An explicit] mutual trust relationship between two CAs requires that each CA issue a certificate to the other to establish the relationship in both directions. The path of trust is not [hierarchical] (neither of the governing CAs is subordinate to the other) although the separate PKIs may be certificate hierarchies. After two CAs have established and specified the terms of trust and issued certificates to each other, entities within the separate PKIs can interact subject to the policies specified in the certificates.“ [MS]

But this is just in theory.

In practice, „most current PKI software employs a form of implicit cross-certification in which all root CAs are equally trusted, which is equivalent to unbounded cross-certification among all CAs. This means that, for example, any certificate can be trivially replaced by a masquerader’s certificate from another CA, since both CAs are equally trusted… With the implicit universal cross-certification that exists in this environment, the security of any certificate is reduced to that of the least trustworthy CA, who can issue a bogus certificate to usurp the legitimate one, at the same level of trust.“ [PG] The bogus certificates issued to Egypt-based MCS holdings and installed in a man-in-the-middle proxy [MCS] or the Superfish MitM adware [SF] are just the most recent examples of exploitation for this obvious vulnerability.

That is to say that universal implicit cross-certification, or the lack of constraints on the signer’s authority, is to security, or the absence of unmitigatable surprises [DG2], what ethylene is to fruit rotting: it makes the whole PKI as weak as its weakest link. And a CA certificate with a secretly embedded backdoor with the promise of exclusive exploitation may attract multiple attackers. With multiple attackers going after a technical opportunity, the Nobody But Us paradigm would quickly turn into an Everybody Else But Me concern for those left behind. The race to exploitation would self-reinforce, leading to a me-too effect. A scenario that would negate any meaningful security whatsoever.

Therefore, when dealing with this class of attacks in the context of X.509 Web 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.

At this time, Mac OS X Yosemite has 211 CA certificates installed. [OSX] A similar number of certificates is present in the Firefox, Google Chrome, and Microsoft Windows certificate stores. Have we sufficient assurance about the hundreds CA certificates we daily entrust our business upon?

The threats posed by a malicious implementer are not convincingly mitigated by current IT product security certification. The CA/Browser Forum requires publicly trusted certificates to be issued in compliance with the European Standard EN 319 411-3. According to the standard, the CA key generation shall be carried out within a device that meets the requirements identified by some approved protection profiles. The CEN Workshop Agreement 14167 Part 2, 3, and 4 are three of those protection profiles. The assurance level for these protection profiles is EAL4 augmented. The augmentation results from product adherence to three additional requirements ADV_IMP.2, AVA_CCA.1, and AVA_VLA.4. These are focused on assessing the presence of vulnerabilities in the Target of Evaluation (TOE) and on guaranteeing that the implementation representation is an accurate and complete instantiation of the TOE security functional (TSF) requirements. Special emphasis is placed on identifying covert channels and on estimating their capacity – which is relevant, because SETUP attacks makes use of the key-generation as a covert channel for itself. However, the certification process requires the developer the performance of the vulnerability assessment and documentation tasks. Of course, this conflicts with our threat model. The evaluator is left with the documentation and the implementation representation provided in fulfillment of the certification. Arguably, at the required Evaluation Assurance Level the assessment may fail to rule out the presence of backdoors in the key generation. Formal methods are in fact required only at the two highest levels (EAL6 and EAL7). And the level of detail of the implementation representation may render backdoor detection unlikely (e.g., HDL at design time, netlist at fabrication time as candidate representations).

Hence, the key takeaway is the following: as long as the implementations of RSA – or, more generally, algorithms vulnerable to this class of attacks – used by trusted entities (e.g., Certification Authorities) cannot be audited by relying parties (e.g., X.509 end-entities), any trust-anchor for the same trusted entities (e.g., root certificate) is to be regarded as a potential backdoor.

That is to say that as long as the implementation of algorithms adopted by CAs and vulnerable to this class of backdoors cannot be audited by relying parties, the assurance provided by illusoryTLS (i.e., none whatsoever) is not any different from the assurance provided by systems relying upon TLS and RSA certificates for origin authentication, confidentiality, and message integrity guarantees.

A number of mitigation exist, from key pinning (if used properly) [HPKP] to Certificate Transparency, to DANE, to Tack, and to proper explicit cross-certification. But none of them is widely deployed, yet.

Backdoor Embedding Algorithm

The subtleness of a backdoor planted in a cryptographic credential resides in the absence of malicious logic in the systems whose security it erodes. This is the reason why there is nothing anything amiss in the illusoryTLS code base. Admittedly funnier, though, is the backdoor embedding algorithm.

The backdoor embedding algorithm used for illusoryTLS is as described in Chapter 10 of [YY]. The rest of this section will introduce a novel way to embed an elliptic curve asymmetric backdoor into a RSA modulus.

Few weeks after the submission of illusoryTLS to the Underhanded Crypto Contest [UCC], Ryan Castellucci published their attack variant on GitHub [RC]. The idea is to

  • embed a Curve25519 public-key into the key-generator,
  • generate an ephemeral Curve25519 key at random,
  • compute a shared secret using Elliptic Curve Diffie-Hellmann,
  • use the shared secret to seed a cryptographically secure,
  • pseudo-random number generator (CSPRNG) based on AES run in CTR mode,
  • generate a normal RSA key using the seeded CSPRNG,
  • replace 32-bytes of the generated modulus with the ephemeral Curve25519 public-key,
  • use the original prime factors to compute two new primes leading to a new modulus embedding the ephemeral public-key,
  • output the RSA key.

To recover the target private key the attacker

  • extracts the ephemeral Curve25519 public-key from the target modulus,
  • computes the shared secret via Elliptic Curve Diffie-Hellmann and using the private-key associated to the public-key embedded in the key-generator,
  • uses the shared secret to seed the cryptographically secure pseudo-random number generator (CSPRNG) based on AES run in CTR mode,
  • generates a normal RSA key using the seeded CSPRNG,
  • replaces 32-bytes of the generated modulus with the ephemeral Curve25519 public-key,
  • uses the original prime factors to compute two new primes leading to the target modulus embedding the ephemeral public-key,
  • output the recovered RSA key.

Although the idea is nice, the key pairs generated using this algorithm fall short in terms of indistinguishability. In fact it is easy to tell backdoored certificates apart from genuine RSA certificate using only black-box access.

The attack embeds a public-key into an RSA modulus. Elliptic curve public-keys are points on the curve. And elliptic-curve points are easily distinguished from uniform random strings. Hence, a security evaluator could check if the coordinates encoded using the candidate 32-byte substrings of the modulus satisfy the elliptic curve equation. Can the backdoor be repaired? How?

If the backdoor designer could make the elliptic curve points indistinguishable from random strings, then the backdoor indistinguishability would be retained. Designed by Daniel J. Bernstein et al. with the goal to make anti-censorship protocols undetectable, Elligator [E] provides an encoding for points on a single curve as strings indistinguishable from uniform random strings.

All cyber security technology is inherently dual use. This long-held and well-sustained belief [DG] is corroborated by Elligator. Undetectability of curve points, just like any and all cyber security tools, can be used for good or ill; for censorship-circumvention or for surveillance.

Yet, it is possible to positively contribute to the discussion and practice of information security by walking the fine line between offence and defence. In this spirit, what follows are:

  • a backdoor embedding algorithm based on Elligator, and
  • the associated key-recovery algorithm.

This backdoor embedding algorithm makes sure that the backdoored RSA key-pairs are indistinguishable from genuine RSA key-pairs.

The key-generation proceeds as follows:

  • embed a Curve25519 public-key into the key-generator,
  • generate an ephemeral Curve25519 key at random and the associated uniform representative string,
  • compute a shared secret using Elliptic Curve Diffie-Hellmann,
  • use the shared secret to seed a cryptographically secure pseudo-random number generator (CSPRNG) based on AES run in CTR mode,
  • generate a normal RSA key using the seeded CSPRNG,
  • replace 32-bytes of the generated modulus with the representative string associated to the ephemeral Curve25519 public-key,
  • use the original prime factors to compute two new primes leading to a new modulus embedding the uniform representative string,
  • output the RSA key.

To recover the target private key the attacker:

  • extracts the representative string from the target modulus,
  • maps the representative string to the candidate ephemeral Curve25519 public-key,
  • computes the shared secret via Elliptic Curve Diffie-Hellmann and using the private-key associated to the public-key embedded in the key-generator,
  • uses the shared secret to seed the cryptographically secure pseudo-random number generator (CSPRNG) based on AES run in CTR mode,
  • generates a normal RSA key using the seeded CSPRNG,
  • replaces 32-bytes of the generated modulus with the representative string found in the target modulus,
  • uses the original prime factors to compute two new primes leading to the target modulus embedding the uniform representative string,
  • output the recovered RSA key.

References

[A14] Dave Aitel, ‘Nobody But Us’, Daily Dave mailing list

[AA14] Axel Arnback, Hadi Asghari, Michel Van Eeten, Niko Van Eljk, Security Collapse in the HTTPS Market

[BULLRUN] COMPUTER NETWORK OPERATIONS. SIGINT ENABLING

[DG] Geer Jr. D. E., (2014); Cybersecurity as Realpolitik.

[DG2] Geer Jr. D. E., (2014); Security of Things, Cambridge

[E] Bernstein D. J., Hamburg M., Krasnova A., and Lange T. (2013); Elligator

[EFF] 20150117-Spiegel-Supply-chain Interdiction. Stealthy Techniques Can Crack Some of SIGINT’s Hardest Targets

[HPKP] Evans, C. et al (2015); Public Key Pinning Extension for HTTP, RFC 7469, IETF

[Go14] Jack Goldsmith, ‘Cyber Paradox: Every Offensive Weapon is a (Potential) Chink in Our Defense — and Vice Versa’

[Gu11] Peter Gutmann, Diginotar broken arrow as a tour-de-force of PKI fail, Cryptography Randombit mailing list

[MC] Adam L. Young and Moti M. Yung, ‘Malicious Cryptography, Exposing Cryptovirology’, 2004, ISBN: 0-7645-4975-8, J. Wiley

[MCS] Langley A. (2015); Maintaining digital certificate security

[MS] Microsoft, Cross Certification

[NST] Renzo Carbonara, network-simple-tls, Haskell library for simple network sockets usage patterns using TLS security

[OSX] List of available trusted root certificates in OS X Yosemite

[PG] Gutmann, P. (2002); PKI: It’s Not Dead, Just Resting. Computer (35,8), IEEE, 0018-9162

[RC] Castellucci, R. (2015); rsabd.py

[SF] Bonneau J. and Eckersley P. and Hoffman-Andrews J. (2015); Lenovo Is Breaking HTTPS Security on its Recent Laptops

[UCC] Underhanded Crypto Contest.

[YY] Adam L. Young and Moti M. Yung, ‘An Elliptic Curve Asymmetric Backdoor in OpenSSL RSA Key Generation’, Advances in Cryptovirology, to appear,

[YY05] Adam L. Young and Moti M. Yung, ‘A Space Efficient Backdoor in RSA and its Applications’. In Bart Preneel and Stafford E. Tavares, editors, Selected Areas in Cryptography — ’05, pp 128-143, Spring, 2005, Lecture Notes in Computer Science No. 3897.

[YY96] Adam L. Young and Moti M. Yung, ‘The Dark Side of Black-Box Cryptography, or: Should we trust Capstone?’. In Advances in Cryptology—Crypto ’96, N. Koblitz (Ed.),  LNCS 1109, pp. 89-103, 1996.

 

 

Share this Post

8 Comments

Comments are closed.