International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

2013-09-23
06:17 [Pub][ePrint] Cryptanalysis of Full RIPEMD-128, by Franck Landelle and Thomas Peyrin

  In this article we propose a new cryptanalysis method for double-branch hash functions that we apply on the standard RIPEMD-128, greatly improving over know results. Namely, we were able to build a very good differential path by placing one non-linear differential part in each computation branch of the RIPEMD-128 compression function, but not necessarily in the early steps. In order to handle the low differential probability induced by the non-linear part located in later steps, we propose a new method for using the freedom degrees, by attacking each branch separately and then merging them with free message blocks. Overall, we present the first collision attack on the full RIPEMD-128 compression function as well as the first distinguisher on the full RIPEMD-128 hash function. Experiments on reduced number of rounds were conducted, confirming our reasoning and complexity analysis. Our results show that 16 years old RIPEMD-128, one of the last unbroken primitives belonging to the MD-SHA family, might not be as secure as originally thought.



06:17 [Pub][ePrint] How to Further Increase Leakage Exploitation Rate in Profiled Side-Channel Attacks?, by Guangjun Fan and Yongbin Zhou and Hailong Zhang and Dengguo Feng

  Template Attack is widely accepted to be one of the most powerful side-channel attacks, because it is assumed that one has full knowledge of targeted crypto devices and thus be well capable of characterizing the side-channel leakages. However, whether or not Template Attack exploits side-channel leakages to the fullest is still not clear. In this paper, we present a negative answer to this central question, by introducing a normalization process into original Template Attack. We present Normalized Template Attack, which has the normalization process. Furthermore, we prove that Normalized Template Attack is better that its original counterpart in terms of leakage exploitation rate. We evaluate the key-recovery efficiency of Normalized Template Attack and original Template Attack as well under identical scenarios, by performing attacks against both simulated and real power traces. Our experimental results show that our method is valid end effective. Remarkably enough, this normalization process is of extremely low computation cost. Therefore, we argue that the

normalization process should be integrated as a necessary part of profile attacks in order to better understand the practical threats of these attacks.



06:17 [Pub][ePrint] Ultra Low-Power implementation of ECC on the ARM Cortex-M0+, by Ruan de Clercq and Leif Uhsadel and Anthony Van Herrewege and Ingrid Verbauwhede

  In this work, elliptic curve cryptography (ECC) is used to make an efficient implementation of a public-key cryptography algorithm on the ARM Cortex-M0+. The goal of this implementation is to make not only a fast, but also a very low-power software implementation. To aid in the elliptic curve parameter selection, the energy consumption of different instructions on the ARM Cortex-M0+ was measured and it was found that there is a variation of up to 22.5% between different instructions. The instruction set architecture (ISA) and energy measurements were used to make a simulation of both a binary curve and a prime curve implementation, and the former was found to have a slightly faster execution time with a lower power consumption. Binary curve arithmetic use instructions which requires less energy than prime curve arithmetic on the target platform. A new field multiplication algorithm is proposed, called Lopez-Dahab with fixed registers, which is an optimization of the Lopez-Dahab (LD) algorithm. The proposed algorithm has a performance improvement of 15\\% over the LD with rotating registers algorithm (which is the current fastest optimization of the LD algorithm). A software implementation that uses the proposed algorithm was made in C and assembly, and on average our implementation of a random point multiplication requires 34.16uJ, whereas our fixed point multiplication requires 20.63uJ. The energy consumption of our implementation beats all known software implementations on embedded platforms, of a point multiplication, on the same equivalent security level by a factor of 7.4.



06:17 [Pub][ePrint] Key-recovery Attacks on Various RO PUF Constructions via Helper Data Manipulation, by Jeroen Delvaux and Ingrid Verbauwhede

  Physically Unclonable Functions (PUFs) are emerging as hardware security primitives. They are mainly used to generate secret keys which are inherently unique for every manufactured sample of a chip. Ring Oscillator (RO) PUFs are among the most widely researched PUFs. In this work, we claim various RO PUF constructions to be vulnerable against manipulation of their public helper data. Partial/full key-recovery is a threat for the following constructions, in chronological order. (1) Temperature-aware cooperative RO PUFs, proposed at HOST 2009. (2) The sequential pairing algorithm, proposed at HOST 2010. (3) Group-based RO PUFs, proposed at DATE 2013. (4) Or more general, all entropy distiller constructions proposed at DAC 2013.



06:17 [Pub][ePrint] Limited-birthday Distinguishers for Hash Functions - Collisions Beyond the Birthday Bound can be Meaningful, by Mitsugu Iwamoto and Thomas Peyrin and Yu Sasaki

  In this article, we investigate the use of limited-birthday distinguishers to the context of hash functions. We first provide a proper understanding of the limited-birthday problem and demonstrate its soundness by using a new security notion Differential Target Collision Resistance (dTCR) that is related to the classical Target Collision Resistance (TCR) notion. We then solve an open problem and close the existing security gap by proving that the best known generic attack proposed at FSE 2010 for the limited-birthday problem is indeed the best possible method.

Moreover, we show that almost all known collision attacks are in fact more than just a collision finding algorithm, since the difference mask for the message input is usually fixed. A direct and surprising corollary is that these collision attacks are interesting for cryptanalysis even when their complexity goes beyond the $2^{n/2}$ birthday bound and up to the $2^{n}$ preimage bound, and can be used to derive distinguishers using the limited-birthday problem. Interestingly, cryptanalysts can now search for collision attacks beyond the $2^{n/2}$ birthday bound.

Finally, we describe a generic algorithm that turns a semi-free-start collision attack on a compression function (even if its complexity is beyond the birthday bound) into a distinguisher on the whole hash function when its internal state is not too wide. To the best of our knowledge, this is the first result that exploits classical semi-free-start collisions on the compression function to exhibit a weakness on the whole hash function. As an application of our findings, we provide distinguishers on reduced or full version of several hash functions, such as RIPEMD-128, SHA-256, Whirlpool, etc.



06:17 [Pub][ePrint] Sub-linear Blind Ring Signatures without Random Oracles, by Essam Ghadafi

  Ring signatures allow a signer to anonymously sign a message on behalf of a set of arbitrarily chosen signers called a ``ring\'\'.

Blind signatures, on the other hand, allow a user to obtain a signature on a message while maintaining the privacy of the message.

Blind ring signatures combine properties of both primitives and hence provide a strong notion of anonymity where the privacy of both the identity of the signer and the message is preserved.

Blind ring signatures find applications in various systems; including multi-authority e-voting and distributed e-cash systems.

In this paper we provide the first provably secure blind ring signature construction that does not rely on random oracles, which solves an open problem raised by Herranz and Laguillaumie at ISC 2006. We present different instantiations all of which are round-optimal (i.e.\\ have a two-move signing protocol), yield sub-linear size signatures, and meet strong security requirements.

In order to realize our constructions efficiently, we construct a sub-linear size set membership proof which works in the different bilinear group settings, which may be of independent interest.

As a secondary contribution, we show how to generically combine our set membership proof with any secure signature scheme meeting some conditions to obtain ring signatures whose security does not rely on random oracles. All our constructions work over the efficient prime-order bilinear group setting and yield signatures of sub-linear size. In addition, our constructions meet strong security requirements: namely, anonymity holds under full key exposure and unforgeability holds against insider-corruption.

Finally, we provide some example instantiations of the generic construction.



03:17 [Pub][ePrint] Invariance-Based Concurrent Error Detection for Advanced Encryption Standard, by Xiaofei Guo and Ramesh Karri

  Naturally occurring and maliciously injected faults reduce the reliability of Advanced Encryption Standard (AES) and may leak confidential information. We developed an invariance-based concurrent error detection (CED) scheme which is independent of the implementation of AES encryption/decryption. Additionally, we improve the security of our scheme with Randomized CED Round Insertion and adaptive checking. Experimental results show that the invariance-based CED scheme detects all single-bit, all single-byte fault, and 99.99999997% of burst faults. The area and delay overheads of this scheme are compared with those of previously reported CED schemes on two Xilinx Virtex FPGAs. The hardware overhead is in the 13.2-27.3% range and the throughput is between 1.8-42.2Gbps depending on the AES architecture, FPGA family, and the detection latency. One can im-

plement our scheme in many ways; designers can trade off performance, reliability, and security according to the available resources.





2013-09-22
14:26 [Job][New] Assistant Professor (Lecturer, Senior Lecturer), Ariel University, Israel

  The Department of Electrical and Electronic Engineering at Ariel University (Israel) invites applications for a tenure-track Lecturer or Senior Lecturer (Assistant Professor) post to begin in 2014. Positions are full-time, tenure-track, with eligible benefits. The candidate will lead a new Cyber Security Program in association with the Center for Homeland Security at Ariel University.



2013-09-19
15:17 [Pub][ePrint] Efficient Pairings Computation on Jacobi Quartic Elliptic Curves, by Sylvain Duquesne, Nadia El Mrabet and Emmanuel Fouotsa

  This paper proposes the computation of the Tate pairing,

Ate pairing and its variations on the special Jacobi quartic elliptic curve

Y^2 = dX^4 +Z^4. We improve the doubling and addition steps in Miller\'s

algorithm to compute the Tate pairing. We use the birational equivalence

between Jacobi quartic curves and Weierstrass curves, together with a

specific point representation to obtain the best result to date among

curves with quartic twists. For the doubling and addition steps in Miller\'s

algorithm for the computation of the Tate pairing, we obtain a theoretical

gain up to 27% and 39%, depending on the embedding degree and the

extension field arithmetic, with respect to Weierstrass curves [2] and

previous results on Jacobi quartic curves [3]. Furthermore and for the

first time, we compute and implement Ate, twisted Ate and optimal

pairings on the Jacobi quartic curves. Our results are up to 27% more

ecient, comparatively to the case of Weierstrass curves with quartic

twists [2].



15:17 [Pub][ePrint] Fuming Acid and Cryptanalysis: Handy Tools for Overcoming a Digital Locking and Access Control System - Full Version, by Daehyun Strobel and Benedikt Driessen and Timo Kasper and Gregor Leander and Da

  We examine the widespread SimonsVoss digital locking system

3060 G2 that relies on an undisclosed, proprietary protocol to mutually authenticate transponders and locks. For assessing the security of the system, several tasks have to be performed: By decapsulating the used microcontrollers with acid and circumventing their read-out protection with UV-C light, the complete program code and data contained in door lock and transponder are extracted. As a second major step, the multi-pass challenge-response protocol and corresponding cryptographic primitives are recovered via low-level reverse-engineering. The primitives turn out to be based on DES in combination with a proprietary construction.

Our analysis pinpoints various security vulnerabilities that enable practical key-recovery attacks. We present two different approaches for unauthorizedly gaining access to installations. Firstly, an attacker having physical access to a door lock can extract a master key, allowing to mimic transponders, in altogether 30 minutes. A second, purely logical attack exploits an implementation flaw in the protocol and works solely via the wireless interface. As the only prerequisite, a valid ID of a transponder needs to be known (or guessed). After executing a few (partial) protocol runs in the vicinity of a door lock, and some seconds of computation, an adversary obtains all of the transponder\'s access rights.



15:17 [Pub][ePrint] Factoring RSA keys from certified smart cards: Coppersmith in the wild, by Daniel J. Bernstein and Yun-An Chang and Chen-Mou Cheng and Li-Ping Chou and Nadia Heninger and Tanja Lange and Nicko van Som

  An attacker can efficiently factor at least 184 distinct 1024-bit RSA keys from Taiwan\'s national \"Citizen Digital Certificate\" database. The big story here is that these keys were generated by government-issued smart cards that were certified secure. The certificates had all the usual buzzwords: FIPS certification from NIST (U.S. government) and CSE (Canadian government), and Common Criteria certification from BSI (German government).

These 184 keys include 103 keys that share primes and that are efficiently factored by a batch-GCD computation. This is the same type of computation that was used last year by two independent teams (USENIX Security 2012: Heninger, Durumeric, Wustrow, Halderman; Crypto 2012: Lenstra, Hughes, Augier, Bos, Kleinjung, Wachter) to factor tens of thousands of cryptographic keys on the Internet.

The remaining 81 keys do not share primes. Factoring these 81 keys requires taking deeper advantage of randomness-generation failures: first using the shared primes as a springboard to characterize the failures, and then using Coppersmith-type partial-key-recovery attacks. This is the first successful public application of Coppersmith-type attacks to keys found in the wild.