C A ' FOSCARI UNIVERSITY OF VENICE A N D MASARYK UNIVERSITY Challenging RSA cryptosystem implementations D O C T O R A L THESIS Matúš Nemec Doctorate Coordinator Advisor (Masaryk University) Prof. Riccardo Focardi Prof. Vashek Matyáš Advisor (Ca' Foscari University) Consultant Prof. Riccardo Focardi Doc. Petr Svenda Cycle: 32 Matricola: 956333 SSD: INF/01 Informatica Semester: Fall 2019 UČO: 396066 Declaration Hereby I declare that this paper is my original authorial work, which I have worked out on my own. A l l sources, references, and literature used or excerpted during elaboration of this work are properly cited and listed in complete reference to the due source. Matúš Nemec Advisor (Ca' Foscari University of Venice): Prof. Riccardo Focardi Advisor (Masaryk University): Prof. Vashek Matyáš Consultant (Masaryk University): Doc. Petr Svenda i Acknowledgements I would like to thank Vashek Matyáš, Riccardo Focardi, Petr Švenda, and Marek Sýs for their guidance and advice. I am thankful to all my co-authors for their fantastic work, and to all the members of CRoCS and A C A D I A groups for creating a welcoming atmosphere. I much appreciate the help of Nicola Miotello and Ada Nazarejová with going through the red tape. Last but not least, this thesis would not be possible without the support of my family and friends. iii Abstract The aim of our research was to study security properties of realworld deployments of the RSA cryptosystem. First we analyze RSA key generation methods in cryptographic libraries. We show a practical application of biases in RSA keys for measuring popularity of cryptographic libraries and we develop a factorization method that breaks a proprietary key generation algorithm. Later we examine published implementation issues in the TLS protocol, such as RSA padding oracles, in the wider context of the Web ecosystem. The main conclusion of our previous research on RSA keys was that libraries leak information about their key generation algorithms through the public keys. The bias in the key is often sufficient to identify a library that likely generated the key. In this thesis, we further demonstrate a practical method for measuring representation of cryptographic libraries in large datasets of RSA public keys. We use statistical inference to approximate a share of libraries matching an observed distribution of RSA keys in an inspected dataset. Such estimate also allows us to deploy an improved key classification method that uses prior probabilities of libraries to more accurately determine the source of a key. Next we adapt a key factorization attack to keys generated by a widely deployed proprietary cryptographic library. Our previous research hinted at issues in the algorithm by showing an unusual bias in the keys. We reveal the algorithm without the access to the source code by analyzing algebraic properties of the keys. We develop a practical factorization attack that can compute private keys corresponding to the public keys used in electronic identification documents, Trusted Platform Modules, authentication tokens, and other domains that use secure chips with this RSA key generation algorithm. Our findings were disclosed in coordination with the manufacturer of the devices to minimize the resulting security threats. Finally, we focus on implementation issues in the TLS protocol, of which RSA key exchange is an integral part. We survey existing practical attacks that affect current usage of TLS for securing the Web. We specify conditions for the attacks as attack trees. Using measurements on popular domains, we confirm that RSA padding oracles are iv currently the most common threat. We show how such security issues get amplified by the complexity of the Web ecosystem. In many cases of vulnerable websites, the issues are caused by external or relateddomain hosts. Our work helps to demonstrate how RSA, a seemingly simple and intuitive cryptosystem, requires a lot of knowledge to be implemented correctly. Unlike RSA, elliptic curve cryptography (ECC) uses random sequences as keys and does not require padding. It is more resistant to bad user configurations and provides many other benefits. We conclude that practitioners should follow the example of TLS version 1.3 and stop using RSA in favor of ECC. v Keywords Bleichenbacher's oracle, Coppersmith's algorithm, cryptographic library, cryptographic protocol, factorization, key generation, RSA, TLS vi Contents 1 Introduction 1 1.1 Problem statement 2 1.2 Contributions 3 1.2.1 Biased RSA key generation methods 3 1.2.2 Vulnerabilities in RSA key generation 3 1.2.3 TLS protocol vulnerabilities 4 1.3 Structure of the thesis 5 2 State of the art 7 2.1 Survey of RSA key generation methods 7 2.2 Bias in RSA primes and keys 8 2.2.1 RSA prime types 9 2.2.2 RSAkeypairs 9 2.2.3 Modular bias 10 2.3 Pseudo-random number generatorfailures 10 3 Measuring popularity of cryptographic libraries 13 3.1 Introduction 14 3.2 Method overview 17 3.2.1 Choice of key features 17 3.2.2 Clustering analysis 18 3.2.3 Dataset classification - original approach . . . . 20 3.2.4 Dataset classification - our approach 20 3.2.5 Limitations 22 3.3 Methodology in detail 23 3.3.1 Model 23 3.3.2 Prior probability estimation 23 3.3.3 Key classification 24 3.3.4 Evaluation of accuracy 24 3.3.5 Additional accuracy considerations 28 3.4 Results on relevant datasets 31 3.4.1 Data preparation 31 3.4.2 Internet-wide TLS scans 35 3.4.3 Popularity between usage domains 37 3.4.4 TLS to CT comparison 37 vii 3.4.5 Detection of transient events 38 3.5 Related work 40 3.6 Additional results 41 3.7 Conclusions 42 4 Factorization of widely used RSA moduli 47 4.1 Introduction 47 4.2 Fingerprinting andfactorization 51 4.2.1 Format of the constructed primes 52 4.2.2 Fingerprinting 53 4.2.3 Factorization - attack principle 55 4.2.4 Coppersmith's algorithm in detail 57 4.2.5 Application of Coppersmith's algorithm . . . . 60 4.2.6 Computing the order of a generator in Z*M, . . . 61 4.2.7 Optimization of the parameters M', m,t 62 4.2.8 Guessing strategy 68 4.3 Practical implementation 69 4.3.1 Details and empirical evaluation 69 4.3.2 Possible improvements and limitations 69 4.4 Analysis of impacts 71 4.4.1 Summary of results 73 4.4.2 Electronic identity documents 74 4.4.3 Code signing 76 4.4.4 Trusted Platform Modules 77 4.4.5 PGP with cryptographic tokens 80 4.4.6 TLS and SCADA-related keys 82 4.4.7 Certification authorities 83 4.4.8 Generic Java Card platform 83 4.4.9 Other domains 85 4.5 Mitigation and disclosure 85 4.5.1 Mitigation 86 4.5.2 Future prevention and analysis 88 4.5.3 Responsible disclosure 89 4.6 Related work 90 4.7 Conclusions 91 5 Amplification of TLS vulnerabilities on the Web 93 5.1 Introduction 93 viii 5.2 Background on TLS 98 5.2.1 The Handshake Protocol 98 5.2.2 Ciphersuites 100 5.3 Attack trees for TLS security 101 5.3.1 Threat model 101 5.3.2 Review of known attacks against TLS 102 5.3.3 Insecure channels 105 5.3.4 Leaky channels 105 5.3.5 Tainted channels 108 5.3.6 Partially leaky channels 109 5.4 Experimental setup 110 5.4.1 Analysis platform 110 5.4.2 Data collection and findings H I 5.4.3 Roadmap 113 5.5 Page integrity 114 5.5.1 Security analysis 114 5.5.2 Experimental results 116 5.6 Authentication credentials 118 5.6.1 Security analysis 118 5.6.2 Experimental results 121 5.6.3 Detected attacks 123 5.7 Web tracking 124 5.7.1 Security analysis 124 5.7.2 Experimental results 126 5.8 Closing remarks 127 5.8.1 Related work 127 5.8.2 Ethics and limitations 128 5.8.3 Summary and perspective 129 5.9 Additional results 130 5.9.1 Notable out of scope attacks against TLS . . . . 130 5.9.2 More detailed attack trees 134 6 Conclusions 139 Bibliography 143 A Author's publications 167 ix 1 Introduction The RSA cryptosystem predates most currently used cryptographic libraries. It is often a necessary part of a new library and perhaps one of the first features to be implemented. In a survey of RSA key generation implementations [Sve+16a], we saw how the source code for RSA in community-driven open-source libraries often remained untouched over many library versions. We sought to challenge RSA cryptosystem implementations to find out whether they were the best they could be or lagging behind the constantly advancing attacks and recommendations. It was proven time after time that it is necessary to repeatedly scrutinize both old and new systems, to actively improve the security of practical applications. Cryptographic implementations were shown to fall short of expectations set by standards, such as when RSA key generation in cryptographic libraries did not follow standards [Sve+16a], the size of the Diffie-Hellman subgroup was not validated by libraries as required [Val+17], or random number generators were not working correctly [Hen+12; Bel08; Bar+16; HFH16]. By scrutinizing not just specifications, but also practical applications, urgent problems can be discovered and addressed. To complicate the matter, without the cooperation of the authors, proprietary systems must be evaluated without the knowledge of their inner workings. This is addressed by black-box testing [Soml6b] and reverse engineering [Nem+17b]. With the presence of bugs in library implementations, it is also desirable to measure impacts of resulting security vulnerabilities. In some cases, the observation cannot be made directly, but the applicability of the attack becomes known only after expending non-trivial work. Previously, we proposed a method for inferring the cryptographic library from bias in an RSA key [Sve+16a], reducing the uncertainty of the presence of a vulnerable library. However, we also identified the shortcoming of the method, which we address in this thesis. Despite some attacks being known in theory, often system designers do not deploy countermeasures unless the feasibility of the attack is demonstrated. There are several examples in the TLS protocol suite. The RC4 stream cipher was known to have biased keystream [MS02], but it was only deprecated [Pop15] in TLS when practical attacks were 1 i . INTRODUCTION constructed [A1F+13; GPM15; VP15]. Weak cryptographic algorithms, such as the MD5 hash function and deliberately weakened RSA and Diffie-Hellman parameters were supported, until SLOTH (transcript collision attacks) [BL16a], F R E A K [Beu+15] and Logjam [Adr+15], respectively, exploited them. Legacy protocol versions often remain supported beyond their usefulness, leading to attacks on the weakest part of the system [JSS15; Avi+16]. Even old attacks need to be revisited and their applicability to new systems verified. Malicious parties may have already done so and may be exploiting the weaknesses. 1.1 Problem statement We aim to scrutinize RSA key generation methods from the perspectives of design and implementation, including an empirical analysis of keys used in real systems. We also study the resiliency of TLS protocol implementations to a variety of known attacks, amplified by the complex dependencies in the Web ecosystem. In summary, the main areas of our research are: • Biased RSA key generation methods - in the literature (standards and practical implementations) there is no consensus on RSA key generation methods. As a result, alternative methods produce keys with different biases. We aim to explore the consequences of using keys from biased distributions, such as RSA key classification and cryptographic library popularity measurements. • Vulnerabilities in RSA key generation - we aim to identify design choices of a selected RSA key generation method to evaluate its security properties. • TLS protocol vulnerabilities - many diverse attacks against implementations of the TLS protocol were published. It can be challenging to understand how they can be mounted and mitigated. Their consequences are not easily evaluated for a specific target in the intricate system of servers running the Web. We aim to ease these tasks and make the results understandable to a wider audience. 2 i . INTRODUCTION 1.2 Contributions We discuss the specific contributions to the research questions. 1.2.1 Biased RSA key generation methods Accurate library popularity measurements are not readily available. They serve an important role for precise RSA key origin classification and for measuring impacts of security vulnerabilities in cryptographic libraries. We created a practical tool capable of making such measurements and able to evaluate the trends in library popularity in historical datasets. Previous solutions that relied on indirect measurements based on proxy information were not backed by rigorous analysis. Alternative methods [Sve+16a] have known limitations. We propose a solution that uses statistical inference to approximate a share of libraries matching an observed distribution of RSA keys in an inspected dataset. The method extends our previous work [Sve+16a]. The main difference is the fact that datasets of keys are processed as a whole. The original solution considered keys individually and did not take advantage of the "big picture". We collected large datasets of public RSA keys from various sources and applied our methods to answer questions pertaining to the popularity of cryptographic libraries on the Internet. We evaluated the trends over time and demonstrated differences across application domains. The results were published as [Nem+17a] and are presented in Chapter 3. 1.2.2 Vulnerabilities in RSA key generation The RSA key generation algorithm used in libraries of Infineon Technologies exhibited remarkable statistical properties, as we noted in [Sve+16a; Sve+16b]. It showed entropy loss and hinted at a possible security vulnerability. The details of the key generation algorithm were not published by the manufacturer since neither the source code nor the object code was made available. 3 i . INTRODUCTION We analyzed a large number of public and private RSA keys from Infineon smartcards using statistical and algebraic methods, in order to reveal the key generation method. We were able to correctly determine the algorithm and precisely measure the entropy loss resulting from its unsound efficiency improvements. We developed and optimized a practical factorization method that reveals the private key given the public key. A n efficient fingerprinting technique was used to detect affected RSA keys in a variety of domains. Millions of electronic identity documents used in several countries were affected, as well as Trusted Platform Modules in multiple laptop models. Other applications that used the flawed library to generate RSA keys used for electronic signatures were also threatened. The results were published as [Nem+17b] and are presented in Chapter 4. The vulnerability received a lot of media attention [Gool7b; Leyl7b; Khal7], especially in connection with electronic identity documents [Gool7a; Leyl7a; Vahl7]. 1.2.3 TLS protocol vulnerabilities We systematically described the conditions and consequences of practical attacks against the TLS protocol. We streamlined the analysis of whether they can be mounted and mitigated on real targets in a wider scope of the Web ecosystem. We performed a security assessment of a selected set of popular websites. We presented the results as specific threats to essential aspects of the security of the sites. Our results showed that the most commonly applicable attacks are variants of the RSA padding oracle. Their consequences range from threatening the confidentiality of past recorded messages to providing an attacker with active M a n in the Middle capabilities. The vulnerabilities are due to implementation errors. It has been argued that the underlying cause is the poor choice of the padding algorithm and complex collection of countermeasures that all need to be implemented correctly. The findings help to reinforce our experience that implementations are not up to date with best practices. We increased the scope of our study from a typical list of most popular websites also to the supporting infrastructure. We were able to find much more vulnerable servers, as secondary systems often receive less attention for maintenance. Most importantly, we were able 4 i . INTRODUCTION to demonstrate how the flaws get amplified by systems that rely on these vulnerable or misconfigured servers. The results were published as [Cal+19] and are presented in Chapter 5. The research was also covered by media [Newl9]. 1.3 Structure of the thesis The thesis is further divided as follows: • Chapter 2 describes our initial research on RSA key generation methods, leading to two major research areas of the thesis. It represents the state of the art before we made our contributions to the topics. More specialized related work is discussed individually in the chapters that cover our concrete research questions. • Chapter 3 presents a practical application for the existence of biased RSA key generation methods. We design and perform measurements of the popularity of cryptographic libraries on the Internet, over time, and across different application domains. • Chapter 4 is dedicated to the flawed RSA key generation algorithm found in a cryptographic library of a manufacturer of secure chips. We describe our attack, its optimization, and performance evaluation. We evaluate various domains for the presence of vulnerable keys. • Chapter 5 details our study of the feasibility and consequences of practical TLS attacks. We demonstrate how a relatively few exploitable vulnerabilities get amplified by the complexity of the Web ecosystem. • Chapter 6 concludes our research on the flaws and shortcomings of RSA implementations. We summarize the main outcomes and future work. • Appendix A lists the publications of the author of the thesis, including the specific contributions made by the author. 5 2 State of the art The topic of this thesis was inspired by the 2016 paper The MillionKey Question - Investigating the Origins ofRSA Public Keys [Sve+16a] co-authored by the author of the thesis. In this chapter, we summarize its results of surveying implementations of RSA key generation. The core idea of the paper - to explore biases in RSA keys in practice and leverage them for RSA key classification - was unique. Hence the single paper covers state of the art for a large part of our research presented herein. The outcomes are very relevant for Chapters 3 and 4. The paper also helps to demonstrate how complicated specifications contribute to problems such as those studied in Chapter 5. Chapters detailing our particular research questions provide more specialized summaries of the more closely related work. Namely, in Chapter 3, we dive deeper into the RSA key classification and discuss alternative ways of estimating the popularity of libraries in Section 3.5. For Chapter 4, we discuss RSA key generation methods and factorization attacks on RSA in Section 4.6. We focus on TLS attacks throughout Chapter 5, presenting both a survey of attacks in Section 5.3 and references to related studies and measurements both for TLS and Web security in Section 5.8. 2.1 Survey of RSA key generation methods We showed in [Sve+16a] that authors of different cryptographic l i braries adopt various methods for RSA key generation. The situation arose from the existence of different competing standards and publications on the topic, as well as from varying limitations and requirements placed on the libraries and similar products. Even subtle differences in the algorithms can introduce small bias into the distributions of the produced keys. We identified the most common sources of the biases that can be detected in public or private keys. Previous surveys of RSA prime generation algorithms were published [LN11; LN14; JP06]. The crucial difference of our work [Sve+16a] was that we focused on the actual outputs of the implementations. Some libraries followed standardized algorithms; many did not include any specification or reference for their algorithms. In addition, 7 2. STATE OF THE ART coding mistakes can create further discrepancies with the original algorithm. A more recent survey [Alb+18] focused on primality testing in implementations. It revealed how a few publications could shape the choices of many independent implementations. Primality testing is often described with the assumption that tested values are random, while the libraries used the same approach for handling adversary inputs. Our paper also shows how to use bias extracted from a specific key to classify the key as originating from a concrete class of RSA key generation implementations. In the best case, a single library can be identified. O n the other hand, large number of libraries behave similarly, hence they belong to the same class. Even though the chosen classification method is simple, a single key is correctly classified on the first try with average accuracy over 40% for 13 classes. This result was extended to large datasets of public RSA keys. However, the produced statistics describing the collections of public RSA keys from the Internet were skewed, due to keys being handled individually. We developed a new method that considers the big picture. It was published in [Nem+17a] and described in Chapter 3. Our survey paper was also the first to point out extensive biases in keys generated by Infineon smartcards. By studying the biases more precisely in subsequent work, we were able to reverse engineer the key generation algorithm and devise a practical RSA key factorization method as seen in Chapter 4. The results were published as [Nem+17b]. 2.2 Bias in RSA primes and keys Bias in RSA primes was previously used to identify the source of RSA keys factored using an efficient batch variant of the greatest common divisor (GCD) algorithm [Hen+12; Mirl2]. Our previous work [Sve+16a] identified more types of bias found in RSA keys. 8 2. STATE OF THE ART 2.2.1 RSA prime types According to the survey [Sve+16a], implementations most commonly generate probable, provable, and strong primes. Papers such as [LN11; JP06] imply an additional category of constructed primes. Some categories can be distinguished based on the factorization of p — 1 and p + 1, p being one of the RSA primes. For every strong prime p, both p — 1 and p + 1 contain a factor of a certain length (or the length is from a specific interval). Provable primes p have such factor in p — 1, but not in the factorization of p + 1. Probable primes may show some bias in the factorizations, yet there are no factors of large fixed length in either p — 1 or p + 1. The paper does not explicitly give a method to tell apart probable primes generated randomly and by an incremental search. In the former case, random numbers are generated until a prime is found. In the latter case, a single random value is generated and incremented until a prime is found. Large primes are not evenly spaced. Incremental search biases the distribution of primes toward primes that are preceded by a larger gap made of composite numbers. Generating any value from a specific gap results in the same prime, hence gaps with more values have a higher probability of being selected. It follows that the distribution of the distance to the previous prime carries different types of bias for these two methods. 2.2.2 RSAkeypairs The RSA modulus is a product of two primes. The libraries usually generate a modulus of a precise length supplied by the user, and the primes have half the bit length of the modulus. A product of two fc-bit numbers has either 2k or 2k — 1 bits. It is possible to generate two fc-bit numbers and discard one or both of them in case their product is too short. It is more common to generate the primes from a smaller interval or to modify the high bits of the candidate values to ensure that their product has the correct length. The choice of interval affects the distribution of the most significant bytes of primes and resulting RSA moduli. It is most obvious when the high bits of primes use shorter intervals than necessary. 9 2. STATE OF THE ART 2.2.3 Modular bias All primes are odd, but some libraries also make values biased modulo larger numbers. A specific case is the OpenSSL library, which does not allow RSA primes equal to one modulo any prime from 3 to 17863. This observation can serve as a fingerprint of the private key, as the probability that two random primes have this property is quite low. It was used to identify keys originating from OpenSSL in a study of keys factorable by the Batch G C D method due to shared primes [Mirl2]. In the extended technical report [Sve+16b] of our survey [Sve+16a], we correctly identified further bias in Infineon primes and moduli. The remainders modulo certain small primes were only from specific subgroups of residue classes and did not represent all residue classes. It was observed that the values were almost uniformly distributed modulo all other tested primes. In this thesis and [Nem+17b], we extended this analysis to composite moduli and were able to describe the bias modulo a product of several consecutive primes. A l l primes originated from a single subgroup generated by a single generator. 2.3 Pseudo-random number generator failures The pseudo-random number generator (PRNG) provides random bits for the key generation. In the case of probable primes, it is usual that the random bits are directly used to construct the candidate value. Hence we can test the bytes of the prime instead of the PRNG output. We skip the bottom bytes that get incremented in incremental search and the top bytes that are modified to fit the intervals. In [Sve+16a], we performed a simple non-overlapping serial test on two consecutive bytes, finding one case of apparent bias. One family of smartcards occasionally produced keys that shared primes that make the keys easy to factor, if they share a prime [Hen+12]. The reason was an unchecked failure of the P R N G that provided zero-value bytes. The top bits were modified, and the value was incremented until a prime was found. It is not necessary to have a fully predictable PRNG output. Even a partial or approximate knowledge of a prime can be used to factor keys with a variant of Coppersmith's attack [Cop96a; Ber+13]. 10 2. STATE OF THE ART In many cases of constructed primes, we do not have direct access to the random sequence. The resulting prime is constructed from partial values. For example, if the library uses strong primes, we would have to factor p — 1 and p + 1 and correctly identify which factors were generated as the auxiliary primes. 11 3 Measuring popularity of cryptographic li- braries In 2016, we surveyed RSA key generation methods used in practice [Sve+16a]. We demonstrated that public RSA keys carry enough bias to classify them to their originating cryptographic library with much higher success than for random guessing. As an additional practical demonstration, we processed millions of keys from public sources and used our method to attribute them to a probable source. However, when we summarized the most likely sources of all keys, some objectively unlikely libraries were represented, such as cryptographic smartcards in the domain of TLS servers. In this chapter, we explain and fix the imprecise measurements. In summary, the problem lies in looking at keys individually instead of considering them all at once. The classification of an individual key always returns the library that produces such key with the highest likelihood. However, the likelihood would be different for a group of two, three, or more keys. We must consider that a library may contribute anything from zero to millions of keys used on the Internet. Individual instances of the same key generation algorithm running independently on thousands of machines produce results very similar to what we collected by running it on a single computer repeatedly. Hence if we look at all the keys generated collectively by millions of computers, all of them using one of a few cryptographic libraries, we can observe a mixture of the distributions that we collected from the same libraries locally. The main principle of our new approach is to discover the parameters of the mixture - how much of the whole is contributed by each library. This, in turn, gives us an approximation of the popularity of cryptographic libraries used on the Internet. Based on our experimental measurements and comparisons with other indicators on the usage of libraries, our new method is much closer to the truth than before. The results in this chapter were published in [Nem+17a]. 13 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES 3.1 Introduction With solid mathematical foundations for the currently used cryptographic algorithms like RSA or AES, a successful attack (a compromise of used keys or exchanged messages, a forgery of signatures, etc.) is achieved only very infrequently through mathematical breakthroughs, but dominantly by a compromise of secrets at the end-points, by attacks on the protocol level or via so-called implementation attacks, often combined with an immense computational effort required from the attacker. Implementation attacks exploit some shortcomings or a specific behavior of the software leading to unintended data leakages in otherwise mathematically secure algorithms. A large number of practical attacks in recent years [Laz+14] testifies how difficult it is to make an implementation secure, robust and without side-channel leakage. Even major libraries such as OpenSSL, Java JCE or Microsoft CryptoAPI were hit by multiple problems including extraction of RSA private keys [BB05] or AES secret keys [Ber05] remotely from a targeted web server and generation of vulnerable keys by a weak or a malfunctioning random generator [Bel08; Hen+12]. It is reasonable to expect that similar problems will occur in future for these and other cryptographic libraries as well. The prediction of an impact for a future bug depends not only on the nature of the bug (unknown in advance) but also on the overall popularity of the affected cryptographic library within the targeted usage domain. A security bug in OpenSSL will probably cause more harm than a bug in an unknown or sparsely used library. Yet the estimation of the popularity of a given library is a complicated affair. As a library produces random keys, it is difficult to attribute a particular key to its originating library based only on the bits of the key. A common approach is to make indirect estimates based on additional information such as specific strings inserted into certificates, default libraries used by a software package which is identified by other means (e.g., the Apache HTTP Server typically uses OpenSSL) or specific key properties (uncommon key lengths or domain parameters). A l l these approaches leave a large uncertainty about the real origin of the target key. A certificate can be crafted by a different software than its key was, a server key may be imported, and 14 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES a combination of an algorithm and key length are only rarely specific to a single library. Our work aims to accurately measure the popularity of libraries based on the subtle biases in bits of RSA public keys due to different implementations of the prime pair selection process, as recently described in [Sve+16a]. The bias has almost no impact on the entropy of a key and poses no threat with respect to factorization attacks. However, it allows for a probabilistic attribution of a key to the originating library. We focus on answering the following questions: 1. How many keys in an inspected dataset originatefrom specific cryptographic libraries ? 2. How does the popularity of cryptographic libraries change over time? Can we detect sudden temporary changes ? 3. What library generated a single given RSA key if the key usage domain (TLS, SSH, etc.) is known? In the original work, all libraries were assigned the same prior probability - an assumption that is certainly inaccurate (intuitively, OpenSSL is a far more common source of TLS keys than PGP software). We propose an improved method that automatically extracts the prior probability directly from a large dataset - obtaining the popularity of libraries in the inspected dataset and subsequently improving the classification accuracy of individual keys. The answer to the first question tells us the popularity of cryptographic libraries in different usage domains. Since the method is based on the actual key counts instead of anecdotal proxies (e.g., installed packages or server strings), it is significantly more accurate. Besides providing usage statistics, the popularity of the libraries is important when estimating the potential impact of (past and future) critical flaws, as well as when deciding where to most efficiently spend the effort on development and security code review. The availability of large Internet-wide scans of TLS handshakes performed every week, Certificate Transparency logs and append-only PGP keyserver databases, allow us to perform a study of cryptographic library popularity over time, hence to find an answer to the second question. When the scans are performed as frequently as every week or 15 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES even every day, temporary changes in the popularity ratio can reveal sudden changes in the distributions of the keys, possibly making a library more prominent than expected. Such phenomena may indicate users reacting to a disclosed vulnerability (e.g., by replacing their keys) or some significant changes in security procedures of server implementations. Finally, an accurate answer to the third question allows us to reveal the originating library of a particular key. The previous work [Sve+16a] correctly labeled the origin of about 40% of random keys, when a single public key was classified in a simulation with evenly probable libraries. We improved the accuracy to over 94% for prior probabilities of libraries typical for the TLS domain. Contributions. Our work brings the following contributions: • A method for an accurate survey of popularity of cryptographic libraries based on matching observed counts of RSA keys to a mixture of biased reference distributions produced by the libraries. • Analyses of usage trends for large real-world archived datasets of certificates for TLS, SSH and PGP from 2010 through 2017. • Detection and analysis of abrupt transient events manifested by a sudden change in the ratio of libraries. • Release of the classification tool and extensible catalog of more than 60 profiles for open/closed-source software libraries, hardware security modules, cryptographic smartcards and tokens. The rest of the chapter is organized as follows: Section 3.2 provides the necessary background for understanding the RSA key classification method based on slight biases in the distribution of keys and a basic overview of the automatic extraction of prior probabilities from an inspected dataset. Section 3.3 explains the details of the library popularity measurement method and discusses the accuracy. Section 3.4 applies our method to large current and archived datasets to measure the popularity of libraries in time and discusses the observed results. Section 3.5 provides a review of related work. We list some additional results in Section 3.6. The chapter is concluded in Section 3.7. 16 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES 3.2 Method overview The authors of [Sve+16a] demonstrated how different implementation choices made by developers of cryptographic libraries lead to biases in generated RSA keys. To generate an RSA key pair, two large random primes p and q (typically half of the binary length of the modulus) must be found. The modulus N is the product of the primes. None of the sources of keys examined by [Sve+16a] produced moduli with uniformly distributed most significant byte, as one might expect from cryptographic keys. Instead, the distributions of moduli of each source were determined by the choice of the primes. In order to reduce the uncertainty about the origin of a particular key, three conditions must be satisfied: 1) bias is present in the key, 2) reference distributions of (ideally) all implementations are known, and 3) a suitable method exists to match the reference data and the observed data. We use the same biases as observed in [Sve+16a]. We collected reference distributions from additional sources and other versions of cryptographic libraries, extending the knowledge of possible key origins. The original classification method was based on conditional probabilities and the application of Bayes' rule. The origin (a group of sources) of a key could be correctly estimated in 40% of attempts - as opposed to 7.7% success of a random guess. We devised a new method that estimates the proportion of sources in a given dataset and more than doubles the average accuracy in TLS datasets. 3.2.1 Choice of key features The most common reasons for the biases in the private primes were efficiency improvements, a special form of the primes, bugs, and uncommon implementation choices. The biases propagate to public moduli to a certain degree - some are directly observable, some require a large number of keys to distinguish and some cannot be seen from the public values. This calls for a creation of a mask of the public keys instead of dealing with the full keys, some properties are extracted and each key is represented by a vector of features. We use the following features, inspired by the original approach: 17 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES 1. The most significant bits of the modulus (2nd to 7th bit): The highest bits of the primes are often set to a constant, e.g., the two highest bits set to 1 to ensure the modulus has the correct bit length. The high bits are sometimes manipulated further, up to four bits were determined non-randomly. Even without directly manipulating the top bits, the intervals from which the primes are chosen are seen in the top bits of the modulus. 2. The modulus modulo 4: Due to bugs and unusual (for RSA) implementation choices, the moduli might end up being Blum integers - due to the primes always being equal to 3 modulo 4, the moduli are always equal to 1 modulo 4. 3. The modulus modulo 3: Another unexplained implementation decision (in OpenSSL and elsewhere) avoids primes p if p — 1 has small divisors, other than 2. If p — 1 and q — 1 are never divisible by 3, then the modulus is always equal to 1 modulo 3 and never equal to 2 modulo 3. For larger prime divisors (5, 7,11, etc.), the property is not directly observable from a single modulus and is therefore impractical for key classification. We rely on the deep analysis of the key generation process and statistical properties of the resulting keys presented in [Sve+16a]. We construct our mask similarly, however, we decided to drop the feature encoding the bit length of the modulus - as it is only relevant for one uncommon library implementation. Our choice of the mask is reflected in Figure 3.1, illustrated by the distributions of mask values for OpenSSL. When compared to [Sve+16a], we also changed the order of the features in the mask, to allow for an easier interpretation of distributions from the illustrations. The relevant biases for all sources are listed in Table 3.3 in Section 3.6. 3.2.2 Clustering analysis For each source we generate a large number of keys (typically one million), extract the features from the keys according to the feature mask and compute the distributions of the feature masks. The previous research [Sve+16a] used a highly representative sample of cryptographic libraries in what were then the most recent available versions. For this 18 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES „ 2.5 2.0 •° 1 .Q O fe. 1. • 6 = 5 Ü 4 3 3 5.2 ^ 1 0 0.5 | : 1.5 Z 0 Q. 0 . 5 1 0 . 0 2 I3 S 2o a- 11/1 n(C U > 1 2 • bilit (13 ° o 6 S. 4 - II ^ 2 • Ü 1 1 1 1 1 2- 0 . 8 2 0 . 6 I 0 . 4 °- 0 . 2 I 0 . 0 6 4 1 2 8 1 9 2 Group 4 > 4 1 3 5 2 o a- 1 rn (J 2 5 5 6 4 1 2 8 1 9 2 Group 7 2 5 5 6 4 1 2 8 1 9 2 Group 8 6 4 1 2 8 1 9 2 Group 9 2 0 . 2 6 4 1 2 8 1 9 2 Group 10 2 5 5 6 4 1 2 8 1 9 2 Group 11 g 4 S 3 o 2 ^ 1 to U 2 5 5 6 4 1 2 8 1 9 2 Group 12 0 6 4 1 2 8 1 9 2 2 5 5 Group 13 Certificate Transparency 03/2017 Total keys: 1 7 , 7 4 5 , 5 4 6 — Original distribution • Group 7 : 6 0 . 0 6 % M Group 1 2 : 2 0 . 4 0 % H Group 1 3 : 1 5 . 2 1 % • Group 1 1 : 3 . 5 0 % • Group 4: 0 . 6 8 % 6 4 1 2 8 1 9 2 2 5 5 2 5 5 2 5 5 2 5 5 2 5 5 Figure 3.3: The reference distributions of the key mask from each library are used to compute the probability with which the given library contributes to the overall distribution of keys in the measured sample. The distribution of keys submitted to Certificate Transparency logs during March 2017 likely contains keys from a mix of distributions as given in the last picture. When we scaled each distribution accordingly and plotted the bars on top of each other (note - the bars are not overlapping), the fit is visually close (the original distribution is given by a black dashed outline and matches the tops of the approximated bars). 25 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES the average correctness of the overall classification process (given as the proportion of keys that were correctly classified, Table 3.2). For the measurement, we repeatedly simulate large datasets according to different distributions, add noise and perform our method. Random noise Even if keys in a large dataset were generated with the same library across many users, the overall distribution will not match our reference distribution exactly, due to the non-deterministic nature of key generation. This contributes to a random noise in the data. We achieve such a noise in our simulations by generating masks nondeterministically (i.e., instead of using reference distributions in place of data, we randomly sample masks according to the distribution). Systematic noise Our analysis does not cover all existing libraries used on the Internet. However, it is quite likely that algorithms used by unknown libraries are similar to those already known (e.g., consider the size of Group 13). In such a case, the library would belong to one of our groups and the only error of the estimation would be in the interpretation of the results - the library is not correctly labeled as a part of our group. Yet still, there may exist groups with profiles that do not match any of our known groups, hence keys generated from these implementations would add systematic noise to the profile of the sample. In our simulations, we create a group representing all unknown distributions. The group profile is chosen randomly in each experiment. To simulate the presence of keys from this group, we modify the prior probability of the simulation to include a certain percentage (e.g., ranging from 0% to 3% in Tables 3.1 and 3.2) of keys to be sampled from the distribution. For example, 3% of systematic noise represents the situation where 3% of the keys in the sample originate from an unknown distribution, not covered by our analysis and belonging to a completely different, never seen before, group. 26 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES Simulation scenarios We considered several distributions of prior probability library usage: Evenly distributed probabilities match the approach in [Sve+16a], however, we face an additional task of first estimating the probabilities from the simulated data. Furthermore, our mask does not use one of the original features (Section 3.2.1). We also assign random prior probabilities to the groups in a different scenario - each group is assigned a uniformly chosen real number from 0 to 1 and the numbers are normalized to sum to 1. Real-world popularities of libraries are better characterized by a geometric distribution - one source dominates (e.g., 50% in our case) and other are exponentially less probable. We additionally ensure that each group has a probability at least 2%. This way, even very rare sources are not completely excluded from the analysis, even if the library is outdated (e.g., PGP SDK 4) or the hardware is very old (e.g., Gemalto G X P E64 smartcard from 2004). We also test the geometric distribution for different permutations of the groups - while in TLS, OpenSSL is always the most probable, in our tests each group may take the first place. Finally, we simulate the data according to the prior probabilities extractedfrom TLS datasets. We add deviations to the probabilities to simulate subtle changes in the popularity of libraries. Accuracy of prior probability estimation The accuracy of the prior probability estimation is given as the expected error in the resulting estimation. The summary is given in Table 3.1. We consider the average error (the expected error in percentage points (pp) for each group probability in each experiment) and the average worst error (the expected error in for the worst result in a given experiment). As an example, if the real probabilities are 60%, 30%, and 10%, and we estimate them as 61%, 32%, and 7%, the average error of the experiment is (1 + 2 + 3) /3 = ± 2 pp and the worst error is ± 3 pp. The averages in Table 3.1 are given for 100 experiments, each simulating one million keys. We considered distinct scenarios (Section 3.3.4) and levels of systematic noise (Section 3.3.4). 27 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES Estimation error (in percentage points) Noise: 0% 1% 2% 3% 0% 1% 2% 3% Distribution Average error Average worst error Even 0.19 0.37 0.63 0.90 0.73 1.71 3.33 5.07 Random 0.19 0.37 0.61 0.84 0.78 1.74 3.25 4.68 Geometric 0.18 0.38 0.63 0.91 0.71 1.70 3.33 4.97 TLS 0.17 0.39 0.66 0.94 0.65 1.78 3.49 5.16 Table 3.1: Accuracy of prior probability estimation for different types of distributions and different amount of systematic noise. The average error gives the expected error of prior probability estimation for each group in percentage points (pp). The average worst error gives the expected value of the largest error in each experiment. E.g., when the keys were generated from a TLS-like distribution with 1% of systematic noise added, the probability of each group differed by ±0.39 pp on average and the worst estimation was off by ±1.78 pp on average. Accuracy of the overall classification process The accuracy of key classification is given as the proportion of keys that were correctly classified as the first guess or at least the second guess. The values in Table 3.2 are given in percents. Tables 3.1 and 3.2 refer to the same set of simulations. The prior probability estimation is performed first. The results show that the classification is quite robust even in the case of errors in prior probability estimations at a level of 5 percentage points, since the success of the classification is not affected dramatically. When compared to the approach of [Sve+16a], the average accuracy increased for other than the even distribution of groups. However, the classification accuracy is improved mostly for the more probable groups and the less probable libraries may be classified incorrectly more frequently than before. 3.3.5 Additional accuracy considerations Some reference distributions can be approximated by a combination of other reference distributions, similarly as the distribution observed in a dataset can be obtained as a combination of reference distributions. A n 28 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES Classification accuracy (in %) with noise Noise: 0% 1% 2% 3% Guess: 1st 2nd 1st 2nd 1st 2nd 1st 2nd Even 33.4 53.2 33.3 52.9 32.9 52.4 32.3 51.8 Random 45.5 67.5 46.1 67.8 45.0 66.7 43.9 65.1 Geometric 81.1 95.2 82.5 95.0 80.3 94.6 80.9 94.3 TLS 94.8 98.7 94.6 98.6 94.4 98.4 94.3 98.3 Table 3.2: Accuracy of key origin classification when prior probability estimates are included in the method for different types of distributions and different amount of systematic noise. The values are in percents. E.g., when the keys were generated from a TLS-like distribution with 1% of systematic noise added, for 94.6% of the keys, the original library was correctly identified on the first guess and 98.6% of keys were correctly labeled by the first or the second most probable group. example of this phenomenon at its worst is the close match of Group 11 (Microsoft libraries) as a combination of 41.3% of Group 13, 30.6% of Group 8, 22.7% of Group 4 and a small portion of other groups. The situation for all groups is illustrated in Figure 3.4, with the most notable groups enlarged. Group 13 has the next closest match, however the error is much larger. Group 7 (OpenSSL) cannot be obtained as a combination of other groups. As a result, the prior probability estimation process may interchange the distribution of Group 11 for a mixture of other distributions or vice versa. Currently, we do not detect such events automatically, since an additional user input would be needed. When considering the results, the domain must be taken into account. E.g., according to our measurement, around 1% of keys in some samples of TLS keys originate from Group 8 (PGP SDK 4 FIPS). Since the presence of the library in TLS is highly unlikely and no other known implementation has the same (quite uncommon) algorithm, we must conclude that this is an error in the estimation. We suspect the error is due to the aforementioned approximation of Group 11. However, there may exist different approximations of the group, hence we cannot simply substitute the suspected ratio. 29 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES Group 1 approximatet 5 Group 2 approximatec 12 • ~ 10 • 8 • o 6 • Q. 4 • il ,> , 1 ro 0 • Group 3 approximated 0 64 128 192 255 Group 4 approximated £ 0 64 128 192 255 Group 5 approximated ' 1.5 ; > 4 I 3 £ 2 O a- 1 £ o H i . . . L0 64 128 192 255 Group 6 approximated 0 64 128 192 255 Group 7 approximated 0 64 128 192 255 Group 8 approximated 0 64 128 192 255 Group 9 approximated 0 64 128 192 255 Group 10 approximated 0 64 128 192 255 Group 12 approximated 0 64 128 192 255 Group 13 approximated 128 192 255 128 192 255 Group 11 approximated 64 128 192 255 128 192 255 Figure 3.4: Some distributions may be interchanged for a mix of other distributions. We used our method to approximate each of the 13 distributions using only the remaining 12 distributions. The graphs show the original distribution as a green outline and the combination of libraries that minimizes the sum of squared distances is visualized by stacking the scaled distributions on top of each other. The results show that Group 7 (OpenSSL) cannot be easily approximated by other groups (the process leads to a large squared differences in the distributions that will not be permitted by the NNLSF method). However, Group 11 (with Microsoft libraries) can be simulated relatively closely by a combination of other distributions. Hence, when a real world distribution contains keys from Group 11, the method may misattribute the keys as coming from a specific mixture of libraries instead. 30 3- MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES We hypothesize that such errors could be avoided if the prior probability estimation would start from a very rough approximation of the probabilities supplied by the user (we use evenly distributed groups) as the starting guess of the NNLSF method. A more resolute solution would remove groups from the analysis if they are unlikely to occur in an examined domain according to empirical evidence. 3.4 Results on relevant datasets Rough estimates of popularity for some cryptographic libraries were provided in [Sve+16a] for TLS, CT and PGP, but with relatively high expected errors. The improvement of accuracy in our work allows for a better inspection of datasets, including the detection of transient events. We also processed significantly more datasets, including the archived ones. 3.4.1 Data preparation We used a wide range of datasets for our analysis. Due to different formats, we pre-process all data into a unified intermediate format. For all datasets, only keys with unique moduli were considered. Censys TLS scan Censys [Dur+15a] performs a full IPv4 address space scan of TCP port 443 on a weekly basis [Cenl5b]. The dataset contains historical scans back to 2015-08-10 when the first scan was performed and continues to present. Each scan is a full snapshot, independent from all other scans, containing all raw and post-processed data from the scan in the form of JSON and CSV files, compressed by LZ4 algorithm [Coll 5]. Some snapshots are only a few days apart and some larger gaps occur, but overall the weekly periodicity is prevalent. Censys scanner tries to perform a TLS handshake with the host being scanned, respecting the IP blacklist maintained by Censys. The latest scan tried to contact 53M hosts. 31 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES EU E EFF SSL Observatory j m*-mw HTTPS Ecosystem ..... Rapi • r - v Unfinished Sonar scan Censys IPv4 TLS sea n Sonarfixed TLS 1.2 handshake Group Group Group Group Group Group Group Group 1: G&D SmartCafe 3.2 2: G&D SmartCafe 4.x & 6.0 3: GNU Crypto 2.0.1 4: Gemalto GXP E64 5: NXPJ2A080&J2A081 &J3A081&JCOP41V2.2.1 6: Oberthur Cosmo Dual 72K 7: OpenSSL 0.9.7 & 1.0.2g & 1.0.2k & 1.1.Oe 8: PGPSDK 4 FIPS Group 9: Infineon JTOP 80K, YubiKey 4 & 4 Nano Group 10: NXPJ2D081 &J2E145G, YubiKey NEO Group 11: BouncyCastle 1.54 (Java), Crypto++ 5.6.0 & 5.6.3 & 5.6.5, Libgcrypt 1.7.6 FIPS, Microsoft CryptoAPI & CNG & .NET Group 12: BouncyCastle 1.53 (Java), CryptixJCE 20050328, FlexiProvider 1.7p7, HSM Utimaco Security Server Se50, Nettle 2.0, PolarSSL 0.10.0, PuTTY 0.67, SunRsaSign OpenJDK 1.8.0, mbedTLS 1.3.19 £, 2.2.1 & 2.4.2 Group 13: Botan 1.5.6 £, 1.11.29 £, 2.1.0, Feitian JavaCOS A22 & A40, Gemalto GCX4 72K, HSM SafeNet Luna SA-1700, LibTomCrypt 1.17, Libgcrypt 1.6.0 & 1.6.5 & 1.7.6, Libgcrypt 1.6.0 FIPS & 1.6.5 FIPS, Nettle 3.2 & 3.3, Oberthur Cosmo 64, OpenSSL FIPS 2.0.12 & 2.0.14, PGPSDK 4, WolfSSL2.0rcl & 3.9.0 & 3.10.2, cryptlib 3.4.3 & 3.4.3.1 Figure 3.5: The combined results from scans of TLS services in the whole IPv4 space as provided by four independent datasets, given with one-month granularity. A n absolute number of unique keys as attributed to different groups by our method are shown. The sudden "jump" for Group 11 (Microsoft libraries) in SonarSSL in 06/2015 is caused by an improper implementation of TLS 1.2 handshake in the scanning software, resulting in an exclusion of a significant portion of Microsoft IIS servers for 18 months. 32 3- MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES Censys Alexa 1M The dataset [Cenl5a] has the same properties as the Censys IPv4 dataset (with respect to periodicity and format). It contains processed TLS handshakes with the top 1 million websites according to the Alexa ranking. The dataset also provides an insight into a specific portion of the Internet certificates, which are otherwise hidden from ordinary IPv4 scans because of the use of Server Name Indication (SNI) TLS extension. SNI enables the web server to multiplex X.509 certificates on a single IP address, because the client sends the desired host name directly in the TLS handshake. Simple TLS handshake returns only one, default virtual host certificate, hence other virtual hosts are hidden from the scan. Moreover, the default certificate is usually generated during server installation (if not overridden later) and thus does not have to be relevant to the context. Rapid7 Sonar SSL Project Sonar [Rapl5] performs a regular scan of IPv4 SSL services on TCP port 443. The dataset includes both raw X.509 certificates and processed subsets. It contains snapshots taken within a time frame of maximum 8 hours. It ranges from 2013-10-30 to the present (still active) with many samples. The files with certificates are incremental, so the scan from a particular day contains only new certificates - not yet seen in the preceding scan. We transform the increments into snapshots. The scanning periodicity varies, making the analysis more complicated. The project also maintains an independent IP address blacklist that evolves in time. Additionally, the scanner code evolves (cipher suite selection, bug fixes, methodology fixes) causing fluctuations in the data. HTTPS Certificate Ecosystem IPv4 TLS scanning dataset [Dur+13] ranging from 2012-06-10 to 2014- 01-29. It is essentially the same as the Sonar SSL dataset with respect to the format and the properties. This dataset contains one host-tocertificate fingerprint mapping file for each scan and one big certificate database for the whole dataset. The periodicity varies a lot. There are many snapshots only two days apart, as well as large gaps between 33 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES samples, up to 50 days. We recoded the dataset to the Sonar SSL format, with an incremental certificate database. We then transformed it to the full snapshot format identical as for Sonar SSL. Certificate Transparency The specification of CT (RFC 6962) allows retrieving an arbitrary range of entries from a log. We processed all entries in logs maintained by Google up to May 2017. A l l entries must be submitted with all the intermediate certificates necessary to verify the certificate chain up to a root certificate published by the log. We process only the leaf certificates. Since the logs are append-only, there is no reliable way of knowing whether an older certificate is still active (the validity period gives an upper estimate), hence we do not have a sample of all certificates in use for a given date. Instead, we process incremental samples - all certificates submitted during a specific period (a day or a week). Client SSH keys - GitHub GitHub gives users SSH-authenticated access to their Git repositories. Developers upload their public SSH keys. One user can have no, one or more SSH keys. GitHub provides an API to list all the registered users and another endpoint allows downloading SSH keys on a per-user basis. We downloaded a list of almost 25M GitHub users with almost 4.8M SSH keys found. The scan was performed in February 2017 and took 3 weeks to finish on a commodity hardware. We implemented a custom multi-threaded crawler for this purpose, downloading user list, SSH keys, parsing them and producing a file for classification. Pretty Good Privacy (PGP) PGP key servers play an important role in the PGP infrastructure as public registers of public PGP keys. The PGP servers synchronize among themselves periodically. We downloaded a dump of the database in April 2017, parsed it and extracted RSA master and subkeys for the analysis. Anyone can upload a valid PGP public key to the key server and download the key later. This has to be taken into 34 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES account during analysis. Anyone can generate thousands of keys and upload them to the key server, which would skew a statistics. This actually happened when a group called Evil 32 [KS15] generated a new PGP key for thousands of identities in the PGP server with a collision on the short key ID to demonstrate the weakness of using a short 32-bit identifier in the PGP ecosystem. 3.4.2 Internet-wide TLS scans Various projects performed Internet-wide scanning since 2010, with different periods, frequencies and scanning techniques. We extracted unique RSA keys from certificates collected by EFF SSL Observatory (only two scans), HTTPS Ecosystem (07/2012-02/2014), Rapid7 SonarSSL (11/2013-05/2017) and Censys IPv4 TLS (08/2015-05/2017) scans. The processing is described in Section 3.4.1. The overlapping portions of the different scans provide a good match except for Group 11 (Microsoft libraries) in the Rapid7 Sonar SSL scan between 11/2013 to 06/2015. The significant decrease of Microsoft libraries is caused by an improper implementation of the TLS vl.2 handshake by the scanning software, resulting in exclusion of a significant portion of Microsoft IIS servers for 18 months as confirmed by Project Sonar authors. Figure 3.5 shows the absolute number of unique RSA keys attributed by us to every classification group of cryptographic libraries. OpenSSL (Group 7) is increasingly more popular, also relatively to other libraries. As of May 2017, there are about 8 million active unique RSA keys generated by OpenSSL. Group 11 that contains Microsoft libraries is relatively stable since 2012 starting with 2M, rising to 2.4M in 2014 and then slightly decreasing to 2.2M keys in 2016. Since there are several changes in the data collection methodology and software, it is difficult to make a conclusion about the significance of the numbers. However, the data indicates a comparably stable number of keys originating from the group. The large Group 13 (containing Nettle, OpenSSL FIPS, and WolfSSL among others) used to be the third most common library with 0.4-0.5M keys, but was gradually matched by Group 12 (containing OpenJDK and mbedTLS) in year 2016. Both groups now have an almost equal share of about 0.5 M unique keys. 35 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES TLS 08/2010 (EFF SSL Observatory) TLS 03/2017 (Censys) Total keys: 5,333,919 — Original distribution • Group 7: 56.65% Group 11: 23.73% Group 13: 15.23% Group 8: 2.02% • Group 12: 1.94% • Group 4: 0.35% iflk.iJk TLS 03/2017 Alexa Top 1M (Censys) J t = Total keys: 353,185 Original distribution Group 7 84.59% Group 11 11.08% I M Group 12 2.17% Group 13 0.92% Group 8 0.67% Group 4 0 47% •jlllllllllllll^mrnr,. 4 128 192 Mask GitHub 02/2017 Total keys: 11.649,495 Original distribution Group 7: 70.16% Group 11: 19.56% Group 12: 4.61% Group 13: 4.10% Group 8: 1.15% Group 4: 0.34% llflilriw^lllHuit. Certificate Transparency 03/2017 Total keys: 17,745,546 — Original distribution H Group 7: 60.06% H Group 12: 20.40% Group 13: 15.21% H Group 11: 3.50% Group 4: 0.68% Ulli 192 255 Mask PGP 04/2017 Total keys: 3,650,466 - - Original distribution • Group 13: 85.20% • Group 7: 11.21% • Group 6: 2.24% • Group 12: 0.59% Group 8: 0.51% Group 10: 0.11% Group 9: 0.10% LI Group 1: Group 2: Group 3: Group 4: Group 5: Group 6: Group 7: Group 8: 128 Mask G&D SmartCafe 3.2 G&D SmartCafe 4.x & 6.0 GNU Crypto 2.0.1 Gemalto GXP E64 NXPJ2A080 &J2A081 & J3A081 & JCOP 41V2.2.1 Oberthur Cosmo Dual 72K OpenSSL 0.9.7 & 1.0.2g & 1.0.2k & l.l.Oe PGPSDK 4 FIPS Group 9: In Group 10: rGroup 11: E 128 192 25 Mask Infineon JTOP 80K, YubiKey 4 & 4 Nano : NXP J2D081 & J2E145G, YubiKey NEO : BouncyCastle 1.54 (Java), Crypto+ + 5.6.0 & 5.6.3 & 5.6.5, Libgcrypt 1.7.6 FIPS, Microsoft CryptoAPI & CNG & .NET Group 12: BouncyCastle 1.53 (Java), CryptixJCE 20050328, FlexiProvider 1.7p7, HSM Utimaco Security Server Se50, Nettle 2.0, PolarSSL 0.10.0, PuTTY 0.67, SunRsaSign OpenJDK 1.8.0, mbedTLS 1.3.19 & 2.2.1 & 2.4.2 Group 13: Botan 1.5.6 & 1.11.29 & 2.1.0, Feitian JavaCOS A22 & A40, Gemalto GCX4 72K, HSM SafeNet Luna SA-1700, LibTomCrypt 1.17, Libgcrypt 1.6.0 & 1.6.5 & 1.7.6, Libgcrypt 1.6.0 FIPS & 1.6.5 FIPS, Nettle 3.2 & 3.3, Oberthur Cosmo 64, OpenSSL FIPS 2.0.12 & 2.0.14, PGPSDK 4, WolfSSL 2.0rcl & 3.9.0 & 3.10.2, cryptlib 3.4.3 & 3.4.3.1 Figure 3.6: Library share in different usage domains. The sources responsible for at least 0.1% of all keys in a particular scan of the domain are listed in the legend. OpenSSL library dominates in all domains, except for the PGP dataset. 36 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES The last somewhat significant group is Group 8 with about 1% of keys, slightly decreasing in popularity since 2016. The group contains only the PGPSDK 4 FIPS implementation, which is unlikely to be so popular in TLS. There either exists a different popular library with a similar prime generation algorithm (not included in the set of libraries studied by us), or a portion of the dataset was misattributed to the library due to a similarity of a combination of profiles, as explained in Section 3.3.5. 3.4.3 Popularity between usage domains Although the TLS ecosystem is the most frequently studied one, large datasets of RSA keys exist for other usage domains. We analyzed and compared the relative popularity of cryptographic libraries as of March 2017 for Internet-wide TLS scans (Censys), obtained from the 1 million most popular domains according to the Alexa survey, and the certificates uploaded to all Google's Certificate Transparency logs during that month. We also present the TLS keys as of December 2010 to illustrate the progress in time. Additionally, SSH authentication keys of all GitHub users and all keys from PGP key servers were analyzed. The differences are shown in Figure 3.6. The analysis shows significant differences among the usage domains. The GitHub SSH dataset is clearly dominated by OpenSSL with more than 96% - the default library behind ssh-keygen utility from OpenSSH software. Fewer than 3% belong to Group 12, which contains the popular SSH client PuTTY for Microsoft Windows. The PGP keys are generated mostly by Group 13 (containing Libgcrypt from the widely used GnuPG software) with about 85% share, followed by OpenSSL with approximately 11%. 3.4.4 TLS to CT comparison According to a survey based on IPv4 scans, Certificate Transparency (CT) and a large set of active domain names [Van+16], the combination of CT and IPv4 scans provides a representative sample of the Internet. We are interested in the differences between the methodologies. A n interesting popularity distribution can be observed from CT logs. CT has been used on a large scale since 2015, with the first logs 37 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES launching in 2013. The logs now contain almost an order of magnitude more certificates than those reachable by direct IPv4 TLS scans. Due to the validation of TLS certificates performed by all modern browsers, all valid certificates used for TLS are now present in CT, but also more. CT logs also contain TLS certificates hidden from IPv4-based scans due to Server Name Indication (SNI) TLS extension. Additionally, certificates never seen in TLS or not intended for TLS can be submitted to the logs. According to a study of the CT landscape [Gus+17], almost 95% of certificates stored in C A operated logs are also seen in CT logs operated by Google (Pilot, Icarus, Rocketeer, Skydiver, Aviator) - we therefore use these logs with newly inserted certificates during certain time frames (a day, a week, a month) to perform our analysis. We compare selected results for certificates submitted to CT during March 2017 with a Censys scan from the same month in Figure 3.6. While OpenSSL is again the most common library in CT, it is responsible only for about 60% of unique RSA keys, where the Censys scan contains about 70% of the same. Microsoft libraries (Group 11) are in a minority with 3.5% in CT, whereas they are responsible for almost 20% in TLS. The longer validity of certificates generated by Microsoft software (especially when compared to certificates produced by Let's Encrypt C A with 3-month validity) is a potential reason, with SNI multiplexing being another one. Groups 12 and 13 are relatively common in CT with 20% and 15%, respectively, whereas both are below 5% in TLS. 3.4.5 Detection of transient events We used our method to estimate the proportion of libraries for keys newly submitted every week to Google's CT servers between October 2016 and May 2017, limited to certificates issued by Let's Encrypt CA, as shown in Figure 3.7. The number of certificates added every week fluctuates significantly, as well as the responsible libraries. Only a relatively small number of keys from Group 11 were inserted when compared to the number of certificates in active use found by TLS scans. This suggest that Microsoft libraries are less likely to be used with Let's Encrypt software. Interestingly, there is a certain periodicity between such certificates being submitted. 38 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES - 1 3 5 7 9 11 - 13 2 4 6 8 10 ••••»••• 12 1Group 1: Group 2: Group 3: Group 4: Group 5: Group 6: Group 7: Group 8: G&D SmartCafe 3.2 G&D SmartCafe 4.x & 6.0 GNU Crypto 2.0.1 Gemalto GXP E64 NXP J2A080 & J2A081 &J3A081&JCOP41V2.2.1 Oberthur Cosmo Dual 72K OpenSSL 0.9.7 & 1.0.2g & 1.0.2k& l.l.Oe PGPSDK 4 FIPS Group 9: Infineon JTOP 80K, YubiKey 4 & 4 Nano Group 10: NXP J2D081 & J2E145G, YubiKey NEO Group 11: BouncyCastle 1.54 (Java), Crypto+4- 5.6.0 & 5.6.3 & 5.6.5, Libgcrypt 1.7.6 FIPS, Microsoft CryptoAPI & CNG & .NET Group 12: BouncyCastle 1.53 (Java), CryptixJCE 20050328, FlexiProvider 1.7p7, HSM Utimaco Security Server Se50, Nettle 2.0, PolarSSL 0.10.0, PuTTY 0.67, SunRsaSign OpenJDK 1.8.0, mbedTLS 1.3.19 & 2.2.1 & 2.4.2 Group 13: Botan 1.5.6 6, 1.11.29 S. 2.1.0, Feitian JavaCOS A22 & A40, Gemalto GCX4 72K, HSM SafeNet Luna SA-1700, LibTomCrypt 1.17, Libgcrypt 1.6.0 & 1.6.5 & 1.7.6, Libgcrypt 1.6.0 FIPS & 1.6.5 FIPS, Nettle 3.2 & 3.3, Oberthur Cosmo 64, OpenSSL FIPS 2.0.12 & 2.0.14, PGPSDK 4, WolfSSL 2.0rcl & 3.9.0 & 3.10.2, cryptlib 3.4.3 & 3.4.3.1 Figure 3.7: The number of keys from distinct groups added to CT weekly, found in certificates issued by Let's Encrypt CA. 39 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES Some periodic monthly insertion events are also visible for Group 12 (OpenJDK, Bouncy Castle before v. 1.54, mbedTLS, etc.) and bi-monthly for Group 13 (OpenSSL FIPS, WolfSSL, etc.). Most Let's Encrypt certificates from the events are reissued after 60 days. 3.5 Related work Only very few prior publications are concerned with the identification of the library responsible for generating an RSA key. Except for [Sve+16a] (the work we directly improve on), the task was done by [Mirl2], who observed that particular biases in private keys generated by OpenSSL can be also seen in the majority of keys that were found in TLS scans and factored by [Hen+12; HFH16; Bel08]. However, the method only worked because of the knowledge of the private primes. Furthermore, the keys were generated with insufficient entropy due to bad random generators. Hence the technique can be extended neither to all keys generated by OpenSSL, nor to other libraries. The popularity of a library can be also estimated from the positive ratings (stars or likes) of open-source repositories, such as those hosted on GitHub. However, this seems to be a very poor method - OpenSSL only has four times as many stars as mbedTLS and closed-source libraries like Microsoft C A P I / C N G cannot be compared this way at all. Server fingerprints were used to probabilistically determine the operating system, or even the versions of the deployed software [Netl7b; Lyol7]. Indeed, the estimates on the number of servers running M i crosoft OS published by [Netl7a] matches the results of our analysis of a scan of the Alexa Top 1 million domains. A similar analysis was performed for software packages handling the SSH connection [Alb+16] mostly served by Dropbear and OpenSSH, confirming the dominance of OpenSSH-based software. Debian-based Linux distributions offer public statistics about the popularity of software packages as a part of a quality assurance effort [GB17]. The results are based on a relatively high number of users (almost 200K) and provide an insight into the number of package installation, yet they cannot capture the number of keys in use. The li- 40 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES braries used to validate SSL certificates in non-browser client software were surveyed in [Geo+12]. A direct identification of software packages running on other cores in a cloud environment based on cache side-channels was demonstrated by [Ira+15; Inc+16]. The measurement requires a local presence, does not scale and cannot be used on archived datasets. However, it recovers not only the library, but also a particular version. Measurements and analyses of the TLS ecosystem have a long history with large scale scans starting in 2010 with the EFF SSL Observatory project [BE10], followed by analyses of both valid certificates [C013; Dur+13; Dur+14; DBH14; Fel+17] (the majority of papers) as well as invalid ones [Chu+16]. The significant increase of popularity of Certificate Transparency servers now provides a view of the certificates that are otherwise unreachable via IP address based scanning [Van+16]. Researchers usually focus on the properties of the certificates (e.g., validity period) or the certificate chain extracted from the TLS handshakes. Chosen cryptographic algorithms and key lengths were also analyzed [Dur+15a; ICS17], showing that more than 85% of currently valid certificates use the RSA algorithm - making our method based on RSA keys representative of the ecosystem. The client SSH authentication keys extracted from GitHub were previously collected and analyzed [Rebl5; Bar+16] with a focus on the algorithms, key lengths, and presence of weak keys, detecting keys generated from OpenSSL with insufficient entropy. 3.6 Additional results Table 3.3 shows the sources considered in the analysis, together with the relevant biases. There are two types of modular bias - modulo 4, due to RSA moduli being Blum integers and modulo 3, due to implementations avoiding primes p such that p — 1 is divisible by 3. The primes are biased due to different intervals, from which they are generated. The bias propagates to public keys. Notation: H2 - the primes have the two top bits set to one; RS - the primes have the top bit set to one, then short moduli are discarded; \/2 - the primes are chosen from the interval (n - length of modulus). Other proprietary implementations of prime selection are: G & D - Giesecke 41 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES & Devrient (G&D); Gem. - Gemalto; Inf. - Infineon; NXP - NXP; PGP - PGP SDK; Uti - Utimaco (similar to RS). Figure 3.8 shows the number of keys attributed by us to different cryptographic libraries in certificates from the Alexa Top 1 million domains collected by Censys. The number of OpenSSL keys is rising and the percentage of keys coming from Microsoft implementations is much smaller than in general TLS scans. Previous analyses of Internet-wide TLS scans [C013; Dur+13; Dur+14; DBH14] compared various properties of certificates. Valid and invalid certificates were compared by [Chu+16], showing that the majority of certificates found by scans are invalid and have interesting properties. We compared self-signed certificates to certificates signed by third parties in historical datasets from HTTPS Ecosystem and Rapid7 Project Sonar. Figure 3.9 shows a significant difference in the keys coming from such certificates. Most notably Microsoft keys are found in self-signed certificates less commonly than OpenSSL keys. As explained in Section 3.4.2, the decrease in the number of certificates between 11/2013 to 06/2015 is caused by an improper implementation of the TLS vl.2 handshake used by Project Sonar. 3.7 Conclusions A wide-scale accurate measurement of the popularity of cryptographic libraries is an important precursor for a security analysis of the Internet ecosystem, such as an evaluation of resilience against security bugs. Yet so far, it was based only on proxy measurements, like the popularity of web server implementations. We proposed a measurement method based on statistical inference, which finds a match between the observed distribution of keys on the Internet and a specific proportion of reference distributions of RSA public keys extracted from cryptographic libraries. Our method does not rely on active communication with a server implementation, hence it also works when proxy information is not available, such as for SSH client keys, where direct scanning of clients is not performed. The analysis is possible thanks to the recently discovered biases in the implementations of RSA public key generation [Sve+16a]. 42 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES The results show an overall increasing reliance on OpenSSL - its share grew from 56% to 70% between the years 2010 and 2017 as observed from keys used by TLS servers. The prevalence of OpenSSL reaches almost 85% within the current Alexa top 1 M domains and more than 96% for client-side SSH keys as used by GitHub users. The usage trends of Microsoft libraries are mostly stable with a share of around 20% for TLS serves and a 10% share of the Alexa top 1M domains. The GnuPG Libgcrypt library and statistically similar implementations are responsible for 85% of all PGP keys. Certificate Transparency logs provide a different ratio of libraries for recently added certificates than Internet-wide scans - OpenSSL is down to 60%, Microsoft is at only 3.5% (probably due to longer validity of certificates) and the remaining libraries account for more than 35% (while their share in IPv4 TLS scans is lower than 10%). This method can also capture short-term events, when incremental datasets are examined (e.g., daily changes). We observed that many certificates from specific libraries were submitted to Certificate Transparency logs periodically, coinciding with the validity of Let's Encrypt certificates. Our measurement also revealed an inconsistency between historical datasets, caused by a bug in the scanning software of Project Sonar, which led to an omission of more than a million Microsoft servers from IPv4 TLS scans during the period of 18 months. 43 3. MEASURING POPULARITY OF CRYPTOGRAPHIC LIBRARIES 0.3M 0.2M - 0.2M 01 I 0.1M 0.1M 0.1M • • i r - " t t " " " t r - T * t T i T T S t * T t i r t t ^ T 1 1 1 N> tC* o v a ' a * ^ o° cy> v \ V o 1 , o° c r T 1 1 1 1 1 1 1 1 1 1 1 1 1 1