International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) 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).

18:17 [Pub][ePrint] Analysis of the Non-Perfect Table Fuzzy Rainbow Tradeoff, by Byoung-il Kim and Jin Hong

  Time memory tradeoff algorithms are tools for inverting one-way functions, and they are often used to recover passwords from unsalted password hashes. There are many publicly known tradeoff algorithms, and the rainbow tradeoff is widely believed to be the best algorithm. This work provides an accurate complexity analysis of the fuzzy rainbow tradeoff algorithm, which has not yet received much attention. It is shown that when the pre-computation cost and the online efficiency are both taken into consideration, the fuzzy rainbow tradeoff is preferable to the original rainbow tradeoff.

18:17 [Pub][ePrint] Resource-Restricted Indifferentiability, by Grégory Demay and Peter Gazi and Martin Hirt and Ueli Maurer

  The notion of indifferentiability was introduced in [MRH04] and in [CDMP05] it was tailored for security analysis of hash function constructions, making indifferentiability from a random oracle the desired property for any hash function design. However, the widely accepted view that a construction enjoying such a proof with an underlying ideal compression function can replace the random oracle in any application without compromising security is not justified in certain settings, as pointed out recently in [RSS11].

In this paper we argue that one general reason for such a failure is the inflexibility of the indifferentiability notion with respect to more complex restrictions on resources (such as memory, randomness) available to the attacker: Typically, the distinguisher and the simulator in an indifferentiability statement are only required to be PPT algorithms, implicitly posing a polynomial restriction also on the resources available to them. We argue that this is not sufficient in certain scenarios and explain why this is the problem underlying the security breakdown described in [RSS11]. We present a systematic treatment of such settings by proposing a more fine-grained notion of memory-aware reducibility that is necessary in contexts when memory is the resource that requires a more detailed quantification.

We employ this new formalism to prove a lower bound on the memory required by any simulator in a domain extension construction of a public random function. Our results imply that if we restrict to simulators without memory, even domain extension by a single bit becomes impossible. On the other hand, for the infinite extension from an ideal compression function to a random oracle, a memory roughly linear in the total sum of the lengths of all queries is required. This solves an open problem given in [RSS11].

Finally, it follows from our results that for any multi-party setting where one cannot assume the existence of a central adversary and hence it requires to be modeled using an independent local simulator for each party, it is impossible to securely construct a public random oracle from a public ideal compression function.

18:17 [Pub][ePrint] An arithmetic intersection formula for denominators of Igusa class polynomials, by Kristin Lauter and Bianca Viray

  In this paper we prove an explicit formula for an arithmetic intersection number on the Siegel moduli space of abelian surfaces, generalizing the work of Bruinier-Yang and Yang.

These intersection numbers allow one to compute the denominators of Igusa class polynomials, which has important applications to the construction of genus 2 curves for use in cryptography.

Bruinier and Yang conjectured a formula for intersection numbers on an arithmetic Hilbert modular surface, and as a consequence obtained a conjectural formula for the intersection number relevant to denominators of Igusa class polynomials under strong assumptions on the ramification of the primitive quartic CM field K. Yang later proved this conjecture assuming that the ring of integers is freely generated by one element over the ring of integers of the real quadratic subfield. In this paper, we prove a formula for the intersection number for more general primitive quartic CM fields, and we use a different method of proof than Yang. We prove a tight bound on this intersection number which holds for all primitive quartic CM fields. As a consequence, we obtain a formula for a multiple of the denominators of the Igusa class polynomials for an arbitrary primitive quartic CM field. Our proof entails studying the Embedding Problem posed by Goren and Lauter and counting solutions using our previous article that generalized work of Gross-Zagier and Dorman to arbitrary discriminants.

18:17 [Pub][ePrint] Polynomial time cryptanalysis of noncommutative-algebraic key exchange protocols, by Boaz Tsaban

  We introduce the \\emph{linear centralizer method} for a passive adversary

to extract the shared key in group-theory based key exchange protocols (KEPs).

We apply this method to obtain a polynomial time cryptanalysis of the

\\emph{Commutator KEP}, introduced by Anshel--Anshel--Goldfeld in 1999 and considered

extensively ever since.

We also apply this method to the \\emph{Centralizer KEP}, introduced by Shpilrain--Ushakov in 2006.

Our method is proved to be of polynomial time using a technical lemma

about sampling invertible matrices from a linear space of matrices.

18:17 [Pub][ePrint] Hardness Preserving Constructions of Pseudorandom Functions, Revisited, by Nishanth Chandran and Sanjam Garg

  We revisit hardness-preserving constructions of a PRF from any length doubling PRG when there is a non-trivial upper bound $q$ on the number of queries that the adversary can make to the PRF. Very recently, Jain, Pietrzak, and Tentes (TCC 2012) gave a hardness-preserving construction of a PRF that makes only $O(\\log q)$ calls to the underlying PRG when $q = 2^{n^\\epsilon}$ and $\\epsilon \\geq \\frac{1}{2}$. This dramatically improves upon the efficiency of the GGM construction. However, they explicitly left open the question of whether such constructions exist when $\\epsilon < \\frac{1}{2}$. In this work, we make progress towards answering this question. In particular we give constructions of PRFs that make only $O(\\log q)$ calls to the underlying PRG even when $q = 2^{n^\\epsilon}$, for $0

18:17 [Pub][ePrint] Security Analysis of an Open Car Immobilizer Protocol Stack, by Stefan Tillich and Marcin W\\\'{o}jcik

  An increasing number of embedded security applications---which traditionally have been heavily reliant on secret and/or proprietary solutions---apply the principle of open evaluation. A recent example is the specification of an open security protocol stack for car immobilizer applications by Atmel, which has been presented at ESCAR 2010. This stack is primarily intended to be used in conjunction with automotive transponder chips of this manufacturer, but could in principle be deployed on any suitable type of transponder chip. In this paper we re-evaluate the security of this protocol stack. We were able to uncover a number of security vulnerabilities. We show that an attacker with a cheap standard reader close to such a car key can track it, lock sections of its EEPROM, and even render its immobilizer functionality completely useless. After eavesdropping on a genuine run of the authentication protocol between the car key and the car, an attacker is enabled to read and write the memory of the car key. Furthermore, we point out the threats of relay attacks and session hijacking, which require slightly more elaborate attack setups. For each of the indicated attacks we propose possible fixes and discuss their overhead.

18:17 [Pub][ePrint] Towards fully collusion-resistant ID-based establishment of pairwise keys, by Oscar Garcia Morchon and Ludo Tolhuizen and Domingo Gomez and Jaime Gutierrez

  Usually a communication link is securedby means of a symmetric-key algorithm. For that, amethod is required to securely establish a symmetric key for that algorithm. This old key establishment

problem is still relevant and of paramount importance both in existing computer networks and new large-scale ubiquitous systems comprising resource-constrained devices.

Identity-based pairwise key agreement allows for the generation of a common key between two parties given a secret keying material

owned by the first party and the identity of the second one. However, existing methods, e.g., based on polynomials, are prone to collusion attacks.

In this paper we discuss a new key establishment scheme aiming at fully collusion-resistant identity-based symmetric-key agreement. Our scheme, the HIMMO algorithm, relies on two design concepts:

Hiding Information and Mixing Modular Operations. Collusion attacks on schemes from literature cannot readily be applied to our scheme; our security analysis further shows that HIMMO\'s design principles

prevent an attacker from performing a number of attacks.

Also, the simple logic of the HIMMO algorithm allows for very efficient implementations in terms of both speed and memory. Finally, being an identitybasedsymmetric-key establishment scheme, HIMMO allows for efficient real-world key exchange protocols.

10:21 [Event][New] SPW 2013: Twenty-first International Workshop on Security Protocols

  Submission: 7 January 2013
Notification: 31 January 2013
From March 18 to March 20
Location: Cambridge, England
More Information:

00:17 [Pub][JoC] FlipIt: The Game of “Stealthy Takeover”


Abstract  Recent targeted attacks have increased significantly in sophistication, undermining the fundamental assumptions on which most cryptographic primitives rely for security. For instance, attackers launching an Advanced Persistent Threat (APT) can steal full cryptographic keys, violating the very secrecy of “secret” keys that cryptographers assume in designing secure protocols. In this article, we introduce a game-theoretic framework for modeling various computer security scenarios prevalent today, including targeted attacks. We are particularly interested in situations in which an attacker periodically compromises a system or critical resource completely, learns all its secret information and is not immediately detected by the system owner or defender. We propose a two-player game between an attacker and defender called FlipIt or The Game of “Stealthy Takeover.” In FlipIt, players compete to control a shared resource. Unlike most existing games, FlipIt allows players to move at any given time, taking control of the resource. The identity of the player controlling the resource, however, is not revealed until a player actually moves. To move, a player pays a certain move cost. The objective of each player is to control the resource a large fraction of time, while minimizing his total move cost. FlipIt provides a simple and elegant framework in which we can formally reason about the interaction between attackers and defenders in practical scenarios. In this article, we restrict ourselves to games in which one of the players (the defender) plays with a renewal strategy, one in which the intervals between consecutive moves are chosen independently and uniformly at random from a fixed probability distribution. We consider attacker strategies ranging in increasing sophistication from simple periodic strategies (with moves spaced at equal time intervals) to more complex adaptive strategies, in which moves are determined based on feedback received during the game. For different classes of strategies employed by the attacker, we determine strongly dominant strategies for both players (when they exist), strategies that achieve higher benefit than all other strategies in a particular class. When strongly dominant strategies do not exist, our goal is to characterize the residual game consisting of strategies that are not strongly dominated by other strategies. We also prove equivalence or strict inclusion of certain classes of strategies under different conditions. Our analysis of different FlipIt variants teaches cryptographers, system designers, and the community at large some valuable lessons: 1.  Systems should be designed under the assumption of repeated total compromise, including theft of cryptographic keys. FlipIt provides guidance on how to implement a cost-effective defensive strategy. 2.  Aggressive play by one player can motivate the opponent to drop out of the game (essentially not to play at all). Therefore, moving fast is a good defensive strategy, but it can only be implemented if move costs are low. We believe that virtualization has a huge potential in this respect. 3.  Close monitoring of one’s resources is beneficial in detecting potential attacks faster, gaining insight into attacker’s strategies, and scheduling defensive moves more effectively. Interestingly, FlipIt finds applications in other security realms besides modeling of targeted attacks. Examples include cryptographic key rotation, password changing policies, refreshing virtual machines, and cloud auditing.

  • Content Type Journal Article
  • Pages 1-59
  • DOI 10.1007/s00145-012-9134-5
  • Authors

    • Marten van Dijk, RSA Laboratories, Cambridge, MA, USA
    • Ari Juels, RSA Laboratories, Cambridge, MA, USA
    • Alina Oprea, RSA Laboratories, Cambridge, MA, USA
    • Ronald L. Rivest, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA

    • Journal Journal of Cryptology
    • Online ISSN 1432-1378
    • Print ISSN 0933-2790

From: Fri, 26 Oct 2012 12:00:56 GMT

15:17 [Pub][ePrint] Quantum-Secure Message Authentication Codes, by Dan Boneh and Mark Zhandry

  We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary\'s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder to prove than its classical analogue. Next, we show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, we present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but we prove that a four-wise independent family is sufficient for one-time security.

15:17 [Pub][ePrint] Graph-Theoretic Algorithms for the ``Isomorphism of Polynomials\'\' Problem, by Charles Bouillaguet and Pierre-Alain Fouque and Amandine Véber

  We give three new algorithms to solve the ``isomorphism of

polynomial\'\' problem, which was underlying the hardness of

recovering the secret-key in some multivariate trapdoor one-way

functions. In this problem, the adversary is given two quadratic

functions, with the promise that they are equal up to linear changes

of coordinates. Her objective is to compute these changes of

coordinates, a task which is known to be harder than

Graph-Isomorphism. Our new algorithm build on previous work in a

novel way. Exploiting the birthday paradox, we break instances of

the problem in time $q^{2n/3}$ (rigorously) and $q^{n/2}$

(heuristically), where $q^n$ is the time needed to invert the

quadratic trapdoor function by exhaustive search. These results are

obtained by turning the algebraic problem into a combinatorial one,

namely that of recovering partial information on an isomorphism

between two exponentially large graphs. These graphs, derived from

the quadratic functions, are new tools in multivariate cryptanalysis.