Updated: 11 hours 10 min ago

### More is Less: On the End-to-End Security of Group Chats in Signal, WhatsApp, and Threema

Sat, 01/06/2018 - 18:57
Secure instant messaging is utilized in two variants: one-to-one communication and group communication. While the first variant has received much attention lately (Frosch et al., EuroS&P16; Cohn-Gordon et al., EuroS&P17; Kobeissi et al., EuroS&P17), little is known about the cryptographic mechanisms and security guarantees of secure group communication in instant messaging. To approach an investigation of group instant messaging protocols, we first provide a comprehensive and realistic security model. This model combines security and reliability goals from various related literature to capture relevant properties for communication in dynamic groups. Thereby the definitions consider their satisfiability with respect to the instant delivery of messages. To show its applicability, we analyze three widely used real-world protocols: Signal, WhatsApp, and Threema. Since these protocols and their implementations are mostly undocumented for the public and two out of three applications among them are closed source, we describe the group protocols employed in Signal, WhatsApp, and Threema. By applying our model, we reveal several shortcomings with respect to the security definition. Therefore we propose generic countermeasures to enhance the protocols regarding the required security and reliability goals. Our systematic analysis reveals that (1) the communications’ integrity – represented by the integrity of all exchanged messages – and (2) the groups’ closeness – represented by the members’ ability of managing the group – are not end-to-end protected. We additionally show that strong security properties, such as Future Secrecy which is a core part of the one-to-one communication in the Signal protocol, do not hold for its group communication.

### Regularly Lossy Functions and Their Applications

Sat, 01/06/2018 - 10:09
In STOC 2008, Peikert and Waters introduced a powerful primitive called lossy trapdoor functions (LTFs). In a nutshell, LTFs are functions that behave in one of two modes. In the normal mode, functions are injective and invertible with a trapdoor. In the lossy mode, functions statistically lose information about their inputs. Moreover, the two modes are computationally indistinguishable. In this work, we put forward a relaxation of LTFs, namely, regularly lossy functions (RLFs). Compared to LTFs, the functions in the normal mode are not required to be efficiently invertible or even unnecessary to be injective. Instead, they could also be lossy, but in a regular manner. We also put forward richer abstractions of RLFs, namely all-but-one regularly lossy functions (ABO-RLFs) and one-time regularly lossy filters (OT-RLFs). We show that (ABO)-RLFs admit efficient constructions from both a variety of number-theoretic assumptions and hash proof system (HPS) for subset membership problems satisfying natural algebraic properties. Thanks to the relaxations on functionality, the constructions enjoy much compact key size and better computational efficiency than that of (ABO)-LTFs. We demonstrate the utility of RLFs and their extensions in the leakage-resilient cryptography. As a special case of RLFs, lossy functions imply leakage-resilient injective one-way functions with optimal leakage rate $1-o(1)$. ABO-RLFs (or OT-RLFs) immediately imply leakage-resilient one-time message authentication code (MAC) with optimal leakage rate $1-o(1)$. ABO-RLFs together with HPS give rise to leakage-resilient chosen-ciphertext (CCA) secure key encapsulation mechanisms (KEM) (this approach extends naturally to the identity-based setting). Combining the construction of ABO-RLFs from HPS, this gives the first leakage-resilient CCA-secure public-key encryption (PKE) with optimal leakage rate based solely on HPS, and thus goes beyond the barrier posed by Dodis et al. (Asiacrypt 2010).

### Algebraic Attack Efficiency versus S-box Representation

Sat, 01/06/2018 - 06:20
Algebraic analysis of block ciphers aims at finding the secret key by solving a collection of polynomial equations that describe the internal structure of a cipher for chosen observations of plaintext/ciphertext pairs. Although algebraic attacks are addressed for cryptanalysis of block and stream ciphers, there is a lack of understanding of the impact of algebraic representation of the cipher on efficiency of solving the resulting collection of equations. The work investigates different S-box representations and their effect on complexity of algebraic attacks. In particular, we observe that a S-box representation defined in the work as \textit{Forward-Backward} (FWBW) leads to a collection of equations that can be solved efficiently. We show that the $SR(10,2,1,4)$ cipher can be broken using standard algebra software \textsc{Singular} and FGb. This is the best result achieved so far. The effect of description of S-boxes for some light-weight block ciphers is investigated. A by-product of this result is that we have achieved some improvements on the algebraic cryptanalysis of LBlock, PRESENT and MIBS light-weight block ciphers. Our study and experiments confirms a counter-intuitive conclusion that algebraic attacks work best for the FWBW S-box representation. This contradicts a common belief that algebraic attacks are more efficient for quadratic S-box representation.

### Cryptanalysis of Compact-LWE Submitted to NIST PQC Project

Fri, 01/05/2018 - 12:01
Very recently, Liu, Li, Kim and Nepal submitted Compact-LWE, a new public key encryption scheme, to NIST as a candidate of the standard of post-quantum cryptography. About the security of Compact-LWE, the authors claimed that "even if the hard problems in lattice, such as CVP and SIS, can be efficiently solved, the secret values or private key in Compact-LWE still cannot be efficiently recovered. This allows Compact-LWE to choose very small dimension parameters, such as n = 8 in our experiment". However, in this paper, we show it is not true by proposing a ciphertext-only attack against Compact-LWE. More precisely, if we can solve CVP, we can decrypt any ciphertext without knowing the private keys. Since the dimension of the underlying lattice is very small (128) for the authors' parameter choice, (approximation-)CVP can be efficiently solved with lattice basis reduction algorithm. Hence, we can always break Compact-LWE with the authors' parameter choice in our experiments, which means that Compact-LWE with the recommended parameters is not secure.

### Two Simple Composition Theorems with H-coefficients

Fri, 01/05/2018 - 10:56
We will present here two new and simple theorems that show that when we compose permutation generators with independent keys, then the quality'' of CCA security increases. These theorems (Theorems 2 and 5 of this paper) are written in terms of H-coefficients (which are nothing else, up to some normalization factors, than transition probabilities). Then we will use these theorems on the classical analysis of Random Feistel Schemes (i.e. Luby-Rackoff constructions) and we will compare the results obtained with the bounds obtained with the coupling technique. Finally, we will show an interesting difference between 5 and 6 Random Feistel Schemes. With 5 rounds on $2n$ bits $\rightarrow 2n$ bits, when the number of $q$ queries satisfies $\sqrt{2^n} \ll q \ll 2^n$, we have some holes'' in the H-coefficient values, i.e. some H values are much smaller than the average value of H. This property for 5 rounds does not exist anymore on 6 rounds.

### Two Sides of the Same Coin: Counting and Enumerating Keys Post Side-Channel Attacks Revisited.

Fri, 01/05/2018 - 10:26
Motivated by the need to assess the concrete security of a device after a side channel attack, there has been a flurry of recent work designing both key rank and key enumeration algorithms. Two main competitors for key ranking can be found in the literature: a convolution based algorithm put forward by Glowacz et al. (FSE 2015), and a path counting based algorithm proposed by Martin et al. (Asiacrypt 2015). Both key ranking algorithms can be extended to key enumeration algorithms (Poussier et al. (CHES 2016) and Martin et al. (Asiacrypt 2015)). The two approaches were proposed independently, and have so far been treated as uniquely different techniques, with different levels of accuracy. However, we show that both approaches (for ranking) are mathematically equivalent for a suitable choice of their respective discretisation parameter. This settles questions about which one returns more accurate rankings. We then turn our attention to their related enumeration algorithms and determine why and how these algorithms differ in their practical performance.

### Near-Optimal Secret Sharing and Error Correcting Codes in AC0

Thu, 01/04/2018 - 21:01
We study the question of minimizing the computational complexity of (robust) secret sharing schemes and error correcting codes. In standard instances of these objects, both encoding and decoding involve linear algebra, and thus cannot be implemented in the class AC0. The feasibility of non-trivial secret sharing schemes in AC0 was recently shown by Bogdanov et al. (Crypto 2016) and that of (locally) decoding errors in AC0 by Goldwasser et al. (STOC 2007). In this paper, we show that by allowing some slight relaxation such as a small error probability, we can construct much better secret sharing schemes and error correcting codes in the class AC0. In some cases, our parameters are close to optimal and would be impossible to achieve without the relaxation. Our results significantly improve previous constructions in various parameters. Our constructions combine several ingredients in pseudorandomness and combinatorics in an innovative way. Specifically, we develop a general technique to simultaneously amplify security threshold and reduce alphabet size, using a two-level concatenation of protocols together with a random permutation. We demonstrate the broader usefulness of this technique by applying it in the context of a variant of secure broadcast.

### Multi-Key Searchable Encryption, Revisited

Thu, 01/04/2018 - 17:04
We consider a setting where users store their encrypted documents on a remote server and can selectively share documents with each other. A user should be able to perform keyword searches over all the documents she has access to, including the ones that others shared with her. The contents of the documents, and the search queries, should remain private from the server. This setting was considered by Popa et al. (NSDI '14) who developed a new cryptographic primitive called Multi-Key Searchable Encryption (MKSE), together with an instantiation and an implementation within a system called Mylar, to address this goal. Unfortunately, Grubbs et al. (CCS '16) showed that the proposed MKSE definition fails to provide basic security guarantees, and that the Mylar system is susceptible to simple attacks. Most notably, if a malicious Alice colludes with the server and shares a document with an honest Bob then the privacy of all of Bob's search queries is lost. In this work we revisit the notion of MKSE and propose a new strengthened definition that rules out the above attacks. We then construct MKSE schemes meeting our definition. We first give a simple and efficient construction using only pseudorandom functions. This construction achieves our strong security definition at the cost of increasing the server storage overhead relative to Mylar, essentially replicating the document each time it is shared. We also show that high server storage overhead is not inherent, by giving an alternate (albeit impractical) construction that manages to avoid it using obfuscation.

### Verifiability of Helios Mixnet

Thu, 01/04/2018 - 16:13
We study game-based definitions of individual and universal verifiability by Smyth, Frink & Clarkson. We prove that building voting systems from El Gamal coupled with proofs of correct key generation suffices for individual verifiability. We also prove that it suffices for an aspect of universal verifiability. Thereby eliminating the expense of individual-verifiability proofs and simplifying universal-verifiability proofs for a class of encryption-based voting systems. We use the definitions of individual and universal verifiability to analyse the mixnet variant of Helios. Our analysis reveals that universal verifiability is not satisfied by implementations using the weak Fiat-Shamir transformation. Moreover, we prove that individual and universal verifiability are satisfied when statements are included in hashes (i.e., when using the Fiat-Shamir transformation, rather than the weak Fiat-Shamir transformation).

### New Techniques for Public Key Encryption with Sender Recovery

Thu, 01/04/2018 - 14:09
In this paper, we consider a scenario where a sender transmits ciphertexts to multiple receivers using a public-key encryption scheme, and at a later point of time, wants to retrieve the plaintexts, without having to request the receivers' help in decrypting the ciphertexts, and without having to locally store a separate recovery key for every receiver the sender interacts with. This problem, known as public key encryption with sender recovery has intuitive solutions based on hybrid encryption-based key encapsulation mechanism and data encapsulation mechanism (KEM/DEM) schemes. We propose a KEM/DEM-based solution that is CCA2-secure, allows for multiple receivers, only requires the receivers to be equipped with public/secret keypairs (the sender needs only a single symmetric recovery key), and uses an analysis technique called plaintext randomization that results in greatly simplified, clean, and intuitive proofs compared to prior work in this area. We instantiate our protocol for public key encryption with sender recovery with the Cramer-Shoup hybrid encryption scheme.

### On Composable Security for Digital Signatures

Thu, 01/04/2018 - 11:10
A digital signature scheme (DSS), which consists of a key-generation, a signing, and a verification algorithm, is an invaluable tool in cryptography. The first and still most widely used security definition for a DSS, existential unforgeability under chosen-message attack, was introduced by Goldwasser, Micali, and Rivest in 1988. As DSSs serve as a building block in numerous complex cryptographic protocols, a security definition that specifies the guarantees of a DSS under composition is needed. Canetti (FOCS 2001, CSFW 2004) as well as Backes, Pfitzmann, and Waidner (CCS 2003) have described ideal functionalities for signatures in their respective composable-security frameworks. While several variants of these functionalities exist, they all share that the verification key and signature values appear explicitly. In this paper, we describe digital signature schemes from a different, more abstract perspective. Instead of modeling all aspects of a DSS in a monolithic ideal functionality, our approach characterizes a DSS as a construction of a functionality for authentically reading values written by a certain party from certain assumed functionalities, e.g., for transmitting verification key and signature values. This approach resolves several technical complications of previous simulation-based approaches, captures the security of signature schemes in an abstract way, and allows for modular proofs. We show that our definition is equivalent to existential unforgeability. We then model two example applications: (1) the certification of values via a signature from a specific entity, which with public keys as values is the core functionality of public-key infrastructures, and (2) the authentication of a session between a client and a server with the help of a digitally signed assertion from an identity provider. Single-sign-on mechanisms such as SAML rely on the soundness of the latter approach.

### Ubiquitous Weak-key Classes of BRW-polynomial Function

Thu, 01/04/2018 - 11:07
BRW-polynomial function is suggested as a preferred alternative of polynomial function, owing to its high efficiency and seemingly non-existent weak keys. In this paper we investigate the weak-key issue of BRW-polynomial function as well as BRW-instantiated cryptographic schemes. Though, in BRW-polynomial evaluation, the relationship between coefficients and input blocks is indistinct, we give out a recursive algorithm to compute another $(2^{v+1}-1)$-block message, for any given $(2^{v+1}-1)$-block message, such that their output-differential through BRW-polynomial evaluation, equals any given $s$-degree polynomial, where $v\ge\lfloor\log_2(s+1)\rfloor$. With such algorithm, we illustrate that any non-empty key subset is a weak-key class in BRW-polynomial function. Moreover any key subset of BRW-polynomial function, consisting of at least $2$ keys, is a weak-key class in BRW-instantiated cryptographic schemes like the Wegman-Carter scheme, the UHF-then-PRF scheme, DCT, etc. Especially in the AE scheme DCT, its confidentiality, as well as its integrity, collapses totally, when using weak keys of BRW-polynomial function, which are ubiquitous.

### Can You Trust Your Encrypted Cloud? An Assessment of SpiderOakONE's Security

Thu, 01/04/2018 - 09:28
This paper presents an independent security review of a popular encrypted cloud storage service (ECS) SpiderOakONE. Contrary to previous work analyzing similar programs, we formally define a minimal security requirements for confidentiality in ECS which takes into account the possibility that the ECS actively turns against its users in an attempt to beak the confidentiality of the users' data. Our analysis uncovered several serious issues, which either directly or indirectly damage the confidentiality of a user's files, therefore breaking the claimed Zero- or No-Knowledge property (e.g., the claim that even the ECS itself cannot access the users' data). After responsibly disclosing the issues we found to SpiderOak, most have been fixed.

### Privacy-Preserving Deep Learning via Additively Homomorphic Encryption

Thu, 01/04/2018 - 00:56
We build a privacy-preserving deep learning system in which many learning participants perform neural network-based deep learning over a combined dataset of all, without actually revealing the participants' local data. To that end, we revisit the previous work by Shokri and Shmatikov (ACM CCS 2015) and point out that local data information may be actually leaked to an honest-but-curious server. We then move on to fix that problem via building an enhanced system with following properties: (1) no information is leaked to the server; and (2) accuracy is kept intact, compared to that of the ordinary deep learning system also over the combined dataset. Our system is a bridge between deep learning and cryptography: we utilise stochastic gradient descent (SGD) applied to neural networks, in combination with additively homomorphic encryption. We show that our usage of encryption adds tolerable overhead to the ordinary deep learning system.

### Hashing solutions instead of generating problems: On the interactive certification of RSA moduli

Wed, 01/03/2018 - 17:48
Certain RSA-based protocols, for instance in the domain of group signatures, require a prover to convince a verifier that a set of RSA parameters is well-structured (e.g., that the modulus is the product of two distinct primes and that the exponent is co-prime to the group order). Various corresponding proof systems have been proposed in the past, with different levels of generality, efficiency, and interactivity. This paper proposes two new proof systems for a wide set of properties that RSA and related moduli might have. The protocols are particularly efficient: The necessary computations are simple, the communication is restricted to only one round, and the exchanged messages are short. While the first protocol is based on prior work (improving on it by reducing the number of message passes from four to two), the second protocol is novel. Both protocols require a random oracle.

### Secure Outsourcing of Circuit Manufacturing

Wed, 01/03/2018 - 15:37
The fabrication process of integrated circuits (ICs) is complex and requires the use of off -shore foundries to lower the costs and to have access to leading-edge manufacturing facilities. Such an outsourcing trend leaves the possibility of inserting malicious circuitry (a.k.a. hardware Trojans) during the fabrication process, causing serious security concerns. Hardware Trojans are very hard and expensive to detect and can disrupt the entire circuit or covertly leak sensitive information via a subliminal channel. In this paper, we propose a formal model for assessing the security of ICs whose fabrication has been outsourced to an untrusted o -shore manufacturer. Our model captures that the IC speci cation and design are trusted but the fabrication facility(ies) may be malicious. Our objective is to investigate security in an ideal sense and follows a simulation based approach that ensures that Trojans cannot release any sensitive information to the outside. It follows that the Trojans' impact in the overall IC operation, in case they exist, will be negligible up to simulation. We then establish that such level of security is in fact achievable for the case of a single and of multiple outsourcing facilities. We present two compilers for ICs for the single outsourcing facility case relying on veri able computation (VC) schemes, and another two compilers for the multiple outsourcing facilities case, one relying on multi-server VC schemes, and the other relying on secure multiparty computation (MPC) protocols with certain suitable properties that are attainable by existing schemes.

### An Inside Job: Remote Power Analysis Attacks on FPGAs

Wed, 01/03/2018 - 15:25
Hardware Trojans have gained increasing interest during the past few years. Undeniably, the detection of such malicious designs needs a deep understanding of how they can practically be built and developed. In this work we present a design methodology dedicated to FPGAs which allows measuring a fraction of the dynamic power consumption. More precisely, we develop internal sensors which are based on FPGA primitives, and transfer the internally-measured side-channel leakages outside. These are distributed and calibrated delay sensors which can indirectly measure voltage fluctuations due to power consumption. By means of a cryptographic core as a case study, we present different settings and parameters for our employed sensors. Using their side-channel measurements, we further exhibit practical key-recovery attacks confirming the applicability of the underlying measurement methodology. This opens a new door to integrate hardware Trojans in a) applications where the FPGA is remotely accessible and b) FPGA-based multi-user platforms where the reconfigurable resources are shared among different users. This type of Trojan is highly difficult to detect since there is no signal connection between targeted (cryptographic) core and the internally-deployed sensors.

### Graded Encoding Schemes from Obfuscation

Wed, 01/03/2018 - 08:43
We construct a graded encoding scheme (GES), an approximate form of graded multilinear maps. Our construction relies on indistinguishability obfuscation, and a pairing-friendly group in which (a suitable variant of) the strong Diffie--Hellman assumption holds. As a result of this abstract approach, our GES has a number of advantages over previous constructions. Most importantly: a) We can prove that the multilinear decisional Diffie--Hellman (MDDH) assumption holds in our setting, assuming the used ingredients are secure (in a well-defined and standard sense). In particular, and in contrast to previous constructions, our GES does not succumb to so-called zeroizing'' attacks. Indeed, our scheme is currently the only GES for which no known cryptanalysis applies. b) Encodings in our GES do not carry any noise. Thus, unlike previous GES constructions, there is no upper bound on the number of operations one can perform with our encodings. Hence, our GES essentially realizes what Garg et al.~(EUROCRYPT 2013) call the dream version'' of a GES. Technically, our scheme extends a previous, non-graded approximate multilinear map scheme due to Albrecht et al.~(TCC 2016-A). To introduce a graded structure, we develop a new view of encodings at different levels as polynomials of different degrees.

### Interactively Secure Groups from Obfuscation

Wed, 01/03/2018 - 08:41
We construct a mathematical group in which an interactive variant of the very general Uber assumption holds. Our construction uses probabilistic indistinguishability obfuscation, fully homomorphic encryption, and a pairing-friendly group in which a mild and standard computational assumption holds. While our construction is not practical, it constitutes a feasibility result that shows that under a strong but generic, and a mild assumption, groups exist in which very general computational assumptions hold. We believe that this grants additional credibility to the Uber assumption.

### Zipf's Law in Passwords

Wed, 01/03/2018 - 00:05