Search

Roughly four decades ago, Taher ElGamal put forward what is today one of the most widely known and best understood public key encryption schemes. ElGamal encryption has been used in many different contexts, chiefly among them by the OpenPGP email encryption standard. Despite its simplicity, or perhaps because of it, in reality there is a large degree of ambiguity on several key aspects of the cipher. Each library in the OpenPGP ecosystem seems to have implemented a slightly different "flavor" of ElGamal encryption. While-taken in isolation-each implementation may be secure, we reveal that in the interoperable world of OpenPGP, unforeseen cross-configuration attacks become possible. Concretely, we propose different such attacks and show their practical efficacy by recovering plaintexts and even secret keys.

We put forward a symmetric encryption primitive tailored towards a specific application: outsourced storage. The setting assumes a memory-bounded computing device that inflates the amount of volatile or permanent memory available to it by letting other (untrusted) devices hold encryptions of information that they return on request. For instance, web servers typically hold for each of the client connections they manage a multitude of data, ranging from user preferences to technical information like database credentials. If the amount of data per session is considerable, busy servers sooner or later run out of memory. One admissible solution to this is to let the server encrypt the session data to itself and to let the client store the ciphertext, with the agreement that the client reproduce the ciphertext in each subsequent request (e.g., via a cookie) so that the session data can be recovered when required. In this article we develop the cryptographic mechanism that should be used to achieve confidential and authentic data storage in the encrypt-to-self setting, i.e., where encryptor and decryptor coincide and constitute the only entity holding keys. We argue that standard authenticated encryption represents only a suboptimal solution for preserving confidentiality, as much as message authentication codes are suboptimal for preserving authenticity. The crucial observation is that such schemes instantaneously give up on all security promises the moment the key is compromised. In contrast, data protected with our new primitive remains fully integrity protected and unmalleable. In the course of this paper we develop a formal model for encrypt-to-self systems, show that it solves the outsourced storage problem, propose surprisingly efficient provably secure constructions, and report on our implementations.

A popular cryptographic option to implement Hierarchical Access Control in organizations is to combine a key assignment scheme with a symmetric encryption scheme. In brief, key assignment associates with each object in the hierarchy a unique symmetric key, and provides all higher-ranked “authorized” subjects with a method to recover it. This setup allows for encrypting the payloads associated with the objects so that they can be accessed by the authorized and remain inaccessible for the unauthorized. Both key assignment and symmetric encryption have been researched for roughly four decades now, and a plethora of efficient constructions have been the result. Surprisingly, a treatment of the joint primitive (key assignment combined with encryption, as used in practice) in the framework of provable security was conducted only very recently, leading to a publication in ToSC 2018(4). We first carefully revisit this publication. We then argue that there are actually two standard use cases for the combined primitive, which also require individual treatment. We correspondingly propose a fresh set of security models and provably secure constructions for each of them. Perhaps surprisingly, the two constructions call for different symmetric encryption primitives: While standard AEAD is the right tool for the one, we identify a less common tool called Encryptment as best fitting the other., IACR Transactions on Symmetric Cryptology, Volume 2020, Issue 2

Recent work by Pijnenburg and Poettering (ESORICS'20) explores the novel cryptographic Encrypt-to-Self primitive that is dedicated to use cases of symmetric encryption where encryptor and decryptor coincide. The primitive is envisioned to be useful whenever a memory-bounded computing device is required to encrypt some data with the aim of temporarily depositing it on an untrusted storage device. While the new primitive protects the confidentiality of payloads as much as classic authenticated encryption primitives would do, it provides considerably better authenticity guarantees: Specifically, while classic solutions would completely fail in a context involving user corruptions, if an encrypt-to-self scheme is used to protect the data, all ciphertexts and messages fully remain unforgeable. To instantiate their encrypt-to-self primitive, Pijnenburg et al propose a mode of operation of the compression function of a hash function, with a carefully designed encoding function playing the central role in the serialization of the processed message and associated data. In the present work we revisit the design of this encoding function. Without questioning its adequacy for securely accomplishing the encrypt-to-self job, we improve on it from a technical/implementational perspective by proposing modifications that alleviate certain conditions that would inevitably require implementations to disrespect memory alignment restrictions imposed by the word-wise operation of modern CPUs, ultimately leading to performance penalties. Our main contributions are thus to propose an improved encoding function, to explain why it offers better performance, and to prove that it provides as much security as its predecessor. We finally report on our open-source implementation of the encrypt-to-self primitive based on the new encoding function., Comment: this is the full version of content that appears at CYSARM'20

Digital signatures guarantee practical security only if the corresponding verification keys are distributed authentically; however, arguably, satisfying solutions for the latter have not been found yet. This paper introduces a novel approach for cryptographic message authentication where this problem does not arise: A linkable message tagging scheme (LMT) identifies pairs of messages and accompanying authentication tags as related if and only if these tags were created using the same secret key. Importantly, our primitive fully avoids public keys and hence elegantly sidesteps the key distribution problem of signature schemes. As an application of LMT we envision an email authentication system with minimal user interaction. Email clients could routinely equip all outgoing messages with corresponding tags and verify for incoming messages whether they indeed originate from the same entity as previously or subsequently received messages with identical sender address. As technical contributions we formalize the notions of LMT and its (more efficient) variant CMT (classifiable message tagging), including corresponding notions of unforgeability. For both variants we propose a range of provably secure constructions, basing on different hardness assumptions, with and without requiring random oracles. This article extends prior work of the same authors that appeared in the proceedings of ACISP 2015 (Gunther and Poettering in 2015).

This work introduces a new class of Algorithm Substitution Attack (ASA) on Symmetric Encryption Schemes. ASAs were introduced by Bellare, Paterson and Rogaway in light of revelations concerning mass surveillance. An ASA replaces an encryption scheme with a subverted version that aims to reveal information to an adversary engaged in mass surveillance, while remaining undetected by users. Previous work posited that a particular class of AEAD scheme (satisfying certain correctness and uniqueness properties) is resilient against subversion. Many if not all real-world constructions – such as GCM, CCM and OCB – are members of this class. Our results stand in opposition to those prior results. We present a potent ASA that generically applies to any AEAD scheme, is undetectable in all previous frameworks and which achieves successful exfiltration of user keys. We give even more efficient non-generic attacks against a selection of AEAD implementations that are most used in practice. In contrast to prior work, our new class of attack targets the decryption algorithm rather than encryption. We argue that this attack represents an attractive opportunity for a mass surveillance adversary. Our work serves to refine the ASA model and contributes to a series of papers that raises awareness and understanding about what is possible with ASAs.

Lossy trapdoor functions (Peikert and Waters, STOC 2008 and SIAM J. Computing 2011) imply, via black-box transformations, a number of interesting cryptographic primitives, including chosen-ciphertext secure public-key encryption. Kiltz, O’Neill, and Smith (CRYPTO 2010) showed that the RSA trapdoor permutation is lossy under the Phi-hiding assumption, but syntactically it is not a lossy trapdoor function since it acts on \(\mathbb {Z}_N\) and not on strings. Using a domain extension technique by Freeman et al. (PKC 2010 and J. Cryptology 2013) it can be extended to a lossy trapdoor permutation, but with considerably reduced lossiness.

Cryptographic channels aim to enable authenticated and confidential communication over the Internet. The general understanding seems to be that providing security in the sense of authenticated encryption for every (unidirectional) point-to-point link suffices to achieve this goal. As recently shown (in FSE17/ToSC17), however, the security properties of the unidirectional links do not extend, in general, to the bidirectional channel as a whole. Intuitively, the reason for this is that the increased interaction in bidirectional communication can be exploited by an adversary. The same applies, a fortiori, in a multi-party setting where several users operate concurrently and the communication develops in more directions. In the cryptographic literature, however, the targeted goals for group communication in terms of channel security are still unexplored. Applying the methodology of provable security, we fill this gap by defining exact (game-based) authenticity and confidentiality goals for broadcast communication, and showing how to achieve them. Importantly, our security notions also account for the causal dependencies between exchanged messages, thus naturally extending the bidirectional case where causal relationships are automatically captured by preserving the sending order. On the constructive side we propose a modular and yet efficient protocol that, assuming only point-to-point links between users, leverages (non-cryptographic) broadcast and standard cryptographic primitives to a full-fledged broadcast channel that provably meets the security notions we put forth.

Digital signatures are often used by trusted authorities to make unique bindings between a subject and a digital object; for example, certificate authorities certify a public key belongs to a domain name, and time-stamping authorities certify that a certain piece of information existed at a certain time. Traditional digital signature schemes however impose no uniqueness conditions, so a trusted authority could make multiple certifications for the same subject but different objects, be it intentionally, by accident, or following a (legal or illegal) coercion. We propose the notion of a double-authentication-preventing signature, in which a value to be signed is split into two parts: a subject and a message. If a signer ever signs two different messages for the same subject, enough information is revealed to allow anyone to compute valid signatures on behalf of the signer. This double-signature forgeability property discourages signers from misbehaving--a form of self-enforcement--and would give binding authorities like CAs some cryptographic arguments to resist legal coercion. We give a generic construction using a new type of trapdoor functions with extractability properties, which we show can be instantiated using the group of sign-agnostic quadratic residues modulo a Blum integer; we show an additional application of these new extractable trapdoor functions to standard digital signatures.

Ratcheted key exchange (RKE) is a cryptographic technique used in instant messaging systems like Signal and the WhatsApp messenger for attaining strong security in the face of state exposure attacks. RKE received academic attention in the recent works of Cohn-Gordon et al. (EuroS&P 2017) and Bellare et al. (CRYPTO 2017). While the former is analytical in the sense that it aims primarily at assessing the security that one particular protocol does achieve (which might be weaker than the notion that it should achieve), the authors of the latter develop and instantiate a notion of security from scratch, independently of existing implementations. Unfortunately, however, their model is quite restricted, e.g. for considering only unidirectional communication and the exposure of only one of the two parties.

This paper contributes to understanding the interplay of security notions for PKE, KEMs, and DEMs, in settings with multiple users, challenges, and instances. We start analytically by first studying (a) the tightness aspects of the standard hybrid KEM+DEM encryption paradigm, (b) the inherent weak security properties of all deterministic DEMs due to generic key-collision attacks in the multi-instance setting, and (c) the negative effect of deterministic DEMs on the security of hybrid encryption.

In many applications where encrypted traffic flows from an open public domain to a protected private domain there exists a gateway that bridges these two worlds, faithfully forwarding all incoming traffic to the receiver. We observe that the notion of indistinguishability against adaptive chosen-ciphertext attacks IND-CCA2, which is a mandatory goal in face of active attacks in a public domain, can be relaxed to indistinguishability against chosen-plaintext attacks IND-CPA once the ciphertexts passed the gateway. The latter then acts as an IND-CCA2/CPA filter by first checking the validity of an incoming IND-CCA2-secure ciphertext, transforming it if valid into an IND-CPA-secure ciphertext, and finally forwarding it to the recipient in the private domain. Non-trivial filtering can result in reduced decryption costs on the recipient's side.We identify a class of encryption schemes with publicly verifiable ciphertexts that admit generic constructions of IND-CCA2/CPA filters with non-trivial verification. These schemes are characterized by existence of public algorithms that can distinguish ultimately between valid and invalid ciphertexts. To this end, we formally define public verifiability of ciphertexts for general encryption schemes, key encapsulation mechanisms and hybrid encryption schemes, encompassing public-key, identity-based and tag-based encryption flavours. We further analyze the security impact of public verifiability and discuss generic transformations and concrete constructions that enjoy this property.

In the realm of public-key encryption, the confidentiality notion of security against selective opening SO attacks considers adversaries that obtain challenge ciphertexts and are allowed to adaptively open them, meaning have the corresponding message and randomness revealed. SOi¾?security is stronger than IND-CCA and often required when formally arguing towards the security of multi-user applications. While different ways of achieving SO secure schemes are known, as they generally employ expensive asymmetric building blocks like lossy trapdoor functions or lossy encryption, such constructions are routinely left aside by practitioners and standardization bodies. So far, formal arguments towards the SO security of schemes used in practice e.g., for email encryption are not known. In this work we shift the focus from the asymmetric to the symmetric building blocks of PKE and prove the following statement: If a PKE scheme is composed of a key encapsulation mechanism KEM and a blockcipher-based data encapsulation mechanism DEM, and the DEM has specific combinatorial properties, then the PKE scheme offers SO security in the ideal cipher model. Fortunately, as we show, the required properties hold for popular modes of operation like CTR, CBC and CCM. This paper not only establishes the corresponding theoretical framework of analysis, but also contributes very concretely to practical cryptography by concluding that selective opening security is given for many real-world schemes.

Cryptographic access control has been studied for over 30 years and is now a mature research topic. When symmetric cryptographic primitives are used, each protected resource is encrypted and only authorized users should have access to the encryption key. By treating the keys themselves as protected resources, it is possible to develop schemes in which authorized keys are derived from the keys explicitly assigned to the user's possession and publicly available information. It has been generally assumed that each user would be assigned a single key from which all other authorized keys would be derived. Recent work has challenged this assumption by developing schemes that do not require public information, the trade-off being that a user may require more than one key. However, these new schemes, which require a chain partition of the partially ordered set on which the access control policy is based, have some disadvantages. In this paper we define the notion of a tree-based cryptographic enforcement scheme, which, like chain-based schemes, requires no public information. We establish that the strong security properties of chain-based schemes are preserved by tree-based schemes, and provide an efficient construction for deriving a tree-based enforcement scheme from a given policy that minimizes the number of keys required., To appear in Proceedings of ACNS 2015

We conduct an analysis of the RC4 algorithm as it is used in the IEEE WPA/TKIP wireless standard. In that standard, RC4 keys are computed on a per-frame basis, with specific key bytes being set to known values that depend on 2 bytes of the WPA frame counter (called the TSC). We observe very large, TSC-dependent biases in the RC4 keystream when the algorithm is keyed according to the WPA specification. These biases permit us to mount an effective statistical, plaintext-recovering attack in the situation where the same plaintext is encrypted in many different frames (the so-called “broadcast attack” setting). We assess the practical impact of these attacks on WPA/TKIP.

Digital signatures guarantee practical security only if the corresponding verification keys are distributed authentically; however, arguably, satisfying solutions for the latter haven’t been found yet. This paper introduces a novel approach for cryptographic message authentication where this problem does not arise: A linkable message tagging scheme (LMT) identifies pairs of messages and accompanying authentication tags as related if and only if these tags were created using the same secret key. Importantly, our primitive fully avoids public keys, and hence elegantly sidesteps the key distribution problem of signature schemes.

At CRYPTO 2014 Bellare, Paterson, and Rogaway (BPR) presented a formal treatment of symmetric encryption in the light of algorithm substitution attacks (ASAs), which may be employed by ‘big brother’ entities for the scope of mass surveillance. Roughly speaking, in ASAs big brother may bias ciphertexts to establish a covert channel to leak vital cryptographic information. In this work, we identify a seemingly benign assumption implicit in BPR’s treatment and argue that it artificially (and severely) limits big brother’s capabilities. We then demonstrate the critical role that this assumption plays by showing that even a slight weakening of it renders the security notion completely unsatisfiable by any, possibly deterministic and/or stateful, symmetric encryption scheme. We propose a refined security model to address this shortcoming, and use it to restore the positive result of BPR, but caution that this defense does not stop most other forms of covert-channel attacks.

A variant of public key encryption that promises efficiency gains due to batch processing is multi-recipient public key encryption (MR-PKE). Precisely, in MR-PKE, a dedicated encryption routine takes a vector of messages and a vector of public keys and outputs a vector of ciphertexts, where the latter can be decrypted individually, as in regular PKE. In this paper we revisit the established security notions of MR-PKE and the related primitive MR-KEM. We identify a subtle flaw in a security model by Bellare, Boldyreva, and Staddon, that also appears in later publications by different authors. We further observe that these security models rely on the knowledge-of-secret-key (KOSK) assumption---a requirement that is rarely met in practice. We resolve this situation by proposing strengthened security notions for MR-PKE and MR-KEMs, together with correspondingly secure yet highly efficient schemes. Importantly, our models abstain from restricting the set of considered adversaries in the way prior models did, and in particular do not require the KOSK setting. We prove our constructions secure assuming hardness of the static Diffie-Hellman problem, in the random oracle model.

RC4 is (still) a very widely-used stream cipher. Previous work by AlFardan et al. (USENIX Security 2013) and Paterson et al. (FSE 2014) exploited the presence of biases in the RC4 keystreams to mount plaintext recovery attacks against TLS-RC4 and WPA/TKIP. We improve on the latter work by performing large-scale computations to obtain accurate estimates of the single-byte and double-byte distributions in the early portions of RC4 keystreams for the WPA/TKIP context and by then using these distributions in a novel variant of the previous plaintext recovery attacks. The distribution computations were conducted using the Amazon EC2 cloud computing infrastructure and involved the coordination of 213 hyper-threaded cores running in parallel over a period of several days. We report on our experiences of computing at this scale using commercial cloud services. We also study Microsoft’s Point-to-Point Encryption protocol and its use of RC4, showing that it is also vulnerable to our attack techniques.

Digital signatures are often used by trusted authorities to make unique bindings between a subject and a digital object; for example, certificate authorities certify a public key belongs to a domain name, and time-stamping authorities certify that a certain piece of information existed at a certain time. Traditional digital signature schemes however impose no uniqueness conditions, so a trusted authority could make multiple certifications for the same subject but different objects, be it intentionally, by accident, or following a (legal or illegal) coercion. We propose the notion of a double-authentication-preventing signature, in which a value to be signed is split into two parts: a subject and a message. If a signer ever signs two different messages for the same subject, enough information is revealed to allow anyone to compute valid signatures on behalf of the signer. This double-signature forgeability property discourages signers from misbehaving—a form of self-enforcement—and would give binding authorities like CAs some cryptographic arguments to resist legal coercion. We give a generic construction using a new type of trapdoor functions with extractability properties, which we show can be instantiated using the group of sign-agnostic quadratic residues modulo a Blum integer.

We develop a three-level hierarchy of privacy notions for (unforgeable) digital signature schemes. We first prove mutual independence of existing notions of anonymity and confidentiality, and then show that these are implied by higher privacy goals. The top notion in our hierarchy is pseudorandomness: signatures with this property hide the entire information about the signing process and cannot be recognized as signatures when transmitted over a public network. This implies very strong unlinkability guarantees across different signers and even different signing algorithms, and gives rise to new forms of private public-key authentication.We show that one way towards pseudorandom signatures leads over our mid-level notion, called indistinguishability: such signatures can be simulated using only the public parameters of the scheme. As we reveal, indistinguishable signatures exist in different cryptographic settings (e.g. based on RSA, discrete logarithms, pairings) and can be efficiently lifted to pseudorandomness deploying general transformations using appropriate encoding techniques. We also examine a more direct way for obtaining pseudorandomness for any unforgeable signature scheme. All our transformations work in the standard model. We keep public verifiability of signatures in the setting of system-wide known public keys. Some results even hold if signing keys are disclosed to the adversary --- given that signed messages have high entropy.

Most security models for authenticated key exchange (AKE) do not explicitly model the associated certification system, which includes the certification authority (CA) and its behaviour. However, there are several well-known and realistic attacks on AKE protocols which exploit various forms of malicious key registration and which therefore lie outside the scope of these models. We provide the first systematic analysis of AKE security incorporating certification systems (ASICS). We define a family of security models that, in addition to allowing different sets of standard AKE adversary queries, also permit the adversary to register arbitrary bitstrings as keys. For this model family we prove generic results that enable the design and verification of protocols that achieve security even if some keys have been produced maliciously. Our approach is applicable to a wide range of models and protocols; as a concrete illustration of its power, we apply it to the CMQV protocol in the natural strengthening of the eCK model to the ASICS setting.

Hierarchical Key Assignment Schemes can be used to enforce access control policies by cryptographic means. In this paper, we present a new, enhanced security model for such schemes. We also give simple, efficient, and strongly-secure constructions for Hierarchical Key Assignment Schemes for arbitrary hierarchies using pseudorandom functions and forward-secure pseudorandom generators. We compare instantiations of our constructions with state-of-the-art Hierarchical Key Assignment Schemes, demonstrating that our new schemes possess an attractive trade-off between storage requirements and efficiency of key derivation.

Kundu and Bertino (VLDB 2008) recently introduced the idea of structural signatures for trees which support public redaction of subtrees (by third-party distributors) while pertaining the integrity of the remaining parts. An example is given by signed XML documents of which parts should be sanitized before being published by a distributor not holding the signing key. Kundu and Bertino also provide a construction, but fall short of providing formal security definitions and proofs. Here we revisit their work and give rigorous security models for the redactable signatures for tree-structured data, relate the notions, and give a construction that can be proven secure under standard cryptographic assumptions.

In Secret Handshakes (SH) and Affiliation-Hiding Authenticated Key Exchange (AH-AKE) schemes, users become group members by registering with Group Authorities (GAs) and obtaining membership credentials. Group members then use their membership credentials to privately authenticate each other and communicate securely. The distinguishing privacy property of SH and AH-AKE is that parties learn each other's groups affiliations and compute common session keys only if their groups match. Current SH and AH-AKE schemes consider GAs to be fully trusted, especially, with regard to (i) security of the registration phase (no phantom members), (ii) secrecy of established session keys, and (iii) privacy. The impact of possible "big brother" ambitions of malicious GAs has not been investigated so far. In this paper, we discuss implications on group members' privacy and security of their communication in the presence of possible GA corruptions. We demonstrate problems arising from relaxed GA trust assumptions and propose an efficient -- yet provably secure -- AH-AKE protocol with enhanced privacy properties.

Privacy-preserving techniques are increasingly important in our highly computerized society where privacy is both precious and elusive. Affiliation-Hiding Authenticated Key Exchange (AH-AKE) protocols offer an appealing service: authenticated key agreement coupled with privacy of group memberships of protocol participants. This type of service is essential in privacy-conscious p2p systems, mobile ad hoc networks and social networking applications. Prior work has succeeded in constructing a number of secure and efficient AH-AKE protocols which all assume full trust in the Group Authority (GA) -- the entity that sets up the group as well as registers and (optionally) revokes members. In this paper, we argue that, for many anticipated application scenarios, the trusted GA model should be relaxed to allow for certain types of malicious behavior. We examine the consequences of malicious GAs and explore the design of stronger AH-AKE protocols that withstand GA attacks. Our results demonstrate that such protocols are both feasible and practical.