International Association
for Cryptologic Research

The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF($p^n$) where $n$ is a small integer greater than $1$. Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good polynomials that define the extension fields used in NFS. We design two new methods for this task, modifying the asymptotic complexity and paving the way for record-breaking computations. We exemplify these results with the computation of discrete logarithms over a field GF($p^2$) whose cardinality is 180 digits (595 bits) long.

Non-malleable codes are kind of encoding schemes which are resilient to tampering attacks. The main idea behind the non-malleable coding is that the adversary can't be able to obtain any valuable information about the message. Non-malleable codes are used in tamper resilient cryptography and protecting memory against tampering attacks. Several kinds of definitions for the non-malleability exist in the literature. The Continuous non-malleability is aiming to protect messages against the adversary who issues polynomially many tampering queries. The first continuous non-malleable encoding scheme has been proposed by Faust et el. (FMNV) in 2014. In this paper, we propose a new method for proving continuous non-malleability of FMNV scheme. This new proof leads to an improved and more efficient scheme than previous one. The new proof shows we can have the continuous non-malleability with the same security by using a leakage resilient storage scheme with about (k+1)(log(q)-2) bits fewer leakage bound (where k is the output size of the collision resistant hash function and q is the maximum number of tampering queries).

In this work, we retake an old idea that Koblitz presented in his landmark paper, where he suggested the possibility of defining anomalous elliptic curves over the base field \F_4. We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. In order to achieve a fast reduction procedure, we adopted a redundant trinomial strategy that embeds elements of the field \F_{4^m}, with m a prime number, into a ring of higher order defined by an almost irreducible trinomial. We also present a number of techniques that allow us to take full advantage of the native vector instructions of high-end microprocessors. Our software library achieves the fastest timings reported for the computation of the timing-protected scalar multiplication on Koblitz curves, and competitive timings with respect to the speed records established recently in the computation of the scalar multiplication over prime fields.

Event date: 14 August 2016

Responsibilities:

Design and develop innovative yet high quality application software for cybersecurity and FinTech initiatives.

• Responsible for developing technical solutions on Blockchain / Distributed Ledger.

• Implement cryptographic algorithm.

Requirements:

• Bachelor’s degree in Computer Science or related disciplines with 6+ years experience or Master’s degree of equivalent education with 3+ years experience or Ph.D degree holder with less experience. Candidates with less experience will be considered as Engineer.

• Understanding of Blockchain platform such as Bitcoin, Ethereum, HyperLedger, Multichain, etc.

• Deep knowledge in Blockchain technology. Understanding of the cryptographic principles underpinning of Bitcoin and Blockchain Technologies.

• Understanding of distributed system and experience in implementing cryptographic protocols is a plus.

• Must possess extensive hands-on experience in one or more programming languages: Java, Scala, Python, JavaScript, C/C++, Go, Ruby, C#, etc.

• Deep knowledge of objected-oriented programming. Deep understanding of data structure, algorithm and design pattern.

Closing date for applications: 30 June 2016

Contact: charlenechoo (at) astri.org

More information: http://www.astri.org

Event date: 29 June to 1 July 2017
Submission deadline: 20 May 2017

Event date: 26 September to 30 September 2016
Submission deadline: 23 June 2016
Notification: 29 July 2016

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large scale oblivious transfer protocols is becoming more evident. Oblivious transfer extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (CRYPTO 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (CRYPTO 2012) presented an efficient OT extension protocol for the setting of malicious adversaries, that is secure in a random oracle model. In this work we improve OT extensions with respect to communication complexity, computation complexity, and scalability in the semi-honest, covert, and malicious model. Furthermore, we show how to modify our maliciously secure OT extension protocol to achieve security with respect to a version of correlation robustness instead of the random oracle. We also provide specific optimizations of OT extensions that are tailored to the use of OT in various secure computation protocols such as Yao’s garbled circuits and the protocol of Goldreich-Micali-Wigderson, which reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations.

Distribution of cryptographic keys between devices communicating over a publicly accessible medium is an important component of secure design for networked systems. In this paper, we consider the problem of group key exchange between Electronic Control Units (ECUs) connected to the Controller Area Network (CAN) within an automobile. Typically, existing solutions map schemes defined for traditional network systems to the CAN. Our contribution is to utilize physical properties of the CAN bus to generate group keys. We demonstrate that pairwise interaction between ECUs over the CAN bus can be used to efficiently derive group keys in both authenticated and non-authenticated scenarios. We illustrate the efficiency and security properties of the proposed protocols. The scalability and security properties of our scheme are similar to multi-party extensions of Diffie-Hellman protocol, without the computational overhead of group operations.

Over the last decade, hardware Trojans have gained increasing attention in academia, industry and by government agencies. In order to design reliable countermeasures, it is crucial to understand how hardware Trojans can be built in practice. This is an area that has received relatively scant treatment in the literature. In this contribution, we examine how particularly stealthy Trojans can be introduced to a given target circuit. The Trojans are triggered by violating the delays of very rare combinational logic paths. These are parametric Trojans, i.e., they do not require any additional logic and are purely based on subtle manipulations on the sub-transistor level to modify the parameters of the transistors. The Trojan insertion is based on a two-phase approach. In the rst phase, a SAT-based algorithm identies rarely sensitized paths in a combinational circuit. In the second phase, a genetic algorithm smartly distributes delays for each gate to minimize the number of faults caused by random vectors. As a case study, we apply our method to a 32-bit multiplier circuit resulting in a stealthy Trojan multiplier. This Trojan multiplier only computes faulty outputs if specic combinations of input pairs are applied to the circuit. The multiplier can be used to realize bug attacks, introduced by Biham et al. In addition to the bug attacks proposed previously, we extend this concept for the specic fault model of the path delay Trojan multiplier and show how it can be used to attack ECDH key agreement protocols. Our method is a general approach to path delay faults. It is a versatile tool for designing stealthy Trojans for a given circuit and is not restricted to multipliers and the bug attack.

Multilinear maps enable homomorphic computation on encoded values and a public procedure to check if the computation on the encoded values results in a zero. Encodings in known candidate constructions of multilinear maps have a noise component, which is crucial for security. However, this noise grows (gets accumulated) with homomorphic computations and must remain below the maximal noise supported by the multilinear map. A smaller gap between the noise in the freshly generated encodings and the maximal noise supported is desirable.

In this work, we put forward a new candidate construction of obfuscation based on GGH13 multilinear maps for which this gap is polynomial (in the security parameter). Our construction is obtained by tailoring GGH13 multilinear maps to a modification of the Lin's [EUROCRYPT 2016] obfuscation construction. We prove the security of this variant of Lin's construction in the hybrid graded encoding model that captures \emph{all known} vulnerabilities of GGH13 maps and \emph{their conceivable extensions} including the recent annihilation attacks of Miles, Sahai, and Zhandry [CRYPTO 2016].

Private information retrieval (PIR) is a way for clients to query a remote database without the database holder learning the clients' query terms or the responses they generate. Compelling applications for PIR are abound in the cryptographic and privacy research literature, yet existing PIR techniques are notoriously inefficient. Consequently, no such PIR-based application to date has seen real-world at-scale deployment. This paper proposes new "batch coding" techniques to help address PIR's efficiency problem. The new techniques exploit the connection between ramp secret sharing schemes and efficient information-theoretically secure PIR (IT-PIR) protocols. This connection was previously observed by Henry, Huang, and Goldberg (NDSS 2013), who used ramp schemes to construct efficient "batch queries" with which clients can fetch several database records for the same cost as fetching a single record using a standard, non-batch query. The new techniques in this paper generalize and extend those of Henry et al. to construct "batch codes" with which clients can fetch several records for only a fraction the cost of fetching a single record using a standard non-batch query over an unencoded database. The batch codes are highly tuneable, providing a means to trade off (i) lower server-side computation cost, (ii) lower server-side storage cost, and/or (iii) lower uni- or bi-directional communication cost, in exchange for a comparatively modest decrease in resilience to Byzantine database servers.

Walter & Thomson (CT-RSA '01) and Schindler (PKC '02) have shown that extra-reductions allow to break RSA-CRT even with message blinding. Indeed, the extra-reduction probability depends on the type of operation: square, multiply, or multiply with a constant. Regular exponentiation schemes can be regarded as protections, as the operation sequence does not depend on the secret.

In this article, we show that there exists a strong negative correlation between extra-reductions of two consecutive operations, provided that the first one feeds the second one. This allows to mount successful attacks even against blinded asymmetrical computations with a regular exponentiation algorithm (such as Square-and-Multiply Always or Montgomery Ladder). We put forward various attack strategies depending on the context (e.g., known modulus or not, known extra-reduction detection probability, etc.), and implement them on two devices (single core ARM Cortex-M4 and dual core ARM Cortex M0-M4)

Cloud services keep gaining popularity despite the security concerns. While non-sensitive data is easily trusted to cloud, security critical data and applications are not. The main concern with the cloud is the shared resources like the CPU, memory and even the network adapter that provide subtle side-channels to malicious parties. We argue that these side-channels indeed leak fine grained, sensitive information and enable key recovery attacks on the cloud. Even further, as a quick scan in one of the Amazon EC2 regions shows, high percentage -55\%- of users run outdated, leakage prone libraries leaving them vulnerable to mass surveillance.

The most commonly exploited leakage in the shared resource systems stem from the cache and the memory. High resolution and the stability of these channels allow the attacker to extract fine grained information. In this work, we employ the \PnP\ attack to retrieve an RSA secret key from a co-located instance. To speed up the attack, we reverse engineer the cache slice selection algorithm for the Intel Xeon E5-2670 v2 that is used in our cloud instances. Finally we employ noise reduction to deduce the RSA private key from the monitored traces. By processing the noisy data we obtain the complete 2048-bit RSA key used during the decryption.

This paper proposes a highly efficient AES hardware architecture that supports both encryption and decryption for the CBC mode. Some conventional AES architectures employ pipelining techniques to enhance the throughput and efficiency. However, such pipelined architectures are frequently unfit because many practical cryptographic applications work in the CBC mode, where block-wise parallelism is not available for encryption. In this paper, we present an efficient AES encryption/decryption hardware design suitable for such block-chaining modes. In particular, new operation-reordering and register-retiming techniques allow us to unify the inversion circuits for encryption and decryption (i.e., SubBytes and InvSubBytes) without any delay overhead. A new unification technique for linear mappings further reduces both the area and critical delay in total. Our design employs a common loop architecture and can therefore efficiently perform even in the CBC mode. We also present a shared key scheduling datapath that can work on-the-fly in the proposed architecture. To the best of our knowledge, the proposed architecture has the shortest critical path delay and the most efficient in terms of throughput per area among conventional AES encryption/decryption architectures with tower-field S-boxes. We evaluate the performance of the proposed and some conventional datapaths by logic synthesis results with the TSMC 65-nm standard-cell library and NanGate 45- and 15-nm open-cell libraries. As a result, we confirm that our proposed architecture achieves approximately 53--72% higher efficiency (i.e., a higher bps/GE) than any other conventional counterpart.

TLS and SSH are two of the most commonly used protocols for securing Internet traffic. Many of the implementations of these protocols rely on the cryptographic primitives provided in the OpenSSL library. In this work we disclose a vulnerability in OpenSSL, affecting all versions and forks (e.g. LibreSSL and BoringSSL) since roughly October 2005, which renders the implementation of the DSA signature scheme vulnerable to cache-based side-channel attacks. Exploiting the software defect, we demonstrate the first published cache-based key-recovery attack on these protocols: 260 SSH-2 handshakes to extract a 1024/160-bit DSA host key from an OpenSSH server, and 580 TLS 1.2 handshakes to extract a 2048/256-bit DSA key from an stunnel server.

Field Programmable Gate Arrays (FPGAs) have been the target of different physical attacks in recent years. Many different countermeasures have already been integrated into these devices to mitigate the existing vulnerabilities. However, there has not been enough attention paid to semi-invasive attacks from the IC backside due to the following reasons. First, the conventional semi-invasive attacks from the IC backside --- such as laser fault injection and photonic emission analysis --- cannot be scaled down without further effort to the very latest nanoscale technologies of modern FPGAs and programmable SoCs. Second, the more advanced solutions for secure storage, such as controlled Physically Unclonable Functions (PUFs), make the conventional memory-readout techniques almost impossible. In this paper, however, novel approaches have been explored: Attacks based on Laser Voltage Probing (LVP) and its derivatives, as commonly used in Integrated Circuit (IC) debug for nanoscale low voltage technologies, are successfully launched against a $60$ nanometer technology FPGA. We discuss how these attacks can be used to break modern bitstream encryption implementations. Our attacks were carried out on a Proof-of-Concept PUF-based key generation implementation. To the best of our knowledge this is the first time that LVP is used to perform an attack on secure ICs.

We introduce subspace trail cryptanalysis, a generalization of invariant subspace cryptanalysis. With this more generic treatment of subspaces we do no longer rely on specific choices of round constants or subkeys, and the resulting method is as such a potentially more powerful attack vector. We provide a general framework for subspace trail cryptanalysis of AES like Substitution-Permutation Network (SPN) constructions. Interestingly,subspace trail cryptanalysis in fact includes earlier techniques based on impossible or truncated differential cryptanalysis and the integral property as special cases. Choosing AES-128 as the perhaps most studied cipher, we describe distinguishers up to 5 round-reduced AES with a single unknown key. As the perhaps most interesting concrete result, we are able to describe the first 5-round distinguisher for (all versions of) AES that does not require any knowledge about subkeys and needs much less than the full codebook.

In recent years, encrypted databases have emerged as a promising direction that provides data confidentiality without sacrificing functionality: queries are executed on encrypted data. However, existing practical proposals rely on a set of weak encryption schemes that have been shown to leak sensitive data.

In this paper, we propose Arx, the first practical and functionally rich database system that encrypts the data only with strong encryption schemes. Arx protects the database with the same level of security as regular AES-based encryption, which by itself is devoid of functionality. We show that Arx supports real applications such as ShareLatex and a health data cloud provider, and that its performance overhead is modest.

Event date: 28 October 2016
Submission deadline: 27 July 2016
Notification: 5 September 2016