International Association
for Cryptologic Research

Peer-to-peer (P2P) systems such as BitTorrent and Bitcoin are susceptible to serious attacks from byzantine nodes that join as peers. Due to well-known impossibility results for designing P2P primitives in unrestricted byzantine settings, research has explored many adversarial models with additional assumptions, ranging from mild (such as pre-established PKI) to strong (such as the existence of common random coins). One such widely-studied model is the general-omission model, which yields simple protocols with good efficiency, but has been considered impractical or unrealizable since it artificially limits the adversary only to omitting messages. In this work, we study the setting of a synchronous network wherein peer nodes have CPUs equipped with a recent trusted computing mechanism called Intel SGX. In this model, we observe that the byzantine adversary reduces to the adversary in the general-omission model. As a first result, we show that by leveraging SGX features, we eliminate any source of advantage for a byzantine adversary beyond that gained by omitting messages, making the general-omission model realizable. Second, we present new protocols that improve the communication complexity of two fundamental primitives — reliable broadcast and common random coins (or beacons) — over the best-known results in the synchronous general-omission model, by utilizing SGX features. Our evaluation of 1000 nodes running on 40 DeterLab machines confirms theoretical efficiency claim.

Blockchains show promise as potential infrastructure for financial transaction systems. The security of blockchains today, however, relies critically on Proof-of-Work (PoW), which forces participants to waste computational resources. We present REM (Resource-Efficient Mining), a new blockchain mining framework that uses trusted hardware (Intel SGX). REM achieves security guarantees similar to PoW, but leverages the partially decentralized trust model inherent in SGX to achieve a fraction of the waste of PoW. Its key idea, Proof-of-Useful-Work (PoUW), involves miners providing trustworthy reporting on CPU cycles they devote to inherently useful workloads. REM flexibly allows any entity to create a useful workload. REM ensures the trustworthiness of these workloads by means of a novel scheme of hierarchical attestations that may be of independent interest.

To address the risk of compromised SGX CPUs, we develop a statistics-based formal security framework, also relevant to other trusted-hardware-based approaches such as Intel's Proof of Elapsed Time (PoET). We show through economic analysis that REM achieves less waste than PoET and variant schemes.

We implement REM and, as an example application, swap it into the consensus layer of Bitcoin core. The result is the first full implementation of an SGX-based blockchain. We experiment with four example applications as useful workloads for our implementation of REM, and report a computational overhead of $5-15\%$.

In the present paper, we propose an automatic search algorithm for optimal differential trails in SIMON-like ciphers. First, we give a more accurate upper bound on the differential probability of SIMON-like round function. It is shown that when the Hamming weight of the input difference $\alpha$, which is denoted by $wt(\alpha)$, is less than one half of the input size, the corresponding maximum differential probability of SIMON-like round function is less than or equal to $2^{-wt(\alpha)-1}$. Based on this, we adapt Matsui's algorithm and propose an efficient algorithm for searching for optimal differential trails. With the proposed algorithm, we find the provably optimal differential trails for $12$, $16$, $19$, $28$ and $37$ rounds of SIMON$32/48/64/96/128$. To the best of our knowledge, it is the first time that the provably optimal differential trails for SIMON$64$, SIMON$96$ and SIMON$128$ are reported. The provably optimal differential trails for $13$, $19$ and $25$ rounds of SIMECK$32/48/64$ are also found respectively, which confirm the results given by K$\ddot{o}$lbl et al. \cite{KolblR15}. Besides the optimal differential trails, we also find the $14$, $17$, $23$, $31$ and $41$-round differentials for SIMON$32/48/64/96/128$, and $14$, $21$ and $27$-round differentials for SIMECK$32/48/64$, respectively. As far as we know, these are the best differential distinguishers for SIMON and SIMECK so far. Compared with the approach based on SAT/SMT solvers used by K$\ddot{o}$lbl et al., our algorithm is more efficient and more practical to evaluate the security against differential cryptanalysis in the design of SIMON-like ciphers.

A $(t, s, v)$-all-or-nothing transform is a bijective mapping defined on $s$-tuples over an alphabet of size $v$, which satisfies the condition that the values of any $t$ input co-ordinates are completely undetermined, given only the values of any $s-t$ output co-ordinates. The main question we address in this paper is: for which choices of parameters does a $(t, s, v)$-all-or-nothing transform (AONT) exist? More specifically, if we fix $t$ and $v$, we want to determine the maximum integer $s$ such that a $(t, s, v)$-AONT exists. We mainly concentrate on the case $t=2$ for arbitrary values of $v$, where we obtain various necessary as well as sufficient conditions for existence of these objects. We consider both linear and general (linear or nonlinear) AONT. We also show some connections between AONT, orthogonal arrays and resilient functions.

A probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form "$x\in L$" by querying only few bits of the proof. A PCP of proximity (PCPP) has the additional feature of allowing the verifier to query only few bits of the input $x$, where if the input is accepted then the verifier is guaranteed that (with high probability) the input is close to some $x'\in L$.

Motivated by their usefulness for sublinear-communication cryptography, we initiate the study of a natural zero-knowledge variant of PCPP (ZKPCPP), where the view of any verifier making a bounded number of queries can be efficiently simulated by making the same number of queries to the input oracle alone. This new notion provides a useful extension of the standard notion of zero-knowledge PCPs. We obtain two types of results.

1. Constructions. We obtain the first constructions of query-efficient ZKPCPPs via a general transformation which combines standard query-efficient PCPPs with protocols for secure multiparty computation. As a byproduct, our construction provides a conceptually simpler alternative to a previous construction of honest-verifier zero-knowledge PCPs due to Dwork et al. (Crypto '92).

2. Applications. We motivate the notion of ZKPCPPs by applying it towards sublinear-communication implementations of commit-and-prove functionalities. Concretely, we present the first sublinear-communication commit-and-prove protocols which make a black-box use of a collision-resistant hash function, and the first such multiparty protocols which offer information-theoretic security in the presence of an honest majority.

The internal state of RC4 stream cipher is a permutation over ${\mathbb Z}_N$ and its state transition is effectively a transposition or swapping of two elements. How the randomness of RC4 state evolves due to its state transitions has been studied for many years. As the number of swaps increases, the state comes closer to a uniform random permutation. We call the burn-in period of RC4 state transition as the number of swaps required to make the state very close to uniform random permutation under some suitably defined distance measure. Earlier, Mantin in his Master's thesis (2001) has performed an approximate analysis of the burn-in period. In this paper, we perform a rigorous analysis of the burn-in period and in the process derive the exact distribution of the RC4 state elements at any stage.

Cost-aware cut-and-choose game is a fundamental technique that has many cryptographic applications. Best existing solutions of this game assumed for simplicity that the number of challenges is publicly known. This paper considers an extension of this game where the number of challenges can be picked probabilistically and hidden to the adversary. Although this small change leads to a linear program with infinitely many variables and constraints, we discover a surprising efficiency solver — using only O(n2) space and O(n2) time where n is the upper-bound on the number of challenges allowed in the strategy space. We then prove that n is bounded for any fixed cost ratio, implying the optimality of our solution extends to the strategy space that allow any number of challenges. As two interesting applications of our game solver, we demonstrate its value in constructing an actively secure two-party computation protocol and an optimal prefix-free code for encryptions.

Counter-cryptanalysis, the concept of using cryptanalytic techniques to detect cryptanalytic attacks, was first introduced by Stevens at CRYPTO 2013 with a hash collision detection algorithm. That is, an algorithm that detects whether a given single message is part of a colliding message pair constructed using a cryptanalytic collision attack on MD5 or SHA-1. The concept's utility was proven when it was used to expose the then-unknown cryptanalytic collision attack exploited by the Flame espionage supermalware.

So far there is a significant cost: to detect collision attacks against SHA-1 (respectively MD5) costs the equivalent of hashing the message 15 (respectively 224) times. In this paper we present a significant performance improvement for collision detection based on the new concept of unavoidable conditions. Unavoidable conditions are conditions that are necessary for all feasible attacks in a certain attack class. As such they can be used to quickly dismiss particular attack classes that may have been used in the construction of the message. To determine an unavoidable condition one must rule out any feasible variant attack where this condition might not be necessary, otherwise adversaries aware of counter-cryptanalysis could easily bypass this improved collision detection with a carefully chosen variant attack. We provide a formal model for unavoidable conditions for collision attacks on MD5-like compression functions.

Furthermore, based on a conjecture solidly supported by the current state of the art, we show how we can determine such unavoidable conditions for SHA-1. We have implemented the improved SHA-1 collision detection using such unavoidable conditions and which is about 16 times faster than without our unavoidable condition improvements. We have measured that overall our implemented SHA-1 with collision detection is only a factor 1.96 slower, on average, than SHA-1.

Traditionally, modes of Message Authentication Codes(MAC) such as Cipher Block Chaining (CBC) are instantiated using block ciphers or keyed Pseudo Random Permutations(PRP). However, one can also use domain preserving keyed Pseudo Random Functions(PRF) to instantiate MAC modes. The very first security proof of CBC-MAC, essentially modeled the PRP as a PRF. Until now very little work has been done to investigate the difference between PRP vs PRF instantiations. Only known result is the rather loose folklore PRP-PRF transition of any PRP based security proof, which looses a factor of $O(\frac{\sigma^2}{2^n})$ (domain of PRF/PRP is $\{0,1\}^n$ and adversary makes $\sigma$ many PRP/PRF calls in total). This loss is significant, considering the fact tight $\Theta(\frac{q^2}{2^n})$ security bounds have been known for PRP based EMAC and ECBC constructions (where $q$ is the total number of adversary queries). In this work, we show for many variations of encrypted CBC MACs (i.e. EMAC, ECBC, FCBC, XCBC and TCBC), random function based instantiation has a security bound $O(\frac{q\sigma}{2^n})$. This is a significant improvement over the folklore PRP/PRF transition. We also show this bound is optimal by providing an attack against the underlying PRF based CBC construction. This shows for EMAC, ECBC and FCBC, PRP instantiations are substantially more secure than PRF instantiations. Where as, for XCBC and TMAC, PRP instantiations are at least as secure as PRF instantiations.

Recently, a number of results have been published that show how to combine classical cryptanalysis with quantum algorithms, thereby (potentially) achieving considerable speed-ups. We follow this trend but add a novel twist by considering how to utilise side channel leakage in a quantum setting.

We show how to `rewrite' an existing algorithm for computing the rank of a key after a side channel attack, such that it results in an enumeration algorithm that produces batches of keys that can be tested using Grover's algorithm. This results in the first quantum key search that benefits from side channel information.

An implementation of a point multiplication function in an elliptic-curve cryptosystem can be attacked by fault injections in order to reveal the secret multiplier. A special kind of such an attack is the sign-change fault attack. Here the result of a point multiplication is changed in such a way that it is still a point on the curve. A well-known countermeasure against this kind of attack is to perform the point multiplication on a modular extension of the main curve by a small curve. Then the result is checked against the result of the same point multiplication recalculated on the small curve. The problem with this countermeasure is that the point at infinity on the small curve may be reached as an intermediate result with a non-negligible probability. In this case the comparison with the result on the small curve is either faulty or meaningless. We propose a variant of the modular extension countermeasure where the point at infinity is never reached as an intermediate result on the main or on the small curve.

With the advantage of not having to memorize long passwords, people are more interested in adopting face authentication for use with mobile devices. However, since facial images are widely shared in social networking sites, it becomes a challenging task to securely employ face authentication for web services to prevent attackers from impersonating the legal users by using the users’ online face photos. Moreover, existing face authentication protocols either require users to disclose their unencrypted facial images to the authentication server or require users to execute computationally expensive secure multiparty computation protocols. For mobile devices with limited computational power, this presents a problem that cannot be overlooked. In this paper, we present a novel privacy preserving face authentication system, called UFace, which has users take close-up facial images for authentication to prevent against impersonation attacks of users’ online facial images. UFace also guarantees that the facial images are only seen by the users and not by any other party (e.g., web service providers and authentication servers). UFace was implemented through two facets: an Android client application to obtain and encrypt the feature vector of the user’s facial image, and server code to securely authenticate a feature vector across multiple servers. The experimental results demonstrate that UFace not only can correctly authenticate a user, but also can be done within seconds which is significantly faster than any existing privacy preserving authentication protocol.

Event date: 10 December to 13 December 2017
Submission deadline: 15 July 2017
Notification: 1 September 2017

CSIRO Data61 is offering an exciting opportunity for a highly talented and motivated research scientist with an outstanding research track in Privacy Enhancing Technologies to join the Data Privacy team within the Cyber Physical Systems Program.

In this position, you will undertake world-leading research activities in the domain of online privacy with a focus on data-driven impactful research with real-life applications. This includes the development of privacy preserving algorithms for data release, analytics query and data processing in multiple strategic and industry-driven projects and the development of fundamental theoretical frameworks for efficient private data-centric multi-party collaboration and data sharing platforms.

You will lead a team of talented researchers with various experience levels and unique world leading profiles in Online Privacy within a vibrant research environment. The team is one of the worlds’ leading research groups in Privacy Technologies and aims to achieve the exciting and challenging goals of enabling the use of data in our digital economy while preserving individuals privacy. Research to be undertaken targets the most prestigious international publication venues and aims to educate Australia’s best undergraduate and postgraduate students.

Before you apply please view the full position description and selection criteria here: (http://www.csiro.au/~/media/Positions/2016/Data61/27141_Senior_Research_Scientist_CSOF6_PD.doc)

Location: Sydney, NSW

Salary: AU $106K to AU $124K plus up to 15.4% superannuation

Tenure: Indefinite

Reference: 27141

How to apply:

To apply for this position you will be required to submit your resume and cover letter, as one document, highlighting your experience as relevant to the role requirements. If your application proceeds to the next stage you may be asked to provide additional information.

Closing date for applications: 19 March 2017

Contact: Mohamed Ali Kaafar, dali (dot) kaafar (at) data61.csiro.au , https://research.csiro.au/ng/about-us/people/dali-kaafar/

More information: https://jobs.csiro.au/job/Sydney-NSW-Senior-Research-Scientist-Privacy-Preserving-Technologies/370805400

PhD studentships in the Centre for Doctoral Training in Cyber Security at Royal Holloway, University of London

The Centre for Doctoral Training in Cyber Security at Royal Holloway is now recruiting for the 2017/18 cohort, with a number of fully-funded PhD studentships to be awarded to qualified and eligible candidates, to start their post-graduate studies in cyber security in October 2017.

The four-year CDT programme is a mix of training and research activities, leading to a PhD thesis in cyber security. Possible research topics include the design and analysis of cryptographic algorithms and protocols; the design of security services for embedded systems; business information systems, telecommunication networks and critical infrastructure security; detection and analysis of malware; geopolitics of security; and the study of economics, psychology, design theory and sociology in the context of cyber security.

The CDT studentships provide an unparalleled opportunity for outstanding candidates to undertake research and training in a discipline that is both intellectually demanding and of wide applicability.

The CDT in Cyber Security, established in 2013, has currently 37 PhD students divided into four cohorts, working on topics ranging from embedded security to cybercrime, from cryptography to geopolitics of security, from software security to cyber economics.

CDT studentships cover college fees plus an annual stipend of £20,296, for four years. We welcome applications from candidates with undergraduate and masters\' qualifications in a wide range of disciplines, including, but not limited to, mathematics, computer science, engineering, geography, economics and sociology. Funding is provided by the EPSRC, so full studentships are available to UK residents only. Closing date for receiving applications is 30 April 2017.

Please visit Royal Holloway\'s CDT in Cyber Security webpage (https://www.royalholloway.ac.uk/isg/cybersecuritycdt/home.aspx) to learn more about its PhD programme, funding eligibility, and how to apply.

Closing date for applications: 30 June 2017

Contact: Professor Carlos Cid

Director, CDT in Cyber Security at Royal Holloway, University of London

cybersecuritycdt (at) royalholloway.ac.uk

More information: https://www.royalholloway.ac.uk/isg/prospectivestudents/cdtstudentships/cdt-studentships-in-cyber-security.aspx

Event date: 29 May 2017
Submission deadline: 10 March 2017
Notification: 10 April 2017

In this paper, we describe and analyze the security of the AES-GCM-SIV mode of operation, as defined in the CFRG specification \cite{CFRG}. This mode differs from the original GCM-SIV mode that was designed in \cite{GL2015} in two main aspects. First, the CTR encryption uses a 127-bit pseudo-random counter instead of a 95-bit pseudo-random value concatenated with a 32-bit counter. This construction leads to improved security bounds when encrypting short messages. In addition, a new key derivation function is used for deriving a fresh set of keys for each nonce. This addition allows for encrypting up to $2^{50}$ messages with the same key, compared to the significant limitation of only $2^{32}$ messages that were allowed with GCM-SIV (which inherited this same limit from AES-GCM). As a result, the new construction is well suited for real world applications that need a nonce-misuse resistant Authenticated Encryption scheme. We explain the limitations of GCM-SIV, which motivate the new construction, prove the security properties of AES-GCM-SIV, and show how these properties support real usages. Implementations are publicly available in \cite{ShayGit}. We remark that AES-GCM-SIV is already integrated into Google's BoringSSL library \cite{BoringSSL}, and its deployment for ticket encryption in QUIC \cite{QUIC} is underway.

Data loss is perceived as one of the major threats for cloud storage. Consequently, the security community developed several challenge-response protocols that allow a user to remotely verify whether an outsourced file is still intact. However, two important practical problems have not yet been considered. First, clients commonly outsource multiple files of different sizes, raising the question how to formalize such a scheme and in particular ensuring that all files can be simultaneously audited. Second, in case auditing of the files fails, existing schemes do not provide a client with any method to prove if the original files are still recoverable.

We address both problems and describe appropriate solutions. The first problem is tackled by providing a new type of "Proofs of Retrievability" scheme, enabling a client to check all files simultaneously in a compact way. The second problem is solved by defining a novel procedure called "Proofs of Recoverability", enabling a client to obtain an assurance whether a file is recoverable or irreparably damaged. Finally, we present a combination of both schemes allowing the client to check the recoverability of all her original files, thus ensuring cloud storage file recoverability.

After the trials of remote internet voting for local elections in 2011 and parliamentary elections in 2013, a number of local referendums has renewed interest in internet voting in Norway.

The voting scheme used in Norway is not quantum-safe and it has limited voter verifiability. In this case study, we consider how we can use fully homomorphic encryption to construct a quantum-safe voting scheme with better voter verifiability.

While fully homomorphic cryptosystems are not efficient enough for the the system we sketch to be implemented and run today, we expect future improvements in fully homomorphic encryption which may eventually make these techniques practical.

In this work we show the existence of special sets of inputs for which the sum of the images under SHA3 exhibits a symmetric property. We develop an analytical framework which accounts for the existence of these sets. The framework constitutes identification of a generic property of iterated SPN based functions pertaining to the round-constant addition and combining it with the notion of $m-$fold vectorial derivatives for differentiation over specially selected subspaces. Based on this we propose a new distinguisher called SymSum for the SHA3 family which penetrates up to 9 rounds and outperforms the ZeroSum distinguisher by a factor of four. Interestingly, the current work is the first analysis of SHA3/Keccak that relies on round-constants but is independent of their Hamming-weights.