International Association
for Cryptologic Research

Various sources have revealed that cryptographic standards and components have been subverted to undermine the security of users, reigniting research on means to achieve security in presence of such subverted components. In this paper we consider direct anonymous attestation (DAA) in this respect. This standardized protocol allows a computer with the help of an embedded TPM chip to remotely attest that it is in a healthy state. Guaranteeing that different attestations by the same computer cannot be linked was an explicit and important design goal of the standard in order to protect the privacy of the user of the computer. Surprisingly, none of the standardized or otherwise proposed DAA protocols achieves privacy when the TPM is subverted, but they all rely on the honesty of the TPM. As the TPM is a piece of hardware, it is hardly possible to tell whether or not a given TPM follows the specified protocol. In this paper we study this setting and provide a new protocol that achieves privacy also in presence of subverted TPMs.

In the last few years multivariate public key cryptography has experienced an infusion of new ideas for encryption. Among these new strategies is the ABC Simple Matrix family of encryption schemes which utilize the structure of a large matrix algebra to construct effectively invertible systems of nonlinear equations hidden by an isomorphism of polynomials. One promising approach to cryptanalyzing these schemes has been structural cryptanalysis, based on applying a strategy similar to MinRank attacks to the discrete differential. These attacks however have been significantly more expensive when applied to parameters using fields of characteristic 2, which have been the most common choice for published parameters. This disparity is especially great for the cubic version of the Simple Matrix Encryption Scheme.

In this work, we demonstrate a technique that can be used to implement a structural attack which is as efficient against parameters of characteristic 2 as are attacks against analogous parameters over higher characteristic fields. This attack demonstrates that, not only is the cubic simple matrix scheme susceptible to structural attacks, but that the published parameters claiming 80 bits of security are less secure than claimed (albeit only slightly.) Similar techniques can also be applied to improve structural attacks against the original Simple Matrix Encryption scheme, but they represent only a modest improvement over previous structural attacks. This work therefore demonstrates that choosing a field of characteristic 2 for the Simple Matrix Encryption Scheme or its cubic variant will not provide any additional security value.

In this paper I propose fully homomorphic public-key encryption (FHPKE) with the recursive ciphertex. A ciphertext consists of three sub-ciphertexts corresponding to one plaintext. When we execute the additional operation or multiplicative operation, a new three sub-ciphertexts are generated from the three sub-ciphertexts recursively without revealing the plaintexts. The scheme is based on the discrete logarithm assumption (DLA) and computational Diffie–Hellman assumption (CDH) of multivariate polynomials on octonion ring with composite number modulus. The scheme is immune from “m and - m attack”.

We present a construction of bent function $f_{a,S}$ with $n=2m$ variables for any nonzero vector $a\in \mathbb{F}_{2}^{m}$ and subset $S$ of $\mathbb{F}_{2}^{m}$ satisfying $a+S=S$. We give the simple expression of the dual bent function of $f_{a,S}$. We prove that $f_{a,S}$ has optimal algebraic degree $m$ if and only if $|S|\equiv 2 (\bmod 4) $. This construction provides series of bent functions with optimal algebraic degree and large symmetric group if $a$ and $S$ are chosen properly.

This paper introduces the notion of attribute-based concurrent signatures. This primitive can be considered as an interesting extension of concurrent signatures in the attribute-based setting. It allows two parties fairly exchange their signatures only if each of them has convinced the opposite party that he/she possesses certain attributes satisfying a given signing policy. Due to this new feature, this primitive can find useful applications in online contract signing, electronic transactions and so on. We formalize this notion and present a con-struction which is secure in the random oracle model under the Strong Dif-fie-Hellman assumption and the eXternal Diffie-Hellman assumption.

Near-MDS matrices provide better trade-offs between security and efficiency compared to constructions based on MDS matrices, which are favored for hardware-oriented designs. We present new designs of lightweight linear diffusion layers by constructing lightweight near-MDS matrices. Firstly generic $n\times n$ near-MDS circulant matrices are found for $5\leq n \leq 9$. Secondly\,, the implementation cost of instantiations of the generic near-MDS matrices is examined. Surprisingly, for $n=7,8$, it turns out that some proposed near-MDS circulant matrices of order $n$ have the lowest XOR count among all near-MDS matrices of the same order. Further, for $n=5,6$, we present near-MDS matrices of order $n$ having the lowest XOR count as well. The proposed matrices, together with previous construction of order less than five, lead to solutions of $n\times n$ near-MDS matrices with the lowest XOR count over finite fields $\mathbb{F}_{2^m}$ for $2\leq n \leq 8$ and $4\leq m \leq 2048$. Moreover, we present some involutory near-MDS matrices of order $8$ constructed from Hadamard matrices. Lastly, the security of the proposed linear layers is studied by calculating lower bounds on the number of active S-boxes. It is shown that our linear layers with a well-chosen nonlinear layer can provide sufficient security against differential and linear cryptanalysis.

Minimizing the Boolean circuit implementation of a given cryptographic function is an important issue. A number of papers \cite{paarISIT97}, \cite{Satoh}, \cite{PaarSome}, \cite{Canright} only consider cancellation-free straight-line programs for producing short circuits over GF(2) while \cite{BP2010} does not. Boyar-Peralta (BP) heuristic \cite{BP2010} yields a valuable tool for practical applications such as building fast software and low-power circuits for cryptographic applications, e.g. AES, PRESENT, and GOST. However, BP heuristic does not take into account the matrix density. In a dense linear system the rows can be computed by adding or removing a few elements from a ``common path'' that is ``close'' to almost all rows. The new heuristic described in this paper will merge the idea of ``cancellation'' and ``common path''. An extensive testing activity has been performed. Experimental results of new and BP heuristic were compared. They show that the Boyar-Peralta bounds are not tight on dense systems.

Due to lack of practical and scalable security verification tools and methodologies, very few of the existing hardware-software security architectures have been thoroughly checked at the design time. To address this issue, our project develops a security verification methodology that is applicable to different hardware-software security architectures during the design phase. The verification framework aims to prove that a system holds desired properties with respect to not just functionality but also security; and we mainly focus on information flow and non-interference properties for verification. Using these properties, confidentiality and integrity of the sensitive data can be checked at design time. The proposed verification framework is built upon Chisel hardware construction language. By extending the Chisel language and tools, we created SecChisel. Ongoing work is focused on implementing SecChisel on top of Chisel~3 and realisation of the static and dynamic security labels.

Proof-of-work-based consensus, adopted in Bitcoin, has already drawn much attention from cryptocurrency and block chain community. Despite its nice decentralization property, it has significant limitation in terms of efficiency since transactions can not be confirmed within seconds. In 2016, hybrid consensus was proposed to partially deal with this issue by introducing committee responsible for validating transactions. However, there still exist some issues with respect to this hybrid consensus such as selfish mining, fairness to the election of committee member, incentives for the consensus scheme, and so on. To improve the hybrid consensus further, we first present a substitution for proof-of-work, named as fair-proof-of-work (fPoW), to solve the issues related to selfish mining and fair committee election. We also demonstrate the incentives for our improved hybrid consensus. Then, based on this consensus, we build privacy-preserving constructions (including identity and content privacy preserving) to make the consensus more applicable and powerful. Finally, we give formal security proof for our newly-proposed consensus scheme. It is expected that this novel consensus scheme could be adopted in block chains which require decentralization, high efficiency, as well as privacy-preserving.

The privacy guarantees of anonymous communication networks (ACNs) are bounded by the number of participants. As a consequence, an ACN can only achieve strong privacy guarantees if it succeeds in attracting a large number of active users. Vice versa, weak privacy guarantees renders an ACN unattractive, leading to a low number of users. In this work, we show how to break this vicious circle. We develop CoverUp, a system that "forces" visitors of highly accessed websites to become involuntary participants of an ACN. CoverUp leverages basic browser functionality to execute server-served JavaScript code and to open remote connections to connect all website visitors to an ACN (which we instantiate by a mix server). We build two applications on top of CoverUp: an anonymous feed and a chat. We show that both achieve practical performance and strong privacy guarantees. Towards a network-level attacker, CoverUp makes voluntary and involuntary participants indistinguishable, thereby providing an anonymity set that includes all voluntary and involuntary participants (i.e., all website visitors). Given this, CoverUp provides even more than mere anonymity: the voluntary participants can hide the very intention to use the ACN. As the concept of forced participation raises ethical and legal concerns, we discuss these concerns and describe how these can be addressed.

SHA-1 is a widely used 1995 NIST cryptographic hash function standard that was officially deprecated by NIST in 2011 due to fundamental security weaknesses demonstrated in various analyses and theoretical attacks.

Despite its deprecation, SHA-1 remains widely used in 2017 for document and TLS certificate signatures, and also in many software such as the GIT versioning system for integrity and backup purposes.

A key reason behind the reluctance of many industry players to replace SHA-1 with a safer alternative is the fact that finding an actual collision has seemed to be impractical for the past eleven years due to the high complexity and computational cost of the attack.

In this paper, we demonstrate that SHA-1 collision attacks have finally become practical by providing the first known instance of a collision. Furthermore, the prefix of the colliding messages was carefully chosen so that they allow an attacker to forge two PDF documents with the same SHA-1 hash yet that display arbitrarily-chosen distinct visual contents.

We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to $2^{63.1}$ SHA-1 compressions and took approximately 6500 CPU years and 100 GPU years. As a result while the computational power spent on this collision is larger than other public cryptanalytic computations, it is still more than 100 000 times faster than a brute force search.

In this paper, we extend the recent work by Wang et al., who proposed a new framework for secure two-party computation in the preprocessing model that can be instantiated efficiently using TinyOT. We show that their protocol can be generalized to the multi-party setting, where the preprocessing functionality is based on the multi-party TinyOT-like protocol. Assuming there are n parties where at most n − 1 parties are corrupted, the function-dependent phase has a total communication complexity of O(\kappa n^2) bits per AND gate; the online phase has a total communication complexity of O(\kappa n^2) bits per input bit.

In the second part of this paper, we propose a new multi-party TinyOT protocol. The new protocol uses a set of new techniques that allows parties to distributively check the correctness without the need for cut-and-choose. The resulting protocol is much more efficient compared to previous protocols: with statistical security parameter \rho, the complexity to generate one AND triple is O(\rho/log|C| n^2), where |C| is the circuit size. The best previous multi-party TinyOT protocol by Frederiksen et al. has a complexity of O(p^2/log^2|C| n^2) per AND triple.

The resulting protocol enjoys extremely high efficiency, compared to the state-of-the-art protocol by Lindell et al. that combines the BMR protocol with the SPDZ protocol.

In this paper, we propose an accurate security evaluation methodology for block ciphers with a binary diffusion layers against division cryptanalysis. We illustrate the division property by the independence of variables, and exploit a one-to-one mapping between division trails and invertible sub-matrices. We give a new way to model the propagation of division property of linear diffusion layers by the smallest amount of inequalities which are generated from linear combinations of row vectors of the diffusion matrix. The solutions of these inequalities are exactly the division trails of linear transformation. Hence the description is compact and optimal.

As applications of our methodology, we first present a 10-round integral distinguisher for Skinny, proposed at CRYPTO 2016 which is of one round more than that found by using the previous method. For Midori, proposed at ASIACRYPT 2015, the designers have obtained a 3.5-round integral characteristic. Surprisingly, we find 7-round integral distinguishers both for Midori64 and Midori128.

Most importantly, we obtain the longest integral distinguishers for block ciphers with a binary diffusion layer. It seems that any more improvement of this kind of integral distinguishers using the division property is impossible. Therefore, the technique can be used to prove security against division cryptanalysis, and we can hopefully expect it to become a useful technique for designers.

In this brief note we connect the discrete logarithm problem over prime fields in the safe prime case to the logarithmic derivative.

We present the first general-purpose digital signature scheme based on supersingular elliptic curve isogenies secure against quantum adversaries in the quantum random oracle model with small key sizes. This scheme is an application of Unruh’s construction of non-interactive zero-knowledge proofs to an interactive zero-knowledge proof proposed by De Feo, Jao, and Plût. We implement our proposed scheme on an x86-64 PC platform as well as an ARM-powered device. We exploit the state-of-the-art techniques to speed up the computations for general C and assembly. Finally, we provide timing results for real world applications.

In the Wyner wiretap channel, a sender is connected to a receiver and an eavesdropper through two noisy channels. It has been shown that if the noise in the eavesdropper channel is higher than the receiver's channel, information theoretically secure communication from Alice to Bob, without requiring a shared key, is possible. The approach is particularly attractive noting the rise of quantum computers and possibility of the complete collapse of today's’ cryptographic infrastructure. If the eavesdropper’s channel is noise free, however, no secrecy can be obtained. The iJam protocol, proposed by Gollakota and Katabi, is an interactive protocol over noise free channels that uses friendly jamming the receiver to establish an information theoretically secure shared key between the sender and the receiver. The protocol relies on the Basic iJam Transmission Protocol (BiT protocol) that uses properties of OFDM (Orthogonal Frequency-Division Multiplexing) to create uncertainty for Eve (hence noisy view) in receiving the sent information, and use this uncertainty to construct a secure key agreement protocol. The protocol has been implemented and evaluated using extensive experiments that examine the best eavesdropper’s reception strategy. In this paper, we develop an abstract model for BiT protocol as a wiretap channel and refer to it as a virtual wiretap channel. We estimate parameters of this virtual wiretap channel, derive the secrecy capacity of this channel and design a secure message transmission protocol with provable semantic security using the channel. Our analysis and protocol give a physical layer security protocol, with provable security, that is implementable in practice (BiT protocol has already been implemented).

Real-world applications of authenticated encryption often require the encryption to be computable {online}, e.g. to compute the $i^{\textrm{th}}$ block of ciphertext after having processed the first $i$ blocks of plaintext. A significant line of research was dedicated to identifying security notions for online authenticated encryption schemes, that capture various security goals related to real-life scenarios. Fouque, Joux, Martinet and Valette proposed definitions of privacy and integrity against adversaries that can query their oracles in a blockwise-adaptive manner, to model memory-constrained applications. A decade later, Fleischmann, Forler and Lucks proposed the notion of online nonce misuse-resistant authenticated encryption (OAE) to capture the security of online authenticated encryption under nonce-reuse.

In this work we investigate the relation between these notions. We first recast the blockwise notions of Fouque et al. to make them compatible with online authenticated encryption schemes that support headers. We then show that OAE and the conjunction of the blockwise notions are "almost" equivalent. We identify the missing property on the side of blockwise notions, and formalize it under the name PRTAG. With PRTAG being just an auxiliary definition, the equivalence we finally show suggests that OAE and the blockwise model for online authenticated encryption capture essentially the same notion of security.

Whitebox cryptography aims to ensure the security of cryptographic algorithms in the whitebox model where the adversary has full access to the execution environment. To attain security in this setting is a challenging problem: Indeed, all published whitebox implementations of standard symmetric-key algorithms such as AES to date have been practically broken. However, as far as we know, no whitebox implementation in real-world products has suffered from a key recovery attack. This is due to the fact that commercial products deploy additional software protection mechanisms on top of the whitebox implementation. This makes practical attacks much less feasible in real-world applications.

There are numerous software protection mechanisms which protect against standard whitebox attacks. One such technique is control flow obfuscation which randomizes the order of table lookups for each execution of the whitebox encryption module. Another technique is randomizing the locations of the various Look up tables (LUTs) in the memory address space. In this paper we investigate the effectiveness of these countermeasures against two attack paradigms. The first known as Differential Computational Analysis (DCA) attack was developed by Bos, Hubain, Michiels and Teuwen in CHES 2016. The attack passively collects software execution traces for several plaintext encryptions and uses the collected data to perform an analysis similar to the well known differential power attacks (DPA) to recover the secret key. Since the software execution traces contain time demarcated physical addresses of memory locations being read/written into, they essentially leak the values of the inputs to the various LUTs accessed during the whitebox encryption operation, which as it turns out leaks sufficient information to perform the power attack. We found that if in addition to control flow obfuscation, one were to randomize the locations of the LUTs in the memory, then it is very difficult to perform the DCA on the resultant system using such table inputs and extract the secret key in reasonable time. As an alternative, we investigate the version of the DCA attack which uses the outputs of the tables instead of the inputs to mount the power analysis attack. This modified DCA is able to extract the secret key from the flow obfuscated and location randomized versions of several whitebox binaries available in crypto literature.

We develop another attack called the Zero Difference Enumeration (ZDE) attack. The attack records software traces for several pairs of strategically selected plaintexts and performs a simple statistical test on the effective difference of the traces to extract the secret key. We show that ZDE is able to recover the keys of whitebox systems. Finally we propose a new countermeasure for protecting whitebox binaries based on insertion of random delays which aims to make both the ZDE and DCA attacks practically difficult by adding random noise in the information leaked to the attacker.

We study a generalization of the $k$-list problem, also known as the Generalized Birthday problem. In the $k$-list problem, one starts with $k$ lists of binary vectors and has to find a set of vectors -- one from each list -- that sum to the all-zero target vector. In our generalized {\em Approximate $k$-list problem}, one has to find a set of vectors that sum to a vector of small Hamming weight $\omega$. Thus, we relax the condition on the target vector and allow for some error positions.

This in turn helps us to significantly reduce the size of the starting lists, which determines the memory consumption, and the running time as a function of $\omega$. For $\omega = 0$, our algorithm achieves the original $k$-list run-time/memory consumption, whereas for $\omega = \frac n 2 $ it has polynomial complexity.

As in the $k$-list case, our Approximate $k$-list algorithm is defined for all $k=2^m, m>1$. Surprisingly, we also find an Approximate 3-list algorithm that improves in the run-time exponent compared to its 2-list counterpart for all $0< \omega < \frac n 2$. To the best of our knowledge this is the first such improvement of some variant of the notoriously hard 3-list problem.

As an application of our algorithm we compute small weight multiples of a given polynomial with more flexible degree than with Wagner's algorithm from Crypto 2002 and with smaller memory consumption than with Minder and Sinclair's algorithm from SODA 2009.

We present new techniques to efficiently scan the space of high-probability differential trails in bit-oriented ciphers. Differential trails consist in sequences of state patterns that we represent as ordered lists of basic components in order to arrange them in a tree. The task of generating trails with probability above some threshold starts with the traversal of the tree. Our choice of basic components allows us to efficiently prune the tree based on the fact that we can tightly bound the probability of all descendants for any node. Then we extend the state patterns resulting from the tree traversal into longer trails using similar bounding techniques. We apply these techniques to the 4 largest Keccak-f permutations, for which we are able to scan the space of trails with weight per round of 15. This space is orders of magnitude larger than previously best result published on Keccak-f[1600] that reached 12, which in turn is orders of magnitude larger than any published results achieved with standard tools, that reached at most 9. As a result we provide new and improved bounds for the minimum weight of differential trails on 3, 4, 5 and 6 rounds. We also report on new trails that are, to the best of our knowledge, the ones with the highest known probability.