Updated: 5 hours 44 min ago

Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions

Wed, 04/18/2018 - 16:41
The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in several seemingly different topics. These include seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey graphs), and non-malleable codes in the split state model. Previously, the best constructions are given in [Li17]: seeded non-malleable extractors with seed length and entropy requirement $O(\log n+\log(1/\epsilon)\log \log (1/\epsilon))$ for error $\epsilon$; two-round privacy amplification protocols with optimal entropy loss for security parameter up to $\Omega(k/\log k)$, where $k$ is the entropy of the shared weak source; two-source extractors for entropy $O(\log n \log \log n)$; and non-malleable codes in the $2$-split state model with rate $\Omega(1/\log n)$. However, in all cases there is still a gap to optimum and the motivation to close this gap remains strong. In this paper, we introduce a set of new techniques to further push the frontier in the above questions. Our techniques lead to improvements in all of the above questions, and in several cases partially optimal constructions. This is in contrast to all previous work, which only obtain close to optimal constructions. Specifically, we obtain: 1. A seeded non-malleable extractor with seed length $O(\log n)+\log^{1+o(1)}(1/\epsilon)$ and entropy requirement $O(\log \log n+\log(1/\epsilon))$, where the entropy requirement is asymptotically optimal by a recent result of Gur and Shinkar [GurS17]; 2. A two-round privacy amplification protocol with optimal entropy loss for security parameter up to $\Omega(k)$, which solves the privacy amplification problem completely; 3. A two-source extractor for entropy $O(\frac{\log n \log \log n}{\log \log \log n})$, which also gives an explicit Ramsey graph on $N$ vertices with no clique or independent set of size $(\log N)^{O(\frac{\log \log \log N}{\log \log \log \log N})}$; and 4. The first explicit non-malleable code in the $2$-split state model with constant rate, which has been a major goal in the study of non-malleable codes for quite some time. One small caveat is that the error of this code is only (an arbitrarily small) constant, but we can also achieve negligible error with rate $\Omega(\log \log \log n/\log \log n)$, which already improves the rate in [Li17] exponentially. We believe our new techniques can help to eventually obtain completely optimal constructions in the above questions, and may have applications in other settings.

A Chosen Plaintext Attack on Offset Public Permutation Mode

Wed, 04/18/2018 - 16:30
Offset Public Permutation Mode (OPP) by Granger et al. is a one-pass authenticated encryption scheme supporting associated data (AEAD scheme). Leveraging an error in analysis of the scheme, a chosen plaintext attack that creates a forgery was discovered. This attack makes no assumptions about the underlying tweakable blockcipher while having negligible complexity requirements and high probability of success. An implementation of the attack is also provided.

An Analysis of the NIST SP 800-90A Standard

Wed, 04/18/2018 - 16:28
We conduct a multi-faceted investigation of the security properties of the three deterministic random bit generator (DRBG) mechanisms recommended in the NIST SP 800-90A standard [4]. This standard received a considerable amount of negative attention, due to the host of controversy and problems with the now retracted DualEC-DRBG, which was included in earlier revisions. Perhaps because of the attention paid to the DualEC, the other algorithms in the standard have received surprisingly patchy analysis to date, despite widespread deployment. This paper provides an analysis of the remaining DRBG algorithms in NIST SP 800-90A. We uncover a mix of positive and less than positive results, emphasizing and addressing the gap between theoretical models, and the NIST DRBGs as specified and used. As an initial positive result, we verify claims in the standard by proving (with a few caveats) the forward security of all three DRBGs. However, digging deeper into flexibility in implementation and usage choices permitted by the standard, we uncover some undesirable properties of these standardized DRBGs. Specifically, we argue that these DRBGs have the property that leaking certain parts of the state may lead to catastrophic failure of the algorithm. Furthermore, we show that flexibility in the specification allows implementers and users of these algorithms to make choices that considerably weaken the algorithms in these scenarios.

Monero Ring Attack: Recreating Zero Mixin Transaction Effect

Wed, 04/18/2018 - 16:28
Monero is one of the privacy-preserving cryptocurrencies employing CryptoNote protocol. The privacy features in Monero are provided by cryptographic techniques called linkable ring signature and one-time public key. Recent studies show that the majority of Monero inputs are traceable prior to mandatory RingCT transaction. After the RingCT was implemented, the problem was mitigated. We propose a novel attack to reduce the anonymity of Monero transactions or even to fully deanonymise the inputs. The proposed protocol can be launched in RingCT scenario and enable multiple attackers to collaborate without trusting each other. The attack scheme can be planted in the existing Monero services without extra fees and without putting the users’ money at risk.

Impossible Differential Cryptanalysis of Midori

Wed, 04/18/2018 - 07:00
Midori is a light weight block cipher recently presented by Banik et al in ASIACRYPT 2015. There are two versions of Midori with state sizes of 64-bit and 128-bit respectively. The round function is based on Substitution-Permutation Network(SPN). In this paper, we give impossible differential cryptanalysis of Midori64. We studied the non-linear layer of the cipher and give two useful properties. We also find the first 6- round impossible differential paths with two non-zero and equal input cells and one non-zero output cell, and then mount 10-round attack. This is the first impossible differential attack on Midori.

How Fast Can We Obfuscate Using Ideal Graded Encoding Schemes

Tue, 04/17/2018 - 22:47
In this work, we present a new obfuscator using a Graded Encoding Scheme (GES) with a binary slot. We characterize a class of circuits taking locally keyed input (each input bit of the circuit is a keyed function over c>1 bits of a binary-variable vector X of length n, where $c$ is called the locality), called ideal functions, such that any function of algebraic degree d (called d-function) over them, can be obfuscated with multilinearity \mu=(d+1)n/c. Next we show that obfuscation of a general circuit C can be bootstrapped by O(n)-functions (the circuit (called RE) composing a garbled circuit (GC) with a pseudorandom function (PRF)), following an approach similar to that of Zimmerman and Applebaum et al. \cite{Zim13,AB15}, assuming PRF (or more precisely RE) exists among d-functions with constant d. To instantiate the above scheme, we achieve the following: 1. A concrete GC of algebraic degree 3 over its random bits, which has output size no more than 20\lambda|C| and random tape length about 10\lambda|C|, where \lambda is the security parameter, |C| denotes the number of gates of the circuit C. 2. A candidate d-function construction, where we argue that d=1 suffices to stop linear distinguishing attacks and d=2 seems enough for fully secure PRF. 3. Instantiation of the GES with a simplified version of the CLT multilinear map, and various techniques that further reduce \mu of the core obfuscator cost-equivalently to dn/(2c)+1 in cases of our interest. If we replace the PRF with d-functions, then we get various heuristic obfuscation-friendly REs, and thus general obfuscators with explicit complexities. For the most optimistic choice, we have \mu=1.5n'/c +2.5, n'\approx n+\log |C|+\log \lambda, n is the number of input bits of C, and c is a selectable constant which result in a {2^c}/{c} times increase of the key size of the RE. Our general obfuscator is VBB secure assuming that our RE is secure and our simplified CLT map is a secure instantiation of our GES (defined relative to known attacks). We leave these assumptions with concrete parameter sets as open challenges. We illustrate the efficiency of our methods with some examples: 1. Our obfuscated AES (c=13, \mu=20.5) has code size <1.5\times 10^{17} bits, whereas no implementable solution is known prior to this work. 2. We can practically obfuscate conjunction functions for n=64, while the latest implementation \cite{cryptoeprint:2017:844} can only handle n=32 with comparable resources. We also verify the security against algebraic attacks in this example.

Securing Systems with Scarce Entropy: LWE-Based Lossless Computational Fuzzy Extractor for the IoT

Tue, 04/17/2018 - 05:11
With the advent of the Internet of Things, lightweight devices necessitate secure and cost-efficient key storage. Since traditional secure key storage is expensive, novel solutions have been developed based on the idea of deriving the key from noisy entropy sources. Such sources when combined with fuzzy extractors allow cryptographically strong key derivation. Information theoretic fuzzy extractors require large amounts of input entropy to account for entropy loss in the key extraction process. It has been shown by Fuller \textit{et al.}~(ASIACRYPT'13) that the entropy loss can be reduced if the requirement is relaxed to computational security based on the hardness of the Learning with Errors problem. Using this computational fuzzy extractor, we show how to construct a device-server authentication system providing outsider chosen perturbation security and pre-application robustness. We present the first implementation of a \emph{lossless} computational fuzzy extractor where the entropy of the source equals the entropy of the key on a constrained device. The implementation needs only 1.45KB of SRAM and 9.8KB of Flash memory on an 8-bit microcontroller. Furthermore, we also show how a device-server authentication system can be constructed and efficiently implemented in our system. We compare our implementation to existing work in terms of security, while achieving no entropy loss.

Function-Revealing Encryption

Mon, 04/16/2018 - 20:20
Multi-input functional encryption is a paradigm that allows an authorized user to compute a certain function---and nothing more---over multiple plaintexts given only their encryption. The particular case of two-input functional encryption has very exciting applications, including comparing the relative order of two plaintexts from their encrypted form (order-revealing encryption). While being extensively studied, multi-input functional encryption is not ready for a practical deployment, mainly for two reasons. First, known constructions rely on heavy cryptographic tools such as multilinear maps. Second, their security is still very uncertain, as revealed by recent devastating attacks. In this work, we investigate a simpler approach towards obtaining practical schemes for functions of particular interest. We introduce the notion of function-revealing encryption, a generalization of order-revealing encryption to any multi-input function as well as a relaxation of multi-input functional encryption. We then propose a simple construction of order-revealing encryption based on function-revealing encryption for simple functions, namely orthogonality testing and intersection cardinality. Our main result is an efficient order-revealing encryption scheme with limited leakage based on the standard DLIN assumption.

3PC ORAM with Low Latency, Low Bandwidth, and Fast Batch Retrieval

Mon, 04/16/2018 - 18:27
Multi-Party Computation of Oblivious RAM (MPC ORAM) implements secret-shared random access memory in a way that protects access pattern privacy against a threshold of corruptions. MPC ORAM enables secure computation of any RAM program on large data held by different entities, e.g. MPC processing of database queries on a secret-shared database. MPC ORAM can be constructed by any (client-server) ORAM, but there is an efficiency gap between known MPC ORAM's and ORAM's. Current asymptotically best MPC ORAM is implied by an "MPC friendly" variant of Path-ORAM called Circuit-ORAM, due to Wang et al. However, using garbled circuit for Circuit-ORAM's client implies MPC ORAM which matches Path-ORAM in rounds but increases bandwidth by \Omega(kappa) factor, while using GMW or BGW protocols implies MPC ORAM which matches Path-ORAM in bandwidth, but increases round complexity by \Omega(log n loglog n) factor, for kappa the security parameter and n the memory size. In this paper we bridge the gap between MPC ORAM and client-server ORAM by showing a specialized 3PC ORAM protocol, i.e. MPC ORAM for 3 parties tolerating 1 fault, which uses only symmetric ciphers and asymptotically matches client-server Path-ORAM in round complexity and for large records also in bandwidth. Our 3PC ORAM also allows for fast pipelined processing: With post- poned clean-up it processes b=O(log n) accesses in O(b+log n) rounds with O(D+poly(log n)) bandwidth per item, where D is record size.

Collusion Resistant Traitor Tracing from Learning with Errors

Mon, 04/16/2018 - 18:26
In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in $\log(n)$ where $n$ is the number of users and prove it secure under the Learning with Errors (LWE) assumption. This is the first traitor tracing scheme with such parameters provably secure from a standard assumption. In addition to achieving new traitor tracing results, we believe our techniques push forward the broader area of computing on encrypted data under standard assumptions. Notably, traitor tracing is substantially different problem from other cryptography primitives that have seen recent progress in LWE solutions. We achieve our results by first conceiving a novel approach to building traitor tracing that starts with a new form of Functional Encryption that we call Mixed FE. In a Mixed FE system the encryption algorithm is bimodal and works with either a public key or master secret key. Ciphertexts encrypted using the public key can only encrypt one type of functionality. On the other hand the secret key encryption can be used to encode many different types of programs, but is only secure as long as the attacker sees a bounded number of such ciphertexts. We first show how to combine Mixed FE with Attribute-Based Encryption to achieve traitor tracing. Second we build Mixed FE systems for polynomial sized branching programs (which corresponds to the complexity class LOGSPACE) by relying on the polynomial hardness of the LWE assumption with super-polynomial modulus-to-noise ratio.

In-region Authentication

Mon, 04/16/2018 - 18:26
Location information has wide applications in customization and personalization of services, as well as secure authentication and access control. We introduce {\em in-Region Authentication (inRA)}, a novel type of authentication, that allows a prover to prove to a set of cooperating verifiers that they are in possession of the correct secret key, and are inside a specified (policy) region of arbitrary shape. These requirements naturally arise when a privileged service is offered to registered users within an area. Locating a prover without assuming GPS (Global Positioning System) signal however, incurs error. We discuss the challenge of designing secure protocols that have quantifiable error in this setting, define and formalize correctness and security properties of the protocols, and propose a systematic approach to designing a family of protocols with provable security where error can be flexibly defined and efficiently minimized. We give a concrete instance of this family that starts with two verifiers, prove its security and evaluate its application to four different policy regions. Our results show that in all cases false acceptance and false rejection of below $6\%$ can be achieved. We compare our results with related works, and propose directions for future research.

Nothing Refreshes Like a RePSI: Reactive Private Set Intersection

Mon, 04/16/2018 - 18:25
Private Set Intersection (PSI) is a popular cryptographic primitive that allows two parties, a client and a server, to compute the intersection of their private sets, so that the client only receives the output of the computation, while the server learns nothing besides the size of the client's set. A common limitation of PSI is that a dishonest client can progressively learn the server's set by enumerating it over different executions. Although these oracle attacks'' do not formally violate security according to traditional secure computation definitions, in practice, they often hamper real-life deployment of PSI instantiations, especially if the server's set does not change much over multiple interactions. In a first step to address this problem, this paper presents and studies the concept of Reactive PSI (RePSI). We model PSI as a reactive functionality, whereby the output depends on previous instances, and use it to limit the effectiveness of oracle attacks. We introduce a general security model for RePSI in the (augmented) semi-honest model and a construction which enables the server to control how many inputs have been used by the client across several executions. In the process, we also present the first construction of a Size-Hiding PSI (SHI-PSI) protocol in the standard model, which may be of independent interest.

Flexible Signatures: Towards Making Authentication Suitable for Real-Time Environments

Mon, 04/16/2018 - 18:23
This work introduces the concept of flexible signatures. In a flexible signature scheme, the verification algorithm quantifies the validity of a signature based on the number of computations performed such that the signature's validation (or confidence) level in $[0,1]$ improves as the algorithm performs more computations. Importantly, the definition of flexible signatures does not assume the resource restriction to be known in advance until the verification process is hard stopped by a system interrupt. Although prominent traditional signature schemes such as RSA, (EC)DSA, EdDSA seem unfit towards building flexible signatures, we find updated versions of the Lamport-Diffie one-time signature and Merkle authentication tree to be suitable for building flexible signatures. We present a flexible signature construction based on these hash-based primitives and prove its security with a concrete security analysis. We also perform a thorough validity-level analysis demonstrating an attractive computation-vs-validity trade-off offered by our construction: a security level of $80$ bits can be ensured by performing only around $\frac{2}{3}$rd of the total hash computations for our flexible signature construction with a Merkle tree of height $20$. We see this work as the first step towards realizing flexible-security cryptographic primitives. Beyond flexible signatures, our flexible-security conceptualization offers an interesting opportunity to build similar primitives in the asymmetric as well as symmetric cryptographic domains. Apart from being theoretically interesting, these flexible security primitives can be of particular interest to real-time systems as well as the Internet of things: rigid all-or-nothing guarantees offered by the traditional cryptographic primitives have been particularly unattractive to these unpredictably resource-constrained

MergeMAC: A MAC for Authentication with Strict Time Constraints and Limited Bandwidth

Mon, 04/16/2018 - 18:14
This paper presents MergeMAC, a MAC that is particularly suitable for environments with strict time requirements and extremely limited bandwidth. MergeMAC computes the MAC by splitting the message into two parts. We use a pseudorandom function (PRF) to map messages to random bit strings and then merge them with a very efficient keyless function. The advantage of this approach is that the outputs of the PRF can be cached for frequently needed message parts. We demonstrate the merits of MergeMAC for authenticating messages on the CAN bus where bandwidth is extremely limited and caching can be used to recover parts of the message counter instead of transmitting it. We recommend an instantiation of the merging function MERGE and analyze the security of our construction. Requirements for a merging function are formally defined and the resulting EUF-CMA security of MergeMAC is proven.

Comparison of Cost of Protection Against Differential Power Analysis of Selected Authenticated Ciphers

Mon, 04/16/2018 - 18:11
Authenticated ciphers, like all physical implementations of cryptography, are vulnerable to side-channel attacks, including differential power analysis (DPA). The t-test leakage detection methodology has been used to verify improved resistance of block ciphers to DPA after application of countermeasures. However, extension of the t-test methodology to authenticated ciphers is non-trivial, since authenticated ciphers require additional input and output conditions, complex interfaces, and long test vectors interlaced with protocol necessary to describe authenticated cipher operations. In this research we augment an existing side-channel analysis architecture (FOBOS) with t-test leakage detection for authenticated ciphers. We use this capability to show that implementations in the Spartan-6 FPGA of the CAESAR Round 3 candidates ACORN, ASCON, CLOC (AES and TWINE), SILC (AES, PRESENT, and LED), JAMBU (AES and SIMON), and Ketje Jr., as well as AES-GCM, are vulnerable to 1st order DPA. We then implement versions of the above ciphers, protected against 1st order DPA, using threshold implementations. The t-test leakage detection methodology is used to verify improved resistance to 1st order DPA of the protected cipher implementations. Finally, we benchmark unprotected and protected cipher implementations in the Spartan-6 FPGA, and compare the costs of 1st order DPA protection in terms of area, frequency, throughput, throughput-to-area (TP/A) ratio, power, and energy-per-bit. Our results show that ACORN has the lowest area (in LUTs), the highest TP/A ratio, and is the most energy-efficient of all DPA-resistant implementations. However, Ketje Jr. has the highest throughput.

Delegatable Attribute-based Anonymous Credentials from Dynamically Malleable Signatures

Mon, 04/16/2018 - 18:09
In this paper, we introduce the notion of delegatable attribute-based anonymous credentials (DAAC). Such systems offer fine-grained anonymous access control and they give the credential holder the ability to issue more restricted credentials to other users. In our model, credentials are parameterized with attributes that (1) express what the credential holder himself has been certified and (2) define which attributes he may issue to others. Furthermore, we present a practical construction of DAAC. For this construction, we deviate from the usual approach of embedding a certificate chain in the credential. Instead, we introduce a novel approach for which we identify a new primitive we call dynamically malleable signatures (DMS) as the main ingredient. This primitive may be of independent interest. We also give a first instantiation of DMS with efficient protocols.

A polynomial attack on a NIST proposal: RankSign, a code-based signature in rank metric

Mon, 04/16/2018 - 18:09
RankSign is a code-based signature scheme proposed to the NIST competition for post-quantum cryptography [AGHRZ17]. It is based on the rank metric and enjoys remarkably small key sizes, about 10KBytes for an intended level of security of 128 bits. It is also one of the fundamental blocks used in the rank metric identity based encryption scheme [GHPT17]. Unfortunately we will show that all the parameters proposed for this scheme in [AGHRZ17] can be broken by an algebraic attack that exploits the fact that the augmented LRPC codes used in this scheme have very low weight codewords.

Giving State to the Stateless: Augmenting Trustworthy Computation with Ledgers

Mon, 04/16/2018 - 16:01
In this work we investigate the problem of achieving secure computation by combining stateless trusted devices with public ledgers. We consider a hybrid paradigm in which a client-side device (such as a co-processor or trusted enclave) performs secure computation, while interacting with a public ledger via a possibly malicious host computer. We explore both the constructive and potentially destructive implications of such systems. We first show that this combination allows for the construction of stateful interactive functionalities (including general computation) even when the device has no persistent storage; this allows us to build sophisticated applications using inexpensive trusted hardware or even pure cryptographic obfuscation techniques. We further show how to use this paradigm to achieve censorship-resistant communication with a network, even when network communications are mediated by a potentially malicious host. Finally we describe a number of practical applications that can be achieved today. These include the synchronization of private smart contracts; rate limited mandatory logging; strong encrypted backups from weak passwords; enforcing fairness in multi-party computation; and destructive applications such as autonomous ransomware, which allows for payments without an online party.

Strain: A Secure Auction for Blockchains

Mon, 04/16/2018 - 12:08
We present Strain, a new auction protocol running on top of blockchains and guaranteeing bid confidentiality against fully-malicious parties. As our goal is efficiency and low blockchain latency, we abstain from using traditional, highly interactive MPC primitives such as secret shares. We focus on a slightly weaker adversary model than MPC which allows Strain to achieve constant latency in both the number of parties and the bid length. The main idea behind Strain is a new maliciously-secure two-party comparison mechanism executed between any pair of bids in parallel. Using zero-knowledge proofs, Strain broadcasts the outcome of comparisons on the blockchain in a way that all parties can verify each outcome. Strain's latency is not only asymptotically optimal, but also efficient in practice, requiring a total of just 4 blocks of the underlying blockchain. Strain provides typical auction security requirements such as non-retractable bids against fully-malicious adversaries.

Z-Channel: Scalable and Efficient Scheme in Zerocash

Sun, 04/15/2018 - 22:28
Decentralized ledger-based cryptocurrencies like Bitcoin present a way to construct payment systems without trusted banks. However, the anonymity of Bitcoin is fragile. Many altcoins and protocols are designed to improve Bitcoin on this issue, among which Zerocash is the first full-fledged anonymous ledger-based currency, using zero-knowledge proof, specifically zk-SNARK, to protect privacy. However, Zerocash suffers two problems: poor scalability and low efficiency. In this paper, we address the above issues by constructing a micropayment system in Zerocash called Z-Channel. First, we improve Zerocash to support multisignature and time lock functionalities, and prove that the reconstructed scheme is secure. Then we construct Z-Channel based on the improved Zerocash scheme. Our experiments demonstrate that Z-Channel significantly improves the scalability and reduces the confirmation time for Zerocash payments.