Project topics and materials
Get Complete Project Material File(s) Now! »
Contributions
Characterization of Real-Life PRNGs under Partial State Corruption
From a theoretical viewpoint, we formally extend the security model of [DPR+13], to capture the behavior of a PRNG against an attacker that has partial access to its internal state. From a practical side, we characterize and give a new security analysis of PRNG implementations from widely used providers in real-life applications: OpenSSL, OpenJDK, Android, Bouncycastle and IBM. To our knowledge, while intensively used in practice, these PRNGs have not been evaluated w.r.t. recent security models. Our analysis reveals new vulnerabilities of these PRNG due to the implementation of their internal state in several fields that are not updated securely during PRNG operations. Our results are summarized in Table 1.1. In this table, we give the size in bits of the internal state of the PRNG and the number of bits (named λ) that an attacker needs to compromise in order to mount an attack against the PRNG.
Robust Password-Protected Secret Sharing
Our PPSS protocol follows the methodology from [JKK14]: it is based on the use of pseudorandom functions (PRFs) evaluated on the password to mask the shares of the secret. These evaluations are performed with servers that own the PRF keys, in an oblivious way, hence the so-called oblivious pseudorandom functions (OPRFs).
Our main contribution is the efficient realization of the robustness, that consists in a single check at the very end of the protocol, during the secret reconstruction. We point out that, in order to achieve robustness in a PPSS protocol, one does not need to distinguish between correct and incorrect shares at each individual evaluation with a server like in the verifying setting presented in [JKK14].
Actually, we propose a new efficient method to convert any Secret Sharing Scheme in a (t`, tr, n)-Robust Gap Threshold Secret Sharing Scheme (RGTSSS) that guarantees to efficiently identify the correct values (and reconstruct the secret) if at least tr shares are correct. However, if at most t` shares are correct, the protocol leaks no information about which shares are correct.
More precisely, we are using an encoding to generate fingerprints of the shares. The assumption that invalid shares encode into random fingerprints is enough for the reconstruction technique to be able to select the correct shares, when their number is high enough. This can be achieved using a hash function modeled as a random oracle [BR93].
Such a (t`, tr, n)-RGTSSS allows the user to execute the PPSS protocol in a robust way. If the number of correct servers’ answers is above the threshold tr, the user can efficiently identify the valid ones and reconstruct the secret. If the number of answers is below another threshold t`, no information about the secret is leaked. It is indeed important that not too few correct shares can be detected as correct as this could result in offline dictionary attacks. For instance, in the case where shares could be individually checked, a dishonest server could easily mount an offline dictionary attack. With our new primitive, even t` corrupted servers cannot perform an offline dictionary attack as they would still need to interact with at least one additional server. The main difference to [JKK14] is in the way to achieve robustness: We ask a bit more from the secret sharing scheme, but much less from the OPRF, allowing more efficient constructions for the latter, which highly improves on the global efficiency.
While similar to [JKKX16] in terms of server interaction efficiency, our technique takes advantage of the RGTSSS to optimize the secret reconstruction. The scheme proposed by [JKKX16] has one significant drawback: the client is supposed to specify the exact set of servers involved in the secret recovery from the beginning, which may lead to frequent failures as the servers may misbehave. Moreover, in case of such a failure, the user is unable to detect the cheating servers. To overcome this drawback when a large number of servers are involved in the protocol, our approach makes use of the robustness feature, to ensure the recovery of the secret and the detection of dishonest servers.
We propose two efficient OPRF constructions: The first one is based on the One-More Gap Diffie-Hellman assumption and its efficiency is quite similar to the one in [JKKX16]. Secondly, we introduce a new oblivious evaluation of the Naor-Reingold PRF [NR97], based on the sole DDH assumption. This new construction compares very favorably to other oblivious evaluations of the Naor-Reingold PRF: our protocol simply uses ElGamal encryption [ElG85] in prime order groups with simple zero-knowledge proofs, whereas for example the scheme in [JKK14] has to work in composite order groups with Paillier encryption [Pai99] and more complex zero-knowledge proofs.
By combining these building bricks, we eventually reach efficient PPSS schemes that satisfy Soundness and Robustness properties. The two proposed solutions are eventually proven in the Random Oracle Model (ROM) [BR93], as our RGTSSS construction requires random non-malleable fingerprints. This can be achieved by using a hash function that is modeled as a random oracle.
Verifiable Symmetric Searchable Encryption with Boolean Queries and Controlled Leakage
We present the CXT (for Composite Cross Tag) verifiable, dynamic, and multiple-keyword SSE scheme. Our SSE solution is inspired from Cash et al. [CJJ+13] OXT scheme, using a Single Keyword Search (SKS) scheme for the least frequent keyword with a cross matching protocol for the other keywords. However, we add verification mechanisms for both components. We thus build CXT from a verifiable SKS and a verifiable data structure allowing to test and verify membership queries.
We give a formal proof of this generic construction and we also give two instantiations of CXT : the first being very simple and efficient, and the second one being based on ORAM-related components, and only leaking a very small amount of information. In particular, this second instantiation is forward secure.
We present an open source implementation of the simple instantiation and show that our approach is practical.
Preliminaries
In this section we introduce briefly the basic ideas of probability and cryptography theory.
For a complete definition we refer to [HPS08].
Random Variable.
A random variable, usually written X , is a function X : Ω → R whose domain is the sample space Ω and the possible values are numerical outcomes in R of a random phenomenon. Random variables are useful for defining events. For example if X is a random variable then, for example, we can define the following event: {ω ∈ Ω : X(ω) ≤ x}.
Probability Distribution.
Let X : Ω → R be a random variable. The probability distribution function of X denoted by PX is defined to be: PX (x) = Pr(X = x) and it can be seen as PX being the probability that X takes on the value x. By x ←$ X we mean that x is sampled according to the distribution of the random variable X.
Indistinguishability.
The notion of computational indistinguishability is central to the theory of cryptog-raphy. Informally speaking, two probability distributions are computationally indis-tinguishable if no efficient algorithm can tell them apart (or distinguish them). For-mally, two distributions X and Y are said to be (t, ε)-computationally indistinguishable, (which we denote CDt(X, Y ) ≤ ε), if for any distinguisher A running within time t, Pr[A(X) = 1] − Pr[A(Y ) = 1] ≤ ε. When t = ∞, meaning A is unbounded, we say that X and Y are ε-close, and their statistical distance is at most ε: SD(X, Y ) ≤ ε.
Symmetric Cryptography.
Symmetric cryptography (also called private-key cryptography), is a setting where two parties share some secret information called a key, and use this key when they wish to communicate secretly with each other. An implicit assumption in any system using rivate-key encryption is that the communicating parties have some way of initially sharing a key in a secret manner. Two users share a secret key K to communicate confidentially. Each user encrypts the message he wants to send to the other user, using the key K; and the other user decrypts the received encrypted message (a.k.a., ciphertext) to get the original message back, using the same key K. Anybody who intercepts the ciphertext should not be able to learn anything about the original message, without knowledge of the secret key K. Formally defined:
Definition 2.1. A private-key encryption scheme is comprised of three algorithms:
• The key-generation algorithm Gen is a probabilistic algorithm that outputs a key k chosen according to some distribution that is determined by the scheme.
• The encryption algorithm algorithm Enc takes as input a key k and a plaintext m and outputs a ciphertext c. We denote the encryption of the plaintext m using the key k by Enck(m).
• The decryption algorithm Dec takes as input a key k and a ciphertext c and outputs a plaintext m. We denote the decryption of the ciphertext c using the key k by Deck(c).
The basic correctness requirement of any encryption scheme is:
• For every key k output by Gen and every plaintext m in the appropriate underlying plaintext space, it holds that: Deck(Enck(m)) = m.
Asymmetric Cryptography.
In contrast to symmetric cryptography, in asymmetric cryptography (also called public-key cryptography) the two parties do not share the same secret key K but they use two different keys, a public key (PK) and a secret key (SK). An important property is that given the public key it is infeasible to forge the secret key. In this scheme, the receiver sends his public key to the sender over an insecure channel, who then encrypts the plaintext using that key and transmits the resulting ciphertext. Finally, the receiver can decrypt the ciphertext using his secret key. In Public Key Cryptosystems both users exchange their public keys publicly to encrypt a plaintext that can be decrypted only with the secret key associated with each public key. By publicly revealing PK one does not reveal an easy way to compute SK.
The definition of public-key encryptions is as follows:
Definition 2.2. A public-key encryption scheme is defined by a tuple of probabilistic, polynomial-time algorithms (Gen, Enc, Dec) that satisfies the following:
• Algorithm Gen takes as input a security parameter 1n and outputs a pair of keys (pk, sk). We refer to the first of these as the public key and the second as the secret key.
• Algorithm Enc takes as input a public key pk and a message m from some underlying plaintext space. It outputs a ciphertext c, and we write this as c ← Encpk(m).
• Algorithm Dec takes as input a private key sk and a ciphertext c and outputs a message m or a special symbol ⊥, and we write this as m ← Decsk(m).
It should satisfy the following property:
• For every n, every (pk, sk) pair output by Gen(1n), and every message m in the appropriate underlying plaintext space, it holds that: Decsk(Encpk(m)) = m.
Game Playing Framework.
Most of our security proofs are proofs by games (also called hybrid arguments) as defined by Shoup in [Sho01, KR01, BR06]. The idea is to define an attack game with procedures to respond to adversary oracle queries, then to prove security using the sequence-of-games as follows: The first game G0 is the original attack game with respect to a given adversary and cryptographic primitive corresponding to some security notion. The last game Gn corresponds to some security notion or is such that the adversary just cannot win. The general framework is that the probability of some event Si defined in the game Gi is very close or negligibly close to the probability of the event Si+1. In other words, we prove that two consecutive games are indistinguishable either perfectly, statistically, or computationally. In constructing such proofs, it is desirable that the changes between successive games are very small, so that analyzing the change is as simple as possible.
Inside the Cloud: Random Number Generation
Introduction
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 eartbeat 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.
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
Bibliography
