Project Topics
Get Complete Project Material File(s) Now! »
Inside the Cloud: Random Number Generation
ntroduction
Randomness is one of the fundamental requirements in cryptography. It is required in most of the fundamental tasks such as encryption, key generation, nonces, random paddings, salts, generation of initialization vectors among several others. The security of these cryptographic algorithms and protocols relies on a source of unbiased and uniformly distributed random bits. Unfortunately, generating random numbers is not that easy as it seems. Von Neumann [VNT61] said Any one who considers arithmetical methods
of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number referring to the fact that it is fundamentally impossible to produce truly random numbers on any deterministic device. In the purest sense of the word, the best we can hope for are pseudo-random numbers which in practice they are generally sufficient even for demanding security-critical applications.
Nevertheless, in practice it is possible to produce unpredictable bits using an algorithm called Pseudo Random Number Generation (PRNG) which accumulates entropy from the environment and outputs pseudorandom strings indistinguishable from the uniform distribution to a computationally-bounded adversary. A typical assumption at the moment of design a PRNG is that the PRNG has an internal memory in which it is possible to store information and access it to produce the output. This memory is called internal state S and it remains secret to the adversary. However, in practice, keeping a piece of memory secret might not be that easy as it is believed. The internal state can be partially compromised through memory corruption attacks such as buffer overflows or fault attacks.
Attacking the internal state is a particularly sensitive topic in a cloud setting, where the hardware is usually outsourced and the PRNG could be running on a virtualized environment. This means that the cloud provider or another user of the server could have access to the whole memory [RTSS09, IIES14], contradicting one of the PRNG design fundamental: The adversary cannot have access to the memory. Different examples of memory attacks are presented in [Erl07] and in [vdVdSCB12].
An implementation error in the software might also help an attacker to learn something secret of the memory like was the case of the CVE-2014-0160 known as Heartbleed bug [Hea14] that affected one of the most used cryptographic libraries: OpenSSL. An attacker could get access to content of the server or client memory by crafting a TLS or DTLS heartbeat packet. Although the attacker can control the size of the compromised memory, it can not control its location, therefore it might have a total or partial access to sensitive information as the internal state of the PRNG.
Currently there are many PRNG implementations from different vendors, and most of them rely on internal directives and parameters that are poorly documented or even undocumented. In most implementations, a PRNG contains a dedicated internal state S which is refreshed periodically with the entropy I collected from its environment (such as network input/output, inter-interrupt timings from some interrupts, inter-keyboard timings, processor clock cycles) and secondly used to compute pseudorandom strings. The entropy collection is a hard problem and it takes much more time than the generating an output. In order to have a constant output of random strings, PRNGs typically maintains an internal state, which is the most critical part of the PRNG and therefore needs to be kept secure during its update.
Related Work
Random number generation does not steal the spotlight of design cryptographic primi-tives and protocols and yet it might be equally important in order to keep the security of algorithms and protocols. After the guidelines for developing PRNGs of Kelsey et al. [KSWH98] and Gutmann [Gut98] not that many implementations have been analyzed.
Theoretical cryptographers also have done some reserach in the area of PRNGs. The first work in the field was presented by Desai et al. [DHY02] in which they modeled a PRNG as a pair of algorithms: the Seed Generation algorithm and the Output Generation algorithm. This model assumes the existence of an entropy pool, different from the internal state, in which randomness is accumulated and it is used to refresh the internal state of the PRNG. An elegant and remarkable work of Barak and Halevi presented in [BH05] modeled a PRNG as a pair of algorithms (refresh and next) based on the design guidelines of Kelsey. Barak and Halevi defined a new security property called robustness that assesses the behavior of a PRNG after its internal state was compromised, but it fails to capture gradual entropy accumulation present in most real-life implementations.
A follow-up paper by Dodis et al. [DPR+13] identified the problem of this slow (and potentially malicious) entropy accumulation and refined the robustness property of a PRNG defined by Barak and Halevi. This new property, still named robustness, captures the idea of how the entropy of the input data should be accumulated in the internal state after a state compromise. A recent work of Dodis et al. [DSSW14] extends the robustness model to address the premature next attack where the internal state has insufficient entropy and an output is generated. To our knowledge, this last security model is the strongest one as it considers the most powerful attacker against a PRNG.
Our work complements the security model of [DPR+13] but in a different way than [DSSW14] does. Inspired on the work of Akavia, Goldwasser and Vaikuntanathan [AGV09], we consider the situation where an attacker can access partially to the memory of the PRNG. Hence we propose a new attacker profile that captures real-life situations where a partial internal state corruption is possible. We also show an analysis of real-life PRNGs using this security model and we demonstrate how it can help to identify new vulnerabilities. In particular, we show that a full internal state corruption is not necessary to compromise a PRNG, instead only a partial one may be sufficient. We characterize how a PRNG can be attacked in order to produce a predictable and we identify how many bits of the internal state are required to mount an attack against the PRNG.
Preliminaries
Other Randomness Weaknesses. Several recent attacks occurred due to an insuffi-cient understanding of PRNG implementations. Michaelis et al. in [MMS13] described and analyzed several PRNG libraries written in Java and they their weaknesses. One striking example is the failure in the Debian Linux distribution, where a commented line of code in the OpenSSL PRNG forced the only source of entropy to be the Process Identifier (PID). An analysis and an attack that breaks the forward-security of Linux PRNGs dev/random and dev/urandom was done in 2006 by Gutterman et al. in [GPR06]. In 2013 Dodis et al. [DPR+ 13] presents an attacks against these PRNG, but related to their internal entropy estimator. Heninger et al. in [HDWH12] presented an analysis of Linux’s PRNG that at boot time the some SSH and TLS keys are generated with insufficient entropy. The Windows PRNG CryptGenRandom was analyzed in 2006 by Dorrendorf et al. in [DGP09] where the authors showed an attack on the forward security of the PRNG implemented in Windows 2000, for which a fix has been published. Argyros and Kiayias in [AK12] presented some practical techniques and algorithms for exploiting randomness vulnerabilities in PHP. More recently, a flaw in the Android PRNG, identified by Kim et al. [KHL13], has been actively exploited against Android-based Bitcoin wallets.
Roadmap
First, we give a formal definition of a PRNG in Section 3.2. Using recent theoretical results in the field, we provide in this work a new security model and we present it as a framework in Section 3.3. We use this framework in Section 3.4 for the analysis of widely used PRNGs and we identify new potential vulnerabilities due to the way they handle their internal state during its update step. Finally in Section 3.4.6 we give a secure implementation using our new framework.
Preliminaries
In this section we describe our notation and definitions used, adapted from the work of Dodis et al. [DPR+13].
Table of contents :
1 Introduction
1.1 This Work
1.2 Contributions
2 Preliminaries
2.1 Random Variable
2.2 Probability Distribution
2.3 Indistinguishability
2.4 Symmetric Cryptography
2.5 Asymmetric Cryptography
2.6 Game Playing Framework
3 Inside the Cloud: Random Number Generation
3.1 Introduction
3.2 Preliminaries
3.3 PRNG Security
3.4 Security of Real-Life PRNGs
3.5 Memory Corruption
3.6 Conclusion
4 Using the Cloud: Key Management
4.1 Introduction
4.2 Preliminaries
4.3 Security Model
4.4 A Robust Gap Threshold Secret Sharing Scheme
4.5 Password-Protected Secret Sharing Protocol
4.6 Comparisons
5 Storing in the Cloud: Searchable Encryption
5.1 Introduction
5.2 Preliminaries
5.3 Building Blocks
5.4 SSE Security Definitions
5.5 A Composite SSE Scheme Supporting Boolean Queries
5.6 CXT Instantiations
5.7 Implementation and Evaluation
6 Conclusion
