International Association
for Cryptologic Research

In this paper, we study both the implications and potential impact of backdoored parameters for two RSA-based pseudorandom number generators: the ISO-standardized Micali-Schnorr generator and a closely related design, the RSA PRG. We observe, contrary to common understanding, that the security of the Micali-Schnorr PRG is not tightly bound to the difficulty of inverting RSA. We show that the Micali-Schnorr construction remains secure even if one replaces RSA with a publicly evaluatable PRG, or a function modeled as an efficiently invertible random permutation. This implies that any cryptographic backdoor must somehow exploit the algebraic structure of RSA, rather than an attacker’s ability to invert RSA or the presence of secret keys. We exhibit two such backdoors in related constructions: a family of exploitable parameters for the RSA PRG, and a second vulnerable construction for a finite-field variant of Micali-Schnorr. We also observe that the parameters allowed by the ISO standard are incompletely specified, and allow insecure choices of exponent. Several of our backdoor constructions make use of lattice techniques, in particular multivariate versions of Coppersmith’s method for finding small solutions to polynomials modulo integers.

Users increasingly store their data in the cloud, thereby benefiting from easy access, sharing, and redundancy. To additionally guarantee security of the outsourced data even against a server compromise, some service providers have started to offer end-to-end encrypted (E2EE) cloud storage. With this cryptographic protection, only legitimate owners can read or modify the data. However, recent attacks on the largest E2EE providers have highlighted the lack of solid foundations for this emerging type of service. In this paper, we address this shortcoming by initiating the formal study of E2EE cloud storage. We give a formal syntax to capture the core functionality of a cloud storage system, capturing the real-world complexity of such a system’s constituent interactive protocols. We then define game-based security notions for confidentiality and integrity of a cloud storage system against a fully malicious server. We treat both selective and fully adaptive client compromises. Our notions are informed by recent attacks on E2EE cloud storage providers. In particular we show that our syntax is rich enough to capture the core functionality of MEGA and that recent attacks on it arise as violations of our security notions. Finally, we present an E2EE cloud storage system that provides all core functionalities and that is both efficient and provably secure with respect to our selective security notions. Along the way, we discuss challenges on the path towards bringing the security of cloud storage up to par with other end-to-end primitives, such as secure messaging and TLS.

We consider a transform, called Derive-then-Derandomize, that hardens a given signature scheme against randomness failure and implementation error. We prove that it works. We then give a general lemma showing indifferentiability of a class of constructions that apply a shrinking output transform to an MD-style hash function. Armed with these tools, we give new proofs for the widely standardized and used $\EdDSA$ signature scheme, improving prior work in two ways: (1) we give proofs for the case that the hash function is an MD-style one, reflecting the use of SHA512 in the NIST standard, and (2) we improve the tightness of the reduction so that one has guarantees for group sizes in actual use.

Dual EC DRBG is widely believed to have been backdoored by the U.S. National Security Agency. But there was another number theoretic PRG proposed alongside Dual EC that has seen surprisingly little attention: the Micali-Schnorr generator, standardized as MS DRBG, which is based on the hardness of RSA. It appears in early drafts of the ANSI X9.82 standard (but was eventually removed in favor of Dual EC) and the final version of ISO 18031 (alongside Dual EC). The MS DRBG standard follows a pattern eerily reminiscent of Dual EC: it incorporates a series of recommended public parameters that are intended to be used in production as the RSA modulus N. Given the known vulnerabilities in Dual EC and the identical provenance, it is reasonable to ask whether MS DRBG is vulnerable to an analogous attack: Does knowledge of the factors of (or malicious construction of) the recommended moduli imply a practical attack on the MS DRBG generator? Surprisingly, this question is not easy to answer. The security proofs of course do not go through if the factors are known, but all obvious attack strategies fail. In this talk, we give historical background on MS DRBG and describe progress toward finding the backdoor (or proving it doesn't exist). We show that any backdoor must somehow exploit the algebraic structure of RSA, rather than just the attacker's ability to invert the RSA operation. We exhibit two such backdoors in related constructions. Ultimately we were unsuccessful in fully finding a plausible backdoor in MS DRBG (or proving one doesn't exist), but we hope this talk will bring more attention to this interesting open problem with potential real-world impact.

Established security bounds for the TLS 1.3 full (1-RTT) and pre-shared key (PSK) handshake protocols grow quadratically with the total number of handshakes across all users. Due to the pervasive use of TLS, these bounds are so loose that they give no guarantees for the standardized parameters used in practice. We give new proofs and concrete bounds that justify the use of these parameters both in principle and in practice. We also discuss the pitfalls that arise when trying to capture the TLS 1.3 key schedule within the random oracle model.

Much of public key cryptography is designed in the Random Oracle Model, which assumes parties have access to one or more independent random functions. Implementing these random functions securely, usually via a cryptographic hash function, critically requires a technique called domain separation. This talk is about how spectacularly wrong things can go when domain separation is not done right, and simple ways to do it right. We begin with a case study on random oracle implementation in the NIST PQC KEM standardization effort, giving attacks arising from poor domain separation on some submissions, and classifying the remaining submissions from dubious to good. We then give a library of proof-validated domain separations that are secure, easy to implement, and usable in any type of cryptographic protocol, not just PQC KEMs.

It is convenient and common for schemes in the random oracle model to assume access to multiple random oracles (ROs), leaving to implementations the task --we call it oracle cloning-- of constructing them from a single RO. The first part of the paper is a case study of oracle cloning in KEM submissions to the NIST Post-Quantum Cryptography standardization process. We give key-recovery attacks on some submissions arising from mistakes in oracle cloning, and find other submissions using oracle cloning methods whose validity is unclear. Motivated by this, the second part of the paper gives a theoretical treatment of oracle cloning. We give a definition of what is an "oracle cloning method" and what it means for such a method to "work," in a framework we call read-only indifferentiability, a simple variant of classical indifferentiability that yields security not only for usage in single-stage games but also in multi-stage ones. We formalize domain separation, and specify and study many oracle cloning methods, including common domain-separating ones, giving some general results to justify (prove read-only indifferentiability of) certain classes of methods. We are not only able to validate the oracle cloning methods used in many of the unbroken NIST PQC KEMs, but also able to specify and validate oracle cloning methods that may be useful beyond that.