International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2014-09-21
14:37 [PhD][Update]

Name: Elisabeth Oswald
Topic: On Side-Channel Attacks and the Application of Algorithmic Countermeasures
Category:implementation

Description: This thesis is devoted to the investigation of implementation attacks on di?erent types of cryptosystems. We focus on the passive types of such attacks, which exploit the running time, the power consumption or the electromagnetic radiation of the attacked device. In particular, most of the attacks which we will discuss in this thesis have been implemented in practice by using power consumption information. In the ?rst part of this thesis, we concentrate on the concepts on which sidechannel attacks are based. We demonstrate how such attacks can be applied to implementations of secret-key cryptosystems and how similar attacks can be used to break implementations of public-key cryptosystems as well. Besides the introductory chapter which addresses the currently exploited side-channels, this part also addresses the di?erent statistical methods which we used for our attacks and which models (or assumptions) we developed to perform attacks on di?erent types of cryptosystems. The second part of this thesis is concerned with the practical aspects of conducting side-channel attacks. We concentrate in this part on power-analysis attacks. Experimental attacks are described and some practical aspects of their realization are discussed. Our main contributions for this thesis are the introduction of a software-based approach to estimate the success for power analysis attacks, which has been published in [AO00], and the investigations on a speci?c type of countermeasures for securing implementations of elliptic curve cryptosystems, see [OA01] (joined work with M. Aigner) and [Osw03]. We developed a highly e?cient representation for the AES S-box [WOL02] (joint work with J. Wolkerstorfer and M. Lamberger). We also conducted experiments on applying power-analysis attcks on implementations of elliptic curve cryptosystems on FPGAs [OOP] (joint work with S. B. ¨ Ors and B. Preneel).Moreover, we have contributed to the NESSIE project by evaluating the vulnerability of some of the NESSI[...]

2014-09-20
18:17 [Pub][ePrint]

In this paper, we propose an efficient and provably secure certificateless public key cryptography (CL-PKC) based authenticated group key agreement (CL-AGKA) protocol that meets practicability, simplicity, and strong notions of security. Our protocol focuses on certificateless public key cryptography (CL-PKC) which simplifies the complex certificate management in the traditional public key cryptography (PKC) and resolves the key escrow problem in identity-based cryptography (IBC). The authenticated group key exchange (AGKA) protocols allow participants to communicate over a public network to exchange a shared secret key. The CL-AGKA protocol is designed to established a group key between group of participants by ensuring that no other outsiders can learn any information about the agreed session key. Our CL-AGKA protocol presents a security notion in random oracle model. It is formally proven that our CL-AGKA protocol provides strong Authenticated Key Exchange (AKE) security. Thus, the proposed protocol provides provable security along with low message exchange cost and computational cost to form the shared group key.

00:17 [Pub][ePrint]

Present-day public-key cryptosystems such as RSA and Elliptic Curve Cryptography (ECC) will become insecure when quantum computers become a reality. This paper presents the new state of the art in efficient software implementations of a post-quantum secure public-key encryption scheme based on the ring-LWE problem. We use a 32-bit ARM Cortex-M4F microcontroller as the target platform. Our contribution includes optimization techniques for fast discrete Gaussian sampling and efficient polynomial multiplication. This implementation beats all known software implementations, on any architecture, by at least one order of magnitude. We further show that our scheme beats all ECC-based public-key encryption schemes by at least one order of magnitude. At 128-bit security we require 121166 cycles per encryption and 43324 cycles per decryption, while at a 256-bit security we require 261939 cycles per encryption and 96520 cycles per decryption. Gaussian sampling is done at an average of 28.5 cycles per sample.

00:17 [Pub][ePrint]

Security is one of the most important features of industrial products. Cryptographic algorithms are mainly used for this purpose to obtain confidentiality and integrity of data in industry. One of the main concerns of researchers in designing cryptographic algorithms is efficiency in either software implementation or hardware implementation. However, the efficiency of some well-known algorithms is highly questionable. The main goal of this paper is to present a novel processor architecture called CIARP (stands for Crypto Instruction-Aware RISC Processor) being feasible for high speed implementation of low throughput cryptographic algorithms. CIARP has been designed based on a proposed instruction set named Crypto Specific Instruction Set (CSIS), that can speed up encryption and decryption processes of data.

00:17 [Pub][ePrint]

We give a detailed account of the use of \$$\\mathbb{Q}\$$-curve reductions to construct elliptic curves over \$$\\mathbb{F}_{p^2}\$$ with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) endomorphisms.

Like GLS (which is a degenerate case of our construction), we offer the advantage over GLV of selecting from a much wider range of curves, and thus finding secure group orders when \$$p\$$ is fixed for efficient implementation.

Unlike GLS, we also offer the possibility of constructing twist-secure curves.

We construct several one-parameter families of elliptic curves over \$$\\mathbb{F}_{p^2}\$$ equipped with efficient endomorphisms for every \$$p > 3\$$, and exhibit examples of twist-secure curves over \$$\\mathbb{F}_{p^2}\$$ for the efficient Mersenne prime \$$p = 2^{127}-1\$$.

00:17 [Pub][ePrint]

The Protocol for Lightweight Authentication of Identity (PLAID) aims at secure and private authentication between a smart card and a terminal. Originally developed by a unit of the Australian Department of Human Services for physical and logical access control, PLAID has now been standardized as an Australian standard AS-5185-2010 and is currently in the fast track standardization process for ISO/IEC 25182-1.2. We present a cryptographic evaluation of PLAID. As well as reporting a number of undesirable cryptographic features of the protocol, we show that the privacy properties of PLAID are significantly weaker than claimed: using a variety of techniques we can fingerprint and then later identify cards. These techniques involve a novel application of standard statistical and data analysis techniques in cryptography. We also discuss countermeasures to our attacks.

00:17 [Pub][ePrint]

This paper shows how to securely authenticate messages using just 29 bit operations per authenticated bit, plus a constant overhead per message. The authenticator is a standard type of \"universal\" hash function providing information-theoretic security; what is new is computing this type of hash function at very high speed.

At a lower level, this paper shows how to multiply two elements of a field of size 2^128 using just 9062 \\approx 71 * 128 bit operations, and how to multiply two elements of a field of size 2^256 using just 22164 \\approx 87 * 256 bit operations. This performance relies on a new representation of field elements and new FFT-based multiplication techniques.

This paper\'s constant-time software uses just 1.89 Core 2 cycles per byte to authenticate very long messages. On a Sandy Bridge it takes 1.43 cycles per byte, without using Intel\'s PCLMULQDQ polynomial-multiplication hardware. This is much faster than the speed records for constant-time implementations of GHASH without PCLMULQDQ (over 10 cycles/byte), even faster than Intel\'s best Sandy Bridge implementation of GHASH with PCLMULQDQ (1.79 cycles/byte), and almost as fast as state-of-the-art 128-bit prime-field MACs using Intel\'s integer-multiplication hardware (around 1 cycle/byte).

00:17 [Pub][ePrint]

The focus of this paper is on differential privacy of streaming data using sketch-based algorithms. Previous works, like Dwork {\\it et al.} (ICS 2010, STOC 2010), explored random sampling based streaming algorithms. We work in the well studied streaming model of computation, where the database is stored in the form of a matrix and a curator can access the database row-wise or column-wise.

Dwork {\\it et al.} (STOC 2010) gave impossibility result for any non-trivial query on a streamed data with respect to the user level privacy. Therefore, in this paper, we restrict our attention to the event level privacy. {We provide optimal, up to logarithmic factor, space differentially private mechanism in the streaming model for three basic linear algebraic tasks: matrix multiplication, linear regression, and low rank approximation, while incurring significantly less additive error}.

Our approach for matrix multiplication and linear regression has some similarities with Blocki {\\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013) on the superficial level, but there are some subtle differences. For example, they perform an affine transformation to convert the private matrix in to a set of $\\{\\sqrt{w/n},1\\}^n$ vectors for some appropriate $w$, while we perform an input perturbation that raises the singular value of the private matrix. %On a high level, the mechanism for linear regression and matrix multiplication can be seen as a private analogue of the known streaming algorithms. In order to get a streaming algorithm for low rank approximation, we have to reuse the random Gaussian matrix in a specific way. We prove that the resulting distribution also preserve differential privacy.

We do not make any assumptions, like singular value separation, as made in the earlier works of Hardt and Roth (STOC 2013) and Kapralov and Talwar (SODA 2013). Further, we do not assume normalized row as in the work of Dwork {\\it et al.} (STOC 2014). All our mechanisms, in the form presented, can also be computed in the distributed setting of Biemel, Nissim, and Omri (CRYPTO 2008).

00:17 [Pub][ePrint]

Secure protocols for password-based user authentication are well-studied in the cryptographic literature but have failed to see wide-spread adoption on the Internet; most proposals to date require extensive modifications to the Transport Layer Security (TLS) protocol, making deployment challenging. Recently, a few modular designs have been proposed in which a cryptographically secure password-based mutual authentication protocol is run inside a confidential (but not necessarily authenticated) channel such as TLS; the password protocol is bound to the established channel to prevent active attacks. Such protocols are useful in practice for a variety of reasons: security no longer relies on users\' ability to validate server certificates and can potentially be implemented with no modifications to the secure channel protocol library.

We provide a systematic study of such authentication protocols. Building on recent advances in modelling TLS, we give a formal definition of the intended security goal, which we call password-authenticated and confidential channel establishment (PACCE). We show generically that combining a secure channel protocol, such as TLS, with a password authentication protocol, where the two protocols are bound together using either the transcript of the secure channel\'s handshake or the server\'s certificate, results in a secure PACCE protocol. Our prototype based on TLS is available as a cross-platform client-side Firefox browser extension and a server-side web application which can easily be installed on deployed web browsers and servers.

00:17 [Pub][ePrint]

Although newly proposed, tree-based Oblivious RAM schemes are drastically more efficient than older techniques, they come with a significant drawback: an inherent dependence on a fixed-size database. This capability is vital for real-world use of Oblivious RAM since one of its most promising deployment scenarios is for cloud storage, where scalability and elasticity are crucial. We revisit the original construction by Shi et al. [16] and propose several ways to support both increasing and decreasing the ORAM\'s size with sublinear communication. We show that increasing capacity can be accomplished by adding leaf nodes to the tree, but that it must be done carefully in order to preserve the probabilistic integrity of the data structures. We also provide new, tighter bounds for the size of interior and leaf nodes in the scheme, saving bandwidth and storage over previous constructions. Finally, we define an oblivious pruning technique for removing leaf nodes and decreasing the size of the tree. We show that this pruning method is both secure and efficient.

00:17 [Pub][ePrint]

The Learning with Errors (LWE) problem has gained a lot of attention in recent years leading to a series of new cryptographic applications. Specifically, it states that it is hard to distinguish random linear equations disguised by some small error from truly random ones. Interestingly, cryptographic primitives based on LWE often do not exploit the full potential of the error term beside of its importance for security.

To this end, we introduce a novel LWE-close assumption, namely Augmented Learning with Errors (A-LWE), which allows to hide auxiliary data injected into the error term by a technique that we call message embedding. In particular, it enables existing cryptosystems to strongly increase the message throughput per ciphertext. We show that A-LWE is for certain instantiations at least as hard as the LWE problem. This inherently leads to new cryptographic constructions providing high data load encryption and customized security properties as required, for instance, in economic environments such as stock markets resp. for financial transactions. The security of those constructions basically stems from the hardness to solve the A-LWE problem.

As an application we introduce (among others) the first lattice-based replayable chosen-ciphertext secure encryption scheme from A-LWE.