Updated: 1 hour 53 min ago

### Partial Key Exposure in Ring-LWE-Based Cryptosystems: Attacks and Resilience

Fri, 11/09/2018 - 12:27
We initiate the study of partial key exposure in ring-LWE-based cryptosystems. Specifically, we - Introduce the search and decision Leaky-RLWE assumptions (Leaky-SRLWE, Leaky-DRLWE), to formalize the hardness of search/decision RLWE under leakage of some fraction of coordinates of the NTT transform of the RLWE secret and/or error. - Present and implement an efficient key exposure attack that, given certain $1/4$-fraction of the coordinates of the NTT transform of the RLWE secret, along with RLWE instances, recovers the full RLWE secret for standard parameter settings. - Present a search-to-decision reduction for Leaky-RLWE for certain types of key exposure. - Analyze the security of NewHope key exchange under partial key exposure of $1/8$-fraction of the secrets and error. We show that, assuming that Leaky-DRLWE is hard for these parameters, the shared key $v$ (which is then hashed using a random oracle) is computationally indistinguishable from a random variable with average min-entropy $238$, conditioned on transcript and leakage, whereas without leakage the min-entropy is $256$.

### On Quantum Slide Attacks

Fri, 11/09/2018 - 12:25
At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon's algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with O(n) quantum time and queries. In this paper we propose many other types of quantum slide attacks. First, we are able to quantize classical advanced slide attacks on Feistel networks. With modular additions inside branch or key-addition operations, these attacks reach up to two round self-similarity. With only XOR operations, they reach up to four rounds self-similarity, with a cost at most quadratic in the block size. Moreover, some of these variants combined with whitening keys (FX construction) can be successfully attacked. We show how these results relate to general quantization principles of classical techniques including sliding with a twist, complementation slide and mirror slidex. Furthermore, we show that some quantum slide attacks can be composed with other quantum attacks to perform efficient key-recoveries even when the round founction is a strong function classically. Finally, we analyze the case of quantum slide attacks exploiting cycle-finding, that were thought to enjoy an exponential speed up in a paper by Bar-On et al. in 2015, where these attacks were introduced. We show that the speed-up is smaller than expected and less impressive than the above variants, but nevertheless provide improved complexities on the previous known quantum attacks in the superposition model for some self-similar SPN and Feistel constructions.

### Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness

Fri, 11/09/2018 - 12:25
Since the celebrated work of Impagliazzo and Rudich (STOC 1989), a number of black-box impossibility results have been established. However, these works only ruled out classical black-box reductions among cryptographic primitives. Therefore it may be possible to overcome these impossibility results by using quantum reductions. To exclude such a possibility, we have to extend these impossibility results to the quantum setting. In this paper, we initiate the study of black-box impossibility in the quantum setting. We first formalize a quantum counterpart of fully-black-box reduction following the formalization by Reingold, Trevisan and Vadhan (TCC 2004). Then we prove that there is no quantum fully-black-box reduction from collision-resistant hash function to one-way permutation (or even trapdoor permutation). This is an extension to the quantum setting of the work of Simon (Eurocrypt 1998) who showed a similar result in the classical setting.

### Homomorphic Secret Sharing for Low Degree Polynomials

Fri, 11/09/2018 - 12:23
Homomorphic secret sharing (HSS) allows $n$ clients to secret-share data to $m$ servers, who can then homomorphically evaluate public functions over the shares. A natural application is outsourced computation over private data. In this work, we present the first plain-model homomorphic secret sharing scheme that supports the evaluation of polynomials with degree higher than 2. Our construction relies on any degree-$k$ (multi-key) homomorphic encryption scheme and can evaluate degree-$\left( (k+1)m -1 \right)$ polynomials, for any polynomial number of inputs $n$ and any sub-logarithmic (in the security parameter) number of servers $m$. At the heart of our work is a series of combinatorial arguments on how a polynomial can be split into several low-degree polynomials over the shares of the inputs, which we believe is of independent interest.

### Towards Provably-Secure Analog and Mixed-Signal Locking Against Overproduction

Fri, 11/09/2018 - 12:19
Similar to digital circuits, analog and mixed-signal (AMS) circuits are also susceptible to supply-chain attacks such as piracy, overproduction, and Trojan insertion. However, unlike digital circuits, supply-chain security of AMS circuits is less explored. In this work, we propose to perform “logic locking” on digital section of the AMS circuits. The idea is to make the analog design intentionally suffer from the effects of process variations, which impede the operation of the circuit. Only on applying the correct key, the effect of process variations are mitigated, and the analog circuit performs as desired. We provide the theoretical guarantees of the security of the circuit, and along with simulation results for the band-pass filter, low-noise amplifier, and low-dropout regulator, we also show experimental results of our technique on a band-pass filter.

### Your Culture is in Your Password: An Analysis of a Demographically-diverse Password Dataset

Fri, 11/09/2018 - 12:18
A large number of studies on passwords make use of passwords leaked by attackers who compromised online services. Frequently, these leaks contain only the passwords themselves, or basic information such as usernames or email addresses. While metadata-rich leaks exist, they are often limited in the variety of demographics they cover. In this work, we analyze a meta-data rich data leak from a Middle Eastern bank with a demographically-diverse user base. We provide an analysis of passwords created by groups of people of different cultural backgrounds, some of which are under-represented in existing data leaks, e.g., Arab, Filipino, Indian, and Pakistani. The contributions provided by this work are many-fold. First, our results contribute to the existing body of knowledge regarding how users include personal information in their passwords. Second, we illustrate the differences that exist in how users from different cultural/linguistic backgrounds create passwords. Finally, we study the (empirical and theoretical) guessability of the dataset based on two attacker models, and show that a state of the art password strength estimator inflates the strength of passwords created by users from non-English speaking backgrounds. We improve its estimations by training it with contextually relevant information.

### Another coin bites the dust: An analysis of dust in UTXO based cryptocurrencies

Thu, 11/08/2018 - 11:03
Unspent Transaction Outputs (UTXOs) are the internal mechanism used in many cryp- tocurrencies to represent coins. Such representation has some clear benefits, but also entails some complexities that, if not properly handled, may leave the system in an inefficient state. Specifically, inefficiencies arise when wallets (the software responsible for transferring coins between parties) do not manage UTXOs properly when performing payments. In this paper, we study three cryptocurrencies: Bitcoin, Bitcoin Cash and Litecoin, by analyzing the actual state of their UTXO sets, that is, the status of their sets of spendable coins. These three cryptocurrencies are the top-3 UTXO based cryptocurrencies by market capitalization. Our analysis shows that the usage of each cryptocurrency is quite different, and let to different results. Furthermore, it also points out that the management of the transactions has not been always performed efficiently and then the actual state of the UTXO set for each cryptocurrency is far from ideal.

### STELLAR: A Generic EM Side-Channel Attack Protection through Ground-Up Root-cause Analysis

Wed, 11/07/2018 - 17:55
The threat of side-channels is becoming increasingly prominent for resource-constrained internet-connected devices. While numerous power side-channel countermeasures have been proposed, a promising approach to protect the non-invasive electromagnetic side-channel attacks has been relatively scarce. Today's availability of high-resolution electromagnetic (EM) probes mandates the need for a low-overhead solution to protect EM side-channel analysis (SCA) attacks. This work, for the first time, performs a white-box analysis to root-cause the origin of the EM leakage from an integrated circuit. System-level EM simulations with Intel 32 nm CMOS technology interconnect stack, as an example, reveals that the EM leakage from metals above layer 8 can be detected by an external non-invasive attacker with the commercially available state-of-the-art EM probes. Equipped with this `white-box' understanding, this work proposes \textit{STELLAR}: Signature aTtenuation Embedded CRYPTO with Low-Level metAl Routing, which is a two-stage solution to eliminate the critical signal radiation from the higher-level metal layers. Firstly, we propose routing of the entire cryptographic cores power traces using the local lower-level metal layers, whose leakage cannot be picked up by an external attacker. Then, the entire crypto IP is embedded within a Signature Attenuation Hardware (SAH) which in turn suppresses the critical encryption signature before it routes the current signature to the highly radiating top-level metal layers. System-level implementation of the STELLAR hardware with local lower-level metal routing in TSMC 65 nm CMOS technology, with an AES-128 encryption engine (as an example cryptographic block) operating at 40 MHz, shows that the system remains secure against EM SCA attack even after $1 M$ encryptions, with $67\%$ energy efficiency and $1.23\times$ area overhead compared to the unprotected AES.

### Attacks and Countermeasures for White-box Designs

Wed, 11/07/2018 - 12:00
In traditional symmetric cryptography, the adversary has access only to the inputs and outputs of a cryptographic primitive. In the white-box model the adversary is given full access to the implementation. He can use both static and dynamic analysis as well as fault analysis in order to break the cryptosystem, e.g. to extract the embedded secret key. Implementations secure in such model have many applications in industry. However, creating such implementations turns out to be a very challenging if not an impossible task. Recently, Bos et al. proposed a generic attack on white-box primitives called differential computation analysis (DCA). This attack was applied to many white-box implementations both from academia and industry. The attack comes from the area of side-channel analysis and the most common method protecting against such attacks is masking, which in turn is a form of secret sharing. In this paper we present multiple generic attacks against masked white-box implementations. We use the term “masking” in a very broad sense. As a result, we deduce new constraints that any secure white-box implementation must satisfy. Based on the new constraints, we develop a general method for protecting white-box implementations. We split the protection into two independent components: value hiding and structure hiding. Value hiding must pro- vide protection against passive DCA-style attacks that rely on analysis of computation traces. Structure hiding must provide protection against circuit analysis attacks. In this paper we focus on developing the value hiding component. It includes protection against the DCA attack by Bos et al. and protection against a new attack called algebraic attack. We present a provably secure first-order protection against the new al- gebraic attack. The protection is based on small gadgets implementing secure masked XOR and AND operations. Furthermore, we give a proof of compositional security allowing to freely combine secure gadgets. We derive concrete security bounds for circuits built using our construction.

### Untagging Tor: A Formal Treatment of Onion Encryption

Tue, 11/06/2018 - 13:11
Tor is a primary tool for maintaining anonymity online. It provides a low-latency, circuit-based, bidirectional secure channel between two parties through a network of onion routers, with the aim of obscuring exactly who is talking to whom, even to adversaries controlling part of the network. Tor relies heavily on cryptographic techniques, yet its onion encryption scheme is susceptible to tagging attacks (Fu and Ling, 2009), which allow an active adversary controlling the first and last node of a circuit to deanonymize with near-certainty. This contrasts with less active traffic correlation attacks, where the same adversary can at best deanonymize with high probability. The Tor project has been actively looking to defend against tagging attacks and its most concrete alternative is proposal 261, which specifies a new onion encryption scheme based on a variable-input-length tweakable cipher. We provide a formal treatment of low-latency, circuit-based onion encryption, relaxed to the unidirectional setting, by expanding existing secure channel notions to the new setting and introducing circuit hiding to capture the anonymity aspect of Tor. We demonstrate that circuit hiding prevents tagging attacks and show proposal 261's relay protocol is circuit hiding and thus resistant against tagging attacks.

### Port Contention for Fun and Profit

Tue, 11/06/2018 - 13:07
Simultaneous Multithreading (SMT) architectures are attractive targets for side-channel enabled attackers, with their inherently broader attack surface that exposes more per physical core microarchitecture components than cross-core attacks. In this work, we explore SMT execution engine sharing as a side-channel leakage source. We target ports to stacks of execution units to create a high-resolution timing side-channel due to port contention, inherently stealthy since it does not depend on the memory subsystem like other cache or TLB based attacks. Implementing said channel on Intel Skylake and Kaby Lake architectures featuring Hyper-Threading, we mount and end-to-end attack that recovers a P-384 private key from an OpenSSL-powered TLS server using a small number of repeated TLS handshake attempts. Furthermore, we show that traces targeting shared libraries, static builds, and SGX enclaves are essentially identical, hence our channel has wide target application.

### A Certain Family of Subgroups of $\mathbb Z_n^\star$ Is Weakly Pseudo-Free under the General Integer Factoring Intractability Assumption

Tue, 11/06/2018 - 10:57
Let $\mathbb G_n$ be the subgroup of elements of odd order in the group $\mathbb Z_n^\star$ and let $\mathcal U(\mathbb G_n)$ be the uniform probability distribution on $\mathbb G_n$. In this paper, we establish a probabilistic polynomial-time reduction from finding a nontrivial divisor of a composite number $n$ to finding a nontrivial relation between $l$ elements chosen independently and uniformly at random from $\mathbb G_n$, where $l\ge1$ is given in unary as a part of the input. Assume that finding a nontrivial divisor of a random number in some set $N$ of composite numbers (for a given security parameter) is a computationally hard problem. Then, using the above-mentioned reduction, we prove that the family $\{(\mathbb G_n,\mathcal U(\mathbb G_n))\}_{n\in N}$ of computational abelian groups is weakly pseudo-free. The disadvantage of this result is that the probability ensemble $\{\mathcal U(\mathbb G_n)\}_{n\in N}$ is not polynomial-time samplable. To overcome this disadvantage, we construct a polynomial-time computable function $\nu\colon D\to N$ (where $D\subseteq\{0,1\}^*$) and a polynomial-time samplable probability ensemble $\{\mathcal G_d\}_{d\in D}$ (where $\mathcal G_d$ is a distribution on $\mathbb G_{\nu(d)}$ for each $d\in D$) such that the family $\{(\mathbb G_{\nu(d)},\mathcal G_d)\}_{d\in D}$ of computational abelian groups is weakly pseudo-free.

### New Perspectives on Zero-Knowledge Multi-Prover Interactive Proofs

Mon, 11/05/2018 - 23:21
In multi-prover interactive proofs (MIPs), the verifier can provide non-local resources for the provers intrinsically. In most cases, this is undesirable. Existing proofs of soundness do not account for the verifier's non-local potential. We show that this may be a problem for many MIPs. We provide a solution by constructing a generalization of the MIP model, of which standard MIPs are a special case. This new model accounts for both the prover and the verifier's non-local correlations. A new property of multi-prover zero-knowledge naturally emerges as a result.

### Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness

Mon, 11/05/2018 - 17:16
The existence of secure indistinguishability obfuscators (iO) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing iO rely on \emph{$d$-linear maps} which allow the encoding of elements from a large domain, evaluating degree $d$ polynomials on them, and testing if the output is zero. While secure \emph{bilinear maps} are well established in cryptographic literature, the security of candidates for $d>2$ is poorly understood. We propose a new approach to constructing iO for general circuits. Unlike all previously known realizations of iO, we avoid the use of $d$-linear maps of degree $d \ge 3$. At the heart of our approach is the assumption that a new \emph{weak} pseudorandom object exists, that we call a \emph{perturbation resilient generator} ($\Delta\mathsf{RG}$). Informally, a $\Delta\mathsf{RG}$ maps $n$ integers to $m$ integers, and has the property that for any sufficiently short vector $a \in \mathbb{Z}^m$, all efficient adversaries must fail to distinguish the distributions $\Delta\mathsf{RG}(s)$ and $\Delta\mathsf{RG}(s)+a$, with at least some probability that is inverse polynomial in the security parameter. $\Delta\mathsf{RG}s$ have further implementability requirements; most notably they must be computable by a family of degree-3 polynomials over $\mathbb{Z}$. We use techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but non-overwhelming distinguishing advantage. In particular, we obtain a new security amplification theorem for functional encryption. As a result, we obtain iO for general circuits assuming: - Subexponentially secure LWE - Bilinear Maps - $poly(\lambda)$-secure 3-block-local PRGs - $(1-1/poly(\lambda))$-secure $\Delta\mathsf{RG}s$

### Faster key compression for isogeny-based cryptosystems

Mon, 11/05/2018 - 15:47
Supersingular isogeny-based cryptography is one of the more recent families of post-quantum proposals. An interesting feature is the comparatively low bandwidth occupation in key agreement protocols, which stems from the possibility of key compression. However, compression and decompression introduce a significant overhead to the overall processing cost despite recent progress. In this paper we address the main processing bottlenecks involved in key compression and decompression, and suggest substantial improvements for each of them. Some of our techniques may have an independent interest for other, more conventional areas of elliptic curve cryptography as well.