International Association
for Cryptologic Research

In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for post-quantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation on various platforms, from desktop CPUs to micro-controllers and FPGAs, and more recent papers have also considered its security against certain types of physical attacks, notably fault injection and cache attacks. We turn to more traditional side-channel analysis, and describe several attacks that can yield a full key recovery.

We first identify a serious source of leakage in the rejection sampling algorithm used during signature generation. Existing implementations of that rejection sampling step, which is essential for security, actually leak the ``relative norm'' of the secret key. We show how an extension of an algorithm due to Howgrave-Graham and Szydlo can be used to recover the key from that relative norm, at least when the absolute norm is easy to factor (which happens for a significant fraction of secret keys). We describe how this leakage can be exploited in practice both on an embedded device (an 8-bit AVR microcontroller) using electromagnetic analysis (EMA), and a desktop computer (recent) Intel CPU running Linux) using branch tracing. The latter attack has been mounted against the open source VPN software strongSwan.

We also show that other parts of the BLISS signing algorithm can leak secrets not just for a subset of secret keys, but for 100% of them. The BLISS Gaussian sampling algorithm in strongSwan is intrinsically variable time. This would be hard to exploit using a noisy source of leakage like EMA, but branch tracing allows to recover the entire randomness and hence the key: we show that a single execution of the strongSwan signature algorithm is actually sufficient for full key recovery. We also describe a more traditional side-channel attack on the sparse polynomial multiplications carried out in BLISS: classically, multiplications can be attacked using DPA; however, our target 8-bit AVR target implementation uses repeated shifted additions instead. Surprisingly, we manage to obtain a full key recovery in that setting using integer linear programming from a single EMA trace.

Fully Homomorphic Encryption (FHE) schemes are a powerful tool that allows arbitrary computations on encrypted data. This makes them a promising tool for a variety of use cases that require outsourcing the computation on privacy-sensitive data to untrusted parties. FHE schemes today operate over finite fields, while many use cases call for natural or even real numbers, requiring appropriate encoding of the data into the plaintext space supported by the encryption scheme. However, the choice of encoding can tremendously impact the overall effort of the computation on the encrypted data. Surprisingly, although the question of selecting the encoding is quite natural and arises immediately in practice, a comprehensive analysis is still missing.

In this work, we formally and experimentally investigate this question for applications that operate over integers and rational numbers based on a selection of natural metrics: the number of finite field additions, the number of finite field multiplications, and the multiplicative depth. Our results are partly constructive and partly negative: We show that for the first two metrics, an optimal choice does exist and we state it explicitly. However, we show likewise that regarding multiplicative depth, the parameters need to be chosen specific to the use-case, as there is no global optimum. Still, we show exactly how one can choose the best encoding depending on the use-case.

Parallel versions of collision search algorithms require a significant amount of memory to store a proportion of the points computed by the pseudo-random walks. Implementations available in the literature use a hash table to store these points to allow fast memory access. We propose to replace the traditional hash table by a radix tree structure, allowing both look-up and insertion in a single operation. We provide theoretical and experimental evidence that memory access is an important factor in determining the runtime of our algorithm. Our benchmarks indicate that our algorithm achieves linear parallel performance.

In the present day, AES is one the most widely used and most secure Encryption Systems prevailing. So, naturally lots of research work is going on to mount a significant attack on AES. Many different forms of Linear and differential cryptanalysis have been performed on AES. Of late, an active area of research has been Algebraic Cryptanalysis of AES, where although fast progress is being made, there are still numerous scopes for research and improvement. One of the major reasons behind this being that algebraic cryptanalysis mainly depends on I/O relations of the AES S- Box (a major component of the AES). As, already known, that the key recovery algorithm of AES can be broken down as an MQ problem which is itself considered hard. Solving these equations depends on our ability reduce them into linear forms which are easily solvable under our current computational prowess. The lower the degree of these equations, the easier it is for us to linearlize hence the attack complexity reduces. The aim of this paper is to analyze the various relations involving small number of monomials of the AES S- Box and to answer the question whether it is actually possible to have such monomial equations for the S- Box if we restrict the degree of the monomials. In other words this paper aims to study such equations and see if they can be applicable for AES.

In CRYPTO 2017, Mennink and Neves showed almost n-bit security for a dual version of EWCDM. In this paper we describe a birthday attack on this construction which violates their claim.

An internet user wanting to share observed content is typically restricted to primitive techniques such as screenshots, web caches or share button-like solutions. These acclaimed proofs, however, are either trivial to falsify or require trust in centralized entities (e.g., search engine caches).

This motivates the need for a seamless and standardized internet-wide non-repudiation mechanism, allowing users to share data from news sources, social websites or financial data feeds in a provably secure manner.

Additionally, blockchain oracles that enable data-rich smart contracts typically rely on a trusted third party (e.g., TLSNotary or Intel SGX). A decentralized method to transfer web-based content into a permissionless blockchain without additional trusted third party would allow for smart contract applications to flourish.

In this work, we present TLS-N, the first TLS extension that provides secure non-repudiation and solves both of the mentioned challenges. TLS-N generates non-interactive proofs about the content of a TLS session that can be efficiently verified by third parties and blockchain based smart contracts. As such, TLS-N increases the accountability for content provided on the web and enables a practical and decentralized blockchain oracle for web content. TLS-N is compatible with TLS 1.3 and adds a minor overhead to a typical TLS session. When a proof is generated, parts of the TLS session (e.g., passwords, cookies) can be hidden for privacy reasons, while the remaining content can be verified.

Practical demonstrations can be found at https://tls-n.org/.

A major challenge in computer security is about establishing the trustworthiness of remote platforms. Remote attestation is the most common approach to this challenge. It allows a remote platform to measure and report its system state in a secure way to a third party. Unfortunately, existing attestation solutions either provide low security, as they rely on unrealistic assumptions, or are not applicable to commodity low-cost and resource-constrained devices, as they require custom secure hardware extensions that are difficult to adopt across IoT vendors. In this work, we propose a novel remote attestation scheme, named Boot Attestation, that is particularly optimized for low-cost and resource-constrained embedded devices. In Boot Attestation, software integrity measurements are immediately committed to during boot, thus relaxing the traditional requirement for secure storage and reporting. Our scheme is very light on cryptographic requirements and storage, allowing efficient implementations, even on the most low-end IoT platforms available today. We also describe extensions for more flexible management of ownership and third party (public-key) attestation that may be desired in fully Internet-enabled devices. Our scheme is supported by many existing off-the-shelf devices. To this end, we review the hardware protection capabilities for a number of popular device types and present implementation results for two such commercially available platforms.

In the present paper, we analyze the security of SIMON-like ciphers against linear cryptanalysis. First, an upper bound is derived on the squared correlation of SIMON-like round function. It is shown that the upper bound on the squared correlation of SIMON-like round function decreases with the Hamming weight of output mask increasing. Based on this, we derive an upper bound on the squared correlation of linear trails for SIMON and SIMECK, which is $2^{-2R+2}$ for any $R$-round linear trail. We also extend this upper bound to SIMON-like ciphers. Meanwhile, an automatic search algorithm is proposed, which can find the optimal linear trails in SIMON-like ciphers under the Markov assumption. With the proposed algorithm, we find the provably optimal linear 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 linear trails for SIMON$64$, SIMON$96$ and SIMON$128$ are reported. The provably optimal linear trails for $13$, $19$ and $25$ rounds of SIMECK$32/48/64$ are also found respectively. Besides the optimal linear trails, we also find the $23$, $31$ and $41$-round linear hulls for SIMON$64/96/128$, and $13$, $21$ and $27$-round linear hulls for SIMECK$32/48/64$. As far as we know, these are the best linear hull distinguishers for SIMON and SIMECK so far. Compared with the approach based on SAT/SMT solvers in \cite{KolblLT15}, our search algorithm is more efficient and practical to evaluate the security against linear cryptanalysis in the design of SIMON-like ciphers.

We study the quantum query complexity of finding a collision for a function $f$ whose outputs are chosen according to a non-uniform distribution $D$. We derive some upper bounds and lower bounds depending on the min-entropy and the collision-entropy of $D$. In particular, we improve the previous lower bound by Ebrahimi, Tabia, and Unruh from $\Omega(2^{k/9})$ to $\Omega(2^{k/5})$ where $k$ is the min-entropy of $D$.

Internet of things (IOT) is the term used to describe a world in which the things interact with other things through internet connection or communication means, share the information together and or people and deliver a new class of capabilities, application and services; the world in which all things and heterogeneous devices are addressable and controllable. Wireless Sensor Networks (WSN) play an important role in such an environment, since they include a wide application field. Researchers are already working on how to integrate WSN better into the IoT environment. One aspect of it is the security aspect of the integration. In 2014, Turkanovi´c proposed a lightweight user authentication and key agreement protocol for heterogeneous WSN(HWSN) based on the internet of things concept. In this scheme, remote user can access a single desired sensor node from the WSN without the necessity of firstly connecting with a gateway node (GWN). Moreover, this scheme is lightweight because it based on a simple symmetric cryptography and it uses simple hash and XOR computations. Turkanovi´c et al.'s scheme had some security shortages and it was susceptible to some security attacks. Recently Sabzinejad Farash et al. proposed an efficient user authentication and key agreement scheme for HWSN tailored for the Internet of Things environment based on Turkanovi´c et al.'s scheme. Although their scheme is efficient, we found out that this scheme is vulnerable to some cryptographic attacks. In this paper, we demonstrate some security weaknesses of the Sabzinejad Farash et al.’s scheme and then we propose an improved and secure mutual authentication and key agreement scheme.

Event date: 13 October to 15 October 2017
Submission deadline: 15 July 2017
Notification: 30 August 2017

The Hardware Security group at Virginia Tech has an open position for a post-doctoral scholar in energy-efficient cryptography, in support of recent new projects. The Internet of Things needs a huge amount of tiny computers, and many of them will be powered in a sustainable manner, such as through harvested energy sources. The project objective is to investigate and demonstrate how such energy-constrained devices can support secure and full Internet connectivity.

We are looking for a candidate with the following qualifications.

• Solid background in cryptographic engineering, covering protocols and algorithms.
• Experience with development of embedded software and/or hardware, including toolchain and design methodology.
• Effective communicator and team leader for a group of PhD students.
• Experience with energy harvesting technologies, intermittently powered computers and design across the hardware/software interface is a plus.

The Hardware Security group at Virginia Tech covers design, optimization and tamper-resistant implementation of cryptographic protocols and related applications. Recent projects include a fault-resistant microprocessor ASIC, side-channel resistant software synthesis, and novel primitives for hardware security.

To apply send your CV to the contact below. Include your publication list, a statement of research interest and objectives, and contact information for two references. Applications will be reviewed on an ongoing basis until the position is filled.

Closing date for applications: 30 September 2017

Contact: Prof. Patrick Schaumont (schaum (at) vt.edu)

More information: http://rijndael.ece.vt.edu/schaum

The University of Bergen in Norway is currently seeking candidates for four open positions as Ph.D. students. The advertised field of research for the positions is computer security, but we are particularly interested in good candidates in cryptography.

Closing date for applications: 1 July 2017

Contact: Håvard Raddum, Section Leader, Simula@UiB, email: haavardr (at) simula.no

or

Tor Helleseth, Professor, Dept. of Informatics, email: Tor.Helleseth (at) ii.uib.no

More information: https://www.jobbnorge.no/en/available-jobs/job/139151/phd-position-in-computer-security-4-positions

Cryptography, Security & Privacy Research Group at Koç University has multiple openings at every level. All accepted applicants will receive competitive scholarships including tuition waiver, housing, monthly stipend, computer, travel support, etc.

• For more information about joining our group and scholarship opportunities, visit

  https://crypto.ku.edu.tr/join

• For applying online, and questions about the application-process for M.Sc. and Ph.D. positions, visit

  https://gsse.ku.edu.tr/en/admissions/application-requirements/

  All applications must be completed online with all the required documents. Deadline is end of June.

• For postdoctoral researcher positions, contact Asst. Prof. Alptekin Küpçü directly, including full CV, sample publications, a research proposal, and 2-3 reference letters sent directly by the referees. Application and starting dates are flexible.

  http://home.ku.edu.tr/~akupcu

Closing date for applications: 31 August 2017

Contact: gsse (at) ku.edu.tr

More information: https://crypto.ku.edu.tr/

We present “Ouroboros Praos”, a new proof-of-stake blockchain protocol that provides, for the first time, a robust distributed ledger that is provably secure in the semi-synchronous adversarial setting, i.e., assuming a delay \Delta in message delivery which is unknown to protocol participants, and fully adaptively secure, i.e., the adversary can choose to corrupt any participant of an ever evolving population of stakeholders at any moment as long the stakeholder distribution maintains an honest majority of stake at any given time. To achieve that, our protocol puts to use forward secure digital signatures and a new type of verifiable random functions that maintains unpredictability under malicious key generation, a property we introduce and instantiate in the random oracle model. Our security proof entails a combinatorial analysis of a class of forkable strings tailored to semi-synchronous blockchains that may be of independent interest in the context of security analysis of blockchain protocols.

Silicon Physical Unclonable Functions (PUFs) have been proposed as an emerging hardware security primitive in various security applications such as device identification, authentication, and cryptographic key generation. Current so-called `strong' PUFs, which allow a large challenge response space, are compositions of Arbiter PUFs (APUFs), e.g. the $x$-XOR APUF. Wide-scale deployment of state-of-the-art compositions of APUFs, however, has stagnated due to various mathematical and physical attacks leading to software models that break the unclonability property of PUFs. The current state-of-the-art attack by Becker, CHES 2015, shows that the XOR APUF can be broken by modeling its APUF components separately thanks to CMA-ES, a machine learning algorithm, based on reliability information of measured XOR APUF responses. Thus, it is an important problem to design a strong PUF which can resist not only traditional modeling attacks but also Becker's attack. In this paper, we propose a new strong PUF design called $(x,y)$-MXPUF, which consists of two layers; the upper layer is an $n$-bit $x$-XOR APUF, and the lower layer is an $(n+1)$-bit $y$-XOR APUF. The response of $x$-XOR APUF for an $n$-bit challenge $\mathbf{c}$ in the upper layer is inserted at the middle of $\mathbf{c}$ to construct a new $(n+1)$-bit challenge for the $y$-XOR APUF in the lower layer giving the final response bit of the $(x,y)$-MXPUF. The reliability of $(x,y)$-MXPUF can be theoretically and experimentally shown to be twice the reliability of $(x+y)$-XOR PUF. In the context of traditional modeling attacks, when we keep the same hardware size, the security of $(x,y)$-MXPUF is only slightly weaker than that of $(x+y)$-XOR PUF. Our main contribution proves that the $(x,y)$-MXPUF is secure against Becker's attack.

There is a recent trend in cryptography to construct protocols based on the hardness of computing isogenies between supersingular elliptic curves. Two prominent examples are Jao-De Feo's key exchange protocol and the resulting encryption scheme by De Feo-Jao-Plût. One particularity of the isogeny problems underlying these protocols is that some additional information is given in input, namely the image of some torsion points with order coprime to the isogeny. This additional information was used in several active attacks against the protocols but the current best passive attacks on the protocols make no use of it at all.

In this paper, we provide new algorithms that exploit the additional information provided in isogeny protocols to speed up the resolution of the underlying problems. Our techniques lead to a heuristic polynomial-time key recovery on a non-standard variant of De Feo-Jao-Plût's protocols in a plausible attack model. This shows that at least some isogeny problems are easier to solve when additional information is leaked.

This paper presents the findings of an independent security review of SpiderOak ONE, a popular encrypted cloud storage application. In this application, the storage provider claims that, since all the users' data is password encrypted and the password never leaves the client, even the storage provider cannot learn any information about the users' data.

After providing a formal description of the key design choices in the reviewed application (e.g., how user's accounts are registered, how new devices are registered, how and what cryptographic keys are used, how file encryption is handled, etc.), we present a number of vulnerabilities that can be exploited by a malicious storage server to break, to different degrees, the confidentiality of the users' password and therefore the users' data.

Our findings have been communicated to SpiderOak in April 2017. The vendor promptly replied to our concerns by releasing an updated version of the application (v. 6.3.0, June 2017) which resolves most of the issues described in this paper.

Secure multi-party computation allows a number of participants to securely evaluate a function on their private inputs and has a growing number of applications. Two standard adversarial models that treat the participants as semi-honest or malicious, respectively, are normally considered for showing security of constructions in this framework. In this work, we go beyond the standard security model in the presence of malicious participants and treat the problem of enforcing correct inputs to be entered into the computation. We achieve this by having a certification authority certify user’s information, which is consequently used in secure two-party computation based on garbled circuit evaluation. The focus of this work on enforcing correctness of garbler’s inputs via certification, as prior work already allows one to achieve this goal for circuit evaluator’s input. Thus, in this work, we put forward a novel approach for certifying user’s input and tying certification to garbler’s input used during secure function evaluation based on garbled circuits. Our construction achieves notable performance of adding only one (standard) signature verification and O(nρ) symmetric key/hash operations to the cost of garbled circuit evaluation in the malicious model via cut-and-choose, in which ρ circuits are garbled and n is the length of the garbler’s input in bits. Security of our construction is rigorously proved in the standard model.

Private Information Retrieval (PIR) allows a client to obtain data from a public database without disclosing the locations accessed. Traditionally, the stress is on preserving sublinear work for the client, while the server's work is taken to inevitably be at least linear in the database size. Beimel, Ishai and Malkin (JoC 2004) show PIR schemes where, following a linear-work preprocessing stage, the server's work per query is sublinear in the database size. However, that work only addresses the case of multiple non-colluding servers; the existence of single-server PIR with sublinear server work remained unaddressed.

We consider single-server PIR schemes where, following a preprocessing stage in which the server obtains an encoded version of the database and the client obtains a short key, the per-query work of both server and client is polylogarithmic in the database size. We call such schemes {\em doubly efficient}. Concentrating on the case where the client's key is secret, we show:

- A scheme, based on one-way functions, that works for a bounded number of queries, and where the server storage is linear in the number of queries plus the database size.

- A scheme for an unbounded number of queries, whose security follows from a new hardness assumption that is related to the hardness of solving a system of noisy linear equations.

We also show the insufficiency of a natural approach for obtaining doubly efficient PIR in the setting where the preprocessing is public.