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).

2015-06-05
03:28 [PhD][New]

Name: Dai Yamamoto
Topic: Security Evaluation and Improvement of Physically Unclonable Functions
Category: implementation

00:17 [Pub][ePrint]

We propose a decentralized cryptocurrency based on a block-chain ledger similar to that of Bitcoin, but where the extremely wasteful proofs of work are replaced by proofs of space, recently introduced by Dziembowski et al. (CRYPTO 2015). Instead of requiring that a majority of the computing power is controlled by honest miners (as in Bitcoin), our currency requires that honest miners dedicate more disk space than a potential adversary.

Once a miner has dedicated and initialized some space, participating in the mining process is very cheap. A new block is added to the chain every fixed period of time (say, every minute), and in every period a miner just has to make a small number of lookups to the stored space to check if she wins\", and thus can add the next block to the chain and get the mining reward. Because this check is cheap, proof-of-space-based currencies share some (but not all) issues with currencies based on proofs of stake\'\', like Peercoin. Concretely, a na\\\"ive solution that simply replaces proofs of work with proofs of space raises two main issues which we address:

\\emph{Grinding:} A miner who can add the next block has some degree of freedom in shaping how the chain looks, e.g. by trying out different sets of transactions to include in her block. The miner can try many possible choices until she finds one which results in a chain that allows her to also mine the next block, thus hijacking the chain forever while dedicating only a small amount of the space. We solve this problem fully by decoupling\" the hash chain from the transactions, so that there is nothing to grind. To bind the transactions back to the hash chain, we add an extra signature chain, which guarantees that past transactions cannot be altered once an honest miner adds a block. Our solution also gives a simple and novel way to solve the grinding problem in currencies based on proofs of stake.

\\emph{Mining multiple chains:} Since checking whether one can add a block is cheap, rational miners will not only try to extend the so-far-best chain, but also try other chains, in the hope that they can extend one of them which will ultimately catch up and overtake the currently-best chain. (In the context of proof-of-stake-based currencies this is known as the nothing-at-stake\" problem.) This not only gives rational miners a larger-than-expected reward (compared to what honest miners get), but also makes consensus very slow, if not impossible. Our solution to this problem is based on penalizing miners who try to work on more than one branch of the chain.

00:17 [Pub][ePrint]

IEEE 802.15.4 is a wireless standard used by a variety of higher-level protocols, including many used in the Internet of Things (IoT). A number of system on a chip (SoC) devices that combine a radio transceiver with a microcontroller are available for use in IEEE 802.15.4 networks. IEEE 802.15.4 supports the use of AES-CCM* for encryption and authentication of messages, and a SoC normally includes an AES accelerator for this purpose. This work measures the leakage characteristics of the AES accelerator on the Atmel ATMega128RFA1, and then demonstrates how this allows recovery of the encryption key from nodes running an IEEE 802.15.4 stack. While this work demonstrates the attack on a specific SoC, the results are also applicable to similar wireless nodes and to protocols built on top of IEEE 802.15.4.

00:17 [Pub][ePrint]

In this paper we analyze the security of the compression function of SHA-1 against collision attacks, or equivalently free-start collisions on the hash function. While a lot of work has been dedicated to the analysis of SHA-1 in the past decade, this is the first time that free-start collisions have been considered for this function.

We exploit the additional freedom provided by this model by using a new start-from-the-middle approach in combination with improvements on the cryptanalysis tools that have been developed for SHA-1 in the recent years. This results in particular in better differential paths than the ones used for hash function collisions so far.

Overall, our attack requires about $2^{50}$ evaluations of the compression function in order to compute a one-block free-start collision for a 76-step reduced version, which is so far the highest number of steps reached for a collision on the SHA-1 compression function. We have developed an efficient GPU framework for the highly branching code typical of a cryptanalytic collision attack and used it in an optimized implementation of our attack on recent GTX-970 GPUs.

We report that a single cheap US$350 GTX-970 is sufficient to find the collision in less than 5 days. This showcases how recent mainstream GPUs seem to be a good platform for expensive and even highly-branching cryptanalysis computations. Finally, our work should be taken as a reminder that cryptanalysis on SHA-1 continues to improve. This is yet another proof that the industry should quickly move away from using this function. 00:17 [Pub][ePrint] We give generic constructions of several fundamental cryptographic primitives based on a new encryption primitive that combines circular security for bit encryption with the so-called reproducibility property (Bellare et al. PKC 2003). At the heart of our constructions is a novel technique which gives a way of de-randomizing reproducible public-key bit-encryption schemes and also a way of reducing one-wayness conditions of a constructed trapdoor-function family (TDF) to circular security of the base scheme. The main primitives that we build from our encryption primitive include k-wise one-way TDFs (Rosen and Segev TCC 2009), CCA2-secure encryption and deterministic encryption. Our results demonstrate a new set of applications of circularly- secure encryption beyond fully-homomorphic encryption and symbolic soundness. Finally, we show the plausibility of our assumptions by showing that the DDH-based circularly-secure scheme of Boneh et al. (Crypto 2008) and the subgroup indistinguishability based scheme of Brakerski and Goldwasser are both reproducible. 00:17 [Pub][ePrint] \\textit{Khudra} is a block cipher proposed in the SPACE\'2014 conference, whose main design goal is to achieve suitability for the increasingly popular Field Programmable Gate Array (FPGA) implementation. It is an 18-round lightweight cipher based on recursive Feistel structure, with a 64-bit block size and 80-bit key size. In this paper, we compute the minimum number of active$F$-functions in differential characteristics in the related-key setting, and give a more accurate measurement of the resistance of \\textit{Khudra} against related-key differential cryptanalysis. We construct a related-key boomerang quartet with probability$2^{-48}$for the 14-round \\textit{Khudra}, which is better than the highest probability related-key boomerang quartet of the 14-round \\textit{Khudra} of probability at most$2^{-72}$claimed by the designers. Then we propose a related-key rectangle attack on the 16-round \\textit{Khudra} without whitening key by constructing a related-key rectangle distinguisher for 12-round \\textit{Khudra} with a probability of$2^{-23.82}$. The attack has time complexity of$2^{78.68}$memory accesses and data complexity of$2^{57.82}\$ chosen plaintexts, and requires only four related keys. This is the best known attack on the round-reduced \\textit{Khudra}.

2015-06-03
22:58 [Job][New]

Applications are invited for a PhD position in the field of cryptography at the Universitat Pompeu Fabra in Barcelona, Spain.

The applicant will join the research group in Wireless Communications and will be co-supervised by Dr. Vanesa Daza and Dr. Carla Ràfols. The topic of research will be interactions between multiparty computation and zero-knowledge proofs.

The candidate should have completed his/her master´s degree by Oct. 2015 in computer science, mathematics or a related area.

The starting date will be around Oct. 2015 and the student will receive a PhD stipend from the Universitat Pompeu Fabra (http://www.upf.edu/dtic_doctorate/_pdf/dtic_upf_phd_calll_2015_16.pdf)

Applications should start with a a short motivation letter, include a full CV, a copy of grade transcript(s) of completed studies and (when possible) one name of reference.

To apply or request further information, please send an email to

cryptoPhDapplications (at) upf.edu. The review of applications will start on June 15th and continue until the position is filled.

2015-06-02
20:30 [Event][New]

Submission: 17 December 2015
From April 13 to April 15
Location: Fes, Morocco

09:17 [Pub][ePrint]

Digital signature is a fundamental primitive with numerous applications. Following the development of pairing-based cryptography, several taking advantage of this setting have been proposed. Among them, the Camenisch-Lysyanskaya (CL) signature scheme is one of the most flexible and has been used as a building block for many other protocols. Unfortunately, this scheme suffers from a linear size in the number of messages to be signed which limits its use in many situations.

In this paper, we propose a new signature scheme with the same features as CL-signatures but without the linear-size drawback: our signature consists of only two elements, whatever the message length, and our algorithms are more efficient. This construction takes advantage of using type 3 pairings, that are already widely used for security and efficiency reasons.

We prove the security of our scheme without random oracles but in the generic group model. Finally, we show that protocols using CL-signatures can easily be instantiated with ours, leading to much more efficient constructions.

09:17 [Pub][ePrint]

We propose new generic key recovery attacks on Feistel-type block ciphers. The

proposed attack is based on the all subkeys recovery approach presented in SAC 2012, which

determines all subkeys instead of the master key. This enables us to construct a key recovery

attack without taking into account a key scheduling function. With our advanced techniques,

we apply several key recovery attacks to Feistel-type block ciphers. For instance, we show

8-, 9- and 11-round key recovery attacks on n-bit Feistel ciphers with 2n-bit key employing

random keyed F-functions, random F-functions, and SP-type F-functions, respectively.

Moreover, thanks to the meet-in-the-middle approach, our attack leads to low-data complexity.

To demonstrate the usefulness of our approach, we show a key recovery attack on the

8-round reduced CAST-128, which is the best attack with respect to the number of attacked

rounds. Since our approach derives the lower bounds on the numbers of rounds to be secure

under the single secret key setting, it can be considered that we unveil the limitation of

designing an efficient block cipher by a Feistel scheme such as a low-latency cipher.