International Association
for Cryptologic Research

Protecting software from malware injection is the holy grail of modern computer security. Despite intensive efforts by the scientific and engineering community, the number of successful attacks continues to increase.

We have a breakthrough novel approach to provably detect malware injection. The key idea is to use the very insertion of the malware itself to allow for the systems to detect it. This is, in our opinion, close in spirit to the famous Heisenberg Uncertainty Principle. The attackers, no matter how clever, no matter when or how they insert their malware, change the state of the system they are attacking. This fundamental idea is a game changer. And our system does not rely on heuristics; instead, our scheme enjoys the unique property that it is proved secure in a formal and precise mathematical sense and with minimal and realistic CPU modification achieves strong provable security guarantees. Thus, we anticipate our system and formal mathematical security treatment to open new directions in software protection.

We initiate the study of provably secure remote memory attestation. We present two protocols offering various efficiency and security trade-offs that detect the presence of injected malicious code in remotely- stored heap memory. While our solutions offer protection only against a specific class of attacks, our novel formal security definitions are general enough to cover a wide range of attacks and settings, and should be useful for further research on the subject.

Industry-funded PhD student at the crossroads of security and cryptography with an emphasis on efficient implementations and protocol design, notably for payment applications. Ideally, the successful applicant will have solid programming and maths skills and a creative mindset.

SIMECK is a family of 3 lightweight block ciphers designed by Yang et al. They

follow the framework used by Beaulieu et al. from the United States National Security Agency

(NSA) to design SIMON and SPECK. A cipher in this family with K-bit key and N-bit block is

called SIMECKN=K.We show that the security of this block cipher against linear cryptanalysis

is not as good as its predecessors SIMON. More precisely, while the best known linear attack

for SIMON32/64, using algorithm 1 of Matsui, covers 13 rounds we present a linear attack in

this senario which covers 14 rounds of SIMECK32/64. Similarly, using algorithm 1 of Matsui,

we present attacks on 19 and 22 rounds of SIMECK48/96 and SIMECK64/128 respectively,

compare them with known attacks on 16 and 19 rounds SIMON48/96 and SIMON64/128

respectively. In addition, we use algorithm 2 of Matsui to attack 18, 23 and 27 rounds of

SIMECK32/64, SIMECK48/96 and SIMECK64/128 respectively, compare them with known

attacks on 18, 19 and 21 rounds SIMON32/64, SIMON48/96 and SIMON64/128 respectively.

Side-channel attacks have been a real threat against many critical embedded systems that rely on cryptographic algorithms as their security engine. A commonly used algorithmic countermeasure, random masking, incurs large execution delay and resource overhead. The other countermeasure, operation shuffling or permutation, can mitigate side-channel leakage effectively with minimal overhead. In this paper, we target utilizing the independence among operations in cryptographic algorithms and randomizing their execution order. We design a tool to automatically detect such independence between statements at the source code level and devise an algorithm for automatic operation shuffling. We test our algorithm on the new SHA3 standard, Keccak. Results show that the tool has effectively implemented operation-shuffling to reduce the side-channel leakage significantly, and therefore can guide automatic secure cryptographic software implementations against differential power analysis attacks.

Cryptographic accumulators are a tool for compact set representation and secure set membership proofs. When an element is added to a set by means of an accumulator, a membership witness is generated. This witness can later be used to prove the membership of the element. Typically, the membership witness has to be synchronized with the accumulator value, and to be updated every time another element is added to the accumulator. In this work we propose an accumulator that, unlike any prior scheme, does not require strict synchronization.

In our construction a membership witness needs to be updated only a logarithmic number times in the number of subsequent element additions. Thus, an out-of-date witness can be easily made current. Vice versa, a verifier with an out-of-date accumulator value can still verify a current membership witness. These properties make our accumulator construction uniquely suited for use in distributed applications, such as blockchain-based public key infrastructures.

In this paper we investigate relations between several masking schemes. We show that the Ishai--Sahai--Wagner private circuits construction is closely related to Threshold Implementations and the Trichina gate. The implications of this observation are manifold. We point out a higher-order weakness in higher-order Threshold Implementations, suggest a mitigation and provide new sharings that use a lower number of input shares.

We consider randomized encodings (RE) that enable encoding a Turing machine Pi and input x into its ``randomized encoding\'\' \\hat{Pi}(x) in sublinear, or even polylogarithmic, time in the running-time of Pi(x), independent of its output length. We refer to the former as sublinear RE and the latter as compact RE. For such efficient RE, the standard simulation-based notion of security is impossible, and we thus consider a weaker (distributional) indistinguishability-based notion of security: Roughly speaking, we require indistinguishability of \\hat{Pi}_0(x_0) and \\hat{Pi}_0(x_1) as long as Pi_0,x_0 and Pi_1,x_1 are sampled from some distributions such that Pi_0(x_0),Time(Pi_0(x_0)) and Pi_1(x_1),Time(Pi_1(x_1)) are indistinguishable.

We first observe that compact RE is equivalent to a variant of the notion of indistinguishability obfuscation (iO)---which we refer to as puncturable iO---for the class of Turing machines without inputs. For the case of circuits, puncturable iO and iO are equivalent (and this fact is implicitly used in the powerful ``punctured program\'\' paradigm by Sahai and Waters [SW13]).

We next show the following:

- Impossibility in the Plain Model: Assuming the existence of subexponentially secure one-way functions, subexponentially-secure sublinear RE does not exists. (If additionally assuming subexponentially-secure iO for circuits we can also rule out polynomially-secure sublinear RE.) As a consequence, we rule out also puncturable iO for Turing machines (even those without inputs).

- Feasibility in the CRS model and Applications to iO for circuits: Subexponentially-secure sublinear RE in the CRS model and one-way functions imply iO for circuits through a simple construction generalizing GGM\'s PRF construction. Additionally, any compact (even with sublinear compactness) functional encryption essentially directly yields a sublinear RE in the CRS model, and as such we get an alternative, modular, and simpler proof of the results of [AJ15,BV15] showing that subexponentially-secure sublinearly compact FE implies iO.

- Applications to iO for Unbounded-input Turing machines: Subexponentially-secure compact RE for natural restricted classes of distributions over programs and inputs (which are not ruled out by our impossibility result, and for which we can give candidate constructions) imply iO for unbounded-input Turing machines. This yields the first construction of iO for unbounded-input Turing machines that does not rely on (public-coin) differing-input obfuscation.

Simeck is a new lightweight block cipher design based on

combining the Simon and Speck block cipher. While the design allows a

smaller and more efficient hardware implementation, its security margins are not well understood. The lack of design rationals of its predecessors further leaves some uncertainty on the security of Simeck.

In this work we give a short analysis of the impact of the design changes by comparing the lower bounds for differential and linear characteristics with Simon. We also give a comparison of the effort of finding those bounds, which surprisingly is significant less for Simeck while covering a larger number of rounds.

Furthermore, we provide new differentials for Simeck which can cover

more rounds compared to previous results on Simon. Based on this we

mount key recovery attacks on 19/26/33 rounds of Simeck32/48/64,

which also give insights on the reduced key guessing effort due to the

different set of rotation constants.

In an implicit authentication system, a user profile is used as an additional factor to strengthen the authentication of mobile users. The profile consists of features that are constructed using the history of user actions on her mobile device over time. The profile is stored on the server and is used to authenticate an access request originated from the device at a later time. An access request will include a vector of recent measurements of the features on the device, that will be subsequently matched against the features stored at the server, to accept or reject the request. The features however include private information such as user location or web sites that have been visited. We propose a privacy-preserving implicit authentication system that achieves implicit authentication without revealing information about the usage profiles of the users to the server. We propose an architecture, give a formal security model and a construction with provable security in two settings where: (i) the device follows the protocol, and (ii) the device is captured and behaves maliciously.

We describe a methods for generating parameter sets and calculating security estimates for NTRUEncrypt. Analyses are provided for the standardized product-form parameter sets from IEEE 1363.1-2008 and for the NTRU Challenge parameter sets.

Mobile application spoofing is an attack where a malicious mobile application

mimics the visual appearance of another one. If such an attack is successful,

the integrity of what the user sees as well as the confidentiality of what she

inputs into the system can be violated by the adversary. A common example of

mobile application spoofing is a phishing attack where the adversary tricks the

user into revealing her password to a malicious application that resembles the

legitimate one.

In this work, we propose a novel approach for addressing mobile application

spoofing attacks by leveraging the visual similarity of application screens. We

use deception rate as a novel metric for measuring how many users would confuse

a spoofing application for the genuine one. We conducted a large-scale online

study where participants evaluated spoofing samples of popular mobile

applications. We used the study results to design and implement a prototype

spoofing detection system, tailored to the estimation of deception rate for

mobile application login screens.

Storage requirements for visual data have been increasing in recent years, following the emergence of many new highly interactive multimedia services and applications for both personal and corporate use. This has been a key driving factor for the adoption of cloud-based data outsourcing solutions. However, outsourcing data storage to the Cloud also leads to new challenges that must be carefully addressed, especially regarding privacy. In this paper we propose a secure framework for outsourced privacy-preserving storage and retrieval in large image repositories. Our proposal is based on IES-CBIR, a novel Image Encryption Scheme that displays Content-Based Image Retrieval properties. Our solution enables both encrypted storage and searching using CBIR queries while preserving privacy. We have built a prototype of the proposed framework, formally analyzed and proven its security properties, and experimentally evaluated its performance and precision. Our results show that IES-CBIR is provably secure, allows more efficient operations than existing proposals, both in terms of time and space complexity, and enables more reliable practical application scenarios.

The aim of this work is to find large S-Boxes, typically operating on 8

bits, having both good cryptographic properties and a low implementation

cost. Such S-Boxes are suitable building-blocks in many lightweight

block ciphers since they may achieve a better security level than

designs based directly on smaller S-Boxes. We focus on S-Boxes

corresponding to three rounds of a balanced Feistel and of a balanced

MISTY structure, and generalize the recent results by Li and Wang on the

best differential uniformity and linearity offered by such a

construction. Most notably, we prove that Feistel networks supersede

MISTY networks for the construction of 8-bit permutations. Based on

these results, we also provide a particular instantiation of an 8-bit

permutation with better properties than the S-Boxes used in several

ciphers, including Robin, Fantomas or CRYPTON.

It has long been known (Shoup and Gennaro 1998) that non-interactive proofs in the Random Oracle model that rely on rewinding extractors can be problematic.

Recent results by Seurin and Treger and Bernhard et al. formally confirmed such limitations for proofs derived from the Schnorr protocol via the Fiat-Shamir transform.

The limitations relate to the concept of adaptive proofs where an extractor needs to recover witnesses from proofs selected adaptively, as opposed to the standard setting where the extractor needs to work just for one proof.

Their main result is a separation between these two settings: under the one-more discrete log assumption, no efficient adaptive extractor can recover all witnesses from non-interactive Schnorr proofs (selected adaptively).

In this paper we generalize, strengthen and extend these results.

First we show that the above separation result holds for generic Sigma-protocols under the natural generalization of the one-more dlog assumption.

Next, we strengthen the theorem by weakening the hypothesis.

Our new assumption, which we call Sigma-one-wayness, says that a dishonest verifier in a single execution of an interactive Sigma protocol cannot recover the witness.

This assumption is incomparable to zero-knowledge, as we will explain.

The main result of this paper clarifies the relation between adaptive proofs of knowledge (with rewinding) and other existing notions.

Bernhard et al. introduced adaptive proofs as a new concept lying

between proofs of knowledge (PoKs, with a rewinding extractor) and

straight-line extractable proofs. They showed a separation between PoKs and

adaptive proofs but left open the question whether adaptive proofs are always

straight-line.

Our result implies that all adaptive proofs admit a straight-line extractor

against the honest prover. This means that adaptive proofs are not a new class

of proofs after all but simply another way to describe proofs with

straight-line extractors.

Finally, we ask ourselves whether the result could be extended to a

reduction to one-wayness of the function concerned -- for Schnorr, this would

mean solving the discrete logarithm (DLOG) problem. Our answer is negative: if

there is any generic metareduction from adaptivity of Fiat-Shamir-Schnorr to

DLOG then there is also a meta-metareduction breaking DLOG directly.

This paper offers a new version of the hHB protocol denoted Light-hHB. This proposal uses the same framework as hHB, that is a two stages protocol: the first one for the establishment of a session key between the reader and the tag and the second one similar to HB+. We also introduce in this paper a novel and lightweight key exchange protocol inspired by the BB84 protocol named the non-quantum key exchange protocol. With the use of a practical implementation of the latter protocol in the first stage of Light-hHB, the transmission cost is drastically reduced compared to the one of hHB, which is its main drawback. In the context of RFID tags, Light-hHB is significantly more practical than hHB and achieves the same security goals.

In this paper, we first present a new class of code based public key cryptosystem(PKC) based on Reed-Solomon code over $\\mathbb{F}_{2^m}$, referred to as K(XVI)SE(1)PKC.

We then present a new class of quadratic multivariate PKC, K(XVI)SE(2)PKC, based on cyclic code over $\\mathbb{F}_2$.

We show that both K(XVI)SE(1)PKC and K(XVI)SE(2)PKC can be secure against the various linear transformation attacks such as Gr\\\"obner bases attack due to a non-linear structure introduced to the ciphertexts.

Namely, thanks to the non-linear transformation introduced in the construction of K(XVI)SE(1)PKC and K(XVI)SE(2)PKC the ciphertexts can be made very secure against the various sorts of linear transformation attacks such as Gr\\\"obner bases attack, although the degree of the multivariate polynomial is all degree 1.

A new scheme presented in this paper that transforms message variables in order to realize non-linear transformations, K(I)TS, would yield a brand-new technique in the field of both code based PKC and multivariate PKC, for much improving the security.

We shall show that the K(XVI)SE(1)PKC can be effectively constructed based on the Reed-Solomon code over $\\mathbb{F}_{2^8}$, extensively used in the present day storage systems

or the various digital transmission systems.

We investigate new constructions of n-circular counterexamples with a focus on the case of n=2. We have a particular interest in what qualities a cryptosystem must have to be able to separate such circular security from IND-CPA or IND-CCA security. To start, we ask whether there is something special about the asymmetry in bilinear groups that is inherent in the works of ABBC10 and CGH12 or whether it is actually the bilinearity that matters. As a further question, we explore whether such counterexamples are derivable from other

assumptions such as the Learning with Errors (LWE) problem. If it were difficult to find such counterexamples, this might bolster are confidence in using 2-circular encryption as a method of bootstrapping Fully Homomorphic Encryption systems that are based on lattice assumptions.

The results of this paper broadly expand the class of assumptions under which we can build 2-circular counterexamples. We first show for any constant k >= 2 how to build counterexamples from a bilinear group under the decision k-linear assumption. Recall that the decision k-linear assumption becomes progressively weaker as k becomes larger. This means that we can instantiate counterexamples

from symmetric bilinear groups and shows that asymmetric groups do not have any inherently special property needed for this problem.

We then show how to create 2-circular counterexamples from the Learning with Errors problem. This extends the reach of these systems beyond bilinear groups and obfuscation.

We present here optimized implementations of the MAKWA password hashing

function on an AMD Radeon HD 7990 GPU, and compare its efficiency with an Intel

i7 4770K CPU for systematic dictionary attacks. We find that the GPU seems to

get more hashing done for a given budget, but not by a large amount (the GPU is less

than twice as efficient as the CPU). Raising the MAKWA modulus size to 4096 bits,

instead of the default 2048 bits, should restore the balance in favour of the CPU. We

also find that power consumption, not hardware retail price, is likely to become the

dominant factor for industrialized, long-term attacking efforts.

Statistical analysis of attacks on symmetric ciphers often require assuming the normal behaviour of a test statistic.

Typically such an assumption is made in an asymptotic sense. In this work, we consider concrete versions of some important

normal approximations that have been made in the literature. To do this, we use the Berry-Ess\\\'{e}en theorem to derive

explicit bounds on the approximation errors. Analysing these error bounds in the cryptanalytic context throws up several

surprising results. One important implication is that this puts in doubt the applicability of the order statistics

based approach for analysing key recovery attacks on block ciphers. This approach has been earlier used to obtain several

results on the data complexities of (multiple) linear and differential cryptanalysis. The non-applicability of the order

statistics based approach puts a question mark on the data complexities obtained using this approach. Fortunately, we

are able to recover all of these results by utilising the hypothesis testing framework. Detailed consideration of the

error in normal approximation also has implications for $\\chi^2$ and the log-likelihood ratio (LLR) based test statistics.

The normal approximation of the $\\chi^2$ test statistics has some serious and counter-intuitive restrictions. One such

restriction is that for multiple linear cryptanalysis as the number of linear approximations grows so does the requirement

on the number of plaintext-ciphertext pairs for the approximation to be proper. The issue of satisfactorily addressing the

problems with the application of the $\\chi^2$ test statistics remains open. For the LLR test statistics, previous work

used a normal approximation followed by another approximation to simplify the parameters of the normal approximation. We

derive the error bound for the normal approximation which turns out to be difficult to interpret. We show that the approximation

required for simplifying the parameters restricts the applicability of the result. Further, we argue that this approximation

is actually not required. More generally, the message of our work is that all cryptanalytic attacks should properly derive and

interpret the error bounds for any normal approximation that is made.