Updated: 10 hours 54 sec ago

A new chosen IV statistical distinguishing framework to attack symmetric ciphers, and its application to ACORN-v3 and Grain-128a

Wed, 11/15/2017 - 07:30
We propose a new attack framework based upon cube testers and d-monomial tests. The d-monomial test is a general framework for comparing the ANF of the symmetric cipher’s output with ANF of a random Boolean function. In the d-monomial test, the focus is on the frequency of the special monomial in the ANF of Boolean functions, but in the proposed framework, the focus is on the truth table. We attack ACORN-v3 and Grain-128a and demonstrate the efficiency of our framework. We show how it is possible to apply a distinguishing attack for up to 676 initialization rounds of ACORN-v3 and 171 initialization rounds of Grain-128a using our framework. The attack on ACORN-v3 is the best practical attack (and better results can be obtained by using more computing power). One can apply distinguishing attacks to black box symmetric ciphers by the proposed framework, and we suggest some guidelines to make it possible to improve the attack by analyzing the internal structure of ciphers. The framework is applicable to all symmetric ciphers and hash functions. We discuss how it can reveal weaknesses that are not possible to find by other statistical tests. The attacks were practically implemented and verified.

ID-HABE: Incorporating ID-based Revocation, Delegation, and Authority Hierarchy into Attribute-Based Encryption

Wed, 11/15/2017 - 07:25
Ciphertext-Policy Attribute-Based Encryption (CP-ABE) has been proposed to implement fine-grained access control. Data owners encrypt data with a certain access policy so that only data users whose attributes satisfy the access policy can decrypt the ciphertext. A user can be automatically assigned an access privilege based on whether his/her attributes satisfying a given access policy described by attributes and their logical relations. In order to provide more flexible policy-based access control, attribute-based revocation approaches had been proposed to provide the NOT logic on attributes to allow attribute-based revocation. However, previous solutions increase the attribute management overhead when considering each user’s ID as an attribute for more precise revocations at the individual user-level. To address this issue, in this paper, an ID-ABE scheme is presented, where a user’s ID is incorporated into the key generation procedure allowing user-ID-based revocation. In addition to ID-based revocation, ID-ABE also presents a hierarchical identity structure to build a delegation framework to enable group-based revocation. In the end, we also evaluate the performance of the proposed scheme in terms of computation, storage and communication overhead, which shows the practical value of the solution for secure data sharing applications.

HIR-CP-ABE: Hierarchical Identity Revocable Ciphertext-Policy Attribute-Based Encryption for Secure and Flexible Data Sharing

Wed, 11/15/2017 - 07:25
Ciphertext Policy Attribute-Based Encryption (CP- ABE) has been proposed to implement the attribute-based access control model. In CP-ABE, data owners encrypt the data with a certain access policy such that only data users whose attributes satisfy the access policy could obtain the corresponding private decryption key from a trusted authority. Therefore, CP-ABE is considered as a promising fine-grained access control mechanism for data sharing where no centralized trusted third party exists, for example, cloud computing, mobile ad hoc networks (MANET), Peer-to-Peer (P2P) networks, information centric networks (ICN), etc.. As promising as it is, user revocation is a cumbersome problem in CP-ABE, thus impeding its application in practice. To solve this problem, we propose a new scheme named HIR-CP-ABE, which implements hierarchical identity- based user revocation from the perceptive of encryption. In particular, the revocation is implemented by data owners directly without any help from any third party. Compared with previous attribute-based revocation solutions, our scheme provides the following nice properties. First, the trusted authority could be offline after system setup and key distribution, thus making it applicable in mobile ad hoc networks, P2P networks, etc., where the nodes in the network are unable to connect to the trusted authority after system deployment. Second, a user does not need to update the private key when user revocation occurs. Therefore, key management overhead is much lower in HIR-CP-ABE for both the users and the trusted authority. Third, the revocation mechanism enables to revoke a group of users affiliated with the same organization in a batch without influencing any other users. To the best of our knowledge, HIR-CP-ABE is the first CP-ABE scheme to provide affiliation-based revocation functionality for data owners. Through security analysis and performance evaluation, we show that the proposed scheme is secure and efficient in terms of computation, communication and storage.

IR-CP-ABE: Identity Revocable Ciphertext-Policy Attribute-Based Encryption for Flexible Secure Group-Based Communication

Wed, 11/15/2017 - 07:25
Ciphertext-Policy Attribute-Based Encryp- tion (CP-ABE) is an access control mechanism over encrypted data and well suited for secure group-based communication. However, it also suffers from the fol- lowing problem, i.e., it is impossible to build all de- sired groups. For example, if two group members have exactly the same attributes, how to construct a group including only one of the two members? Obviously, at- tributes alone cannot distinguish these two members, therefore existing CP-ABE solutions do not work. To address this issue, in this paper, we present a new CP-ABE scheme (called IR-CP-ABE) that incorporates an Identity-based Revocation capability. With IR-CP-ABE, an access policy will be constructed by not only group members’ attributes but also their identities. To build a group, first, build a candidate group based on all de- sired group members’ attributes; second, remove unde- sired members by revoking their identities. By evaluat- ing the security and efficiency of a proposed construc- tion, we show that the IR-CP-ABE scheme is secure and efficient for practical applications.

Impossible Differential Attack on Midori128 Using Rebound-like Technique

Wed, 11/15/2017 - 03:48
Midori is a family of lightweight block cipher proposed by Banik et al. in ASIACRYPT 2015 and it is optimized with respect to the energy consumed by the circuit per bit in encryption or decryption operation. Midori is based on the Substitution-Permutation Network, which has two variants according to the state sizes, i.e. Midori64 and Midori128. It attracted a lot of attention of cryptanalyst since its release. For Midori64, the first meet-in-the-middle attack was proposed by Lin and Wu, which was published on the ToSC 2017 recently. The first impossible differential attack of Midori64 was presented by Chen et al. and Dong gave the first related-key differential attack. Guo et al. introduced an invariant space attack against full-round Midori64 in weak key setting, which was published in ToSC 2017 recently. However, for Midori128, there are only one impossible differential cryptanalysis result proposed by Chen et al. against 10-round reduced Midori128 and one related-key result by Gerault et al. in INDOCRYPT 2016. In this paper, we present a new impossible differential attack on Midori128 by using a new impossible differential proposed by Sasaki et al., we achieve 10-round impossible differential attack with the time complexity $2^{111}$ and 11-round impossible differential attack with the time complexity $2^{126.94}$ finally. This is the best single-key cryptanalytic result of Midori128 as far as we know. We should point out the our attacks do not threaten the security of full-round Midori128.

Evaluating web PKIs - A Survey

Tue, 11/14/2017 - 11:46
Certificate authorities serve as trusted parties to help secure web communications. They are a vital component for ensuring the security of cloud infrastructures and big data repositories. Unfortunately, recent attacks using mis-issued certificates show this model is severely broken. Much research has been done to enhance certificate management in order to create more secure and reliable cloud architectures. However, none of it has been widely adopted yet, and it is hard to judge which one is the winner. This chapter provides a survey with critical analysis on the existing proposals for managing public key certificates. This evaluation framework would be helpful for future research on designing an alternative certificate management system to secure the internet.

Collateral damage of Facebook Apps: an enhanced privacy scoring model

Tue, 11/14/2017 - 10:14
Establishing friendship relationships on Facebook often entails information sharing which is based on the social trust and implicit contract between users and their friends. In this context, Facebook offers applications (Apps) developed by third-party application providers (AppPs), which may grant access to users' personal data via Apps installed by their friends. Such access takes place outside the circle of social trust with the user not being aware whether a friend has installed an App collecting her data. In some cases, one or more AppPs may cluster several Apps and thus gain access to a collection of personal data. As a consequence privacy risks emerge. Previous research has mentioned the need to quantify privacy risks on Online Social Networks (OSNs). Nevertheless, most of the existing works do not focus on the personal data disclosure via Apps. Moreover, the problem of personal data clustering from AppPs has not been studied. In this work, we perform a general analysis of the privacy threats stemming from the personal data requested by Apps installed by the user’s friends from a technical and legal point of view. In order to assist users, we propose a model and a privacy scoring formula to calculate the amount of personal data that may be exposed to AppPs. Moreover, we propose algorithms that based on clustering, computes the visibility of each personal data to the AppPs.

Montgomery curves and their arithmetic: The case of large characteristic fields

Tue, 11/14/2017 - 04:53
Three decades ago, Montgomery introduced a new elliptic curve model for use in Lenstra's ECM factorization algorithm. Since then, his curves and the algorithms associated with them have become foundational in the implementation of elliptic curve cryptosystems. This article surveys the theory and cryptographic applications of Montgomery curves over non-binary finite fields, including Montgomery's x-only arithmetic and Ladder algorithm, x-only Diffie--Hellman, y-coordinate recovery, and 2-dimensional and Euclidean differential addition chains such as Montgomery's PRAC algorithm.

Security Analysis of a Dynamic Threshold Secret Sharing Scheme Using Linear Subspace Method

Mon, 11/13/2017 - 03:51
A dealer-free and non-interactive dynamic threshold secret sharing scheme has been proposed by Harn et.al., in 2015. In this scheme, a (t; n) secret sharing scheme in secret reconstruction phase can turn into a (m; n) scheme in secret reconstruction phase, where m is the number of participanting shareholders. It has been claimed that the secrecy of shares and the secrecy of the secret are unconditionally preserved if $m \in (t; 1 + t(t + 1)=2]$. This paper provides a security analysis of this scheme in two directions. Firstly, we show that this scheme does not have the dynamic property, i.e. any t + 1 released values are sufficient to reconstruct the secret, even the agreed updated threshold is larger. Secondly, we show that any t + 1 released values are sufficient to forge the released value of a non-participating shareholder. The technique that we enjoyed for our analysis is the linear subspace method, which basically measures the information leaked by the known parameters of the scheme by computing the dimension of the linear subspace spanned by these parameter. This method has shown to be capable of cryptanalysis of some secret sharing based schemes, whose security relies on keeping the coefficients of the underlying polynomial(s) secret.

The Strength of Weak Randomization: Efficiently Searchable Encryption with Minimal Leakage

Sat, 11/11/2017 - 17:28
Efficiently searchable and easily deployable encryption schemes enable an untrusted, legacy service such as a relational database engine to perform searches over encrypted data. The ease with which such schemes can be deployed on top of existing services makes them especially appealing in operational environments where encryption is needed but it is not feasible to replace large infrastructure components like databases or document management systems. Unfortunately all previously known approaches for efficiently searchable encryption are vulnerable to inference attacks where an adversary can use knowledge of the distribution of the data to recover the plaintext with high probability. In this paper, we present the first efficiently searchable, easily deployable database encryption scheme that is provably secure against inference attacks even when used with real, low-entropy data. Ours is also the only efficiently searchable construction that provides any provable security for protecting multiple related attributes (columns) in the same database. Using this ESE construction as a building block, we give an efficient construction for performing range queries over encrypted data. We implemented our constructions in Haskell and used them to query encrypted databases of up to 10 million records. In experiments with a local Postgres database and with a Google Cloud Platform database, the response time for our encrypted queries is not excessively slower than for plaintext queries. With the use of parallel query processing, our encrypted queries can achieve similar and in some cases superior performance to queries on the plaintext.

Non-malleable Randomness Encoders and their Applications

Sat, 11/11/2017 - 17:28
Non-malleable Codes (NMCs), introduced by Dziembowski, Peitrzak and Wichs (ITCS 2010), serve the purpose of preventing "related tampering" of encoded messages. The most popular tampering model considered is the $2$-split-state model where a codeword consists of 2 states, each of which can be tampered independently. While NMCs in the $2$-split state model provide the strongest security guarantee, despite much research in the area we only know how to build them with poor rate ($\Omega(\frac{1}{logn})$, where $n$ is the codeword length). However, in many applications of NMCs one only needs to be able to encode randomness i.e., security is not required to hold for arbitrary, adversarially chosen messages. For example, in applications of NMCs to tamper-resilient security, the messages that are encoded are typically randomly generated secret keys. To exploit this, in this work, we introduce the notion of "Non-malleable Randomness Encoders" (NMREs) as a relaxation of NMCs in the following sense: NMREs output a random message along with its corresponding non-malleable encoding. Our main result is the construction of a $2$-split state, rate-$\frac{1}{2}$ NMRE. While NMREs are interesting in their own right and can be directly used in applications such as in the construction of tamper-resilient cryptographic primitives, we also show how to use them, in a black-box manner, to build a $3$-split-state (standard) NMCs with rate $\frac{1}{3}$. This improves both the number of states, as well as the rate, of existing constant-rate NMCs.

Post-quantum IND-CCA-secure KEM without Additional Hash

Sat, 11/11/2017 - 17:27
With the gradual progress of NIST's post-quantum cryptography standardization, several practical post-quantum secure key encapsulation mechanism (KEM) schemes have been proposed. Generally, an IND-CCA-secure KEM is usually achieved by introducing an IND-CPA-secure (or OW-CPA-secure) public-key encryption (PKE) scheme, then applying some generic transformations to it. All these generic transformations are constructed in the random oracle model (ROM). To fully assess the post-quantum security, security analysis in the quantum random oracle model (QROM) is preferred. However, current works either lacked a QROM security proof or just followed Targhi and Unruh's proof technique (TCC-B 2016) and modified the original transformations by adding an additional hash to the ciphertext to achieve the QROM security. In this paper, by using a novel proof technique, we present QROM security reductions for two widely used generic transformations without suffering any ciphertext overhead. Meanwhile, the security bounds are much tighter than the ones derived by utilizing Targhi and Unruh's proof technique. Thus, our QROM security proofs not only provide a solid post-quantum security guarantee for previous KEM schemes, but also simplify the constructions and reduce the ciphertext sizes. We also provide QROM security reductions for Hofheinz-Hoevelmanns-Kiltz modular transformations (TCC 2017), which can help to obtain a variety of combined transformations with different requirements and properties.

Analysis of the Bitcoin UTXO set

Fri, 11/10/2017 - 14:39
Bitcoin relies on the Unspent Transaction Outputs (UTXO) set to efficiently verify new generated transactions. Every unspent out- put, no matter its type, age, value or length is stored in every full node. In this paper we introduce a tool to study and analyze the UTXO set, along with a detailed description of the set format and functionality. Our analysis includes a general view of the set and quantifies the difference between the two existing formats up to the date. We also provide an ac- curate analysis of the volume of dust and unprofitable outputs included in the set, the distribution of the block height in which the outputs where included, and the use of non-standard outputs.

Privately Constraining and Programming PRFs, the LWE Way

Fri, 11/10/2017 - 14:26
*Constrained* pseudorandom functions allow for delegating constrained'' secret keys that let one compute the function at certain authorized inputs---as specified by a constraining predicate---while keeping the function value at unauthorized inputs pseudorandom. In the *constraint-hiding* variant, the constrained key hides the predicate. On top of this, *programmable* variants allow the delegator to explicitly set the output values yielded by the delegated key for a particular set of unauthorized inputs. Recent years have seen rapid progress on applications and constructions of these objects for progressively richer constraint classes, resulting most recently in constraint-hiding constrained PRFs for arbitrary polynomial-time constraints from Learning With Errors~(LWE) [Brakerski, Tsabary, Vaikuntanathan, and Wee, TCC'17], and privately programmable PRFs from indistinguishability obfuscation (iO) [Boneh, Lewi, and Wu, PKC'17]. In this work we give a unified approach for constructing both of the above kinds of PRFs from LWE with subexponential $\exp(n^{\varepsilon})$ approximation factors. Our constructions follow straightforwardly from a new notion we call a *shift-hiding shiftable function*, which allows for deriving a key for the sum of the original function and any desired hidden shift function. In particular, we obtain the first privately programmable PRFs from non-iO assumptions.

Proposal for Protocol on a Quorum Blockchain with Zero Knowledge

Fri, 11/10/2017 - 13:37
In this paper, we present an implementation scheme of an RTGS on Quorum using the Solidity language. It is heavily inspired by the Schnorr signature protocol to verify the identity of the participants. We have implemented a distributed ledger solution for Delivery vs Payment that promises to offer increased efficiency and resilience. Our architecture mimics current market structure. For such needs, we added an extra layer of security that allows our solution to comply with the requirements of the regulator while enabling competitive actors to collaborate using the shared registry. It also leaves room for regulation, while still running in a decentralised way with coordinating agents. We use non-interactive zero-knowledge algorithms, which are cryptographic protocols with numerous applications in the fields of cryptocurrencies. They allow an agent to verify that another agent holds a specific information, while the latter never discloses this information. For the sake of our experimentations, we had to use very small integers in our protocols. These integers are too small to comply with current security standards in finance, although the architectural principles can be easily transposed with better performing protocols. We present suggestions to improve our proof of concept and our architecture in the last part.

Universally Composable Secure Two and Multi-party Computation in the Corruptible Tamper-Proof Hardware Token Model

Fri, 11/10/2017 - 12:30
In this work we introduce the corruptible token model. This model generalizes the stateless tamper-proof token model introduced by Katz (EUROCRYPT '07) and relaxes the trust assumption. Our improved model is motivated by the real-world practice of outsourcing hardware production to possibly untrusted manufacturers and allows tokens created by honest parties to be corrupted at the time of their creation. Assuming one-way functions, we show how to UC-securely realize the tamper-proof token functionality of Katz in the corruptible token model with $n$ stateless tokens assuming that the adversary corrupts at most $n-1$ of them. We then apply this transformation to existing two and MPC protocols to achieve a UC-secure 2PC/MPC protocol in the corruptible token model assuming only the existence of one-way functions. Finally, we further transform the above protocol to only use tokens of small size that take only short inputs. The technique in the last transformation can also be used to improve the assumption of UC-secure hardware obfuscation by Nayak et al. (NDSS '17) from collision-resistant hash functions to one-way functions, which can then be transformed into a protocol with $n$ corruptible tokens in our model.

Fairness in an Unfair World: Fair Multiparty Computation from public Bulletin Boards

Fri, 11/10/2017 - 12:06
Secure multiparty computation allows mutually distrusting parties to compute a function on their private inputs such that nothing but the function output is revealed. Achieving fairness --- that all parties learn the output or no one does -- is a long studied problem with known impossibility results in the standard model if a majority of parties are dishonest. We present a new model for achieving fairness in MPC against dishonest majority by using public bulletin boards implemented via existing infrastructure such as blockchains or Google's certificate transparency logs. We present both theoretical and practical constructions using either witness encryption or trusted hardware (such as Intel SGX). Unlike previous works that either penalize an aborting party or achieve weaker notions such as $\Delta$-fairness, we achieve complete fairness using existing infrastructure.

Enter the Hydra: Towards Principled Bug Bounties and Exploit-Resistant Smart Contracts

Fri, 11/10/2017 - 12:04
Vulnerability reward programs, a.k.a. bug bounties, are a popular tool that could help prevent software exploits. Today, however, they lack rigorous principles for setting bounty amounts and require high payments to attract economically rational hackers. Rather than claim bounties for serious bugs, hackers often sell or exploit them. We present the Hydra Framework, the first general, principled approach to modeling and administering bug bounties and boosting incentives for hackers to report bugs. The key idea is what we call an exploit gap, a program transformation that enables runtime detection of security-critical bugs. The Hydra Framework transforms programs via N-of-N-version programming (NNVP), a variant of classical N-version programming that executes multiple independent program instances. We apply the Hydra Framework to smart contracts, small programs that execute on blockchains. We show how Hydra contracts greatly amplify the power of bounties to incentivize bug disclosure by economically rational adversaries, establishing the first framework for economic evaluation of smart contract security. We also model powerful adversaries capable of bug withholding, exploiting race conditions in blockchains to claim bounties before honest users can. We present Submarine Commitments, a countermeasure of independent interest that conceals transactions on blockchains. We present a simple core Hydra Framework for Ethereum. We report the implementation of two Hydra contracts—an ERC20 token contract and a Monty-Hall-like game.

Secure Deduplication of Encrypted Data: Refined Model and New Constructions

Fri, 11/10/2017 - 12:03
Cloud providers tend to save storage via cross-user deduplication, while users who care about privacy tend to encrypt their files on client-side. Secure deduplication of encrypted data (SDoE) is an active research topic. In this paper, we propose a formal security model for this problem. We also propose two single-server SDoE protocols and prove their security in our model. We evaluate their deduplication effectiveness via simulations with realistic datasets.

Promise Zero Knowledge and its Applications to Round Optimal MPC

Fri, 11/10/2017 - 12:02
We devise a new partitioned simulation technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of promise zero knowledge (ZK) where the ZK property only holds against non-aborting verifiers. We show that unlike standard ZK, promise ZK can be realized in three rounds in the simultaneous-message model under standard assumptions. We demonstrate the following applications of our new technique: -> We construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard LWE and DDH. Previously, such protocols required sub-exponential-time hardness assumptions. -> We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for list coin-tossing'' -- a slight relaxation of coin-tossing that suffices for most conceivable applications -- based on injective one-way functions. This result generalizes to randomized input-less functionalities assuming polynomially hard LWE. Previously, four round MPC protocols required sub-exponential hardness assumptions and no multi-party three-round protocols with polynomial simulation were known for any relaxed security notions against malicious adversaries. In order to base security on polynomial-time standard assumptions, we also develop a new leveled rewinding security technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving non-malleability'' across different primitives. This technique may be of independent interest.